Anyview 第四章 15年数据结构Word下载.docx
《Anyview 第四章 15年数据结构Word下载.docx》由会员分享，可在线阅读，更多相关《Anyview 第四章 15年数据结构Word下载.docx（19页珍藏版）》请在冰点文库上搜索。
*/
/*若复制成功，则返回TRUE；
否则FALSE。
*/
{
//if（TRUE==StackEmpty_Sq（S1））returnFALSE;
//当S1是空的时候
SqStackS3;
if（ERROR==InitStack_Sq（S2,S1.size,S1.increment））returnFALSE;
if（ERROR==InitStack_Sq（S3,S1.size,S1.increment））returnFALSE;
//对S1、S2的初始化
if（!
StackEmpty_Sq（S2））returnFALSE;
StackEmpty_Sq（S3））returnFALSE;
//对S1、S2的判空
ElemTypee;
while（S1.top）
{
Pop_Sq（S1,e）;
Push_Sq（S3,e）;
}
while（S3.top）
Pop_Sq（S3,e）;
Push_Sq（S2,e）;
//DestroyStack_Sq（S1）;
//DestroyStack_Sq（S3）;
returnTRUE;
}
DS03-PE37
【题目】假设将循环队列定义为：
以域变量rear
和length分别指示循环队列中队尾元素的位置和内
含元素的个数。
试给出此循环队列的队满条件，并
写出相应的入队列和出队列的算法（在出队列的算
法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下：
ElemTypeelem[MAXQSIZE];
intlength;
intrear;
}CLenQueue;
**********/
StatusEnCQueue（CLenQueue&
Q,ElemTypex）
/*将元素x加入队列Q，并返回OK；
*/
/*若失败，则返回ERROR。
{
if（MAXQSIZE<
=Q.length）returnERROR;
//队满，无法插入
Q.rear=（Q.rear+1）%MAXQSIZE;
Q.elem[Q.rear]=x;
Q.length+=1;
returnOK;
StatusDeCQueue（CLenQueue&
Q,ElemType&
x）
/*将队列Q的队头元素退队到x，并返回OK；
if（0==Q.length）returnERROR;
x=Q.elem[（（Q.rear+MAXQSIZE-Q.length+1）%MAXQSIZE）];
Q.length-=1;
DS03-PE44
【题目】已知k阶斐波那契序列的定义为:
f0=0,f1=0,…,fk-2=0,fk-1=1;
fn=fn-1+fn-2+…+fn-k,n=k,k+1,…
试利用循环队列编写求k阶斐波那契序列中第
项fn+1n的算法。
本题的循环队列的类型定义如下：
ElemType*base;
intfront;
//队头位标
//队尾位标，指示队尾元素的下一位置
intmaxSize;
//最大长度
}SqQueue;
longAddSum（intn,ElemType*q）
longsum=0;
inti;
for（i=0;
i<
n;
i++）
sum+=q[i];
returnsum;
}
longFib（intk,intn）
/*求k阶斐波那契序列的第n+1项fn*/
if（k<
2||n<
-1）returnERROR;
if（n<
k）return0;
if（n+1==k）return1;
SqQueueQ;
inta,i;
Q.base=（ElemType*）malloc（k*sizeof（ElemType））;
if（NULL==Q.base）returnERROR;
Q.maxSize=k;
k;
{
Q.base[i]=0;
//初始化序列
Q.base[k-1]=1;
Q.front=0;
Q.rear=k-1;
a=k;
while（a<
=n）
Q.rear=（Q.rear+1）%k;
Q.base[Q.rear]=AddSum（k,Q.base）;
a++;
returnQ.base[Q.rear];
DS03-PE81
【题目】试对一元稀疏多项式Pn（x）采用存储量同多项式
项数m成正比的顺序存储结构，编写求Pn（x0）的算法（x0
为给定值）。
一元稀疏多项式的顺序存储结构:
intcoef;
//系数
intexp;
//指数
}Term;
Term*elem;
//存储空间基址
//长度（项数）
}Poly;
floatFunction（Term*p,floatx）
inta;
floatsum=1;
if（0==p->
exp）returnsum;
for（a=0;
a<
p->
exp;
a++）
sum*=x;
floatEvaluate（PolyP,floatx）
/*P.elem[i].coef存放ai，*/
/*P.elem[i].exp存放ei（i=1,2,...,m）*/
/*本算法计算并返回多项式的值。
不判别溢出。
/*入口时要求0≤e1<
e2<
...<
em，算法内不对此再作验证*/
floatsum=0;
Term*p;
p=P.elem;
if（0==P.length）returnsum;
while（P.length--）
sum+=p->
coef*Function（p,x）;
p++;
DS03-PE85
【题目】假设有两个集合A和B分别用两个线性表LA和LB
表示（即：
线性表中的数据元素即为集合中的成员），
试写一算法，求并集A＝A∪B。
1、在每个元素遍历的时候，排除相同的元素
2、插入
顺序表类型定义如下
//当前长度
//存储容量
//空间不够增加空间大小
}SqList;
//顺序表
可调用顺序表的以下接口函数：
StatusInitList_Sq（SqList&
L,intsize,intinc）;
//初始化顺序表L
intListLength_Sq（SqListL）;
//返回顺序表L中元素个数
StatusGetElem_Sq（SqListL,inti,ElemType&
//用e返回顺序表L中第i个元素的值
intSearch_Sq（SqListL,ElemTypee）;
//在顺序表L顺序查找元素e，成功时返回该元素在表中第一次出现的位置，否则返回-1
StatusAppend_Sq（SqList&
L,ElemTypee）;
//在顺序表L表尾添加元素e
voidAppend_Sq1（SqListL,ElemTypee）
L.elem[L.length]=e;
voidUnion（SqList&
La,SqListLb）
inta=ListLength_Sq（Lb）;
intb=ListLength_Sq（La）;
ElemType*p;
p=（ElemType*）realloc（La.elem,（a+b）*sizeof（ElemType））;
La.elem=p;
La.length=b;
La.size=a+b;
inti=1;
while（i<
=a）
GetElem_Sq（Lb,i,e）;
if（-1==Search_Sq（La,e））
Append_Sq1（La,e）;
La.length++;
}
i++;
DS04-PE38
【题目】假设以带头结点的循环链表表示队列，并且
只设一个指针指向队尾元素结点（注意不设头指针），
试编写相应的队列初始化、入队列和出队列的算法。
带头结点循环链队列CLQueue的类型定义为：
typedefstructLQNode{
ElemTypedata;
structLQNode*next;
}LQNode,*CLQueue;
StatusInitCLQueue（CLQueue&
rear）//初始化空队列
rear=（CLQueue）malloc（sizeof（LQNode））;
if（NULL==rear）returnERROR;
rear->
next=rear;
StatusEnCLQueue（CLQueue&
rear,ElemTypex）//入队
LQNode*p;
p=（LQNode*）malloc（sizeof（LQNode））;
if（NULL==p）returnERROR;
p->
data=x;
next=rear->
next;
next=p;
rear=p;
StatusDeCLQueue（CLQueue&
rear,ElemType&
x）//出队
if（rear->
next==rear）
returnERROR;
CLQueuep;
p=rear->
next->
x=p->
data;
if（p==rear）
rear=rear->
else
next=p->
DS04-PE62
【题目】试写一算法，在带头结点单链表L插入第i元素e。
带头结点单链表的类型定义为：
typedefstructLNode{
structLNode*next;
}LNode,*LinkList;
intLengthLinkList（LinkListL）
LinkListp=L;
intlength=0;
while（p->
next）
length++;
p=p->
returnlength;
StatusInsert_L（LinkListL,inti,ElemTypee）
/*在带头结点单链表L插入第i元素e，并返回OK。
/*若参数不合理，则返回ERROR。
if（NULL==L）returnERROR;
intlength=LengthLinkList（L）;
if（i>
length+1||i==0）returnERROR;
LinkListq;
q=（LNode*）malloc（sizeof（LNode））;
if（NULL==q）returnERROR;
inta=0;
q->
data=e;
if（i==length+1）
while（a++<
length）
next=q;
while（a++<
i-1）
DS04-PE64
【题目】试写一算法，在带头结点单链表删除第i元素到e。
StatusDelete_L（LinkListL,inti,ElemType&
e）
/*在带头结点单链表L删除第i元素到e，并返回OK。
if（NULL==L||i==0||i>
length）returnERROR;
LinkListp;
p=L;
if（i==length）
while（--i>
0）
e=p->
next=NULL;
DSO4-PE66
【题目】试写一算法，在带头结点单链表的第i元素起的
所有元素从链表移除，并构成一个带头结点的新链表。
StatusSplit_L（LinkListL,LinkList&
Li,inti）
/*在带头结点单链表L的第i元素起的所有元素*/
/*移除，并构成带头结点链表Li，返回OK。
/*若参数不合理，则Li为NULL，返回ERROR。
if（NULL==L||i==0）returnERROR;
length）
Li=NULL;
Li=（LNode*）malloc（sizeof（LNode））;
if（NULL==Li）
Li->
DS04-PE68
【题目】试写一算法，在带头结点单链表删除第i元素
起的所有元素。
StatusCut_L（LinkListL,inti）
/*在带头结点单链表L删除第i元素起的所有元素，并返回OK。
DS04-PE70
【题目】试写一算法，删除带头结点单链表中所有值
为x的元素，并释放被删结点空间。
单链表类型定义如下：
StatusDeleteX_L（LinkListL,ElemTypex）
/*删除带头结点单链表L中所有值为x的元素，*/
/*并释放被删结点空间，返回实际删除的元素个数。
intcount=0;
if（NULL==L->
next）returncount;
if（NULL==p->
next）
if（x==p->
data）
count++;
returncount;
while（p->
升级会员 