数据结构与算法 链表程序.rtf

《数据结构与算法 链表程序.rtf》由会员分享，可在线阅读，更多相关《数据结构与算法 链表程序.rtf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 数据结构与算法 -实验报告 姓名：朱丽 班级：电子 105 班 学号：2010021528 Tel：15948042225实验一：线性表的存储结构定义及基本操作实验一：线性表的存储结构定义及基本操作一、实验目的：一、实验目的：.掌握线性表的逻辑特征.掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算.熟练掌握线性表的链式存储结构定义及基本操作.加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：二、实验内容：（一）基本实验内容（顺序表）：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、销毁、置空表、求表长、

2、查找元素、判线性表是否为空;1问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：.创建一个新的顺序表，实现动态空间分配的初始化;.根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表;.根据顺序表结点的位置删除一个结点(位置删除);.彻底销毁顺序线性表，回收所分配的空间;.对顺序线性表的所有元素删除，置为空表;.返回顺序线性表数据元素个数;.按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第 i 个结点，查找该元素的值，对查找结果进行返回;.按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置

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

4、存在，1iListLength(L);操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1;.“销毁算法”初始条件：顺序线性表 L 已存在;操作结果：销毁顺序线性表 L;.“置空表算法”初始条件：顺序线性表 L 已存在;操作结果：将 L 重置为空表;.“求表长算法”初始条件：顺序线性表 L 已存在;操作结果：返回 L 中数据元素个数;.“按序号查找算法”初始条件：顺序线性表 L 已存在，元素位置为 i，且 1iListLength(L)操作结果：返回 L 中第 i 个数据元素的值;.“按值查找算法”初始条件：顺序线性表 L 已存在，元素值为 e;操作结果：返回 L 中

5、数据元素值为 e 的元素位置;.“判表空算法”初始条件：顺序线性表 L 已存在;操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE;分析:修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。(二）基本实验内容（链表）：二）基本实验内容（链表）：建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除和输出操作。1 问题描述：利用线性表的链式存储结构,设计一组输入数据（假定为一组整数），能够对单链表进行如下操作：.初始化一个带表头结点的空链表;.创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。.插入结点根据给定位

6、置进行插入（位置插入）。.删除结点根据给定位置进行删除（位置删除）。.输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点。.编写主程序，实现对各不同的算法调用。其它的操作算法描述略。2实现要求：对链表的各项操作一定要编写成为 C（C+）语言函数，组合成模块化的形式，还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价。.“初始化算法”的操作结果：构造一个空的线性表 L，产生头结点,并使 L 指向此头结点;.“建立链表算法”初始条件：空链存在;操作结果：选择逆位序或正位序的方法，建立一个单链表，并且返回完成的结果;.“链表（位置）插入算法”初始条件：已知单链表 L 存在;操作结果

7、：在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e;.“链表（位置）删除算法”初始条件：已知单链表 L 存在;操作结果：在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值;.“输出算法”初始条件：链表 L 已存在;操作结果：依次输出链表的各个结点的值;三：基本程序三：基本程序:（一）线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表）(1)文件 1：pubuse.h 是公共使用的常量定义和系统函数调用声明，以后每个实验中几乎都涉及到此文件。#include#include#include/*malloc()等*/#include/*INT_MAX 等*/#

8、include/*EOF(=Z 或 F6),NULL*/#include/*atoi()*/#include/*eof()*/#include/*floor(),ceil(),abs()*/#include/*exit()*/*函数结果状态代码*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1/*#define OVERFLOW-2 因为在 math.h 中已定义 OVERFLOW 的值为 3,故去掉此行*/typedef int Status;/*Status 是函数的类型,其值是函数结

9、果状态代码，如 OK 等*/typedef int Boolean;/*Boolean 是布尔类型,其值是 TRUE 或 FALSE*/(2)文件 2：seqlistDef.h 进行线性表的动态分配顺序存储结构的表示#define LIST_INIT_SIZE 10/*线性表存储空间的初始分配量*/#define LISTINCREMENT 2/*线性表存储空间的分配增量*/typedef structElemType*elem;/*存储空间基址*/int length;/*当前长度*/int listsize;/*当前分配的存储容量(以 sizeof(ElemType)为单位)*/SqLis

10、t;(3)文件 3：seqlistAlgo.h 进行线性表顺序存储结构的基本实验算法定义Status ListInit_Sq(SqList&L)/*算法 2.3*/*操作结果：构造一个空的顺序线性表*/L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/*存储分配失败*/L.length=0;/*空表长度为 0*/L.listsize=LIST_INIT_SIZE;/*初始存储容量*/return OK;Status ListInsert_Sq(SqList&L,int i,El

11、emType e)/*算法 2.4*/*初始条件：顺序线性表 L 已存在，1iListLength(L)+1*/*操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1*/ElemType*newbase,*q,*p;if(iL.length+1)/*i 值不合法*/return ERROR;if(L.length=L.listsize)/*当前存储空间已满,增加分配*/newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLO

12、W);/*存储分配失败*/L.elem=newbase;/*新基址*/L.listsize+=LISTINCREMENT;/*增加存储容量*/q=L.elem+i-1;/*q 为插入位置*/for(p=L.elem+L.length-1;p=q;-p)/*插入位置及之后的元素右移*/*(p+1)=*p;*q=e;/*插入 e*/+L.length;/*表长增 1*/return OK;Status ListDelete_Sq(SqList&L,int i,ElemType*e)/*算法 2.5*/*初始条件：顺序线性表 L 已存在，1iListLength(L)*/*操作结果：删除 L 的第

13、i 个数据元素，并用 e 返回其值，L 的长度减 1*/ElemType*p,*q;if(iL.length)/*i 值不合法*/return ERROR;p=L.elem+i-1;/*p 为被删除元素的位置*/*e=*p;/*被删除元素的值赋给 e*/q=L.elem+L.length-1;/*表尾元素的位置*/for(+p;p=q;+p)/*被删除元素之后的元素左移*/*(p-1)=*p;L.length-;/*表长减 1*/return OK;Status ListPrint_Sq(SqList L)/*初始条件：顺序线性表 L 已存在*/*操作结果：依次对 L 的数据元素输出*/int

