您现在的位置是:网站首页> 内容页

数据结构与算法----双向链表

  • u乐平台手机客户端
  • 2019-03-25
  • 214人已阅读
简介PS:前面已经说过线性表的两种表现形式,一种是顺序,另一种是链式,链式的一种普通表现形式就是加入一个指针,前一个的指针指向后一个结点的地址,那么还有一种形式就是双向链表,里面又加上了一

PS:前面已经说过线性表的两种表现形式,一种是顺序,另一种是链式,链式的一种普通表现形式就是加入一个指针,前一个的指针指向后一个结点的地址,那么还有一种形式就是双向链表,里面又加上了一个指针变量,让前指针变量指向直接前驱,后指针变量指向直接后继。

/** * 创建结构体 * */typedef struct DoubleLink { int data; struct DoubleLink *prior; struct DoubleLink *next;} DoubleLink, *DoubleLinkL;

创建双向链表并初始化

注:这里我们是只创建了一个空的链表,内部无数据,所以首结点的两个指针变量要为NULL。

/** * 初始化 * */DoubleLinkL initLink() { DoubleLinkL L = (DoubleLinkL) malloc(sizeof(DoubleLink)); L->next = NULL; L->prior = NULL; return L;}

开始插入数据

在插入数据之前我们要考虑一个事情就是,链表中有数据和无数据的插入是否一样,也就是说指针改变是否一致,在左右都有值的时候平时要改变4条线,那么如果只有首结点的话移动几条呢。

其实可以说是移动3条,但画图的话就看到两条。

如图:

::|::

 

首先当只要一个首结点或者在最后一个结点插入的情况下,如第一个图,

     s->next = p->next; s->prior = p; p->next = s;

当前后都有结点的时候,如第二个图

     s->next = p->next; s->prior = p; p->next = s; s->next->prior = s;

整体插入代码就是

int insertLink(DoubleLinkL &L, int pos, int e) { DoubleLinkL p = L; int i = 0; while (p && i < pos-1) { p = p->next; i++; } if (!p || i > pos-1) { printf("插入失败,下标问题"); return -1; } DoubleLinkL s = (DoubleLinkL) malloc(sizeof(DoubleLink)); s->data = e; if (p->next == NULL) { s->next = p->next; s->prior = p; p->next = s; } else { s->next = p->next; s->prior = p; p->next = s; s->next->prior = s; } return 0;}

删除图解

对于删除比较简单,在前后都有结点的情况下,如图一,如果本来只要一个结点,前面是首结点的情况下,直接把首结点的next指向NULL即可。(本人画图不怎么样不要在意)

 

p->next->next->prior=p;//一定要写在该位置。p->next=p->next->next;

如果首结点后只有一个结点

p->next=NULL;

删除全部代码

int deleteLink(DoubleLinkL &L,int pos,int e){ DoubleLinkL p = L; int i = 0; while (p && i < pos-1) { p = p->next; i++; } if (!p || i > pos-1) { printf("插入失败,下标问题"); return -1; } if(p->next==NULL){ p->next=NULL; }else{ p->next->next->prior=p;//一定要写在该位置。 p->next=p->next->next; } return 0; }

修改和查找

这个修改和查找是比较简单的,直接找到知道该结点修改就完事了,干就对了。

int getElem(DoubleLinkL L,int pos){ DoubleLinkL p = L; int i = 0; while (p && i < pos) { p = p->next; i++; } if (!p || i > pos) { printf("查找失败,下标问题"); return -1; } printf("查找的数据:%d",p->data); return 0; } int updataLink(DoubleLinkL &L,int pos,int e){ DoubleLinkL p = L; int i = 0; while (p && i < pos) { p = p->next; i++; } if (!p || i > pos) { printf("修改失败,下标问题"); return -1; } p->data=e; return 0; }

总结:双向链表主要是插入和删除复杂点,其他的和单链表都差不多,双向链表存在着4条指向线先后顺序,如果连接顺序不正确,断开后的数据就会丢失。

 

, 1, 0, 9);

文章评论

Top