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

实验一线性表的基本操作一、实验目的：1．掌握线性表的顺序和链式存储结构。2．熟练地利用顺序和链式存储结构实现线性表的基本操作。 3．能熟练地掌握顺序和链式存储结构中算法的实现。二、实验内容：第一部分：单链表1．需求分析本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。　　①输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数　　②输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。　　③程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作　　④ 测试数据：　　A． 插入操作中依次输入11、22、33、44、55、66生成一个单链表　　B． 查找操作中输入55返回这个元素在单链表中的位置C． 输入要插入的位置为5，插入的元素为123；　　D． 删除操作中输入44。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()各函数间关系如下：实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。　　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) 其他模块伪码算法4．调式分析#include iostream#include iomanipusing namespace std;struct Node{int data;Node *next;};class LinkList{public: LinkList(); LinkList(int a[],int n); int getLength(); int Get(int i); int Locate(int x); void Insert (int i,int x); int Delete (int i); void PrintList(); void menus(); void InList();private: Node *first;};void LinkList::menus(){ cout============endl;cout0---退出程序endl;cout1---查看原始链表：endl;cout2---查看链表长度：endl;cout3---按位取出链表中的元素：endl;cout4---按值取出链表中的元素：endl;cout5---插入元