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

数据结构学习指导（2）——数据结构算法学习参考（线性表和树）1线性表（一）线性表的定义n（n=0）个元素的有限集合，(a1,a2,...,ai-1,ai,ai+1,..,an)。每个数据元素的类型是相同的，数据元素之间的相对位置是一维的(线性的)（二）存储结构（1）顺序结构datatypea[size+1];//线性表的容量intn;//线性表的长度（2）链式结构typedefstructnode{datatypedata;//数值域structnode*next;//指针域}node,*linklist;（三）算法设计2.1设线性表存于a[1。。size]的前n个分量中,且递增有序，将x插入到线性表的适当位置,以保持线性表的有序性。设计思想：(1)查找x的插入位置i。从a[n]处开始，边比较边后移。(2)将x查入到a[i+1]中，表长加1。voidinsert(datatypea[],intn,datatypex){//在有序表a[1]..a[n]中插入x,并保持线性表的有序性if(n==size)cout”arrayoverflow”endl;else{inti=n;while((i=1)&&(xa[i])){a[i+1]=a[i];i--;}//(1)找插入位置,同时元素后移a[i+1]=x;n++;//(2)插入x,表长+1}}2.2已知线性表存于a[1。。size]中的前n个分量中，删除从第i个元素起的k个元素。设计思想：将k个元素一次删除，即从i+k开始，每一元素前移k个元素位置。voiddelete_1(datatypea[],intn,inti,intk){//删除线性表中从第i个元素起的k个元素if(（k=1）&&（i=1）&&（i+k-1=n）){for(j=i+k;j=n;j++)a[j-k]=a[j];//前移k个元素n-=k;//表长-k}elsecout”入口参数错误”endl;}2.3已知两个线性表la和lb，且顺序存储，其值递增排列，要求将它们归并成一个新的有序表lc。设计思想：(1)当线性表la和线性表lb均未结束时，比较，将较小数存于线性表lc;(2)若一线性表结束，将另一线性表存于lc。voidmerge_1(datatypela[],datatypelb[],datatype&lc[],intna,intnb,int&nc){//将长度为na的有序表la和长度为nb的有序表lb归并为一个长度为nc的有序表lc//设lc表的存储空间足够大inti=1,j=1,k=0;//指针初始化while(（i=na）&&（j=nb）)//归并if(la[i]=lb[j])lc[++k]=la[i++];elselc[++k]=lb[j++];while(i=na)lc[++k]=la[i++];//插入la的剩余段while(j=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的元素前移（要注意移动位置），并计被删元素的个数n1(4)表长-n1Voiddelete_2(inta[],intn,intmin,intmax){//删除线性表中所有大于min且小于max的元素。intk=1,n1=0,j;while(k=n&&(a[k]min||a[k]max))k++;//(1)找到第一个被删条件元素的位置kj=k+1;while(j=n)if(a[j]=min||a[j]=max)a[k++]=a[j++];//删除所有大于min且小于max的元素,也即将a[j]=min||a[j]=max的元素前移else{n1++;j++;}//当minmin且a[k]max时，记录其元素的个数n1n-=n1;//表长-n1}思考题：2.5将顺序存储的线性表（v1,v2,…,vn）改变成(vk+1,vk+2,…,vn,v1,v2,…,vk)。2.6将顺序存储的线性表（v1,v2,…,vn）改变成(v1,v3,v5,…)，即删除原来序号为偶数的那些元素。2.7从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。2.8从键盘输入一系列整数，建立一个长度为n的、不含重复元素的顺序表。2.9在按元素值非降次序排列的顺序表中，找出重复次数最多的元素。2.10两个值递增排列的有序表A和B，且顺序存储，将A和B归并成一个新的有序表C，要求C中元素值各不相同。2.11写出在带头结点的动态单链表结构上实现线性表操作LOCATE(L,X)和LENGTH(L)的算法LOCATE：用x与每一结点的数据域的值进行比较，若等于x，表示查找成功，否则，查找失败。linklistlocate(listlink&ha,elemypex){//ha:带头结点的单链表的头指针{node*p=ha-next;//p:指向第一个元素结点while(p&&p-data!=x)p=p-next;//当p不空并且p-data不等于x时,p后移return(p);//成功:p;失败:p=NULL}LENGTH:逐一访问每一结点并计数,即可得此链表的长度。intlength(listlink&ha){//ha:带头结点的单链表的头指针{node*p=ha;//p:指向头结点intlen=0;while(p-next){p=p-next;++len;}//当p不空x时,访问其结点,并计数return(len);//len:即为此链表的长度}2.12已知ha和hb分别指向两个单链表的头结点,且头结点的数据域(整型)中存放链表的长度,写一算法将这两个链表接在一起,并要求以尽可能短的时间完成。设计思想：(1)比较ha和hb两链表,找较短链；(2)沿较短链找到最后一个结点；(3)将两链连接上。voidconcat(linklistha,linklisthb,linklist&hc)if(ha-datahb-data){p=ha;q=hb-next}else{p=hb;q=ha-next}//p指向较短链,q指向较长链hc=p;//将头指针指向较短链,hc:新生成的链表的头指针,利用原空间while(p-next)p=p-next;//沿较短的链表查找至链表尾端(当p-next==NULL),若p不空,则p后移,直到最后一个结点p-next=q；//两链表链接上}2.13已知线性表中的元素按值递增排列,并以单链表作存储结构，写一高效算法,删除表中所有值大于min且小于max的元素(若表中存在这样的元素)。设计思想：(1)从第一个结点开始找其值min的结点p(它的前趋结点为pre)；(2)保存pre,从p开始找所有值max的结点,并删除每个这样的p结点；(3)pre-next指向p。voiddelete_3(linklist&h,intmin,intmax){//h:带头结点的单链表的头指针node*pre=h,*p=h-next;while(p&&p-data=min){pre=p;p=p-next;}//p:其值min的结点,pre是p的前趋while(p&&p-datamax){u=p;p=p-next;deleteu;}//删除所有的其值min并且max的结点ppre-next=p;}2.14已知线性表中的元素按值递增排列,并以单链表作存储结构，写一高效算法,删除表中的多余元素,使得运算后的线性表中所有元素的值均不相同。设计思想：从第一个结点开始,每一结点的值与后一结点的值作比较,若相等,则删除后一结点,直至整个链表结束。voiddelete_4(linklist&h){//h:带头结点的单链表的头指针linklistu,p=h-next;while(p-next)if(p-data==p-next-data){u=p-next;p-next=u-next;deleteu;}//删除元素的值相同值的结点elsep=p-next;//p后移}2.15以单链表作存储结构,实现线性表就地逆置的算法,即将线性表(a1,a2,......an)==(an,......,a2,a1)设计思想：(1)首先建立一个空链表(逆置后链表的初值)；(2)取出原链表(a1,...,an)中的一结点；(3)插入到新链表(an,...,a1序)的表头处;(4)重复(2)和(3)步,直到原链表空止。Voidexchange(linklistha,linklist&hb){//(a1,a2,......an)==(an,......,a2,a1)//ha:原链表的头指针，hb：逆置后新链表的头指针。两链表均不带头结点node*p;hb=NULL;//新链表置初值while(ha){p=ha;ha=ha-next;//从原链表的表头中取出一个结点pp-next=hb;hb=p;//将p插入到新链表的表头处}}2.16设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,写一算法将A表和B表归并成一个按元素值递增有序排列(表中各值均不相同)的线性表C。设计思想：(1)当A表和B表都不空时,进行比较,将较小数链入C表表尾,以保证其递增性;(2)若某一链表空,将另一链表接在C表之后。voidmerge_2(linklistha,linklisthb,linklist&hc){//ha,hb是两个链表（有序表）的头指针,hc是归并后的新链表（有序表）的头指针，均带头结点node*pa,*pb,*rc;pa=ha-next;pb=hb-next;hc=ha;rc=hc;//利用原链表A的头结点，得新链表C的头结点,hc:头指针,rc:尾指针while(pa&&pb)if(pa-datapb-data){s=pa;pa=pa-next;}elseif(pa-data==pb-data){s=pa;pa=pa-next;pb=pb-next;}else{s=pb;pb=pb-next;}rc-next=s;rc=s;}//当A表和B表都不空时,进行比较,将较小数链入C表表尾,以保证其递增性;if（!pa）{rc-next=pb；else{rc-next=pa;deletehb;}2.16已知A、B和C为以链表存储的三个递增有序的线性表，对A作如下运算：删除那些在B中出现又在C中出现的元素。设计思想:从A表中取出每一个元素p-data，检查是否出现在B表和C表中，是，则删除P。注意：应保留p的前趋。voiddelete_5(linklist&ha,linklisthb,linklisthc){//ha,hb,hc分别为A链、B链和C链的头指针,3个链表均带头结点node*pre,*p,*pb,*pc;pre=ha;p=ha-next;//pre:p的前趋pb=hb-next;pc=hc-next;//pb,pc:总指向hb,hc链的最后一个已考查的结点while(p)//A表不空{x=p-data;while(pb&&pb-datax)pb=pb-next;//当pb不空时，找等于x的结点pbwhile(pc&&pc-datax)pc=pc-next;//当pc不空时，找等于x的结点pcif((pb&&pb-data==x)&&(pc&&pc-data==x))//x在B中出现同时又在c中出现{pre-next=p-next;free(p);//删除pp=pre-next//p后移，考察下一结点}else{pre=p;p=p-next;}//p后移，考察下一结点}}2.17已知由单链表表示的线性表中，含有三类字符的数据元素（字母、