大數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)上機(jī)代碼完整版

1、實用標(biāo)準(zhǔn)文檔大全數(shù)據(jù)結(jié)構(gòu)第一、二次上機(jī)：#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define list_init_size 100/線性表存儲空間的初始分配量#define LISTINCREMENT 10/線性表存儲空間的分配增量typedef int Status;typedef int El

2、emType;typedef structElemType *elem;int length;int listsize;SqList;/存儲空間基址/當(dāng)前長度/當(dāng)前分配的存儲容量(以sizeof(ElemType) 為單位)Status InitList_Sq(SqList &L)/構(gòu)造一個空的線性表LL.elem =(ElemType * )malloc(list_init_size*sizeof(ElemType);if(!L.elem )exit(OVERFLOW);/ 存儲分配失敗L.length =0;/空表長度為0L.listsize =list_init_size;/ 初

3、始存儲容量return OK;/Initlist_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e)/在順序線性表L 中第 i 個位置之前插入新的元素e，/i 的合法值為1<=i<=ListLength_Sq(L)+1ElemType *p,*q,*newbase; if(i<1|i>L.length +1)return ERROR;if(L.length >=L.listsize ) newbase=(ElemType/定義指針/i 值不合法/當(dāng)前存儲空間已滿，增加分配*)realloc(L.elem,(

4、L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW); / 存儲分配失敗L.elem =newbase;/新基址L.listsize +=LISTINCREMENT; / 增加存儲容量q=&(L.elem i-1);/q 為插入位置for(p=&(L.elem L.length -1);p>=q;-p)*(p+1)=*p;/插入位置及之后的元素右移*q=e;/插入 e+L.length ;/表長增1return OK;/ListInsert_SqStatus ListDelete_Sq(

5、SqList &L,int i,ElemType &e)/在順序線性表L 中刪除第i 個元素，并用e 返回其值/i 的合法值為1<=i<=ListLength_Sq(L)ElemType *p,*q;/定義指針 void display(SqList L)if(i<1) | (i>L.length ) return ERROR;p=&(L.elem i-1);e=*p;q=L.elem +L.length -1; for(+p;p<=q;+p) *(p-1)=*p;-L.length ;return OK;/ListDelete_sq/i

6、值不合法/p 為被刪除元素的位置/被刪除元素的值賦給e/表尾元素的位置/被刪除元素之后的元素左移/表長減1/定義for 循環(huán)函數(shù)int i;for(i=0;i<=L.length -1;i+)printf("%dn",L.elem i); int LocateElem_Sq(SqList L,ElemType e)在順序線性表L中查找第1個值與e滿足compare。的元素的位序/若找到，則返回其在L 中的位序，否則返回0ElemType *p;int i=1;/i 的初值為第一個元素的位序p=L.elem ;/p 的初值為第一個元素的存儲位置while(i<=L

7、.length && *p+!=e) +i;if(i<=L.length) return i;else return 0;/LocateElem_Sqvoid MergeList_Sq(SqList La,SqList Lb,SqList &Lc )/已知順序線性表La 和 Lb 的元素按值非遞減排列/歸并La 和 Lb 得到新的順序線性表Lc， Lc 的元素也按非遞減排列ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa=La.elem ;pb=Lb.elem ;Lc.listsize =Lc.length =La.length

8、+Lb.length ;pc=Lc.elem =(ElemType *)malloc(Lc.listsize *sizeof(ElemType);if(!Lc.elem )exit(OVERFLOW);/存儲分配失敗pa_last=La.elem +La.length -1;pb_last=Lb.elem +Lb.length -1;while(pa<=pa_last && pb<=pb_last)/歸并if(*pa<=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa<=pa_last) *pc+=*pa+;/插入La 的剩余元素

9、while(pb<=pb_last) *pc+=*pb+;/插入Lb 的剩余元素/MergeList_Sqvoid main()/*SqList L;/ 定義線性表InitList_Sq(L);/ 調(diào)用空表/插入數(shù)據(jù)ListInsert_Sq(L,1,10);ListInsert_Sq(L,2,20);ListInsert_Sq(L,1,30);ListInsert_Sq(L,3,40);printf(" 插入后：n");display(L);/ 調(diào)用循環(huán)函數(shù)ListInsert_Sq(L,3,100);/ 在 L 表第三個位置插入100printf(" 插

10、入后：n");display(L);ElemType e;定義 ee 表示ListDelete_Sq(L,3,e);/ 刪除 L 表的第三個元素，用 printf(" 刪除后：n");display(L);printf(" 被刪除元素：%dnnnn",e);*/SqList La,Lb,Lc;InitList_Sq(La);ListInsert_Sq(La,1,3);ListInsert_Sq(La,2,5);ListInsert_Sq(La,3,8);ListInsert_Sq(La,4,11); printf("La 插入后：n&

11、quot;);display(La);InitList_Sq(Lb);ListInsert_Sq(Lb,1,2);ListInsert_Sq(Lb,2,6);ListInsert_Sq(Lb,3,8);ListInsert_Sq(Lb,4,9);ListInsert_Sq(Lb,5,11);ListInsert_Sq(Lb,6,15);ListInsert_Sq(Lb,7,20); printf("Lb 插入后：n");display(Lb);MergeList_Sq(La,Lb,Lc); printf(" 歸并后：n");display(Lc);pri

12、ntf("n");int a=LocateElem_Sq( Lc, 5); printf("%dn",a);第三次上機(jī)：#include <stdio.h>#include <malloc.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNodeElemType data;s

13、truct LNode *next;LNOde,*LinkList;Status GetElem_L(LinkList L,int i,ElemType &e)/L 為帶頭結(jié)點的單鏈表的頭指針ERROR/當(dāng)?shù)?i 個元素存在時，其值賦給e 并返回 OK ，否則返回LinkList p;p=L->next;int j=1;/初始化，p 指向第一個結(jié)點，j 為計數(shù)器while(p&&j<i)/順指針向后查找，直到p 指向第 i 個元素或p 為空p=p->next;+j;if(!p|j>i)return ERROR;/第i 個元素不存在e=p->

14、data;/取第i 個元素return OK;/GetElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e) /在帶頭結(jié)點的單鏈線性表L 中第 i 個位置之前插入元素LinkList p,s;p=L;int j=0;while(p&&j<i-1)p=p->next;+j;/尋找第i-1 個結(jié)點if(!p|j>i-1) return ERROR;/i 小于或者大于表長+1s=(LinkList)malloc(sizeof(LNode);/生成新結(jié)點s->data=e;s->next=p-

15、>next;/插入 L 中p->next=s;return OK;/ListInsert_LStatus ListDelete_L(LinkList &L,int i,ElemType &e)/在帶頭結(jié)點的單鏈線性表L 中，刪除第i 個元素，并由e 返回其值LinkList p,q;p=L;int j=0;while(p->next&&j<i-1)/尋找第i 個結(jié)點，并令p 指向其前趨p=p->next;+j;if(!(p->next)|j>i-1) return ERROR;/刪除位置不合理q=p->next;p

16、->next=q->next;/刪除并釋放結(jié)點e=q->data;free(q);return OK;/ListDelete_L void CreateList_L(LinkList &L,int n)/逆位序輸入n 個元素的值，建立帶表頭結(jié)點的單鏈線性表LLinkList p;L=(LinkList)malloc(sizeof(LNode);L->next =NULL; /先建立一個帶頭結(jié)點的單鏈表for(int i=n;i>0;-i)/生成新結(jié)點/輸入元素值/插入到表頭p=(LinkList)malloc(sizeof(LNode);scanf(&qu

17、ot;%d",&p->data);p->next=L->next ;L->next =p;/CreateList_Lvoid display(LinkList L) LinkList p=L->next;/定義 for 循環(huán)函數(shù)while(p)printf("%d,",p->data);p=p->next;printf("n"); void main()LinkList L;CreateList_L(L,3);display(L);ListInsert_L(L,2,100);display(L)

18、;ElemType e;ListDelete_L(L,2,e);display(L);printf(" 被刪除的值=%dn",e);GetElem_L(L,3,e);printf(" 獲取的值=%dn",e);第四次上機(jī)#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2

19、typedef int SElemType;typedef int Status;#define STACK_INIT_SIZE 100#define STRCKINCREMENT 10 typedef structSElemType *base;SElemType *top;int stacksize;SqStack;/存儲空間初始分配量/存儲空間分配增量在棧構(gòu)造之前和銷毀之后，base的值為NULL/棧頂指針/當(dāng)前已分配的存儲空間，以元素為單位Status InitStack(SqStack &S)/構(gòu)造一個空棧SS.base =(SElemType *)malloc(STACK_

20、INIT_SIZE * sizeof(SElemType);if(!S.base )exit(OVERFLOW);/存儲分配失敗S.top =S.base ;S.stacksize =STACK_INIT_SIZE;return OK;/InitStackStatus GetTop(SqStack S,SElemType &e)/若棧不空，則用e 返回 S 的棧頂元素，并返回OK ；否則返回ERRORif(S.top =S.base )return ERROR;e=*(S.top -1);return OK;/GetTopStatus Push(SqStack &S,SElem

21、Type e)/插入元素e 為新的棧頂元素if(S.top - S.base >=S.stacksize )/棧滿，追加存儲空間S.base =(SElemType * )realloc(S.base ,(S.stacksize +STRCKINCREMENT) * sizeof(SElemType);if(!S.base )exit(OVERFLOW);S.top =S.base +S.stacksize ;S.stacksize +=STRCKINCREMENT;/存儲分配失敗*S.top +=e; return OK;/PushStatus Pop(SqStack &S,S

22、ElemType &e)/若棧不空，則刪除 S的棧頂元素，用 e返回其值，并返回 OK;否則返回ERROR if(S.top =S.base )return ERROR;e=*-S.top ;return OK;/PopStatus StackEmpty(SqStack S) if(S.top=S.base)return TRUE;else return ERROR;void conversion()/對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)SqStack S;int N;SElemType e;InitStack(S);/構(gòu)造空棧scanf("%d&qu

23、ot;,&N); while(N)Push(S,N % 8);N=N/8;printf(" 轉(zhuǎn)換成八進(jìn)制后的數(shù)為：");while(!StackEmpty(S)Pop(S,e);printf("%d",e); printf("n");/conversionvoid main()SqStack S;SElemType e,x;InitStack(S);Push(S,5);Push(S,4);Push(S,3);Push(S,2);Push(S,1);GetTop(S,e);printf(" 棧頂元素為%dn"

24、,e);printf("n");Pop(S,x);printf(" 刪除的棧頂元素為%dn",x);printf("n");printf(" 輸入一個十進(jìn)制數(shù)：");conversion();第五次上機(jī)/* 隊列的鏈?zhǔn)酱鎯?/#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBL

25、E -1#define OVERFLOW -2typedef int QElemType;typedef int Status;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/隊頭指針QueuePtr rear;/隊尾指針LinkQueue;Status InitQueue(LinkQueue &Q)/構(gòu)造一個空隊列QQ.front =Q.rear =(QueuePtr)malloc(sizeof(QNode);if(!Q.front

26、)exit(OVERFLOW);/存儲分配失敗Q.front ->next =NULL;return OK;Status DestroyQueue(LinkQueue &Q)/銷毀隊列Qwhile(Q.front )Q.rear =Q.front ->next ;free(Q.front );Q.front =Q.rear ;return OK;Status EnQueue(LinkQueue &Q,QElemType e)/插入元素e 為 Q 的新的隊尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit

27、(OVERFLOW);/存儲分配失敗p->data=e; p->next=NULL; Q.rear ->next =p; Q.rear =p; return OK; Status DeQueue(LinkQueue &Q,QElemType &e)/若隊列不為空，則刪除Q 的隊頭元素，用e 返回其值，并返回OK；/否則返回ERRORQueuePtr p;if(Q.front =Q.rear )return ERROR;p=Q.front ->next ;e=p->data;Q.front ->next =p->next;if(Q.rea

28、r =p)Q.rear =Q.front ;free(p);return OK;void disp(LinkQueue Q)QueuePtr p;p=Q.front->next;/定義for 循環(huán)函數(shù)while(p)printf("%d ",p->data);p=p->next;printf("n");void main()LinkQueue Q;QElemType e;InitQueue(Q);printf(" 插入的元素為：n");EnQueue(Q,25);EnQueue(Q,5);EnQueue(Q,12);

29、EnQueue(Q,60);EnQueue(Q,33);disp(Q);printf(" 刪除隊頭元素后：n");DeQueue(Q,e);disp(Q);DestroyQueue(Q);if(DestroyQueue(Q)=1)printf(" 銷毀隊列成功！n");elseprintf(" 銷毀隊列失??！n");附加：/* 隊列的順序存儲*/#define MAXQSIZE 100/最大隊列長度/初始化的動態(tài)分配存儲空間/頭指針，若隊列不空，指向隊列頭元素typedef struct QElemType *base int fro

30、nt;int rear;/尾指針，若隊列不空，指向隊列尾元素的下一個位置 SqQueue;Status InitQueue(SqQueue &Q)/構(gòu)造一個空隊列Q.base =(QElemType *)malloc(MAXQSIZE * sizeof(QElemType);if(!Q.base )exit(OVERFLOW);/存儲分配失敗Q.front =Q.rear =0;return OK;int QueueLenth(SqQueue Q)/返回Q 的元素個數(shù)，即隊列的長度return(Q.rear -Q.front +MAXQSIZE)%MAXQSIZE;Status EnQ

31、ueue(SqQueue &Q,QElemType e)/插入元素e 為 Q 的新的隊尾元素if(Q.rear +1) % MAXQSIZE =Q.front) return ERROR;/隊列滿Q.base Q.rear =e;Q.rear =(Q.rear +1) % MAXQSIZE;return OK;Status DeQueue(SqQueue &Q,QElemType &e)/若隊列不為空，則刪除Q 的隊頭元素，用e 返回其值，并返回OK；/否則返回ERRORif(Q.front =Q.rear ) return ERROR;e=Q.base Q.front ;Q.front =(Q.front +1)% MAXQSIZE;return OK;第六次上機(jī)#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define TRUE 1#define FALSE 0