順序表的基本操作

1、精選優(yōu)質(zhì)文檔-傾情為你奉上順序表的基本操作/*sqList.h 文件*/#define LIST_INIT_SIZE 50 /*初始分配的順序表長度*/#define INCREM 10 /*溢出時，順序表長度的增量*/#define OVERFLOW 1#define OK 0#define ERROR -1typedef int ElemType; /*定義表元素的類型*/typedef struct SqListElemType *elem; /*存儲空間的基地址*/int length; /*順序表的當前長度*/int listsize; /*當前分配的存儲空間*/SqList;/*s

2、qListOp.h 文件*/#include Sqlist.hint InitList_sq(SqList &L); /順序表創(chuàng)建函數(shù)定義void FreeList_sq(SqList &L); /順序表銷毀函數(shù)定義int ListInsert_sq(SqList &L, int i, ElemType e); /在順序表的位置i插入元素evoid PrintList_sq(SqList &L); /遍歷并輸出順序表所有元素int ListDelete_sq(SqList &L, int i,ElemType &e); /刪除順序表第i個元素的bool ListEmpty(SqList &L)

3、; /判斷順序表是否為空int LocateElem_sq(SqList L,ElemType e); /在順序表里查找出第1個與e相等的數(shù)據(jù)元素位置/已知線性表La和Lb的元素按值非遞減排列/歸并后的La和Lb得到新的順序線性表Lc，Lc的元素也是按值非遞減排列void MergeList_sq(SqList La,SqList Lb, SqList &Lc);/*sqListOp.cpp文件*/#include #include #include #include sqlistOp.h/創(chuàng)建順序表int InitList_sq(SqList &L) L.elem = (ElemType*)

