数据结构实验二线性表及其实现

实验编号：2 四川师大数据结构实验报告 2016 年 9 月 30 日实验二 线性表及其实现_一实验目的及要求（1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点。（2） 通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用。（3） 掌握循环链表和双链表的定义和构造方法。二实验内容（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除、查找（顺序查找、折半查找） 、排序等） ，并设计一个菜单调用线性表的基本操作。（2） 建立一个按元素递增有序的单链表 L，并编写程序实现：a） 将x插入其中后仍保持L的有序性；b） 将数据值介于min和max之间的结点删除，并保持L的有序性；c） 将单链表L 逆置并输出；（3） 编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。注：（1）为必做题， （2）（3）选做。三主要仪器设备及软件（1） PC 机（2） Dev C+ ,Visual C+, VS2010 等四实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除、查找（顺序查找、折半查找） 、排序等） ，并设计一个菜单调用线性表的基本操作。A.顺序储存： 代码部分：Main.cpp:#include“Sqlist.h“int main()Sqlist L;int e = 0, number=0,locat =0,elect=0;int ret;/存放返回值printf(“请先创建一个含有 10 个整型元素的顺序表！n“);Initlist_Sq(L);do elect=Print_Sq(L);switch (elect)case 0:break;case 1:/插入printf(“请输入你想添加的位置和数字（用空格隔开）：“);scanf_s(“%d%d“,ListInsert_Sq(L, number, locat);break;case 2:/删除printf(“请输入你想删除数字的位置：“);scanf_s(“%d“, listDelete_Sq(L, locat, e);printf(“the delete number is %dn“, e);break;case 3:/顺序查找printf(“请输入你想查找的数字：“);scanf_s(“%d“, ret=listFine1_Sq(L, locat, number);if(ret)printf(“%d 在表中的位置是%dn“, number, locat);break;case 4:/折半查找printf(“请输入你想查找的数字：“);scanf_s(“%d“, ret=listFine2_Sq(L, locat, number);if(ret)printf(“%d 在表中的位置是%dn“, number, locat);break;case 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 printf(“现有线性表：n“);for (; i L.length + 1)return ERROR;if (L.length = L.listsize)newelem = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType);if (!newelem) exit(OVERFLOW);L.elem = newelem;L.listsize += LISTINCREMENT;q = for (p = p = q; -p)*(p + 1) = *p;*q = e;+L.length;return OK;/删除第 i 个位置的元素并返回 eStatus listDelete_Sq(Sqlist if (iL.length)return ERROR;p = e = *p;for (q = i - 1; q L.elemmid)low = mid+1;else if (e L.elemj)min = j;temp = L.elemi;L.elemi = L.elemmin;L.elemmin = temp;min = i + 1;return OK;/降序Status Decending_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_SIZE 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 /输出顺序表；Status Initlist_Sq(Sqlist /创建链表；Status ListInsert_Sq(Sqlist /在 i 处插入 e；Status listDelete_Sq(Sqlist /删除 i 位置上的元素返回到 e；Status listFine1_Sq(Sqlist L, int /顺序查找Status listFine2_Sq(Sqlist L, int /折半查找S