数据结构实验一线性表的基本操作.docx

天津农学院13级软件工程1班李光耀
/NUMPAGES18
实验一线性表的基本操作
一、实验目的：
1．掌握线性表的顺序和链式存储结构。
2．熟练地利用顺序和链式存储结构实现线性表的基本操作。
3．能熟练地掌握顺序和链式存储结构中算法的实现。
二、实验内容：
第一部分：单链表
1．需求分析
本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
①输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数
②输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。
③程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作
④测试数据：
A．插入操作中依次输入11、22、33、44、55、66生成一个单链表
B．查找操作中输入55返回这个元素在单链表中的位置
C．输入要插入的位置为5，插入的元素为123；
D．删除操作中输入44。
2．概要设计
（1）为了实现上述程序功能，需要定义单链表的抽象数据类型：ADTLinkList{数据对象：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()
InitLinkList
InsLinkList
各函数间关系如下：
main

DelLinkList
Menu

dispLinkList
LocLinkList

实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。1)结点类型和指针类型typedefstructnode{intdata;structnode*next;}Node,*LinkListl;
2)单链表的基本操作
为了方便，在单链表中设头结点，其data域没有意义。
boolInitLinkList(LinkList&L)（伪码算法）voidDispLinkList(LinkListL)（伪码算法）voidmenu()（伪码算法）boolInsLinkList(LinkList&L,intpos,inte)（伪码算法）boolDelLinkList(LinkList&L,intpos,int&e)（伪码算法）intLocLinkList(LinkListL,inte)（伪码算法）
3)其他模块伪码算法
4．调式分析#include<iostream>
#include<iomanip>
usingnamespacestd;
structNode
{
intdata;
Node*next;
};
classLinkList
{
public:
LinkList();
LinkList(inta[],intn);
intgetLength();
intGet(inti);
intLocate(intx);
voidInsert(inti,intx);
intDelete(inti);
voidPrintList();
voidmenus();
voidInList();
private:
Node*first;
};

voidLinkList::menus()
{
cout<<"============"<<endl;
cout<<0<<"---"<<"退出程序"<<endl;
cout<<1<<"---"<<"查看原始链表："<<endl;
cout<<2<<"---"<<"查看链表长度："<<endl;
cout<<3<<"---"<<"按位取出链表中的元素："<<endl;
cout<<4<<"---"<<