单链表的创建及增删改查功能的实现

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<math.h>
  4 
  5 typedef int datatype;
  6 typedef struct node{          //结点类型定义
  7     datatype data;           //结点的数据域
  8     struct node *next;      //结点的指针域
  9 }listnode,*linklist;
 10 listnode *p;
 11 linklist head;
 12 /*注意：定义结点结构时，有几点需要注意：
 13         linklist和listnode *是不同名字的同一个指针类型，
 14         linklist类型的指针变量head表示他是单链表的头指针，
 15         listnode *类型的指针变量p表示它是指向某一结点的指针*/
 16 linklist initlist()
 17 {
 18     linklist l;
 19     l=(listnode*)malloc(sizeof(listnode));
 20     if(l==null)
 21     {
 22         printf("分配空间失败！");
 23         exit(1);
 24     }
 25     l->next=null;
 26     return l;
 27 }
 28 
 29 /*头插法建立单链表*/
 30 linklist creatlistf()
 31 {
 32     datatype x;
 33     linklist l;
 34     listnode *s;
 35     l=(listnode *)malloc(sizeof(listnode));      //头结点
 36     if(l==null)                                 //检查l是否分配到储存空间
 37     {
 38         printf("分配空间失败！");
 39         exit(1); 
 40     }
 41     l->next=null;
 42     scanf("%d",&x);
 43     while(x!=0)
 44     {
 45         s=(listnode *)malloc(sizeof(listnode));     //为新插入的结点申请空间
 46         if(s==null)
 47         {
 48             printf("分配空间失败！");
 49             exit(1);
 50         }
 51         s->data=x;
 52         s->next=l->next;
 53         l->next=s;
 54         scanf("%d",&x);
 55     }
 56     return l;
 57 }
 58 
 59 
 60 /*尾插法建立单链表*/
 61 linklist creatlistl()
 62 {
 63     datatype x;
 64     linklist l=(listnode *)malloc(sizeof(listnode));         //头结点
 65     if(l==null)
 66     {
 67         printf("分配空间失败！");
 68         exit(1);
 69     }
 70     listnode *s,*r;
 71     r=l;
 72     scanf("%d",&x);
 73     while(x!=0)           //以0输入表示结束
 74     {
 75         s=(listnode *)malloc(sizeof(listnode));          //为新插入的结点申请空间
 76         if(s==null)
 77         {
 78             printf("分配空间失败！");
 79             exit(1);
 80         }
 81         s->data=x;
 82         r->next=s;
 83         r=s;
 84         scanf("%d",&x);
 85     }
 86     r->next=null;             //单链表的最后一个指针为空
 87     return l;
 88 }
 89 
 90 //获取链表长度 
 91 int getlength(linklist l)
 92 {
 93     int num=0;
 94     listnode *p;
 95     p=l->next;
 96     while(p!=null)
 97     {
 98         num++;
 99         p=p->next;
100     }
101     return(num);
102 }
103 
104 //查找第i位元素 
105 listnode *getnode(linklist l,int i)
106 {
107     int j=1;
108     listnode *p;
109     if(i<1||i>getlength(l))
110     {
111         printf("查找的位置不正确！");
112         exit(1);
113     }
114     p=l->next;
115     while(p!=null&&j<i)
116     {
117         p=p->next;
118         j++;
119     }
120     return p;
121 }
122 
123 //查找元素x 
124 int locatelisti(linklist l,datatype x)
125 {
126     listnode *p=l->next;
127     int i=1;
128     while(p!=null&&p->data!=x)
129     {
130         p=p->next;
131         i++;
132     }
133     if(p==null)
134         return 0;
135     else
136         return i;
137 } 
138 
139 //在第i位插入元素x 
140 void insertlist(linklist l,datatype x,int i)
141 {
142     listnode *p,*q,*s;
143     int j=1;
144     p=l;
145     if(i<1||i>getlength(l)+1)
146     {
147         printf("插入位置不正确！");
148         exit(1);
149     }
150     s=(listnode *)malloc(sizeof(listnode));
151     if(s==null)
152     {
153         printf("分配空间失败！");
154         exit(1);
155     }
156     s->data=x;
157         while(j<=i)
158         {
159             q=p;
160             p=p->next;
161             j++;
162         }
163         s->next=p;
164         q->next=s;
165 }
166 
167 //删除第i位元素 
168 void deletelist(linklist l,int i)
169 {
170     listnode *p,*q;
171     int j=1;
172     p=l;
173     if(i<1||i>getlength(l))
174     {
175         printf("删除位置不正确！");
176         exit(1);
177     }
178     while(j<i)
179     {
180         p=p->next;
181         j++;
182     }
183     q=p->next;
184     p->next=q->next;
185     free(q);
186 }
187 
188 //打印链表 
189 void printlist(linklist l)
190 {
191     listnode *p;
192     p=l->next;
193     printf("链表元素如下：\n");
194     while(p!=null)
195     {
196         printf("%d ",p->data);
197         p=p->next;
198     }
199     printf("\n");
200 }
201 int main()
202 {
203     datatype a;
204     head=initlist();
205     printf("我们将采用头插法创建一个单链表l!\n请输入您要输入的数据（以空格隔开，以0结束！）\n");
206     head=creatlistf();
207     printf("单链表的长度为：%d\n",getlength(head));
208     printf("请输入您要查找元素的结点序号：");
209     scanf("%d",&a);
210     printf("第%d个元素为：%d\n",a,getnode(head,a)->data);
211     printf("请输入您要查找的元素：");
212     scanf("%d",&a);
213     printf("您查找的元素%d在链表中的第%d个位置\n",a,locatelisti(head,a));
214     int x,i;
215     printf("请输入您要插入元素的数值以及位置：");
216     scanf("%d%d",&x,&i);
217     insertlist(head,x,i);
218     printlist(head);
219     printf("请输入您想要删除元素的位置：");
220     scanf("%d",&i);
221     deletelist(head,i);
222     printlist(head);
223     return 0;
224 }