数据结构（C语⾔版）习题解答
1.3设n是正整数。试写出下列程序段中⽤记号“△”标注的语句的频度：
(2) i=1; k=0;
do {
△k+=10*i;
i++;
}while(i<=n-1)
当n=1时，执⾏1；
当n>=2时，执⾏n-1次；
(3)i=1; k=0;
do {
△k+ = 10*i; i++;
}while(i==n);
当n=2时，执⾏2次；
当n!=2时，执⾏1次；
(4) i=1; j=0;
while(i+j≤n) {
△if(i
}
执⾏n次；
(5) x=n; y=0; //n是不⼩于1的常数
while(x>=(y+1)*(y+1)){
△y++;
}
执⾏向下取整)
(6) x=91; y=100;
while ( y>0 )
△if(x>100) { x-=10; y--; }
else x++ ;
}
If语句执⾏100次
(7) for( i=0; i
for( j=i; j
for( k=j; k
△x+=2;
过程：n1n1
i0j i
n(n1)(n2) (n j)
6
--==
++ -=
∑∑
第⼆章
2.3 已知顺序表La中数据元素按⾮递减有序排列。试写⼀个算法，将元素x插到La的合适位置上，保持该
表的有序性。思路：先判断线性表的存储空间是否满，若满返回Error；否则从后向前先移动数据，到合适的位置插⼊。
Status Insert_SqList(SqList &La,int x)//把x 插⼊递增有序表La 中
{
if(La.length==La.listsize) return ERROR;
for(i=La.length-1;La.elem[i]>x&&i>=0;i--)
La.elem[i+1]=La.elem[i];
La.elem[i+1]=x;
La.length++;
return OK;
}//Insert_SqList
2.5 试写⼀个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表
（a
1,a
2
, ..., a
n-1
,a
n
）逆置为(a
n
,a
n-1
,
..., a
2
,a
1
//思路就是两个指⽰变量i，j同时分别从顺序表的开始和结尾处相向改变
void reverse(SqList &A)//顺序表的就地逆置
{
ElemType p;
for(i=1,j=A.length;i
{
//A.elem[i]<->A.elem[j];
p=A.elem[i];
A.elem[i[=A.elem[j];
A.elem[j]=p;
}
}//reverse
2.7 已知线性表L采⽤顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）L中数据元素⽆序排列；(2)L中数据元素⾮递减有序排列。
数据结构与算法c++版 pdf
void Delete_SameElem(SqLink &L, int L.length){ //内层循环移动参数，中层循环寻相同元，外层循环遍历整个表
int i=0; int j=i+1; int length=L.length;
while(i
for(j=i+1;j
if(L.Elem[j]==L.Elem[i]){//
for(k=j; k
L.Elem[k]=L.Elem[k+1];
length--;
j--;//移动元素后，由于少了⼀个元素，因此要减1
}
}//end if
If(L.Elem[j]>L.Elem[i]) break;//第⼆⼩问添加此句
}//end for
}//end while
}//end functoion
2.8 已知线性表L采⽤链式结构存放。对两种不同情况分别写出算法，删除L中
值相同的多余元素，使得L中没有重复元素：(1)L中数据元素⽆序排列；(2)L
中数据元素⾮递减有序排列。
（1）L中数据元素⽆序排列；
思路：由于是⽆序排列，需要线性表中每个元素都要相互进⾏⽐较。
Status ListDelete（Linklist &L）//L是带头结点的线性表
ElemType *p,*q;
p==L->next;q=p->next; //设定p变化较慢，q变化较快
while(p->next){
while(q) {
if(p->data!=q->data)
q=q->next;
else{
q=q->next;
p->next=q;
}//else
}//while
p=p->next;q=p->next;//开始后⼀结点的寻
return OK；
}//ListDelete
(2)L中数据元素⾮递减有序排列。
思路：由于是有序的，遍历⼀次线性表就⾏了
Status ListDelete (LinkList &L)
{
ElemType *p,*q;
p=L->next;q=p->next;
while(p->next)
{
if (p->data!=q->data){
p=p->next; //和第⼀问不同地⽅
q=p->next;
}//if
else {
while(p->data==q->data)
q=q->next;//多个连续的重复值
}//else
p->next=q;p=q;q=p->next;//删除值重复的结点，并修改相应的指针
return OK；
}//ListDelete
2.9 设有两个⾮递减有序的单链表A,B。请写出算法，将A和B就地归并成⼀个按元素值⾮递增有序的单链表。
// 将合并逆置后的结果放在C表中，并删除B表
Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) {
LinkList pa,pb,qa,qb;
pa=A;
pb=B;
qa=pa; // 保存pa的前驱指针
qb=pb; // 保存pb的前驱指针
pa=pa->next;
pb=pb->next;
A->next=NULL;
C=A;
while(pa&&pb){
if(pa->datadata){
qa=pa;
pa=pa->next;
qa->next=A->next; //将当前最⼩结点插⼊A表表头
A->next=qa;
}
else{
qb=pb;
pb=pb->next;
qb->next=A->next; //将当前最⼩结点插⼊A表表头
A->next=qb;
}
}
while(pa){
qa=pa;
pa=pa->next;
qa->next=A->next;
A->next=qa;
}
while(pb){
qb=pb;
pb=pb->next;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。