• ElemType.h
• DynaSeqList.h
• DynaSeqList.cpp
• ElemType.cpp
• Lab.cpp
• 測試結果
• 注意

ElemType.h

/*** *ElemType.h - ElemType的定義 * ****/#ifndef ELEMTYPE_H #define ELEMTYPE_Htypedef int ElemType; //定義數據類型int compare(ElemType x, ElemType y); //聲明判斷函數 void visit(ElemType e); //聲明打印函數#endif /* ELEMTYPE_H */

DynaSeqList.h

/*** * DynaSeqList.h - 動態順序表的定義 * ****/#if !defined(DYNASEQLIST_H) #define DYNASEQLIST_H#include "ElemType.h"/*------------------------------------------------------------ 順序表結構的定義 ------------------------------------------------------------*/typedef struct List {ElemType *elem; // 存儲空間的基址int length; // 順序表中結點元素的個數int listsize; // 順序表的存儲空間大小 } SqList;/*------------------------------------------------------------ // 順序表的基本操作 ------------------------------------------------------------*/bool InitList(SqList *L); //線性表初始化 void DestroyList(SqList *L); //線性表銷毀 bool ListEmpty(SqList L); //線性表判空 int ListLength(SqList L); //線性表長度 bool GetElem(SqList L, int i, ElemType *e); //獲得下標 i 的數據元素 int LocateElem(SqList L, ElemType e, int (*fp)(ElemType, ElemType));//獲得和元素e有關的元素 bool PriorElem(SqList L, ElemType cur_e, ElemType *pre_e); //獲得數據元素的前驅 bool NextElem(SqList L, ElemType cur_e, ElemType *nxt_e); //獲得數據元素的后繼 void ListTraverse(SqList L, void (*fp)(ElemType)); //遍歷線性表 void ClearList(SqList *L); //清空線性表 bool ListInsert(SqList* L, int i, ElemType e); //在 i 位置插入數據元素 void HeadInsert(SqList* L, ElemType e); //線性表的頭部插入元素 void TailInsert(SqList* L, ElemType e); //線性表的尾部插入元素 bool ListDelete(SqList *L, int i, ElemType *e); //刪除 i 位置的數據元素 void ListDeleteHead(SqList* L,ElemType* e); //刪除線性表的頭部元素 void ListDeleteTail(SqList* L,ElemType* e); //刪除線性表的尾部元素 void unionList(SqList* La, SqList Lb); //求兩個線性表的并集 #endif /* DYNASEQLIST_H */

DynaSeqList.cpp

