链表的基本操作和总结( 带头结点)

[来源] 达内    [编辑] 达内   [时间]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); "> 链表总结:

< 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); ">1、链表有两种类型.一种是带有表头的和不带有表头的,其实基本操作都差不多。

< 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); ">   只是在带有表头的链表中,第一个节点没放东西,属于浪费资源,但是便于插入和删除,主要针对的是第一个节点的操作。(个人习惯用带有表头的链表)

< 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); "> 

< 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); "> 2、在创建代表头的链表时,起初只用创建表头就行了,返回一个表头。然后根据需要在插入数据,这样建立链表。 

< 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); ">    而在建无表头的链表时,一般是在创建时就生成了链表。然后在插入时,单独用一个函数。相对于带有表头的链表,代码冗余了一些。

< 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); "> 

< 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); "> 3、在使用malloc函数动态开辟空间时,虽然指定了多少字节,但是系统在开辟空间时,系统会在内存堆区中沿着空闲的连续的内存依次找,

< 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); ">   找到了足够用户使用的内存空间了,返回给用户。所以得到的并不是所申请的,VC++中默认的是给(40H)空间。

< 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); "> 

< 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); ">4、在创建完了链表后,虽然是动态开辟的,但是在内存中是连续的,相隔(40H)字节。

< 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); ">   但是如果此时要动态开辟一个节点插入链表中时,发现此节点的内存地址并不是和原来的链表的地址连续,而是在不同的地方。

< 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); "> 

< 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); "> 5、在链表中进行操作时(访问数据成员),最理想的方法就是使用p = p->next;依次遍历链表。这样才能准确无误的遍历整个链表。

< 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); ">   而有很多情况都用的是p + i 来访问第几个节点。这个在链表中是错误的。经过我在VC++6.0中调试发现,用指针p指向链表表头(链表不为空),

< 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); ">   当用p = p->next;可以正常得到链表的第一个节点。而当用P++时,p指向的是位置内存区域,所以不可能得到第一个节点,更别谈其他的p + i 等。

< 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); "> 

< 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); "> 6、而P++一般适用于什么情况呢?一般是针对连续的内存区域,例如数组,字符串中,在这里用P++是合理无误的。

< 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); "> 

< 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
))        //
非法删除点。前者:是否越界; 后者:删除点是否<=0


125     { 
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 }

资源下载