數(shù)據(jù)結(jié)構(gòu)線性表的基本操作及應(yīng)用試驗(yàn)報(bào)告

1、實(shí)驗(yàn)日期2021.4.19教師簽字 成績 實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)名稱第二章線性表的根本操作及應(yīng)用【實(shí)驗(yàn)?zāi)康摹?1) 熟練掌握線性表的根本操作的實(shí)現(xiàn)；(2) 以線性表的各種操作(建立、插入、刪除等)的實(shí)現(xiàn)為重點(diǎn)；(3) 通過本次實(shí)驗(yàn)加深對C語言的使用(特別是函數(shù)的參數(shù)調(diào)用、指針類型 的應(yīng)用和鏈表的建立等各種根本操作).【實(shí)驗(yàn)內(nèi)容】1 .順序表的根本操作(順序表的插入、訪問、刪除操作)#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#defineOVERFLOW -1typedefint ElemT

2、ype;typedefint Status;#defineLIST_INIT_SIZE 100#defineLISTINCREMENT 10typedefstruct)ElemType *elem;int length;int listsize;JSqList;Status InitList_Sq(SqList *L)(int i,n;L->elem = (ElemType * )malloc(LIST_INIT_SIZE*sizeof(ElemType); if(! L->elem) exit (OVERFLOW);printfC*您希望您的順序表有兒個(gè)元素：,scanf(M%d

3、&n);printfC'Xn");printf("輸入您的<1個(gè)元素,以構(gòu)建順序表:n",n);for(i=l;i<=n;i+)scanf(d,&L->elemi-l);L->length = n;L->listsize = LIST_INIT_SIZE;return OK;InitList_SqStatus PrintList_Sq(SqList L)(int i;printf(順序表中的元素為：");for (i=l ;i<=L.length;i+)printf(H%d H,L.elemi-

