[c/c++] C数据结构: 顺序表 Sequence List

 1 #include "stdio.h"
 2 #include "stdlib.h"
 3 
 4 #define MAXSIZE 10
 5 
 6 typedef int ElemType;
 7 typedef struct {
 8     int *elem;
 9     int length;
10     int listsize;
11 } Sqlist;
12 
13 // 初始化顺序表
14 void
15 initSqlist(Sqlist *L) {
16     L->elem = (int *) malloc(MAXSIZE * sizeof(ElemType));
17     if(!L->elem) exit(0);
18     L->length = 0;
19     L->listsize = MAXSIZE;
20 }
21 
22 // 向顺序表插入元素 
23 void
24 insertSqlistElem(Sqlist *L,int i,ElemType item) {
25     ElemType *base,*insertPtr,*p;
26 
27     if(i < 1 || i > L->length + 1) exit(0); // 为啥要+1 是因为有向顺序表末尾追加
28 
29     if(L->length >= L->listsize) { // 需要申请更多的空间
30         base = (ElemType *) realloc(L->elem,(L->listsize + 10) * sizeof(ElemType));
31         L->elem = base;
32         L->listsize = L->listsize + 10;
33     }
34     insertPtr = &(L->elem[i-1]); // 要插入的元素的启始位置
35     // 从末尾开始到插入点,所有的数据向前移
36     for(p = &L->elem[L->length - 1]; p >= insertPtr; p--) {
37         *(p + 1) = *p;
38     }
39     *insertPtr = item;
40     L->length++;
41 } 
42 
43 // 从顺序表删除元素
44 void 
45 deleteSqlistElem(Sqlist *L,int i) {
46     ElemType *deleteElem,*q;
47 
48     if(i < 1 || i > L->length) exit(0);
49 
50     deleteElem = &(L->elem[i - 1]);
51     q = L->elem + L->length - 1;
52     // 从删除位置开始,后面的数据向前移
53     for(++deleteElem; deleteElem <= q; ++deleteElem) *(deleteElem - 1) = *deleteElem;
54     L->length--;
55 }
56 
57 // 打印输出顺序表
58 void 
59 printSqlist(Sqlist *L) {
60     int i;
61     for(i = 0; i < L->length; i++) printf("%d ",L->elem[i]);
62     printf("\n");
63 }
64 
65 int
66 main() {
67     Sqlist sqlist;
68     int    i;
69 
70     initSqlist(&sqlist);
71     for(i = 0; i < 15; i++) insertSqlistElem(&sqlist, i+1,i+1);
72     printf("\nThe content of the list is \n");
73     printSqlist(&sqlist);
74 
75     deleteSqlistElem(&sqlist,5);
76     printf("\nDelete the fifth element\n");
77     printSqlist(&sqlist);
78 
79     return 0;
80 }