數(shù)據(jù)結(jié)構(gòu)_實(shí)驗(yàn)二_線性表及其實(shí)現(xiàn)

1、實(shí)驗(yàn)編號(hào)：2 四川師大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 2016年9月30日實(shí)驗(yàn)二 線性表及其實(shí)現(xiàn)_一 實(shí)驗(yàn)?zāi)康募耙螅?） 熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)（順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)）上的實(shí)現(xiàn)，以線性表的各種操作（建立、插入、刪除等）的實(shí)現(xiàn)為實(shí)驗(yàn)重點(diǎn)。（2） 通過本次實(shí)驗(yàn)幫助學(xué)生加深對(duì)順序表、鏈表的理解，并加以應(yīng)用。（3） 掌握循環(huán)鏈表和雙鏈表的定義和構(gòu)造方法。二 實(shí)驗(yàn)內(nèi)容（1） 編程實(shí)現(xiàn)線性表兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）中的基本操作的實(shí)現(xiàn)（線性表的創(chuàng)建、插入、刪除、查找（順序查找、折半查找）、排序等），并設(shè)計(jì)一個(gè)菜單調(diào)用線性表的基本操作。（2） 建立一個(gè)按元素遞增有序的單鏈表L，并編寫程序?qū)崿F(xiàn)：a） 將

2、x插入其中后仍保持L的有序性；b） 將數(shù)據(jù)值介于min和max之間的結(jié)點(diǎn)刪除，并保持L的有序性；c） 將單鏈表L逆置并輸出；（3） 編程實(shí)現(xiàn)將兩個(gè)按元素遞增有序的單鏈表合并為一個(gè)新的按元素遞增的單鏈表。注：（1）為必做題，（2）（3）選做。三 主要儀器設(shè)備及軟件（1）PC機(jī)（2）Dev C+ ,Visual C+, VS2010等四 實(shí)驗(yàn)主要流程、基本操作或核心代碼、算法片段（該部分如不夠填寫，請(qǐng)另加附頁(yè)）（1） 編程實(shí)現(xiàn)線性表兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）中的基本操作的實(shí)現(xiàn)（線性表的創(chuàng)建、插入、刪除、查找（順序查找、折半查找）、排序等），并設(shè)計(jì)一個(gè)菜單調(diào)用線性表的基本操作。A.順序儲(chǔ)存：

3、Ø 代碼部分：Main.cpp:#include"Sqlist.h"int main()Sqlist L;int e = 0, number=0,locat =0,elect=0;int ret;/存放返回值printf("請(qǐng)先創(chuàng)建一個(gè)含有10個(gè)整型元素的順序表！n");Initlist_Sq(L);do elect=Print_Sq(L);switch (elect) case 0: break; case 1:/插入 printf("請(qǐng)輸入你想添加的位置和數(shù)字（用空格隔開）："); scanf_s("%d%d&

4、quot;,&number,&locat); ListInsert_Sq(L, number, locat); break; case 2:/刪除 printf("請(qǐng)輸入你想刪除數(shù)字的位置："); scanf_s("%d", &locat); listDelete_Sq(L, locat, e); printf("the delete number is %dn", e);break; case 3:/順序查找 printf("請(qǐng)輸入你想查找的數(shù)字："); scanf_s("%d&

5、quot;, &number);ret=listFine1_Sq(L, locat, number);if(ret)printf("%d在表中的位置是%dn", number, locat);break; case 4:/折半查找 printf("請(qǐng)輸入你想查找的數(shù)字："); scanf_s("%d", &number);ret=listFine2_Sq(L, locat, number);if(ret)printf("%d在表中的位置是%dn", number, locat); break;cas

6、e 5:/升序 Ascending_Sq(L);break;case 6:/降序 Decending_Sq(L); break; default: printf("輸入錯(cuò)誤!n"); while (elect != 0);system("pause");return 0;Sqlist.cpp:#include"Sqlist.h"/輸出表格int Print_Sq(Sqlist &L)int i = 0;printf("現(xiàn)有線性表：n");for (; i < L.length; i+)printf(&

7、quot;%5d", L.elemi);printf("n");i = 0;printf("*n");printf("*1.插入*n");printf("*2.刪除*n");printf("*3.順序查找*n");printf("*4.折半查找*n");printf("*5.排升序*n");printf("*6.排降序*n");printf("*0.退出*n");printf("*n")

8、;printf("請(qǐng)輸入你的選擇：");scanf_s("%d", &i);return i;/創(chuàng)建順序線性表Status Initlist_Sq(Sqlist &L)int i, number;L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;for (i = 0; i<LIST_INIT_SIZE; i+)printf(

9、"請(qǐng)輸入第%d個(gè)數(shù)字：", i + 1);scanf_s("%d", &number);L.elemi = number;L.length+;return OK;/在線性表中的第i個(gè)位置插入e；Status ListInsert_Sq(Sqlist &L, int i, ElemType e)ElemType *q, *p, *newelem;if (i<1 | i>L.length + 1)return ERROR;if (L.length >= L.listsize)newelem = (ElemType *)rea

