《数据结构与算法 链表程序》由会员分享，可在线阅读，更多相关《数据结构与算法 链表程序（15页珍藏版）》请在金锄头文库上搜索。
1、 数据结构与算法-实验报告姓名：朱丽班级：电子 105 班学号：2010021528Tel： 15948042225实验一：线性表的存储结构定义及基本实验一：线性表的存储结构定义及基本 操作操作一、实验目的：一、实验目的：. 掌握线性表的逻辑特征. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算. 熟练掌握线性表的链式存储结构定义及基本操作. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：二、实验内容：（一）基本实验内容（顺序表）：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、销毁、置空表、求表长
2、、查找元素、判线性表是否为空;1问题描述：利用顺序表,设计一组输入数据（假定为一组整数） ，能够对顺序表进行如下操作：. 创建一个新的顺序表，实现动态空间分配的初始化;. 根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表;. 根据顺序表结点的位置删除一个结点(位置删除);. 彻底销毁顺序线性表，回收所分配的空间;. 对顺序线性表的所有元素删除，置为空表;. 返回顺序线性表数据元素个数;. 按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第 i 个结点，查找该元素的值，对查找结果进行返回;. 按值查找，根据给定数据元素的值，只能顺序比
3、较，查找该元素的位置，对查找结果进行返回;. 判断顺序表中是否为空表，对判断结果进行返回;. 编写主程序，实现对各不同的算法调用。2实现要求：对顺序表的各项操作一定要编写成为 C（C+）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价;. “初始化算法”的操作结果：构造一个空的顺序线性表。对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间;. “位置插入算法” 的初始条件：顺序线性表 L 已存在，给定的元素位置为i，且 1iListLength(L)+1 ;操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1;. “位置删除算法
4、”的初始条件：顺序线性表 L 已存在，1iListLength(L) ;操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 ;. “销毁算法”初始条件：顺序线性表 L 已存在;操作结果：销毁顺序线性表 L;. “置空表算法”初始条件：顺序线性表 L 已存在;操作结果：将 L 重置为空表;. “求表长算法”初始条件：顺序线性表 L 已存在;操作结果：返回 L 中数据元素个数;. “按序号查找算法”初始条件：顺序线性表 L 已存在，元素位置为 i，且1iListLength(L)操作结果：返回 L 中第 i 个数据元素的值;. “按值查找算法”初始条件：顺序线性表 L
5、已存在，元素值为 e;操作结果：返回 L 中数据元素值为 e 的元素位置;. “判表空算法”初始条件：顺序线性表 L 已存在;操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE;分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。(二）基本实验内容（链表）：二）基本实验内容（链表）：建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除和输出操作。1 问题描述：利用线性表的链式存储结构,设计一组输入数据（假定为一组整数） ，能够对单链表进行如下操作：. 初始化一个带表头结点的空链表;. 创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点
6、数据，并建立起前后相互链接的关系。. 插入结点根据给定位置进行插入（位置插入） 。. 删除结点根据给定位置进行删除（位置删除） 。. 输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点。. 编写主程序，实现对各不同的算法调用。其它的操作算法描述略。2实现要求：对链表的各项操作一定要编写成为 C（C+）语言函数，组合成模块化的形式，还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价。. “初始化算法”的操作结果：构造一个空的线性表 L，产生头结点,并使 L 指向此头结点;. “建立链表算法” 初始条件：空链存在;操作结果：选择逆位序或正位序的方法，建立一个单链表，并且返回完成的
7、结果;. “链表（位置）插入算法”初始条件：已知单链表 L 存在;操作结果：在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e;. “链表（位置）删除算法”初始条件：已知单链表 L 存在;操作结果：在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值;. “输出算法”初始条件：链表 L 已存在;操作结果：依次输出链表的各个结点的值;三：基本程序三：基本程序:（一）线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表）(1) 文件 1： pubuse. h 是公共使用的常量定义和系统函数调用声明，以后每个实验中几乎都涉及到此文件。#include#include#
8、include /* malloc()等*/#include /* INT_MAX 等*/#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 中已
9、定义 OVERFLOW 的值为 3,故去掉此行*/typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如 OK 等*/typedef int Boolean; /* Boolean 是布尔类型,其值是 TRUE 或 FALSE */ (2) 文件 2：seqlistDef. h 进行线性表的动态分配顺序存储结构的表示#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量*/#define LISTINCREMENT 2 /* 线性表存储空间的分配增量*/typedef structElemType *elem; /*
10、存储空间基址*/int length; /* 当前长度*/int listsize; /* 当前分配的存储容量(以 sizeof(ElemType)为单位) */SqList; (3)文件 3：seqlistAlgo.h 进行线性表顺序存储结构的基本实验算法定义Status ListInit_Sq(SqList if(!L. elem)exit(OVERFLOW); /* 存储分配失败*/L.length=0; /* 空表长度为 0 */L.listsize=LIST_INIT_SIZE; /* 初始存储容量*/return OK;Status ListInsert_Sq(SqList if(
11、iL.length+1) /* i 值不合法*/return ERROR;if(L.length=L.listsize) /* 当前存储空间已满,增加分配*/newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW); /* 存储分配失败*/L.elem=newbase; /* 新基址*/L.listsize+=LISTINCREMENT; /* 增加存储容量*/q=L.elem+i-1; /* q 为插入位置*/for(p=L.elem+L.l
12、ength-1;p=q;-p) /* 插入位置及之后的元素右移*/*(p+1)=*p;*q=e; /* 插入 e */+L.length; /* 表长增 1 */return OK;Status ListDelete_Sq(SqList if(iL.length) /* i 值不合法*/return ERROR;p=L.elem+i-1; /* p 为被删除元素的位置*/*e=*p; /* 被删除元素的值赋给 e */q=L.elem+L.length-1; /* 表尾元素的位置*/for(+p;pL.length) /* i 值不合法*/exit(ERROR);e=*(L.elem+i-1)
13、;return OK;/* 还有一些算法，请同学们自己补充完整*/(4)文件 4：seqlistUse.cpp 进行线性表顺序存储结构的基本算法验证#include“pubuse.h“ /* 实现通用常量的定义，常用系统函数的声明*/typedef int ElemType; /*实现一组整数的操作,将 int 型特定义为通用的 ElemType 类型名*/#include“seqlistDef.h“ /* 采用线性表的动态分配顺序存储结构定义*/#include“seqlistAlgo.h“ /* 采用顺序表的基本算法定义*/void main()SqList L;Status i;int
14、j;ElemType t;/* 首先一定要初始化顺序表*/i=ListInit_Sq(L);if(i=1) /* 创建空表 L 成功*/for(j=1;j#include#include /* malloc()等*/#include /* INT_MAX 等*/#include /* EOF(=Z 或 F6),NULL */#include /* atoi() */#include /* eof() */#include /* floor(),ceil(),abs() */#include /* exit() */* 函数结果状态代码*/#define TRUE 1#define FALSE
15、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 是布尔类型,其值是 TRUE 或 FALSE */2 文件 linklistDef.h 是线性表的单链表存储结构的定义struct LNodeElemType data;struct LNode *n
16、ext;typedef struct LNode *LinkList; /* 另一种定义 LinkList 的方法*/3 文件 linklistAlgo.h 是单链表的基本算法描述/* 以下的算法均是针对带表头结点的单链表*/Status ListInit_Link(LinkList /* 产生头结点,并使 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 重置为空
