山东大学《数据结构》实验指导02线性表.docx

实验二线性表
一实验任务
1)线性表的顺序表示和实现
2)线性表的链式结构表示和实现二实验目的
1)掌握线性表的类型定义和结构特点。
2)掌握线性表的顺序存储表示、链式存储表示及其C语言实现。
3)掌握顺序表的各种基本操作的实现。
4)掌握线性表在链式存储结构上的各种操作。
三实验原理
1.线性表的逻辑结构及特性
所谓线性表(LineajList),就是n(nNO)个数据元素的集合{ai,a2,…,an}, 这些数据元素之间有逻福上的线性关系。
线性表的抽象数据类型定义如下：
ADT List数据对象：D={aj | ajGEIemSet, i=l,2,n>0}
数据关系：Ri = {< aj-i, ai > | aj-1, ajeD, i =2,…,n)基本操作：
CreatList(&L)操作结果：生成一个空的线性表L。
ListLength(L)初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。
ListInsert(&L, i, e)初始条件：线性表L已存在，lWiWListLength(L)+l。
操作结果:在L中第i个位置之前插入新的数据元素e, L的长度加loListDelete(&L, i, &e)
初始条件：线性表L已存在且非空，lWWListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减lo
Get日em(L, i, &e)初始条件：线性表L已存在，lWWListLength(L)。
操作结果：用e返回L中第i个数据元素的值。
LocateElem(L, e, compare())初始条件：线性表L已存在，compare()是数据元素判定函数。
操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。假设这样的数据元素不存在，那么返回值为0。
ListEmpty(L)初始条件：线性表L已存在。
操作结果：假设L为空表，那么返回TRUE,否那么返回FALSE。
ClearList(&L)初始条件：线性表L已存在。
操作结果：将L重置为空表。
DestroyList(&L)初始条件：线性表L已存在。
操作结果：销毁线性表L。
} ADT List
2 .线性表的顺序表示
线性表的顺序表示就是利用一组地址连续的内存空间依次存储线性表的各 个数据元素，即以元素在计算机内''物理位置相邻〃来表示线性表中数据元素之间 的逻辑关系。
由于顺序存储结构是一种随机存取的存储结构，所以通常利用C语言中动态 分配的一组连续的存储单元作为顺序存储结构所需要的存储空间。
可通过定义结构体类型来实现线性表的动态分配顺序存储结构。具体数据类 型描述如下：
#define MAXLEN 100
#define LISTJNCREASE 10 〃线性表存储空间的动态分配增量
typedef struct
{ElemType *list;〃线性表的存储空间的基地址
intlength;〃线性表的当前长度intmaxsize; 〃线性表当前分配的存储容量
}List_Sq;
3 . ^性表的链式结构
链式存储结构具有以下特点：不要求逻辑上相邻的元素在物理结构上也相邻; 允许迅速简单地插入或删除结点，而不必移动大量元素；但只能顺序存取而不能 随机存取线性表中任一元素。
线性表的链式存储结构可通过单链表来实现。此时，线性表中的每个元素对 应单链表中的一个结点，每个结点的数据域存储线性表的数据元素，每个结点的 指针域存储其后继元素所在结点的地址，可以通过每个结点的指针域访问到其后 继结点，如图2,1所示。
头指针第一个结点
图2.1线性链表例如
因此，单链表中每个结点都是由包含这个数据元素的信息和一个指示其直接 后继的指针组成的一个结构体类型，具体描述如下：
typedef struct LNode
{ElemType data;
struct LNode * next;
} LNode, * List_Link;每个单链表的反指针L是ListJJnk型的变量，指向链表中第一个结点。由表 头指针出发可以依次访问到每个结点，存取相应的数据元素值。线性表中数据元 素间的线性关系都可以通过单链表中结点指针域的链接关系反映出来。当 L=NULL时，意味着所表示的线性表为''空〃表，其长度n为''零
四实验设备、仪器、工具及资料
微机、VC五实验内容
（1）实验任务工：顺序表的表示与实现
请编制C程序，利用顺序存储方式来实现以下功能：
1）建立主程序菜单，使之具有建立线性表、插入元素、删除元素、查找元 素、销毁线性表、结束程序运行等菜单项。
2）根据键盘输入数据生成一个线性表，并输出该原始线性表。
3）根据屏幕菜单的提示选择，进行数据插入、删除、查找等操作。
4）最后，输出修改之后的线性表并结束程序的运行。
（2）实验任务2：线性表的链式存储表示与实现
请编制C程序，利用链式存储方式来实现以下功能：
1）建立主程序菜单，使之具有建立线性表、插入元素、删除元素、查找元 素、销毁线性表、结束程序运行等菜单项。
2）根据键盘输入数据生成一个单链表，并输出该原始单链表。
3）根据屏幕菜单的提示选择，进行数据插入、删除、查找等操作。
4）最后，输出修改之后的单链表并结束程序的运行。
（3）实验任务3：线性表的合并（选做）
编制C程序实现以下功能：
1）建立两个线性表（顺序存储表示或链式存储表示）。
2）对已建立的两个线性表进行升序排序。
3）合并这两个有序表。
六实验步骤（1）实验预习
1）预习本实验原理中关于线性表的定义、顺序存储表示和链式存储结构。
2）分析掌握教材21~23页中的算法2-1~2-5,为完成实验任务1做好准备。
3）分析掌握教材27~30页中的算法2-9~2-13,为完成实验任务2做好准 备。
4）分析掌握教材25页中的算法2-7~2-8或教材31-32页中的算法 2-15-2-16,为完成实验任务3做好准备。
（2）实验步骤
1）问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件 是什么。
2）系统的结构设计。按照以数据结构为中心的原那么划分模块。最后写出每 个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示那么更加清晰，这样便完成了系统结构设计。
3）详细设计详细设计的目的是对子程序（过程或函数）的进一步求精。 用IF、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的 目的是防止陷入细节。
4）编码。在详细设计的基础上，对详细设计的结果进一步求精，用C语言 表示出来。
5）在VC环境下调试程序。
七实验报告要求
实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：
1）需求分析及规格说明：问题描述，求解的问题是什么。
2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互 关系。
3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调 用关系。
4）调试报告。
5）本实验任务1、2的程序清单及运行结果。
八思考题
1）通过实验任务1、2的实现比拟线性表的两种存储结构的优缺点。
2）实现任务3种采用哪种存储表示更容易些？