10、lloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType);if (!newelem) exit(OVERFLOW);L.elem = newelem;L.listsize += LISTINCREMENT;q = &(L.elemi - 1);for (p = &(L.elemL.length - 1); p >= q; -p)*(p + 1) = *p;*q = e;+L.length;return OK;/刪除第i個(gè)位置的元素并返回eStatus listDelete_Sq(Sqlist &L,

11、int i, ElemType &e)ElemType *p, q;if (i<1 | i>L.length)return ERROR;p = &(L.elemi - 1);e = *p;for (q = i - 1; q<L.length - 1; q+)p+;*(p - 1) = *p;-L.length;return OK;/順序查找Status listFine1_Sq(Sqlist L, int &locat, ElemType e)ElemType j = 0;for (; j<L.length; j+)if (e = L.elemj

12、)locat = j + 1;return OK;printf("not find");return ERROR;/折半查找Status listFine2_Sq(Sqlist L, int &locat, ElemType e)int high = L.length-1, low = 0,mid;domid=(high + low) / 2;if (e > L.elemmid)low = mid+1;else if (e < L.elemmid)high = mid-1;elselocat = mid+1;return OK;while (low &l

13、t;= high);printf("not find");return ERROR;/升序Status Ascending_Sq(Sqlist L)int i, j, min=0, temp;for (i = 0; i < L.length - 1; i+)for (j = i; j < L.length; j+)if (L.elemmin > L.elemj)min = j;temp = L.elemi;L.elemi = L.elemmin;L.elemmin = temp;min = i + 1;return OK;/降序Status Decendi

14、ng_Sq(Sqlist L)int i, j, max = 0, temp;for (i = 0; i < L.length - 1; i+)for (j = i; j < L.length; j+)if (L.elemmax< L.elemj)max = j;temp = L.elemi;L.elemi = L.elemmax;L.elemmax = temp;max = i + 1;return OK;Sqlist.h:#include"stdio.h"#include"stdlib.h"#define LIST_INIT_SIZ

15、E 10#define LISTINCREMENT 2#define OK 1#define OVERFLOW 0#define ERROR 0typedef int Status;typedef int ElemType;typedef struct ElemType *elem;int length;int listsize;Sqlist;int Print_Sq(Sqlist &L);/輸出順序表；Status Initlist_Sq(Sqlist &L);/創(chuàng)建鏈表；Status ListInsert_Sq(Sqlist &L, int i, ElemType

16、e);/在i處插入e；Status listDelete_Sq(Sqlist &L, int i, ElemType &e);/刪除i位置上的元素返回到e；Status listFine1_Sq(Sqlist L, int &locat, ElemType e);/順序查找Status listFine2_Sq(Sqlist L, int &locat, ElemType e);/折半查找Status Ascending_Sq(Sqlist L);/升序Status Decending_Sq(Sqlist L);/降序Ø 運(yùn)行結(jié)果：B. 鏈?zhǔn)絻?chǔ)存：&#

17、216; 代碼部分：Mian.cpp#include"LinkList.h"int main()LinkList L = NULL;int elect = 0, locat;ElemType e;CreatList_L(L);do elect = Menu(L);switch (elect)case 0:break;case 1:/插入printf("請(qǐng)輸入你想添加的位置和數(shù)字（用空格隔開）：");scanf_s("%d%d", &locat, &e);ListInsert_L(L, locat, e);break;c

