链表的基本操作和总结（带头结点）

［来源］达内［编辑］达内［时间］2012-10-17

链表有两种类型.一种是带有表头的和不带有表头的，其实基本操作都差不多

之前写了不带头结点的链表，发现在操作时还遇到一些问题，后来又写了一下带有头结点的链表，还有一些调试的心得，与大家共享。。。

< p style="margin: 10px auto; padding: 0px; text-indent: 0px; color: rgb(57, 57, 57); font-family: verdana, 'ms song', Arial, Helvetica, sans-serif; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 21px; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(250, 247, 239); "> 链表总结:

< div style="margin: 5px 0px; padding: 5px; background-color: rgb(245, 245, 245); font-family: 'Courier New'; font-size: 12px; border: 1px solid rgb(204, 204, 204); overflow: auto; color: rgb(57, 57, 57); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; " class="cnblogs_code">

  1
 //
链表的基本操作(带有表头)  2 
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 
  6 typedef int
 ElemType;   7
 
  8 typedef struct
 node   9
 {  10
     ElemType data;  11
     struct node *next; 
 12 }LNode, *LinkList; 
 13
 
 14 //
初始化链表 （只建表头）

 15 void
 InitLinkList(LinkList &L) 
 16

 {  17
     LinkList p = NULL;  18
     if (NULL == L) 
 19     { 
 20         p = (LinkList)malloc(
sizeof

(LNode));  21
         if (NULL == p) 
 22         { 
 23             printf(
"

内存分配失败\n"
);  24
 

            free(p);  25
             exit(0); 
 26

         }  27
 
 28         L = p; 
 29         L->next =
 NULL; 

 30     } 
 31     else

 32     { 
 33         printf("
链表不为空，无需初始化\n
"

);  34
         exit(0); 
 35     } 
 36 } 
 37
 
 38 //
