線性順序表——數(shù)據(jù)結(jié)構(gòu)

1、/頭文件#include <stdio.h>#include <stdlib.h>/預(yù)定義常量和類型:函數(shù)結(jié)果狀態(tài)代碼#define OK 1#define ERROR 0#define TURE 1#define FALSE 0 #define INFEASIBLE -1#define OVERFLOW -2/-線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)-#define LIST_INIT_SIZE 100 /線性表存儲(chǔ)空間的初始分配量#define LINSTINCREMENT 10 /線性表存儲(chǔ)空間的分配增量/數(shù)據(jù)類型說(shuō)明,其值是函數(shù)結(jié)果狀態(tài)代碼typedef int Stat

2、us;typedef int ElemType;typedef struct ElemType *elem; /存儲(chǔ)空間基址int length; /當(dāng)前長(zhǎng)度int listsize; /當(dāng)前分配的存儲(chǔ)容量（以sizeof(ElemType)為單位SqList; /定義了一個(gè)線性表的數(shù)據(jù)類型/-函數(shù)基本操作-/ 函數(shù)InitList的主要功能是初始化一個(gè)線性表,構(gòu)造一個(gè)空的線性表L。Status InitList(SqList &L) L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) print

3、f("分配失敗n"); exit(OVERFLOW); /存儲(chǔ)分配失敗 L.length=0; /空表長(zhǎng)度為0L.listsize=LIST_INIT_SIZE; /初始存儲(chǔ)容量return OK; /InitList/函數(shù)Exist的主要功能是判斷線性表L是否存在。Status exist(SqList &L) if(L.elem!=NULL)&&(L.listsize>=LIST_INIT_SIZE) /檢測(cè)線性表是否存在 return OK; else return ERROR;/若線性表存在返回OK，否則返回ERROR/函數(shù)Destro

4、yList的主要功能是銷毀線性表L。Status DestroyList(SqList &L)if(exist(L)/判斷線性表是否存在 free(L.elem); /釋放空間L.elem =NULL; /將指針賦值為空L.length=-1; /當(dāng)前長(zhǎng)度賦值為-1，標(biāo)志線性表不存在L.listsize=0; /當(dāng)前最大容量賦值為0return OK;elsereturn ERROR;/成功釋放空間時(shí)返回OK，否則返回ERROR/函數(shù)ClearList的主要功能是將L重置為空表。Status ClearList(SqList &L)if(!(L.elem=NULL) /重置為空

5、表return OK;else return ERROR;/重置線性表，成功返回OK，失敗返回ERROR/函數(shù)ListEmpty的主要功能是判斷線性表是否為空表。Status ListEmpty(SqList L) if(!exist(L) return ERROR; else if(ClearList(L) return TURE; else return FALSE; return OK;/函數(shù)ListLength的主要功能是檢測(cè)線性表的數(shù)據(jù)元素個(gè)數(shù)。 Status ListLength(SqList &L)/返回?cái)?shù)據(jù)元素個(gè)數(shù)if(exist(L)/判斷線性表是否存在return

6、L.length ;/返回元素個(gè)數(shù)elsereturn -1;/檢驗(yàn)線性表元素個(gè)數(shù)，成功返回?cái)?shù)字，失敗返回-1./函數(shù)GetElem的主要功能是返回線性表中指定位置的數(shù)據(jù)元素。 Status GetElem(SqList &L, int i, ElemType &e)/ 線性表已存在，用e返回線性表 L中第i個(gè)元素 if ( exist(L) && i > 0 && i < L.length+1) /判定線性表存在和元素位置 i是否合法e = L.elemi - 1; /將指定位置元素賦給ereturn OK; elsereturn

7、ERROR;/成功返回 OK, 失敗返回ERROR/函數(shù)compare的主要功能是判斷線性表中有與輸入元素相同的數(shù)值，函數(shù)默認(rèn)程序compare(ElemType e1, ElemType e2) if(e1=e2)return OK; /相等，返回OKelsereturn ERROR;/不相等，返回ERROR /函數(shù)返回值是一個(gè)執(zhí)行成功與否的狀態(tài)標(biāo)志/函數(shù)LocateElem的主要功能是返回滿足函數(shù)compare()的數(shù)據(jù)元素位序。int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType,ElemType) int i; El

