将顺序表（ADT SqList）的数据对象，数据关系及基本操作（函数）用C语言实现，并测试。
手机用户点击代码移动可查看未显示内容
1.SqList.h头文件内容
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#define LIST_INIT_SIZE 100 #define LISTINCREASEMENT 10 typedef int ElemType; typedef struct { ElemType *elem; int length; int listsize; }SqList; //函数名： void ListInit(SqList &L); void ListOutput(SqList &L); void Listvisit(ElemType e); int ListInsert(SqList &L,int i,ElemType e); int ListDelete(SqList &L,int i); int ListGetLength(SqList L); int ListClear(SqList &L); int ListDestroy(SqList &L); int ListIsEmpty(SqList L); int ListLocateElem(SqList L,ElemType e); int ListGetElem(SqList L,int i,ElemType &e); int ListPriorElem(SqList L, ElemType cur_e, ElemType &pre_e); int ListNextElem(SqList L, ElemType cur_e, ElemType &next_e); void ListTraverse(SqList L, void(*visit)(ElemType)); void ListSort(SqList &L,int t); void ListMerge(SqList La, SqList Lb, SqList &Lc); |
函数实现
1.顺序表的初始化
|
1 2 3 4 5 6 7 |
void ListInit(SqList &L){ L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; } |
注释：为了检查顺序表是否初始化，本人调用了检查顺序表是否为空的函数
（bool ListIsEmpty(SqList L)）函数实现在下面会讲到。
2.顺序表的输出
|
1 2 3 4 5 6 |
void ListOutput(SqList &L){ int i; for (i = 0; i < L.length; i++) printf("%d ", L.elem[i]); printf("\n"); } |
3.顺序表的长度
|
1 2 3 4 5 6 |
int ListGetLength(SqList L){ if(L.elem!=NULL) return L.length; else return ERROR; } |
4.插入一个值到顺序表中
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int ListInsert(SqList &L,int i,ElemType e){ ElemType *q,*p,*newbase; if(i<1||i>L.length+1)return ERROR; if(L.length>=L.listsize) { newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREASEMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREASEMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } |
5.删除顺序表中的一个值
|
1 2 3 4 5 6 7 8 9 10 11 |
int ListDelete(SqList &L,int i){ ElemType *p,*q; if(i<1||i>L.length+1)return ERROR; p=&(L.elem[i-1]); q=L.elem+L.length-1; if (i == 1)*p = *(p + 1); for(++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; } |
6.顺序表是否为空的判断函数
|
1 2 3 4 5 6 |
bool ListIsEmpty(SqList L){ if(L.length==0) return TRUE; else return FALSE; } |
注释：空为TRUE 非空为FALUSE
7.顺序表数据的位置查询
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int ListLocateElem(SqList L, ElemType e){ int i,k=-1; for(i=1;i<=L.length;i++) { if(*(L.elem+(i-1))==e) { k=i; break; } } return k; } |
8.顺序表某个位置的数据查询
|
1 2 3 4 5 6 7 8 9 10 |
int ListGetElem(SqList L, int i, ElemType &e){ if(i<1||i>L.length+1)return ERROR; int j; ElemType *p; p=L.elem; for(j=0;j<i-1;j++) p++; e=*p; return OK; } |
9.查询某个值的前驱和后继
前驱：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int ListPriorElem(SqList L, ElemType cur_e, ElemType &pre_e) { int i; for (i = 1; i <= L.length; i++) { if (L.elem[i-1] == cur_e) break; } if (i < 1 || i > L.length+1)return ERROR; else { pre_e = L.elem[i-2]; return OK; } } |
后继：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int ListNextElem(SqList L, ElemType cur_e, ElemType &next_e) { int i; for (i = 1; i <= L.length; i++) { if (L.elem[i-1] == cur_e) break; } if (i>L.length)return ERROR; else { next_e = L.elem[i]; return OK; } } |
10.两个非递减顺序表的合并
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void ListMerge(SqList La, SqList Lb, SqList &Lc){ ElemType *pa, *pb,*pc; pa = La.elem; pb = Lb.elem; Lc.listsize =Lc.length= La.length + Lb.length; pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType)); if (!Lc.elem)exit(OVERFLOW); ElemType *pa_last, *pb_last; pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1; while (pa <= pa_last&&pb <= pb_last) { if (*pa <= *pb)*pc++ = *pa++; else *pc++ = *pb++; } while (pa <= pa_last)*pc++ = *pa++; while (pb <= pb_last)*pc++ = *pb++; }//非递减归并 |
11.顺序表的排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
void ListSort(SqList &L,int t) { int i,j; ElemType m; if (t == 0) { for (i = 0; i < L.length-1; i++) { for (j = 0; j < L.length - 1 - i; j++) { if (L.elem[j]>L.elem[j + 1]) { m = L.elem[j]; L.elem[j] = L.elem[j + 1]; L.elem[j + 1] = m; } } } } else { for (i = 0; i < L.length - 1; i++) { for (j = 0; j < L.length - 1 - i; j++) { if (L.elem[j]<L.elem[j + 1]) { m = L.elem[j]; L.elem[j] = L.elem[j + 1]; L.elem[j + 1] = m; } } } } }//冒泡法排序 |
12.顺序表的清除和销毁
清除：
|
1 2 3 4 5 6 7 8 9 10 |
int ListClear(SqList &L) { if(L.elem==NULL) return ERROR; else { L.length=0; return OK; } } |
销毁：
|
1 2 3 4 5 6 7 8 9 10 |
int ListDestroy(SqList &L) { if(L.elem==NULL) return ERROR; else { free(L.elem); return OK; } } |
注释：清除后使用LISTISEMPTY函数判断是否清空。
MAIN函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
int main() { printf("------------------------------------------\n"); SqList L; printf("顺序表L初始化......\n"); ListInit(L); printf("------------------------------------------\n"); printf("检查顺序表是否为空：\n"); if (ListIsEmpty(L) == TRUE) printf("EMPTY\n"); else printf("SUBFULL\n"); printf("------------------------------------------\n"); int i,n; printf("输入顺序表的长度（小于100）：\n"); scanf("%d", &n); printf("输入%d个值：\n",n); for (i = 0; i < n; i++,L.length++) scanf("%d", &L.elem[i]); printf("检查顺序表：\n"); ListOutput(L); printf("------------------------------------------\n"); printf("顺序表当前长度为%d。\n", ListGetLength(L)); printf("------------------------------------------\n"); printf("插入一个值到当前顺序表中：\n"); printf("输入插入的位置：\n"); int p; scanf("%d", &p); printf("输入插入的值：\n"); ElemType e; scanf("%d", &e); ListInsert(L, p, e); printf("顺序表的值：\n"); ListOutput(L); printf("顺序表当前长度为%d\n", ListGetLength(L)); printf("------------------------------------------\n"); printf("删除当前顺序表中的一个值：\n"); printf("输入删除的位置：\n"); scanf("%d", &p); ListDelete(L, p); printf("顺序表的值：\n"); ListOutput(L); printf("顺序表当前长度为%d\n", ListGetLength(L)); printf("------------------------------------------\n"); printf("检查顺序表是否为空：\n"); if (ListIsEmpty(L) == TRUE) printf("EMPTY\n"); else printf("SUBFULL\n"); printf("------------------------------------------\n"); printf("顺序表数据的位置查询：\n"); printf("输入需要查询的值：\n"); ElemType d; scanf("%d", &e); if (ListLocateElem(L, e) >= 1) printf("%d在第%d个位置。\n",e,ListLocateElem(L,e)); else printf("ERROR"); printf("------------------------------------------\n"); printf("顺序表位置的数据查询：\n"); printf("输入需要查询的位置：\n"); scanf("%d", &p); if (ListGetElem(L,p,e) == OK) printf("第%d个元素是%d。\n",p,e); else printf("ERROR"); printf("------------------------------------------\n"); printf("查询某个值的前驱和后继：\n"); ElemType pre_e, next_e; printf("输入此值：\n"); scanf("%d", &e); ListPriorElem(L, e, pre_e); ListNextElem(L, e, next_e); printf("%d的前驱是%d，后继是%d。\n", e,pre_e,next_e); printf("------------------------------------------\n"); printf("若顺序表L为非递减排列，\n请创建非递减顺序表M\n并使用非递减归并函数（Y/N)?\n"); char flag; getchar(); scanf("%c", &flag); if (flag == 'Y') { SqList M, N; printf("顺序表M初始化......\n"); ListInit(M); printf("输入顺序表的长度（小于100）：\n"); scanf("%d", &n); printf("输入%d个值：\n", n); for (i = 0; i < n; i++, M.length++) scanf("%d", &M.elem[i]); printf("检查顺序表L和M：\n"); printf("L: "); ListOutput(L); printf("M: "); ListOutput(M); printf("非递减归并后：\n"); ListMerge(L, M, N); ListOutput(N); } system("pause"); printf("------------------------------------------\n"); printf("顺序表排序：\n"); printf("降序排列为：\n"); ListSort(L, -1); ListOutput(L); printf("升序排列为：\n"); ListSort(L, 0); ListOutput(L); printf("------------------------------------------\n"); printf("顺序表清除中......\n"); ListClear(L); printf("检查顺序表是否为空：\n"); if (ListIsEmpty(L) == TRUE) printf("EMPTY\n"); else printf("SUBFULL\n"); printf("\n"); printf("顺序表销毁中......\n"); ListDestroy(L); printf("------------------------------------------\n"); system("pause"); return 0; } |
小结：
1. 实验中使用工程文件使得代码文件更有可移植性并程序化，更加规范。
2. 试验中代码文件由VC++6.0转移到VS或Code::Blocks时应打开工程文件的.dsp文件使得代码自动导入。
3. 顺序表中Merge函数应注意要对新的归并顺序表进行实时的Malloc动态分配，且调用该函数时应注意两个顺序表必须是非递减的。
4. 在顺序表的输入时，for语句最好实时对L.length进行修改，同样地在Insert和Delete函数中也应采取同样地措施。
5. 在本人实现的顺序表中，要注意内部存储是从0开始的，但是在面向用户时是从1开始。
6. 对&引用标识符在函数调用时要注意。
7. 由于函数只能return一个值，可以使用地址来返回其它值（增加一个变量）如前驱函数后继函数等。
8. 由于ElemType在程序中被定义为int,因此可以使用scanf(%d)
类型不同时要注意。推荐使用C++ cin函数。
原创非商业转载请注明出处，商业转载请联系。
