数据结构双链表

双向链表(Double Linked List)(详情请看这里

双(向)链表中有两条方向不同的链,即每个结点中除next域存放后继结点地址外,还增加一个指向其直接前趋的指针域prior。

tip:
①双链表由头指针head惟一确定的。
②带头结点的双链表的某些运算变得方便。
③将头结点和尾结点链接起来,为双(向)循环链表。

双向链表的结点结构和形式描述

[cce_cpp]
typedef struct dlistnode{
DataType data;//数据类型
struct dlistnode *prior,*next; //定义前驱和后继结点指针
}DListNode;
typedef DListNode *DLinkList;
DLinkList head;
[/cce_cpp]

双链表的删除、插入操作:

由于双链表的对称性,在双链表能能方便地完成各种插入、删除操作。(源代码参考了这位同学

VS2008编译 运行通过

[cce_cpp]
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
typedef struct node //定义双链表
{
int data;
struct node *prior;
struct node *next;
}snode;

snode *creat() //创建双链表
{
snode *head, *p, *q;
int x;
head = (snode *)malloc(sizeof(snode));//分配内存空间
q = head;//head 和p指向头指针
printf("请输入创建双链表的值,以-1结束. ");
printf("x = ");
scanf("%d", &x);
while (x != -1)
{
p = (snode *)malloc(sizeof(snode));//创建一个新的结点
p->data = x;//输入数据
q->next = p;//head头结点的next存储下一个结点的首地址
p->prior = q;//新结点的prior存储前一个结点的首地址
q = p;//将q移动到新的结点
printf("x = ");
scanf("%d", &x);
}
q->next = NULL;//将新结点的next置空
return head;//返回头指针
}

void display(snode *head)//显示数据
{
snode *p = head->next;//将p移动到头指针
while (p != NULL)//循环输出数据
{
printf("%4d", p->data);
p = p->next;//移动到下一个结点
}
printf(" ");
}

int length(snode *head)//测链表的结点数
{
snode *p = head->next;
int i = 0;
while (p != NULL)
{
p = p->next;//移动到下一个结点
i++;
}
return i;
}

void opposite(snode *head)//反向输出
{
snode *p = head->next;
while (p->next != NULL)
p = p->next;//将p移动到倒数第二个结点
while (p != head)
{
printf("%4d", p->data);
p = p->prior;//移动指针
}
printf(" ");
}

int insnode(snode *head, int x, int i) //把x插入到链表的第i的位置
{
snode *p = head->next, *s;
if(i < 1 || i > length(head) + 1)
return 0;
else if (i == 1)//插入head中间结点
{
s = (snode *)malloc(sizeof(snode)); //分配内存
s->next = p;//结点s的next存储p所指向结点的首地址
p->prior = s;//p所指向结点的prior存储结点s的首地址
s->prior = head;//结点s的next存储head结点的首地址
head->next = s;//head结点的next存储结点s的首地址
s->data = x;//赋值
}
else//在中间插入
{
s = (snode *)malloc(sizeof(snode)); //分配内存
for (int j = 1; j < i - 1; j++)
p = p->next;//移动到要插入的结点
if (p->next != NULL)
{
s->next = p->next;//将结点s的next指向p所指向结点的下一个结点
p->next->prior = s;//p所指向结点的下一个结点的prior指向s的首地址
p->next = s;//p所指的结点的next指新插入的s结点
s->prior = p;//结点s的prior指向前一个结点的首地址
s->data = x;
}
else//在结尾插入
{
s->next = NULL;//s是最后一个结点 将next置空
p->next = s;//将p结点的next指向s的首地址
s->prior = p;//将结点s的prior指向前一结点的首地址
s->data = x;
}
}
return 1;
}

int delnode(snode *head, int i)//删除链表中第i个结点
{
snode *p = head->next, *q = head;
if(i < 1 || i > length(head))
return 0;
else
{
for (int j = 1; j < i; j++)
{
p = p->next;//找到结点
q = q->next;//找到删除的前一结点
}
if (p->next != NULL)
{
q->next = p->next;//删除的结点的后一结点的首地址赋值给删除的结点的前一结点的next
p->next->prior = q;//删除的结点的后一结点的prior指向删除的结点的前一结点的首地址
}
else//删除尾结点
q->next = p->next;//置空最后一个结点
free(p);
}
return 1;
}
int main()
{
snode *headl = creat(); //创建双链表
printf("最初的链表如下: ");
display(headl);
printf("\n为了证明是双链表反向输出: ");
opposite(headl);
int num, location;
printf("\n请分别输入您要插入到链表中的数以及想插入的位置:");
scanf("%d %d", &num, &location);
if (insnode(headl, num, location))
{
printf("插入新值以后的链表如下: ");
display(headl);
printf("\n为了证明插入新值以后仍然是双链表,反向输出如下: ");
opposite(headl);
}
else
printf("输入有误 ");
printf("\n请输入您想删除的结点位置:");
scanf("%d", &location);
if (delnode(headl, location))
{
printf("删除第%d个结点后的链表如下: ", location);
display(headl);
printf("\n为了证明删除一个结点以后仍然是双链表,反向输出如下: ");
opposite(headl);
}
else
printf("输入有误! ");
system("pause");
}
[/cce_cpp]
打赏作者

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注