单链表的基本操作

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 #include<time.h>
  5 
  6 
  7 typedef struct LNode 
  8 {    
  9     int data;
 10     struct LNode *next;
 11 }LNode;
 12 
 13 //初始化单链表
 14 int initList(LNode *&L)
 15 {
 16     L = (LNode *)malloc(sizeof(LNode));
 17     L->next = NULL;
 18     printf("链表初始化成功\n");
 19     return 1;
 20 }
 21 
 22 
 23 //给定一个单链表初值，后续每个结点为累计+3赋值 ，长度为n（头插法）
 24 int InsertList(LNode *L, int s ,int n)
 25 {
 26     if(n<1)
 27     {    
 28         printf("请输入正确的长度！！");
 29         return 0;
 30     }
 31     //t用来指向新生成的节点
 32     LNode *t;
 33 
 34     int p=0;
 35     int q=s;
 36     while(p<n)
 37     {
 38         t=(LNode *)malloc(sizeof(LNode));
 39         t->data=q;
 40         t->next=L->next;
 41         L->next=t;    
 42         q-=3; 
 43         p++;    
 44     }
 45     return 1;
 46 
 47 }
 48 
 49 
 50 //给定一个单链表初值，后续每个结点为累计+3赋值 ，长度为n（尾插法）
 51 int InsertList2(LNode *L, int s ,int n)
 52 {
 53     if(n<1)
 54     {    
 55         printf("请输入正确的长度！！");
 56         return 0;
 57     }
 58     //t用来指向新生成的节点
 59     LNode *t,*r;
 60     r=L;
 61 
 62     int q=s;
 63     for(int i=0;i<n;i++)
 64     {
 65         t=(LNode*)malloc(sizeof(LNode));
 66         t->data=q;
 67         r->next=t;
 68         r=r->next;
 69         q+=3;
 70     }
 71     r->next=NULL;
 72     return 1;
 73 
 74 }
 75 //遍历链表
 76 void OutList(LNode *L)
 77 {
 78     LNode *p;
 79     p=L->next;
 80     while(p)
 81     {
 82         printf("%3d \n",p->data);
 83         p=p->next;
 84     }
 85 }
 86 //实现a，b两个有序链表的有序拼接，拼接后为串c
 87 void merge(LNode *a,LNode *b,LNode *&c)
 88 {
 89     LNode *p=a->next;
 90     LNode *q=b->next;
 91     LNode *r;
 92     c=a;
 93     c->next=NULL;
 94     free(b);
 95     r=c;
 96     while(p!=NULL && q!=NULL)
 97     {
 98         if(p->data<=q->data)
 99         {
100             r->next=p;
101             p=p->next;
102             r=r->next;
103         }
104         else
105         {
106             r->next=q;
107             q=q->next;
108             r=r->next;
109         }
110     }
111     r->next=NULL;
112     if(p!=NULL)
113         r->next=p;
114     if(q!=NULL)
115         r->next=q;
116 }
117 //查找链表中是否存在值为x的元素，若存在则删除，否则返回0
118 int findAndDelete(LNode *L,int x)
119 {
120     LNode *p,*q;
121     p=L;
122     while(p->next!=NULL)
123     {
124         if(p->next->data==x)
125             break;
126         p=p->next;
127 
128     }
129     if(p->next==NULL)
130     {
131         return 0;
132     }
133     else
134     {
135         q=p->next;
136         p->next=p->next->next;
137         free(q);
138         return 1;
139     }
140 }
141 void main()
142 {    
143     LNode *L;
144     LNode *t;
145     LNode *L1;
146     initList(L);
147     initList(L1);
148     if(InsertList2(L,5,5)==1)
149     {
150         printf("赋值成功\n");
151     }else
152         printf("赋值失败");
153     if(InsertList(L1,30,5)==1)
154     {
155         printf("赋值成功\n");
156     }else
157         printf("赋值失败");
158 
159     merge(L1,L,t);
160     OutList(t);
161     findAndDelete(t,5);
162     OutList(t);
163 
164 }