数据结构(C语言版)习题解答
- 格式：doc
- 大小：934.00 KB
- 文档页数：22
精品文档，知识共享！
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; 精品文档，知识共享！
过程：n1n1i0jin(n1)(n2)(nj)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 试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a2, ..., an-1,an）逆置为(an,an-1, ..., a2,a1)
//思路就是两个指示变量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中数据元素非递减有序排列。
精品文档，知识共享！
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;
qb->next=A->next;
A->next=qb;
}
pb=B;
free(pb);
return OK;
}
2.13 设以带头结点的双向循环链表表示的线性表L=(a1,a2,a3,...,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。
void Reform(DuLinkedList &L)//按1,3,5,...4,2 的顺序重排双向循环链表L 中的所有结点
{
p=L.next;
while(p->next!=L&&p->next->next!=L)
{
p->next=p->next->next;
p=p->next;
} //p指向最后一个奇数结点
if(p->next==L) //结点个数是奇数，使最后一个奇数结点next指向最后一个偶数结点
p->next=L->pre->pre;
else//结点个数是偶数，使最后一个奇数结点next指向最后一个偶数结点
p->next=L->pre;
p=p->next; //此时p 指向最后一个偶数结点 精品文档，知识共享！
while(p->pre->pre!=L)
{
p->next=p->pre->pre;
p=p->next;
}
p->next=L;//最后一个结点next指向头结点
//调整了next 链的结构,此时pre 链仍为原状
//调整pre 链的结构
for(p=L;p->next!=L;p=p->next) p->next->pre=p;
L->pre=p; //头结点的pre指向a2结点
}//Reform
第三章 栈和队列
3.6 试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符‘&’,且序列2是序列1的逆序。例如，“a+b&b+a”是属于该模式的字符序列，而“1＋3&3－1”则不是。
算法：
int SeqReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
InitStack(s);
while((e=getchar())!='&')
{
if(e==’@’)
return 0;//不允许在’&’之前出现’@’
push(s,e);
}//序列1输入完毕
while( (e=getchar())!='@')
{
if(StackEmpty(s))
return 0;
pop(s,c);
if(e!=c)
return 0;
}
if(!StackEmpty(s))
return 0;//序列1元素还有剩余
return 1;
