广东工业大学C语言anyview第三章答案
1、【题目】已知k阶裴波那契序列的定义为
f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1;
f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,...
试编写求k阶裴波那契序列的第m项值的函数算法，
k和m均以值调用的形式在函数参数表中出现。
**********/
Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */
{
int i,t[100],s,j;
if(k<2||m<0) return 0;
if((m>=0)&&mdata=x;
p->next=NULL;
}
else return NULL;
return p;
}
5、链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList; 试写一函数，构建长度为2且两个结点的值依次为x和y的链表。 **********/
LinkList CreateLinkList(ElemType x, ElemType y)
/* 构建其两个结点的值依次为x和y的链表。*/ /* 若构建失败，则返回NULL。 */ {
LNode *p,*q;p=(LNode*)malloc(sizeof(LNode));q=(LNode*)malloc(sizeof(LNode));
if(p&&q)
{
p->data=x;q->data=y;
p->next=q;q->next=NULL;
}
else return NULL;
return p;
}
6、链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList; 试写一函数，构建长度为2的升序链表，两个结点的值 分别为x和y，但应小的在前，大的在后。
**********/
LinkList CreateOrdLList(ElemType x, ElemType y)
/* 构建长度为2的升序链表。 */
/* 若构建失败，则返回NULL。 */
{
LNode *p,*q;p=(LNode*)malloc(sizeof(LNode));q=(LNode*)malloc(sizeof(LNode));
int a;if(x>y) {a=x;x=y;y=a;} if(p&&q)
{
p->data=x;q->data=y;
p->next=q;q->next=NULL; }
else return NULL;
return p;
}
7、若顺序栈的类型重新定义如下。试编写算法， 实现顺序栈的入栈操作。
typedef struct {
ElemType *elem; // 存储空间的基址
ElemType *top; // 栈顶元素的下一个位置
int size; // 当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} SqStack2;
***********/
Status Push_Sq2(SqStack2 &S, ElemType e)
/* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/ /* 将e压入S，返回OK。 */
{
ElemType *newbase;
if(S.top>=&S.elem[S.size]) {
if(S.increment<=0) return ERROR;
S.size=S.size+S.increment; }
*(S.top++)=e;
return OK;
}
8、试写一算法，借助辅助栈，复制顺序栈S1得到S2。 顺序栈的类型定义为:
typedef struct {
ElemType *elem; // 存储空间的基址
int top; // 栈顶元素的下一个位置，简称栈顶位标
int size; // 当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} SqStack; // 顺序栈
可调用顺序栈接口中下列函数:
Status InitStack_Sq(SqStack &S, int size, int inc); // 初始化顺序栈S Status DestroyStack_Sq(SqStack &S); // 销毁顺序栈S
Status StackEmpty_Sq(SqStack S); // 栈S判空，若空则返回TRUE，否则FALSE
Status Push_Sq(SqStack &S, ElemType e); // 将元素e压入栈S Status Pop_Sq(SqStack &S, ElemType &e); // 栈S的栈顶元素出栈到e ***********/
Status CopyStack_Sq(SqStack S1, SqStack &S2)
/* 借助辅助栈，复制顺序栈S1得到S2。 */ /* 若复制成功，则返回TRUE;否则FALSE。 */
{
InitStack_Sq(S2,S1.size,S1.increment);
if(TRUE==StackEmpty_Sq(S2))
for(int i=0;iQ.rear)
l=Q.maxSize-Q.front+Q.rear; return l;
}
10、如果希望循环队列中的元素都能得到利用， 则可设置一个标志域tag，并以tag值为0或1来区分尾 指针和头指针值相同时的队列状态是"空"还是"满"。 试编写与此结构相应的入队列和出队列的算法。 本题的循环队列CTagQueue的类型定义如下:
typedef struct {
ElemType elem[MAXQSIZE];
int tag;
int front;
int rear;
} CTagQueue;
**********/
Status EnCQueue(CTagQueue &Q, ElemType x)
/* 将元素x加入队列Q，并返回OK;*/
/* 若失败，则返回ERROR。 */ {
if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
Q.elem[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXQSIZE; return OK;
}
Status DeCQueue(CTagQueue &Q, ElemType &x)
/* 将队列Q的队头元素退队到x，并返回OK;*/ /* 若失败，则返回ERROR。 */ {
if(Q.rear==Q.front&&Q.tag==0) return ERROR;
x=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXQSIZE; return OK;
}
11、假设将循环队列定义为:以域变量rear
和length分别指示循环队列中队尾元素的位置和内
含元素的个数。试给出此循环队列的队满条件，并
写出相应的入队列和出队列的算法(在出队列的算
法中要返回队头元素)。
本题的循环队列CLenQueue的类型定义如下:
typedef struct {
ElemType elem[MAXQSIZE];
int length;
int rear;
} CLenQueue;
**********/
Status EnCQueue(CLenQueue &Q, ElemType x)
/* 将元素x加入队列Q，并返回OK;*/
/* 若失败，则返回ERROR。 */ {
int front;
if(Q.length!=0)
{
front=(MAXQSIZE+Q.rear+1-Q.length)%MAXQSIZE;
if((Q.rear+1)%MAXQSIZE==front) return ERROR;
Q.elem[++Q.rear]=x;
}
if(Q.length==0)
{
Q.elem[0]=x; Q.rear=0;
}
Q.length++;
return OK;
}
Status DeCQueue(CLenQueue &Q, ElemType &x)
/* 将队列Q的队头元素退队到x，并返回OK;*/
/* 若失败，则返回ERROR。 */ {
int front;
if(Q.length==0) return ERROR; front=(MAXQSIZE+Q.rear+1-Q.length)%MAXQSIZE;
x=Q.elem[front];
Q.length--;
return OK;
}
12、已知k阶斐波那契序列的定义为:
f0=0, f1=0, …, fk-2=0, fk-1=1;
fn=fn-1+fn-2+…+fn-k, n=k,k+1,…
试利用循环队列编写求k阶斐波那契序列中第
n+1项fn的算法。
本题的循环队列的类型定义如下:
typedef struct {
ElemType *base; // 存储空间的基址
int front; // 队头位标
int rear; // 队尾位标，指示队尾元素的下一位置
int maxSize; // 最大长度
} SqQueue;
**********/
long Fib(int k, int n)
/* 求k阶斐波那契序列的第n+1项fn */
{
int i,s,j;
long f;
SqQueue Q;
Q.base=(ElemType*)malloc((n+1)*sizeof(ElemType));
Q.maxSize=n+1; Q.front=Q.rear=0; if(k<2||n<0) return 0;
if((n>=0)&&nk)
{
for(i=0;i<=k-2;i++) Q.base[i]=0;
Q.base[k-1]=1; Q.base[k]=1;
for(i=k+1;i<=n;i++) {
s=0;
for(j=i;j>i-k;j--)
s+=Q.base[j-1];
Q.base[i]=s;
}
f=Q.base[n];
}
return f;
}
13、设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表，
A'和B'分别为A和B中除去最大共同前缀后的子表(例如， A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大
的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后
的子表分别为A'=(x,z)和B'=(y,x,x,z))。若A'=B'=空表，
则A=B;若A'=空表，而B'? 空表，或者两者均不为空表， 且A'的首元小于B'的首元，则AB。试写一个比 较A和B大小的算法。(注意:在算法中，不要破坏原表A 和B，也不一定先求得A'和B'才进行比较)。
顺序表类型定义如下:
typedef struct {
ElemType *elem;
int length;
int size;
int increment;
} SqList;
**********/
char Compare(SqList A, SqList B) /* 比较顺序表A和B, */
/* 返回'<', 若A', 若A>B */
{
int i;
if((A.elem[0]==0)&&(B.elem[0]!=0)) return'<';
if((A.elem[0]!=0)&&(B.elem[0]==0)) return'>';
if((A.elem[A.length-1]-B.elem[B.length-1]==0)) return '=';
if((A.elem[0]!=0)&&(B.elem[0]!=0)) {
for(i=0;(A.elem[i]!=0)||(B.elem[i]!=0);i++)
{
if(A.elem[i]-B.elem[i]==0) continue;
if(A.elem[i]-B.elem[i]>0) return'>';
if(A.elem[i]-B.elem[i]<0) return'<';
}
if(A.elem[i]==0) return'<';
if(B.elem[i]==0) return'>'; }
}
14、试写一算法，实现顺序表的就地逆置，
即利用原表的存储空间将线性表(a1,a2,…,an)
逆置为(an,an-1,…,a1)。
顺序表类型定义如下:
typedef struct {
ElemType *elem;
int length;
int size;
int increment;
} SqList;
**********/
void Inverse(SqList &L) {
int i,b;
if(L.length!=0)
{
for(i=0;i<(L.length-1)/2;i++) { b=L.elem[i];L.elem[i]=L.elem[L.length-1-i];L.elem[L.length-1-i]=b;
}
if(L.length%2==0)
{b=L.elem[(L.length-1)/2];L.elem[(L.length-1)/2]=L.elem[(L.length-1)/2+1];L.elem[(L.length-1)/
2+1]=b;
}
}
}
15、试对一元稀疏多项式Pn(x)采用存储量同多项式
项数m成正比的顺序存储结构，编写求Pn(x0)的算法(x0 为给定值)。
一元稀疏多项式的顺序存储结构:
typedef struct {
int coef; // 系数
int exp; // 指数
} Term;
typedef struct {
Term *elem; // 存储空间基址
int length; // 长度(项数)
} Poly;
**********/
float Evaluate(Poly P, float x) /* P.elem[i].coef 存放ai， */ /* P.elem[i].exp存放ei (i=1,2,...,m) */
/* 本算法计算并返回多项式的值。不判别溢出。 */ /* 入口时要求0?e1data==0) return TRUE; else return FALSE;
}
18、试写一算法，实现链栈的取栈顶元素操作。
链栈的类型定义为:
typedef struct LSNode {
ElemType data; // 数据域
struct LSNode *next; // 指针域
} LSNode, *LStack; // 结点和链栈类型
***********/
Status GetTop_L(LStack S, ElemType &e)
/* 取链栈S的栈顶元素到e，并返回OK; */
/* 若S是空栈，则失败，返回ERROR。 */
{
if(S->data==0) return ERROR; e=S->data;
return OK;
}
19、试写一算法，实现链队列的判空操作。
链队列的类型定义为:
typedef struct LQNode {
ElemType data;
struct LQNode *next; } LQNode, *QueuePtr; // 结点和结点指针类型
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LQueue; // 链队列类型
***********/
Status QueueEmpty_LQ(LQueue Q) /* 判定链队列Q是否为空队列。 */ /* 若Q是空队列，则返回TRUE，否则FALSE。*/ {
if(Q.front==0) return TRUE; else return FALSE;
}
20、试写一算法，实现链队列的求队列长度操作。 链队列的类型定义为:
typedef struct LQNode {
ElemType data;
struct LQNode *next; } LQNode, *QueuePtr; // 结点和结点指针类型
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LQueue; // 链队列类型
***********/
int QueueLength_LQ(LQueue Q) /* 求链队列Q的长度并返回其值 */
{
int i=0;
if(Q.front==0) return 0; while(Q.front->data!=0)
{i++;Q.front=Q.front->next;} return i;
}
21、假设以带头结点的循环链表表示队列，并且
只设一个指针指向队尾元素结点(注意不设头指针)， 试编写相应的队列初始化、入队列和出队列的算法。 带头结点循环链队列CLQueue的类型定义为:
typedef struct LQNode {
ElemType data;
struct LQNode *next; } LQNode, *CLQueue; **********/
Status InitCLQueue(CLQueue &rear) // 初始化空队列 {
rear=(LQNode*)malloc(sizeof(LQNode));
rear->next=rear;
return OK;
}
Status EnCLQueue(CLQueue &rear, ElemType x) // 入队 {
LQNode *s;
s=(LQNode*)malloc(sizeof(LQNode));
if((rear->next==rear)&&(null!=s)) {s->data=x;rear->next=s;s->next=rear;rear=s;return OK;}
s->data=x;
s->next=rear->next; rear->next=s;
rear=s;
return OK;
}
Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队 {
if(rear->next!=rear) { x=rear->next->next->data;
LQNode *A;
A=(LQNode*)malloc(sizeof(LQNode));
A=rear->next;
A->next=A->next->next;
return OK;
}
else return 0;
}
22、试写一算法，实现带头结点单链表的判空操作。
单链表的类型定义为:
typedef struct LNode {
ElemType data;
struct LNode *next; } LNode, *LinkList; // 结点和结点指针类型
***********/
Status ListEmpty_L(LinkList L) /* 判定带头结点单链表L是否为空链表。 */ /* 若L是空链表，则返回TRUE，否则FALSE。*/ {
if(L->next==null) return TRUE; else return FALSE;
}
23、试写一算法，实现带头结点单链表的销毁操作。 单链表的类型定义为:
typedef struct LNode {
ElemType data;
struct LNode *next; } LNode, *LinkList; // 结点和结点指针类型
***********/
Status DestroyList_L(LinkList &L)
/* 销毁带头结点单链表L，并返回OK。*/
{
free(L);
L->next=null;
return OK;
}
24、试写一算法，实现带头结点单链表的清空操作。
单链表的类型定义为:
typedef struct LNode {
ElemType data;
struct LNode *next; } LNode, *LinkList; // 结点和结点指针类型
***********/
Status ClearList_L(LinkList &L) /* 将带头结点单链表L置为空表，并返回OK。*/ /* 若L不是带头结点单链表，则返回ERROR。 */ {
if(L->data!=0||L==null) return ERROR;
L->next=null;
return OK;
}
25、试写一算法，实现带头结点单链表的求表长度操作。 单链表的类型定义为:
typedef struct LNode {
ElemType data;
struct LNode *next; } LNode, *LinkList; // 结点和结点指针类型
***********/
int ListLength_L(LinkList L) /* 求带头结点单链表L的长度，并返回长度值。*/ /* 若L不是带头结点单链表，则返回-1。 */ {
int l=0;
if(L->data!=0||L==null) return -1;
while(L->next!=0)
{l++;L=L->next;}
return l;
}
26、试写一算法，在带头结点单链表L插入第i元素e。 带头结点单链表的类型定义为:
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
**********/
Status Insert_L(LinkList L, int i, ElemType e)
/* 在带头结点单链表L插入第i元素e，并返回OK。*/ /* 若参数不合理，则返回ERROR。 */ {
int j;
LNode *s;
s=(LNode*)malloc(sizeof(LNode)); if(null!=s)
s->data=e;
if(i<=0||((L->next==null)&&(i>1))) return ERROR;
for(j=1;jnext;
if(L==null) return ERROR; }
s->next=L->next;
L->next=s;
return OK;}
27、试写一算法，在带头结点单链表删除第i元素到e。 带头结点单链表的类型定义为:
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
**********/
Status Delete_L(LinkList L, int i, ElemType &e)
/* 在带头结点单链表L删除第i元素到e，并返回OK。*/ /* 若参数不合理，则返回ERROR。 */ { int j;
if(i<=0||L->next==null) return ERROR; for(j=1;jnext;
if(L->next==null) return ERROR; }
e=L->next->data;
L->next=L->next->next;
return OK;
}
28、试写一算法，在带头结点单链表的第i元素起的
所有元素从链表移除，并构成一个带头结点的新链表。
带头结点单链表的类型定义为:
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
**********/
Status Split_L(LinkList L, LinkList &Li, int i)
/* 在带头结点单链表L的第i元素起的所有元素 */
/* 移除，并构成带头结点链表Li，返回OK。 */
/* 若参数不合理，则Li为NULL，返回ERROR。 */
{
int j=0;
int k=0;
Li=(LNode*)malloc(sizeof(LNode));
if((L->next==null)||(i==0)) {Li=null;return ERROR;}
LNode *A;LNode *B;
A=(LNode*)malloc(sizeof(LNode)); B=(LNode*)malloc(sizeof(LNode)); A=L;
while(A->next!=null) {A=A->next;k++; } if(knext;j++;}
D=Li;
while(B!=null){
D->next=B;
D=B;
B=B->next;
}
C->next=null;
return OK;
}
29、试写一算法，在带头结点单链表删除第i元素
起的所有元素。
带头结点单链表的类型定义为:
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
**********/
Status Cut_L(LinkList L, int i) /* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。*/ /* 若参数不合理，则返回ERROR。 */
{
int j=0;
int k=0;
if((L->next==null)||(i==0)) return ERROR;
LNode *A;LNode *B;
A=(LNode*)malloc(sizeof(LNode)); B=(LNode*)malloc(sizeof(LNode)); A=L;
while(A->next!=null) {A=A->next;k++; }
if(knext;j++;}
C->next=null;
return OK;
}
本文档为【广东工业大学C语言anyview第三章答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483