数据结构实验一题目一线性表实验报告

-数据结构实验报告实验名称： 实验1线性表学生姓名： 班 级： 班内序号： 学 号：日 期：1 实验要求1、实验目的： 熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力 2、实验内容：题目1： 线性表的基本功能：1、 构造：使用头插法、尾插法两种方法2、 插入：要求建立的链表按照关键字从小到大有序3、 删除4、 查找5、 获取链表长度6、 销毁7、 其他：可自行定义编写测试main()函数测试线性表的正确性。2. 程序分析 2.1 存储结构 带头结点的单链表2.2 关键算法分析1.头插法a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现：Linklist:Linklist(int a,int n)/头插法front=new Node;front-next=NULL;for(int i=n-1;i=0;i-)Node*s=new Node;s-data=ai;s-next=front-next;front-next=s;2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将ai写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针b、代码实现: Linklist:Linklist(int a,int n,int m)/尾插法front=new Node;Node*r=front;for(int i=0;idata=ai;r-next=s;r=s;r-next=NULL;时间复杂度：O(n)3、按位查找a、伪代码实现: 初始化工作指针p和计数器j，p指向第一个结点，j=1 循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 若p为空，说明第i个元素不存在，抛出异常 否则，说明p指向的元素就是所查找的元素，返回元素地址b、代码实现Node* Linklist:Get(int i)/得到指向第i个数的指针Node*p=front-next;int j=1;while(p&j!=i)/p非空且j不等于i，指针后移p=p-next;j+;return p;4、插入操作a、伪代码实现: 如果链表为空，直接插入判断p的下一个结点的值大于x且p的值小于x在堆中建立新结点 将要插入的结点的数据写入到新结点的数据域 修改新结点的指针域 修改前一个指针的指针域，使其指向新插入的结点的位置 b、代码实现void Linklist:Insert(int x)/将x按顺序插入Node*p=front-next;if(!p)/如果链表为空，直接插入Node*s=new Node;s-data=x;s-next=front-next;front-next=s;else while(!(p-next-datax)&(p-datanext;Node*s=new Node;/将x插入到p之后s-data=x;s-next=p-next;p-next=s;5、删除操作a、伪代码实现:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点 设q指向第i个元素 将q元素从链表中删除 保存q元素的数据 释放q元素b、代码实现int Linklist:Delete(int i)/删除第i个位置的结点Node*p=front;if(i!=1)p=Get(i-1);/得到第i-1个位置的指针Node*q=p-next;p-next=q-next;int x=q-data;delete q;return x;6遍历打印函数a、伪代码实现:判断该链表是否为空链表，如果是，报错 如果不是空链表，新建立一个temp指针 将temp指针指向头结点 打印temp指针的data域 逐个往后移动temp指针，直到temp指针的指向的指针的next域为空 b、代码实现void Linklist:show()/打印数组元素Node*p=front-next;while(p)coutdatanext;7.获取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n b 、代码实现void Linklist:Getlength()/得到数组长度Node*p=front-next;int j=0;while(p)p=p-next;j+;coutj;2.3 其他源代码#includeusing namespace std;struct Nodeint data;struct Node* next;class Linklistpublic:Linklist(int a,int n);Linklist(int a,int n,int m);Node* Get(int i);void Insert(int x);int Delete(int i);int Locate(int x);void Getlength();void show();Linklist();private:Node*front;Linklist:Linklist(int a,int n)/头插法front=new Node;front-next=NULL;for(int i=n-1;i=0;i-)Node*s=new Node;s-data=ai;s-next=front-next;front-next=s;Linklist:Linklist(int a,int n,int m)/尾插法front=new Node;Node*r=front;for(int i=0;idata=ai;r-next=s;r=s;r-next=NULL;Node* Linklist:Get(int i)/得到指向第i个数的指针Node*p=front-next;int j=1;while(p&j!=i)/p非空且j不等于i，指针后移p=p-next;j+;return p;void Linklist:Insert(int x)/将x按顺序插入Node*p=front-next;if(!p)/如果链表为空，直接插入Node*s=new Node;s-data=x;s-next=front-next;front-next=s;else while(!(p-next-datax)&(p-datanext;Node*s=new Node;/将x插入到p之后s-data=x;s-next=p-next;p-next=s;int Linklist:Delete(int i)/删除第i个位置的结点Node*p=front;if(i!=1)p=Get(i-1);/得到第i-1个位置的指针Node*q=p-next;p-next=q-next;int x=q-data;delete q;return x;int Linklist:Locate(int x)/得到值为x的位置Node*p=front-next;int j=1;while(p)if(p-data=x)return j;p=p-next;j+;return -1;void Linklist:Getlength()/得到数组长度Node*p=front-next;int j=0;while(p)p=p-next;j+;coutnext;delete front;void Linklist:show()/打印数组元素Node*p=front-next;while(p)coutdatanext;void main()/主函数int a10=1,2,3,4,5,6,7,8,9,11;Linklist A(a,10);Linklist B(a,10,1);cout原数组为：;A.show();coutendl;A.Insert(10);cout插入操作后的数组变为：;A.show();coutendl;A.Delete(7);cout删除操作后的数组为：;A.sho