/*** *DynaSeqList.cpp - 動態順序表，即順序表的動態數組實現 ****/ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <memory.h> #include <assert.h> #include "DynaSeqList.h"const int LIST_INIT_SIZE = 100; // 表初始分配的最大長度 const int LISTINCREMENT = 10; // 分配內存的增量/*------------------------------------------------------------ 操作目的： 初始化順序表 初始條件： 無 操作結果： 構造一個空的線性表 函數參數：SqList *L 待初始化的線性表 返回值：bool 操作是否成功 ------------------------------------------------------------*/ bool InitList(SqList *L) {L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));if (!L->elem)return false;else{L->length = 0;L->listsize = LIST_INIT_SIZE;return true;} }/*------------------------------------------------------------ 操作目的： 銷毀順序表 初始條件： 線性表L已存在 操作結果： 銷毀線性表L 函數參數：SqList *L 待銷毀的線性表 返回值：無 ------------------------------------------------------------*/ void DestroyList(SqList *L) {if (L->elem)free(L->elem);L->elem = NULL; }/*------------------------------------------------------------ 操作目的： 判斷順序表是否為空 初始條件： 線性表L已存在 操作結果： 若L為空表，則返回true，否則返回false 函數參數：SqList L 待判斷的線性表 返回值：bool 是否為空 ------------------------------------------------------------*/ bool ListEmpty(SqList L) {if (!L.length)return true;elsereturn false; }/*------------------------------------------------------------ 操作目的： 得到順序表的長度 初始條件： 線性表L已存在 操作結果： 返回L中數據元素的個數 函數參數：SqList L 線性表L 返回值：int 數據元素的個數 ------------------------------------------------------------*/ int ListLength(SqList L) {return L.length; }/*------------------------------------------------------------ 操作目的： 得到順序表的第i個元素 初始條件： 線性表L已存在，1<=i<=ListLength(L) 操作結果： 用e返回L中第i個數據元素的值 函數參數：SqList L 線性表Lint i 數據元素的位置ElemType *e 第i個數據元素的值 返回值：bool 操作是否成功 ------------------------------------------------------------*/ bool GetElem(SqList L, int i, ElemType *e) {if (i < 1 || i > L.length)return false;else*e = L.elem[i - 1];return true; }/*------------------------------------------------------------ 操作目的： 得到順序表指定元素的位置 初始條件： 線性表L已存在 操作結果： 返回L中第一個與e滿足關系compare()的數據元素的位序。若這樣的元素不存在則返回0。 函數參數：SqList L 線性表LElemType e 數據元素eint (*fp)() 用于比較相等的函數指針 返回值：int 與e滿足關系compare()的數據元素的位序 ------------------------------------------------------------*/ int LocateElem(SqList L, ElemType e, int (*fp)(ElemType, ElemType)) {for (int i = 0; i < L.length; i++){if(!(*fp)(e,L.elem[i]))return i + 1;}return 0; }/*------------------------------------------------------------ 操作目的： 得到順序表指定元素的前驅 初始條件： 線性表L已存在 操作結果： 若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅，否則操作失敗，pre_e無定義 函數參數：SqList L 線性表LElemType cur_e 數據元素cur_eElemType *pre_e 前驅數據元素 返回值：bool 操作是否成功 ------------------------------------------------------------*/ bool PriorElem(SqList L, ElemType cur_e, ElemType *pre_e) {int i = LocateElem(L, cur_e, compare);if (i!=0 && i!= 1){*pre_e = L.elem[i - 2];return true;}return false; }/*------------------------------------------------------------ 操作目的： 得到順序表指定元素的后繼 初始條件： 線性表L已存在 操作結果： 若cur_e是L的數據元素，且不是最后一個，則用nxt_e返回它的后繼，否則操作失敗，nxt_e無定義 函數參數：SqList L 線性表LElemType cur_e 數據元素cur_eElemType *nxt_e 后繼數據元素 返回值：bool 操作是否成功 ------------------------------------------------------------*/ bool NextElem(SqList L, ElemType cur_e, ElemType *nxt_e) {int i = LocateElem(L, cur_e, compare);if (i!=0 && i != L.length){*nxt_e = L.elem[i];return true;}return false; }/*------------------------------------------------------------ 操作目的： 遍歷順序表 初始條件： 線性表L已存在 操作結果： 依次對L的每個元素調用函數fp 函數參數：SqList L 線性表Lvoid (*fp)() 訪問每個數據元素的函數指針 返回值：無 ------------------------------------------------------------*/ void ListTraverse(SqList L, void (*fp)(ElemType)) {for (int i = 0; i < L.length; i++)(*fp)(L.elem[i]);printf("\n"); }/*------------------------------------------------------------ 操作目的： 清空順序表 初始條件： 線性表L已存在 操作結果： 將L置為空表 函數參數：SqList *L 線性表L 返回值：無 ------------------------------------------------------------*/ void ClearList(SqList *L) {L->length = 0; }/*------------------------------------------------------------ 操作目的： 在順序表的指定位置插入結點，插入位置i表示在第i個元素之前插入 初始條件： 線性表L已存在，1<=i<=ListLength(L) + 1 操作結果： 在L中第i個位置之前插入新的數據元素e，L的長度加1 函數參數：SqList *L 線性表Lint i 插入位置ElemType e 待插入的數據元素 返回值：bool 操作是否成功 ------------------------------------------------------------*/ bool ListInsert(SqList *L, int i, ElemType e) {ElemType* newbase = NULL;if (i < 1 || i>L->length + 1)return false;if (L->length == L->listsize){newbase = (ElemType*)realloc(L->elem, (LIST_INIT_SIZE + LISTINCREMENT) * sizeof(ElemType));if (!newbase)return false;else{L->elem = newbase;L->listsize += LISTINCREMENT;}}for (int j = L->length; j >= i; j--)L->elem[j] = L->elem[j - 1];L->elem[i - 1] = e;++L->length;return true; }/*------------------------------------------------------------ 操作目的： 在順序表的指定位置插入結點，插入位置i表示在第i個元素之前插入 初始條件： 線性表L已存在，1<=i<=ListLength(L) + 1 操作結果： 在L中第i個位置之前插入新的數據元素e，L的長度加1 函數參數：SqList *L 線性表Lint i 插入位置ElemType e 待插入的數據元素 返回值：bool 操作是否成功 ------------------------------------------------------------*/ void HeadInsert(SqList* L, ElemType e) //線性表的頭插法 {ListInsert(L, 1, e); }/*------------------------------------------------------------ 操作目的： 在順序表的指定位置插入結點，插入位置i表示在第i個元素之前插入 初始條件： 線性表L已存在，1<=i<=ListLength(L) + 1 操作結果： 在L中第i個位置之前插入新的數據元素e，L的長度加1 函數參數：SqList *L 線性表Lint i 插入位置ElemType e 待插入的數據元素 返回值：bool 操作是否成功 ------------------------------------------------------------*/void TailInsert(SqList* L, ElemType e) //線性表的尾插法 {ListInsert(L, L->length + 1, e); } /*------------------------------------------------------------ 操作目的： 刪除順序表的第i個結點 初始條件： 線性表L已存在且非空，1<=i<=ListLength(L) 操作結果： 刪除L的第i個數據元素，并用e返回其值，L的長度減1 函數參數：SqList *L 線性表Lint i 刪除位置ElemType *e 被刪除的數據元素值 返回值：bool 操作是否成功 ------------------------------------------------------------*/ bool ListDelete(SqList* L, int i, ElemType* e) {if (i < 1 || i>L->length)return false;*e = L->elem[i -1];for (int j = i - 1; j < L->length - 1; j++){L->elem[j] = L->elem[j + 1];}--L->length;return true; }void ListDeleteHead(SqList* L, ElemType* e) //線性表的頭刪法 {ListDelete(L,1, e); } void ListDeleteTail(SqList* L, ElemType* e) //線性表的尾刪法 {ListDelete(L, L->length, e); }/*------------------------------------------------------------ 操作目的： 求兩個線性表的并集 初始條件： 兩個線性表La 和 Lb 都已存在且非空，1<=i<=ListLength(La) 1<=i<=ListLength(Lb) 操作結果： 打印連接之后的線性表 函數參數：SqList* La, SqList* Lb 求并集的兩個線性表 返回值：void 不需要返回值 ------------------------------------------------------------*/ void unionList(SqList* La, SqList Lb) {int La_len = ListLength(*La);int Lb_len = ListLength(Lb);ElemType e = 0;for (int i = 0; i < Lb_len; i++){GetElem(Lb, i, &e); // 取 Lb 中第 i 個數據元素賦給 e if (!LocateElem(*La, e, compare)) //如果e和線性表 La 的所有元素都不想等ListInsert(La, La->length, e); //把 e 插入到La的尾部 elsecontinue;} }

