順序表的基本操作(2)

1、.順序表的基本操作/*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;/*sqListOp.h文件

2、*/#include "Sqlist.h"int InitList_sq(SqList &L);/ 順序表創(chuàng)建函數定義void FreeList_sq(SqList &L);/ 順序表銷毀函數定義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 個元

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

4、>#include <stdlib.h>#include "sqlistOp.h"/ 創(chuàng)建順序表int InitList_sq(SqList &L) L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);/* 初始化失敗，返回 0*/L.length = 0;/* 置空表長度為 0*/L.listsize = LIST_INIT_SIZE;/* 置初始空間容量 */return OK;/* 初始化成功，返回 1*/./*InitL

5、ist*/ 銷毀順序表void FreeList_sq(SqList &L)if (L.elem)free(L.elem);printf(" 完成鏈表內存銷毀n");/ 在順序表的第 i 個位置之前插入新元素int ListInsert_sq(SqList &L, int i, ElemType e)int k;if (i<1 | i>L.length + 1) return ERROR; /* 插入位置不合法*/if (L.length >= L.listsize)/* 存儲空間滿，重新分配空間*/L.elem = (ElemType*)

6、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; k-)/* 插入位置之后元素后移*/L.elemk + 1 = L.elemk;L.elemi - 1 = e;/* 插入元素 */L.length+;/* 順序表長度加1*/return OK;/*ListInsert*/ 遍歷并輸出順序表所有元素 vo

7、id 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)int k;if (i<1 | i>L.length) return ERROR; /* 刪除位置不合法*/e = L.elemi-1;for (k = i - 1;

8、 k<L.length - 1; k+)/* 元素前移 */L.elemk = L.elemk + 1;L.length-;/* 順序表長度減1*/return OK;/ 在順序表里查找出第 1 個與 e 相等的數據元素位置 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;return -1;/ 已知線性表 La 和 Lb 的元素按值非遞減排列/ 歸并后的 La 和 Lb 得到新的順序線

9、性表 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 指向 La 的當前位置， j 指向 Lb 當前位置， k 指向 Lc 當前

10、位置while(i<La.length && j<Lb.length)/ 歸并if(La.elemi<Lb.elemj)Lc.elemk = La.elemi;i+;elseLc.elemk = Lb.elemj;j+;k+;while(i<La.length) Lc.elemk+ = La.elemi+;while(j<La.length) Lc.elemk+ = Lb.elemj+;/MergeList_sqbool ListEmpty(SqList &L) / 判斷順序表是否為空if(L.length > 0)return 1;

11、elsereturn 0;/* main.cpp文件 */#include <stdio.h>#include <malloc.h>#include "sqlistOp.h"void main().SqList L;printf(" 準備創(chuàng)建順序表n");if (OK != InitList_sq(L)printf(" 順序表創(chuàng)建出錯n");if(ListEmpty(L)printf(" 表不為空 n");elseprintf(" 表為空 n");int i = 0;fo

12、r (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 個元素后再遍歷輸出順序表n");ElemType e;ListDelete_sq(L,10,e);PrintList_sq

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

14、for (i = 1; i <= 10; i+)ListInsert_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);

15、FreeList_sq(Lb);FreeList_sq(Lc);getchar();/單鏈表的操作/*linkList.h文件 */#define INIT_SIZE 50/* 初始分配的順序表長度*/#define INCREM 10/* 溢出時，順序表長度的增量*/enum Status OK,ERROR;typedef int ElemType; /* 定義表元素的類型*/typedefstructLNodeElemTypedata;/* 結點的數據域*/structLNode*next;/* 結點的指針域 */LNode, *LinkList;/*linkListOp.h文件 */#i

16、nclude "linkList.h"LinkList InitList_L();/ 創(chuàng)建單鏈表頭結點void CreateList_L(LinkList &L,int 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)

17、;/ 刪除單鏈表第i 個位置的元素.Status GetElem_L(LinkList L,int i,ElemType &e);/ 獲取單鏈表第i 個位置的元素int LocateElem_L(LinkList L,ElemType e); / 查找出第1 個與 e 相等的數據元素位置void ListConvert_L(LinkList &L); / 單鏈表翻轉void FreeList_L(LinkList L);/ 銷毀單鏈表/*linkListOp.cpp文件*/#include <malloc.h>#include <stdio.h>#inc