14、 i;printf(n);for(i=0;iL.length;i+)printf(%d,L.elemi);return OK;/*Status ListDestroy_Sq(SqList L)/*初始条件：顺序线性表 L 已存在*/*操作结果：销毁顺序线性表 L*/*Free(L.elem);L.elem=NULL;L.length=0;L.listsize=0;return OK;*/Status ListClear_Sq(SqList L)/*初始条件：顺序线性表 L 已存在*/*操作结果：将顺序线性表 L 重置为空表*/L.length=0;return OK;Status ListEm

15、pty_Sq(SqList L)/*初始条件：顺序线性表 L 已存在*/*操作结果：若顺序线性表 L 为空表，则返回 TRUE,否则返回 FALSE*/if(L.length=0)return TRUE;/else/return FALSE;Status ListGetElem_Sq(SqList L,int i,ElemType&e)/*初始条件：顺序线性表 L 已存在,1iListLength(L)*/*操作结果：用 e 返回 L 中第 i 个数据元素的值*/if(iL.length)/*i 值不合法*/exit(ERROR);e=*(L.elem+i-1);return OK;/*还有一

16、些算法，请同学们自己补充完整*/(4)文件 4：seqlistUse.cpp 进行线性表顺序存储结构的基本算法验证#includepubuse.h/*实现通用常量的定义，常用系统函数的声明*/typedef int ElemType;/*实现一组整数的操作,将 int 型特定义为通用的 ElemType 类型名*/#includeseqlistDef.h/*采用线性表的动态分配顺序存储结构定义*/#includeseqlistAlgo.h/*采用顺序表的基本算法定义*/void main()SqList L;Status i;int j;ElemType t;/*首先一定要初始化顺序表*/i=

17、ListInit_Sq(L);if(i=1)/*创建空表 L 成功*/for(j=1;j=5;j+)/*在表 L 中插入 5 个元素，每个元素的值分别为 2，4，6，8，10*/i=ListInsert_Sq(L,j,2*j);ListPrint_Sq(L);/*输出表 L 的内容*/ListInsert_Sq(L,2,20);/*随机指定插入点位置，假设在第二个元素前插入新的元素，其值为 20*/ListPrint_Sq(L);/*检验一下插入的结果，输出表 L 的内容*/ListDelete_Sq(L,4,&t);/*随机指定删除点位置，假设对第四个元素进行删除*/ListPrint_Sq

