數(shù)據(jù)結構_實驗二_線性表及其實現(xiàn)

1、實驗編號：2 四川師大數(shù)據(jù)結構實驗報告 2016年9月30日實驗二 線性表及其實現(xiàn)_一 實驗目的及要求（1） 熟悉線性表的基本運算在兩種存儲結構（順序結構和鏈式結構）上的實現(xiàn)，以線性表的各種操作（建立、插入、刪除等）的實現(xiàn)為實驗重點。（2） 通過本次實驗幫助學生加深對順序表、鏈表的理解，并加以應用。（3） 掌握循環(huán)鏈表和雙鏈表的定義和構造方法。二 實驗內容（1） 編程實現(xiàn)線性表兩種存儲結構（順序存儲、鏈式存儲）中的基本操作的實現(xiàn)（線性表的創(chuàng)建、插入、刪除、查找（順序查找、折半查找）、排序等），并設計一個菜單調用線性表的基本操作。（2） 建立一個按元素遞增有序的單鏈表L，并編寫程序實現(xiàn)：a） 將

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

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

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

5、quot;, &number);ret=listFine1_Sq(L, locat, number);if(ret)printf("%d在表中的位置是%dn", number, locat);break; case 4:/折半查找 printf("請輸入你想查找的數(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("輸入錯誤!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("請輸入你的選擇：");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、"請輸入第%d個數(shù)字：", i + 1);scanf_s("%d", &number);L.elemi = number;L.length+;return OK;/在線性表中的第i個位置插入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個位置的元素并返回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);/降序Ø 運行結果：B. 鏈式儲存：&#

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("請輸入你想添加的位置和數(shù)字（用空格隔開）：");scanf_s("%d%d", &locat, &e);ListInsert_L(L, locat, e);break;c

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

19、; break;case 4:/返回某位置的數(shù)值printf("請輸入你想返回數(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("輸入錯誤!/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)有鏈式表：n");Printf_L(L);printf("n");i = 0;printf("*n");printf("*1.插入*n");printf("*2.刪除*n");printf("*3.輸入數(shù)字返回位置*n");printf("*4.輸入位置返回數(shù)值*n&

21、quot;);printf("*5.排升序*n");printf("*6.排降序*n");printf("*0.退出*n");printf("*n");printf("請輸入你的選擇：");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("請輸入鏈表長度：");scanf_s("%d", &length);for (i = 0; i < length; +i)printf("請輸入第%d個數(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Ø 運行結果：（2）建立一個按元素遞增有序的單鏈表L，并編寫程序實現(xiàn)：a）將x插入其中后仍保持L的有序性；b）將數(shù)據(jù)值介于min和max之間的結點刪除，并保持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("請輸入你想插入的數(shù)字：");scanf_s("%d",&e);ListInsert_L(L, e);break;case 2:printf("請輸入min和max(用空格隔開)：");scanf_s("%d%d", &min, &max);ListDelete_L(L, min, max);break;case 3:Reverse_L(L);break;default:printf("輸入錯誤！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之間的結點*n");printf("*3.逆置鏈表*n");printf("*n&q

34、uot;);printf("請輸入你的選擇");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("請輸入想創(chuàng)建的單鏈表的長度：");scanf_s("%d", &n);for (; i <= n; +i)p = (

35、LNode *)malloc(sizeof(LNode);if (!p) exit(ERROR);printf("請輸入第%d個數(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);Ø 運行結果：（3）編程實現(xiàn)將兩個按元素遞增有序的單鏈表合并為一個新的按元素遞增的單鏈表。Ø 代碼部分：Mian.cpp:#include"LinkList.h"int main()LinkList La,Lb, Lc;printf("第一個鏈表n");CreatList_L(La);printf("第二個鏈表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(" ->請輸入創(chuàng)建鏈表的長度：");scanf_s("%d", &n);for (; n > 0; -n)p = (LNode *)malloc(sizeof(LNode);if (!p) exit(ERROR);printf("請輸入第%d個數(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