《算法与数据结构》吴景岚王润鸿编撰
闽江学院计算机实验教学中心印制
目录
前言 (1)
实验一顺序表基本操作的实现 (2)
实验二链表基本操作的实现 (4)
实验三串基本操作的实现 (7)
实验四二叉树基本操作的实现 (9)
实验五图基本操作的实现 (12)
前言
《数据结构》是计算机科学与技术、软件工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。
《数据结构》是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。
实验一顺序表基本操作的实现
专业：计算机科学系嵌入式应用班级： 2班学号： 3141101212 姓
名：粟代琼
实验地点：工A207 实验时间： 2015 10 15 指导教师：陈雄峰【实验课程名称】算法与数据结构
【实验项目名称】顺序表基本操作的实现
一、实验目的
1掌握线性表顺序存储基本操作；
2学会设计实验数据验证程序。
二、实验仪器及环境计算机，window xp操作系统，VC++6.0
三、实验内容及步骤
线性表顺序存储基本操作
存储结构定义：
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct{
ElemType *elem; //存储空间基址
int length；//当前长度
int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList；
实现的基本操作：
InitList( &L )
操作结果：构造一个空的线性表 L 。
DestroyList( &L )
初始条件：线性表 L 已存在。
操作结果：销毁线性表 L 。
ListLength( L )
初始条件：线性表 L 已存在。
操作结果：返回 L 中元素个数。
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 无定义。
GetElem( L, i, &e )
初始条件：线性表 L 已存在，1≤i≤LengthList(L)。
操作结果：用 e 返回 L 中第 i 个元素的值。
LocateElem( L, e, compare( ) )
初始条件：线性表 L 已存在，compare( ) 是元素判定函数。
操作结果：返回 L 中第1个与 e满足关系 compare( )的元素的位序。若这样的元素不存在，则返回值为0。
ClearList( &L )
初始条件：线性表 L 已存在。
操作结果：将 L 重置为空表。
PutElem( &L, i, &e )
初始条件：线性表L已存在，1≤i≤LengthList(L)。
操作结果：L 中第 i 个元素赋值同 e 的值。
ListInsert( &L, i, e )
初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。
操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。ListDelete( &L, i, &e )
初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。
操作结果：删除L 的第 i 个元素，并用 e 返回其值，L 的长度减1。四、实验记录(自己设计测试数据验证算法的正确性)
五、
六、实验小结
七、思考题
1.线性表的顺序存储有何优缺点？
优点：具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出；
缺点：
（1）顺序存储空间容易满，出现上溢，程序访问容易出问题，顺序存储结构下，存储空间不便扩充；
（2）顺序存储空间的分配问题，分多了浪费，分少了空间不足上溢
（3）顺序存储插入与删除一个元素，必须移动大了的数据元素，以此对大的线性表，特别是在元素的插入和删除很频繁的情况下，采取顺序存储
很是不方便，效率低；
2.各举一两个例子说明求解什么样的问题用顺序存储较好。【源代码说明】
1．文件名：
2．操作说明：
实验二链表基本操作的实现
专业：班级：学号：姓名：
实验地点：实验时间：指导教师：
【实验课程名称】算法与数据结构
【实验项目名称】链表基本操作的实现
一、实验目的
1掌握线性表链式存储基本操作；
2学会设计实验数据验证程序。
二、实验仪器及环境计算机，window xp操作系统，VC++6.0
三、实验内容及步骤
线性表链式存储基本操作
存储结构定义：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
实现的基本操作：
InitList( &L )
操作结果：构造一个空的线性表 L 。
DestroyList( &L )
初始条件：线性表 L 已存在。
操作结果：销毁线性表 L 。
ListEmpty( L )
初始条件：线性表L已存在。
