线性表和链式表实验报告

1、 数据结构与算法实验院 别：计算机科学与信息工程学院年级专业：2014级空间信息与数字技术姓 名：杨哲庆学 号：1420012138评语和成绩: 2015 年 9月 实验1 线性表实验1.1 顺序表1.1.1 实验的主要内容和目的 了解顺序存储的基本思想； 掌握基于顺序表基本操作的实现； 掌握计算基于顺序表基本操作的时间性能； 认识顺序表和链表之间的区别。1.1.2 代码SeqList.h (SeqList类的声明)#if !defined(AFX_SEQLIST_H_A502EFF8_79FB_4E5E_96F3_B8C7E03EB41B_INCLUDED_)#define AFX_SEQL

2、IST_H_A502EFF8_79FB_4E5E_96F3_B8C7E03EB41B_INCLUDED_#if _MSC_VER > 1000#pragma once#endif / _MSC_VER > 1000/*=*/#include<iostream>using namespace std;const int MaxSize=100;template<class T>class SeqListpublic:SeqList() length=0;SeqList(T a,int n);/1int getlength() return length;T G

3、et(int i); /2int Locate(T x); /3void Insert(int i,T x);/4T Delete(int i); /5void PrintList(); /6private:T dataMaxSize;int length;/*=*/#endif SeqList.cpp (SeqList类的实现)#include<iostream>#include "SeqList.h"using namespace std;template<class T>SeqList<T>:SeqList(T a,int n)if

4、(n>MaxSize) throw "参数非法，发生溢出！"for(int i=0;i<n;i+)datai = ai;length = n;template<class T>T SeqList<T>:Get(int i)if(i>length | i<1) throw "查找位置非法"else return datai-1;template<class T>int SeqList<T>:Locate(T x)for(int i=0;i<length;i+)if(datai=x

5、) return i+1;return 0;template<class T>void SeqList<T>:Insert(int i,T x)if(length>=MaxSize) throw "数据上溢"if( i>length+1 | i<1 ) throw "参数非法，不在链表的长度范围内"for(int j=length;j>=i;j-)dataj=dataj-1;datai-1=x;length+;template<class T>T SeqList<T>:Delete(

6、int i)if(length=0) throw "数据下溢"if(i>length | i<1) throw"参数非法，不再链表的长度范围内"int x=datai-1;for(int j=i;j<length;j+)dataj-1=dataj;length-;return x;template<class T>void SeqList<T>:PrintList()for(int i=0;i<length;i+)cout<<datai<<" "cout<&

7、lt;endl;test.cpp(主函数测试文件)#include<iostream>using namespace std;#include"SeqList.cpp"int main(void)int r5=1,2,3,4,5;SeqList<int> L(r,5);cout<<"执行插入操作前的数据为："<<endl;L.PrintList();tryL.Insert(2,3);catch(char* s)cout<<s<<endl;cout<<"执行插入后

8、的数据为："<<endl;L.PrintList();cout<<"值为3的元素位置为："cout<<L.Locate(3)<<endl;cout<<"当前顺序表长度为："cout<<L.getlength()<<endl;cout<<"执行删除第一个元素操作，删除前数据为："<<endl;L.PrintList();tryL.Delete(1);catch(char* s)cout<<s<<e

9、ndl;cout<<"删除后的数据为："<<endl;L.PrintList();return 0;1.1.3 总结(1) 实验过程中碰到了2个比较有意义的错误，分别是错误a和错误b：a.调用了SeqList类的声明文件SeqList.h却没有调用SeqList类的实现文件SeqList.cpp。如图1-1；图 a1 改正：将SeqList.cpp中加入代码：#include "SeqList.h",如图1-2； 然后再在test.cpp中将#include "SeqList.h"改为#include &quo