4、1 );printf(HnH);return OK;)/PrintList_Sqint ListInsert_Sq(SqList* L,int i,ElemType x)對順序表進(jìn)行插入操作intj；if (L->length=L->listsize)(printf("ttt 順序表已滿");retum 0;elseif (i<llli>L->length)(printf("ttt 位置不合法");retum 0;)else(for(j=L->length-1 ;j>=i-1 ;-j)L->elemj+l=

5、L->elemj;L->elemi-l=x;L->length+;return 1;)int ListDelete_Sq(SqList* LJnt i) 對順序表進(jìn)行刪除操作intj；if (i< 1 lli>L->length)(printf(nttt 不存在第 i 個(gè)元素n);return 0; elsefor (j=il ;jvL>length;j+)L->elemj=L->elemj+l ;)L->length;return 1;1int LocateElem(SqList *L, int i) (if(i<llli&g

6、t;L->length)return ERROR;else return L->elemi-l;int scan()(int choose;printf(選擇要執(zhí)行的根本操作:nl.插入元素；2.刪除元素；3.訪問元素An);printf("輸入其他值退出程序n");scanf(d",&choose);return(choose);void niain()(SqList L;ElemType e;int i;int quit=O;if (InitList_Sq(&L)=OVERFLOW)printf(分配失敗,退出程序！,printf(

7、H輸出程序中的元素n)；PrintList_Sq(L);while(!quit)switch(scan()(case l:printf("n請輸入你所需要插入的位置和你要插入的元素：,printf("»請輸入i和e的值:")；scanf(,%d%dH,&i,&e);if (ListInsert_Sq(&L,i,e)=OK) PrintList_Sq(L);break;case 2:printf("n請輸入你所需要?jiǎng)h除元素的位置:")；scanf(d,&i);if(ListDelete_Sq(&L

8、,i)=OK) PrintList_Sq(L);break;case 3:printf("請輸入所要查找元素的位scanf(d,&i);if(LocateElem(&L,i)printf(n 該位置元素的值為:d!n,LocateElem(&L,i);else printf("該位置的元素不存在!n");break;default:quit=l;printf(操作結(jié)束!);printf(n)；2.單向鏈表的根本操作(單向鏈表的插入、刪除、查找以及并表操作)#include<stdio.h>#include<malloc.h

9、>typedef int ElemType;#define OK 1#define ERROR 0#define flag 0typedef struct LNode(ElemType data;struct LNode *next; LNode,*LinkList;LinkList InitLinkList()LinkList L;L=(LinkList)malloc(sizeof(LNode);L->next=NULL; return L;LinkList LocateLinkList(LinkList L,int i)LinkList p;int j;p=L->next

10、;j=l;while(p!=NULL&&j<i)p=p->next; j+;if(j=i)return p;else return NULL; -void LinkListInsert(LinkList L, int i, ElemType e)插入元素LinkList p,s; intj;j=l;p=L;while(p&&j<i)p=p->next;j+;1if(p=NULLIIj>i)printf("插入位置不正確n");else (s=(LNode *)malloc(sizeof(LNode);s->

11、data=e;s->next=p->next;p->next=s;printf("%d已插入到鏈表中n",e);)void LinkListDeIete(LinkList L,int i) 刪除元素(LinkList p,q;int j;j=l；p=L;while(p->next&&j<i)p=p->next;j+;)if(p->next=NULL)printf("刪除位置不正確n");else(q=p->next;p->next=q->next;free(q);printf(第

12、d個(gè)元素已從鏈表中刪除n,i);)LinkList CreatLinkList()/建立單向鏈表(LinkList L=InitLinkList(),p,r;ElemType e;r=L;printf("請依次輸入鏈表中的元素,輸入0結(jié)束n);scanf(M%d&e);while (e!=flag)p=(LinkList)malloc(sizeof(LNode);p->data=e;r->next=p;r=p;scanf(d,&e);r->next=NULL;return L;int LinkListLength(LinkList L)(LinkLi

13、st p;int j;p=L->next;j=0；while(p!=NULL)(j+；p=p->next;return j;void LinkListPrint(LinkList L)(LinkList p;p=L->next;if(p=NULL) printf("單鏈表為空表n)；else(printf(鏈表中的元素為:nH);while(p!=NULL)printf("%d ,p->data);p=p->next;)printf(HnH);void Mergelist_L(LinkList La,LinkList Lb,LinkList L

14、c)(LNode *p"pb,*pc,*p;pa=La->next:pb=Lb->next;Lc=La;pc=Lc;while(pa&&pb)if(pa->data<=pb->data) (pc->next=pa;pc=pa;pa=pa->next;else pc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;p=Lc->next;printf("合并結(jié)果;while(p) printf(H%4d'p->data);p=p->ne

15、xt;)free(Lb);int scan()(int d;printf(請選擇你所要執(zhí)行的單向鏈表的根本操作:nl.插入元素;2.刪除元素;3.訪問元素4兩個(gè)單向鏈表的合并An,printf(其他鍵退出程序)；printfC'Xn");scanf(d,&d);return(d);1void main()( LinkList La,Lb,Lc;int quit=O;int ijocate;ElemType e;LinkList L,p;L=CreatLinkList();while(!quit)switch(scan()(case 1:printf(請輸入插入元素的位

16、置和值(中間以空格或回車分隔):n)；scanf(d%d%&i,&e);LinkListInsert(L,i,e);LinkListPrint(L);break;case 2:if(LinkListLength(L)=O)printf("鏈表已經(jīng)為空,不能刪除nn)；elseprintf(請輸入待刪除元素的位置:n,scanf(cT,&i);LinkListDelete(LJ);1LinkListPrint(L);break;case 3:printf("請輸入待查詢元素在鏈表中的位置：,scanf(d,&i);p=LocateLinkLis

17、t(L,i);if(P)printf(鏈表中第1%個(gè)元素的值為:dn,i,p->data);elseprintf("S詢位置不正確nn");break;case 4:Lza=CreatLinkList();Lb=CreatLinkList();Mergelist_L( La, Lb, Lc);printf(Hnn);break;default:quit=l;printf(操作結(jié)束!);printf(HnH);)3.單向循環(huán)鏈表的根本操作單向鏈表的插入、刪除、查找操作)#include<stdio.h>#inckide<malloc.h>type

18、def int EleniType;#define OK 1#define ERROR 0#define flag 0 typedef struct LNode ElemType data;struct LNode *next;) LNode,*LinkList;LinkList InitLinkList()(LinkList L;L=(LinkList)malloc(sizeof(LNode);L->next=L;return L;LinkList LocateLinkList(LinkList L,int i)(LinkList p;intj;p=L->next;jT；whil

19、e(p !=L&&j<i)p=p->next; j+;if(j=i)return p;else return NULL; 一void LinkListInsert(LinkList L, int i, ElemType e)插入元素(LinkList p,s;intj;j=l；p=L;while(p->next!=L&&j<i)p=p->next;j+;if(p=Lllj>i)printf("插入位置不正確n");else s=(LNode *)malloc(sizeof(LNode);s->data

20、=e;s->next=p->next;p->next=s;printf("%d已插入到鏈表中n",e);1void LinkListDeIete(LinkList L,int i) 刪除元素LinkList p,q;int j;j=l；p=L;while(p->next!=L&&j<i)p=p->next;j+；LinkList p;p=L->next;printfC*鏈表中的元素為:n);while(p!=L)(printf(H%d ,p->data);p=p->next;)printf(Hnn);in

21、t scan()(int d;printf(請選擇你所要執(zhí)行的單向鏈表的根本操作:nl.插入元素;2.刪除元素;3.訪 問元素An");printfC*其他鍵退出程序)；printf(偵')；scanf(d,&d);return(d);void niain()int quit=O;int i;ElemType e;LinkList L,p;L=CreatLinkList();while(!quit)switch(scan()(case 1:printf(請輸入插入元素的位置和值(中間以空格或回車分隔):n)；scanf(d%d,&i,&e);LinkL

22、istInsert(L,i,e);LinkListPrint(L);break;case 2:if(LinkListLength(L)=O)printf("鏈表已經(jīng)為空,不能刪除nn)；elseprintfC*請輸入待刪除元素的位置:n, scanf(d,&i);LinkListDelete(L,i);)LinkListPrint(L);break;case 3:printfC*請輸入待查詢元素在鏈表中的位置:,scanf(d,&i);p=LocateLinkList(LJ);if(P)printf(鏈表中第1個(gè)元素的值為:dn,i,p->data);elsep

23、rintf("S詢位置不正確nn");break;default:quit=l;printf("操作結(jié)束!,printf(HnH);)4.雙向鏈表的根本操作(雙向鏈表的插入、刪除、查找以及并表操作)#include<stdio.h>#inckide<malloc.h>#define flag 0 typedef int status;typedef int ElemType;typedef struct DuLNode(ElemType data;struct DuLNode *prior;struct DuLNode *next; DuL

24、Node,*DuLinkList;DuLinkList InitDiiLinkListQDuLinkList L;L=(DuLinkList)malloc(sizeof(DuLNode);L->next=L->prior=NULL; return L;DuLinkList CreatDuLinkList()(DuLinkList L=InitDuLinkList(),p,r;ElemType e;r=L;printf(H請依次輸入鏈表中的元素,輸入.結(jié)束n)；scanf(M%d&e);while (e!=flag)p=(DuLinkList)malloc(sizeof(Du

25、LNode);p->data=e;r->next=p;p->prior=r->next;r=p;scanf(d,&e);r->next=NULL;return L;void ListInsert_DuL(DuLinkList L, int i, ElemType e)( DuLinkList p,s;int j;j=l；p=L;while(p&&j<i)p=p->next;j+;)if(p=NULLIIj>i)printf("插入位置不正確n");else (s=(DuLinkList)malloc(s

26、izeof(DuLNode);s->data=e;s->next=p->next; p->next->prior=s;s->prior=p; p->next=s;printf("%d已插入到雙向鏈表中n",e); )void ListDelete_DuL(DuLinkList L,int i)刪除元素(DuLinkList p,q;intj;j=l；p=L;while(p->next&&j<i)(p=p->next;j+;)if(p->next=NULL)printf(刪除位置不正確n);el

27、seq=p->next;p->next=q->next;q->next->prior=p;free(q);printf(第d個(gè)元素已從鏈表中刪除n,i);void LinkListPrint_DuL(DuLinkList L)DuLinkList p;p=L->next;if(p=NULL) printfC'雙鏈表為空表n);else(printf(鏈表中的元素為:n)；while(p!=NULL)(printf(H%d 'p->data);p=p->next;)printf(HiiH);int DuLinkListLength(

28、DuLinkList L)(DuLinkList p;int j;p=L->next;j=0；while(p!=NULL)(j+;p=p->next;return j;DuLinkList LocateDuLinkList(DuLinkList L,int i)(DuLinkList p;int j;p=L->next;j=l;while(p!=NULLx&&j<i)p=p->next; j+;)if(j=i)return p;else return NULL;void Mergelist_L(DuLinkList La.DuLinkList Lb

29、,DuLinkList Lc)DuLNode *pa,*pb,*pc,*p;pa=La->next:pb=Lb->next;Lc=La;pc=Lc;while(pa&&pb)(if(pa->data<=pb->data) (pc->next=pa:pc=pa;pa=pa->next;else pc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;p=Lc->next;printf("合并結(jié)果:")；while(p) (printf(H%4d'p

30、->data);p=p->next;)free(Lb);int scan()(int d;printf(請選擇你所要執(zhí)行的雙向鏈表的根本操作:nl.插入元素;2.刪除元素;3.訪問元素4兩個(gè)雙向鏈表的合并An)；printf(其他鍵退出程序)；printf("»");scanf(d,&d);return(d);void main()int quit=O;int i;ElemType e;DuLinkList L,p;DuLinkList La,Lb,Lc;L=CreatDuLinkList();while(!quit)(switch(scan(

31、)case 1:printfC*請輸入插入元素的位置和值(中間以空格或回車分隔):n“)；scanf(d%d,&i,&e);ListInsert_DuL(L,i,e);LinkListPrint_DuL(L);break;case 2:if(DuLinkListLength(L)=O)printf("鏈表已經(jīng)為空,不能刪除nn");elseprintf(請輸入待刪除元素的位置:n,scanf(M%d&i);ListDelete_DuL(L,i);LinkListPrint_DuL(L);break;case 3:printfC*請輸入待查詢元素在鏈表

32、中的位置：,scanf(d,&i);p=LocateDuLinkList(L,i);if(P)printf(鏈表中第d個(gè)元素的值為:dn,i,p->data);elseprintfC*查詢位置不正確而站")；break;case 4:Lza=CreatDuLinkList():Lb=CreatDuLinkList();Mergelist_L( La, Lb, Lc);printf(Hnn);break;default:quit=l;printf("操作結(jié)束!,printf("n);15.雙向循環(huán)鏈表的根本操作(雙向循環(huán)鏈表的插入、刪除以及訪問操作)#

33、include<stdio.h>#inckide<malloc.h>#define flag 0typedef int status;typedef int ElemType;typedef struct DuLNodeElemType data;struct DuLNode *prior;struct DuLNode *next; DuLNode,*DuLinkList;DuLinkList InitDuLinkListQDuLinkList L;L=(DuLinkList)malloc(sizeof(DuLNode);L->next=L; L->prio

34、r=L;return L;DuLinkList CreatDuLinkList()(DuLinkList L=InitDuLinkList(),p,r;ElemType e;r=L;printf("請依次輸入鏈表中的元素,輸入0結(jié)束n)； scanf(d,&e);while (e!=flag)p=(DuLinkList)malloc(sizeof(DuLNode);p->data=e;r->next=p;p->prior=r->next;r=p;scanf(M%d&e);r->next=L; L->prior=r;return L;

35、)void ListInsert_DuL(DuLinkList L, int i, ElemType e)( DuLinkList p,s;intj;j=l；p=L;while(j<i)p=p->next;j+;)if(j>i)printf(插入位置不正確n)；else (s=(DuLinkList)malloc(sizeof(DuLNode);s->data=e;s->next=p->next; p->next->prior=s;s->prior=p; p->next=s;printf("%d已插入到雙向循環(huán)鏈表中n&qu

36、ot;,e); void ListDelete_DuL(DuLinkList L,int i)刪除元素(DuLinkList p,q;int j;j=l；p=L;while(p->next !=L&&j<i)(p=p->next;j+;if(p->next=L)printf("刪除位置不正確n");else(q=p->next;p->next=q->next;q->next->prioi-p;free(q);printfC*第<1個(gè)元素已從雙向循環(huán)鏈表中刪除n,i);void LinkListPrint_DuL(DuLinkList L)DuLinkList p;p=L->next;if(p->next=L) printf(H雙鏈表為空表n");else(printf(鏈表中的元素為:nH);wh