1  /**//*
2 sgx 2008-10-30 c语言 双向链表
3 */
4 #include <stdio.h>
5#include <assert.h>
6#include <malloc.h>
7#include<time.h>
8#include<stdlib.h>
9
10#define NUM 12
11#define TRUE 1;
12#define FALSE 0;
13
14typedef int ELEMTYPE;
15
16typedef struct DoubleLinkNode
17 {
18 ELEMTYPE data;
19 struct DoubleLinkNode *last;
20 struct DoubleLinkNode *next;
21}dLinkNode,*dLinkList;
22
23dLinkList CreateDLlist(void);/**//*创建空链*/
24int InitDLlist(dLinkList * dl);/**//*初始化链*/
25int InsertLNode(dLinkNode *pNode,ELEMTYPE e);/**//*节点前插入节点,返回TRUE,FALSE*/
26int InsertNNode(dLinkNode *pNode,ELEMTYPE e);/**//*在某节点后面插入节点,*/
27int DeleteNode(dLinkNode *pNode);/**//*删除节点,返回TRUE换或FALSE*/
28void DestroyDLlist(dLinkList dl);/**//*销毁链*/
29void LNTravel(dLinkList dl);/**//*从前向后遍历*/
30void NLTravel(dLinkList dl);/**//*从后向前遍历*/
31
32int main()
33{
34 dLinkList dl=CreateDLlist();
35  if(InitDLlist(&dl)){
36 printf("Initial sucess!\n");
37 }
38
39 LNTravel(dl);
40 NLTravel(dl);
41 DestroyDLlist(dl);
42
43 return 0;
44}
45
46dLinkList CreateDLlist(void)/**//*创建空链*/
47{
48 dLinkList dl=NULL;
49 return dl;
50}
51
52int InitDLlist(dLinkList *dl)/**//*初始化链*/
53{
54 ELEMTYPE e;
55 char symbol;
56 dLinkNode *pNode;
57 if(*dl!=NULL){
58 printf("this LinkList has been Initialed.\n");
59 return FALSE;
60 }
61
62 //printf("input data:");
63 //scanf("%d",&e);
64
65 srand(time(NULL));
66 e=rand()%100;
67
68 // getchar();/*获取空格*/
69
70 *dl=(dLinkNode*)malloc(sizeof(dLinkNode));
71 if(dl==NULL){
72 printf("assigned memory failed,end Initailization!\n");
73 return FALSE;
74 }
75 (*dl)->data=e;
76 (*dl)->next=NULL;
77 (*dl)->last=NULL;
78 pNode=*dl;
79
80 int t=NUM;
81
82 while(t--)
83 {
84 e=rand()%1000;
85 InsertNNode(pNode,e);
86 pNode=pNode->next;
87 }
88
89 return TRUE;
90
91}
92int InsertLNode(dLinkNode *pNode,ELEMTYPE e)/**//*节点前面插入节点,返回TRUE,FALSE*/
93{
94 dLinkNode *newNode,*lastNode;
95 if(pNode==NULL)
96 {
97 printf("Node is NULL,canot operate!\n");
98 return FALSE;
99 }
100 newNode = (dLinkNode*)malloc(sizeof(dLinkNode));
101 if(!newNode){printf("assigned memory failed!\n");return FALSE;}/**//*分配失败*/
102 newNode->data=e;/**//*插入数据*/
103 if(pNode->last==NULL)
104 {
105 newNode->last=NULL;
106 }
107 else
108 {
109 lastNode = pNode->last;
110 lastNode->next = newNode;
111 newNode->last = lastNode;
112
113 }
114 newNode->next=pNode;
115 pNode->last=newNode;
116 return TRUE;
117}
118int InsertNNode(dLinkNode *pNode,ELEMTYPE e)/**//*在某节点后面插入节点,*/
119{
120 dLinkNode *newNode,*nextNode;
121 if(pNode==NULL)
122 {
123 printf("Node is NULL,canot operate!\n");
124 return FALSE;
125 }
126 newNode = (dLinkNode*)malloc(sizeof(dLinkNode));
127 if(!newNode){printf("assigned memory failed!\n");return FALSE;}/**//*分配失败*/
128 newNode->data = e;/**//*插入数据*/
129
130 if(pNode->next==NULL)
131 {
132 newNode->next=NULL;
133 }
134 else
135 {
136 nextNode=pNode->next;
137 newNode->next = nextNode;
138 nextNode->last=newNode;
139 }
140 pNode->next=newNode;
141 newNode->last=pNode;
142
143 return TRUE;
144}
145int DeleteNode(dLinkNode *pNode)/**//*删除节点,返回FALSE或TRUE*/
146{
147 ELEMTYPE e;
148 dLinkNode *LastNode,*NextNode;
149 if(pNode==NULL){printf("Node is NULL,cannot operate it!\n");return FALSE;}
150 LastNode=pNode->last;
151 NextNode = pNode->next;
152 e=pNode->data;
153 if(pNode->next ==NULL && NULL == pNode->last)
154 {
155 free(pNode);
156 printf("%d is deleted,this LinkList now is NULL!\n",e);
157 return TRUE;
158 }
159 else if(pNode->next == NULL)
160 {
161 LastNode->next = NULL;
162 }
163 else if(pNode->last == NULL)
164 {
165 NextNode->last=NULL;
166 }
167 else
168 {
169 LastNode->next=NextNode;
170 NextNode->last=LastNode;
171 }
172 free(pNode);
173 printf("%d is deleted.\n",e);
174 return TRUE;
175}
176void DestroyDLlist(dLinkList dl)/**//*销毁链*/
177{
178 dLinkNode *pNode=dl;
179 dLinkNode *temp;
180 if(pNode==NULL)
181 {printf("the LinkList has been already destroyed!\n");return;}
182 while(pNode->next != NULL)
183 {
184 temp=pNode;
185 pNode=temp->next;
186 DeleteNode(temp);
187 }
188 DeleteNode(pNode);
189}
190void LNTravel(dLinkList dl)/**//*从前向后遍历*/
191{
192 dLinkList pNode;
193 if(dl==NULL){printf("LinkList is NULL!\n");return;}
194 pNode=dl;
195 printf("Travel this LinkList InOrder: ");
196 do
197 {
198 printf("%d\t",pNode->data);
199 pNode=pNode->next;
200 }while(pNode!=NULL);
201 printf("\n");
202}
203void NLTravel(dLinkList dl)/**//*从后向前遍历*/
204{ dLinkList pNode;
205 if(dl==NULL){printf("LinkList is NULL!\n");return;}
206 pNode=dl;
207 printf("Travel this LinkList PostOrder: ");
208 while(pNode->next!=NULL)pNode=pNode->next;
209 do
210 {
211 printf("%d\t",pNode->data);
212 pNode=pNode->last;
213 }while(pNode!=NULL);
214 printf("\n");
215} http://www.cnblogs.com/mjc467621163/archive/2011/07/17/2108514.htmlhttp://topic.csdn.net/u/20081030/15/250b5b04-319b-45fe-a8a7-b079b6380743.htmlhttp://www.cnblogs.com/ncindy/archive/2006/12/30/607608.htmlhttp://www.cnblogs.com/liushang0419/archive/2011/05/29/2061757.html
|