2016广工AnyView数据结构 第1-5章答案

/**********

【题目】试写一算法，如果三个整数a，b和c的值 不是依次非递增的，则通过交换，令其为非递增。 ***********/

void Descend(int &a, int &b, int &c) /* 通过交换，令 a >= b >= c */ {

if(c<=b&&b<=a) return; else {

if(a

void swap(int &a,int &b) {

int temp; temp=a; a=b; b=a; }

/**********

【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法 的时间复杂度。 **********/

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ {

float answer =a[0]; float temp= 1.0; for(int i=1;i<=n;i++) {

temp*=x;

answer+=a[i]*temp; }

return answer; }

/**********

【题目】已知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 */ {

if(k<=1||m<0) return ERROR; else if(m==k-1) f=1;

else if(m==0) f=0; else {

int i,j,sum; int *t;

t=(int*)malloc(m*sizeof(int)); for(i=0;i<=k-2;i++) t[i]=0; t[k-1]=1;

for(i=k;i<=m;i++) { sum=0;

for(j=i-k;j<=i;j++) sum+=t[j]; t[i]=sum; } f=t[m]; }

return OK; }

/**********

【题目】试编写算法，计算i!×2^i的值并存入数组 a[0..n-1]的第i-1个分量中 (i=1,2,…,n)。假设计

算机中允许的整数最大值为MAXINT，则当对某个k (1≤k≤n)使k!×2^k>MAXINT时，应按出错处理。注意 选择你认为较好的出错处理方法。 **********/

Status Series(int a[], int n)

/* 求i!*2^i序列的值并依次存入长度为n的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则OVERFLOW */ {

int t=1,p=1;

for(int i=1;i<=n;i++) { t*=i; p*=2; a[i-1]=t*p;

if(a[i-1]>MAXINT) return ERROR; }

return OK; }

/**********

【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛， 各院校的单项成绩均以存入计算机并构成一张表，表中每一行 的形式为：

项目名称性别校名成绩得分

编写算法，处理上述表格，以统计各院校的男、女总分和团体 总分，并输出。 **********/

void Scores(ResultType *result, ScoreType *score)

/* 求各校的男、女总分和团体总分, 并依次存入数组score */ /* 假设比赛结果已经储存在result[ ]数组中, */ /* 并以特殊记录 {\（域scorce=0）*/

/* 表示结束 */ {

int i=0;

while(result[i].sport!=NULL) {

switch(result[i].schoolname) {

case 'A': score[0].totalscore+=result[i].score; if(result[i].gender==male)

score[0].malescore+=result[i].score; else

score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore+=result[i].score; if(result[i].gender==male)

score[1].malescore+=result[i].score; else

score[1].femalescore+=result[i].score; break; case 'C': score[2].totalscore+=result[i].score; if(result[i].gender==male)

score[2].malescore+=result[i].score; else

score[2].femalescore+=result[i].score; break; case 'D': score[3].totalscore+=result[i].score; if(result[i].gender==male)

score[3].malescore+=result[i].score; else

score[3].femalescore+=result[i].score; break; case 'E': score[4].totalscore+=result[i].score; if(result[i].gender==male)

score[4].malescore+=result[i].score; else

score[4].femalescore+=result[i].score; break; } i++; } }

/**********

【题目】试写一算法，对序列S的第i个元素赋以值e。 序列的类型定义为： typedef struct {

ElemType *elem; int length; } Sequence; ***********/

Status Assign(Sequence &S, int i, ElemType e)

/* 对序列S的第i个元素赋以值e，并返回OK。 */ /* 若S或i不合法，则赋值失败，返回ERROR */ {

if(S.length<1||i>S.length) return ERROR; else

S.elem[i]=e; return OK; }

/**********

【题目】试写一算法，由长度为n的一维数组a构建一个序列S。

序列的类型定义为： typedef struct {

ElemType *elem; int length; } Sequence; ***********/

Status CreateSequence(Sequence &S, int n, ElemType *a)

/* 由长度为n的一维数组a构建一个序列S，并返回OK。 */ /* 若构建失败，则返回ERROR */ {

if(n<1)

return ERROR; else {

S.elem=(ElemType*)malloc(n*sizeof(ElemType)); S.elem[0]=a[0]; for(int i=1;i

return OK; }

/**********

【题目】链表的结点和指针类型定义如下 typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

试写一函数，构建一个值为x的结点。 ***********/

LinkList MakeNode(ElemType x)

/* 构建一个值为x的结点，并返回其指针。*/ /* 若构建失败，则返回NULL。 */ {

LNode * p;

p=(LNode*)malloc(sizeof(LNode)); if(p==NULL) return NULL; else

p->data=x; return p; }

/**********

【题目】链表的结点和指针类型定义如下 typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

试写一函数，构建长度为2且两个结点的值依次为x和y的链表。 **********/

LinkList CreateLinkList(ElemType x, ElemType y) /* 构建其两个结点的值依次为x和y的链表。*/ /* 若构建失败，则返回NULL。 */ {

LNode * p;

p=(LNode*)malloc(sizeof(LNode)); if(p==NULL) return NULL; else {

p->next=(LNode*)malloc(sizeof(LNode)); if(p->next==NULL) return NULL; p->data=x;

p->next->data=y; p->next->next=NULL; }

return p; }

/**********

【题目】链表的结点和指针类型定义如下 typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

试写一函数，构建长度为2的升序链表，两个结点的值 分别为x和y，但应小的在前，大的在后。 **********/

LinkList CreateOrdLList(ElemType x, ElemType y) /* 构建长度为2的升序链表。 */ /* 若构建失败，则返回NULL。 */ {

LNode * p;

p=(LNode*)malloc(sizeof(LNode));

if(p==NULL) return NULL; else {

p->next=(LNode*)malloc(sizeof(LNode)); if(p->next==NULL) return NULL;

p->data=(x

p->next->data=(x>y)?x:y; p->next->next=NULL; }

return p; }

/**********

【题目】试写一算法，实现顺序栈的判空操作 StackEmpty_Sq(SqStack S)。 顺序栈的类型定义为： typedef struct {

ElemType *elem; // 存储空间的基址

int top; // 栈顶元素的下一个位置，简称栈顶位标 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack; // 顺序栈 ***********/

Status StackEmpty_Sq(SqStack S)

/* 对顺序栈S判空。 */ /* 若S是空栈，则返回TRUE；否则返回FALSE */ {

if(S.top==0) return TRUE; return FALSE; }

/**********

【题目】试写一算法，实现顺序栈的取栈顶元素操作 GetTop_Sq(SqStack S, ElemType &e)。 顺序栈的类型定义为： typedef struct {

ElemType *elem; // 存储空间的基址

int top; // 栈顶元素的下一个位置，简称栈顶位标 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack; // 顺序栈

***********/

Status GetTop_Sq(SqStack S, ElemType &e)

/* 取顺序栈S的栈顶元素到e，并返回OK； */ /* 若失败，则返回ERROR。 */ {

if(S.top==0) return ERROR; e=S.elem[S.top-1]; return OK; }

/**********

【题目】试写一算法，实现顺序栈的出栈操作 Pop_Sq(SqStack &S, ElemType &e)。 顺序栈的类型定义为： typedef struct {

ElemType *elem; // 存储空间的基址

int top; // 栈顶元素的下一个位置，简称栈顶位标 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack; // 顺序栈 ***********/

Status Pop_Sq(SqStack &S, ElemType &e)

/* 顺序栈S的栈顶元素出栈到e，并返回OK；*/ /* 若失败，则返回ERROR。 */ {

if(S.top==0) return ERROR; e=S.elem[--S.top]; return OK; }

/**********

【题目】若顺序栈的类型重新定义如下。试编写算法， 构建初始容量和扩容增量分别为size和inc的空顺序栈S。 typedef struct {

ElemType *elem; // 存储空间的基址

ElemType *top; // 栈顶元素的下一个位置 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack2; ***********/

Status InitStack_Sq2(SqStack2 &S, int size, int inc)

/* 构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/

/* 若成功，则返回OK；否则返回ERROR。 */ {

S.elem=(ElemType*)malloc(sizeof(ElemType)); if(S.elem==NULL||size<=0||inc<=0) return ERROR; S.top=S.elem; S.size=size;

S.increment=inc; return OK; }

/**********

【题目】若顺序栈的类型重新定义如下。试编写算法， 实现顺序栈的判空操作。 typedef struct {

ElemType *elem; // 存储空间的基址

ElemType *top; // 栈顶元素的下一个位置 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack2; ***********/

Status StackEmpty_Sq2(SqStack2 S)

/* 对顺序栈S判空。 */ /* 若S是空栈，则返回TRUE；否则返回FALSE */ {

if(S.top==S.elem) return TRUE; return FALSE; }

/**********

【题目】若顺序栈的类型重新定义如下。试编写算法， 实现顺序栈的入栈操作。 typedef struct {

ElemType *elem; // 存储空间的基址

ElemType *top; // 栈顶元素的下一个位置 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack2; ***********/

Status Push_Sq2(SqStack2 &S, ElemType e)

/* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/ /* 将e压入S，返回OK。 */

{

ElemType * p;

if(S.top-S.elem>S.size) {

p=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType)); if(p==NULL) return ERROR; S.elem=p;

S.size+=S.increment; }

*(S.top++)=e; return OK; }

/**********

【题目】若顺序栈的类型重新定义如下。试编写算法， 实现顺序栈的出栈操作。 typedef struct {

ElemType *elem; // 存储空间的基址

ElemType *top; // 栈顶元素的下一个位置 int size; // 当前分配的存储容量

int increment; // 扩容时，增加的存储容量 } SqStack2; ***********/

Status Pop_Sq2(SqStack2 &S, ElemType &e)

/* 若顺序栈S是空的，则返回ERROR； */ /* 否则将S的栈顶元素出栈到e，返回OK。*/ {

if(S.elem==S.top) return ERROR; e=*(--S.top); return OK; }

/**********

【题目】试写一算法，借助辅助栈，复制顺序栈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。 */ {

if(StackEmpty_Sq(S1)) {

S2.top=0; return TRUE; }

S2.elem=S1.elem; S2.top=S1.top; return TRUE; }

/**********

【题目】试写一算法，求循环队列的长度。 循环队列的类型定义为： typedef struct {

ElemType *base; // 存储空间的基址 int front; // 队头位标

int rear; // 队尾位标，指示队尾元素的下一位置 int maxSize; // 最大长度 } SqQueue; ***********/

int QueueLength_Sq(SqQueue Q)

/* 返回队列Q中元素个数，即队列的长度。 */ {

if(Q.rear-Q.front<0)

return Q.maxSize-Q.front+Q.rear; return Q.rear-Q.front; }

/**********

【题目】如果希望循环队列中的元素都能得到利用， 则可设置一个标志域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.front==Q.rear&&Q.tag==1) return ERROR; if(Q.rear==0) {

Q.elem[0]=x; Q.rear+=1; } else {

Q.elem[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXQSIZE; }

Q.tag=1; return OK; }

Status DeCQueue(CTagQueue &Q, ElemType &x) /* 将队列Q的队头元素退队到x，并返回OK；*/ /* 若失败，则返回ERROR。 */ {

if(Q.front==Q.rear&&Q.tag==0) return ERROR; x=Q.elem[Q.front];

Q.front=(Q.front+1)%MAXQSIZE; Q.tag=0; return OK; }

/**********

【题目】假设将循环队列定义为：以域变量rear 和length分别指示循环队列中队尾元素的位置和内

含元素的个数。试给出此循环队列的队满条件，并 写出相应的入队列和出队列的算法（在出队列的算 法中要返回队头元素）。

本题的循环队列CLenQueue的类型定义如下： typedef struct {

ElemType elem[MAXQSIZE]; int length; int rear; } CLenQueue; **********/

Status EnCQueue(CLenQueue &Q, ElemType x) /* 将元素x加入队列Q，并返回OK；*/ /* 若失败，则返回ERROR。 */ {

if(Q.length==MAXQSIZE) return ERROR;

Q.rear=(Q.rear+1)%MAXQSIZE; Q.elem[Q.rear]=x; Q.length++; return OK; }

Status DeCQueue(CLenQueue &Q, ElemType &x)

/* 将队列Q的队头元素退队到x，并返回OK；*/ /* 若失败，则返回ERROR。 */ {

if(Q.length==0) return ERROR;

x=Q.elem[(Q.rear+MAXQSIZE-Q.length+1)%MAXQSIZE]; Q.length--; return OK; }

/**********

【题目】已知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 */ {

if(k<2||n<0) return ERROR; if(n

else if(n==k-1) return 1; else {

SqQueue S;

S.base=(ElemType*)malloc((n+1)*sizeof(ElemType)); S.base[k-1]=1; int i,j,sum;

for(i=0;i

for(i=k;i

sum=0;

for(j=i-k;j<=i;j++) sum+=S.base[j]; S.base[i]=sum; }

return S.base[n]; } }

/**********

【题目】设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=0;

while((i<=A.length-1)&&(i<=B.length-1)&&(A.elem[i]==B.elem[i])) ++i;

if(i==A.length&&i==B.length) return '=';

else if(i==A.length&&i!=B.length&&A.elem[i]

else if(i!=A.length&&i!=B.length&&A.elem[i]

else if(i==0&&A.elem[i]>B.elem[i]) return '>'; else

return '<' ; }

/**********

【题目】试写一算法，实现顺序表的就地逆置， 即利用原表的存储空间将线性表(a1,a2,…,an) 逆置为(an,an-1,…,a1)。 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int size;

int increment; } SqList;

**********/

void Inverse(SqList &L) {

ElemType temp;

struct LNode *next;

} LNode, *LinkList; // 结点和结点指针类型 ***********/

Status ListEmpty_L(LinkList L)

/* 判定带头结点单链表L是否为空链表。 */ /* 若L是空链表，则返回TRUE，否则FALSE。*/ {

if(L==L->next||!L->next) return TRUE; return FALSE; }

/**********

【题目】试写一算法，实现带头结点单链表的销毁操作。 单链表的类型定义为： typedef struct LNode { ElemType data; struct LNode *next;

} LNode, *LinkList; // 结点和结点指针类型 ***********/

Status DestroyList_L(LinkList &L)

/* 销毁带头结点单链表L，并返回OK。*/ {

if(L==L->next||!L->next) {

free(L); return OK; }

LNode * p=L->next, *pt; while(p!=NULL) {

pt=p->next; free(p); p=pt; }

free(L); return OK; }

/**********

【题目】试写一算法，实现带头结点单链表的清空操作。

单链表的类型定义为： typedef struct LNode {

ElemType data; struct LNode *next;

} LNode, *LinkList; // 结点和结点指针类型 ***********/

Status ClearList_L(LinkList &L)

/* 将带头结点单链表L置为空表，并返回OK。*/ /* 若L不是带头结点单链表，则返回ERROR。 */ {

if(L==NULL)

return ERROR; LNode * p=L->next, *pt; while(p!=NULL) {

pt=p->next; free(p); p=pt; }

L->next=NULL; return OK; }

/**********

【题目】试写一算法，实现带头结点单链表的求表长度操作。 单链表的类型定义为： typedef struct LNode { ElemType data; struct LNode *next;

} LNode, *LinkList; // 结点和结点指针类型 ***********/

int ListLength_L(LinkList L)

/* 求带头结点单链表L的长度，并返回长度值。*/ /* 若L不是带头结点单链表，则返回-1。 */ {

if(L==NULL) return -1; LinkList p=L->next; int count=0; while(p!=NULL) {

count++; p=p->next; }

return count; }

/**********

【题目】试写一算法，在带头结点单链表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。 */ {

if(i<0) return ERROR; int count=0; LinkList p= L;

while(p!=NULL&&count

p=p->next; count++; }

if(!p||count>i-1)return ERROR; //这步很重要 LinkList ptr;

ptr= (LNode*)malloc(sizeof(LNode)); ptr->data=e;

ptr->next=p->next; p->next=ptr; return OK; }

/**********

【题目】试写一算法，在带头结点单链表删除第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。 */ {

if(i<0) return ERROR; int count= 0;

LinkList p= L, pt;

while(p!=NULL&&count

p=p->next; count++; }

if(p->next==NULL||count>i-1) return ERROR; //这步很重要 pt=p->next;

p->next=p->next->next; e=pt->data; free(pt); return OK; }

/**********

【题目】试写一算法，在带头结点单链表的第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 count= 0; LinkList p= L, ptr;

while(p!=NULL&&count

p=p->next; //P指向第i-1号元素 count++; }

if(i<0||p==NULL||count>i-1||p->next==NULL) {

Li=NULL;

return ERROR; //查错 }

ptr=(LinkList)malloc(sizeof(LNode));

if(ptr==NULL) //为新链表开辟储存空间 return ERROR; Li=ptr;

Li->next=p->next; p->next=NULL; return OK; }

/**********

【题目】试写一算法，在带头结点单链表删除第i元素 起的所有元素。

带头结点单链表的类型定义为： typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; **********/

Status Cut_L(LinkList L, int i)

/* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。*/ /* 若参数不合理，则返回ERROR。 */ {

int count= 0;

LinkList p= L, pt;

while(p!=NULL&&count

p=p->next; //P指向第i-1号元素 count++; }

if(i<=0||p==NULL||count>i-1||p->next==NULL) {

return ERROR; //查错 }

if(i==1) {

free(L->next); L->next=NULL; return OK; }

pt=p->next; //pt指向将第i号元素 p->next=NULL; while(pt!=NULL) {

p=pt->next; free(pt); pt=p; }

return OK;

}

/**********

【题目】试写一算法，删除带头结点单链表中所有值 为x的元素，并释放被删结点空间。 单链表类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; **********/

Status DeleteX_L(LinkList L, ElemType x)

/* 删除带头结点单链表L中所有值为x的元素， */ /* 并释放被删结点空间，返回实际删除的元素个数。*/ {

int count= 0;

LinkList p= L->next, pf=L, q; while(p!=NULL) { if(p->data==x) { q=p; p=p->next; free(q); pf->next=p; count++; } else {

pf=p;

p=p->next; } }

return count; }

/**********

【题目】试写一算法，删除带头结点单链表中所有值 小于x的元素，并释放被删结点空间。 单链表类型定义如下： typedef struct LNode { ElemType data; struct LNode *next;

} LNode, *LinkList; **********/

Status DeleteSome_L(LinkList L, ElemType x)

/* 删除带头结点单链表L中所有值小于x的元素， */ /* 并释放被删结点空间，返回实际删除的元素个数。*/ {

int count= 0;

LinkList p= L->next, pf=L, q; while(p!=NULL) {

if(p->data

p=p->next; free(q); pf->next=p; count++; } else { pf=p;

p=p->next; } }

return count; }

/**********

【题目】试以顺序表L的L.rcd[L.length+1]作为监视哨， 改写教材3.2节中给出的升序直接插入排序算法。 顺序表的类型RcdSqList定义如下： typedef struct { KeyType key; ... } RcdType;

typedef struct {

RcdType rcd[MAXSIZE+1]; // rcd[0]闲置 int length; } RcdSqList; **********/

void InsertSort(RcdSqList &L) {

int i,j;

for(i=0;i

if(L.rcd[i+1].key

L.rcd[L.length+1].key=L.rcd[i+1].key; j=i+1;

do{ j--; L.rcd[j+1].key=L.rcd[j].key;

}while(L.rcd[L.length+1].key

L.rcd[j].key=L.rcd[L.length+1].key; //L.rcd[L.length+1] 需移到左边那个数（位置为[j]），判别条件为其需大于rcd[j-1]

} //即当 L.rcd[L.length+1].key > L.rcd[j-1].key 时终止 while() }

/**********

【题目】如下所述，改写教材1.3.2节例1-10的冒泡排序算法： 将算法中用以起控制作用的布尔变量change改为一个整型 变量，指示每一趟排序中进行交换的最后一个记录的位置， 并以它作为下一趟起泡排序循环终止的控制值。 顺序表的类型RcdSqList定义如下： typedef struct { KeyType key; ... } RcdType;

typedef struct {

RcdType rcd[MAXSIZE+1]; // rcd[0]闲置 int length; } RcdSqList; **********/

void BubbleSort(RcdSqList &L)

/* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：\ */ /* Status GT(RedType a, RedType b); 比较：\ */ /* void Swap(RedType &a, RedType &b); 交换 */ {

int i = L.length-1; int change=i,j;

for(;(i>=1)&&change;i--){ change = 0; for(j=1;j<=i;j++){

if(GT(L.rcd[j],L.rcd[j+1])){ Swap(L.rcd[j],L.rcd[j+1]);

change = j; } }

i = change; } }

/**********

【题目】已知记录序列L.rcd[1..L.length]中的关键 字各不相同，可按如下所述实现计数排序：另设数组 c[1..n]，对每个记录a[i]，统计序列中关键字比它 小的记录个数存于c[i]，则c[i]=0的记录必为关键字 最小的记录，然后依c[i]值的大小对序列中记录进行 重新排列。试编写算法实现上述排序方法。 顺序表的类型RcdSqList定义如下： typedef struct { KeyType key; ... } RcdType;

typedef struct {

RcdType rcd[MAXSIZE+1]; // rcd[0]闲置 int length; } RcdSqList; **********/

void CountSort(RcdSqList &L)

/* 采用顺序表存储结构，在函数内自行定义计数数组c */ {

int * c;

c= (int*)malloc((L.length+1)*sizeof(int)); //创建计数数组c,统计序列中关键字比其他大的个数

KeyType * temp;

temp= (KeyType*)malloc((L.length+1)*sizeof(KeyType)) ; //创建临时数组，根据c[i]的值直接插入 int i,j;

for(i=0;i

c[i]=0; //初始化C[i] for(i=1;iL.rcd[j].key)

c[i]++; //统计序列中关键字比其他大的个数,存入c[i] for(i=1;i

temp[c[i]+1]=L.rcd[i].key; //根据c[i]的值直接插入对应位置 for(j=1;j

L.rcd[j].key=temp[j]; //把排序完的数据返回到原始序列 }

/**********

【题目】已知某哈希表的装载因子小于1，哈希函数H(key) 为关键字(标识符)的第一个字母在字母表中的序号，处理 冲突的方法为线性探测开放定址法。试编写一个按第一个 字母的顺序输出哈希表中所有关键字的算法。 哈希表的类型HashTable定义如下： #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1

typedef char StrKeyType[4]; typedef struct {

StrKeyType key; // 关键字项

int tag; // 标记 0:空；1:有效; -1:已删除 void *any; // 其他信息 } RcdType;

typedef struct {

RcdType *rcd; // 存储空间基址 int size; // 哈希表容量

int count; // 表中当前记录个数 } HashTable; **********/

void PrintKeys(HashTable ht, void(*print)(StrKeyType)) /* 依题意用print输出关键字 */ {

int n,i;

for(char c='A';c<='Z';c++){ n = (c-'A')% ht.size; i = n;

while((n+1)% ht.size!=i){

if(ht.rcd[n].tag!=-1&&ht.rcd[n].key[0]==c) print(ht.rcd[n].key); n = (n+1)% ht.size; } } }

/**********

【题目】假设哈希表长为m，哈希函数为H(x)，用链地址法 处理冲突。试编写输入一组关键字并建造哈希表的算法。 哈希表的类型ChainHashTab定义如下： #define NUM 7 #define NULLKEY -1 #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 typedef char HKeyType; typedef struct HNode { HKeyType data; struct HNode* next; }*HLink;

typedef struct {

HLink *rcd; // 指针存储基址，动态分配数组 int count; // 当前表中含有的记录个数 int size; // 哈希表的当前容量 }ChainHashTab; // 链地址哈希表

int Hash(ChainHashTab H, HKeyType k) { // 哈希函数 return k % H.size; }

Status Collision(ChainHashTab H, HLink &p) {

// 求得下一个探查地址p if (p && p->next) { p = p->next; return SUCCESS;

} else return UNSUCCESS; }

**********/

int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) /* 直接调用下列函数 */ /* 哈希函数： */ /* int Hash(ChainHashTab H, HKeyType k); */

/* 冲突处理函数： */ /* int Collision(ChainHashTab H, HLink &p); */ {

int i=0, pos; bool flag= true;; HLink p, pt;

while(es[i]!='\\0'){

p=(HNode*)malloc(sizeof(HNode)); p->data=es[i]; p->next=NULL; pos=Hash(H,es[i]);

if(H.rcd[pos]==NULL) H.rcd[pos]=p; else {

pt=H.rcd[pos]; while(pt){

if(pt->data==p->data){ flag=false; break; } pt=pt->next; } if(flag){

pt=H.rcd[pos]; p->next=pt; H.rcd[pos]=p; } } i++;

flag= true; } }

/**********

【题目】试编写如下定义的递归函数的递归算法: g(m,n) = 0 当m=0,n>=0 g(m,n) = g(m-1,2n)+n 当m>0,n>=0 **********/

int G(int m, int n)

/* 如果 m<0 或 n<0 则返回 -1 */ {

if(n<0||m<0) return -1; else if(m==0) return 0; else if(m>0)

return G(m-1,2*n)+n; }

/**********

【题目】试写出求递归函数F(n)的递归算法： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0

**********/ int F(int n)

/* 如果 n<0 则返回 -1 */ {

if(n<0) return -1; if(n==0) return n+1; else

return n*F(n/2); }

/**********

【题目】求解平方根的迭代函数定义如下：

sqrt(A,p,e) = p 当|p*p-A|=e

其中，p是A的近似平方根，e是结果允许误差。试写出相 应的递归算法。 **********/

float Sqrt(float A, float p, float e) {

if(p*p-A

return Sqrt(A,(p+A/p)/2,e); }

/**********

【题目】已知Ackerman函数的定义如下： akm(m,n) = n+1 当m=0 akm(m,n) = akm(m-1,1) 当m!=0,n=0 akm(m,n) = akm(m-1,akm(m,n-1)) 当m!=0,n!=0 请写出递归算法。 **********/

int Akm(int m, int n)

/* 若 m<0 或 n<0 则返回-1 */ {

if(m<0||n<0) return -1; else if(m==0) return n+1; else if(n==0)

return Akm(m-1,1);

else

return Akm(m-1,Akm(m,n-1)); }

/**********

【题目】试写出求递归函数F(n)的非递归算法： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0 **********/ int F(int n)

/* 如果 n<0 则返回 -1 */ {

if(n<0) return -1; else if(n==0) return n+1; else

return n*F(n/2); }

/**********

【题目】求解平方根的迭代函数定义如下：

sqrt(A,p,e) = p 当|p*p-A|=e

其中，p是A的近似平方根，e是结果允许误差。试写出相 应的非递归算法。 **********/

float Sqrt(float A, float p, float e) {

if(p*p-A

return Sqrt(A,(p+A/p)/2,e); }

/**********

【题目】假设以二维数组g[1..m][1..n]表示一个图像 区域，g[i][j]表示该区域中点(i,j)所具颜色，其值

为从0到k的整数。试编写递归算法，将点(i0,j0)所在 区域的颜色置换为颜色c。约定与(i0,j0)同色的上、 下、左、右的邻接点为同色区域的点。

表示图像区域的类型定义如下： typedef char GTYPE[m+1][n+1]; **********/

void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0) /* 在g[1..m][1..n]中，将元素g[i0][j0] */

/* 所在的同色区域的颜色置换为颜色c */ {

char color=g[i0][j0]; g[i0][j0]=c;

if(i0-1>=1&&g[i0-1][j0]==color) ChangeColor(g,m,n,c,i0-1,j0); if(j0-1>=1&&g[i0][j0-1]==color) ChangeColor(g,m,n,c,i0,j0-1); if(i0+1<=m&&g[i0+1][j0]==color) ChangeColor(g,m,n,c,i0+1,j0); if(j0+1<=n&&g[i0][j0+1]==color) ChangeColor(g,m,n,c,i0,j0+1); }

/**********

【题目】试按依次对每个元素递归分解的分析方法重写求广义表的深度的递归算法。 广义表类型GList的定义：

typedef enum {ATOM,LIST} ElemTag; typedef struct GLNode{ ElemTag tag; union {

char atom; struct {

GLNode *hp, *tp; } ptr; }un; } *GList;

**********/

int GListDepth(GList ls)

/* Return the depth of list */ {

int h1,h2; if(ls==NULL) return 1;

if(ls->tag==ATOM) return 0;

h1= GListDepth(ls->un.ptr.hp)+1;

本文来源：https://www.bwwdw.com/article/i7cf.html