线性表和链式表实验报告.doc

《线性表和链式表实验报告.doc》由会员分享，可在线阅读，更多相关《线性表和链式表实验报告.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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#includeusing namespace std;const int MaxSize=100;templateclass SeqListpublic:SeqList() length=0;SeqList(T a,int n);/1int getlength() return length;T Get(int i); /2int Locate(T x); /3void Insert(in

3、t i,T x);/4T Delete(int i); /5void PrintList(); /6private:T dataMaxSize;int length;#endif SeqList.cpp (SeqList类的实现)#include#include SeqList.husing namespace std;templateSeqList:SeqList(T a,int n)if(nMaxSize) throw 参数非法，发生溢出！;for(int i=0;in;i+)datai = ai;length = n;templateT SeqList:Get(int i)if(ilen

4、gth | i1) throw 查找位置非法;else return datai-1;templateint SeqList:Locate(T x)for(int i=0;ilength;i+)if(datai=x) return i+1;return 0;templatevoid SeqList:Insert(int i,T x)if(length=MaxSize) throw 数据上溢;if( ilength+1 | i=i;j-)dataj=dataj-1;datai-1=x;length+;templateT SeqList:Delete(int i)if(length=0) thro

5、w 数据下溢;if(ilength | i1) throw参数非法，不再链表的长度范围内;int x=datai-1;for(int j=i;jlength;j+)dataj-1=dataj;length-;return x;templatevoid SeqList:PrintList()for(int i=0;ilength;i+)coutdatai ;coutendl;test.cpp(主函数测试文件)#includeusing namespace std;#includeSeqList.cppint main(void)int r5=1,2,3,4,5;SeqList L(r,5);co

6、ut执行插入操作前的数据为：endl;L.PrintList();tryL.Insert(2,3);catch(char* s)coutsendl;cout执行插入后的数据为：endl;L.PrintList();cout值为3的元素位置为：;coutL.Locate(3)endl;cout当前顺序表长度为：;coutL.getlength()endl;cout执行删除第一个元素操作，删除前数据为：endl;L.PrintList();tryL.Delete(1);catch(char* s)coutsendl;cout删除后的数据为： 1000#pragma once#endif / _MS

7、C_VER 1000templatestruct NodeT data;Node* next;templateclass LinkListpublic:LinkList();LinkList(T a,int n);virtual LinkList();int getLength();int Locate(T x);void Insert(int i,T x);T Delete(int i);void PrintList();private:Node* first;#endifLinkList.cpp(LinkList类的声明)#include#include LinkList.husing n

8、amespace std;templateLinkList:LinkList()first=new Node;first-next=NULL;templateLinkList:LinkList(T a,int n)Node*r,*s;first=new Node;r=first;for(int i=0;in;i+)s=new Node;s-data=ai;r-next=s;r=s;r-next=NULL;templateLinkList:LinkList()Node*q=NULL;while(first!=NULL)q=first;first=first-next;delete q;templ

9、ateint LinkList:getLength()int count=0;Node*p=first-next;while(p)count+;p=p-next;return count;templatevoid LinkList:Insert(int i,T x)Node*p=first,*s=NULL;int count=0;while(p!=NULL & countnext;count+;if(p=NULL) throw位置非法;elses=new Node;s-data=x;s-next=p-next;p-next=s;templateT LinkList:Delete(int i)N

10、ode*p=first,*q=NULL;T x;int count=0;while(p!=NULL & countnext;count+;if(p=NULL | p-next=NULL)throw位置;elseq=p-next;x=q-data;p-next=q-next;delete q;return x;templateint LinkList:Locate(T x)Node*p=first-next;int count=1;while(p!=NULL)if(p-data=x)return count;p=p-next;count+;return 0;templatevoid LinkLi

11、st:PrintList()Node*p=first-next;while(p!=NULL)coutdatanext;coutendl;test.cpp(主函数测试文件)#includeLinkList.cppusing namespace std;int main(void)int r5=1,2,3,4,5;LinkList L(r,5);cout执行插入操作前的数据为：endl;L.PrintList();tryL.Insert(2,3);catch(char* s)coutsendl;cout执行插入后的数据为：endl;L.PrintList();cout值为5的元素位置为：;cout

12、L.Locate(5)endl;cout当前单链表的长度为：;coutL.getLength()endl;cout执行删除第一个元素操作，删除前数据为：endl;L.PrintList();tryL.Delete(1);catch(char* s)coutsendl;cout删除后的数据为：endl;L.PrintList();return 0;1.2.3 总结(1) 实验过程中碰到了2个比较有意义的错误，分别是错误a和错误b：a.如图所示，当执行此错误程序时，程序会寻到到链表的i+1位，而不是第i位并进行插入。图a-1改正：将counti改为counti-1即可。原因：在数组中是以0为下标的

13、元素为头元素，而在链表中是以1为下表的元素为头元素。图a-2b.如果用图b-1所示的代码进行计算单链表的长度的操作，当p为空指针时count也会为1。图b-1改正：将count+放入while(p)的循环中即可。图b-2(2) 实验过程使用的主要知识点（ abc编号）a.单链表按值查找算法Locate.b.头插法建立单链表LinkList.c.单链表插入算法Insert.(3) 实验中遇到的不理解或体会比较深的问题（ abc编号）a.当频繁要进行插入和删除操作时，单链表是比较合适的选择。b.经常发生有些变量重复定义，有些变量忘记定义，调用函数经常忘记修改参数。让我认识到细节决定成败。c.让我认识到数据结构与算法是如同骨骼，而C+语言如同肉体。两者并存，才能使得程序更加完整，健全。