链表的基本操作（ 无头结点）
［来源］ 达内 ［编辑］ 达内 ［时间］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); "> 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); "> 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); "> 具体代码如下：若有问题，希望大家及时指正，共同探讨。。。 < 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
4
5 #include <stdio.h> 6 #include <stdlib.h> 7 8 typedef int ElemType; 9 10 typedef struct node 11 { 12 ElemType data; 13 struct node *next; 14 }LNode, *LinkList; 15 16 17 // 尾插法创建链表 18 LinkList CreateLinkList( int nNodeCount) 19 { 20 LinkList head = NULL, p = NULL, r = NULL; 21 int i; 22 23 for (i = 0; i < nNodeCount; i++ ) 24 { 25 p = (LinkList)malloc( sizeof (LNode)); 26 if (NULL == p) 27 { 28 printf( " 分配内存失败\n" ); 29 free(p); 30 exit(0); 31 } 32 33 printf(" 为p->data赋值：" ); 34 scanf("%d ", &p->data); 35 p->next = NULL; // 动态创建一个节点时，在初始状态下，令next域为空 36 37 if (NULL == head) 38 { 39 head = p; 40 } 41 else 42 { 43 r->next = p; 44 } 45 r = p; 46 } 47 48 return head; 49 } 50 51 // 输出链表 52 void PrintLinkList(LinkList L) 53 { 54 LinkList p = NULL; 55 if (NULL == L) 56 { 57 printf(" 链表为空\n" ); 58 exit(0); 59 } 60 61 p = L; 62 while (NULL != p) 63 { 64 printf("%d\t ", p->data); 65 p = p->next; 66 } 67 printf(" \n" ); 68 } 69 70 // 插入 （关键点：0， 1， 2） 71 void InsertLinkList(LinkList &L, int nInsertPoint, ElemType nInsertValue) 72 { 73 LinkList p = NULL, r = NULL; 74 int i = 1; 75 76 if (NULL == L) //链表校验 77 { 78 printf(" 链表为空\n" ); 79 exit(0); 80 } 81 82 r = (LinkList)malloc( sizeof(LNode)); // 创建节点校验 83 if (NULL == r) 84 { 85 printf(" 内存分配失败\n "); 86 free(r); 87 exit(0 ); 88 } 89 r->data = nInsertValue; 90 r->next = NULL; 91 92 p = L; 93 while ((NULL != p) && (i < nInsertPoint - 1 )) // 合法插入点，指针移动 94 { 95 p = p->next; 96 i++; 97 } 98 99 if (1 == nInsertPoint) // 插入点为1 100 { 101 r->next = p; 102 L = r; 103 } 104 else 105 { 106 while ((NULL == p) || (i > nInsertPoint - 1 )) // 判断非法插入点。前者判断是否越界，后者判断是否 <=0; 107 { 108 printf( " 非法插入点，请检查参数\n " ); 109 exit(0); 110 } 111 112 // 合法插入点 113 r->next = p-> next; 114 p->next = r; 115 } 116 } 117 118 // 删除 119 void DeleteLinkList(LinkList &L, int nDeletePoint) 120 { 121 LinkList p = NULL, r = NULL; 122 int i = 1; 123 124 if (NULL == L) 125 { 126 printf(" 链表为空，无法删除\n "); 127 exit(0 ); 128 } 129 130 p = L; 131 while ((NULL != p) && (i < nDeletePoint - 1 )) 132 { 133 p = p->next; 134 i++; 135 } 136 137 if (1 == nDeletePoint) 138 { 139 L = p->next; 140 r = p; 141 } 142 else 143 { 144 while ((NULL == p) || (i > nDeletePoint - 1 )) 145 { 146 printf( " 非法删除点， 请检查参数\n " ); 147 exit(0); 148 } 149 150 // 合法删除点 151 r = p->next; 152 p->next = r-> next; 153 } 154 155 free(r); // 释放删除节点 156 } 157 158 // 销毁 159 void DestroyLinkList(LinkList &L) 160 { 161 LinkList p = NULL, r = NULL; 162 163 if (NULL == L) 164 { 165 printf(" 链表为空\n "); 166 exit(0 ); 167 } 168 169 p = L; 170 while (NULL != p) 171 { 172 r = p; 173 p = p->next; 174 free(r); 175 } 176 printf(" 成功销毁\n "); 177 } 178 179 // 查找元素 180 ElemType FindLinkList(LinkList L, int nFindPoint) 181 { 182 LinkList p = NULL; 183 int i = 1 ; 184 185 if (NULL == L) 186 { 187 printf(" 链表为空\n "); 188 exit(0 ); 189 } 190 191 p = L; 192 while ((NULL != L) && (i < nFindPoint - 1 )) 193 { 194 p = p->next; 195 i++; 196 } 197 198 if (1 == nFindPoint) 199 { 200 return p->data; 201 } 202 else 203 { 204 while ((NULL == p) || (i > nFindPoint - 1 )) 205 { 206 printf( " 非法查找点\n" ); 207 exit(0); 208 } 209 210 return p->next->data; 211 } 212 } 213 214 // 修改元素 215 void ModifyLinkList(LinkList &L, int nModifyPoint, ElemType nModifyValue) 216 { 217 LinkList p = NULL; 218 int i = 1; 219 220 if (NULL == L) 221 { 222 printf(" 链表为空\n "); 223 exit(0 ); 224 } 225 226 p = L; 227 while ((NULL != L) && (i < nModifyPoint - 1 )) 228 { 229 p = p->next; 230 i++; 231 } 232 233 if (1 == nModifyPoint) 234 { 235 p->data = nModifyValue; 236 } 237 else 238 { 239 while ((NULL == p) || (i > nModifyPoint - 1 )) 240 { 241 printf( " 非法修改点\n" ); 242 exit(0); 243 } 244 245 p->next->data = nModifyValue; 246 } 247 248 } 249 250 int main() 251 { 252 LinkList La = NULL; 253 254 La = CreateLinkList( 4); 255 256 /* 测试插入 257 printf("插入前链表:\n"); 258 PrintLinkList(La); 259 260 InsertLinkList(La, -1, 4); 261 262 printf("插入后链表:\n"); 263 PrintLinkList(La); 264 //*/ 265 266 /* 测试删除 267 printf("删除前链表:\n"); 268 PrintLinkList(La); 269 270 DeleteLinkList(La, 2); 271 272 printf("删除后链表:\n"); 273 PrintLinkList(La); 274 //*/ 275 276 /* 测试查找 277 PrintLinkList(La); 278 int x = FindLinkList(La, 2); 279 printf("%d\n", x); 280 //*/ 281 282 /* 测试修改 283 PrintLinkList(La); 284 ModifyLinkList(La, -1, 4); 285 PrintLinkList(La); 286 //*/ 287 288 DestroyLinkList(La); //销毁链表 289 290 return 0; 291 }
