/************************************************************************/
/* 数据结构：双向链表 */
/* 挑灯看剑-shuchangs@126.com 2010-10 */
/* 云歌国际（Cloud Singers International） www.cocoral.com */
/************************************************************************/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include "core.h"
typedef struct NODE
{
int data; //数据域
struct NODE* next; //后继结点
struct NODE* prior; //前驱结点
}Node, * NodePointer;
//描述线性链表的头结点
typedef struct
{
int len; //记录结点长度
struct NODE* head; //记录第一个结点
struct NODE* tail;//记录最后一个结点
}NodeHead;
void main()
{
/***************函数原型【开始】*************************/
void NodeInsert(NodeHead* H, int i, int e);
void NodePrint(NodeHead H, char tag);
void autoList(NodeHead* H, int n);
Status NodeDelete(NodeHead* H, int i, Node* N);
/***************函数原型【结束】*************************/
//初始化线性链表头元
NodeHead H =
{
0, NULL, NULL
};
Node N =
{
0, NULL, NULL
};
int i = 0, j = 0, e = 0;
char tag = 'Y';
NodePrint(H, 'H');
autoList(&H, 10); //自动化链表
NodePrint(H, 'h'); //正向打印测试
NodePrint(H, 't'); //反向打印测试
/*
//动态创建双向链表
puts("请输入插入元素位置和元素值！");
scanf("%d %d %c", &i, &e, &tag);
while (tag == 'Y')
{
NodeInsert(&H, i, e);
NodePrint(H,'H');
NodePrint(H,'T');
puts("请输入插入元素位置和元素值！");
scanf("%d %d %c", &i, &e, &tag);
}
*/
//执行删除操作
for (j = 0; j < 5; j++)
{
puts("请输入要删除结点的位置：");
scanf("%d", &i);
if (NodeDelete(&H, i, &N))
{
puts("删除成功！");
if (N.next && N.prior)
{
printf("删除当前结点值：%d，其前驱结点值：%d，后继结点值：%d\n",
N.data, N.prior->data, N.next->data);
}
else
{
printf("删除当前结点值：%d\n", N.data);
}
NodePrint(H, 'H');
NodePrint(H, 't');
}
}
}
//在线性链表的第i个位置前面插入元素e
void NodeInsert(NodeHead* H, int i, int e)
{
static Status NodeIsEmpty(NodeHead H); //函数原型
NodePointer p = NULL, q = NULL;//遍历指针
COUNT j = 0; //计数器
NodePointer s = (NodePointer) malloc(sizeof(Node));//为新结点分配存储空间
s->data = e;
//插入前预检查
if (!NodeIsEmpty(*H)) //如果链表非空
{
if (i == 1) //如果i等于1
{
p = H->head;//p指向第一个结点，在p的前面插入，只需处理p前面的指针
p->prior = s; //p的后继结点保持不变
s->next = p;
s->prior = NULL;
H->head = s;
//+++++++++++链表的尾结点重设指向次尾结点++++++++++
//查找次尾结点
for (p = H->head,j = 1; j <= H->len - 2; j++)
p = p->next;
//重设尾结点前驱指针
H->tail->prior = p;
//+++++++++++++++++++++++++++++++++++++++++++++++++
H->len += 1; //长度加1
puts("插入成功！");
}
else if (i >= 2 && i <= H->len) //如果i在2-Len区间
{
//查找第i-1个结点
p = H->head;//p指向第一个结点
//q = H->tail;//q指向最后一个结点
for (j = 2;
j <= i - 1;
j++) //p初始化指向第1个元素，因此循环次数为i-1次
p = p->next; //p前进一位，直到指向第i-1个结点
//执行插入操作
s->next = p->next;
s->prior = p;
p->next = s; //在p的后面插入，其前驱指针不变
H->len += 1;//长度加1
//-----------处理头元-尾结点-----------------------
for (p = H->head; p != NULL; p = p->next)
H->tail = p;
//-------------------------------------------------
//+++++++++++链表的尾结点重设指向次尾结点++++++++++
//查找次尾结点
for (p = H->head,j = 1; j <= H->len - 2; j++)
p = p->next;
//重设尾结点前驱指针
H->tail->prior = p;
//+++++++++++++++++++++++++++++++++++++++++++++++++
puts("插入成功！");
//NodePrint(*H, 'H');
}
else
{
printf("当前区间：1-%d，插入位置为：%d\n", H->len, i);
puts("插入位置越界，默认为链表中的第一个结点！");
p = H->head;//p指向第一个结点，在p的前面插入，只需处理p前面的指针
p->prior = s; //p的后继结点保持不变
s->next = p;
s->prior = NULL;
H->head = s; //链表的尾结点保持不变
H->len += 1; //长度加1
//-----------处理头元-尾结点-----------------------
for (p = H->head; p != NULL; p = p->next)
H->tail = p;
//-------------------------------------------------
//+++++++++++链表的尾结点重设指向次尾结点++++++++++
//查找次尾结点
for (p = H->head,j = 1; j <= H->len - 2; j++)
p = p->next;
//重设尾结点前驱指针
H->tail->prior = p;
//+++++++++++++++++++++++++++++++++++++++++++++++++
puts("插入成功！");
}
}
else
{
printf("插入前链表为空，插入元素 e=%d 默认为第一个结点！\n", s->data);
H->head = H->tail = s; //头指针和尾指针均指向新插入结点
H->len = 1;
s->next = s->prior = NULL; //后继结点和前驱结点均为NULL
puts("插入成功！");
}
}
/*
* 判断结点是否为空
*/
static Status NodeIsEmpty(NodeHead H)
{
if (H.len == 0 || H.head == NULL || H.tail == NULL)
return TRUE;
else
return FALSE;
}
//以下内容见版面《数据结构：双向链表2》
分享到：
相关推荐
数据结构：双向链表的基本程序
双向链表是一种重要的线性数据结构，与单向链表相比，它提供了更灵活的访问和操作方式。本文将深入探讨双向链表的概念、结构以及其源码实现。 双向链表的每个节点不仅包含数据元素，还包含两个指针，一个指向前一个...
数据结构中的双向链表是一种线性数据结构，与单向链表不同，它在每个节点中不仅包含指向下一个节点的指针，还包含一个指向前一个节点的指针。这使得双向链表支持双向遍历，增加了操作的灵活性。本文将深入探讨C++中...
双向链表是一种特殊的数据结构，它在编程中具有重要的应用。本文将深入探讨双向链表的概念，实现，以及如何进行基本操作。 双向链表，顾名思义，是一种链式存储结构，其中每个节点包含两个指针，一个指向前一个节点...
双向链表是一种特殊的数据结构，它在计算机程序设计中扮演着重要角色，特别是在C++这样的编程语言中。本节将深入探讨双向链表的概念、其结构、操作以及C++中的实现。 双向链表与单链表不同，它允许每个节点不仅有一...
双向链表是数据结构中的一种，尤其在处理需要前后移动元素的问题时，它的优势尤为突出。本篇文章将详细探讨双向链表的基本概念、结构以及实现，旨在帮助初学者理解并掌握这一重要知识点。 双向链表是一种线性数据...
双向链表是一种重要的线性数据结构，与常见的单向链表相比，它具有更丰富的操作能力。本文将深入探讨双向链表的概念、特点、实现方式以及在给定的“DoubleLink”压缩包中可能包含的相关功能。 双向链表（Doubly ...
双向链表是一种重要的线性数据结构，它扩展了单链表的概念，允许在数据元素之间进行双向链接。这种数据结构使得在链表中的前一个和后一个元素之间进行导航变得容易。 双向链表的每个节点包含三部分：数据域、前向...
在C语言中，双向链表是一种非常重要的数据结构，它扩展了单链表的概念，使得在链表中的每个节点不仅可以指向下一个节点，还可以指向前一个节点。这使得在链表中进行前向和后向遍历变得十分方便，且在插入和删除操作...
本讲座主要探讨了一种特殊的数据结构——双向链表。双向链表是一种线性数据结构，它允许我们在列表中的节点之间进行双向移动，而不仅仅像单链表那样只能从前往后或从后往前。 双向链表的定义： 双向链表是由一系列...
### 数据结构源代码之双向链表 #### 概述 本文档主要介绍如何通过C语言实现双向链表的基本操作。继单链表之后，双向链表作为一种更灵活的数据结构，支持从前向后以及从后向前的遍历。双向链表在每个节点中除了包含...
在计算机科学和编程领域，理解并能够实现单向链表的源码是至关重要的，因为它是构建更复杂数据结构（如双向链表、循环链表等）的基础。 在单向链表中，每个节点有两个部分：数据域和指针域。数据域存储实际的数据，...
双向链表是一种常用的数据结构，它可以满足更加方便的查找前驱，而付出空间的代价。双向链表的节点定义如下： typedef struct node { int x; struct node *prior, *next; } DLNode; 双向链表的空间结构如下图所...
双向链表是一种重要的线性数据结构，它在很多编程任务中都有广泛的应用。本课程设计主要关注双向链表的实现及其排序算法，这对于理解和掌握数据结构至关重要。 双向链表与单向链表不同，每个节点不仅包含数据，还...
在这个"数据结构之双向链表(完整版)"的资源中，你将找到关于双向链表的详细实现和实际应用。 双向链表的结构由一系列节点组成，每个节点包含数据元素和两个指针，一个指向前一个节点（prev），另一个指向后一个节点...
1. **节点结构**：双向链表的节点包含三个字段：数据、向前的指针和向后的指针。 2. **链表头尾**：双向链表有头节点和尾节点，头节点的前一个节点是null，而尾节点的后一个节点也是null。 3. **插入操作**：在...
以上就是关于双向链表建立、遍历和插入节点的基本操作，这些基本操作构成了双向链表操作的基础，是理解和实现更复杂数据结构算法的关键。通过熟悉这些操作，开发者可以在实际项目中灵活运用双向链表，提高程序的效率...
总结起来，C语言中的双向链表是一种实用的数据结构，它通过增加对前一个节点的引用，增强了链表的灵活性。理解和掌握如何在C语言中创建、操作和管理双向链表是提高编程技能的关键一步，尤其对于处理需要频繁插入、...
在计算机科学领域，数据结构是组织和管理数据的重要方式，而双向链表是其中一种基本的数据结构。双向链表与单向链表不同，它在每个节点中存储了两个指针，一个指向前一个节点，另一个指向后一个节点，使得在链表中...