线性表的存储结构定义及基本操作(实验报告)-2011600724-何俊林.

1、姓名：何俊林学号： 201160072411软件工程 1线性表的存储结构定义及基本操作（实验报告）一、 实验目的：. 掌握线性表的逻辑特征. 掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算. 熟练掌握线性表的链式存储结构定义及基本操作. 理解循环链表和双链表的特点和基本运算. 加深对顺序存储数据结构的理解和链式存储数据结构的理解,逐步培养解决实际问题的编程能力二、 实验内容(一) 基本实验内容 (顺序表 )：建立顺序表 ,完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁,置空表、求表长、查找元素、判线性表是否为空;1. 问题描述：. 利用顺序表 ,设计一组输入数据( 假定为一

2、组整数 ), 能够对顺序表进行如下操作：. 创建一个新的顺序表,实现动态空间分配的初始化;. 根据顺序表结点的位置插入一个新结点 ( 位置插入 ), 也可以根据给定的值进行插入 ( 值插入 ), 形成有序顺序表 ;. 根据顺序表结点的位置删除一个结点 ( 位置删除 ),也可以根据给定的值删除对应的第一个结点 ,或者删除指定值的所有结点 (值删除 );. 利用最少的空间实现顺序表元素的逆转;. 实现顺序表的各个元素的输出;. 彻底销毁顺序线性表,回收所分配的空间;. 对顺序线性表的所有元素删除,置为空表 ;. 返回其数据元素个数;. 按序号查找 ,根据顺序表的特点 ,可以随机存取 ,直接可以定位

3、于第 i 个结点 ,查找该元素的值 ,对查找结果进行返回 ;. 按值查找 ,根据给定数据元素的值,只能顺序比较 ,查找该元素的位置,对查找结果进行返回 ;. 判断顺序表中是否有元素存在,对判断结果进行返回;. 编写主程序 ,实现对各不同的算法调用。2. 实现要求对顺序表的各项操作一定要编写成为C(C+) 语言函数 ,组合成模块化的形式,每个算法的实现要从时间复杂度和空间复杂度上进行评价;. “初始化算法”的操作结果：构造一个空的顺序线性表。对顺序表的空间进行动态管理,实现动态分配、回收和增加存储空间 ;. “位置插入算法”的初始条件：顺序线性表L 已存在 ,给定的元素位置为i, 且 1iLis

4、tLength(L)+1; 操作结果：在 L 中第 i 个位置之前插入新的数据元素e,L的长度加 1;. “位置删除算法”的初始条件：顺序线性表L 已存在 ,1 iListLength(L);操作结果：删除 L 的第 i 个数据元素 ,并用 e 返回其值 ,L 的长度减 1;. “逆转算法”的初始条件：顺序线性表L已存在 ;. 操作结果：依次对 L 的每个数据元素进行交换 ,为了使用最少的额外空间,对顺序表的元素进行交换 ;. “输出算法”的初始条件：顺序线性表L 已存在 ; 操作结果：依次对L 的每个数据元素进行输出 ;. “销毁算法”初始条件：顺序线性表L 已存在 ;操作结果：销毁顺序线性

5、表L;. “置空表算法”初始条件：顺序线性表L 已存在 ; 操作结果：将 L 重置为空表 ;. “求表长算法”初始条件：顺序线性表L 已存在 ; 操作结果：返回L 中数据元素个数 ;. “按序号查找算法”初始条件：顺序线性表L 已存在 ,元素位置为 i, 且 1 iListLength(L) 操作结果：返回 L 中第 i个数据元素的值. “按值查找算法”初始条件：顺序线性表L 已存在 ,元素值为 e; 操作结果：返回 L 中数据元素值为 e 的元素位置 ;. “判表空算法”初始条件：顺序线性表L 已存在 ;. 操作结果：若L 为空表 ,则返回 TRUE,否则返回FALSE;分析：修改输入数据,