18、lude "linklistOp.h"/ 初始化線性單表，即創(chuàng)建一個頭結點LinkList InitList_L() LinkList H = (LinkList)malloc(sizeof(LNode);/* 申請一個頭結點*/if (!H)return NULL;/* 申請失敗 */H->next = NULL;/* 頭結點的指針域置空*/return H;/ 創(chuàng)建 n 個結點的單鏈表，包括所有鏈表節(jié)點void CreateList_L(LinkList &L,int n)/ 逆位序輸入 n 個元素的值，建立帶表頭結點的單鏈表 L L = (LinkLis

19、t)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 個與 e 相等的數據元素位置 int LocateElem_L(LinkList L,ElemType e)int i = 1;LinkList p = L-&g

20、t;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, ElemType e)LinkList p = L;int j = 0;while(p && j&l

21、t;i -1)/ 尋找第 i-1 個結點p = p->next; +j;if(!p | j>i) 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+

22、, p ->data); p = p->next;/ 獲取單鏈表第 i 個位置的元素Status GetElem_L(LinkList L,int i,ElemType &e)/L 為帶頭結點的單鏈表的頭指針/ 當第 i 個元素存在，其值賦給 e 并返回 OK，否則飯否 ERROR LinkList p = L->next;int j = 1; while(p && j<i)p = p->next; +j;.if(!p) return ERROR;/ 第 i 個元素不存在e = p->data;return OK;/ 刪除單鏈表第 i

23、 個位置的元素 ,并由 e 返回其值Status ListDelete_L(LinkList &L, int i, ElemType &e) LinkList p = L;int j = 0;while(p ->next && j<i -1)/ 尋找第 i 個結點，并令p 指向其前驅p = p->next; +j;if(!p ->next | j>i -1) return ERROR;/ 刪除位置不合理LinkList q = p->next;p->next = q->next;e = q->data;fre

24、e(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 <stdio.h>#include <malloc.h>#include "linklistOp.h"void main()printf(" 準備創(chuàng)建單鏈表n

25、");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("

26、刪除的元素值= %dn",e);getchar();printf(" 獲取第 10 個元素 n");GetElem_L(L,10,e);printf(" 獲取到的元素值e = %dn",e);getchar();printf(" 查找數據元素14 在單鏈表的位置n");int idx = LocateElem_L(L,14);printf("14 在單鏈表的位置= %dn",idx);getchar();printf(" 單鏈表翻轉操作n");ListConvert_L(L);Prin

27、tList_L(L);getchar();printf(" 單鏈表翻轉操作n");ListConvert_L(L);PrintList_L(L);getchar();printf(" 準備銷毀單鏈表n");FreeList_L(L);getchar();./*sqStack.h 文件*/#define INIT_SIZE 100#define INCREMENT10/typedef int ElemType;typedef char ElemType;typedef struct SqStack ElemType *base;ElemType *top;

28、int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h 文件*/#include "sqStack.h"StatusInitStack(SqStack&S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cp

29、p 文件*/#include <malloc.h>#include <stdlib.h>#include "sqStackOp.h"StatusInitStack(SqStack&S)/ 構造一個空的棧S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);if(! S.base)exit(OVERFLOW); /存儲分配失敗S.top=S.base;S.stacksize=INIT_SIZE;returnOK; /InitStack.Status GetTop(SqStack S,ElemTy

30、pe &e)/ 若棧不空，則用e 返回 S 的棧頂元素，并返回OK；否則返回ERRORif(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.stacksize+INCREMENT)*sizeof(ElemType);if(!S.base)exit(OVE

31、RFLOW); /存儲分配失敗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(SqStack &S)if(S.top = S.base)return

32、true;elsereturn false;/*main.cpp文件*/#include <stdio.h>.#include <stdlib.h>#include "sqStackOp.h"void 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);prin

