没有合适的资源?快使用搜索试试~ 我知道了~
首页严蔚敏《数据结构(c语言版)习题集》全答案
严蔚敏《数据结构(c语言版)习题集》全答案
需积分: 44 33 下载量 161 浏览量
更新于2023-03-03
评论
收藏 258KB PDF 举报
严蔚敏《数据结构(c语言版)习题集》全答案严蔚敏《数据结构(c语言版)习题集》全答案严蔚敏《数据结构(c语言版)习题集》全答案
资源详情
资源评论
资源推荐
说明 : 1. 本文是对严蔚敏《数据结构 (c 语言版 ) 习题集》一书中所有算 法
设计题目的解决方案 , 主要作者为 kaoyan.com 计算机版版主一具 . 以下网
友 :siice, 龙抬头 ,iamkent,zames,birdthinking 等为答案的修订和完善
工作提出了宝贵意见 , 在此表示感谢 ;
2. 本解答中的所有算法均采用类 c 语言描述 , 设计原则为面向交流、面 向
阅读 , 作者不保证程序能够上机正常运行 ( 这种保证实际上也没有任何意
义 );
3. 本解答原则上只给出源代码以及必要的注释 , 对于一些难度较高或思
路特殊的题目将给出简要的分析说明 , 对于作者无法解决的题目将给出必
要的讨论 . 目前尚未解决的题目有 : 5.20, 10.40;
4. 请读者在自己已经解决了某个题目或进行了充分的思考之后 , 再参考
本解答 , 以保证复习效果 ;
5. 由于作者水平所限 , 本解答中一定存在不少这样或者那样的错误和不
足 , 希望读者们在阅读中多动脑、勤思考 , 争取发现和纠正这些错误 , 写出
更好的算法来 . 请将你发现的错误或其它值得改进之处向作者报告 : yi-
ju@263.net
第一章 绪论
1.16
void print_descending(int x,int y,int z)// 按从大到小顺序输出三
个数
{
scanf("%d,%d,%d",&x,&y,&z);
if(x<y) x<->y; //<-> 为表示交换的双目运算符 , 以下同
if(y<z) y<->z;
if(x<y) x<->y; // 冒泡排序
printf("%d %d %d",x,y,z);
}//print_descending
1.17
Status fib(int k,int m,int &f)// 求 k 阶斐波那契序列的第 m 项的值 f
{
int tempd;
if(k<2||m<0) return ERROR;
if(m<k-1) f=0;
else if (m==k-1) f=1;
else
{
for(i=0;i<=k-2;i++) temp[i]=0;
temp[k-1]=1; // 初始化
for(i=k;i<=m;i++) // 求出序列第 k 至第 m 个元素的值
{
sum=0;
for(j=i-k;j<i;j++) sum+=temp[j];
temp[i]=sum;
}
f=temp[m];
}
return OK;
}//fib
分析 : 通过保存已经计算出来的结果 , 此方法的时间复杂度仅为 O(m^2). 如
果采用递归编程 ( 大多数人都会首先想到递归方法 ), 则时间复杂度将高达
O(k^m).
1.18
typedef struct{
char *sport;
enum{male,female} gender;
char schoolname; // 校名为 'A','B','C','D' 或 'E'
char *result;
int score;
} resulttype;
typedef struct{
int malescore;
int femalescore;
int totalscore;
} scoretype;
void summary(resulttype result[ ])// 求各校的男女总分和团体总分 ,
假设结果已经储存在 result[ ] 数组中
{
scoretype score;
i=0;
while(result[i].sport!=NULL)
{
switch(result[i].schoolname)
{
case 'A':
score[ 0 ].totalscore+=result[i].score;
if(result[i].gender==0) score[ 0
].malescore+=result[i].score;
else score[ 0 ].femalescore+=result[i].score;
break;
case 'B':
score.totalscore+=result[i].score;
if(result[i].gender==0) score.malescore+=result[i].score;
else score.femalescore+=result[i].score;
break;
…… …… ……
}
i++ ;
}
for(i=0;i<5;i++)
{
printf("School %d:",i);
printf("Total score of male:%d",score[i].malescore);
printf("Total score of female:%d",score[i].femalescore);
printf("Total score of all:%d",score[i].totalscore);
}
}//summary
1.19
Status algo119(int a[ARRSIZE])// 求 i!*2^i 序列的值且不超过 maxint
{
last=1;
for(i=1;i<=ARRSIZE;i++)
{
a[i-1]=last*2*i;
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
last=a[i-1];
return OK;
}
}//algo119
分析 : 当某一项的结果超过了 maxint 时 , 它除以前面一项的商会发生异常 .
1.20
void polyvalue()
{
float ad;
float *p=a;
printf("Input number of terms:");
scanf("%d",&n);
printf("Input the %d coefficients from a0 to a%d:",n,n);
for(i=0;i<=n;i++) scanf("%f",p++);
printf("Input value of x:");
scanf("%f",&x);
p=a;xp=1;sum=0; //xp 用于存放 x 的 i 次方
for(i=0;i<=n;i++)
{
sum+=xp*(*p++);
xp*=x;
}
printf("Value is:%f",sum);
}//polyvalue
第二章 线性表
2.10
Status DeleteK(SqList &a,int i,int k)// 删除线性表 a 中第 i 个元素
起的 k 个元素
{
if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
for(count=1;i+count-1<=a.length-k;count++) // 注意循环结束的条
件
a.elem[i+count-1]=a.elem[i+count+k-1];
a.length-=k;
return OK;
}//DeleteK
2.11
Status Insert_SqList(SqList &va,int x)// 把 x 插入递增有序表 va 中
{
if(va.length+1>va.listsize) return ERROR;
va.length++;
for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
return OK;
}//Insert_SqList
2.12
int ListComp(SqList A,SqList B)// 比较字符表 A 和 B, 并用返回值表示
结果 , 值为正 , 表示 A>B; 值为负 , 表示 A<B; 值为零 , 表示 A=B
{
for(i=1;A.elem[i]||B.elem[i];i++)
if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i];
return 0;
}//ListComp
2.13
LNode* Locate(LinkList L,int x)// 链表上的元素查找 , 返回指针
{
for(p=l->next;p&&p->data!=x;p=p->next);
return p;
}//Locate
2.14
int Length(LinkList L)// 求链表的长度
{
for(k=0,p=L;p->next;p=p->next,k++);
return k;
}//Length
2.15
void ListConcat(LinkList ha,LinkList hb,LinkList &hc)// 把链表 hb
接在 ha 后面形成链表 hc
{
hc=ha;p=ha;
while(p->next) p=p->next;
p->next=hb;
}//ListConcat
2.16
见书后答案 .
2.17
Status Insert(LinkList &L,int i,int b)// 在无头结点链表 L 的第 i 个
元素之前插入元素 b
{
p=L;q=(LinkList*)malloc(sizeof(LNode));
q.data=b;
if(i==1)
{
q.next=p;L=q; // 插入在链表头部
}
else
{
while(--i>1) p=p->next;
q->next=p->next;p->next=q; // 插入在第 i 个元素的位置
}
}//Insert
2.18
Status Delete(LinkList &L,int i)// 在无头结点链表 L 中删除第 i 个 元
素
{
if(i==1) L=L->next; // 删除第一个元素
else
{
p=L;
while(--i>1) p=p->next;
p->next=p->next->next; // 删除第 i 个元素
}
}//Delete
2.19
Status Delete_Between(Linklist &L,int mink,int maxk)// 删除元素
递增排列的链表 L 中值大于 mink 且小于 maxk 的所有元素
{
p=L;
while(p->next->data<=mink) p=p->next; //p 是最后一个不大于 mink
的元素
if(p->next) // 如果还有比 mink 更大的元素
{
q=p->next;
while(q->data<maxk) q=q->next; //q 是第一个不小于 maxk 的元素
p->next=q;
}
}//Delete_Between
2.20
Status Delete_Equal(Linklist &L)// 删除元素递增排列的链表 L 中所 有
值相同的元素
{
p=L->next;q=p->next; //p,q 指向相邻两元素
while(p->next)
{
if(p->data!=q->data)
{
p=p->next;q=p->next; // 当相邻两元素不相等时 ,p,q 都向后推一步
}
else
{
while(q->data==p->data)
{
free(q);
q=q->next;
}
p->next=q;p=q;q=p->next; // 当相邻元素相等时删除多余元素
}//else
}//while
}//Delete_Equal
2.21
void reverse(SqList &A)// 顺序表的就地逆置
{
for(i=1,j=A.length;i<j;i++,j--)
A.elem[i]<->A.elem[j];
}//reverse
2.22
void LinkList_reverse(Linklist &L)// 链表的就地逆置 ; 为简化算法 ,
假设表长大于 2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; // 把 L 的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
分析 : 本算法的思想是 , 逐个地把 L 的当前元素 q 插入新的链表头部 ,p 为 新
表表头 .
2.23
void merge1(LinkList &A,LinkList &B,LinkList &C)// 把链表 A 和 B 合
并为 C,A 和 B 的元素间隔排列 , 且使用原存储空间
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q; // 将 B 的元素插入
if(s)
{
t=q->next;q->next=s; // 如 A 非空 , 将 A 的元素插入
}
p=s;q=t;
}//while
}//merge1
2.24
void reverse_merge(LinkList &A,LinkList &B,LinkList &C)// 把元素
递增排列的链表 A 和 B 合并为 C, 且 C 中元素递减排列 , 使用原空间
{
pa=A->next;pb=B->next;pre=NULL; //pa 和 pb 分别指向 A,B 的当前元 素
while(pa||pb)
{
if(pa->data<pb->data||!pb)
{
pc=pa;q=pa->next;pa->next=pre;pa=q; // 将 A 的元素插入新表
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; // 将 B 的元素插入新表
}
pre=pc;
}
C=A;A->next=pc; // 构造新表头
}//reverse_merge
分析 : 本算法的思想是 , 按从小到大的顺序依次把 A 和 B 的元素插入新表 的
头部 pc 处 , 最后处理 A 或 B 的剩余元素 .
2.25
void SqList_Intersect(SqList A,SqList B,SqList &C)// 求元素递增
排列的线性表 A 和 B 的元素的交集并存入 C 中
{
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j])
{
if(A.elem[i]<B.elem[j]) i++;
if(A.elem[i]>B.elem[j]) j++;
if(A.elem[i]==B.elem[j])
{
C.elem[++k]=A.elem[i]; // 当发现了一个在 A,B 中都存在的元素 ,
i++;j++; // 就添加到 C 中
}
}//while
}//SqList_Intersect
2.26
void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)// 在
链表结构上重做上题
{
p=A->next;q=B->next;
pc=(LNode*)malloc(sizeof(LNode));
while(p&&q)
{
if(p->data<q->data) p=p->next;
else if(p->data>q->data) q=q->next;
else
{
s=(LNode*)malloc(sizeof(LNode));
s->data=p->data;
pc->next=s;pc=s;
p=p->next;q=q->next;
}
}//while
C=pc;
}//LinkList_Intersect
2.27
void SqList_Intersect_True(SqList &A,SqList B)// 求元素递增排列
的线性表 A 和 B 的元素的交集并存回 A 中
{
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j])
{
if(A.elem[i]<B.elem[j]) i++;
else if(A.elem[i]>B.elem[j]) j++;
else if(A.elem[i]!=A.elem[k])
{
A.elem[++k]=A.elem[i]; // 当发现了一个在 A,B 中都存在的元素
i++;j++; // 且 C 中没有 , 就添加到 C 中
}
}//while
while(A.elem[k]) A.elem[k++]=0;
}//SqList_Intersect_True
2.28
void LinkList_Intersect_True(LinkList &A,LinkList B)// 在链表结
构上重做上题
{
p=A->next;q=B->next;pc=A;
while(p&&q)
{
if(p->data<q->data) p=p->next;
else if(p->data>q->data) q=q->next;
else if(p->data!=pc->data)
{
pc=pc->next;
pc->data=p->data;
p=p->next;q=q->next;
}
}//while
}//LinkList_Intersect_True
2.29
void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
{
i=0;j=0;k=0;m=0; //i 指示 A 中元素原来的位置 ,m 为移动后的位置
while(i<A.length&&j<B.length&& k<C.length)
{
if(B.elem[j]<C.elem[k]) j++;
else if(B.elem[j]>C.elem[k]) k++;
else
{
same=B.elem[j]; // 找到了相同元素 same
while(B.elem[j]==same) j++;
while(C.elem[k]==same) k++; //j,k 后移到新的元素
while(i<A.length&&A.elem[i]<same)
A.elem[m++]=A.elem[i++]; // 需保留的元素移动到
新位置
while(i<A.length&&A.elem[i]==same) i++; // 跳过相同的元素
}
}//while
while(i<A.length)
A.elem[m++]=A.elem[i++]; //A 的剩余元素重新存储。
A.length=m;
}// SqList_Intersect_Delete
分析 : 先从 B 和 C 中找出共有元素 , 记为 same, 再在 A 中从当前位置开始 , 凡
小于 same 的
元素均保留 ( 存到新的位置 ), 等于 same 的就跳过 , 到大于 same 时就再找 下
一个 same.
2.30
void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList
C)// 在链表结构上重做上题
{
p=B->next;q=C->next;r=A-next;
while(p&&q&&r)
{
if(p->data<q->data) p=p->next;
else if(p->data>q->data) q=q->next;
else
{
u=p->data; // 确定待删除元素 u
while(r->next->data<u) r=r->next; // 确定最后一个小于 u 的元素
指针 r
if(r->next->data==u)
{
s=r->next;
while(s->data==u)
{
t=s;s=s->next;free(t); // 确定第一个大于 u 的元素指针 s
}//while
r->next=s; // 删除 r 和 s 之间的元素
}//if
while(p->data=u) p=p->next;
while(q->data=u) q=q->next;
}//else
}//while
}//LinkList_Intersect_Delete
2.31
Status Delete_Pre(CiLNode *s)// 删除单循环链表中结点 s 的直接前驱
{
p=s;
while(p->next->next!=s) p=p->next; // 找到 s 的前驱的前驱 p
p->next=s;
return OK;
}//Delete_Pre
2.32
Status DuLNode_Pre(DuLinkList &L)// 完成双向循环链表结点的 pre 域
{
for(p=L;!p->next->pre;p=p->next) p->next->pre=p;
return OK;
}//DuLNode_Pre
2.33
Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList
&C)// 把单链表 L 的元素按类型分为三个循环链表 .CiList 为带头结点的 单
循环链表类型 .
{
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));p=A;
B=(CiList*)malloc(sizeof(CiLNode));q=B;
C=(CiList*)malloc(sizeof(CiLNode));r=C; // 建立头结点
while(s)
{
if(isalphabet(s->data))
{
p->next=s;p=s;
}
else if(isdigit(s->data))
{
q->next=s;q=s;
}
else
{
r->next=s;r=s;
}
}//while
p->next=A;q->next=B;r->next=C; // 完成循环链表
}//LinkList_Divide
2.34
void Print_XorLinkedList(XorLinkedList L)// 从左向右输出异或链表
的元素值
{
p=L.left;pre=NULL;
while(p)
{
printf("%d",p->data);
q=XorP(p->LRPtr,pre);
pre=p;p=q; // 任何一个结点的 LRPtr 域值与其左结点指针进行异或运
算即得到其右结点指针
}
}//Print_XorLinkedList
2.35
Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)// 在异
或链表 L 的第 i 个元素前插入元素 x
{
p=L.left;pre=NULL;
r=(XorNode*)malloc(sizeof(XorNode));
r->data=x;
if(i==1) // 当插入点在最左边的情况
{
p->LRPtr=XorP(p.LRPtr,r);
r->LRPtr=p;
L.left=r;
return OK;
}
j=1;q=p->LRPtr; // 当插入点在中间的情况
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre);
pre=p;p=q;
}//while // 在 p,q 两结点之间插入
if(!q) return INFEASIBLE; //i 不可以超过表长
p->LRPtr=XorP(XorP(p->LRPtr,q),r);
q->LRPtr=XorP(XorP(q->LRPtr,p),r);
r->LRPtr=XorP(p,q); // 修改指针
return OK;
}//Insert_XorLinkedList
2.36
Status Delete_XorLinkedList(XorlinkedList &L,int i)// 删除异或链
表 L 的第 i 个元素
{
p=L.left;pre=NULL;
if(i==1) // 删除最左结点的情况
{
q=p->LRPtr;
q->LRPtr=XorP(q->LRPtr,p);
L.left=q;free(p);
return OK;
}
j=1;q=p->LRPtr;
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre);
pre=p;p=q;
}//while // 找到待删结点 q
if(!q) return INFEASIBLE; //i 不可以超过表长
if(L.right==q) //q 为最右结点的情况
{
p->LRPtr=XorP(p->LRPtr,q);
L.right=p;free(q);
return OK;
}
r=XorP(q->LRPtr,p); //q 为中间结点的情况 , 此时 p,r 分别为其左右结
点
p->LRPtr=XorP(XorP(p->LRPtr,q),r);
r->LRPtr=XorP(XorP(r->LRPtr,q),p); // 修改指针
free(q);
return OK;
}//Delete_XorLinkedList
2.37
void OEReform(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) p->next=L->pre->pre;
else 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 链的结构 , 此时 pre 链仍为原状
for(p=L;p->next!=L;p=p->next) p->next->pre=p;
L->pre=p; // 调整 pre 链的结构 , 同 2.32 方法
}//OEReform
分析 :next 链和 pre 链的调整只能分开进行 . 如同时进行调整的话 , 必须使
用堆栈保存偶数结点的指针 , 否则将会破坏链表结构 , 造成结点丢失 .
2.38
DuLNode * Locate_DuList(DuLinkedList &L,int x)// 带 freq 域的双向
循环链表上的查找
{
p=L.next;
while(p.data!=x&&p!=L) p=p->next;
if(p==L) return NULL; // 没找到
p->freq++;q=p->pre;
while(q->freq<=p->freq) q=q->pre; // 查找插入位置
if(q!=p->pre)
{
p->pre->next=p->next;p->next->pre=p->pre;
q->next->pre=p;p->next=q->next;
q->next=p;p->pre=q; // 调整位置
}
return p;
}//Locate_DuList
2.39
float GetValue_SqPoly(SqPoly P,int x0)// 求升幂顺序存储的稀疏多
项式的值
{
PolyTerm *q;
xp=1;q=P.data;
sum=0;ex=0;
while(q->coef)
{
while(ex<q->exp) xp*=x0;
sum+=q->coef*xp;
q++;
}
return sum;
}//GetValue_SqPoly
2.40
void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)// 求稀疏多
项式 P1 减 P2 的差式 P3
{
PolyTerm *p,*q,*r;
Create_SqPoly(P3); // 建立空多项式 P3
p=P1.data;q=P2.data;r=P3.data;
while(p->coef&&q->coef)
{
if(p->exp<q->exp)
{
r->coef=p->coef;
r->exp=p->exp;
p++;r++;
}
else if(p->exp<q->exp)
{
r->coef=-q->coef;
r->exp=q->exp;
q++;r++;
}
else
{
if((p->coef-q->coef)!=0) // 只有同次项相减不为零时才需要存入
P3 中
{
r->coef=p->coef-q->coef;
r->exp=p->exp;r++;
}//if
p++;q++;
}//else
}//while
while(p->coef) // 处理 P1 或 P2 的剩余项
{
r->coef=p->coef;
r->exp=p->exp;
p++;r++;
}
while(q->coef)
{
r->coef=-q->coef;
r->exp=q->exp;
q++;r++;
}
}//Subtract_SqPoly
2.41
void QiuDao_LinkedPoly(LinkedPoly &L)// 对有头结点循环链表结构存
储的稀疏多项式 L 求导
{
p=L->next;
if(!p->data.exp)
{
L->next=p->next;p=p->next; // 跳过常数项
}
while(p!=L)
{
p->data.coef*=p->data.exp--;// 对每一项求导
p=p->next;
剩余35页未读,继续阅读
lxb76486791
- 粉丝: 6
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0