线性表：单链表基本操作代码

  1 此代码由https://fishc.com.cn/thread-46760-1-1.html转载
  2 
  3 #include<stdio.h>
  4 #include<stdlib.h>
  5 
  6 #define OK 1
  7 #define ERROR -1
  8 #define LEN sizeof(LinkList)
  9 
 10 typedef int Status;
 11 typedef int ElemType;
 12 
 13 typedef struct Node//声明结构体  定义单链表   //typedef struct LNode 
 14 {                                           //{
 15     ElemType data;                      //       ElemType  data;
 16     struct Node *next;                  //       struct LNode *next; 
 17 }LinkList;                                  //}LinkList;
 18 
 19 LinkList *InitList();
 20 Status HeadInsert(LinkList *L);
 21 Status PrintList(LinkList *L);
 22 Status TailInsert(LinkList *L);
 23 Status ListLength(LinkList *L);
 24 Status GetElem(LinkList *L);
 25 Status LocateElem(LinkList *L);
 26 Status ListInsert(LinkList *L);
 27 Status ListDelete(LinkList *L);
 28 void DestoryLinkList(LinkList **L);
 29 
 30 LinkList *InitList()//初始化结构体（生成带头结点的空链表） 
 31 {                                                //算法实现 
 32     LinkList *L;                             //Status InitList(LinkList *L) 
 33     L = (LinkList *)malloc(LEN);             //{ 
 34     if(L == NULL)                            //      L = new LNode;     //生成新结点作为头结点 
 35     {                                        //      L->next = NULL;    //头指针的指针域为空 
 36         printf("内存分配失败");           //      return OK; 
 37         exit(ERROR);                     //}
 38     }
 39     
 40     L->next = NULL;
 41     
 42     return L;
 43 }
 44 
 45 Status HeadInsert(LinkList *L)//头插法               //算法实现 
 46 {                                                    //void CreateList_Head(LinkList *L,int n) 
 47     LinkList *p;                                 //{
 48     int i;                                       //       L = newLnode;  
 49                                                      //       L->next = NULL;              
 50     printf("请输入数字<以86结束>:");              //       for(i = 0; i < n; i++)
 51     scanf("%d",&i);                              //       {  
 52     while(i != 86)                               //            p = new LNode;        //生成新结点*p 
 53     {                                            //            cin>>p->data;         //输入元素值赋给新生成的结点 
 54         p = (LinkList *)malloc(LEN);         //            p->next = L->next     //p的指针域指向头结点的下一个结点的数据域 
 55         p->data = i;           //输入数据     //            L->next = p;          //头结点的指针域指向p的数据域插入完成 
 56         p->next = L->next;                   //       }
 57         L->next = p;                         //}         
 58         scanf("%4d",&i);
 59     }
 60     return OK;
 61 }
 62 
 63 Status PrintList(LinkList *L)//打印 
 64 {
 65     LinkList *p;
 66     p = L->next;
 67     printf("操作结果是：");
 68     while(p != NULL)
 69     {
 70         printf("%5d",p->data);
 71         p = p->next;
 72     } 
 73     printf("\n");    
 74     return OK;
 75 }
 76 
 77 Status TailInsert(LinkList *L)                                    //算法描述 
 78 {                                                                   void CreatList_R(LinkList *L,int n)
 79     int i;                                                      { 
 80     LinkList *tail,*p;                                                L = new LNode;
 81     tail = L;  //尾指针的初值为头结点                                   L->next = NULL;
 82     printf("请输入正整数<以86结束>:");                                  r = L;  //尾指针r指向头结点 
 83     scanf("%d",&i);                                                   for(i = 0; i < n; i++)
 84                                                                       {
 85     while(i != 86)                                                         p = newLNode;
 86     {                                                                      cin>>p->data; 
 87         p = (LinkList *)malloc(LEN);                                   p->next = NULL;
 88         p->data = i;                                                   r->next = p; 
 89         tail->next = p; //新结点插入到表尾tail之后                       r = p;
 90         tail = p;       //将尾指针tail指向新插入的节点               }
 91         scanf("%d",&i);                                      }   
 92     }
 93     
 94     tail->next = NULL;
 95     return OK;
 96 }
 97 
 98 Status ListLength(LinkList *L)//测量长度 
 99 {
100     int i = 0;
101     LinkList *p;
102     
103     p = L->next;
104     while(p != NULL)
105     {
106         i++;
107         p = p->next;
108     }
109     printf("线性表的长度为：%d\n",i);
110     return i;
111 }
112 
113 Status GetElem(LinkList *L)//获取元素          //算法实现 
114 {                                              //Status GetElem(LinkList *L,int i,ElemType &e) 
115     int i = 0;                                 //{ 根据序号i获取元素的值 并用e返回 
116     int j;                                     //    p = L->next;
117     int temp = 0;                              //    while(p != NULL && j<i)
118     LinkList *p,*T;                            //    {
119     T = L->next;                               //        p = p->next; 
120     p = L->next;                               //        j++;
121     while(p != NULL)//测量一下线性表的长度           //    }
122     {                                              //    if(!p || j>i) return ERROR;
123         i++;                                       //    e = p->data;
124         p = p->next;                               //    return OK; 
125     }                                          //}
126     printf("请输入想要查找元素的位置：");
127     scanf("%d",&j);
128     if(j > i || i < 0)
129     printf("不好意思没那个位置\n");
130      
131     while(T != NULL)
132     {
133         temp++;
134         if(temp == j)
135         {
136             printf("第%d位置上的元素是：%d\n",j,T->data);
137             break;
138         }
139         T = T->next;
140     }
141     
142     return OK;
143 }
144 
145 Status LocateElem(LinkList *L)//定位,按值查找   //算法实现 
146 {                                               //LinkList *LocateElem(LinkList L,ElemType e) 
147     int i = 0,j,k = 0;                          //{        //寻找e元素 
148     LinkList *p;                                //         p = L->next;   //初始化p指向首元结点 
149                                                     //         while(p && p->data != e)   
150     p = L->next;                                //         { 
151     printf("请输入想要查找的数据：");             //                 p = p->next;   //扫描 
152     scanf("%d",&j);                             //         }
153     while(p != NULL)                            //         return p;             //返回e的结点地址p 
154     {                                           //}
155         i++;
156         if((p->data) == j)
157         {
158             printf("%d的位置是%d\n",j,i);
159             k = 1;
160             break;
161         }
162         
163         p = p->next;
164     }
165     if(k == 0)
166     {
167         printf("你查找的元素不存在啊！\n");
168     }
169     
170     return OK;
171 }
172 
173 Status ListInsert(LinkList *L)//插入                            //算法描述 
174 {                                                               //Status ListInsert(LinkList *L,int i,Elemtype e) 
175     int i,j,k = 0;                                              //{
176     LinkList *p,*q,*r;                                          //      p = L;
177                                                                 //      j = 0;
178     p = L->next;                                                //      while(p && (j<i-1))
179      printf("请输入插入的位置以及想要插入的数(无越界检查)");         //      { 
180     scanf("%d %d",&i,&j);                                       //           p = p->next;
181                                                                 //           j++;
182     q = (LinkList *)malloc(LEN);                                //      }    
183     q->data = j;                                                    //      if(!p || j>i-1)  return ERROR;
184     while(p != NULL)                                            //      s = new LNode;
185     {                                                           //      s->data = e;
186          if(i == 1) //如果插在头部的情况                       //      s->next = p->next;
187          {                                                   //      p->next = s;
188              q->next = L->next;                          //      return OK; 
189              L->next = q;                                //}
190              break;
191         }
192          else if((k+1) == i)//否则就往后找 
193          {
194              q->next = p->next;//数据的指针域指向p的下一个结点 
195              p->next = q;
196              break;
197         }
198          
199          p= p->next;
200      } 
201      
202      r = L->next;
203      printf("操作结果是：\n");
204      while(r != NULL)
205      {
206          printf("%5d",(r->data));
207          r = r->next;
208      }
209      printf("\n");
210      return OK;
211 }
212 
213 Status ListDelete(LinkList *L)                               //算法描述 
214 {                                                            //Status ListDelete(LinkList *L,Elemtype i) 
215     int i;                                                   //{ //带头结点的链表中删除第i个元素
216     LinkList *p,*q;                                          //     p =L;j = 0;   
217                                                                  //        while((p->next) && (j<i-1))
218     p = L->next;                                             //     {p = p->next; j++;}  //查找第i-1个结点 让p指向它
219     printf("请输入你想要删除的数组<相同的只删除一个>:");        //         if(!(p->next) || (j>i-1))  return ERROR;
220     scanf("%d",&i);                                          //          q = p->next;
221     while(p != NULL)                                         //          p->next = q->next;    
222     {                                                        //          delete q;
223         if(L->next->data == i)  //第一个数=               //          return OK;
224         {                                                  //  }
225             L->next = L->next->next;                
226             break;                                    
227         }
228         else if(p->next->data == i)
229         {
230             p->next = p->next->next;
231             break;
232         }
233         
234         p = p->next;
235     }
236     
237     q = L->next;
238     printf("操作结果是：");
239     while(q != NULL)
240     {
241         printf("%5d",(q->data));
242         q = q->next;
243     }
244     printf("\n");
245     return OK; 
246 } 
247 
248 void DestoryLinkList(LinkList **L)
249 {
250     LinkList *temp;
251     while(*L != NULL)
252     {
253         temp = *L;
254         *L = (*L)->next;
255         free(temp);
256     }
257 }
258 
259 Status main(void)             //主函数 
260 {
261     int i,j;
262     LinkList *L;
263     L = InitList();       //初始化单链表 
264     while(1)
265     {
266         printf("建立单链表：1.头插法  2.尾插法  3.结束\n");
267         printf("请输入操作序号");
268         scanf("%d",&i);
269         if(i == 1)
270         {
271             HeadInsert(L);
272             PrintList(L);
273             break;
274         }
275         else if(i == 2)
276         {
277             TailInsert(L);
278             PrintList(L);
279             break;
280         }     
281         else if(i == 3)
282         {
283             exit(0);         //代码正常退出  exit(1)为代码为非正常退出 
284         }
285         else
286         {
287             printf("输入有误，请重新输入\n"); 
288         }
289         
290     }
291     
292     printf("单链表操作:1.求长度 2.按位置求值 3.按值查找 4.插入 5.删除 6.退出\n");
293     while(1)
294     {
295         printf("请输入操作序号：");
296         scanf("%d",&j);
297         
298         if(j == 1)
299         {
300             ListLength(L);  //测量长度 
301         }
302         else if(j == 2)
303         {
304             GetElem(L);     //获取元素 
305         }
306         else if(j == 3)
307         {
308             LocateElem(L); //定位查找 
309         }
310         else if(j == 4)
311         {
312             ListInsert(L);  //插入 
313         } 
314         else if(j == 5)
315         {
316             ListDelete(L); //删除 
317         }
318         else if(j == 6)
319         {
320             exit(0);
321         }
322         else 
323         {
324             printf("数据输入有误\n"); 
325         }
326     }
327     
328     DestoryLinkList(&L);
329     
330     return 0;
331 }