8、emType *p; i=1 ;/i的處值為第1個(gè)元素的位序 p=L.elem; /p的初值為第1個(gè)元素的存儲(chǔ)位置 while(i<=L.length&&!(*compare)(*p+,e)+i; if(i<=L.length) return i; else return ERROR; /在順序線性表L中查找第一個(gè)與e滿足compare()的元素的位序 /若找到，則返回其在L中的位序，否則返回ERROR/函數(shù)PriorElem的主要功能是返回指定元素的前驅(qū)。Status PriorElem(SqList L,ElemType cur_e,ElemType &

9、pre_e) int i=0; /初始化元素下標(biāo) while(i<L.length) /循環(huán)條件if(L.elemi=cur_e)/若L.elemi的元素值與cur_e相等if(i>0)/判斷i值是否合法 pre_e=L.elemi-1; return pre_e;/滿足條件，用pre_e返回元素cur_e前驅(qū)的值 else return -1; i+;/循環(huán)條件不滿足，繼續(xù)循環(huán)if(i>=L.length)return ERROR;/不滿足循環(huán)條件，無(wú)法繼續(xù)實(shí)行return OK;/操作成功，返回OK/返回給定元素的前驅(qū)，成功則返回OK,由pre_e帶回前驅(qū)值，失敗則返回E

10、RROR/函數(shù)NextElem的主要功能是返回元素元素的后繼。Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)int i=0;while(i<L.length)/循環(huán)條件if(L.elemi=cur_e)/若L.elemi的元素值與cur_e相等if(i!=L.length-1)/判斷i值是否合法 next_e=L.elemi+1; return next_e;/滿足條件，用next_e返回元素cur_e后繼的值 else return -1; i+;/循環(huán)條件不滿足，繼續(xù)循環(huán)if(i>=L.length)r

11、eturn ERROR;/不滿足循環(huán)條件，無(wú)法繼續(xù)實(shí)行return OK;/操作成功，返回1 /若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回他的后繼，若失敗，則next_e無(wú)定義/函數(shù)visit的主要功能是判斷是依次輸出線性表的元素的值Status visit(ElemType e) printf("%d ",e); return OK;/輸出完成，返回OK/函數(shù)ListInsert的主要功能是向線性表中插入新的元素。Status ListInsert(SqList &L, int i, ElemType e)/參數(shù)L表示的是一個(gè)已經(jīng)初始化的線性

