欢迎来到天天文库
浏览记录
ID:46690149
大小:145.50 KB
页数:17页
时间:2019-11-26
《数据结构学习指导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)&&(x3、删除从第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均未结束时,比较,将较小数存于线性表l4、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]<=min9、10、a[j]>=max)a[k++]=a[j++];//删除所有大于min且小于max的元素,也即将a[j]<=min11、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
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]<=min9、10、a[j]>=max)a[k++]=a[j++];//删除所有大于min且小于max的元素,也即将a[j]<=min11、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
6、
7、a[k]8、+;//(l)找到第一个被删条件元素的位置kj二k+1;while(j<=n)if(a[j]<=min9、10、a[j]>=max)a[k++]=a[j++];//删除所有大于min且小于max的元素,也即将a[j]<=min11、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
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
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
此文档下载收益归作者所有