6、预期输出并验证输出的结果,加深对有关算法的理解。(二) 基本实验内容 (单链表 )：建立单链表 ,完成链表 ( 带表头结点 )的基本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。1. 问题描述：利用线性表的链式存储结构 ,设计一组输入数据 (假定为一组整数 ),能够对单链表进行如下操作：.初始化一个带表头结点的空链表;. 创建一个单链表是从无到有地建立起一个链表,即一个一个地输入各结点数据起前后相互链接的关系。又分为逆位序(插在表头 )输入 n 个元素的值和正位序尾) 输入

7、 n 个元素的值 ;,并建立( 插在表. 插入结点可以根据给定位置进行插入 ( 位置插入 ),也可以根据结点的值插入到已知的链表中 (值插入 ), 且保持结点的数据按原来的递增次序排列 ,形成有序链表。. 删除结点可以根据给定位置进行删除( 位置删除 ),也可以把链表中查找结点的值为搜索对象的结点全部删除( 值删除 );. 输出单链表的内容是将链表中各结点的数据依次显示,直到链表尾结点 ;. 编写主程序 ,实现对各不同的算法调用。其它的操作算法描述略。2. 实现要求：对链表的各项操作一定要编写成为C(C+)语言函数 ,组合成模块化的形式,还要针对每个算法的 实现从时间复杂度和空间复杂度上进行评

8、价。. “初始化算法”的操作结果：构造一个空的线性表L, 产生头结点 ,并使 L 指向此头结点;. “建立链表算法”初始条件：空链存在; 操作结果：选择逆位序或正位序的方法,建立一个单链表 ,并且返回完成的结果 ;. “链表 ( 位置 )插入算法”初始条件：已知单链表L 存在 ; 操作结果：在带头结点的单链线性表 L 中第 i 个位置之前插入元素e;. “链表 ( 位置 )删除算法”初始条件：已知单链表L 存在;. 操作结果：在带头结点的单链线性表L 中 ,删除第 i 个元素 ,并由 e 返回其值 ;. “输出算法”初始条件：链表L 已存在 ;操作结果：依次输出链表的各个结点的值;( 三) 扩

9、展实验内容 (顺序表 )查前驱元素、查后继元素、顺序表合并等.1. 问题描述：. 根据给定元素的值 ,求出前驱元素 ;. 根据给定元素的值 ,求出后继元素 ;. 对已建好的两个顺序表进行合并操作,若原线性表中元素非递减有序排列,要求合并后的结果还是有序 (有序合并 ); 对于原顺序表中元素无序排列的合并只是完成A=A B (无序合并 ), 要求同样的数据元素只出现一次。. 修改主程序 ,实现对各不同的算法调用。2. 实现要求：. “查前驱元素算法”初始条件：顺序线性表L 已存在 ;操作结果：若数据元素存在且不是第一个 ,则返回前驱 ,否则操作失败 ;. “查后继元素算法”初始条件：顺序线性表L

10、 已存在 ;操作结果：若数据元素存在且不是最后一个 ,则返回后继 ,否则操作失败 ;. “无序合并算法”的初始条件：已知线性表La 和 Lb;. 操作结果：将所有在线性表Lb 中但不在 La 中的数据元素插入到 La 中 ;. “有序合并算法”的初始条件：已知线性表La 和 Lb 中的数据元素按值非递减排列;操作结果：归并 La 和 Lb 得到新的线性表Lc,Lc 的数据元素也按值非递减排列;(四) 扩展实验内容 (链表 )1. 问题描述：. 求前驱结点是根据给定结点的值,在单链表中搜索其当前结点的后继结点值为给定的值,将当前结点返回 ;. 求后继结点是根据给定结点的值,在单链表中搜索其当前结

11、点的值为给定的值,将后继结点返回 ;. 两个有序链表的合并是分别将两个单链表的结点依次插入到第3 个单链表中 ,继续保持结点有序 ;2. 实现要求：. “求前驱算法”初始条件：线性表L 已存在 ;. 操作结果：若cur_e 是 L 的数据元素 ,且不是第一个 ,则用 pre_e 返回它的前驱 ;. “求后继算法”初始条件：线性表L 已存在 ;. 操作结果：若cur_e 是 L 的数据元素 ,且不是最后一个 ,则用 next_e 返回它的后继 ;. “两个有序链表的合并算法”初始条件：线性表单链线性表La 和 Lb 的元素按值非递减排列 ; 操作结果：归并La 和 Lb 得到新的单链表。三、 实

12、验环境和实验步骤实验环境：利用CodeBlocks10.05 集成开发环境进行本实验的操作。实验步骤顺序表的定义与操作：1. 启动 CodeBlocks10.5;2. 按“ Create a new project ”, 通过” file”, 按“ C/C+ source ”,选择” c”,然后 GO.储存文件“ D:c 语言 顺序表 .c “，3. 进行编代码。4、编好之后，搞ctrl+shift+F9进行编译。然后按ctrl+F10.5. 如果编译出问题，然后进行调试。实验步骤链表的定义与操作：1. 启动 CodeBlocks10.5;2. 按“ Create a new project

13、”, 通过” file”, 按“ C/C+ source ”,选择” c”,然后 GO.储存文件“ D:c 语言 单链表 .c “，3. 进行编代码。4、编好之后，搞ctrl+shift+F9进行编译。然后按ctrl+F10.5. 如果编译出问题，然后进行调试。四、 实验分析顺序表代码如下：#include #include stdlib.h#include #define LIST_INIT_SIZE 100#define ok 1#define ERROR 0#define OVERFLOW -1#define Num 3typedef int DataType;typedef int S

14、tatus;typedef structDataType *elem;int Length;int Listsize;SeqList;SeqList L;Status InitSeqList(SeqList *L)L-elem=(DataType*)malloc(LIST_INIT_SIZE*sizeof(DataType);if(!L-elem)exit(OVERFLOW);L-Length=0;L-Listsize=LIST_INIT_SIZE;return ok;Status InsertSeqList(SeqList *L,int i,DataType e)DataType *q,*p

15、;if(iL-Length+1)return ERROR;elseif(L-Length=L-Listsize)printf(TheSeqList is full!);return ERROR;elseq=L-elem+i-1;for(p=L-elem+L-Length-1;p=q;-p)*(p+1)=*p;*q=e;+L-Length;return ok;int DeleteSeqList(SeqList *L,int i)int j;if(iL-Length)printf(the i number is not exist!);return ERROR;elsefor(j=i-1;jLen

16、gth;j+)*(L-elem+j)=*(L-elem+j+1);L-Length-;return ok;/void SearchSeqList(SeqList *L, DataType x)void SearchSeqList(SeqList *L,int x)int j=0;while (jLength&*(L-elem+j)!=x)j+;if(jL-Length)printf(error);elseprintf(运行结果 );printf(%d,j+1);void PrintfSeqList(SeqList *L)Printf( 运行结果 :);int i;for (i=0;iLengt

17、h;i+)printf(%d,*(L-elem+i);void LenSeqList(SeqList *L)int i=0,*j;for(j=L-elem;iLength;j+)i+;printf(n元素个数为： %d,i);void PriorSeqLement(SeqList *L,int i)int *j;if(iL-Length)printf(输入有误 );else if(i=1)printf(无前驱 );else j=L-elem+i-2;printf(运行结果： );printf(%d,*j);Status NextSeqElement(SeqList *L,int i)int*j

18、;if(iLength)printf(输入有误 );else if(i=1)printf(无后继 );else j=L-elem+i;printf(运行结果： );printf(%d,*j);return ok;void ListSeqEmpty(SeqList *L)if(L-Length=0)printf(书序表为空 );else printf(顺序表非空 );Status ChangSeqList(SeqList *L)int i,j,q;for(i=0,j=L-Length-1;iLength/2;i+,j-)q=*(L-elem+i);*(L-elem+i)=*(L-elem+j);

19、*(L-elem+j)+q;return ok;Status ClearSeqList(SeqList *L)L-Length=0;return ok;void DestorySeqList(SeqList *L)free(L);L-Length=0;L-Listsize=0;void main()SeqList *LA=&L;int i,e,j,x,k,m,*p,q=0;InitSeqList(&L);printf(输入元素： );for(p=LA-elem;qLength+;PrintfSeqList(&L);printf(n输入要插入元素的位置和元素：);scanf(%d,%d,&i,&

20、e);InsertSeqList(LA,i,e);PrintfSeqList(&L);printf(n输入要删除元素的位置：);scanf(%d,&j);DeleteSeqList(&L,j);PrintfSeqList(&L);printf(n输入要查找的值：);scanf(%d,&x);SearchSeqList(&L,x);PrintfSeqList(&L);printf(n输入元素求其前驱：);scanf(%d,&k);PriorSeqList(&L,k);PrintfSeqList(&L);printf(n输入元素求其后继：);scanf(%d,&m);NextSeqList(&L,

21、m);printf(n求表长： );LenSeqList(&L);/判断表是否为空printf(n判断表是否为空：n);ListSeqEmpty(&L);printf(n);printf( 逆转 :n);ChangSeqList(&L);PrintfSeqList(&L);printf(n);printf( 置空表 :n);ClearSeqList(&L);printf(n);printf( 销毁： );DestorySeqList(&L);单链表代码：/ List.h#include using namespace std;typedef int ElemType ;typedef stru

22、ct studentElemType n;struct student *next;Student,*SListLink;class SListpublic:SList();/建立一个空链表 *void CreateSList();/建立链表 *void ClearSList();/将链表重置为空链表 *ElemType SListLength();/返回链表中的长度 *bool SListEmpty();/判断链表是否为空链表 *ElemType GetElem();/返回链表的一个元素 *void SortElem();/对链表排序void SListInsert();/插入一个元素 *v

23、oid SListDelete();/删除一个元素 *bool SlistDeleteSame();/删除相同的元素void ShowSList();/显示一个链表 *void FileSave();/写入文件void FileRead();/从文件打开void FileDelete();/从文件删除void FileCheck();/查看文件内容SList();/销毁链表private:SListLink head;SListLink p;SListLink q;SListLink temp;int slistlength;SList:SList()/建立一个空链表head=p=q=temp

24、=NULL;slistlength=0;void SList:CreateSList()/建立链表if (head=NULL)ElemType m;cout请输入一个数字：(0, 负数表示结束输入)m;if (m0)head=q=p=temp=new Student;q-n=m;+slistlength;while (m!=0&m=0)cout请输入一个数字：m;if (m!=0&m=0)p=new Student;p-n=m;+slistlength;q-next=p;q=p;p-next=NULL;cout链表创建成功 endl;/没有输出？elsehead=p=q=NULL;elseco

25、ut你已经创建过新链表了endl;int SList:SListLength()/返回链表中的长度cout链表中的元素个数是：slistlengthendl;return slistlength;ElemType SList:GetElem()/返回链表对应序号的一个元素if (head!=NULL)ElemType m;cout请输入要返回的数在链表中的序号m;if (m=0)if (slistlength=m)int indx=1;p=head;while(1)if (m=indx)cout链表返回你查找的数：nn;p=p-next;+indx;if (m=indx)cout链表返回你查找

26、的数：nn;elsecout序号超出链表范围endl;return -1;elsecout不允许非法输入 endl;return -1;elsecout此链表是空链表 endl;return -1;bool SList:SListEmpty()/判断链表是否为空链表if (head!=NULL)cout此链表不是空链表endl;return false;elsecout此链表是空链表 endl;return true;bool SList:SlistDeleteSame()/删除链表中相同元素ElemType m;cout删除链表中相同元素的节点，请输入一个要删除的数：m;if (m=0)if

27、 (head!=NULL)return true;elsecout这是一个空链表 endl;return false;elsecout不允许非法输入 next)temp=p;for (q=p-next;q!=NULL;q=q-next)if (q-n=temp-n)temp=q;if (temp!=p)ElemType t=p-n;p-n=temp-n;temp-n=t;cout排序成功 endl;elsecout此链表是空链表 ,不能进行此操作next=NULL)delete head;head=NULL;elsep=head-next;while (q!=NULL&p!=NULL)q=p-

28、next;head-next=q;delete p;p=q;q=p-next;delete head;head=NULL;slistlength=0;cout重置链表成功 endl;elsecout此链表是空链表 endl;void SList:ShowSList()/显示一个链表if (head!=NULL)p=head;cout显示链表所有元素：docoutnnext; while (p!=NULL);endl;cout此链表共有元素:slistlength个endl;elsecout此链表是空链表endl;void SList:SListInsert()/头插法插入一个元素ElemTyp

29、e m;cout请输入要插入的数字：m;if (m0)if (head!=NULL)p=new Student;p-n=m;+slistlength;p-next=head;head=p;elsehead=new Student;head-n=m;+slistlength;head-next=NULL;cout插入数据成功 endl;return;void SList:SListDelete()/删除一个元素ElemType m;bool flig=true;cout请输入要删除的数字：m;if (m0)if (head!=NULL)if (head-n=m)/头结点指向的值符合删除要求if

30、(head-next=NULL)/delete head;head=NULL;-slistlength;删除头结点，且头结点没有后继元素时coutreturn;删除数据成功 next;head-next=NULL;delete head;head=NULL;-slistlength;head=p;cout删除数据成功 n=m)if (p-next=NULL)/要删除的是链表的最后一个元素q=head;while (q-next-next!=NULL)/寻找出倒数第二个节点q=q-next;q-next=NULL;delete p;p=NULL;-slistlength;cout删除数据成功 n

31、ext-n!=m)q=q-next;q-next=p-next;p-next=NULL;delete p;p=NULL;-slistlength;cout删除数据成功 next;while (p!=NULL);if (flig)cout你输入的数据链表中不存在endl;return;elsecout此链表是空链表，不能进行此操作endl;return;void SList:FileSave()ofstream out;out.open( 单向链表练习 .txt);if (!out.is_open()cerr打开文件出错 endl;return;elseif (head=NULL)cerr链表为

32、空无数据可以保存endl;elsep=head;dooutnnext; while (p!=NULL);cout文件保存成功 endl;out.close();void SList:FileRead()ifstream in;in.open( 单向链表练习 .txt);if (!in.is_open()cerr打开文件出错 endl;return;elseif (head!=NULL)cout链表不为空，不能进行此操作n1).eof()delete p;temp-next=NULL;break;q-n=n1;+slistlength;p=new Student;q-next=p;temp=q;

33、q=p;cout文件读取成功 endl;in.close();void SList:FileDelete()ifstream in;in.open( 单向链表练习 .txt);if (!in.is_open()cerr文件不存在 endl;return;in.close();char a=del单向链表练习 .txt;ElemType choice;docout确认要删除文件吗？1= 是 0= 否 choice;system(cls); while (choice!=1&choice!=0); switch (choice)case 1: system(a);cout成功删除文件 endl;b

34、reak;case 0:cout放弃删除文件 endl;break;void SList:FileCheck()ifstream in;in.open( 单向链表练习 .txt);if (!in.is_open()cerr文件查看出错，请检查文件是否存在;return;ElemType n1;cout单向链表练习 .txt文件内容 :n1).eof()break;coutn1endl;SList:SList()/删销毁一个链表cout感谢使用 endl;void main_menu(ElemType &choice)bool judge=true;dosystem(cls);coutnttt链

35、表练习 -C+ 语言实现 endl;coutntt1.创建一个链表 n;couttt2.将链表置空 n;couttt3.返回链表长度 n;couttt4.判断链表是否为空链表 n;couttt5.返回链表的一个元素 n;couttt6.为链表插入一个元素 n;couttt7.为链表删除一个元素 n;couttt8.显示一个链表 n;couttt9.对链表进行排序 n;couttt10.将链表保存为文件 n;couttt11.从文件中打开链表 n;couttt12.删除文件及信息 n;couttt13.查看文件信息 n;couttt0.退出 nendl;coutchoice;for (int i=0;i!=14;+i)if (choice=i)judge=false; while (judge);/main.cpp#include #include List.husing namespac