1、實驗二順序表與鏈表【實驗目的】1、掌握線性表中元素的前驅、后續的概念。2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。3、對線性表相應算法的時間復雜度進行分析。4、理解順序表、鏈表數據結構的特點（優缺點）。【實驗學時】4學時【實驗預習】回答以下問題：1、順序表的存儲表示假設線性表中每一個數據元素的存儲空間大小為1個字節，并且以其所占存儲空間的第一個字節的地址作為該元素的存儲位置，則線性表中任一個數據元素的存儲位置為：LOC（Ai尸LOC（A1）+（i-1）*1其中，LOC（A1）為線性表中第一個數據元素al的存儲位置，也稱為線性表的起始位置（首地址）。typedef struct

2、SqlistElemType *slist;/存儲空間的基地址int length;/ 表長度int listsize;/當前分配的存儲空間容量Sqlist;2、單鏈表的存儲表示線性鏈表也稱單鏈表，在每一個結點中只包含一個指針，用于指示該結點的直接后繼結點，整個鏈表通過指針相連，最后一個結點因為沒有后繼結點，其指針置為空（NULL ）。這樣，鏈表中所有數據元素（結點）構成一對一的邏輯關系，實現線性表的鏈式存儲。【實驗內容和要求】1、按照要求完成程序 exp2_1.c,實現順序表的相關操作。以下函數均具有返回值，若 操作完成，返回 OK,操作失敗返回ERROR。函數需返回的其他數據，使用函數參數

3、返回。 exp2_1.c部分代碼如下：#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1#define INIT_SIZE 100#define INCREM 10typedef int ElemType; /*定義表元素的類型 */* (1)-補充順序表的存儲分配表示，采用定長和可變長度存儲均可*/typedef struct SqlistElemType *slist;/ 基地址int length;/ 表長度int listsize;/分配的空間Sqlist;/*函數聲明*/int Init

