雙向鏈表就是在單項鏈表的基礎上增加了一個前向指針域。基本操作還是一樣的，該雙向鏈表是帶有頭節點的，最后一個節點的next指針域是為空的，不是指向首節點的。
雙向鏈表的結構定義
~~~
typedef char datatype;
typedef struct node
{
datatype data;
struct node *prior, *next;
}linknode;
typedef linknode *linklist;
~~~
創建一個鏈表
~~~
linklist CreatDlist(void)
{
char ch;
linklist head;
linknode *p, *h, *r;
head = (linknode *)malloc(sizeof(linknode));
head->next = NULL;
h = head;
r = head;
while((ch = getchar()) != '\n')
{
p = (linknode *)malloc(sizeof(linknode));
p->data = ch;
p->next = NULL;
if(r == head)
{
r->next = p;
}
else
{
r->next = p;
r->prior = h;
h = h->next;
}
r = p;
}
return head;
}
~~~
找到鏈表中一個節點
~~~
linknode * GetNode(linklist head, int i)
{
linknode *p = head;
int j = 0;
while(p && j<i)
{
p = p->next;
j++;
}
return p;
}
~~~
插入一個節點
~~~
void InsetDlist(linklist head, datatype ch, int i)
{
linknode *p = head->next, *t;
int j = 0;
while(p && j < i-1)
{
p = p->next;
j++;
}
t = (linknode *)malloc(sizeof(linknode));
t->data = ch;
t->prior = p;
t->next = p->next;
p->next = t;
t->next->prior = t;
}
~~~
刪除一個節點
~~~
void DeleteDlist(linklist head, int i)
{
linknode *p = head->next;
int j = 0;
while(p && j < i-1)
{
p = p->next;
j++;
}
p->next->prior = p->prior;
p->prior->next = p->next;
puts("a");
free(p);
}
~~~
顯示整個雙向鏈表
~~~
void ShowDlist(linklist head)
{
linknode *p = head;
while(p)
{
printf("%c", p->data);
p = p->next;
}
putchar('\n');
}
~~~
釋放整個雙向鏈表
~~~
void FreeDlist(linklist head)
{
linknode *p;
int i = 0;
p = head;
while(p)
{
free(p);
head = head->next;
p = head;
i++;
}
printf("\nthe dlist free is ok.the node has %d.\n", i);
}
~~~
雙向鏈表的測試程序
~~~
#include <stdio.h>
#include <stdlib.h>
#include "dlist.h"
void show(linknode *p)
{
printf("p->prior:%c\n", p->prior->data);
printf("p->data:%c\n", p->data);
printf("p->next:%c\n", p->next->data);
}
int main(void)
{
linklist head;
//linknode *p;
head = CreatDlist();
ShowDlist(head->next);
p = GetNode(head, 3);
show(p);
DeleteDlist(head, 3);
p = GetNode(head, 3);
show(p);
InsetDlist(head, 'x', 2);
ShowDlist(head->next);
FreeDlist(head);
return 0;
}
~~~
