实验2 链表验证实验.doc

《实验2 链表验证实验.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、班级：计算机13-2学号：1：成绩：_________实验二单链表操作验证一、实验目的1)掌握线性表的存储结构；2)验证单链表及其基本操作的实现；3)进一步掌握数据结构及算法的程序实现的基本方法。二、实验容1)用头插法（或尾插法）建立带头结点的单链表；2)对已建立的单链表实现插入、删除、查找等基本操作。。三、设计与编码a)本实验用到的理论知识模板类、多文件系统，链表的操作b)算法设计参见课本《数据结构（C++版）》c)编码将算法转化为c++程序，设计主函数完成对各成员函数的调用。源代码：//LinkList.h#ifndef_LINKLIST_H#define_LINKLIST

2、_H#includeusingnamespacestd;templatestructNode{Tdata;structNode*next;};templateclassLinkList{Node*first;//单链表的头指针public:LinkList(Ta[],intn);//建立有n个元素的单链表~LinkList();//析构函数voidCreateList(intn);voidInsert(inti,Tx);//在单链表中第i个位置插入值为x的节点TDelete(inti);//在单链表中删除第i个节点

3、intLocate(Tx);//求单链表中值为x的序号voidPrintList();//遍历单链表，按序号依次输出个元素};templateLinkList::LinkList(Ta[],intn){first=newNode;first->next=NULL;//初始化一个空链表for(inti=n;i>=0;i--){Node*s;s=newNode;s->data=a[i];s->next=first->next;//为每个数组元素建立一个结点first->next=s;//插入到头结点之后}}//构造函数，创建一个新的链表tem

4、plateLinkList::~LinkList(){Node*p;p=newNode;p=first;//工作指针p初始化while(p){//释放单链表的每一个结点的存储空间Node*q;q=newNode;q=p;//暂存被释放结点p=p->next;//工作指针p指向被释放结点的下一个结点，使单链表不断开deleteq;}}//析构函数,释放空间templatevoidLinkList::Insert(inti,Tx){Node*p;p=newNode;p=first;//工作指针p初始化i

5、ntj=0;while(p&&jnext;//工作指针p后移j++;}if(!p)throw"位置";else{Node*s;s=newNode;s->data=x;//向存申请一个结点s，其数据域为xs->next=p->next;//将结点s插入到结点p之前p->next=s;}}//插入元素到位置itemplateTLinkList::Delete(inti){Node*p,*q;Tx;p=newNode;p=first;intj=0;//工作指针p初始化while(p&&j

6、结点p=p->next;j++;}if(!p

7、

8、!p->next)throw"位置";//结点p不存在或结点p的后继结点不存在else{q=p->next;x=q->data;//暂存被删结点p->next=q->next;//摘链deleteq;returnx;}}//删除位置i的函数templateintLinkList::Locate(Tx){Node*p;p=newNode;p=first->next;intj=1;while(p&&p->data!=x){p=p->next;//工作指针p后移j++;}if(p)returnj;els

9、ereturn0;}//查找templatevoidLinkList::PrintList(){Node*p;//设置工作指针p=first->next;//从首元结点开始遍历inti=1;//元素位序while(p){cout<data<<"t";p=p->next;i++;}cout<#include"Windows.h"#include"Lin