实验指导-线性表 (1).doc

实验一 线性表的应用一、实验题目 线性表的应用 二、实验课时 2课时 三、实验目的 1掌握线性表的概念、特点；2熟悉线性表的两种存储结构：顺序存储、链表存储，以及基于两种存储结构的相关运算的实现；3掌握线性表的相关应用问题的程序设计方法，培养分析问题、解决问题的能力。 四、实验内容和要求1、附录所列代码用于验证顺序表的基本操作，实现了顺序表的初始化、创建、判空、输出、按值查找、按序号查找、插入、删除等基本功能。代码中包含至少五处错误。请编辑，调试，修改该代码，直至正确运行，并保留代码运行的界面截图。填写实验报告时，本题不需提交代码，只用贴运行结果截图。2、请根据如下存储结构定义改写第一题的代码：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structElemType *elem; int length; int listsize;SqList;要求：（1）、实现顺序表的初始化、创建、判空、输出、按值查找、插入、删除、销毁共8项功能。（2）、实现清除顺序表中的重复元素的功能，即删除重复元素中的多余元素，只保留其中序号最小的一个。例如:顺序表(2,4,4,3,2,4)清除重复元素后变为(2,4,3)。提示：让一个整型变量 i 从头到尾扫描顺序表中的元素序号，当i定值于一个元素序号后，再用另一个整型变量 j 反向扫描元素序号n-1,i+1。当 j 定值于某一个序号后，就可以比较ai与aj，若ai=aj，则删除aj。所以，算法可用二重循环实现，外、内层的循环控制变量分别为i和j。（3）、要求实现顺序表达的划分功能，即将顺序表 (a1，a2，. ，an) 重新排列为以 a1 为界的两部分：a1 前面的值均比 a1 小，a1 后面的值都比 a1 大 。a1 也称为基准。例如：顺序表（25,30,20,60,10,35,15），划分后结果为（15,10,20,25,30,60,35）。提示：从第二个元素开始到最后一个元素，逐一向后扫描：(1)当前数据元素 ai比 a1 大时，表明它已经在 a1 的后面，不必改变它与 a1 之间的位置，继续比较下一个。(2)当前结点若比 a1 小，说明它应该在 a1 的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。（4）、以上所有功能可在同一个源代码中通过不同的函数实现。填写实验报告时，本题需提交源代码及运行结果截图（运行界面截图中所用测试数据不允许使用题目中举例用数据）。3、基于如下定义编制程序，验证单链表的基本运算。typedef struct LNode int data; struct LNode *next; LNode,*LinkList;要求：（1）、要求编制系统菜单，菜单中至少包含五大功能项：1、单链表的创建；2、结点的插入；3、结点的删除；4、统计结点个数；5、退出系统。参考截图：图1（2）、单链表要带头结点；（3）、结点的插入：要求在值为x的结点之前插入值为y的结点，x，y由用户通过键盘输入；（4）、结点的删除：要求删除值为x的结点，x由用户通过键盘输入；（5）、结点的统计：不计头结点；（6）、要求系统界面友好，所有用户输入信息需讨论数据的合法性，输出结果的提示信息描述完备、清晰。（7）、填写实验报告时，本题要提交源代码及运行界面截图（不允许使用与图1相同的测试数据）。4、采用顺序存储结构或链式存储结构完成集合(A-B)(B-A)的运算。假设集合A=（c,b,e,g,f,d）,B=(a,b,n,f),则(A-B)(B-A)=（c,e,g,d,a,n）。参考运行结果：图2要求：提交实验报告时，本题需提交源代码及运行结果截图（不允许使用与图2相同的测试数据）。五、实验报告提交内容（1）按附录二格式填写实验报告。（2）填写实验报告时可酌情书写实验小结或实验心得。注意：不是写给老师看的，是写给自己看的，日后备查或参考之用。（3）实验课结束后的下一周最后一次课之前将实验报告电子档交各班学习委员，文件名格式为：学号最后两位姓名下划线线性表实验.doc，例如：35张小梅_线性表实验.doc（文件名格式错扣分）。学习委员收齐全班报告后放在同一个文件夹中，压缩后发我QQ邮箱：363540268，压缩文件的文件名格式为：班级名线性表实验报告，例如：软件Q1341线性表实验报告。附录一：#include #define MaxSize 100#define NULL 0typedef struct sqlistint dataMaxSize; int length;void InitList(SqList *l)l=new SqList; l-length=0;void CreatList(SqList *l,int a,int n)int i; for(i=0;idatai=ai; l-length=n;int ListEmpty(SqList *l)return(l-length=0);void DispList(SqList *l)int i; if(ListEmpty(l) return; for(i=0;ilength;i+) coutdatai ; coutendl;int GetElem(SqList *l,int i,int m)if(il-length) return 0; m=l-datai-1; return 1;int LocateElem(SqList *l,int k)int i=0; while(ilength)&(l-datai=k) i+; if(i=l-length) return 0; else return i+1;void DestroyList(SqList *&l)delete(l);void main()SqList *L=NULL; int num,i,a100,j,e,k,v; InitList(L); couthow many elements?num; coutinput:endl; for(i=0;iai; CreatList(L,a,num); coutThe list is:endl; DispList(L); coutsearch:num?j; if(!GetElem(L,j,e) coutnum error!endl; else coutthe num of jis:eendl; coutsearch:value?k; v=LocateElem(L,k); if(!v) coutnot exist!endl; else coutkis num of vendl; DestroyList(L); coutThe list is destroied!end