文档介绍：石家庄经济学院
实验报告
学院: 信息工程学院
专业: 计算机
信息工程学院计算机实验中心制
《数据结构》实验报告
姓名
张文楚
学号
409109070515
日期
7-8节
实验室
计算机基础实验室
指导教师
张有华
设备编号
实验题目
实验三线性表的链式存储结构
一实验内容
语言的上机环境,掌握C 语言的基本结构。
。
(建表、插入、删除等)和具体的函数定义。
二实验目的
掌握链式存储结构的特点,了解、掌握并实现单链表的常用的基本算法。
三需求设计
线性表抽象数据类型的描述及实现
ADT List{
数据对象:
数据关系:
基本操作:构造一个空的线性表L InitList();
销毁线性表L DestroyList();
将L重置为空表 ClearList();
判断L是否为空 ListEmpty();
求表长 ListLength();
查找元素 LocateElem();
求前驱 PriorElem();
求后继 NextElem();
插入元素 ListInsert();
删除元素 ListDelete();
元素调用visit()函数 ListTraverse(L,visit())
}ADT List;
程序具体实现要求:
:
**********************************
* 1. 构造线性表
* 2. 插入元素
* 3. 删除元素
* 4. 查找元素
* 5. 显示表长
* 6. 求后继
* 7. 求前驱
* 8. 输出所有元素
* 0. 结束程序运行
***********************************
请输入您的选择(0,1,...,8):
四详细设计
步骤1:给出线性表的抽象数据类型的定义。
ADT List{
数据对象:
数据关系:
基本操作:
InitList(&L);
操作结果:构造一个空的线性表L。
DestroyList(&L)
初始条件:线性表L已存在。
操作结果:销毁线性表L。
ClearList(&L)
初始条件:线性表L已存在。
操作结果:将L重置为空表。
ListEmpty(L)
初始条件:线性表L已存在。
操作结果:若L为空表,则返回TRUE,否则返回FALSE。
ListLength(L)
初始条件:线性表L已存在。
操作结果:返回L中数据元素个数。
GetElem(L,i,&e)
初始条件:线性表L已存在,1≤i≤ListLength(L)。
操作结果:用e返回L中第i数据个元素的值。
LocateElem(L,pare())
初始条件:pare( )是数据元素判定函数。
操作结果:pare()的数据元素的位序。若这样的数据元素不存在,则返回值为0。
PriorElem(L,cur_e,&pre_e)
初始条件:线性表L已存在。
操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义
NextElem(L,cur_e,&next_e)
初始条件:线性表L已存在。
操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义。
ListInsert(&L,i,e)
初始条件:线性表L已存在,1≤i≤ListLength(L)+1。
操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。
ListDelete(&L,i,&e)
初始条件:线性表L已存在且非空,1≤i≤ListLength(L)。
操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。
ListTraverse(L,visit())
初始条件:线性表L已存在。
操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()失败,则操作失败。
} ADT List;
步骤2:用C语言给出线性表的链式存储结构及相关操作的声明。
//单链表的存储结构
typedef struct LNode
{
ElemType data; //结点数据域
struct LNode *next;
} LNode,*LinkList;
基本操作的声明:
St