18、ase 2:printf("請(qǐng)輸入你想刪除數(shù)字的位置：");scanf_s("%d", &locat);ListDelete_L(L, locat, e);printf("the delete number is %dn", e);break;case 3:/查找printf("請(qǐng)輸入你想查找的數(shù)字：");scanf_s("%d", &e);if (LocatElem_L(L, locat, e)printf("%d在表中的位置是%dn", e, locat)

19、; break;case 4:/返回某位置的數(shù)值printf("請(qǐng)輸入你想返回?cái)?shù)值的位置：");scanf_s("%d", &locat);if (GetElem_L(L, locat, e)printf("第%d位置的值是%dn", locat, e);break;case 5:Ascending_L(L);break;case 6:Decending_L(L);break;default:printf("輸入錯(cuò)誤!/n"); while (elect != 0);system("pause&q

20、uot;);return 0;LinkList.cpp#include"LinkList.h"/輸出菜單int Menu(LinkList L)int i = 0;printf("現(xiàn)有鏈?zhǔn)奖恚簄");Printf_L(L);printf("n");i = 0;printf("*n");printf("*1.插入*n");printf("*2.刪除*n");printf("*3.輸入數(shù)字返回位置*n");printf("*4.輸入位置返回?cái)?shù)值*n&

21、quot;);printf("*5.排升序*n");printf("*6.排降序*n");printf("*0.退出*n");printf("*n");printf("請(qǐng)輸入你的選擇：");scanf_s("%d", &i);return i;/創(chuàng)建鏈表void CreatList_L(LinkList &L)LNode *p = NULL, *pr = NULL;ElemType data;int i, length;L = (LinkList)malloc

22、(sizeof(LNode);if (L = NULL) exit(0);L->next = NULL;pr = L;printf("請(qǐng)輸入鏈表長(zhǎng)度：");scanf_s("%d", &length);for (i = 0; i < length; +i)printf("請(qǐng)輸入第%d個(gè)數(shù)據(jù)：", i + 1);p = (LinkList)malloc(sizeof(LNode);if (p = NULL) exit(0);scanf_s("%d", &data);p->data =

23、 data;pr->next = p;p->next = NULL;pr = pr->next;return;/輸出鏈表void Printf_L(LinkList L)LNode *p = L->next;while (p)printf("%dt", p->data);p = p->next;return;/插入元素到鏈表Status ListInsert_L(LinkList &L, int i, ElemType e)LNode *p = L, *pr = NULL;int j = 0;while (p&&j

24、<i - 1)p = p->next;+j;if (!p | j>i - 1) exit(ERROR);pr = (LNode *)malloc(sizeof(LNode);pr->data = e;pr->next = p->next;p->next = pr;return OK;/刪除鏈表中的元素Status ListDelete_L(LinkList &L, int i, ElemType e)LNode *p = L, *pr = NULL;int j = 0;while (p&&j<i - 1)p = p->

25、;next;+j;if (!p | j>i - 1) exit(ERROR);pr = p->next;p->next = pr->next;return OK;/查找元素e并返回位置i。Status LocatElem_L(LinkList L, int &i, ElemType e)LNode *p = L->next;int j = 1;while (p && (p->data != e)p = p->next;+j;if (!p | (p->data != e)printf("鏈表中不存在%dn"

26、;, e);return ERROR;i = j;return OK;/返回元素e的位置。Status GetElem_L(LinkList L, int i, ElemType &e)LNode *p = L->next;int j = 0;while (p&&j<i - 1)p = p->next;+j;if (!p | j>i - 1)printf("此鏈表沒有第%d位n", i);return ERROR;e = p->data;return OK;/升序。Status Ascending_L(LinkList

27、&L)LNode *p = L->next, *pr = NULL;ElemType temp;int sign=1;while (sign)sign = 0;while (p->next != NULL)pr = p->next;if (p->data > pr->data)temp = p->data;p->data = pr->data;pr->data = temp;sign = 1;p = p->next;p = L->next;return OK;/降序。Status Decending_L(LinkL

28、ist &L)LNode *p = L->next, *pr = NULL;ElemType temp;int sign = 1;while (sign)sign = 0;while (p->next != NULL)pr = p->next;if (p->data < pr->data)temp = p->data;p->data = pr->data;pr->data = temp;sign = 1;p = p->next;p = L->next;return OK;Linklist.h#include<

29、stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0typedef int Status;typedef int ElemType;typedef struct LNode ElemType data;struct LNode * next;LNode, *LinkList;int Menu(LinkList L);/輸出菜單。void CreatList_L(LinkList &L);/創(chuàng)建鏈表。void Printf_L(LinkList L);/輸出鏈表。Status ListInsert_L(LinkLis

30、t &L, int i, ElemType e);/在i位置插入e元素。Status ListDelete_L(LinkList &L, int i, ElemType e);/刪除i位置的元素并返回e。Status LocatElem_L(LinkList L, int &i, ElemType e);/查找元素e并返回位置i。Status GetElem_L(LinkList L, int i, ElemType &e);/返回元素e的位置。Status Ascending_L(LinkList &L);/升序Status Decending_L(L

31、inkList &L);/降序。#pragma onceØ 運(yùn)行結(jié)果：（2）建立一個(gè)按元素遞增有序的單鏈表L，并編寫程序?qū)崿F(xiàn)：a）將x插入其中后仍保持L的有序性；b）將數(shù)據(jù)值介于min和max之間的結(jié)點(diǎn)刪除，并保持L的有序性；c）將單鏈表L逆置并輸出；Ø 代碼部分：Mian.cpp#include"LinkList.h"int main ()LinkList L;int elect, e,min,max;listCreat_L(L);do printf("現(xiàn)有鏈表：");Printf_L(L);elect = menu();s

32、witch (elect)case 0:break;case 1:printf("請(qǐng)輸入你想插入的數(shù)字：");scanf_s("%d",&e);ListInsert_L(L, e);break;case 2:printf("請(qǐng)輸入min和max(用空格隔開)：");scanf_s("%d%d", &min, &max);ListDelete_L(L, min, max);break;case 3:Reverse_L(L);break;default:printf("輸入錯(cuò)誤！n&q

33、uot;);break; while (elect);system("pause");return 0;LinkList.cpp#include"LinkList.h"/輸出菜單int menu()int elect;printf("n*n");printf("*0.退出*n");printf("*1.插入元素*n");printf("*2.刪除介于min和max之間的結(jié)點(diǎn)*n");printf("*3.逆置鏈表*n");printf("*n&q

34、uot;);printf("請(qǐng)輸入你的選擇");scanf_s("%d",&elect);return elect;/創(chuàng)建鏈表Status listCreat_L(LinkList &L)LNode *p = NULL, *pr = NULL;int n,i=1,data;L = (LinkList)malloc(sizeof(LNode);pr = L;printf("請(qǐng)輸入想創(chuàng)建的單鏈表的長(zhǎng)度：");scanf_s("%d", &n);for (; i <= n; +i)p = (

35、LNode *)malloc(sizeof(LNode);if (!p) exit(ERROR);printf("請(qǐng)輸入第%d個(gè)數(shù)據(jù)：",i);scanf_s("%d", &data);p->data = data;pr->next = p;pr = pr->next;p->next = NULL;return OK;/輸出鏈表void Printf_L(LinkList L)LNode *p = L->next;while (p)printf("%5d", p->data);p = p-&

36、gt;next;return;/插入元素Status ListInsert_L(LinkList &L, ElemType e)LNode *p = L->next,*pr;while (p->next&&p->next->data < e)p = p->next;pr = (LNode *)malloc(sizeof(LNode);pr->data = e;pr->next = p->next;p->next = pr;return OK;/刪除介于min和max之間的元素Status ListDelete_

37、L(LinkList &L, ElemType min, ElemType max)LNode *p = L->next, *pr;while (p)if (p->next&&(p->next->data > min && p->next->data < max)pr = p->next;p->next = pr->next;free(pr);elsep = p->next;return OK;/置逆Status Reverse_L(LinkList &L)LinkList

38、La;LNode *p = NULL, *pr = L->next;La = (LinkList)malloc(sizeof(LNode);if (!La) exit(ERROR);La->next = NULL;while (pr)p = (LNode *)malloc(sizeof(LNode);if (!p) exit(ERROR);p->data = pr->data;p->next = La->next;La->next = p;pr = pr->next;L = La;return OK;LinkList.h#include<s

39、tdio.h>#include<stdlib.h>#define OK 1#define ERROR 0typedef int Status;typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next;LNode, *LinkList;int menu();Status listCreat_L(LinkList &L);Status ListInsert_L(LinkList &L, ElemType e);void Printf_L(LinkList L);Status

40、 ListDelete_L(LinkList &L, ElemType min, ElemType max);Status Reverse_L(LinkList &L);Ø 運(yùn)行結(jié)果：（3）編程實(shí)現(xiàn)將兩個(gè)按元素遞增有序的單鏈表合并為一個(gè)新的按元素遞增的單鏈表。Ø 代碼部分：Mian.cpp:#include"LinkList.h"int main()LinkList La,Lb, Lc;printf("第一個(gè)鏈表n");CreatList_L(La);printf("第二個(gè)鏈表n");CreatLi

41、st_L(Lb);CombinList_L(La, Lb, Lc); printf("合并后的鏈表為：n");PrintList_L(Lc);system("pause");return OK;LinkList.cpp:#include"LinkList.h"/創(chuàng)建鏈表Status CreatList_L(LinkList &L)LNode *p = NULL, *pr = NULL;int n, i=0;ElemType data;L = (LinkList)malloc(sizeof(LNode);if (!L) exit

42、(ERROR);pr = L;printf(" ->請(qǐng)輸入創(chuàng)建鏈表的長(zhǎng)度：");scanf_s("%d", &n);for (; n > 0; -n)p = (LNode *)malloc(sizeof(LNode);if (!p) exit(ERROR);printf("請(qǐng)輸入第%d個(gè)數(shù)據(jù)：",+i);scanf_s("%d", &data);p->data = data;pr->next = p;p->next = NULL;pr = pr->next;return OK;/輸出鏈表Status PrintList_L(LinkList L)LNode *p = L->next;while (p)printf("%5d", p->data);p = p->next;printf("n");return OK;/合并鏈表Status