数据结构双向链表 C语言实现

dlist.h

 1 #ifndef __dList_H
 2 #define __dlist_H
 3 
 4 typedef    int Item;
 5 typedef struct Node *PNode;
 6 typedef PNode Position;
 7 /*定义节点类型*/
 8 typedef struct Node
 9 {
10     Item data; /*数据域*/
11     PNode previous; /*指向前驱*/
12     PNode next;    /*指向后继*/
13 }Node;
14 
15 /*定义链表类型*/
16 typedef struct
17 {
18     PNode head; /*指向头节点*/
19     PNode tail; /*指向尾节点*/
20     int size;
21 }DList;
22 
23 
24 /*分配值为i的节点，并返回节点地址*/
25 Position MakeNode(Item i);
26 /*释放p所指的节点*/
27 void FreeNode(PNode p);
28 /*构造一个空的双向链表*/
29 DList* InitList();
30 /*摧毁一个双向链表*/
31 void DestroyList(DList *plist);
32 /*将一个链表置为空表，释放原链表节点空间*/
33 void ClearList(DList *plist);
34 /*返回头节点地址*/
35 Position GetHead(DList *plist);
36 /*返回尾节点地址*/
37 Position GetTail(DList *plist);
38 /*返回链表大小*/
39 int GetSize(DList *plist);
40 /*返回p的直接后继位置*/
41 Position GetNext(Position p);
42 /*返回p的直接前驱位置*/
43 Position GetPrevious(Position p);
44 /*将pnode所指节点插入第一个节点之前*/
45 PNode InsFirst(DList *plist,PNode pnode);
46 /*将链表第一个节点删除并返回其地址*/
47 PNode DelFirst(DList *plist);
48 /*获得节点的数据项*/
49 Item GetItem(Position p);
50 /*设置节点的数据项*/
51 void SetItem(Position p,Item i);
52 /*删除链表中的尾节点并返回其地址，改变链表的尾指针指向新的尾节点*/
53 PNode Remove(DList *plist);
54 /*在链表中p位置之前插入新节点S*/
55 PNode InsBefore(DList *plist,Position p,PNode s);
56 /*在链表中p位置之后插入新节点s*/
57 PNode InsAfter(DList *plist,Position p,PNode s);
58 /*返回在链表中第i个节点的位置*/
59 PNode LocatePos(DList *plist,int i);
60 /*依次对链表中每个元素调用函数visit()*/
61 void ListTraverse(DList *plist,void (*visit)());
62 
63 #endif