33、tf(" 出棧元素= %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(!StackEm

34、pty(S) Pop(S,y);printf("%c ",y); ;printf("%c ",x);*/getchar();實驗內容（ 2）參考程序./*sqStack.h 文件*/#define INIT_SIZE 100#define INCREMENT10typedef int ElemType;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h 文件*/#includ

35、e "sqStack.h"StatusInitStack(SqStack&S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp 文件*/#include <malloc.h>#include <stdlib.h>#include "sqSta

36、ckOp.h"StatusInitStack(SqStack&S)/ 構造一個空的棧S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);if(! S.base)exit(OVERFLOW); /存儲分配失敗S.top=S.base;S.stacksize=INIT_SIZE;returnOK; /InitStack.Status GetTop(SqStack S,ElemType &e)/ 若棧不空，則用e 返回 S 的棧頂元素，并返回OK；否則返回ERRORif(S.top=S.base) return ERROR

37、;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.stacksize+INCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW); /存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=INCREMENT;*S.top+=e;ret

38、urn 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(SqStack &S)if(S.top = S.base)return true;elsereturn false;/*main.cpp文件*/#include <stdio.h>#include <st

39、dlib.h>#include "sqStackOp.h".void main()SqStack s;int x;InitStack(s);scanf("%d",&x);/%d -十進制輸入； %O-八進制輸入；%x-十六進制輸入/ 修改這里輸入進制和下面整除和余數計算，就可以獲得其他進制的轉換while(x!=0)Push(s,x%8);x=x/8;while(!StackEmpty(s)Pop(s,x);printf("%d ",x);printf("n");getchar();實驗內容（ 3）參

40、考程序/*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.h"Status InitQueue (SqQueue &Q) ;Status EnQueue (SqQueue &Q, QElemType e);Status DeQueue (

41、SqQueue &Q, QElemType &e) ;bool QueueEmpty(SqQueue &Q);.int QueueLength(SqQueue Q);/*sqQueueOp.cpp文件 */#include <malloc.h>#include <stdlib.h>#include "sqQueueOp.h"Status InitQueue (SqQueue &Q) / 構造一個空隊列 Q Q.base = (QElemType *) malloc(MAXQSIZE *sizeof (QElemType

42、); if (!Q.base) exit (OVERFLOW);/存儲分配失敗Q.front = 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) /若隊

43、列不空，則刪除Q 的隊頭元素，/用 e 返回其值，并返回OK;否則返回ERRORif (Q.front = 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) %

44、MAXQSIZE;/*main.cpp文件 */#include <stdio.h>#include <stdlib.h>#include "sqQueueOp.h"void 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)

45、;printf(" 當前隊列長度= %d n",QueueLength(Q);DeQueue(Q,e);printf(" 隊首元素 %d 出隊，當前隊列長度=%dn",e,QueueLength(Q);EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)DeQueue(Q,e);printf(" 隊首元素 %d 出隊，當前隊列長度=%dn",e,QueueLength(Q);.getchar();實驗內容（ 4）參考程序/*linkQueue.h文件 */typedef int QElemTy

46、pe;typedef struct QNode /結點類型QElemTypedata;struct QNode*next; QNode, *QueuePtr;typedef struct /鏈隊列類型QueuePtrfront;/隊頭指針QueuePtrrear;/隊尾指針 LinkQueue;enum StatusOK,ERROR,OVERFLOW;/*linkQueueOp.h文件 */#include "linkQueue.h"Status InitQueue (LinkQueue &Q) ;Status EnQueue (LinkQueue &Q,

47、QElemType e);Status DeQueue (LinkQueue &Q, QElemType &e) ;bool QueueEmpty(LinkQueue &Q);/*linkQueueOp.cpp文件 */#include <malloc.h>#include <stdlib.h>#include "linkQueueOp.h"Status InitQueue (LinkQueue &Q) / 構造一個空隊列 QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNod

48、e);.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->next = NULL;Q.rear->next = p;Q.rear = p;return OK;Stat

49、us DeQueue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除 Q 的隊頭元素，/ 用 e 返回其值，并返回 OK；否則返回 ERRORif (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;/ 判斷隊列是否為空bool QueueEmpty(LinkQueue &Q)if(Q.front = Q.rear)return true;elsereturn false;./*main.cpp文件 */#include <