链表实验报告样本

__________级 __________班 _______年_______月_____日 姓名____________ 学号____________ 电话_____________ 1．实验题目

编制一个演示单链表（双向链表）插入、删除、查找等操作的程序

2．需求分析

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

① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素值都是整数 ② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。

③ 程序所达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作 ④ 测试数据：

A． 插入操作中依次输入11，12，13，14，15，16，生成一个单链表 B． 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置 C． 删除操作中依次输入2，5，删除位于2和5的元素

3．概要设计

1）为了实现上述程序功能，需要定义单链表的抽象数据类型：

ADT LinkList {

数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 数据关系：R={|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()

各函数间关系如下：

4．详细设计

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

typedef struct node { int data;

struct node *next; }Node,*LinkListl;

2) 单链表的基本操作

为了方便，在单链表中设头结点，其data域没有意义。 bool InitLinkList(LinkList &L) （伪码算法）

void DispLinkList(LinkList L) （伪码算法） void menu() （伪码算法）

bool InsLinkList(LinkList &L,int pos,int e) （伪码算法）

bool DelLinkList(LinkList &L,int pos,int &e) （伪码算法）

int LocLinkList(LinkList L,int e) （伪码算法） 3) 其他模块伪码算法

5．调试分析 6．使用说明

程序名为LinkList.exe，运行环境为DOS。程序执行后显示

======================== 0----EXIT 1----INSERT 2----DELETE 3----LOCATE

======================= SELECT:

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

选择0：退出程序

选择1：显示“INSERT pos,e =” ，

要求输入要插入的位置和元素的值（都是整数）。 选择2：显示“DELETE pos =” ，

要求输入要删除元素的位置，执行成功后返回元素的值。 选择3：显示“LOCATE e = ” ，

要求输入要查找元素的值，执行成功后返回元素在表中的位置

7．测试结果

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。返回输入错误