双链表存储结构:
要建立双链表,首先要明白双链表的存储结构定义:
typedef struct DLinkList{ //存储结构定义
int data;
DLinkList * prior;
DLinkList * next;
}
思想:
从一个空表开始,读取数组a中的元素,生成新节点。将读取在节点的数据域,然后将节点插入到当前链表的表头上,在头结点后,首结点之前。 直到结束为止
思路:
1.创建一个头结点 L 并将前驱指针和后继指针都置为零
2.通过for循环,将一个个元素读取,并保存数据域中,并插入到链表中。
总结:
这里有两个指针域,与单链表不同(只有一个指针域),所以这里要改动四处,前后各两个(单链表只改动两个)
C代码实现:
void CreateDListF(DLinkList *& L,int a[],int n){
DLinkList * s; int i;
L = (DLinkList *)malloc(sizeof(DLinkList));
L->next = L->prior = null; //将前后指针域置为空
for(int i = 0; i < n; i++){
s = (DLinkList *)malloc(sizeof(DLinkList));
s->next = L->next; //这两个为后继指针的
if(L->next != null){
L->next->prior = s;
}
L->next = s; //这两个为前驱指针的
s->prior = L;
}
}