/************************************************************************/
/* 数据结构：双向链表 */
/* 挑灯看剑-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》
分享到：
相关推荐
数据结构：双向链表源码，为了让读者有更好的体验，把源码上传上去，有任何问题，或者有任何bug可以直接私信我，我会及时回复，并且解决对应问题
数据结构：双向链表的基本程序
数据结构：双向链表的实现和测试(C++).doc
完整双向链表的实现代码，包括了线性表的基本操作:插入、删除、访问和查找
数据结构 双向链表存储 附带基础处理函数 附带测试函数
数据结构双向链表代码，代码结构清晰，很容易读懂，适合初学者学习，100%原装代码。
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
从初学者的角度深入的分析了内核数据结构的双向循环链表 list_head结构如何构建链表 分析了list_entry LIST_HEAD list_for_each 并最后给出了一个例子以便学习
数据结构 双向链表的实现
数据结构大作业，c++用双向链表实现约瑟夫环，内含.h与.cpp
双向链表 建立 遍历 插入一个结点 数据结构双向链表的相关操作（C语言版）
数据结构中的双向链表的代码实现，对初学者有帮助
JavaScript数据结构之双向链表 单向链表在遍历时只能从头到尾或者从尾遍历到头；所以单向链表可以轻松到达下一节点，但是回到上一个节点是很困难的 而双向链表既可以从头遍历到尾, 又可以从尾遍历到头，链表的...
这是一个双向链表的实现，集成了删除、添加以及迭代功能
C语言实现数据结构：单链表，循环链表，双向链表；静态顺序队列，动态顺序队列，链式队列；静态顺序栈，动态顺序栈，链式栈；二叉树，线索二叉树；排序算
用数据结构双向链表的只是实现了求集合的交集并集。
双向链表（数据结构课程设计），有做课程设计的很有用啊
继数据结构源代码之单链表后，双线性链表的C代码实现