12、表變量/e表示待插入的數(shù)據(jù)/函數(shù)返回值是一個(gè)執(zhí)行成功與否的狀態(tài)標(biāo)志 /i的合法值為1<=i<=ListLength_Sq(L)+1ElemType *newbase,*q,*p;if(i<1|i>L.length+1) return ERROR; /i值不合法if(L.length>=L.listsize) /當(dāng)前存儲(chǔ)空間已滿，增加分配newbase=(ElemType *)realloc(L.elem,(L.listsize +LINSTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存儲(chǔ)分配失敗L

13、.elem=newbase;/新基址L.listsize+=LINSTINCREMENT;/增加存儲(chǔ)容量q=&(L.elem i-1); /q為插入位置 for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p; /插入位置及之后的元素后移*q=e; /插入e+L.length ;/表長(zhǎng)增加1return OK;/插入成功，返回OK/ListInsert/函數(shù)ListDelete的主要功能是刪除線性表中的元素。Status ListDelete(SqList &L,int i,ElemType &e)/線性表L已存在且非空，

14、在順序線性表L中刪除第i個(gè)元素，并用e返回其值，L的長(zhǎng)度-1 /i的合法值為1<=i<=LIstLength_Sq(L) ElemType *q,*p;if(i<1)|(i>L.length)return ERROR; /i值不合法p=&(L.elemi-1); /p為被刪除元素的位置 e=*p; /被刪除元素的值賦給e q=L.elem+L.length-1; /表尾元素的位置 for(+p;p<=q;+p) *(p-1)=*p; /被刪除之后的元素往前移 -L.length; /表長(zhǎng)減一 return OK;/ListDelete/函數(shù)ListTrav

15、erse的主要功能是對(duì)每個(gè)元素調(diào)用visit()函數(shù)測(cè)試。Status ListTraverse(SqList L,Status(*visit)(ElemType) ElemType *p=L.elem; /p指向第1個(gè)元素 int i; for(i=1;i<=L.length;i+) /從表L的第1個(gè)元素到最后1個(gè)元素 visit(*p+); /對(duì)每個(gè)數(shù)據(jù)元素調(diào)用visit() return OK;/操作成功 /順序線性表L已存在,依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit(),一旦visit()失敗，則操作失敗int main()SqList L;ElemType e,cur_e,pr

16、e_e,next_e;int i,j,n;InitList(L);printf("輸入元素的個(gè)數(shù)為:");scanf("%d",&n);while(n<=0)/n的合法值為n>0printf("輸入錯(cuò)誤,請(qǐng)重新輸入n");printf("輸入元素的個(gè)數(shù)為:");scanf("%d",&n);printf("請(qǐng)輸入%d個(gè)元素:",n);/輸入元素for(i=1;i<=n;i+)scanf("%d",&e);ListI

17、nsert(L,i,e);/調(diào)用函數(shù)ListInsert輸入/顯示線性表的元素個(gè)數(shù),依次顯示元素printf("線性表共有%d個(gè)元素，線性表中的元素依次為:",ListLength(L); for(i=0;i<n;i+) printf("%d ",L.elemi); printf("n");/函數(shù)GetElem的應(yīng)用，返回線性表L中第i個(gè)元素的值printf("請(qǐng)輸入要返回?cái)?shù)據(jù)元素的位序:");scanf("%d",&i);while(i<1|i>L.length)/i

18、的合法值為0<i<L.length+1printf("輸入錯(cuò)誤,請(qǐng)重新輸入n");printf("請(qǐng)輸入元素的序數(shù)為:");scanf("%d",&i);GetElem(L,i,e);printf("第%d個(gè)的元素的值為%dn",i,e);printf("n");/函數(shù)LocateElem和函數(shù)compare()的應(yīng)用，查找第一個(gè)與e滿足函數(shù)compare()的元素的位序 printf("請(qǐng)輸入數(shù)據(jù)元素e:");scanf("%d",&

19、amp;e);printf("第一個(gè)與e滿足關(guān)系的元素的位序?yàn)?%dn",LocateElem(L,e,(*compare); printf("n");/函數(shù)priorElem的應(yīng)用，輸出某數(shù)據(jù)元素的前驅(qū)printf("請(qǐng)輸入數(shù)據(jù)元素cur_e:");scanf("%d",&cur_e);if(PriorElem(L,cur_e,pre_e)!=-1) printf("%d的前驅(qū)為:%dn",cur_e,PriorElem(L,cur_e,pre_e);else printf("

20、;線性表L中沒(méi)有數(shù)據(jù)元素%d的前驅(qū)n",cur_e);printf("n");/函數(shù)NextElem的應(yīng)用,輸出某元素的后繼printf("請(qǐng)輸入數(shù)據(jù)元素cur_e:");scanf("%d",&cur_e);if(NextElem(L,cur_e,next_e)!=-1) printf("%d的后繼為:%dn",cur_e,NextElem(L,cur_e,next_e);else printf("線性表L中沒(méi)有數(shù)據(jù)元素%d的后繼n",cur_e);printf("

21、n");/函數(shù)ListInsert的應(yīng)用，插入元素printf("請(qǐng)輸入要插入的數(shù)據(jù)元素的位置i:");scanf("%d",&i); printf("請(qǐng)輸入要插入的數(shù)據(jù)元素e:");scanf("%d",&e); if(i>=1&&i<=L.length) ListInsert(L,i,e); printf("插入新的數(shù)據(jù)元素后的線性表L中的數(shù)據(jù)元素為:"); for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n");printf("n");/函數(shù)ListDelete的應(yīng)用，刪除元素 printf("請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)元素的位置j:"); scanf("%d",&j); ListDelete(L,j,e); printf("刪除數(shù)據(jù)元素后的線性表L中的數(shù)據(jù)元素為:"); for(i=0;i<L.le