10、t;SeqList.cpp",如图1-3。图 a2图a3b.SeqList的成员函数用if进行判断，用“throw”进行抛出一串字符串。而“catch”得到的应该是字符串的首地址，应该是个指针，而不应该如图b-1所示。图b-1改正：将错误代码:catch(char s) 改为:catch(char* s)即可，如图b-2所示。图b-2(2) 实验过程使用的主要知识点（ abc编号）a. 顺序表按值查找算法Locate.b. 顺序表插入算法Insert.c. 顺序表删除算法Delete.(3) 实验中遇到的不理解或体会比较深的问题（ abc编号）a. 顺序表的插入以及删除操作距离表头或

11、表尾越近，则程序运行耗时越短。b. 顺序表本质还是一个一维数组。c. 如果需要进行频繁的查找操作，顺序表是一个合适的选择。1.2 链式表1.2.1 实验的主要内容和目的 了解顺链接存储的基本思想； 掌握基于单链表基本操作的实现； 掌握计算基于单链表基本操作的时间性能； 熟悉单链表的基本运算在两种存储结构上的实现；1.2.2 代码LinkList.h (LinkList类的声明)#if !defined(AFX_LINKLIST_H_B3F42344_7C3F_4313_8B60_09F1F2998D68_INCLUDED_)#define AFX_LINKLIST_H_B3F42344_7C3

12、F_4313_8B60_09F1F2998D68_INCLUDED_#if _MSC_VER > 1000#pragma once#endif / _MSC_VER > 1000template<class T>struct NodeT data;Node<T>* next;template<class T>class LinkListpublic:LinkList();LinkList(T a,int n);virtual LinkList();int getLength();int Locate(T x);void Insert(int i,

13、T x);T Delete(int i);void PrintList();private:Node<T>* first;#endifLinkList.cpp(LinkList类的声明)#include<iostream>#include "LinkList.h"using namespace std;template<class T>LinkList<T>:LinkList()first=new Node<T>first->next=NULL;template<class T>LinkList&

14、lt;T>:LinkList(T a,int n)Node<T>*r,*s;first=new Node<T>r=first;for(int i=0;i<n;i+)s=new Node<T>s->data=ai;r->next=s;r=s;r->next=NULL;template<class T>LinkList<T>:LinkList()Node<T>*q=NULL;while(first!=NULL)q=first;first=first->next;delete q;templa

15、te<class T>int LinkList<T>:getLength()int count=0;Node<T>*p=first->next;while(p)count+;p=p->next;return count;template<class T>void LinkList<T>:Insert(int i,T x)Node<T>*p=first,*s=NULL;int count=0;while(p!=NULL && count<i-1)p=p->next;count+;if(

16、p=NULL) throw"位置非法"elses=new Node<T>s->data=x;s->next=p->next;p->next=s;template<class T>T LinkList<T>:Delete(int i)Node<T>*p=first,*q=NULL;T x;int count=0;while(p!=NULL && count<i-1)p=p->next;count+;if(p=NULL | p->next=NULL)throw"位

17、置"elseq=p->next;x=q->data;p->next=q->next;delete q;return x;template<class T>int LinkList<T>:Locate(T x)Node<T>*p=first->next;int count=1;while(p!=NULL)if(p->data=x)return count;p=p->next;count+;return 0;template<class T>void LinkList<T>:PrintL

18、ist()Node<T>*p=first->next;while(p!=NULL)cout<<p->data<<" "p=p->next;cout<<endl;test.cpp(主函数测试文件)#include"LinkList.cpp"using namespace std;int main(void)int r5=1,2,3,4,5;LinkList<int> L(r,5);cout<<"执行插入操作前的数据为："<<endl;L

19、.PrintList();tryL.Insert(2,3);catch(char* s)cout<<s<<endl;cout<<"执行插入后的数据为："<<endl;L.PrintList();cout<<"值为5的元素位置为："cout<<L.Locate(5)<<endl;cout<<"当前单链表的长度为："cout<<L.getLength()<<endl;cout<<"执行删除第一个元素操作，删除前数据为：