数据结构线性表试验报告.doc

线性表上机实习1、实验目的（1）熟悉将算法转换为程序代码的过程。（2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。（3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。2、实验要求（1）熟悉顺序表的插入、删除和查找。（2）熟悉单链表的插入、删除和查找。3、 实验内容:1 顺序表 （1）抽象数据类型定义 typedef struct TypeData datamaxsize; /容量为maxsize的静态顺手表 int n; /顺序表中的实际元素个数 SeqList; /静态顺序表的定义 在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单选择界面，通过不同的数字输入，实现对顺序表，删除，插入，查找，显示等操作。 （2）存储结构定义及算法思想 在顺序表结构体的定义中，typedef int TypeData 为整型，存储结构如下： for(n=0;nm;n+) cout请输入线性表数据L.datan; /顺序将数据存入顺序表 /其他存储与此类似，都是直接赋值与数组的某一位插入版块子函数：void insert(SeqList &L) /插入数据 int a,b,c,k; cout请输入插入的数及其插入的位置ab; if(b(L.n+1) cout不能在该位置插入b) L.datac=L.datac-1;c-; /通过循环，实现插入位置后的数据挨个往后移动一位 L.datab=k;顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。 显示操作是通过循环实现表中第一个元素到最后一个元素的输出，查找操作是直接取数组中的查找位输出。（3） 实验结果与分析 2 单链表 （1）抽象数据类型定义typedef struct nodeDataType data; /链表的数据类型struct node *link; /链表的结点指针linknode,*linklist; /定义了结构体linklode和结构体指针linklist 在本次实验中，首先程序自己建立一个空的头结点，通过菜单的功能选择“添加链表数据”可自由添加链表的节点数及元素值。在菜单选择中，有“添加链数据”，“插入链表数据”，“删除链表数据”，“查找链表数据”和“显示链表数据”功能，选择不能的功能选择就能实现不同的操作。其中“添加链表数据”可反复批量输入链表数据。（2） 存储结构定义及算法思想 在单链表中，typedef int DataType;DataType data;定义链表存储数据位整型。存储结构如下：while(p-link!=NULL)p=p-link; k+; /首先找到单链表的最后结点（如果是只有头结点 的单链表则直接跳过），以便后面接着输入数据 for(int i=0;ia;i+) cout请输入数据q-data; q-link=p-link; /将前面一个结点的指向(及NULL)赋给新开辟的结点的指向p-link=q; /将插入点前面一个结点指向新开辟的的结点p=q; /将指明的最后一个一个结点向后移1位到最后一位，以便后面接着输入 删除结点子函数： void delate(linklist &l) /删除单链表数据 linklist p; int m,n,i=0; cout请输入想要删除的结点位置m; p=l; /将头结点赋给转移指针p while(p&ilink; /当在单链表中间已查到删除结点或p=NULL时跳出循环i+; if(p=NULL) /当p=NULL跳出循环时，表明链表中没有该结点 cout该结点不存在，删除错误link-data; /找到删除接结点将数据取出并显示出来（找结点时是找的前一个结点） cout被删除的结点元素为: nlink=p-link-link; /将删除结点的前后结点链接起来 链表的删除，插入操作是类似的，要考虑到加入或减少一个结点后，前后结点的链接关系，以及删除或插入的是最后一个结点时，新空间的开辟与结点收尾等问题。其中删除功能的一部分就是查找功能，显示功能也是从链表的头结点遍历至最后一个，依次输出。（4） 实验结果与分析3 心得体会 本次数据结构实习我收获颇丰，以前学过c语言与c+也有经常上机，但以往都是偏向于程序整体的算法设计，没有像这次的实习这样是着重在线性表，链表结构的算法设计上面。这次上机实习，让我更加熟练了结构体及结构体指针的用法，线性表的设计等等，同时在这次实习中，引用，指针，地址这三个的用法曾一度让我混淆，在查阅书籍后才得以解决，也希望老师在课堂上有时间时给我们详细讲解一下，指针，地址，引用三者的使用。附录：顺序表源代码:#includeusing namespace std;#define maxsize 50typedef int TypeData;typedef struct TypeData datamaxsize;int n;SeqList;void makeSeq( SeqList &L) / 输入线性表数据 int m,n,k; cout请输入线性表长度m; for(n=0;nm;n+) cout请输入线性表数据L.datan; L.n=m; cout您输入的线性表为：endl; for(k=0;km;k+) coutL.datak ; coutendl;void showSeq(SeqList L) /输出线性表数据 int a=0; while(aL.n) coutL.dataa ; a+; coutendl;void insert(SeqList &L) /插入数据 int a,b,c,k; cout请输入插入的数及其插入的位置ab; if(b(L.n+1) cout不能在该位置插入b) L.datac=L.datac-1;c-; L.datab=k;void delate(SeqList &L) /删除数据 int wei; cout请输入想要删除数据的位置wei; if(weiL.n) cout不能在该位置删除endl;return; while(weiL.n) L.datawei-1=L.datawei; wei+; L.n=L.n-1;void find(SeqList L) /查找数据int a; cout请输入您想查找数的位置a; if(a(L.n) cout不能在该位置插入endl; return; cout该位置的数据为： L.dataa-1endl;void main() SeqList L; int xuanze; makeSeq(L); while(1) cout请选择功能endl; cout插入 1endl; cout删除 2endl; cout查找 3endl; cout显示 4endl; coutendl请输入xuanze; switch(xuanze) case 1: insert(L);break; case 2: delate(L);break; case 3: find(L);break; case 4: showSeq(L);break; default :break; 单链表源代码：#includeusing namespace std;typedef int DataType;typedef struct nodeDataType data;struct node *link;linknode,*linklist;linklist chushihua() linklist L; L=(linklist )malloc(sizeof(linknode); L-link=NULL; cout开辟空间成功，头结点建立endl; return L;void shuru(linklist &l) int a,k=0; cout请输入要存入的结点个数a; linklist p,q; p=l; while(p-link!=NULL) p=p-link;k+; for(int i=0;ia;i+) cout请输入数据q-data; q-link=p-link;p-link=q;p=q; void show(linklist l)cout链表数据为：link; while(p!=NULL) coutdatalink; coutendl; void find(linklist l) int m,i=0; cout请输入查找的结点m; linklist p; p=l-link; while(p&ilink;i+; if(!p) cout链表没有这么长,查找错误endl;return; cout查找结点的数据位： dataendl; void insert(linklist l) linklist p,q; int m,n,i=0; cout请输入您要插入的结点位置及插入的数据mn; p=l; while(p&ilink;i+; if(p=NULL) cout不能在该位置插入，插入错误data=n; q-link=p-link;p-link=q; void delate(linklist &l) linklist p; int m,n,i=0; cout请输入想要删除的结点位置m; p=l; while(p&ilink;i+; if(p=NULL) cout该结点不存在，删除错误link-data; cout被删除的结点元素为: nlink=p-link-link; void main() linklist L; int select; L=chushihua(); while(1) cout请选择功能endl; cout添加链表数据 1endl; cout插入链表数据 2endl; cout删