ElemType.cpp

/*** *ElemType.cpp - ElemType的實現 * ****/#include <stdio.h> #include "ElemType.h"int compare(ElemType x, ElemType y) {return(x-y); }void visit(ElemType e) {printf("%d\t", e); }

Lab.cpp

#include <stdio.h> #include "DynaSeqList.h"int main() {SqList myList;if (InitList(&myList))printf("初始化成功\n");elseprintf("初始化失敗\n");//頭插法printf("頭插法：\n");for (int i = 0; i < 10; i++){ListInsert(&myList, i, i * 10);}ListTraverse(myList, visit);ElemType x = 0;ElemType data = 0;ListDelete(&myList, 2, &x);printf("刪除的是%d\n", x);ListTraverse(myList, visit);printf("在線性表頭部插入數據元素值為666\n");HeadInsert(&myList, 666);ListTraverse(myList, visit);printf("在線性表尾部插入數據元素值為258\n");TailInsert(&myList, 258);ListTraverse(myList, visit);ListDeleteHead(&myList, &x);printf("刪除線性表的頭部數據元素值為%d\n", x);ListTraverse(myList, visit);ListDeleteTail(&myList, &x);printf("刪除線性表的尾部數據元素值為%d\n", x);ListTraverse(myList, visit);x = 4;data = 555;if (ListInsert(&myList, x, data))printf("成功在第%d的位置插入元素%d\n", x, data);elseprintf("在第%d的位置插入失敗。\n", x);ListTraverse(myList, visit);x = 3;if (ListDelete(&myList, x, &data))printf("成功在第%d的位置刪除元素%d\n", x, data);elseprintf("在第%d的位置刪除失敗。\n", x);ListTraverse(myList, visit);if (ListEmpty(myList))printf("線性表為空\n");elseprintf("線性表非空\n");printf("線性表長度為 %d\n", ListLength(myList));x = 5;if (GetElem(myList, x, &data)){printf("第%d位置的數據元素存在\n", x);}else{printf("%d位置的數據元素不存在\n", x);}printf("獲得第%d位置的數據元素為%d\n", x, data);x = 80;printf("線性表中和%d相等的元素為%d\n", x, LocateElem(myList, x, compare));x = 5;if (GetElem(myList, x, &data)){printf("位置為%d的元素存在\n", x);printf("位置為%d的元素下標為%d\n", x, data);}elseprintf("位置為%d的元素不存在\n", x);x = 70;if (PriorElem(myList, x, &data))printf("數據元素%d的前驅元素存在，前驅元素數值為%d\n", x, data);elseprintf("數據元素%d的前驅元素不存在", x);x = 80;if (NextElem(myList, x, &data))printf("數據元素%d的后繼元素存在，后繼元素數值為%d\n", x, data);elseprintf("數據元素%d的后繼元素不存在\n", x);printf("清空線性表:\n");ClearList(&myList);if (!ListLength(myList))printf("線性表清空成功\n");elseprintf("線性表清空失敗\n");printf("銷毀線性表:\n");DestroyList(&myList);if (NULL ==myList.elem)printf("線性表銷毀成功\n");elseprintf("線性表銷毀失敗\n");return 0; }

測試結果

注意

上面我們所實現的線性表的基本操作數據類型為 int 類型，我們可以把ElemType設置為任何我們所需要的數據類型或者結構體類型，但是所有的操作都不需要搞定從而體現出來數據結構的靈活性，這是非常重要的一點需要讀者去深刻體會。

總結

以上是生活随笔為你收集整理的线性表的动态顺序存储和实现（C语言实现）【线性表】（4）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。