18、(L);/*检验一下删除的结果，输出表 L 的内容*/printf(n The Deleted value is%d,t);/*检验一下删除点元素的值*/ListPrint_Sq(L);/*检验一下插入和删除后的结果，输出表 L 的内容*/system(pause);基本程序（二，链表）(1)文件 1：pubuse.h 是公共使用的常量定义和系统函数调用声明，以后每个实验中几乎都涉及到此文件。#include#include#include/*malloc()等*/#include/*INT_MAX 等*/#include/*EOF(=Z 或 F6),NULL*/#include/*atoi(

19、)*/#include/*eof()*/#include/*floor(),ceil(),abs()*/#include/*exit()*/*函数结果状态代码*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1/*#define OVERFLOW-2 因为在 math.h 中已定义 OVERFLOW 的值为 3,故去掉此行*/typedef int Status;/*Status 是函数的类型,其值是函数结果状态代码，如 OK 等*/typedef int Boolean;/*Boolean

20、 是布尔类型,其值是 TRUE 或 FALSE*/2 文件 linklistDef.h 是线性表的单链表存储结构的定义struct LNodeElemType data;struct LNode*next;typedef struct LNode*LinkList;/*另一种定义 LinkList 的方法*/3 文件 linklistAlgo.h 是单链表的基本算法描述/*以下的算法均是针对带表头结点的单链表*/Status ListInit_Link(LinkList&L)/*操作结果：构造一个空的线性表 L*/L=(LinkList)malloc(sizeof(struct LNode);

21、/*产生头结点,并使 L 指向此头结点*/if(!L)/*存储分配失败*/exit(OVERFLOW);L-next=NULL;/*指针域为空*/return OK;Status ListDestroy_Link(LinkList L)/*初始条件：线性表 L 已存在。*/*操作结果：销毁线性表 L*/LinkList q;while(L)q=L-next;free(L);L=q;return OK;Status ListClear_Link(LinkList L)/*不改变 L*/*初始条件：线性表 L 已存在。*/*操作结果：将 L 重置为空表*/LinkList p,q;p=L-next

22、;/*p 指向第一个结点*/while(p)/*没到表尾*/q=p-next;free(p);p=q;L-next=NULL;/*头结点指针域为空*/return OK;Status ListEmpty_Link(LinkList L)/*初始条件：线性表 L 已存在。*/*操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE*/if(L-next)/*非空*/return FALSE;elsereturn TRUE;int ListLength_Link(LinkList L)/*初始条件：线性表 L 已存在。*/*操作结果：返回 L 中数据元素个数*/int i=0;LinkL

23、ist p=L-next;/*p 指向第一个结点*/while(p)/*没到表尾*/i+;p=p-next;return i;Status GetElem_Link(LinkList L,int i,ElemType&e)/*算法 2.8*/*初始条件:L 为带头结点的单链表的头指针*/*操作结果：当第 i 个元素存在时,其值赋给 e 并返回 OK,否则返回 ERROR*/int j=1;/*j 为计数器*/LinkList p=L-next;/*p 指向第一个结点*/while(p&jnext;j+;if(!p|ji)/*第 i 个元素不存在*/return ERROR;e=p-data;/

24、*取第 i 个元素*/return OK;int LocateElem_Link(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)/*初始条件:线性表 L 已存在,compare()是数据元素判定函数(满足为 1,否则为0)*/*操作结果:返回 L 中第 1 个与 e 满足关系 compare()的数据元素的位序。*/*若这样的数据元素不存在,则返回值为 0*/int i=0;LinkList p=L-next;while(p)i+;if(compare(p-data,e)/*找到这样的数据元素*/return i;p=p-ne

25、xt;return 0;Status ListInsert_Link(LinkList L,int i,ElemType e)/*算法 2.9,不改变 L*/*在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e*/int j=0;LinkList p=L,s;while(p&jnext;j+;if(!p|ji-1)/*i 小于 1 或者大于表长*/return ERROR;s=(LinkList)malloc(sizeof(struct LNode);/*生成新结点*/s-data=e;/*插入 L 中*/s-next=p-next;p-next=s;return OK;Status

26、 ListDelete_Link(LinkList L,int i,ElemType&e)/*算法 2.10,不改变 L*/*在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值*/int j=0;LinkList p=L,q;while(p-next&jnext;j+;if(!p-next|ji-1)/*删除位置不合理*/return ERROR;q=p-next;/*删除并释放结点*/p-next=q-next;e=q-data;free(q);return OK;Status ListTraverse_Link(LinkList L)/*初始条件：线性表 L 已存在*/

27、*操作结果:依次对 L 的每个数据元素的值进行输出*/LinkList p=L-next;while(p)printf(%d,p-data);p=p-next;printf(n);return OK;void CreateList_Link(LinkList&L,int n)/*算法 2.11*/*逆位序(插在表头)输入 n 个元素的值，建立带表头结构的单链线性表 L*/int i;LinkList p;L=(LinkList)malloc(sizeof(struct LNode);L-next=NULL;/*先建立一个带头结点的单链表*/printf(请输入%d 个数据n,n);for(i=

28、n;i0;-i)p=(LinkList)malloc(sizeof(struct LNode);/*生成新结点*/scanf(%d,&p-data);/*输入元素值*/p-next=L-next;/*插入到表头*/L-next=p;4将测试数据和主函数新定义一个文件,如取名为:linlistUse.cpp./*linlistUse.cpp 主要实现算法 2.9、2.10、2.11、2.12 的程序*/#includepubuse.htypedef int ElemType;#includelinklistDef.h#includelinklistAlgo.hvoid main()int n=5

29、;LinkList Lb;int i;ElemType e;printf(按非递增顺序,);CreateList_Link(Lb,n);/*逆位序输入 n 个元素的值*/printf(Lb=);/*输出链表 Lb 的内容*/ListTraverse_Link(Lb);/*算法 2.9 的测试*/printf(n enter insert location and value:);scanf(%d%d,&i,&e);ListInsert_Link(Lb,i,e);/*在 Lb 链表中第 i 个结点处插入一个新的结点，其值为 e;*/printf(Lb=);/*输出链表 Lb 的内容*/ListT

30、raverse_Link(Lb);/*算法 2.10 的测试*/printf(n enter deleted location:);scanf(%d,&i);ListDelete_Link(Lb,i,e);/*在 Lb 链表中删除第 i 个结点，其值为返回给 e 变量*/printf(The Deleted e=%dn,e);/*输出被删结点的内容*/printf(Lb=);/*输出链表 Lb 的内容*/ListTraverse_Link(Lb);四、实验环境和实验步骤四、实验环境和实验步骤实验环境：利用 Visual C+集成开发环境进行本实验的操作。实验步骤顺序表的定义与操作：1启动 VC

31、+;2.新建工程/Win32 Console Application，选择输入位置：如“d:”，输入工程的名称：如“SeqlistDemo”;按“确定”按钮，选择“An Empty Project”，再按“完成”按钮，3新建文件/C/C+Header File，选中“添加到工程的复选按钮”，输入文件名“pubuse.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序;4.新建文件/C/C+Header File，选中“添加到工程的复选按钮”，输入文件名“seqlistDef.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序;5.新建文件/C/C+Header File，选

32、中“添加到工程的复选按钮”，输入文件名“seqlistAlgo.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序;6.新建文件/C+Source File，选中“添加到工程的复选按钮”，输入文件名“seqlistUse.cpp”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序;7按 F7 键，或工具图标进行工程的建立，如有错误，根据错误显示区中的提示，改正错误，重新建立应用程序;8按 Ctrl+F5 键，或工具图标进行工程的执行。实验步骤链表的定义与操作：1启动 VC+;2.新建工程/Win32 Console Application，选择输入位置：如“d:”，输入工程的名

33、称：如“linklistDemo”;按“确定”按钮，选择“An Empty Project”，再按“完成”按钮，3加载实验一中的 pubuse.h 选中菜单的“project”“add to project”-“files”选择已存在文件，确定，然后一定将文件 pubuse.h 拷贝到所建的工程目录下;4.新建文件/C/C+Header File，选中“添加到工程的复选按钮”，输入文件名“linklistDef.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序;5.新建文件/C/C+Header File，选中“添加到工程的复选按钮”，输入文件名“linklistAlgo.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序;6.新建文件/C+Source File，选中“添加到工程的复选按钮”，输入文件名“linklistUse.cpp”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序;7构件、调试、运行与实验一相同。思考题思考题:2对于同样的一组整数，比较线性表的两种不同存储结构的特点和使用场合。答案：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数 据元素（这组存储单元可以是连续的，也可以是不连续的。）而循环链表是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。