Anyview 第四章 15年数据结构Word下载.docx

1、 */ /* 若复制成功，则返回TRUE；否则FALSE。 */ / if（ TRUE=StackEmpty_Sq（S1） ） return FALSE;/当S1是空的时候 SqStack S3; if（ ERROR=InitStack_Sq（ S2,S1.size,S1.increment ） ） return FALSE; if（ ERROR=InitStack_Sq（ S3,S1.size,S1.increment ） ） return FALSE;/对S1、S2的初始化 if（ !StackEmpty_Sq（S2） ）return FALSE;StackEmpty_Sq（S3） ）re

2、turn FALSE;/对S1、S2的判空 ElemType e; 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）; return TRUE;DS03-PE37【题目】假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。本题的循环队列CLenQ

3、ueue的类型定义如下： ElemType elemMAXQSIZE; int length; int rear; CLenQueue;*/Status EnCQueue（CLenQueue &Q, ElemType x） /* 将元素x加入队列Q，并返回OK；*/ /* 若失败，则返回ERROR。 if（ MAXQSIZE=Q.length ） return ERROR;/队满，无法插入 Q.rear = （Q.rear+1）%MAXQSIZE; Q.elemQ.rear=x; Q.length+=1; return OK;Status DeCQueue（CLenQueue &Q, Elem

4、Type &x） /* 将队列Q的队头元素退队到x，并返回OK； if（ 0=Q.length ） return ERROR; 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; int front; / 队头位标 / 队尾位标，指示队

5、尾元素的下一位置 int maxSize; / 最大长度 SqQueue;long AddSum（int n,ElemType *q） long sum=0; int i; for（ i=0; in; i+ ） sum += qi; return sum; long Fib（int k, int n）/* 求k阶斐波那契序列的第n+1项fn */ if（ k2|n-1 ） return ERROR; if（ nk ） return 0; if（ n+1=k ） return 1; SqQueue Q; int a,i; Q.base=（ElemType*）malloc（k*sizeof（Ele

6、mType）; if（ NULL=Q.base ）return ERROR; Q.maxSize=k;k; Q.basei=0; /初始化序列 Q.basek-1=1; Q.front=0; Q.rear=k-1; a=k; while（ aexp ） return sum; for（ a=0;aexp; a+ ） sum *= x;float Evaluate（Poly P, float x）/* P.elemi.coef 存放ai， */* P.elemi.exp存放ei （i=1,2,.,m） */* 本算法计算并返回多项式的值。不判别溢出。/* 入口时要求0e1e2.coef*Func

7、tion（p,x）; p+;DS03-PE85【题目】假设有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员），试写一算法，求并集AAB。1、在每个元素遍历的时候，排除相同的元素2、插入顺序表类型定义如下 / 当前长度 / 存储容量 / 空间不够增加空间大小 SqList; / 顺序表可调用顺序表的以下接口函数：Status InitList_Sq（SqList &L, int size, int inc）; / 初始化顺序表Lint ListLength_Sq（SqList L）; / 返回顺序表L中元素个数Status GetElem_Sq（SqList

8、 L, int i, ElemType &/ 用e返回顺序表L中第i个元素的值int Search_Sq（SqList L, ElemType e）;/ 在顺序表L顺序查找元素e，成功时返回该元素在表中第一次出现的位置，否则返回-1Status Append_Sq（SqList &L, ElemType e）; / 在顺序表L表尾添加元素evoid Append_Sq1（SqList L, ElemType e） L.elemL.length=e;void Union（SqList &La, SqList Lb） int a=ListLength_Sq（Lb）; int b=ListLengt

9、h_Sq（La）; ElemType *p; p=（ElemType*）realloc（La.elem,（a+b）*sizeof（ElemType）; La.elem=p; La.length=b; La.size=a+b; int i=1; while（ inext=rear;Status EnCLQueue（CLQueue &rear, ElemType x） / 入队 LQNode *p; p=（LQNode*）malloc（sizeof（LQNode）; if（ NULL=p ） return ERROR; p-data=x;next=rear-next;next=p; rear=p;

10、Status DeCLQueue（CLQueue &rear, ElemType &x） / 出队 if（ rear-next=rear ） return ERROR; CLQueue p; p=rear-next- x=p-data; if（ p=rear ） rear=rear- elsenext=p-DS04-PE62【题目】试写一算法，在带头结点单链表L插入第i元素e。带头结点单链表的类型定义为：typedef struct LNode struct LNode *next; LNode, *LinkList;int LengthLinkList（LinkList L） LinkLis

11、t p=L; int length=0; while（ p-next ） length+; p=p- return length;Status Insert_L（LinkList L, int i, ElemType e）/* 在带头结点单链表L插入第i元素e，并返回OK。/* 若参数不合理，则返回ERROR。 if（ NULL=L ） return ERROR; int length=LengthLinkList（L）; if（ ilength+1|i=0 ） return ERROR; LinkList q; q=（LNode*）malloc（sizeof（LNode）; if（ NULL

12、=q ） return ERROR; int a=0; q-data=e; if（ i=length+1 ） while（a+length）next=q; while（ a+length ） return ERROR; LinkList p; p=L; if（ i=length ） while（-i0） e=p-next=NULL;DSO4-PE66【题目】试写一算法，在带头结点单链表的第i元素起的所有元素从链表移除，并构成一个带头结点的新链表。Status Split_L（LinkList L, LinkList &Li, int i）/* 在带头结点单链表L的第i元素起的所有元素 */*

13、移除，并构成带头结点链表Li，返回OK。/* 若参数不合理，则Li为NULL，返回ERROR。 if（ NULL=L | i=0 ） return ERROR;length ） Li=NULL; Li=（LNode*）malloc（sizeof（LNode）; if（ NULL=Li ） Li-DS04-PE68【题目】试写一算法，在带头结点单链表删除第i元素起的所有元素。Status Cut_L（LinkList L, int i）/* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。DS04-PE70【题目】试写一算法，删除带头结点单链表中所有值为x的元素，并释放被删结点空间。单链表类型定义如下：Status DeleteX_L（LinkList L, ElemType x）/* 删除带头结点单链表L中所有值为x的元素， */* 并释放被删结点空间，返回实际删除的元素个数。int count=0;if（ NULL=L-next ） return count; if（NULL=p-next） if（x=p-data） count+; return count; while（p-