插入元素

 39 void
 InsertLinkList(LinkList &L, int
 nInsertPoint, ElemType nInsertValue)  40
 { 

 41     LinkList p = NULL, r =
 NULL;  42     int
 i = 0; 
 43
 
 44     if
 (NULL == L)  45
     {  46
         printf("
表头为空，请先初始化\n

"); 
 47         exit(0
);  48
     }  49
 
 50     r = (LinkList)malloc(
sizeof(LNode));  51
     if (NULL == r) 
 52     { 
 53         printf("
内存分配失败\n"
);  54
         free(r);  55
         exit(0); 
 56     } 
 57     r->data =
 nInsertValue; 

 58
     
 59     p = L; 
 60     while
 ((NULL != p) && (i < nInsertPoint - 1
))   //

合法插入点，指针移动，定位到带插入点之前

 61     { 
 62         p = p->next; 
 63         i++; 
 64     } 
 65
 
 66     while
 ((NULL == p) || (i > nInsertPoint - 1
))   

//非法插入点。 前者：插入点越界； 后者：插入点<=0；

 67     { 
 68         printf("
非法插入点，请检查参数\n
"

);  69
         exit(0); 
 70     } 
 71
 
 72     r->next = p->
next;  73     p->next =
 r; 

 74 } 
 75
 
 76 //
校验头指针和其next域是否为空

 77 void
 CheckLinkList(LinkList L)  78
 {  79
     if (NULL == L) 
 80     { 
 81         printf("
指针为空，请检查参数\n
"

);  82
         exit(0); 
 83     } 
 84     if
 (NULL == L->

next)  85     { 
 86         printf("
链表为空，无法销毁.\n
"

);  87
         exit(0); 
 88     } 
 89 } 
 90
 
 91 //
输出链表

 92 void
 PrintLinkList(LinkList L)  93
 {  94
     LinkList p = NULL;  95
     int i = 0
;  96
 
 97     CheckLinkList(L); 
 98
     
 99     p = L->next;        
//注意：此处不是p = L;

100     while
 (NULL != p) 101
     { 102
         printf("%d 
", p->data); 
103         p = p->next; 
104     } 
105
 
106     printf("
\n"
); 107
 } 108
 
109 //
删除节点

110 void
 DeleteLinkList(LinkList &L, int
 nDeletePoint) 

111 { 
112     LinkList p = NULL, r =
 NULL; 

113     int
 i = 0; 
114
 
115     CheckLinkList(L); 
116
 
117     p = L; 
118     while
 ((NULL != p) && (i < nDeletePoint - 1
))        

//指针移动到删除点之前

119     { 
120         p = p->next; 
121         i++; 
122     } 
123
 
124     while
 ((NULL == p) || (i > nDeletePoint - 1
))        //
非法删除点。前者：是否越界； 后者：删除点是否<=0125
     { 

126         printf("
非法删除点.\n"
); 127
         exit(0); 
128     } 
129
 
130     //
删除节点

131     r = p->next; 
132     p->next = r->
next; 

133
 
134     free(r); 
135 } 
136
 
137 //
销毁链表

138 void
 DestroyLinkList(LinkList &L) 
139

 { 140
     LinkList p = NULL, r = NULL; 
141

 
142     CheckLinkList(L); 
143
 
144     p = L->next;        
//注意：此处不是p = L;

145     while
 (NULL != p) 146
     { 147
         r = p; 148
         p = p->next; 149
         free(r); 150
     } 151
 
152     printf("
成功销毁链表\n"
); 153
 } 154
 
155 //
通过查找点，查找元素值 （返回p->data）

156 ElemType FindElem(LinkList L, 
int nFindPoint) 157
 { 158
     LinkList p = NULL; 159
     int i = 0
; 160
 
161     CheckLinkList(L); 
162
 
163     p = L; 
164     while
 ((NULL != p) && (i < nFindPoint)) 
165

     { 166
         p = p->next; 167
         i++; 168
     } 169
     while
 ((NULL == p) || (i > nFindPoint) || 0

 == nFindPoint)            //
非法查找点。前者：是否越界； 后者：删除点是否<=0

170     { 
171         printf("
非法查找点.\n"
); 172
         exit(0); 
173     } 
174
 
175     return
 p->data; 176
 } 177
 
178 //
通过元素查找，若存在，返回其位序，否则返回-1

179 int
 LocateElem(LinkList L, ElemType elem) 
180

 { 181
     LinkList p = NULL; 182
     int nSeq = 1
; 183
 
184     CheckLinkList(L); 
185
 
186     p = L->next; 
187     while
 ((NULL != p) && (elem != p->data)) 
188

     { 189
         nSeq++; 190
         p = p->next; 191
     } 192
 
193     if
 (NULL == p) 194
     { 195
         return -1
;        //没找到

196     } 
197     else

198     { 
199         return
 nSeq;     200
     } 201
 } 202
 
203 int
 LengthOfLinkList(LinkList L) 
204

 { 205
     LinkList p = NULL; 206
     int nLength = 0
; 207
     
208     CheckLinkList(L); 
209
 
210     p = L->next; 
211     while
 (NULL != p) 212
     { 213
         nLength++; 214
         p = p->next; 215
     } 216
     return nLength; 
217 } 
218
 
219 
220 int
 main() 221
 { 222
     LinkList La = NULL; 223
     int nInsertCount;  //
待插入元素个数

224     int
 nInsertValue;  //
待插入元素值225     
int

 i = 0; 
226
 
227     InitLinkList(La); 
228
 
229     printf("
请输入插入个数:"
); 230
     scanf("%d
", &nInsertCount); 
231
 
232     while
 (i < nInsertCount) 233
     { 234
         printf("
为p->data赋值:

"); 
235         scanf("
%d"
, &nInsertValue); 236
 
237
         InsertLinkList(La, i + 1
, nInsertValue);        //

插入元素

238 
239         i++; 
240     } 
241
 
242     /*
-------------测试查找------------- 
243

     int x = FindElem(La, -1); 
244     printf("%d\n", x); 
245     */

246 
247     /*
-------------测试序号------------- 
248

     int nSeq = LocateElem(La, 3); 
249     printf("%d\n", nSeq); 
250     */

251 
252 
253     /*
-------------测试长度------------- 
254

     int nLength = LengthOfLinkList(La); 
255 
    printf("%d\n", nLength); 

256     */

257     
258     /*
-------------测试删除------------- 
259

     //删除前 260
     PrintLinkList(La); 261
 
262     //删除后 
263 
    DeleteLinkList(La, 4); 

264     PrintLinkList(La); 
265     */

266 
267     DestroyLinkList(La); 
268
 
269     return
 0; 
270 }

顶

踩

上一篇：第 21 届 IOCCC 获胜者源代码公布
下一篇：链表的基本操作（无头结点）

链表的基本操作和总结（带头结点）

资源下载

2002-2014 达内科技有限公司版权所有京ICP备08000853号

链表的基本操作和总结（ 带头结点）

资源下载

2002-2014 达内科技有限公司 版权所有 京ICP备08000853号

链表的基本操作和总结（带头结点）

2002-2014 达内科技有限公司版权所有京ICP备08000853号