赞
踩
双向链表与单向链表的结构类似,但多了一个指向前驱结点的指针。此外空的双向链表的指针域需要特别注意。
双向链表可以有效提高算法的时间性能,说白了就是以空间换取时间。
此外,双向链表也可以有循环链表。
双向链表的初始化如下:
- #include"stdio.h"
- #include"stdlib.h"
- typedef int ElemType;
- typedef struct DualNode
- {
- ElemType data;
- struct DualNode* prior; //前驱结点
- struct DualNode* next; //后继结点
- }DualNode, * DualLinkList;
- int InitList(DualLinkList* L, int LinkSize)
- {
- //生成还有多少个结点的双向链表
- DualNode* p, * q;
- int i;
- *L = (DualLinkList)malloc(sizeof(DualNode));
- if (!(*L))
- return 0;
- (*L)->next = NULL;
- (*L)->prior = NULL;
- p = (*L);
- for (int i = 0; i < LinkSize; i++)
- {
- q = (DualNode*)malloc(sizeof(DualNode));
- if (!(q))
- return 0;
- q->data = 0; //结点赋值,初值暂定为0
- q->prior = p;
- q->next = p->next;
- p->next = q;
-
- p = q; //更新p的位置
- }
- //如果想构建循环链表
- //p->next = (*L)->next;
- //(*L)->next->prior = p;
- }
插入操作需要一个顺序,该顺序不能违反。如果要在第P个位置插入一个新节点,则:
1、首先新建结点s的后继结点应当指向位置P的结点
s->next=p;
2、新建结点s的前驱结点应当指向位置P的上一个结点
s->prior=p->prior;
3、修改P位置上一个结点的指针域,上一个结点的后继结点需要指向s
p->prior->next=s;
4、修改P位置的结点的指针,该节点的前驱结点要修改为s
p->prior=s;
- int InsetDualLinkList(DualLinkList* L, int posi, ElemType n)
- {
- //插入在位置posi
- DualNode* p, * s;
- p = *L;
- int i = 1;
- //找到第posi个结点
- while (p && i < posi)
- {
- p = p->next;
- i++;
- }
- if (!p || i > posi)
- return 0;
- //创建待插入结点
- s = (DualNode*)malloc(sizeof(DualNode));
- s->data = n;
- //更新指针域
- s->next = p;
- s->prior = p->prior;
- p->prior->next = s;
- p->prior = s;
- return 1;
- }
1、首先完成待删除结点P的上下两个结点的指针更新,包括:
p->prior->next=p->next;
p->next->prior=p->prior;
2、更新完成后释放P结点的空间
Free(p);
- int DeleteDualLinkList(DualLinkList* L, int posi, ElemType *n)
- {
- //删除位置posi的结点,其值返回在n里
- DualNode* p;
- int i = 1;
- p = *L;
- //找到posi位置
- if (!p && i < posi)
- {
- p = p->next;
- i++;
- }
- if (!p || i > posi)
- return 0;
- //更新指针域,释放空间
- p->prior->next = p->next;
- p->next->prior = p->prior;
- *n = p->data;
- free(p);
- return true;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。