北京邮电大学电信工程学院数据结构实验报告实验名称：实验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=a[i];s->next=front->next;front->next=s;}}2、尾插法a、伪代码实现：a.在堆中建立新结点b.将a[i]写入到新结点的数据域c.将新结点加入到链表中d.修改修改尾指针b、代码实现:Linklist::Linklist(int a[],int n,int m)//尾插法{front=new Node;Node*r=front;for(int i=0;i<n;i++){Node*s=new Node;s->data=a[i];r->next=s;r=s;}r->next=NULL;}时间复杂度：O(n)3、按位查找a、伪代码实现: 初始化工作指针p和计数器j，p指向第一个结点，j=1循环以下操作，直到p为空或者j等于1b1：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;}elsewhile(!((p->next->data>x)&&(p->data<x)))//判断p的下一个结点的值大于x且p的值小于x{p=p->next;}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){cout<<p->data<<" ";p=p->next;}}7.获取链表长度函数a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0如果不是空链表，新建立一个temp指针，初始化整形数n为0将temp指针指向头结点判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回nb 、代码实现void Linklist::Getlength()//得到数组长度{Node*p=front->next;int j=0;while(p){p=p->next;j++;}-cout<<j;}2.3 其他源代码#include<iostream>using namespace std;struct Node{int data;struct Node* next;};class Linklist{public: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=a[i];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;i<n;i++){Node*s=new Node;s->data=a[i];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;}elsewhile(!((p->next->data>x)&&(p->data<x)))//判断p的下一个结点的值大于x且p的值小于x{p=p->next;}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++;}cout<<j;}Linklist::~Linklist()//析构{Node*p=front;while(p){front=p;p=p->next;delete front;}}void Linklist::show()//打印数组元素{Node*p=front->next;while(p){cout<<p->data<<" ";p=p->next;}}void main()//主函数{int a[10]={1,2,3,4,5,6,7,8,9,11};Linklist A(a,10);Linklist B(a,10,1);cout<<"原数组为：";A.show();cout<<endl;-A.Insert(10);cout<<"插入操作后的数组变为：";A.show();cout<<endl;A.Delete(7);cout<<"删除操作后的数组为：";A.show();cout<<endl;A.Locate(1);cout<<"数组长度为：";A.Getlength();A.~Linklist();cout<<endl;}3. 程序运行结果1.测试主函数流程：2、运行结果-4. 总结调试时出现的问题及解决的方法：在设计将x按顺序插入的函数时，没有分清p->next->next->data和 p->next->data的区别，通过认真查阅和理解书本知识解决。