数据结构实验报告王立鑫

《数据结构实验报告王立鑫》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验报告题目：线性表的应用举例班级：计算数学14-1姓名王立鑫学号：140108010041成绩：实验一线性表的应用举例一、实验目的耍求学牛必须掌握线性表的顺序存储和链式存储两种结构，在此基础上实现插入、删除、查找等基本操作。二、实验内容及步骤1.求两个线性表La和Lb的并集La=LaULb（要求：“就地运算”，运算结果仍然存放在La中）输入：线性表La、线性表Lb输出：变化了的Launion（&La,Lb）处理方法：扩大线性表La,将存在于线性表Lb阳不存在于线性表La中的数据元素插入到线性表La屮去步骤：1）从线性表L

2、b屮依次取得每个数据元素；2）依值在线性表La屮进行杳访；3）若不存在，则插入之。2.已知线性表La和Lb中的数据元素按值非递减有序排列，要求将La和Lb归并成一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。输入：线性表La、线性表Lb（均按值非递减有序排列）输出：Lc（按值非递减有序排列）mergefLa,Lb,&Lc）处理方法：由La和Lb均按值非递减有序排列，可设置两个位直指示器i和j,分别指向La和Lb中的当前元素,初始均指向第1个。比较i和j所指向的元素ai和bj,选取值小的插入到Lc的尾部，并使相应的位置指

3、示器向后移。步骤：1）从La和Lb中各取一个元素进行比较，小者插入Lc中，相应指示器增12）若La插入完毕，将Lb中剩余元素全部插入Lc中3）若Lb插入完毕，将La中剩余元素全部插入Lc中3.创建单链表一-尾插法输入：键盘输入输出：带头结点的单链表L处理方法：待插结点机插入到最后一个结点之后。步骤：1）获得最后一个结点的位置，使P指向该结点2）p->next二newLNode;3)p=p->next;4)cin»p->data;5)p->next=NULL;分析:耍想获取最后一个结点的位置，必须从头指针开始顺着next链搜索链表的

4、全部结点，该过程的时间复杂度是0(斤)。如果每次插入都按此方法获取最后一个结点的位置，则整个创建算法的时间复杂度为0(/72)o四.编写程序1.求两个线性表La和Lb的并集#includeusingnamespacestd;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintElemType;typedefintStatus;#defineOK1#defineOVERFLOW0#defineERROR0typedefstruct//定义线性表{Elem

5、Type*elem;〃存储空间棊地址intlength;〃当前表长intlistsize;〃当前表的容量}Sq_List;StatuslnitList(Sq_List&L)〃线性表的初始化，初始化一个空表{L.elem=newElemType[LIST_INIT_SIZE];if(!L.elem)returnOVERFLOW;〃申请失败L.length=O;L.listsize=LIST_INIT_SIZE;returnOK;}intListLength(Sq_ListL)〃计算线性表当前元素个数intj=0;while(j

6、zeof(L.elem))if(L.elem[j]=='O')break;j++；}Llength=j;returnL」ength;}StatusGetElem(Sq_ListL,inti,ElemType&e)〃获取第i个元素{if(L.length==O)returnERROR;if(i

7、

8、i>L.length)returnERROR;//i非法elsee=L.elem[i-l];returnOK;}intLocateElem(Sq_ListL,ElemTypee)〃定位元素e的位序{if(L.length==O)ret

9、urnERROR;inti=l;while(L.elem[i-l]!=e&&i<=L.length){i++；}returniv二L」ength?i:0;}StatusListlnsert(Sq_List&Lzinti,ElemTypee)〃在第i个元素之前插入元素e{intj=L」ength;if(i>j+l

10、

11、i=L.listsize){L.listsize+=USTINCREMENT;ElemType*p=newElemType[L」istsize];if(!p)return

12、OVERFLOW;forfintk=O;kvL.length;k++)〃将元素移至新地址处p[k]=L.elem[k];deleteL.elem;L.elem=p;}while(j>=i){Lelem[j]=L.elem[j-l];J-；}L.el