4、List_sq(Sqlist *L);int CreateList_sq(Sqlist *L,int n);int ListInsert_sq(Sqlist *L,int i,ElemType e);int PrintList_sq(Sqlist *L);int ListDelete_sq(Sqlist *L,int ElemType *e);int ListLocate(Sqlist *L,ElemType e,int *pos);int menu_select();/* (2)-順序表的初始化*/int InitList_sq(Sqlist *L)L->slist=(ElemType

5、*)malloc(INIT_SIZE*sizeof(ElemType);if(!L->slist)return ERROR;L->length=0;L->listsize=INIT_SIZE; 初始空間容量return OK;/*InitList*/* (3)-創建具有n個元素的順序表*/int CreateList_sq(Sqlist *L,int n)ElemType e;int i;for(i=0;i<n;i+)printf("input data %d:",i+1);scanf("%d",&e);if(!ListI

6、nsert_sq(L,i+1,e)return ERROR; return OK;/*CreateList*/*(4)-輸出順序表中的元素*/ int PrintList_sq(Sqlist *L) int i;for(i=1;i<=L->length;i+) printf("%5d",L->slisti-1); return OK;/*PrintList*/* (5)-在順序表的第i個位置之前插入新元素 e*/ int ListInsert_sq(Sqlist *L,int i,ElemType e) int k;if(i<1|i>L->

7、;length+1) return ERROR;if(L->length>=L->listsize)當前空間已滿，申請新的空間L->slist=(ElemType *)realloc(L->slist,(L->listsize+INCREM)*sizeof(ElemType); if(!L->slist) return ERROR;L->listsize+=INCREM;for(k=L->length-1;k>=i-1;k-) L->slistk+1=L->slistk;L->slisti-1=e;L->len

8、gth+;return OK;/*ListInsert*/* (6)-在順序表中刪除第i個元素，e返回刪除的元素*/int ListDelete_sq(Sqlist *L,int i,ElemType *e)int j;if(i<1|i>L->length)return ERROR;*e=L->slisti-1;for(j=i;i<L->length;j+)L->slistj-1=L->slistj;L->length-;return OK;*/* ListDelete_sq */* (7)-在順序表中查找指定值元素，pos為返回其位置序號

9、int ListLocate(Sqlist *L,ElemType e,int *pos)ElemType *end=L->slist+L->length;ElemType *p=L->slist;int i;for(i=1;p<end;p+)if(*p=e)*pos=i;break; i+;if(p>=end)return ERROR;elsereturn OK;/* ListLocate */*定義菜單字符串數組*/int menu_select()char *menu="n*MENU*n","1. Create Listn&qu

10、ot;, /* 創建順序表 */"2. Get曰ementn",/*查找順序表中的元素*/"3. Insert datan",/* 插入數據 */"4. Delete datan", /* 刪除數據*/"0. Quitn",/* 退出 */"n*MENU*n"char s3;/*以字符形式保存選擇號*/int c,i;/*定義整形變量*/for (i=0;i<7;i+)/*輸出主菜單數組*/printf("%s",menui);do printf("nEnte

11、r you choice(04):");/* 在菜單窗 口外顯示提示信息*/scanf("%s",s);/* 輸入選擇項 */c=atoi(s);/*將輸入的字符串轉化為整形數*/ while (c<0|c>4);/*選擇項不在04之間重輸*/return c;/*返回選擇項，主程序根據該數調用相應的函數*/ /*主函數*/int main()Sqlist sl;InitList_sq(&sl);int n;int m,k;printf("please input n:");/*輸入順序表的元素個數*/scanf("

12、;%d",&n);if(n=0)printf("ERROR");for (;)/*無限循環*/*/switch (menu_select() /*調用主菜單函數，返回值整數作開關語句的條件 case 1:printf("n1-Create Sqlist:n");CreateList_sq(&sl,n);printf("nPrint Sqlist:n");PrintList_sq(&sl);break;case 2:printf("n3-GetElem from Sqlist:n")

13、;printf("please input search data:");scanf("%d",&k);int pos;if (!ListLocate(&sl,k,&pos) printf("Not found");elseprintf("found the element, position is %dn",pos);printf("nPrint Sqlist:n"); PrintList_sq(&sl);break;case 3:printf("n4

14、-Insert from Sqlist:n");printf("n input insert location and data:(location,data)n"); scanf("%d,%d",&m,&k);if (ListInsert_sq(&sl,m,k)printf("nOKn");printf("nPrint Sqlist:n");PrintList_sq(&sl);elseprintf("nERROR!");break;case 4:pri

15、ntf("n5-Delete from Sqlist:n");printf("nplease input delete locationn");scanf("%d",&k);int deldata;if (ListDelete_sq(&sl,k,&deldata)printf("nOKn");printf("nDelete data is %dn",deldata);printf("nPrintSqlist:n");PrintList_sq(&

16、sl);elseprintf("nERROR!");break;case 0:exit(0); /*如菜單返回值為 0程序結束*/return 0;2、按照要求完成程序exp2_2.c,實現單鏈表的相關操作。exp2_2.c部分代碼如下：#include<stdio.h> #include<malloc.h> #define ERROR 0 #define OK 1 typedef int ElemType; /*定義表元素的類型 */* (1)-線性表的單鏈表存儲表示*/typedef struct LNode ElemType data;stru

17、ct LNode *next; LNode,*LinkList;LNode *InitList(LinkList L); /*帶頭結點單鏈表初始化*/void PrintList(LinkList L);/*輸出帶頭結點單鏈表的所有元素*/int GetElem(LinkList L,int i,ElemType *e);/* 查找第 i 位置的元素，并由e返回其值*/int InsertElem(LinkList L,int i,ElemType e);/* 在第 i 個位置插入元素 e*/ int DeleteElem(LinkList L,int i,ElemType *e);/* 刪除

18、第 i 位置的元素，并由 e返回其值 */ void DestroyLinkList(LinkList L);/*釋放鏈表及其空間 */LinkList CreateList(int n); /* 創建 n 個結點的單鏈表 */ int menu_select();/* 菜單函數*/*帶頭結點單鏈表初始化*/LNode *InitList(LinkList L) L=(LNode *)malloc(sizeof(LNode);/* 申請一個頭結點 */if (!L) return ERROR;/* 申請失敗 */L->next=NULL;/*頭結點的指針域置空 */return L; /

19、* (1)-輸出帶頭結點單鏈表的所有元素*/void PrintList(LinkList L) LNode *p;p=L->next;while(p!=NULL) printf("%5d",p->data); p=p->next; /*PrintList*/*(2)-在單鏈表的第i個位置插入元素e,若插入成功返回 OK,插入失敗返回 int InsertElem(LinkList L,int i,ElemType e)LNode *p=L,*s;int j=0;while(p&&j<i-1)/尋找插入位置 p=p->next;

20、j+；if(!p|j>i-1)return ERROR;s=(LNode*)malloc(sizeof(LNode); if(!s)return ERROR;s->data=e;s->next=p->next;p->next=s;return OK;/* InsertElem */*(3)-查找第i位置的元素，若存在返回OK并由e返回其值，若不存在返回 int GetElem(LinkList L,int ElemType *e)LNode *p;int j=1; while(p&&j<i)p=p->next;j+; if(!p|j&g

21、t;i) return ERROR;*e=p->data;return OK;/*GetElem*/ERROR*/ERROR*/*（4）-刪除第i位置的元素，成功返回OK,并由e返回其值，若不成功返回ERROR ,注意刪除的結點必須釋放其所占空間*/int DeleteElem(LinkList L,int i,ElemType *e)LNode *p=L,*s;int j=0;while(p&&j<i-1)/尋找插入位置p=p->next;j+；if(!p|j>i-1)return ERROR;s=p->next;p->next=s->

22、;next;*e=s->data;free(s);return OK;/* DeleteElem */* (5)-創建具有n個結點的單鏈表，創建成功返回其頭指針*/LinkList CreateList(int n)LNode *p,*q,*head;int i;head=(LinkList)malloc(sizeof(LNode);head->next=NULL;p=head;for(i=0;i<n;i+)q=(LinkList)malloc(sizeof(LNode);printf("input data %d",i+1);scanf("%d

23、",&q->data);q->next=NULL;/節點指針域置空 p->next=q;/新節點連接在表末尾 p=q;return head;/*CreateList*/*釋放鏈表及其空間*/ void DestroyLinkList(LinkList L) LNode *p=L,*q;while(p)q=p->next;free(p);p=q;/* DestroyLinkList */ int menu_select()/*初始化鏈表*/*查找元素*/*插入元素*/*刪除元素*/*創建具有n個元素的鏈表*/char *menu="n*MEN

24、U*n","1. Init LinkListn","2. Get Elementn","3. Insert datan","4. Delete datan","5. CreateLinkListn","0. Destroy LinkList&&Quitn", /*釋放鏈表所占空間 &退出 */"n*MENU*n"char s3;/*以字符形式保存選擇號*/int c,i;/*定義整形變量*/for (i=0;i<8;

25、i+)/*輸出主菜單數組*/printf("%s",menui); do printf("nEnter you choice(05):");/* 在菜單窗 口外顯示提示信息*/scanf("%s",s);/* 輸入選擇項 */c=atoi(s);/*將輸入的字符串轉化為整形數*/ while (c<0|c>5);/*選擇項不在05之間重輸*/return c;/*返回選擇項，主程序根據該數調用相應的函數*/int main() int i,n;ElemType e;LinkList L=NULL;/*定義指向單鏈表的指針

26、*/for (;)/*無限循環*/switch (menu_select() /*調用主菜單函數，返回值整數作開關語句的條件*/*值不同，執行的函數不同， break不能省略*/case 1:printf("n1-Init LinkList:n");L=InitList(L);if(L!=NULL)printf("nInitLinkList OK!n");elseprintf("nInitLinkList Error!n");break;case 2:printf("n2-GetElem from LinkList:n&qu

27、ot;);printf("input pos=");scanf("%d",&i);if (L!=NULL&&GetElem(L,i,&e)printf("No%i is %d",i,e);printf("nPrintfList:n");PrintList(L);elseprintf("Error&Not exists!");break;case 3:printf("n3-Insert e into LinkList:n");printf

28、("input pos=");scanf("%d",&i);printf("input e=");scanf("%d",&e);if(L!=NULL&&InsertElem(L,i,e)printf("nInsert OK!n");printf("nPrintfList:n");PrintList(L);elseprintf("nInsert Error!n");break;case 4:printf("n4-De

29、lete from LinkList:n");printf("input pos=");scanf("%d",&i);if(L!=NULL&&DeleteElem(L,i,&e)printf("nOKn");printf("nDelete data is %dn",e);printf("nPrintfList:n"); PrintList(L); elseprintf("nDelete Error!n"); break; case 5

30、:printf("please input n:");/*輸入單鏈表的元素個數 */scanf("%d",&n);if (n<0) printf("ERROR"); break; printf("nCreate LinkListn");L=CreateList(n);if (L=NULL) printf("Error!n"); break; printf("nPrintfList:n"); PrintList(L); break; case 0:printf(&

31、quot;nDestroy linklist and free memoryn");if(L!=NULL) DestroyLinkList(L); L=NULL; exit(0);/*如菜單返回值為0程序結束*/ return 0;3、循環鏈表的應用(約瑟夫回環問題)用整數序列1, 2, 3,，n表示順序坐在圓桌周圍的人，并采用循環鏈表作為存儲結構。任意位置k開始計數，計到 m讓此位置的人出局，重復上述過程，直至只剩下最后一個人。依次輸出每個出局的人的序號。提示：用一個無頭結點的循環單鏈表來實現n個元素的存儲。exp2_3.c部分代碼如下:#include<stdio.h>

32、;#include<malloc.h>#define ERROR 0#define OK 1typedef int ElemType; /*定義表元素的類型 */typedef struct LNode/*線性表的單鏈表存儲 */ElemType data;struct LNode *next; LNode,*LinkList;/* (1)-創建具有n個結點的無頭結點的單向循環鏈表，返回其頭指針*/LinkList CreateList(int n)LinkList head=NULL;LNode *s,*r;int i;for(i=1;i<=n;i+) s=(LNode*)

33、malloc(sizeof(LNode);s->data=i;s->next=NULL;if(head=NULL) head=s; else r->next=s; r=s; r->next=head;return head;/*CreateList*/* (2)-輸出無頭結點循環單鏈表的所有元素*/void PrintList(LinkList L) LNode *p,*q;p=L->next;p=L; q=p; while(p!=NULL)printf("%5d",p->data);p=p->next;if(p=q)break;p

34、rintf("n");/*PrintList*/*/*(3)-約瑟夫問題計算，依次輸出出局的元素的序號 void JOSEPHUS(int n,int k,int m,LinkList L)LNode *p,*q;int i;p=L;for(i=1;i<k;i+)q=p;p=p->next;while(p->next!=p)for(i=1;i<m;i+)q=p;p=p->next;q->next=p->next;printf("%5d",p->data);free(p);p=q->next;print

35、f("%5d",p->data);/*JOSEPHUS*/int main()int n,m,k;LinkList L=NULL;/* 定義指向單鏈表的指針 */輸入n個人、從k位置開始、報 m出局while(scanf("%d%d%d",&n,&k,&m)=3)/*n個元素從k位置開始每 m個報數*/L=CreateList(n);PrintList(L);JOSEPHUS(n,k,m,L);return 0;4、選做實驗：設有頭單鏈表，設計算法將表中值相同的元素僅保留一個結點。提示：指針p從鏈表的第一個元素開始，利用指針

36、 q從指針p位置開始向后搜索整個鏈表， 刪除與之值相同的元素；指針p繼續指向下一個元素，開始下一輪的刪除，直至p=null為至，既完成了對整個鏈表元素的刪除相同值。#include<malloc.h>#include<stdio.h>#define ERROR 0定義表元素的類型*/#define OK 1typedef int ElemType; /*/* (1)-線性表的單鏈表存儲表示 typedef struct LNode ElemType data;struct LNode *next; LNode,*LinkList;LinkList L=NULL;LNod

37、e *InitList(LinkList L); /* void PrintList(LinkList L); /* void DestroyLinkList(LinkList L);/* LinkList CreateList(int n); /* /*帶頭結點單鏈表初始化*/LNode *InitList(LinkList L) L=(LNode *)malloc(sizeof(LNode); if (!L) return ERROR;/*L->next=NULL;/*return L;*/帶頭結點單鏈表初始化*/輸出帶頭結點單鏈表的所有元素*/釋放鏈表及其空間*/創建n個結點的單鏈表*/*申請一個頭結