数据结构实验报告之链表顺序表的操作

1、编写程序实现顺序表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。在此基础上设计一个主程序完成如下功能：

（1）初始化顺序表L；

（2）依次在表尾插入a，b，c，d，e五个元素；

（3）输出顺序表L；

（4）输出顺序表L的长度；

（5）判断顺序表L是否为空；

（6）输出顺序表L的第4个元素；

（7）输出元素c的位置；

（8）在第3个位置上插入元素f，之后输出顺序表L；

（9）删除L的第2个元素，之后输出顺序表L；

（10）销毁顺序表L。

2、编写程序实现单链表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。在此基础上设计一个主程序完成如下功能：

（1）初始化单链表L；

（2）依次在表尾插入a，b，c，d，e五个元素；

（3）输出单链表L；

（4）输出单链表L的长度；

（5）判断单链表L是否为空；

（6）输出单链表L的第4个元素；

（7）输出元素c的位置；

（8）在第3个位置上插入元素f，之后输出单链表L；

（9）删除L的第2个元素，之后输出单链表L；

（10）销毁单链表L。

  1 顺序表
  2 #include<stdio.h>
  3 #include<malloc.h>
  4 #include<stdlib.h>
  5 
  6 #define  TRUE     1
  7 #define  FALSE    0
  8 #define  OK           1
  9 #define  ERROR   0
 10 #define  INFEASIBLE  -1
 11 #define  OVERFLOW  -2
 12 typedef  int  Status;
 13 typedef  char ElemType;
 14 
 15 #define   LIST_INIT_SIZE    100                                                                        //线性表存储空间的初始分配量
 16 #define   LISTINCREMENT   10                                                                        //线性表存储空间的分配增量
 17 typedef  struct {
 18     ElemType  *elem;                                                                                  //存储空间基地址
 19     int    length;                                                                                  //当前长度
 20     int    listsize;                                                                                //当前分配的存储容量
 21 } SqList;
 22 
 23 Status InitList_Sq(SqList &L) {                                                                    //算法2.3
 24     L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
 25     if (!L.elem) exit(OVERFLOW);                                                                     //存储分配失败
 26     L.length = 0;                                                                                    //空表长度为0
 27     L.listsize = LIST_INIT_SIZE;                                                                        //初始存储容量
 28     return OK;
 29 }//InitList_Sq
 30 
 31 Status ListInsert_Sq(SqList &L, int i, ElemType e) {                                                //算法2.4
 32     ElemType *newbase, *p, *q;
 33     if (i<1 || i>L.length + 1)   return  ERROR;                                                    //i值不合法
 34     if (L.length >= L.listsize)
 35     {                                                                                                //当前存储空间已满，增加分配
 36         newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
 37         if (!newbase)  exit(OVERFLOW);                                                                //存储分配失败
 38         L.elem = newbase;                                                                                //新基址
 39         L.listsize += LISTINCREMENT;                                                                    //增加存储容量
 40     }
 41     q = &(L.elem[i - 1]);                                                                                //q为插入位置
 42     for (p = &(L.elem[L.length - 1]); p >= q; --p)  *(p + 1) = *p;                                                //元素右移
 43     *q = e;                                                                                              //插入e
 44     ++L.length;                                                                                        //表长增1
 45     return OK;
 46 }
 47 
 48 void DispSqList(SqList L)
 49 {
 50     int i;
 51     for (i = 0; i < L.length; i++)
 52         printf("%c ", L.elem[i]);
 53 }
 54 
 55 Status ListDelete(SqList &L, int i, ElemType &e)
 56 {
 57     ElemType  *p,*q;
 58     if ((i < 1) || (i > L.length)) return ERROR;
 59     p = &(L.elem[i - 1]);
 60     e = *p;
 61     q = L.elem + L.length - 1;
 62     for (++p; p <= q; ++p)
 63         *(p - 1) = *p;
 64     --L.length;
 65     return OK;
 66 } //ListDelete_Sq
 67 
 68 Status GetElem(SqList L, int i, ElemType &e)
 69 {
 70     if (L.length == 0 || i<1 || i>L.length)
 71         return ERROR;
 72     e = L.elem[i - 1];
 73     return OK;
 74 }
 75 
 76 int ListLength(SqList L)
 77 {
 78     return(L.length);
 79 }
 80 
 81 Status DestroyList(SqList &L)
 82 {
 83     free(L.elem);
 84     L.length = 0;
 85     return OK;
 86 }
 87 
 88 Status ListEmpty(SqList L)
 89 {
 90     return(L.length == 0);
 91 }
 92 
 93 int LocateElem(SqList L, ElemType e)
 94 {
 95     int i = 0;
 96     while (i < L.length && L.elem[i] != e) i++;
 97     if (i >= L.length)  return 0;
 98     else  return i + 1;
 99 }
