数据结构学习指导2(算法指导-线性表和树)

《数据结构学习指导2(算法指导-线性表和树)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构学习指导(2)—数据结构算法学习参考(线性表和树)1线性表(%1)线性表的定义n(n>=0)个元素的有限集合,(al,a2,…,ai-1,ai,ai+1,・.,an)。每个数据元素的类型是相同的，数据元素之间的相对位置是一维的(线性的)(%1)存储结构(1)顺序结构datatypea[size+l];//线性表的容量intn;//线性表的长度(2)链式结构typedefstruetnode{datatypedata;//数值域structnode*next;//扌&针域}node,*linklist;(%1)算法设计2.1设线性表存于a[loosize]的前n个分量中，且递增有序，将x

2、插入到线性表的适当位置，以保持线性表的有序性。设计思想：仃)查找x的插入位置i。从a[n]处开始，边比较边后移。⑵将x査入到a[i+l]中，表长加1。voidinsert(datatypea[],intn,datatypex){〃在有序农a[n]中插入x,并保持线性表的有序性if(n==size)cout«,zarrayoverflow^«endl;else{inti二n;while((i>=l)&&(x

3、删除从第i个元素起的k个元素。设计思想：将k个元素一次删除，即从i+k开始，每一元素前移k个元素位置。voiddelete_l(datatypea[],intn,inti,intk){〃删除线性表中从第i个元素起的k个元素if((k>=l)&&(i>=l)&&(i+kTUn)){for(j二i+k;j<二n;j++)a[j-k]=a[j];//前移k个元素n-=k;//表长-kelsecout«/z入口参数错误z/«endl;2.3已知两个线性表la和lb,且顺序存储，其值递增排列，要求将它们归并成一个新的有序表lc。设计思想：仃)当线性表la和线性表lb均未结束时，比较，将较小数存于线性表l

4、c;(2)若一线性表结束，将另一线性表存于lc。voidmerge_l(datatypela[],datatypelb[],datatype&lc[],intna,intnb,int&nc){//将长度为na的冇序表la和长度为nb的冇序表lb归并为一个长度为nc的冇序表lc//设lc表的存储空间足够大inti=l,j=l,k=0;//指针初始化while((i<=na)&&(j<=nb))//归并if(la[i]<=lb[jj)lc[++k]=la[i++];elselc[++k]二lb[j++];while(i<=na)lc[++k]二la[i++];//插入la的剩余段while(j<=

5、nb)lc[++k]=lb[j++];//插入lb的剩余段nc=k;//k为lc中元素个数}2.4一个有序表以顺序结构存储，删除该表中所有大于min且小于max的元素。设计思想：(1)首先找到第1个被删元素(大于min且小于max的元素)；(2)记住这个位置k;(3)从k+1开始将小于min或大于max的元素前移(要注意移动位置)，并计被删元素的个数nl(4)表长-nlVoiddelete_2(inta[],intn,intmin,intmax){//删除线性表中所有大于min且小于max的元素。intk=l,nl=0,j;while(k<=n&&(a[k]

6、

7、a[k]

8、+;//(l)找到第一个被删条件元素的位置kj二k+1;while(j<=n)if(a[j]<=min

9、

10、a[j]>=max)a[k++]=a[j++];//删除所有大于min且小于max的元素，也即将a[j]<=min

11、

12、a[j]>=max的元素前移else{nl++;j++;}//当min>min且a[k]

13、,V2,…,Vn)改变成(VW…),即删除原来序号为偶数的那些元素。2.7从顺序

14、表中删除垂复的元素，并使剩余元素间的相对次序保持不变。2.8从键盘输入一系列整数，建立一个长度为n的、不含垂复元素的顺序表。2.9在按元素值非降次序排列的顺序表中，找出垂复次数最多的元素。2.10两个值递增排列的有序表A和B,且顺序存储，将A和B归并成一个新的有序表C,要求C中元素值各不相同。2.11写出在带头结点的动态单链表结构上实现线性表操作LOCATE(L,X)和LENGTH(L)的算法LO