实验一-链式结构实现线性表

北京邮电大学信息与通信工程学院第5页北京邮电大学电信工程学院第1页数据结构实验报告实验名称：实验一——链式结构实现线性表学生姓名：班级：班内序号：学号：日期：实验要求实验目的：通过选择下面四个题目之一进行实现，掌握如下内容：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力实验内容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：带头结点的单链表不带头结点的单链表循环链表双链表静态链表线性表的基本功能：构造：使用头插法、尾插法两种方法插入：要求建立的链表按照关键字从小到大有序删除查找获取链表长度销毁其他：可自行定义编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构存储结构：顺序表2.2关键算法分析头插法示意图：算法步骤：堆中建立新结点S->next指向front->nextfront->next指向sNode<T>*s=newNode<T>; s->data=a[i]; s->next=front->next; front->next=s;时间复杂度：O(n)尾插法算法步骤：堆中建立新结点Node<T>*s=newNode<T>;将新结点加入到链表中r->next=front->next修改尾指针r=s按值查找结点示意图：template<classT>LinkList<T>::~LinkList()//析构函数{ Node<T>*p=front; while(p) { front=p; p=p->next; deletefront; }}template<classT>Node<T>*LinkList<T>::Get(inti){ Node<T>*p=front->next; intj=1; while(p&&j!=i) { p=p->next; j++; } returnp; }template<classT>Node<T>*LinkList<T>::Locate(intn,Node<T>*s){ inti=1; Node<T>*p; p=front->next; if(p) while(p) { if(p->data==n) cout<<"元素序号："<<i<<endl; p=p->next; i++; } else throw"空链表！"; /*while(p&&p->data!=n) { p=p->next; } returnp; t=0; if(p->next)// Locate(n,p->next) ; else returnNULL;*/}template<classT>voidLinkList<T>::Insert(inti,Tx){ Node<T>*p=Get(i); if(p) {Node<T>*s=newNode<T>; s->data=p->data;// s->next=p->next; p->next=s; p->data=x; } else throw"输入有误";}template<classT>TLinkList<T>::Delete(inti){ Node<T>*p=front; if(i!=1) p=Get(i-1); Node<T>*q=p->next; p->next=q->next; Tx=q->data; deleteq; returnx;}template<classT>intLinkList<T>::GetLength(){ inti=0; Node<T>*p=front->next; if(p){ i++; p=p->next;} returni;}template<classT>voidLinkList<T>::Print(){ Node<T>*p=front->next; if(front->next) { while(p) { cout<<p->data<<""; p=p->next; } cout<<endl; } else throw"该表没有元素";}voidmain(){ intx,y; inta[6]={1,2,3,4,5,6}; LinkList<int>L(a,6); L.Print(); cout<<"请输入要插入的位置和数值："; cin>>x>>y; L.Insert(x,y); L.Print(); cout<<"请输入要删除的元素序号："; cin>>x; L.Delete(x); L.Print(); cout<<"请输入需要查找的元素序号："; cin>>x; cout<<L.Get(x)->data<<endl; cout<<"请输入需要查找的元素："; cin>>x; L.Locate(x,NULL); cout<<L.GetLength();3.程序运行结果测试主函数流程：流程图如图所示开始打印序列开始打印序列是否退出？结束是输入插入的位置和数值输入插入的位置和数值打印修改后序列打印修改后序列输入删除的位置输入删除的位置打印修改后序列打印修改后序列输入查找的关键值输入查找的关键值打印查找关键值打印查找关键值的位置测试条件：初始序列为123456插入位置1数值6是删除元素序号3查找元素序号2查找元素6测试结论初始序列为123456插入位置1数值6后序列：6123456是删除元素序号3后序列：613456查找元素序号2后查找到序号2所对应元素为：1查找元素6查找到所对应元素序号为1和64.总结本次实验我掌握了线性表的