文档介绍：该【数据结构与算法分析课后习题答案 】是由【幸福人生】上传分享，文档一共【26】页，该文档可以免费在线阅读，需要了解更多关于【数据结构与算法分析课后习题答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构与算法分析课后习题答案
数据结构与算法分析课后习题答案
【篇一:《数据结构与算法》课后习题答案】
>
。(√)
,但同一线性表中的数据元素具有相同的特性,因此属于同一数据对象。(√)
,逻辑上相邻的元素在物理位置上不一定相邻。(√)
,插入和删除时移动元素的个数与该元素的位置有关。(√)
。(√)
[arrsize]的前elenum个分量中,且递增有序。试写一算法,将x插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构(顺序存储的思想是用物理上的相邻表示逻辑上的相邻,不一定将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储,分配的存储空间是固定大小的,所以首先确定是否还有存储空间,若有,则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,(也可以从高下标端开始一边比较,一边移位)然后插入x,最后修改表示表长的变量。
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[low]=r[high];
r[high]=k;
}
}
}
,设计一个算法,用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表:
(a1,a2,…,am,b1,b2,…,bn)改变为:
(b1,b2,…,bn,a1,a2,…,am)。
【提示】比较m和n的大小,若mn,则将表中元素依次前移m次;否则,将表中元素依次后移n次。
voidprocess(seqlist*l,intm,intn)
{if(m=n)
for(i=1;i=m;i++)
{x=l-data[0];
for(k=1;k=l-last;k++)
l-data[k-1]=l-data[k];
l-data[l-last]=x;
}
elsefor(i=1;i=n;i++)
{x=l-data[l-last];
for(k=l-last-1;k=0;k--)
l-data[k+1]=l-data[k];
l-data[0]=x;}
}
,试写一算法,将值为x的结点插入到表l中,使得l仍然递增有序,并且分析算法的时间复杂度。
linklistinsert(linklistl,intx)
{p=l;
while(p-nextxp-next-data)
p=p-next;/*寻找插入位置*/s=(lnode*)malloc(sizeof(lnode));/*申请结点空间*/s-data=x;/*填装结点*/
s-next=p-next;
p-next=s;/*将结点插入到链表中*/return(l);
}
(递增)的单链表a和b,编写算法将它们合并成一个链表c而不改变其排序性。
linklistcombine(linklista,linklistb)
{c=a;
rc=c;
pa=a-next;/*pa指向表a的第一个结点*/
pb=b-next;/*pb指向表b的第一个结点*/
free(b);/*释放b的头结点*/
while(papb)/*将pa、pb所指向结点中,值较小的一个插入到链表c的表尾*/if(pa-datapb-data)
{rc-next=pa;
rc=pa;
pa=pa-next;
}
else
{rc-next=pb;
rc=pb;
pb=pb-next;
}
if(pa)rc-next=pa;
elserc-next=pb;/*将链表a或b中剩余的部分链接到链表c的表尾*/
return(c);
}
,既无头结点也无头指针,p为指向该链表中某一结点的指针,编写算法删除该结点的前驱结点。
【提示】利用循环单链表的特点,通过s指针可循环找到其前驱结点p及p的前驱结点q,然后可删除结点*p。
vioddelepre(lnode*s)
{lnode*p,*q;
p=s;
while(p-next!=s)
{q=p;
p=p-next;
}
q-next=s;
free(p);
}
,其元素递增排列,编写算法求出a和b的交集c,要求c同样以元素递增的单链表形式存储。
【提示】交集指的是两个单链表的元素值相同的结点的集合,为了操作方便,先让单链表c带有一个头结点,最后将其删除掉。算法中指针p用来指向a中的当前结点,指针q用来指向b中的当前结点,将其值进行比较,两者相等时,属于交集中的一个元素,两者不等时,将其较小者跳过,继续后面的比较。
linklistintersect(linklista,linklistb)
{lnode*q,*p,*r,*s;
linklistc;
c=(lnode*)malloc(sizeof(lnode));
c-next=null;
r=c;
p=a;
q=b;
while(pq)
if(p-dataq-data)p=p-next;
elseif(p-data==q-data)
{s=(lnode*)malloc(sizeof(lnode));
s-data=p-data;
r-next=s;
r=s;
p=p-next;
q=q-next;
}
elseq=q-next;
r-next=null;
c=c-next;
returnc;
}
,每个结点中除有prior、data和next域外,还有一个访问频度freq域,在链表被起用之前,该域的值初始化为零。每当在链表进行一次locata(l,x)运算后,令值为x的结点中的freq域增1,并调整表中结点的次序,使其按访问频度的非递增序列排列,以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的locata(l,x)算法。
【提示】在定位操作的同时,需要调整链表中结点的次序:每次进行定位操作后,要查看所查找结点的freq域,将其同前面结点的freq域进行比较,同时进行结点次序的调整。typedefstructdnode
【篇二:数据结构课后习题答案】
lass=txt>高等学校精品资源共享课程