100 
101 void main()
102 {
103     SqList  h;
104     ElemType e;
105     InitList_Sq(h);
106     ListInsert_Sq(h, h.length + 1, 'a');
107     ListInsert_Sq(h, h.length + 1, 'b');
108     ListInsert_Sq(h, h.length + 1, 'c');
109     ListInsert_Sq(h, h.length + 1, 'd');
110     ListInsert_Sq(h, h.length + 1, 'e');
111     DispSqList(h);
112     printf("%d

",ListLength(h));
113     ListEmpty(h);
114     if (ListEmpty(h))
115     {
116         printf("Empty

");
117     }
118     else
119     {
120         printf("Not empty

");
121     }
122     GetElem(h, 4, e);
123     printf("%c
", e);
124     printf("%d
",LocateElem(h, 'c'));
125     ListInsert_Sq(h,3,' f');
126     DispSqList(h);
127     ListDelete(h, 2, e);
128     DispSqList(h);
129     DestroyList(h);
130 }
131 
132 
133 
134 
135 
136 单链表
137 
138 
139 
140 #include<stdio.h>
141 #include<malloc.h>
142 #include<stdlib.h>
143 
144 #define  TRUE     1
145 #define  FALSE    0
146 #define  OK           1
147 #define  ERROR   0
148 #define  INFEASIBLE  -1
149 #define  OVERFLOW  -2
150 typedef  int  Status;
151 
152 typedef  char ElemType;
153 
154 
155 typedef  struct LNode {
156     ElemType    data;
157     int length;
158     struct  LNode  *next;
159 }LNode, *LinkList;
160 
161 
162 Status InitList_L(LinkList &L) {
163     L = (LinkList)malloc(sizeof(LNode));
164     L->next = NULL;
165     return OK;
166 }
167 
168 Status ListInsert_L(LinkList L, int i, ElemType e) {
169     LinkList p = L,s;
170     int j = 0;
171     while (p && j < i - 1)
172     {
173         p = p->next;
174         ++j;
175     }
176     if (!p || j > i - 1) 
177     { 
178         return ERROR; 
179     }
180     else
181     {
182         s = (LinkList)malloc(sizeof(LNode));
183         s->data = e;
184         s->next = p->next;
185         p->next = s;
186         return OK;
187     }
188 }
189 
190 void DispList_L(LinkList L)
191 {
192     LinkList p = L->next;
193     while (p != NULL)
194     {
195         printf("%c
", p->data);
196         p = p->next;
197     }
198 
199 }
200 
201 void DestoryList(LinkList &L)
202 {
203     LinkList p = L, q = p->next;
204     while (q != NULL)
205     {
206         free(p);
207         p = q;
208         q = p->next;
209     }
210     free(p);
211 }
212 
213 Status ListLength_L(LinkList L) {
214     LinkList p = L; int n = 0;
215     while (p->next != NULL)
216     {
217         n++;
218         p = p->next;
219     }
220     return (n);
221 }
222 
223 Status ListDelete(LinkList L, int i, ElemType &e){
224     int j;
225     LinkList p, q;
226     p = L; 
227     j = 1;
228     while (p->next && j < i)
229     {
230         p = p->next;
231         ++j;
232     }
233     if (!(p->next) || j > i)
234     {
235         return ERROR;
236     }
237     q = p->next;
238     p->next = q->next;
239     e = q->data;
240     free(q);
241     return OK;
242 }
243 
244 Status ListEmpty_L(LinkList L)
245 {
246     return(L->length == 0);
247 }
248 
249 Status GetElem(LinkList L, int i, ElemType &e)
250 {
251     int j;
252     LinkList p;
253     p = L->next;
254     j = 1;
255     while (p&&j<i)
256     {
257         p = p->next;
258         ++j;
259     }
260     if (!p || j > i)
261     {
262         return ERROR;
263     }
264     e = p->data;
265     return OK;
266 }
267 
268 Status LocateElem(LinkList L, int e)
269 {
270     LinkList p = L;
271     int n=0;
272     //p->length = 0;
273     while (p != NULL)
274     {
275         if(p->data != e)
276         {
277             p = p->next;
278             n++;
279         }
280         else
281         {
282             break;
283         }
284     }
285     if(p != NULL)
286     {
287         return n;
288     }
289     else
290     {
291         return ERROR;
292     }
293 }
294 
295 void main()
296 {
297     LinkList  h;
298     ElemType e;
299     InitList_L(h);
300     ListInsert_L(h, 1, 'a');
301     ListInsert_L(h, 2, 'b');
302     ListInsert_L(h, 3, 'c');
303     ListInsert_L(h, 4, 'd');
304     ListInsert_L(h, 5, 'e');
305     DispList_L(h);
306     printf("%d
", ListLength_L(h));
307     if (ListEmpty_L(h))
308     {
309         printf("Empty

");
310     }
311     else
312     {
313         printf("Not empty

");
314     }
315     GetElem(h, 4, e);
316     printf("%c
", e);
317     printf("%d
", LocateElem(h, 'c'));
318     ListInsert_L(h, 3, 'f');
319     DispList_L(h);
320     ListDelete(h, 2, e);
321     DispList_L(h);
322     DestoryList(h);
323 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lumc5/p/11540765.html