数据结构实验报告顺序表

选课时间段： 周四6、7、8、9

序 号：

实验报告

课程名称： 数据结构

实验名称： 顺序表的实现

指导教师：

学生姓名：

学生学号：

实验日期： 2013年4月11日

一、实验目的

1、 熟悉实验环境

2、 理解顺序表的基本操作

3、 了解顺序表的建立和输出

4、 掌握顺序表的插入、删除、合并和归并等实现方法

二、实验内容

三、实验步骤

1．需求分析

本演示程序用C语言编写，完成顺序表的生成，任意位置的插入、删除，以及确定某一元素在顺序表中的位置。

① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数。

② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后顺序表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。

③ 程序所能达到的功能：完成顺序表的生成（通过插入操作）、插入、删除、查找操作。

④ 测试数据：

A． 插入操作中依次输入11，12，13，14，15，16，生成一个顺序表

B． 查找操作中依次输入12，15，22返回这3个元素在顺序表中的位置

C． 删除操作中依次输入2，5，删除位于2和5的元素

2．概要设计

1）为了实现上述程序功能，需要定义顺序表的抽象数据类型： ADT LinkList { 数据对象：D={ai|ai∈IntegerSet,i=0,1,2, ,n,n≥0} 数据关系：R={<ai,ai+1>|ai,ai+1 ∈D} 基本操作： InitLinkList(&L) 操作结果：构造一个空的顺序表L. InsLinkList(&L,pos,e) 初始条件：顺序表L已存在

} 操作结果：将元素e插入到顺序表L的pos位置 DelLinkList(&L,pos,&e) 初始条件：顺序表L已存在 操作结果：将顺序表L中pos位置的元素删除，元素值置入e中返回 LocLinkList(L,e) 初始条件：顺序表L依存在 操作结果：顺序表L中查找是否元素e，若存在，返回元素在表中的位置；若不存 在，返回-1. Menu() 操作结果：在屏幕上显示操作菜单 2）本程序包含7个函数： ① 主函数main() ② 初始化顺序表函数InitLinkList() ③ 显示操作菜单函数menu() ④ 显示顺序表内容函数dispLinkList() ⑤ 插入元素函数InsLinkList() ⑥ 删除元素函数DelLinkList() ⑦ 查找元素函数LocLinkList()

3．详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出C代码算法。对主程序和其他模块也都需要写出C代码算法。

1) 结点类型和指针类型

？？？？？？？？？？？？

2) 顺序表的基本操作

bool InitLinkList(LinkList &L) （C代码算法） void DispLinkList(LinkList L) （C代码算法） void menu() （C代码算法） bool InsLinkList(LinkList &L,int pos,int e) （C代码算法） bool DelLinkList(LinkList &L,int pos,int &e) （C代码算法） int LocLinkList(LinkList L,int e) （C代码算法）

3) 其他模块C代码算法

4．使用说明

程序名为？？？？？？？？.exe，运行环境为DOS。程序执行后显示 ======================== 0----EXIT 1----INSERT 2----DELETE 3----LOCATE ======================= SELECT:

在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后顺序表的内容。

选择0：退出程序 选择1：显示“INSERT pos,e =” ， 要求输入要插入的位置和元素的值（都是整数）。 选择2：显示“DELETE pos =” ， 要求输入要删除元素的位置，执行成功后返回元素的值。 选择3：显示“LOCATE e = ” ， 要求输入要查找元素的值，执行成功后返回元素在表中的位置

6．测试结果

1） 建立顺序表：

» 选择1，分别输入（0，11），（0，12），（0，13），（0，14）（0，15）。得到顺序表（15，14，13，12，11）

2） 插入：

» 选择1输入（1，100），得到顺序表（15，100，14，13，12，11）

» 选择1输入（-1，2），显示输入错误

» 选择1输入（7，2），显示输入错误

» 选择1输入（6，2），得到顺序表（15，100，14，13，12，11，2）

3） 删除：

» 选择2，输入1。返回e=100，得到顺序表（15，14，13，12，11，2） » 选择2，输入0。返回e=15，得到顺序表（14，13，12，11，2）

» 选择2，输入4。返回e=2，得到顺序表（14，13，12，11）

» 选择2，输入5。返回输入错误

4） 查找

» 选择3，输入14。返回pos=0

» 选择3，输入100。返回输入错误

四、实验总结（结果分析和体会）