1、链表的基本操作（ 无头结点）

　　　　这几天在寝室专门写链表，其实链表的操作和线性表相比有区别。

　　1、数据结构：

　　采用的结构体：数据域和指针域。

　　2、在插入，删除和销毁时，主要都是指针的指向发生变化，所以在写代码时务必校验，指针是否为空，否则容易造成程序的崩溃。。。

　　

　　　　具体代码如下：若有问题，希望大家及时指正，共同探讨。。。

  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 }