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

1、数据结构实验报告实验名称：实验一一一链式结构实现线性表学生姓名：班 级：班内序号：学 号：日 期：1.实验要求实验目的：通过选择下面四个题目之一进行实现，掌握如下内容：?熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法?学习指针、模板类、异常处理的使用?掌握线性表的操作的实现方法?学习使用线性表解决实际问题的能力实验内容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表,基本功能。线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表并完成线性表线性表的基本功能:构造：使用头插法、尾插法两种方法1 1、插入：要求建立的链表按

2、照关键字从小到大有序2 2、删除3 3、查找4 4、获取链表长度5 5、销毁6 6、其他：可自行定义编写测试 main()main()函数测试线性表的正确性。2.程序分析2.12.1 存储结构2.22.2 关键算法分析算法步骤：1堆中建立新结点2S-next指向front-next3front-next指向s头插法示意图:Frontdatanejct存储结构：顺序表frontNode *s=new Node;s_data=ai; s-n ext=fr ont-n ext; front-n ext=s;时间复杂度：0(n)尾插法算法步骤：1堆中建立新结点Node *s=new Node;2将新结

3、点加入到链表中r-next=front-next3修改尾指针r=s按值查找结点示意图:next二二二一ddUElint i=1;Node* p;p=front-next;匕较P指向的元素是否与检索值相同if(P)while(p)if(p-data=n)cout元素序号：in ext;i+；elsethrow空链表！;时间复杂度：0(n)插入操作:算法步骤:1堆中建立新结点Node *s=new Node;2将新结点插入到要插入位置后一节点p的后面，将后一结点数据写入s3P指向s,在p中写入新的值s-data=p-data;s-n ext=p-n ext;p_n ext=s;p-data=x;时

4、间复杂度：O(1)算法步骤:1从第一个结点开始，查找第i-1个元素，设为p指向该结点;2设q指向第i个元素：q = p-next;3摘链，即将q元素从链表中摘除：p-next = q-next;4保存q元素的数据：x = q-data;5释放q元素：delete q;删除结点示意图:pq删除结点示意图说明：如果算法比较复杂， 可以将多句代码合成一个步骤进行说明。以这样写：1从第一个结点开始，查找第i-1个元素，设为2设q指向第i个元素：q = p-next;3摘链，即将q元素从链表中摘除：p_n ext = q_n ext;x = q-datadelete q;时间复杂度：0(n)2.32.3

5、 其他程序代码：#inelude using namespace std;template struct NodeT data;struct Node * next;template class LinkListpublic比如也可p指向该结点;LinkList()front=new Node ;front-next=NULL;LinkList( T a, int n);Li nkList();Node * Get( int i);Node * Locate( int n, Node * s);void Insert( int i,T x);T Delete( int i);int GetLe

6、ngth();void Print();private :Node * front;template LinkList :LinkList( T 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-n ext=fr ont-n ext; front-n ext=s;/*templateLinkList:LinkList(T a,int n)front=new Node;Node *r=fro nt;for(i nti=O;i n ;i+)No

7、de* s=new Node; s-data=ai;r-n ext=s;r=s;r-n ext=NULL;*/ template LinkList :LinkList() Node * p=front;while (p)fron t=p;/尾插法/析构函数p=p-n ext;delete front;template Node * LinkList :Get( int i) Node * p=front-next;int j=1;while (p&j!= i)p=p-n ext;j+;return p;template Node * LinkList :Locate( int i=1;

8、Node * p;p=front-n ext;if(P)while (p)if(p-data= n)COUtvv 元素序号:p=p-n ext;i+;elsethrow 空链表！;/*while(p&p-data!=n)int n,Node * s)in ext;return p;t=0;if(p-n ext)Locate( n,p-n ext);elsereturn NULL;*/ template void LinkList :Insert( int i,T x)Node * p=Get( i);if(p)Node * s= new Node ;s-data=p-data;s-n

9、ext=p-n ext;p_n ext=s;p-data= x;elsethrow 输入有误;template /T LinkList :Delete( int i)Node * p=front;if(i!=1)p=Get( i-1);Node * q=p-next;p_n ext=q _n ext;T x=q_data;delete q;return x; template int LinkList :GetLength()int i=0;Node * p=front-next;if(P)i+；p=p-n ext;return i; template void LinkList :Print

10、()Node * p=front-next;if(fro nt- n ext)while (p)coutdatan ext; coute ndl;elsethrow 该表没有元素;void main()int x,y;int a6=1,2,3,4,5,6;LinkList L(a,6);L.Pri nt();coutvv 请输入要插入的位置和数值:cin xy;L.ln sert(x,y);L.Pri nt();cout 请输入要删除的元素序号：cinx;L.Delete(x);L.Pri nt();cout 请输入需要查找的元素序号:cinx;coutdatae ndl;cout 请输入需要查找的元素：cinx;L.Locate(x, NULL);coutL.GetLe ngth();n3.程序运行结果测试主函数流程：流程图如图所示打印序列可输入插入的位置和数值打印修改后序列4输入删除的位置1r打印修改后序列输入查找的关键值4打印查找关键值的位置1、测试条件:初始序列为1 2 3 4 5 6插入位置1数值6是删除元素序号3查找元素序号2查找元素62、测试结论初始序列为1 2 3 4 5 6插入位置1数值6后序列：6 1 2 3 4 5 6是删除元素序号3后序列：6 1 3 4 5 6查找元素序号2后查找到序号2所对应元素为