实验2链表验证实验.docx

班级：计算机13-2 学号：1 姓名： 成绩：_________实验二 单链表操作验证实验目的掌握线性表的链接存储结构；验证单链表及其基本操作的实现；进一步掌握数据结构及算法的程序实现的基本方法。实验内容用头插法（或尾插法）建立带头结点的单链表；对已建立的单链表实现插入、删除、查找等基本操作。。设计与编码本实验用到的理论知识模板类、多文件系统，链表的操作算法设计参见课本《数据结构（C++版）》编码将算法转化为c++程序，设计主函数完成对各成员函数的调用。源代码：//LinkList.h#ifndef _LINKLIST_H#define _LINKLIST_H#include iostreamusing namespace std;template class Tstruct Node {T data;struct NodeT*next;};template class Tclass LinkList {NodeT*first; //单链表的头指针public:LinkList(T a[],int n); //建立有n个元素的单链表~LinkList(); //析构函数void CreateList(int n); void Insert(int i,T x); //在单链表中第i个位置插入值为x的节点T Delete(int i); //在单链表中删除第i个节点int Locate(T x); //求单链表中值为x的序号void PrintList(); //遍历单链表，按序号依次输出个元素};template class TLinkListT::LinkList(T a[],int n) {first=new NodeT;first-next=NULL; //初始化一个空链表for ( int i=n; i=0; i--) {NodeT *s;s=new NodeT;s-data=a[i];s-next=first-next; //为每个数组元素建立一个结点first-next=s; //插入到头结点之后}} //构造函数，创建一个新的链表template class TLinkListT::~LinkList() {NodeT*p;p=new NodeT;p=first; //工作指针p初始化while (p) { //释放单链表的每一个结点的存储空间NodeT*q;q=new NodeT;q=p; //暂存被释放结点p=p-next; //工作指针p指向被释放结点的下一个结点，使单链表不断开delete q;}} //析构函数,释放空间template class Tvoid LinkListT::Insert(int i,T x) {NodeT*p;p=new NodeT;p=first; //工作指针p初始化int j=0;while (pji-1) {p=p-next; //工作指针p后移j++;}if (!p) throw位置;else {NodeT*s;s=new NodeT;s-data=x; //向内存申请一个结点s，其数据域为xs-next=p-next; //将结点s插入到结点p之前p-next=s;}} //插入元素到位置itemplate class TT LinkListT::Delete(int i) {NodeT*p,*q;T x;p=new NodeT;p=first;int j=0; //工作指针p初始化while (pji-1) { //查找第i-1个结点p=p-next;j++;}if (!p || !p-next)throw位置; //结点p不存在或结点p的后继结点不存在else {q=p-next;x=q-data; //暂存被删结点p-next=q-next; //摘链delete q;return x;}} //删除位置i的函数template class Tint LinkListT::Locate(T x) {NodeT*p;p=new NodeT;p=first-next;int j=1;while (pp-data!=x) {p=p-next; //工作指针p后移j++;}if (p)return j;elsereturn 0;} //查找template class Tvoid LinkListT::PrintList() {NodeT*p;//设置工作指针p=first-next;//从首元结点开始遍历int i=1;//元素位序while(p){coutp-data\t;p=p-next;i++;}coutendl;} //遍历显示链表#endif//LinkList.cpp#include iost