4、malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) exit(OVERFLOW); /*初始化失敗，返回0*/L.length = 0; /*置空表長度為0*/L.listsize = LIST_INIT_SIZE; /*置初始空間容量*/return OK; /*初始化成功，返回1*/*InitList*/銷毀順序表void FreeList_sq(SqList &L)if (L.elem)free(L.elem);printf(完成鏈表內(nèi)存銷毀n);/在順序表的第i個位置之前插入新元素int ListInsert_sq(SqList &L

5、, int i, ElemType e)int k;if (iL.length + 1) return ERROR; /*插入位置不合法*/if (L.length = L.listsize) /*存儲空間滿，重新分配空間*/L.elem = (ElemType*)realloc(L.elem, (LIST_INIT_SIZE + INCREM)*sizeof(ElemType);if (!L.elem) return OVERFLOW; /*存儲分配失敗*/L.listsize += INCREM; /*修改存儲空間大小*/for (k = L.length - 1; k = i - 1;

6、k-) /*插入位置之后元素后移*/L.elemk + 1 = L.elemk;L.elemi - 1 = e; /*插入元素*/L.length+; /*順序表長度加1*/return OK;/*ListInsert*/遍歷并輸出順序表所有元素void PrintList_sq(SqList &L)if (!L.elem)return;int i = 0;for (i = 0; i L.length; i+)printf(第%d元素= %dn, i, L.elemi);/刪除順序表第i個位置的元素int ListDelete_sq(SqList &L, int i,ElemType &e)i

7、nt k;if (iL.length) return ERROR; /*刪除位置不合法*/e = L.elemi-1;for (k = i - 1; kL.length - 1; k+) /*元素前移*/L.elemk = L.elemk + 1;L.length-; /*順序表長度減1*/return OK;/在順序表里查找出第1個與e相等的數(shù)據(jù)元素位置int LocateElem_sq(SqList L,ElemType e)int i = 0;while(i=L.length)if(L.elemi = e) break;elsei+;if(i=L.length) return i;ret

8、urn -1;/已知線性表La和Lb的元素按值非遞減排列/歸并后的La和Lb得到新的順序線性表Lc，Lc的元素也是按值非遞減排列void MergeList_sq(SqList La,SqList Lb, SqList &Lc)ElemType *pa = La.elem;ElemType *pb = Lb.elem;Lc.listsize = Lc.length = La.length + Lb.length;if(!Lc.elem) exit(OVERFLOW); /存儲分配失敗int i = 0,j = 0; /書上合并的算法采用指針方式，這里采用簡單點的方法int k =0; /i指向

9、La的當前位置，j指向Lb當前位置，k指向Lc當前位置while(iLa.length & jLb.length) /歸并if(La.elemiLb.elemj) Lc.elemk = La.elemi;i+;elseLc.elemk = Lb.elemj;j+;k+;while(iLa.length) Lc.elemk+ = La.elemi+;while(j 0)return 1;elsereturn 0;/* main.cpp 文件*/#include #include #include sqlistOp.hvoid main()SqList L;printf(準備創(chuàng)建順序表n);if

10、(OK != InitList_sq(L)printf(順序表創(chuàng)建出錯n);if(ListEmpty(L)printf(表不為空n);elseprintf(表為空n);int i = 0;for (i = 1; i = 20; i+)ListInsert_sq(L, i, 2 * i);printf(準備遍歷并輸出順序表n);PrintList_sq(L);getchar();printf(在第10個位置插入值為99的元素后再遍歷輸出順序表n);ListInsert_sq(L, 10, 99);PrintList_sq(L);getchar();printf(刪除第10個元素后再遍歷輸出順序表

11、n);ElemType e;ListDelete_sq(L,10,e);PrintList_sq(L);printf(刪除的數(shù)據(jù)元素值 = %d n,e);getchar();printf(查找出一個數(shù)據(jù)元素的在順序表中的位置n);i = LocateElem_sq(L,20);if(-1 = i)printf(順序表不包含這個數(shù)據(jù)元素n);elseprintf(元素在順序表的位置 = %dn,i);printf(創(chuàng)建另一個順序表n);SqList Lb;if (OK != InitList_sq(Lb)printf(順序表創(chuàng)建出錯n);for (i = 1; i = 10; i+)ListI

12、nsert_sq(Lb, i, 2 * i-1);printf(準備遍歷并輸出順序表n);PrintList_sq(Lb);SqList Lc;if (OK != InitList_sq(Lc)printf(順序表創(chuàng)建出錯n);printf(將兩個順序表合并打印合并后的順序表n);MergeList_sq(L, Lb, Lc);PrintList_sq(Lc);printf(準備銷毀順序表n);FreeList_sq(L);FreeList_sq(Lb);FreeList_sq(Lc);getchar();/ 單鏈表的操作/*linkList.h 文件*/#define INIT_SIZE 5

13、0 /*初始分配的順序表長度*/#define INCREM 10 /*溢出時，順序表長度的增量*/enum Status OK,ERROR;typedef int ElemType; /*定義表元素的類型*/typedef struct LNodeElemType data; /*結點的數(shù)據(jù)域*/struct LNode *next; /*結點的指針域*/LNode, *LinkList;/*linkListOp.h 文件*/#include linkList.hLinkList InitList_L(); /創(chuàng)建單鏈表頭結點void CreateList_L(LinkList &L,int

14、 n); /創(chuàng)建單鏈表頭結點和n個元素結點Status ListInsert_L(LinkList &L, int i, ElemType e); /在單鏈表的第i個位置之前插入新元素xvoid PrintList_L(LinkList L); /遍歷并輸出單鏈表所有元素Status ListDelete_L(LinkList &L, int i, ElemType &e);/刪除單鏈表第i個位置的元素Status GetElem_L(LinkList L,int i,ElemType &e);/獲取單鏈表第i個位置的元素int LocateElem_L(LinkList L,ElemType

15、 e); /查找出第1個與e相等的數(shù)據(jù)元素位置void ListConvert_L(LinkList &L); /單鏈表翻轉void FreeList_L(LinkList L); /銷毀單鏈表/*linkListOp.cpp文件 */#include #include #include linklistOp.h/初始化線性單表，即創(chuàng)建一個頭結點LinkList InitList_L() LinkList H = (LinkList)malloc(sizeof(LNode); /*申請一個頭結點*/if (!H) return NULL; /*申請失敗*/H-next = NULL; /*頭結

16、點的指針域置空*/return H;/創(chuàng)建n個結點的單鏈表，包括所有鏈表節(jié)點void CreateList_L(LinkList &L,int n)/逆位序輸入n個元素的值，建立帶表頭結點的單鏈表LL = (LinkList)malloc(sizeof(LNode);L-next = NULL; /建立一個帶頭結點的單鏈表for(int i= n; i 0; i-)LinkList p = (LinkList)malloc(sizeof(LNode); /生成新結點p-data = 2*i; /輸入元素值p-next = L-next; /插入到表頭L-next = p;/在順序表里查找出第1

17、個與e相等的數(shù)據(jù)元素位置int LocateElem_L(LinkList L,ElemType e)int i = 1;LinkList p = L-next;while(p)if(p-data = e) break;elsep = p-next;i+;if(p) return i;return 0;/銷毀單鏈表表void FreeList_L(LinkList L)LinkList p = L;while (p)L = L-next;free(p);p = L;/在單鏈表的第i個位置之前插入新元素Status ListInsert_L(LinkList &L, int i, ElemTyp

18、e e)LinkList p = L; int j = 0;while(p & jnext;+j;if(!p | ji) return ERROR;LinkList s = (LinkList)malloc(sizeof(LNode);s-data = e;s-next = p-next;p-next = s;return OK;/遍歷并輸出單鏈表所有元素void PrintList_L(LinkList L)int i = 0;LinkList p = L-next;while (p)printf(第%d元素= %dn, i+, p-data);p = p-next;/獲取單鏈表第i個位置的

19、元素Status GetElem_L(LinkList L,int i,ElemType &e)/L為帶頭結點的單鏈表的頭指針/當?shù)趇個元素存在，其值賦給e并返回OK，否則飯否ERRORLinkList p = L-next;int j = 1;while(p & jnext;+j;if(!p) return ERROR;/第i個元素不存在e = p-data;return OK;/刪除單鏈表第i個位置的元素,并由e返回其值Status ListDelete_L(LinkList &L, int i, ElemType &e)LinkList p = L; int j = 0;while(p-

20、next & jnext;+j;if(!p-next | ji-1) return ERROR; /刪除位置不合理LinkList q = p-next;p-next = q-next;e = q-data;free(q);return OK;/單鏈表翻轉，不增加額外的存儲空間void ListConvert_L(LinkList &L)LinkList p,q;p=L-next;L-next=NULL;while(p)q=p;p=p-next;q-next=L-next;L-next=q;/*main.cpp文件 */#include #include #include linklistOp

21、.hvoid main()printf(準備創(chuàng)建單鏈表n);LinkList L;CreateList_L(L,20);printf(準備遍歷并輸出單鏈表n);PrintList_L(L);getchar();printf(在第10個位置插入值為99的元素后再遍歷輸出單鏈表n);ListInsert_L(L, 10, 99);PrintList_L(L);getchar();printf(刪除第10個元素后再遍歷輸出單鏈表n);ElemType e;ListDelete_L(L,10,e);PrintList_L(L);printf(刪除的元素值 = %dn,e);getchar();prin

22、tf(獲取第10個元素n);GetElem_L(L,10,e);printf(獲取到的元素值e = %dn,e);getchar();printf(查找數(shù)據(jù)元素14在單鏈表的位置n);int idx = LocateElem_L(L,14);printf(14在單鏈表的位置 = %dn,idx);getchar();printf(單鏈表翻轉操作n);ListConvert_L(L);PrintList_L(L);getchar();printf(單鏈表翻轉操作n);ListConvert_L(L);PrintList_L(L);getchar();printf(準備銷毀單鏈表n);FreeLi

23、st_L(L);getchar();/*sqStack.h文件 */#define INIT_SIZE 100#define INCREMENT 10/typedef int ElemType;typedef char ElemType;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h文件 */#include sqStack.hStatus InitStack(SqStack &S) ;Status GetTo

24、p(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S); /*sqStackOp.cpp文件 */#include #include #include sqStackOp.hStatus InitStack(SqStack &S) /構造一個空的棧 S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(! S.base) exit(OVERFLOW)

25、; /存儲分配失敗 S.top=S.base; S.stacksize=INIT_SIZE; return OK; /InitStackStatus GetTop(SqStack S,ElemType &e)/若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR if(S.top=S.base) return ERROR; e=*(S.top-1); return OK; /GetTop Status Push(SqStack &S,ElemType e)/插入元素e為新的棧頂元素 if(S.top-S.base=S.stacksize) /棧滿，追加存儲空間 S.base=(El

26、emType *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType); if(!S.base)exit(OVERFLOW); /存儲分配失敗 S.top=S.base+S.stacksize; S.stacksize+=INCREMENT; *S.top+=e; return OK; /PushStatus Pop(SqStack &S,ElemType &e)/若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if(S.top=S.base) return ERROR; e=*(-S.top); retur

27、n OK; /Push/判斷棧是否為空bool StackEmpty(SqStack &S)if(S.top = S.base) return true;elsereturn false;/*main.cpp文件 */#include #include #include sqStackOp.hvoid main()printf(Hellow stack n);SqStack S; /定義順序棧Sif(OK != InitStack(S) printf(順序棧初始化出錯，退出.n);exit(-1);Push(S, 1);Push(S,2);Push(S,3);int e;Pop(S, e);p

28、rintf(出棧元素 = %d n,e);Push(S,4);Push(S,5);while(!StackEmpty(S)Pop(S, e);printf(出棧元素 = %d n,e);/*SqStack S; char x,y; InitStack(S); x=c;y=k; Push(S,x); Push(S,a); Push(S,y); Pop(S,x); Push(S,t); Push(S,x); Pop(S,x); Push(S,s); while(!StackEmpty(S) Pop(S,y);printf(%c ,y); ; printf(%c ,x);*/getchar();實驗

29、內(nèi)容（2）參考程序/*sqStack.h文件 */#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h文件 */#include sqStack.hStatus InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status

30、Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp文件 */#include #include #include sqStackOp.hStatus InitStack(SqStack &S) /構造一個空的棧 S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(! S.base) exit(OVERFLOW); /存儲分配失敗 S.top=S.base; S.stacksi

31、ze=INIT_SIZE; return OK; /InitStackStatus GetTop(SqStack S,ElemType &e)/若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR if(S.top=S.base) return ERROR; e=*(S.top-1); return OK; /GetTopStatus Push(SqStack &S,ElemType e)/插入元素e為新的棧頂元素 if(S.top-S.base=S.stacksize) /棧滿，追加存儲空間 S.base=(ElemType *)realloc(S.base,(S.stacksi

32、ze+INCREMENT)*sizeof(ElemType); if(!S.base)exit(OVERFLOW); /存儲分配失敗 S.top=S.base+S.stacksize; S.stacksize+=INCREMENT; *S.top+=e; return OK; /PushStatus Pop(SqStack &S,ElemType &e)/若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if(S.top=S.base) return ERROR; e=*(-S.top); return OK; /Push/判斷棧是否為空bool StackEmpty

33、(SqStack &S)if(S.top = S.base) return true;elsereturn false;/*main.cpp文件 */#include #include #include sqStackOp.hvoid main()SqStack s;int x;InitStack(s);scanf(%d,&x); /%d-十進制輸入；%O-八進制輸入； %x-十六進制輸入/修改這里輸入進制和下面整除和余數(shù)計算，就可以獲得其他進制的轉換while(x!=0)Push(s,x%8); x=x/8; while(!StackEmpty(s) Pop(s,x); printf(%d

34、,x); printf(n);getchar();實驗內(nèi)容（3）參考程序/*sqQueue.h 文件*/#define MAXQSIZE 100typedef int QElemType;typedef struct SqQueue QElemType *base;int front;int rear;SqQueue;enum StatusOK,ERROR,OVERFLOW;/*sqQueueOp.h 文件*/#include sqQueue.hStatus InitQueue (SqQueue &Q) ;Status EnQueue (SqQueue &Q, QElemType e);Sta

35、tus DeQueue (SqQueue &Q, QElemType &e) ;bool QueueEmpty(SqQueue &Q);int QueueLength(SqQueue Q);/*sqQueueOp.cpp 文件*/#include #include #include sqQueueOp.h Status InitQueue (SqQueue &Q) / 構造一個空隊列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存儲分配失敗 Q.fro

36、nt = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; Status DeQueue (SqQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front

37、 = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;/判斷隊列是否為空bool QueueEmpty(SqQueue &Q)if(Q.front= Q.rear) return true;elsereturn false;/計算循環(huán)隊列長度int QueueLength(SqQueue Q)return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;/*main.cpp 文件*/#include #include #include sq

38、QueueOp.hvoid main()printf(Hello Queue n);SqQueue Q; /定義順序隊列QQElemType e;if(OK != InitQueue(Q) printf(順序隊列初始化出錯，退出.n);exit(-1);EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);printf(當前隊列長度 = %d n,QueueLength(Q);DeQueue(Q,e);printf(隊首元素%d出隊，當前隊列長度=%dn,e,QueueLength(Q);EnQueue(Q,9);EnQueue(Q,11);w

39、hile(!QueueEmpty(Q)DeQueue(Q,e);printf(隊首元素%d出隊，當前隊列長度=%dn,e,QueueLength(Q);getchar();實驗內(nèi)容（4）參考程序/*linkQueue.h 文件*/typedef int QElemType; typedef struct QNode / 結點類型 QElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct / 鏈隊列類型 QueuePtr front; / 隊頭指針 QueuePtr rear; / 隊尾指針 LinkQueue;en

40、um StatusOK,ERROR,OVERFLOW;/*linkQueueOp.h 文件*/#include linkQueue.hStatus InitQueue (LinkQueue &Q) ;Status EnQueue (LinkQueue &Q, QElemType e);Status DeQueue (LinkQueue &Q, QElemType &e) ;bool QueueEmpty(LinkQueue &Q);/*linkQueueOp.cpp 文件*/#include #include #include linkQueueOp.hStatus InitQueue (Li

41、nkQueue &Q) / 構造一個空隊列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存儲分配失敗 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 QueuePtr p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存儲分配失敗 p-data = e; p-

42、next = NULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear) return ERROR; QueuePtr p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;/判斷隊列是

43、否為空bool QueueEmpty(LinkQueue &Q)if(Q.front = Q.rear) return true;elsereturn false;/*main.cpp 文件*/#include #include #include linkQueueOp.hvoid main()printf(Hello LinkQueue n);LinkQueue Q; /定義順序隊列QQElemType e;if(OK != InitQueue(Q) printf(順序隊列初始化出錯，退出.n);exit(-1);EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);

44、EnQueue(Q,7);DeQueue(Q,e);printf(隊首元素%d出隊，n,e);EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)DeQueue(Q,e);printf(隊首元素%d出隊，n,e);getchar();typedef char TElemType;typedef struct BiTNode / 結點結構 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;enum Status ERROR = 0,OK = 1,OVERF

45、LOW = 2;/* biTreeOp.h 文件 */#include biTree.h/按先序次序輸入二叉樹中結點中的值，以鏈式存儲Status CreateBiTree(BiTree & T);/對鏈式存儲的二叉樹先序遍歷Status PreOrderTraverse(BiTree T); /對鏈式存儲的二叉樹中序遍歷Status InOrderTraverse(BiTree T); /對鏈式存儲的二叉樹后序遍歷Status PostOrderTraverse(BiTree T); /對鏈式存儲的二叉樹層序遍歷Status LevelOrderTraverse(BiTree T); /對鏈式存儲的二叉樹先序遍歷Status FreeBiTree(BiTree T);/* biTreeOp.cpp 文件 */#include #include #include biTreeOp.h/#include sqQ