PS:前面已经说过线性表的两种表现形式,一种是顺序,另一种是链式,链式的一种普通表现形式就是加入一个指针,前一个的指针指向后一个结点的地址,那么还有一种形式就是双向链表,里面又加上了一个指针变量,让前指针变量指向直接前驱,后指针变量指向直接后继。
/**
* 创建结构体
* */
typedef struct DoubleLink {
int data;
struct DoubleLink *prior;
struct DoubleLink *next;
} DoubleLink, *DoubleLinkL;
/**
* 初始化
* */
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("插入失败,下标问题\n");
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("插入失败,下标问题\n");
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("查找失败,下标问题\n");
return -1;
}
printf("查找的数据:%d\n",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("修改失败,下标问题\n");
return -1;
}
p->data=e;
return 0;
}