数据结构线性表实验报告

《数据结构》实验报告院系应用科技学院专业电子信息工程姓名陈高雪学号12035201005410级电信班2011年10月11日1.实验目的1.掌握线性表的基本运算。2.掌握顺序村存储的概念，学会对顺序存储数据结构进行操作。3.加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能力。2.需求分析要求用c语言编写一个演示程序，首先建立一个空表，然后根据用户选择，能够在线性表的任意位置实现插入元素、删除元素、初始化线性表、查找某一元素的在线性表中得位置。（1）建立线性表的功能输入的形式和输入的范围：调用出入函数，输入插入的位置和数值，用逗号隔开输出的形式：调用输出函数，按顺序输出线性表所插入的值，以及所对应功能的值。（2）插入功能输入的形式和输入值的范围：输入一个表示位置的正整数和一个表示插入元素值的正整数，两个正整数之间用逗号隔开，出入位置的和法取值范围是1sizesize+1。输出的形式：如果输入的参数合法，则按顺序显示插入后的线性表，否则显示错误。（3）删除功能输入的形式和输入值的范围：输入一个表示删除位置或要删除的元素值的正整数，删除位置或删除元素值的取值范围是1sizeesize+1或线性表中的元素，否则显示参数错误的信息。输出的形式：如果输入参数合法，则按顺序显示删除后线性表中的各个元素值，否则显示参数错误的信息。（4）查找功能输入的形式和输入值的范围：输入一个要查找的元素值，元素值的合法取值范围是正整数。输出的形式：如果存在要查找的元素，则显示要查找元素的位置，否则显示参数错误信息。3.概要设计（1）为了实现上述程序功能，需要第一一个简化的线性表抽象数据类型：TypedefstructLinearList{Int*list;Intsize;IntMAXSIZE;}List;基本操作：初始化线性表ListInit(L)操作前提：L是一个未初始化的线性表操作结果：将L初始化成一个空的线性表向空表指定位置插入元素ListInsert(L)操作前提：L是一个还有位置的线性表操作结果：将元素插入到指定位子并输出线性表删除指定元素值ListDelete_1（L）操作前提：线性表L存在操作结果：将线性表中指定的元素值删除，并输出线性表删除指定位置的元素值ListDelete_2（L）操作前提：线性表L存在操作结果：将线性表中指定位置的元素值删除，并输出线性表查找线性表中的元素ListFind（L）操作前提：线性表L存在操作结果：在线性表L中查找指定元素e，若存在该元素返回该元素在表中的位置，否则提示错误输出线性表元素OutputList(L)操作前提：线性表存在操作结果：输出整线性表L的所有元素值（2）本程序共有6函数：主函数main()初始化线性表函数InitList()输出函数OutputList()插入函数ListInsert()删除函数ListDelete()查找函数ListFind()各函数的关系如下：主函数Main()调用初始化线性表函数InitList()、插入函数ListInsert()、删除函数ListDelete()、查找函数ListFind()、查找函数ListFind()插入函数ListInsert()调用输出函数OutputList(L)删除函数ListDelete()调用输出函数OutputList(L)查找函数ListFind()调用输出函数OutputList(L)（3）主函数的伪码Main(){定义一个字符参数ch;定义整形元素位置参数i；定义整形参数e,j=1;说明一个线性表L;循环做下面处理，直到读入的为‘y’时推出：{根据具体选项，读入需要的数据，做下面的选择处理，知道循环结束：{根据所选择选项调用相关的函数进行处理，然后输出处理后的线性表以及所要执行的内容。}}}4.详细设计采用线性表实现概要设计中的定义的抽象数据类型，有关数据数据类型和伪码算法定义如下：（1）类型定义typedefstructLinearList{int*list;intsize;intMAXSIZE;}List;（2）基本操作的伪码算法初始化voidInitList(List&L){构造一个空表L；定义空表长度为0；初始存储空间的容量；}插入操作voidListInsert(List&L,inti,inte){Int*p；判断位置i是否合法不合法返回空；判断当前容量是否已满{申请一个新的基止newbase;L.list=newbase;增加存储容量；}定义插入位置*q；p=q;--p)*(p+1)=*p;插入元素e；表长加1；}删除操作intListDelete_1(List&L,inte,int&i){定义三个指针*p,*q,*m;P=L.list;;循环做下面处理{If(*p=e);{m=p;q=L.list+L.size-1;被删除元素之后的元素左移；表长减1；continue;p++;}i++;}return1；}查找操作intListFind(ListL,inte)/*在顺序线性表L中查找第1个值与e满足compare()的元素的位序。若找到，则返回其在L中的位序，否则返回0。*/{定义第一元素的存储位置为1；P=首元素的地址；While（i不能超过表长）++I;if(i=L.size)returni;elsereturn0;}5.使用说明程序名为实验1.exe，程序执行过程如下：运行程序显示如下菜单：printf(\t\t\t---线性表---\n);printf(\n\t\t\t********************************);printf(\n\t\t\t*1-----初始化*);printf(\n\t\t\t*2-----插入元数值*);printf(\n\t\t\t*3-----删除指定元素值*);printf(\n\t\t\t*4-----删除指定位置*);printf(\n\t\t\t*5-----查找线性表中的元素*);printf(\n\t\t\t*6-----输出线性表元素*);printf(\n\t\t\t*0-----退出*);printf(\n\t\t\t********************************\n);printf(请选择菜单号(0-6):);用户输入0~6的数字，选择执行相应的功能。每执行一次功能，就会显示执行的结果以及执行后线性表的内容。选择0：提示是否退出程序，输入y退出，输入n返回菜单。选择1：初始化线性表选择2：提示“请输入位置i和数值e：”，要求用户输入一个表示插入元素位置的和一个表示插入元素的正整数，两个数之间用空格隔开。如果插入合法，按顺序输出线性表，否则提示错误！选择3：提示“请输入要删除的元素值e：”，要求用户输入一个表示删除元素的正整数，删除元素的合法范围是正整数。如果输入参数合法，按顺序输出线性表，否则提示错误！选择4：提示“请输入要删除的指定位置i:”，要求用户输入一个表示删除位置的正整数，删除位置的合法范围是1到当前线性表的长度。如果输入参数合法，按顺序输出线性表，否则提示错误！选择5：提示“请输入线性表中要查找的元素e:”，要求用户输入一个要查找的元素值，元素的合法范围是正整数。如果输入元素值合法，输出所查找元素值在线性表中的位置，否则提示错误！选择6：直接输出整个线性表。6.测试结果程序运行显示一下菜单：---线性表---*********************************1-----初始化**2-----插入元数值**3-----删除指定元素值**4-----删除指定位置**5-----查找线性表中的元素**6-----输出线性表元素**0-----退出*********************************请选择菜单号(0-6):（1）初始化操作：选择1初始化线性表屏幕提示“初始化成功！”再次提示选择菜单（2）插入操作：选择2屏幕提示“请输入位置i和数值e:”输入11屏幕显示输出线性表元素:1插入成功！屏幕显示选择菜单选择2屏幕提示“请输入位置i和数值e:”输入22屏幕显示输出线性表元素:1插入成功！屏幕显示选择菜单选择2屏幕提示“请输入位置i和数值e:”输入33屏幕显示输出线性表元素:1插入成功！屏幕显示选择菜单选择2屏幕提示“请输入位置i和数值e:”输入55屏幕显示插入位置错误！输出线性表元素:1屏幕显示选择菜单（3）删除指定元素值操作：选择3屏幕提示“请输入要删除的元素值e:”输入2后，屏幕显示输出线性表：13删除成功！再次显示选择菜单选择4屏幕提示“请输入要删除的指定位置i:”输入1后，屏幕显示输出线性表：3删除成功！再次显示选择菜单（4）删除指定位置元素操作：选择4屏幕显示“请输入要删除的指定位置i:”输入2屏幕显示删除成功！输出线性表元素有：13（5）查找操作：选择5屏幕显示“请输入线性表中要查找的元素e:”输入3，屏幕显示该元数值在线性表中第3位输出线性表元素:123输入4，屏幕显示该元素值不在线性表中，并输出线性表元素：123再次回到选择菜单（6）显示：选择6屏幕显示线性表元素有:123再次回到选择菜单（7）退出：选择0，屏幕提示“是否真的退出程序y/n:”输入n，屏幕显示请重新选择...:再次显示程序选择菜单输入y，屏幕显示退出程序！Pressanykeytocontinue