双向链表 – 数据结构
最后更新于：2022-04-01 20:05:55
双向链表就是在单项链表的基础上增加了一个前向指针域。基本操作还是一样的，该双向链表是带有头节点的，最后一个节点的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 && jnext;
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
#include
#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;
}
~~~
';