dlist.c

  1 #include"dlist.h"
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 /*分配值为i的节点，并返回节点地址*/
  5 Position MakeNode(Item i)
  6 {
  7     PNode p = NULL;
  8     p = (PNode)malloc(sizeof(Node));
  9     if(p!=NULL)
 10     {
 11         p->data = i;
 12         p->previous = NULL;
 13         p->next = NULL;
 14     }
 15     return p;
 16 }
 17 /*释放p所指的节点*/
 18 void FreeNode(PNode p)
 19 {
 20      free(p);
 21 }
 22 /*构造一个空的双向链表*/
 23 DList * InitList()
 24 {
 25     DList *plist = (DList *)malloc(sizeof(DList));
 26     PNode head = MakeNode(0);
 27     if(plist!=NULL)
 28     {
 29         if(head!=NULL)
 30         {
 31             plist->head = head;
 32             plist->tail = head;
 33             plist->size = 0;
 34         }
 35         else
 36             return NULL;
 37     }
 38     return plist;
 39 }
 40 
 41 /*摧毁一个双向链表*/
 42 void DestroyList(DList *plist)
 43 {
 44     ClearList(plist);
 45     free(GetHead(plist));
 46     free(plist);
 47 }
 48 
 49 /*判断链表是否为空表*/
 50 int IsEmpty(DList *plist)
 51 {
 52     if(GetSize(plist) == 0 && GetTail(plist) == GetHead(plist))
 53         return 1;
 54     else
 55         return 0;
 56 }
 57 /*将一个链表置为空表，释放原链表节点空间*/
 58 void ClearList(DList *plist)
 59 {
 60     PNode temp,p;
 61     p = GetTail(plist);
 62     while(!IsEmpty(plist))
 63     {
 64         temp = GetPrevious(p);
 65         FreeNode(p);
 66         p = temp;
 67         plist->tail = temp;
 68         plist->size--;
 69     }
 70 }
 71 
 72 /*返回头节点地址*/
 73 Position GetHead(DList *plist)
 74 {
 75     return plist->head;
 76 }
 77 
 78 /*返回尾节点地址*/
 79 Position GetTail(DList *plist)
 80 {
 81     return plist->tail;
 82 }
 83 
 84 /*返回链表大小*/
 85 int GetSize(DList *plist)
 86 {
 87     return plist->size;
 88 }
 89 
 90 /*返回p的直接后继位置*/
 91 Position GetNext(Position p)
 92 {
 93     return p->next;
 94 }
 95 
 96 /*返回p的直接前驱位置*/
 97 Position GetPrevious(Position p)
 98 {
 99     return p->previous;
100 }
101 
102 /*将pnode所指节点插入第一个节点之前*/
103 PNode InsFirst(DList *plist,PNode pnode)
104 {
105     Position head = GetHead(plist);
106 
107     if(IsEmpty(plist))
108         plist->tail = pnode;
109     plist->size++;
110 
111     pnode->next = head->next;
112     pnode->previous = head;
113 
114     if(head->next!=NULL)
115         head->next->previous = pnode;
116     head->next = pnode;
117 
118     return pnode;
119 }
120 
121 /*将链表第一个节点删除,返回该节点的地址*/
122 PNode DelFirst(DList *plist)
123 {
124     Position head = GetHead(plist);
125     Position p=head->next;
126     if(p!=NULL)
127     {
128         if(p==GetTail(plist))
129             plist->tail = p->previous;
130         head->next = p->next;
131         head->next->previous = head;
132         plist->size--;
133 
134     }
135     return p;
136 }
137 
138 /*获得节点的数据项*/
139 Item GetItem(Position p)
140 {
141     return p->data;
142 }
143 
144 /*设置节点的数据项*/
145 void SetItem(Position p,Item i)
146 {
147     p->data = i;
148 }
149 
150 /*删除链表中的尾节点并返回地址，改变链表的尾指针指向新的尾节点*/
151 PNode Remove(DList *plist)
152 {
153     Position p=NULL;
154     if(IsEmpty(plist))
155         return NULL;
156     else
157     {
158         p = GetTail(plist);
159         p->previous->next = p->next;
160         plist->tail = p->previous;
161         plist->size--;
162         return p;
163     }
164 }
165 /*在链表中p位置之前插入新节点s*/
166 PNode InsBefore(DList *plist,Position p,PNode s)
167 {
168     s->previous = p->previous;
169     s->next = p;
170     p->previous->next = s;
171     p->previous = s;
172 
173     plist->size++;
174     return s;
175 }
176 /*在链表中p位置之后插入新节点s*/
177 PNode InsAfter(DList *plist,Position p,PNode s)
178 {
179     s->next = p->next;
180     s->previous = p;
181 
182     if(p->next != NULL)
183         p->next->previous = s;
184     p->next = s;
185 
186     if(p == GetTail(plist))
187         plist->tail = s;
188 
189     plist->size++;
190     return s;
191 }
192 
193 /*返回在链表中第i个节点的位置*/
194 PNode LocatePos(DList *plist,int i)
195 {
196     int cnt = 0;
197     Position p = GetHead(plist);
198     if(i>GetSize(plist)||i<1)
199         return NULL;
200 
201     while(++cnt<=i)
202     {
203         p=p->next;
204     }
205 
206     return p;
207 }
208 
209 /*依次对链表中每个元素调用函数visit()*/
210 void ListTraverse(DList *plist,void (*visit)())
211 {
212     Position p = GetHead(plist);
213     if(IsEmpty(plist))
214         exit(0);
215     else
216     {
217 
218         while(p->next!=NULL)
219         {
220             p = p->next;
221             visit(p->data);
222         }
223     }
224 }

test.c

 1 #include"dlist.h"
 2 #include<stdio.h>
 3 
 4 void print(Item i)
 5 {
 6     printf("数据项为%d 
",i);
 7 }
 8 int main()
 9 {
10     DList *plist = NULL;
11     PNode p = NULL;
12 
13     plist = InitList();
14     p = InsFirst(plist,MakeNode(1));
15     InsBefore(plist,p,MakeNode(2));
16     InsAfter(plist,p,MakeNode(3));
17 
18     printf("p前驱位置的值为%d
",GetItem(GetPrevious(p)));
19     printf("p位置的值为%d
",GetItem(p));
20     printf("p后继位置的值为%d
",GetItem(GetNext(p)));
21 
22 
23     printf("遍历输出各节点数据项:
");
24     ListTraverse(plist,print);
25     printf("除了头节点该链表共有%d个节点
",GetSize(plist));
26     FreeNode(DelFirst(plist));
27     printf("删除第一个节点后重新遍历输出为:
");
28     ListTraverse(plist,print);
29     printf("除了头节点该链表共有%d个节点
",GetSize(plist));
30     DestroyList(plist);
31     printf("链表已被销毁
");
32 }

运行结果：

[walt740@localhost 02.Doublylinklist]$ gcc test.c dlist.c dlist.h -o test
[walt740@localhost 02.Doublylinklist]$ tree -L 2
.
├── dlist.c
├── dlist.h
├── test
├── test.c
└── 345217214345220221351223276350241250
    ├── bin
    ├── obj
    ├── 345217214345220221351223276350241250.cbp
    ├── 345217214345220221351223276350241250.depend
    └── 345217214345220221351223276350241250.layout

3 directories, 7 files
[walt740@localhost 02.Doublylinklist]$ ./test
p前驱位置的值为2
p位置的值为1
p后继位置的值为3
遍历输出各节点数据项:
数据项为2 
数据项为1 
数据项为3 
除了头节点该链表共有3个节点
删除第一个节点后重新遍历输出为:
数据项为1 
数据项为3 
除了头节点该链表共有2个节点
链表已被销毁
[walt740@localhost 02.Doublylinklist]$ ^

转自 -- http://blog.csdn.net/hopeyouknow/article/details/6716177

数据结构 双向链表 C语言实现

数据结构双向链表 C语言实现