2015广工数据结构答案

/**********

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

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

if(a<=b){t=a;a=b;b=t;} if(b<=c){t=b;b=c;c=t;} if(a<=b){t=a;a=b;b=t;} }

/**********

【题目】试编写算法求一元多项式 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 */ { int i,j;float p=0,t=1; for(i=0;i<=n;i++) {

p=a[i]*t+p; t=t*x ; } return p; }

/**********

【题目】已知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 t[60],sum,i,j;

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

else if(m==k-1) f=1; else

{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 last=1; int i;

for(i=1;i<=n;i++) {a[i-1]=last*2*i; if(a[i-1]>MAXINT) return OVERFLOW; last=a[i-1]; } 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) /*使用switch语句记录各院校的成绩*/

{

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(i<0) return ERROR;

if(S.length

} 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 */ { int i;

S.elem=(ElemType*)malloc(n*sizeof(ElemType)); if(S.elem==NULL) return ERROR; S.length=n;

if(n<=0) return ERROR; for(i=0;i

/**********

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

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

LinkList MakeNode(ElemType x)

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

LNode *p=&a;

if(p==NULL) return NULL; a.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 a,b; LNode *p1=&a; LNode *p2=&b;

if(p1==NULL||p2==NULL) return NULL; a.data=x; b.data=y; a.next=p2; return p1; }

/**********

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

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

LinkList CreateOrdLList(ElemType x, ElemType y) /* 构建长度为2的升序链表。 */ /* 若构建失败，则返回NULL。 */ { LNode a,b; LNode *p1=&a; LNode *p2=&b;

if(p1==NULL||p2==NULL) return NULL; if(x

{a.data=y; b.data=x;} a.next=p2; return p1;

}

/**********

【题目】试写一算法，实现顺序栈的判空操作 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(NULL==S.elem||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 *newbase; if(S.top-S.elem>S.size)

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

S.size=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.top-S.elem==0) 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)==TRUE) { 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中元素个数，即队列的长度。 */

{ int s;

s=Q.rear-Q.front;

if(s<0) s=Q.maxSize-Q.front+Q.rear; return s; }

/**********

【题目】如果希望循环队列中的元素都能得到利用， 则可设置一个标志域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 */ {

SqQueue Q; int i,j; long fn=0;

Q.base=(ElemType*)malloc(sizeof(ElemType)); Q.front=0; Q.rear=0; Q.maxSize=k; for(i=0;i

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

Q.base[Q.rear]=1;

Q.rear=(Q.rear+1)%Q.maxSize;

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

for(i=k;i<=n;i++){ fn=0;

for(j=0;j

Q.base[Q.rear]=fn;

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

return fn; }

/**********

【题目】设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(iB.elem[i]) return '>'; i++; }

if(i==A.length&&i!=B.length) return '<'; if(i!=A.length&&i==B.length) return '>'; if(i==A.length&&i==B.length) return '='; }

/**********

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

int increment; } SqList;

**********/

void Inverse(SqList &L) { int i;

ElemType t;

for(i=0;i

L.elem[i]=L.elem[L.length-i-1]; L.elem[L.length-i-1]=t; } }

/**********

【题目】试对一元稀疏多项式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≤e1

float a=1,f=0;

for(i=0;i

for(j=0;j

f=f+P.elem[i].coef*a; }

return f; }

/**********

【题目】假设有两个集合A和B分别用两个线性表LA和LB 表示(即：线性表中的数据元素即为集合中的成员）， 试写一算法，求并集A＝A∪B。 顺序表类型定义如下 typedef struct {

ElemType *elem; // 存储空间的基址 int length; // 当前长度 int size; // 存储容量

int increment; // 空间不够增加空间大小 } SqList; // 顺序表

可调用顺序表的以下接口函数：

Status InitList_Sq(SqList &L, int size, int inc); // 初始化顺序表L int ListLength_Sq(SqList L); // 返回顺序表L中元素个数

Status GetElem_Sq(SqList L, int i, ElemType &e);

// 用e返回顺序表L中第i个元素的值 int Search_Sq(SqList L, ElemType e);

// 在顺序表L顺序查找元素e，成功时返回该元素在表中第一次出现的位置，否则返回-1 Status Append_Sq(SqList &L, ElemType e); // 在顺序表L表尾添加元素e **********/

void Union(SqList &La, SqList Lb) { int i;

for(i=0;i

if(Search_Sq(La,Lb.elem[i])==-1) Append_Sq(La,Lb.elem[i]); } }

/**********

【题目】试写一算法，实现链栈的判空操作。 链栈的类型定义为： typedef struct LSNode {

ElemType data; // 数据域 struct LSNode *next; // 指针域

} LSNode, *LStack; // 结点和链栈类型 ***********/

Status StackEmpty_L(LStack S)

/* 对链栈S判空。若S是空栈，则返回TRUE；否则返回FALSE */ { if(S==NULL) return TRUE; else return FALSE; }

/**********

【题目】试写一算法，实现链栈的取栈顶元素操作。 链栈的类型定义为： typedef struct LSNode {

ElemType data; // 数据域 struct LSNode *next; // 指针域

} LSNode, *LStack; // 结点和链栈类型 ***********/

Status GetTop_L(LStack S, ElemType &e)

/* 取链栈S的栈顶元素到e，并返回OK; */ /* 若S是空栈，则失败，返回ERROR。 */ { if(S==NULL) return FALSE; e=S->data; return OK;

}

/**********

【题目】试写一算法，实现链队列的判空操作。 链队列的类型定义为：

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==NULL) return TRUE; else return FALSE; }

/**********

【题目】试写一算法，实现链队列的求队列长度操作。 链队列的类型定义为：

typedef struct LQNode { ElemType data;

struct LQNode *next;

} LQNode, *QueuePtr; // 结点和结点指针类型 typedef struct {

QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LQueue; // 链队列类型 ***********/

int QueueLength_LQ(LQueue Q)

/* 求链队列Q的长度并返回其值 */ { if(Q.front==NULL) return 0; int i=1;

QueuePtr p; p=Q.front;

while(p!=Q.rear){ p=p->next; i++; }

return i;

}

/**********

【题目】假设以带头结点的循环链表表示队列，并且 只设一个指针指向队尾元素结点(注意不设头指针)， 试编写相应的队列初始化、入队列和出队列的算法。 带头结点循环链队列CLQueue的类型定义为： typedef struct LQNode { ElemType data;

struct LQNode *next; } LQNode, *CLQueue; **********/

Status InitCLQueue(CLQueue &rear) // 初始化空队列 {

rear=(LQNode*)malloc(sizeof(LQNode)); if(rear==NULL) return ERROR; rear->next=rear; return OK; }

Status EnCLQueue(CLQueue &rear, ElemType x) // 入队 { CLQueue p;

p=(LQNode*)malloc(sizeof(LQNode)); if(p==NULL) return ERROR; p->data=x;

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

Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队 {CLQueue p,t; t=rear->next;

if(t==rear) return ERROR; p=t->next; x=p->data;

t->next=p->next; free(p);

return OK; }

/**********

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

单链表的类型定义为： 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; }

/**********

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

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

Status DestroyList_L(LinkList &L)

/* 销毁带头结点单链表L，并返回OK。*/ { LinkList p; p=L->next;

while(p!=NULL){ L->next=p->next; free(p); p=L->next; } 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 FALSE; LinkList p; p=L->next;

while(p!=NULL){ L->next=p->next; free(p); p=L->next; }

return OK; }

/**********

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

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

int ListLength_L(LinkList L)

/* 求带头结点单链表L的长度，并返回长度值。*/ /* 若L不是带头结点单链表，则返回-1。 */ { int i=0; LinkList p;

if(L==NULL) return -1; p=L->next;

while(p!=NULL){ p=p->next; i++; } return i; }

/**********

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

LinkList p,t=L;

if(i<=0) return ERROR; if(L==NULL) return ERROR;

p=(LNode*)malloc(sizeof(LNode)); if(p==NULL) return ERROR; for(j=1;jnext;

if(t==NULL) return ERROR; }

p->data=e;

p->next=t->next; t->next=p; 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。 */ { int j;

LinkList p,t=L;

if(i<=0) return ERROR;

if(L->next==NULL||L==NULL) return ERROR; for(j=1;jnext;

if(t->next==NULL) return ERROR; }

p=t->next; e=p->data;

t->next=p->next; free(p);

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 j;

LinkList p,t=L;

Li=(LNode*)malloc(sizeof(LNode)); if(Li==NULL) return ERROR;

if(i<=0) {Li=NULL;return ERROR;}

if(L==NULL||L->next==NULL) {Li=NULL;return ERROR;} for(j=1;jnext;

if(t->next==NULL) {Li=NULL;return ERROR;} }

p=t->next; t->next=NULL; Li->next=p; 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 j;

LinkList p1,p2,t=L;

if(i<=0) return ERROR;

if(L->next==NULL||L==NULL) return ERROR; for(j=1;jnext;

if(t->next==NULL) return ERROR; }

p1=t->next; t->next=NULL; while(p1!=NULL){ p2=p1->next; free(p1); p1=p2; }

return OK; }

/**********

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

Status DeleteX_L(LinkList L, ElemType x)

/* 删除带头结点单链表L中所有值为x的元素， */ /* 并释放被删结点空间，返回实际删除的元素个数。*/ { //if(L==NULL||L->next==NULL) return ERROR; int i=0;

LinkList p1=L,p2;

while(p1->next!=NULL){ if(p1->next->data==x){ p2=p1->next;

p1->next=p2->next; free(p2); i++; }

else

p1=p1->next; }

return i; }

/**********

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

Status DeleteSome_L(LinkList L, ElemType x)

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

LinkList p1=L,p2;

while(p1->next!=NULL){ if(p1->next->datanext;

p1->next=p2->next; free(p2); i++; } else

p1=p1->next; }

return i; }

/**********

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

typedef struct {

RcdType rcd[MAXSIZE+1]; // r[0]闲置

int length; } RcdSqList; **********/

void InsertSort(RcdSqList &L) {int i,j;

for(i=L.length;i>1;i--){

if(L.rcd[i-1].key>L.rcd[i].key){ L.rcd[L.length+1]=L.rcd[i-1]; j=i-1;

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

}while(L.rcd[L.length+1].key>L.rcd[j+1].key); L.rcd[j]=L.rcd[L.length+1]; } } }

/**********

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

typedef struct {

RcdType rcd[MAXSIZE+1]; // r[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 change,t,i,j;

for(i=L.length,change=L.length;i>1&&change>1;i--){ t=change; change=1; for(j=1;j

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

{Swap(L.rcd[j],L.rcd[j+1]);change=j;}

} }

/**********

【题目】已知记录序列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 r[MAXSIZE+1]; // r[0]闲置 int length; } RcdSqList; **********/

void CountSort(RcdSqList &L)

/* 采用顺序表存储结构，在函数内自行定义计数数组c */ {int c[50]={0},i,j;

for(i=1;i

if(L.rcd[j].key

RcdType *L1; if(L.length!=0)

L1=(RcdType*)malloc(L.length*sizeof(RcdType)); for(i=1;i

for(i=1;i

free(L1); }

/**********

【题目】已知某哈希表的装载因子小于1，哈希函数H(key) 为关键字(标识符)的第一个字母在字母表中的序号，处理 冲突的方法为线性探测开放定址法。试编写一个按第一个

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