線性表（List）是最常見的也是最簡單的一種數(shù)據(jù)結(jié)構(gòu)。所謂線性表就是零個或者多個數(shù)據(jù)元素的有限序列。注意定義中的幾個關(guān)鍵字：有限、序列。有限就是告訴我們元素個數(shù)是有限的；而序列就是說元素之間是有順序的。
線性表的抽象數(shù)據(jù)類型：
ADT線性表（List）
Data
線性表的數(shù)據(jù)元素集合對象為{a1、a2、……an}，每個數(shù)據(jù)元素的類型均為DataType。其中除了第一個元素外，每一個元素有且只有一個直接前驅(qū)元素，出來最后一個元素外，每一個元素有且只有一個后繼元素。元素之間的關(guān)系是一一對應(yīng)的關(guān)系。
Operation
InitList（&L）：初始化操作，建立一個空的線性表L。
DestoryList（&L）：線性表已存在，銷毀線性表L。
ClearList(&L):線性表已存在，將L重置為空表。
ListEmpty（L）:線性表已存在,若L為空表，則返回TRUE，否則返回FALSE.
ListLength（L）：線性表已存在,返回線性表的數(shù)據(jù)元素的個數(shù)。
GetElem（L,I,&x）：線性表已存在，并且1< i ListInsert（&L,i，e）線性表已存在，并且1< i ListDelist（&L，i，&e）線性表已存在，并且1< i InsertList_Back(*L, x):線性表已存在 ,從線性表的尾部開始插入元素，L的長度加1。 InsertList_Front(*L, ElemType x)：線性表已存在 ,從線性表的頭部開始插入元素，L的長度加1。 DelitelList_Back(*L)：線性表已存在 ,從線性表的尾部開始刪除元素，L的長度減1。 DelitelList_Front(*L)：線性表已存在 ,從線性表的頭部開始刪除元素，L的長度減1。 Delite_Val(*L, key)：線性表已存在，如果線性表中存在key值，則刪除線性表中的key值，L的長度減1,并且返回TRUE,如果線性表中不存在key值，則返回FALSE. void Clear(*L):線性表已存在,清空現(xiàn)象表中的所有元素。 void Sort(*L);線性表已存在，對線性表中存在的元素排序。排序成功返回TRUE，排序失敗返回FALSE。 Reverse (*L)：線性表已存在，并且順序表中存在元素，逆置。逆置成功返回TRUE，失敗返回FALSE。 void Show_list(*L)：線性表已存在，打印輸出，線性表中 所有元素。 endADT 線性表的存儲結(jié)構(gòu)，前邊我們已經(jīng)提過，對于數(shù)據(jù)的存儲結(jié)構(gòu)只有兩種，一種為順序存儲結(jié)構(gòu)，另一種為鏈?zhǔn)酱鎯Y(jié)構(gòu)。線性表作為一種數(shù)據(jù)結(jié)構(gòu)也有兩種存儲結(jié)構(gòu)，今天我們先只談順序存儲結(jié)構(gòu)，也就是順序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)，我將在后邊總結(jié)。 頭文件宏定義等聲明： #include #include #include #include using namespace std; #include"SeqList.h" #define ElemType int #define DEFAULT_SIZE 8 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status; typedef int DataType; 初始化操作： typedef struct List { DataType *bace; int capacity; int length; }SeqList; //初始化順序表，初始化成功返回OK，失敗返回ERROR Status Init_list(SeqList *list) { list->capacity = DEFAULT_SIZE ; list->bace = (DataType *)malloc(sizeof(DataType) * list->capacity ); list->length = 0; if(NULL == list->bace) { return ERROR; } else return OK; } 插入元素操作： //順序表頭插元素，插入成功返回TRUE,插入失敗返回FALSE, Status Insert_front(SeqList *list,ElemType x) { if(list->length >= list->capacity) { cout<<"存儲空間已滿，不能插入"< return FALSE; } for(int i = list->length; i > 0; i--) { list->bace[i] = list->bace[i - 1]; } list->bace[0] = x; list->length++; return TRUE; } //順序表尾插，插入成功返回TRUE,插入失敗返回ERROR Status Insert_back(SeqList *list, ElemType x) { if(list->length >= list->capacity) { cout<<"存儲空間，不能插入"< return FALSE; } list->bace[list->length] = x; list->length++; return TRUE; } //順序表按照值插入，插入成功返回TRUE，插入失敗返回ERROR Status Insert_Value(SeqList *list, ElemType x) { int i; if(list->length >= list->capacity) { cout<<"存儲空間，不能插入"<< x < return FALSE; } for(i = list->length; i > 0; i--) { if(list->bace[i-1] > x) list->bace[i] = list->bace[i - 1]; else break; } list->bace[i] = x; list->length++; return TRUE; } //按照位置插入，插入成功返回TRUE，插入失敗返回ERROR Status Insert_pos(SeqList *list,int pos,ElemType x) { if(pos < 0 || pos >= list->length) { cout<<"插入位置錯誤"< return FALSE; } for(int i = list->length; i > pos; i--) { list->bace[i] = list->bace[i - 1]; } list->bace[pos] = x; list->length++; return TRUE; } 刪除元素操作： //頭刪,刪除成功返回TRUE，刪除失敗返回ERROR Status Delise_Front(SeqList *list,ElemType *x) { if(0 == list->length) { cout<<"空間已無元素不能刪除了"< return FALSE; } *x = list->bace[0]; for(int i = 0; i < list->length ; i++) { list->bace[i] = list->bace[i + 1]; } list->length--; return TRUE; } //尾刪,刪除成功返回TRUE，刪除失敗返回ERROR Status Delite_back(SeqList *list, ElemType *x) { if(0 == list->length) { cout<<"空間已無元素不能刪除了"< return FALSE; } *x = list->bace[list->length - 1]; list->length--; return TRUE; } //按位置刪除，刪除成功返回TRUE，刪除失敗返回ERROR Status Delite_pos(SeqList *list,int pos,ElemType *x) { if(pos < 0 || pos >= list->length ) { cout<<"刪除位置出錯"< return FALSE; } *x = list->bace[pos]; for(int i = pos; i < list->length; i++) { list->bace[i] = list->bace[i + 1]; } list->length--; return TRUE; } //按值刪除，刪除成功返回TRUE，刪除失敗返回ERROR Status Delite_value(SeqList *list, ElemType x) { if(0 == list->length) { cout<<"空間已無元素不能刪除了"< return FALSE; } for(int i = 0; i < list->length; i++) { if( x == list->bace[i]) { list->bace[i] = list->bace[i + 1]; list->length--; } } return TRUE; } 取元素操作： //打印輸出順序表 Status Show_list(SeqList *list) { for(int i = 0; i < list->length; i++) { cout< } cout< return TRUE; } 排序、逆置等其他操作： //清空順序表 Status Clear(SeqList *list) { list->length = 0; return TRUE; } //排序排序操作，這里采用冒泡排序，讀者也可以采用其他排序方法。 Status Sort_List(SeqList *list) { for(int i = 0; i < list->length - 1; i++) { for(int j = 0; j < list->length - i - 1; j ++) { if(list->bace[j] > list->bace[j + 1]) { ElemType temp = list->bace[j]; list->bace[j] = list->bace[j + 1]; list->bace[j + 1] = temp; } } } return TRUE; } //釋放內(nèi)存空間 Status Destory(SeqList *list) { list->length = 0; list->capacity = 0; free(list->bace); list->bace = NULL; return TRUE; } 主函數(shù)測試程序： typedef enum { EXIT, INIT_LIST, INSERT_FRONT, INSERT_BACK, INSERT_VALUE, INSERT_POS, DELITE_FRONT, DELITE_BACK, DELITE_POS, DELITE_VALUE, CLEAR_LIST, SORT_LIST, RESERVE_LIST, SHOW_LIST, DESTORY_LIST, }ENUM; void show() { cout<<"***************************************"< cout<<"* [1] InitList [2] Insert_Front *"< cout<<"* [3] Insert_Back [4] Insert_Value *"< cout<<"* [5] Insrt_pos [6] Delite_Front *"< cout<<"* [7] Delite_Back [8] Delite_pos *"< cout<<"* [9] Delite_value [10] Clear_List *"< cout<<"* [11] Sort_List [12] Reserve_List *"< cout<<"* [13] Show_List [14] Destory_List *"< cout<<"* [0] Exit_System *"< cout<<"***************************************"< } void insert_fr(SeqList *list) { ElemType x; printf("請輸入要插入的元素\n"); scanf("%d",&x); int result1 = Insert_front(list, x); if(TRUE == result1) printf("insert frount ok\n"); else printf("insert frount error\n"); } void insert_ba(SeqList *list) { ElemType x; printf("請輸入要插入的元素\n"); scanf("%d",&x); int result1 = Insert_back(list,x); if(TRUE == result1) printf("insert back ok\n"); else printf(" insert back error\n"); } void insert_value(SeqList *list) { ElemType x; printf("請輸入要插入的元素\n"); scanf("%d",&x); int result1 = Insert_Value(list,x); if(TRUE == result1) printf("insert value ok\n"); else printf("insert value error\n"); } void insert_pos(SeqList *list) { int pos,x; printf("請輸入要插入的位置和值\n"); scanf("%d%d",&pos,&x); int result1 = Insert_pos(list,pos, x); if(TRUE == result1) printf("insert pos x ok\n"); else printf("insert pos x error\n"); } void delite_fr(SeqList *list) { int x; int result1 = Delise_Front(list, &x); if(TRUE == result1) { printf("delite ok\n"); } else printf("delite fr error\n"); } void delite_br(SeqList *list) { int x; int result1 = Delite_back(list, &x); if(TRUE == result1) { printf("delite ok\n"); } else printf("delite br error\n"); } void delite_pos(SeqList *list) { int pos, x; printf("請輸入要刪除的位置：\n"); scanf("%d",&pos); int result1 = Delite_pos(list,pos,&x); if(TRUE == result1) { printf("%d delite pos ok\n",x); } else printf("delite pos error\n"); } void delite_value(SeqList *list) { int x; printf("請輸入要刪除的值\n"); scanf("%d",&x); int result1 = Delite_value(list, x); if(TRUE == result1) { printf("%d delite pvalue ok\n",x); } else printf("delite value error\n"); } void clear_list(SeqList *list) { int result1 = Clear(list); if(TRUE == result1) { printf("clear ok\n"); } else printf("clear error\n"); } void sort_list(SeqList *list) { int result1 = Sort_List(list); if(TRUE == result1) { printf(" sort ok\n"); } else printf("sort error\n"); } void show_list(SeqList *list) { int result1 = Show_list(list); if(TRUE == result1) { printf(" show ok\n"); } else printf("show error\n"); } void destory(SeqList *list) { int result1 = Destory(list); if(TRUE == result1) { printf(" destor ok\n"); } else printf("detor error\n"); } void Reserve(SeqList *list) { int result1 = Reserve_List (list); if(TRUE == result1) { printf(" res ok\n"); } else printf("res error\n"); } void main() { int Select_Value,Cyc_Value = 1; SeqList list; int result1 = Init_list(&list); while(Cyc_Value) { show(); printf("請選擇\n"); scanf("%d",&Select_Value); switch(Select_Value) { case INIT_LIST: Init_list(&list); break; case INSERT_FRONT: insert_fr(&list); break; case INSERT_BACK: insert_ba(&list); break; case INSERT_VALUE: insert_value(&list); break; case INSERT_POS: insert_pos(&list); break; case DELITE_FRONT: delite_fr(&list); break; case DELITE_BACK: delite_br(&list); break; case DELITE_POS: delite_pos(&list); break; case DELITE_VALUE: delite_value(&list); break; case CLEAR_LIST: clear_list(&list); break; case SORT_LIST: sort_list(&list); break; case RESERVE_LIST: Reserve(&list); break; case SHOW_LIST: show_list(&list); break; case DESTORY_LIST: destory(&list); break; case EXIT: Cyc_Value = 0; break; default : printf("輸入選項錯誤,請重新選擇\n"); break; } } } 以上代碼都是筆者進行了測試，數(shù)據(jù)結(jié)構(gòu)部分主要是關(guān)注對于順序表的基本操作，主程序這里只是作為測試程序，沒有在進一步優(yōu)化，并且，順序表的插入刪除，這里是不考慮相同元素的，尤其在按值刪除時，只會刪除掉優(yōu)先遇到的值，并不會全部刪除相同的值。 順序表的優(yōu)缺點： 優(yōu)點：可以快速獲取到表中任意數(shù)據(jù)元素， 缺點：插入和刪除操作需要移動大量元素，當(dāng)線性表的長度變化較大時，很難確定存儲空間的大小，造成存儲空間“碎片”當(dāng)順序表比較長時，插入、刪除時比較浪費時間。 另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
網(wǎng)站標(biāo)題：數(shù)據(jù)結(jié)構(gòu)之線性表（C語言版）-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://weahome.cn/article/dsjiig.html
重慶分公司
重慶分公司
