文档介绍：数据结构与算法分析课后习题答案【篇一:《数据结构与算法》课后习题答案】>。(√),但同一线性表中的数据元素具有相同的特性,因此属于同一数据对象。(√),逻辑上相邻的元素在物理位置上不一定相邻。(√),插入和删除时移动元素的个数与该元素的位置有关。(√)。(√)[arrsize]的前elenum个分量中,且递增有序。试写一算法,将x插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构(顺序存储的思想是用物理上的相邻表示逻辑上的相邻,不一定将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储,分配的存储空间是固定大小的,所以首先确定是否还有存储空间,若有,则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,(也可以从高下标端开始一边比较,一边移位)然后插入x,最后修改表示表长的变量。intinsert(datatypea[],int*elenum,datatypex)/*设elenum为表的最大下标*/{if(*elenum==arrsize-1)return0;/*表已满,无法插入*/else{i=*elenum;while(i=0a[i]x)/*边找位置边移动*/{a[i+1]=a[i];i--;}a[i+1]=x;/*找到的位置是插入位的下一位*/(*elenum)++;return1;/*插入成功*/}}时间复杂度为o(n)。,其元素值非递减有序排列,编写一个算法删除顺序表中多余的值相同的元素。【提示】对顺序表a,从第一个元素开始,查找其后与之值相同的所有元素,将它们删除;再对第二个元素做同样处理,依此类推。voiddelete(seqlist*a){i=0;while(ia-last)/*将第i个元素以后与其值相同的元素删除*/{k=i+1;while(k=a-lasta-data[i]==a-data[k])k++;/*使k指向第一个与a[i]不同的元素*/n=k-i-1;/*n表示要删除元素的个数*/for(j=k;j=a-last;j++)a-data[j-n]=a-data[j];/*删除多余元素*/a-last=a-last-n;i++;}},从一个给定的顺序表a中删除值在x~y(x=y)之间的所有元素,要求以较高的效率来实现。【提示】对顺序表a,从前向后依次判断当前元素a-data[i]是否介于x和y之间,若是,并不立即删除,而是用n记录删除时应前移元素的位移量;若不是,则将a-data[i]向前移动n位。n用来记录当前已删除元素的个数。voiddelete(seqlist*a,intx,inty){i=0;n=0;while(ia-last){if(a-data[i]=xa-data[i]=y)n++;/*若a-data[i]介于x和y之间,n自增*/elsea-data[i-n]=a-data[i];/*否则向前移动a-data[i]*/i++;}a-last-=n;},每个元素是一个字符,现存于向量r[n]中,试写一算法,使r中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间,元素移动次数最小。【提示】对线性表进行两次扫描,第一次将所有的字母放在前面,第二次将所有的数字放在字母之后,其它字符之前。intfch(charc)/*判断c是否字母*/{if(c=ac=z||c=ac=z)return(1);elsereturn(0);}intfnum(charc)/*判断c是否数字*/{if(c=0c=9)return(1);elsereturn(0);}voidprocess(charr[n]){low=0;high=n-1;while(lowhigh)/*将字母放在前面*/{while(lowhighfch(r[low]))low++;while(lowhigh!fch(r[high]))high--;if(lowhigh){k=r[low];r[low]=r[high];r[high]=k;}}low=low+1;high=n-1;while(lowhigh)/*将数字放在字母后面,其它字符前面*/{while(lowhighfnum(r[low]))low++;while(lowhigh!fnum(r[high]))high--;if(lowhigh){k=r[low];r[lo