李淑芬教材第3章答案级.docx
《李淑芬教材第3章答案级.docx》由会员分享，可在线阅读，更多相关《李淑芬教材第3章答案级.docx（9页珍藏版）》请在冰点文库上搜索。
李淑芬教材第3章答案级
*p17/1.6/4打印所有的“水仙花数”，所谓水仙花数是指一个3位数，其各位数字三次方和等于该数字本身。
编写该问题的算法。
*/
#include
voidmain（）
{
inti;
intis（intnumber）;
printf（"所有的水仙花数：
\n"）;
for（i=99;i<1000;i++）
if（is（i）==1）printf（"%d\n",i）;
}
intis（intnumber）
{
intx=number%10;
inty=number/10%10;
intz=number/100;
if（x*x*x+y*y*y+z*z*z==number）return1;
elsereturn0;
}
*p17/1.6/5一个数如果恰好等于它的因子之和，这个数就称为“完数”。
例如，6的因子为1,2,3,而6=1+2+3，因此6是“完数”。
编程序找出1000以内的所有完数。
*/
#include
intmain（）
{
inti,j,k;
printf（"1000以内的完数有：
\n"）;
for（i=1;i<1000;i++）{
k=0;
for（j=1;jif（i%j==0）
k=k+j;
}
if（k==i）
printf（"%d\n",k）;
}
return0;
}
作业+
1、voidsortNode（linkList*head）//删除单链表重复元素
{
linkList*p,*q,*r;
p=head;
while（p->next）
{
q=p->next;
while（q->next）
{
if（p->next->data==q->next->data）//条件为真，删除重复元素
{
r=q->next;
q->next=r->next;
free（r）;
}
else
q=q->next;
}//while（q->next）
p=p->next;
}
}
}
2、VoidDelete_repnum（squlisttp*L,inti）//删除顺序表重复元素
{inti,j,k;
while（i<=（*L）.len）
{
j=i+1;
while（j<=（*L）.len）
if（（*L）.vec[j]=（*L）.vec[i]）
{
for（k=j;k<=（*L）.len;k++）
（*L）.vec[k-1]=（*L）.vec[k];/*元素前移*/
（*L）.len--;/*修改长度*/}
else
j++;
i++;
}}
作业1（ppt）
VoidDelete_repnum（SeqList*L,inti）删除有序顺序表中的重复元素
{inti,j,k;
while（i<=（*L）.len-1）
{
if（（*L）.vec[i+1]=（*L）.vec[i]）
{
for（k=i;k<=（*L）.len;k++）
（*L）.vec[k]=（*L）.vec[k+1];/*元素前移*/
（*L）.len--;/*修改长度*/}
else
i++;
}
}
2、逆置顺序表
voidreverse（list*L）
{
intlow=0,high=L->len-1;
intt,i;
if（L->len==0）return0;//顺序表为空，直接返回
for（i=0;ilen/2;i++）{
t=L->data[low];
L->data[low++]=L->data[high];
L->data[high--]=t;
}
}
3、在线性表L中找出最大值和最小值的元素及其所在的位置。
voidList_Min&Max（SeqList*L）{
inti,pos_Min;
intMax_data=L->data[0],Min_data=L->data[0];
for（i=0;iif（Min_data>L->data[i]）{//查找最小值及其位置
Min_data=L->data[i];
Pos_Min=i;
}
if（Max_datadata[i]）{
Max_data=L->data[i];
Pos_Max=i;
}
}
四、应用题
2、本算法的功能是将线性表的首元素移动到线性表的最后。
如：
（a1，a2，…….，an），算法执行后，线性表变为（a2，a3，……..，an，a1）。
5、xsxxxsssxxsxxsxxssss
3入x，3出s，*入x，-入x，y入x，y出s，-出s，*出s，-入x，a入x，a出s，/入x，y入x，y出s，^入，2入，2出，^出，/出，-出。
6、可以得到14种输出序列：
abcd,abdc,acbd,acdb,adcb,
bacd,bcad,bcda,bdca,badc.
cbad,cbda,cdba,
dcba
7、9-2*4+（8+1）/3表达式前后输入#，表示开始和结束。
序号
运算符栈
操作数栈
输入字符
1
#
9
2
#
9
-
3
#-
9
2
4
#-
92
*
5
#-*
92
4
6
#-*
924
+
7
#-
98
8
#
1
9
#+
1
（
10
#+（
1
8
11
#+（
18
+
12
#+（+
18
1
13
#+（+
181
）
14
#+
19
/
15
#+/
19
3
16
#+/
193
#
17
#+
13
18
#
4
五、算法设计题
五
（1）.设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有效性
I：
带头结点
Intinsert（NODE*L，intx）
{NODE,*s,*p;
P=L;带头结点
While（p->next）
{
if（p->next->data>x）
{s=malloc（sizeof（NODE））;
s->data=x;s->next=p;
p->next=s;
}
else
p=p->next;
}
Return0;
}
II不带头结点
Intinsert（NODE*L，intx）
{NODE,*s,*p;
P=L;不带头结点
While（p）
{
if（p->data>x）
{s=malloc（sizeof（NODE））;
s->data=x;s->next=p;
p=s;
}
else
p=p->next;
}
Return0;
}
五
（2）、有一个线性表存储在一个不带头结点的单链表的第i个元素之前插入一个元素的算法
分析：
对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。
voidLinkedListlnsert（LinkedList*L，intx，inti）
{//不带头结点的单链表的第i个元素之前插入一个元素
p=L：
j=1;
while（p!
=NULL&&j{p=p->next；j++；}
if（i<=0||p==NULL）printf（”插入位置不正确＼n”）；
else{
while（p!
=NULL&&j{p=p->next；j++；}
q=（LinkedList*）malloc（sizeof（LinkedList））；
q->data=x；
if（i==1）{q->next=L；L=q；}//在第一个元素之前插入
else{q->next=p->next；p->next=q；}//在其他位置插入
}
}
五、（3）设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。
试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。
答：
（1）分析：
用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将A、B表中较小的元素写入C中，直到有一个表先结束。
最后将没结束的表的剩余元素写入C表中。
SeqList*Seqmerge（SeqListA，SeqListB，SeqList*C）
{//有序顺序表A和B归并成有序顺序表C
i=0；j=0；k=0；//i，i，k分别为顺序表A，B，C的下标
while（i{if（A.data[i]{C->data[k]=A.data[i]；i++；}
else{C->data[k]=B.data[j];j++；}//B中当前元素较小
k++；}
if（i==m）for（t=j；tdata[k]=B.data[t];k++；}
//B表长度大于A表
elsefor（t=i；tdata[k]=A.data[t]；k++；}
//A表长度大于B表
C->length=m+n；
returnC;
}
（2）
VOidLinkmerge（LinkedList*A，LinkedList*B，LinkedList*C）
{／／有序链表A和B归并成有序链表C
pa=A->next；pb=B->next；C=A；pc=C；
while（pa&&pb）／／A和B都不为空时
{if（pa->datadata）／／A当前结点值较小
{qa=pa->next；pC->next=pa；pc=pc->next；pa=qa；}
else{qb=pb->next；pc->next=pb：
pc=pc->next；pb=qb；}
//B当前结点值较小
}
if（pa）pc->next=pa；//A没有结束，将A表剩余元素链接到C表
if（pb）pc->next=pb；//B没有结束，将B表剩余元素链接到C表
free（B）；//释放B表的头结点
}
本算法需要遍历两个线性表，因此时间复杂度为O（m+n）。
五（4）编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。
答：
分析：
根据题目要求，不能为表中的元素申请新的结点空间。
用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点，将q所指向的结点从A表删除，并链接到B表。
voiddecompose（LinkedList*A，LinkedList*B）
{//单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表B
LinkedList*r;
p=A->next；
B=（LinkedList*）malloc（sizeof（LinkedList））；
r=B；
while（p!
=NULL&&p->next!
=NULL）
{q=p->next；//q指向偶数序号的结点
p->next=q->next；//将q从A表中删除
r->next=q；//将q结点链接到B链表的末尾
r=q；//r总是指向B链表的最后—•个结点
p=p->next；//p指向原链表A中的奇数序号的结点
}
r->next=NULL;//将生成B链表中的最后一个结点的next域置为空
}
升级会员 