数据结构题目



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



void Descend(int &a, int &b, int &c)
/ 通过交换，令 a >= b >= c /
{ int d;
if(aMAXINT时，应按出错处理。注意
选择你认为较好的出错处理方法。
**/
Status Series(int a[], int n)
/ 求i!2^i序列的值并依次存入长度为n的数组a； /
/ 若所有值均不超过MAXINT，则返回OK，否则OVERFLOW /
{
int i,sum=0,sum1=1,sum2=1;
int j;
for(i=1;i<=n;i++)
{
for(j=i;j>0;j–) sum1=j;
for( j=i;j>0;j–) sum2=sum22;

sum=sum1sum2;
if(sum>MAXINT||sum1>MAXINT||sum2>MAXINT)
{

return OVERFLOW;
break;
}
a[i-1]=sum;
sum1=1;sum2=1;
}
return OK;
}

/**
【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，
各院校的单项成绩均以存入计算机并构成一张表，表中每一行
的形式为：
项目名称 性别 校名 成绩 得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体
总分，并输出。
**/
void Scores(ResultType result, ScoreType score)
/ 求各校的男、女总分和团体总分,并依次存入数组score /
/ 假设比赛结果已经储存在result[ ]数组中, /
/ 并以特殊记录 {“”, male, ‘ ‘, “”, 0 }（域scorce=0）/
/ 表示结束 /
{
typedef enum {female,male} Sex;
typedef struct{
char sport; // 项目名称
Sex gender; // 性别（女：female；男：male）
char schoolname; // 校名为’A’,’B’,’C’,’D’或’E’
char result; // 成绩
int score; // 得分（7,5,4,3,2或1）
} ResultType;

typedef struct{
int malescore; // 男子总分
int femalescore; // 女子总分
int totalscore; // 男女团体总分
} ScoreType;

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++;
}
int j;
for( j=0;j<5;j++) {="" printf("the="" school="" %s:="" ",="" result[i].schoolname)="" ;="" *输出各院校的男女总分和团体总分*="" printf("total:="" %f",&score[i].totalscore);="" printf("male:="" %f",&score[i].malescore);="" printf("female:="" %f",&score[i].femalescore);="" }="" **********="" 【题目】试写一算法，对序列s的第i个元素赋以值e。="" 序列的类型定义为：="" typedef="" struct="" elemtype="" *elem;="" int="" length;="" sequence;="" ***********="" status="" assign(sequence="" &s,="" i,="" e)="" *="" 对序列s的第i个元素赋以值e，并返回ok。*="" 若s或i不合法，则赋值失败，返回error="" if(i<0||i="">S.length||S.elem==NULL) 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 /
{
S.elem=(ElemType)malloc(nsizeof(ElemType));
if(S.elem==a||n<=0) return ERROR;
S.elem = a;
S.length = n;
if(&S.elem[0]==NULL) return ERROR;
else 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)
{
p->data=x;
p->next=NULL;
}
else return NULL;
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 p1,p2;
p1 = (LNode)malloc(sizeof(LNode));
p2 = (LNode)malloc(sizeof(LNode));
if(p1)
{
p1->data=x;
p1->next=p2;
}else return NULL;
if(p2)
{
p2->data=y;
p2->next=NULL;
}

else return NULL;
return p1;
}

/**
【题目】链表的结点和指针类型定义如下
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));
p->data = x;
q->data = y;
if(x>y){
q->next = p;
p->next = NULL;
return q;
}else{
p->next = q;
q->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.elem==NULL||S.top==NULL) return TRUE;
else 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(0==S.top) 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(sizesizeof(ElemType));
if(NULL==S.elem) return OVERFLOW;
if(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;
else 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;
S.top++;
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) 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。/
{
SqStack S3;
ElemType e;
InitStack_Sq(S3,S1.size,S1.increment);
InitStack_Sq(S2,S1.size,S1.increment);
while(StackEmpty_Sq(S1)!=TRUE){
Pop_Sq(S1,e);
Push_Sq(S3,e);
}
while(StackEmpty_Sq(S3)!=TRUE){
Pop_Sq(S3,e);
Push_Sq(S2,e);
}

return TRUE;
}

/**
【题目】试写一算法，求循环队列的长度。
循环队列的类型定义为：
typedef struct {
ElemType base; // 存储空间的基址
int front; // 队头位标
int rear; // 队尾位标，指示队尾元素的下一位置
int maxSize; // 最大长度
} SqQueue;
**/
int QueueLength_Sq(SqQueue Q)
/ 返回队列Q中元素个数，即队列的长度。/
{ return (Q.rear-Q.front+Q.maxSize)%Q.maxSize;

}

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

Status DeCQueue(CTagQueue &Q, ElemType &x)
/ 将队列Q的队头元素退队到x，并返回OK；/
/ 若失败，则返回ERROR。 /
{ if(Q.tag==0&&Q.front==Q.rear)
return ERROR;
x=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
if(Q.front==Q.rear)
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.length++;
Q.rear=(Q.rear+1)%MAXQSIZE;
Q.elem[Q.rear]=x;
return TRUE;

}
Status DeCQueue(CLenQueue &Q, ElemType &x)
/ 将队列Q的队头元素退队到x，并返回OK；/
/ 若失败，则返回ERROR。 /
{
int front;
if(Q.length==0) return ERROR;
Q.length–;
front=MAXQSIZE-Q.length+Q.rear;
x=Q.elem[front%MAXQSIZE];
front=(front+1)%MAXQSIZE;
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 /
{
int i,j ;
if(1 >=k|| 0 > n) return ERROR;
SqQueue fib;
fib.base = (ElemType)malloc(30sizeof(ElemType));
fib.maxSize = 30;
fib.front = fib.rear = 0;
for(;fib.rear < k;fib.rear++)
{
if(fib.rearB。试写一个比
较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<B; /
/ ‘=’, 若A=B; /
/ ‘>’, 若A>B /
{
int i;
if(0 == A.length && 0 == B.length)
return ‘=’;
else
{
for(i = 0; i < A.length||i< B.length;i++)
{
if(A.elem[i] < B.elem[i])
return ‘<’;
if(A.elem[i] > B.elem[i])
return ‘>’;
}
if(A.length > B.length) return ‘>’;
if(A.length < B.length) return ‘<’;
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 temp;
for(i=0;i<L.length/2;i++) {
temp=L.elem[i];
L.elem[i]=L.elem[L.length-1-i];
L.elem[L.length-1-i]=temp; }

}


/**
【题目】试对一元稀疏多项式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<e2<…<em，算法内不对此再作验证/
{ int i,j;
float sum = 0,sum1 ;
for(i = 0;i 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(NULL == Q.front) 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的长度并返回其值/
{
LQNode p = Q.front;
int i=1;
if(Q.front == NULL) return ERROR;
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) // 初始化空队列
{ LQNode p;
if(NULL ==(p = (LQNode)malloc(sizeof(LQNode))))
return ERROR;
p->next = p;
rear = p;
return OK;
}

Status EnCLQueue(CLQueue &rear, ElemType x) // 入队
{ LQNode p;
if(NULL ==(p = (LQNode)malloc(sizeof(LQNode))))
return ERROR;
p->data = x;
p->next=rear->next;
rear->next = p;
rear = p;
return OK;
}

Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队
{
if(rear == rear->next )
return ERROR;
else
{
x = rear->next->next->data;
rear->next->next = rear->next->next->next;
}
return OK;
}

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

单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList; // 结点和结点指针类型
**/
Status ListEmpty_L(LinkList L)
/ 判定带头结点单链表L是否为空链表。 /
/ 若L是空链表，则返回TRUE，否则FALSE。/
{
if(NULL == L->next) return TRUE;
else return FALSE;
}

/**
【题目】试写一算法，实现带头结点单链表的销毁操作。
单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList; // 结点和结点指针类型
*/
Status DestroyList_L(LinkList &L)
/ 销毁带头结点单链表L，并返回OK。/
{
//if(NULL == L||NULL == L->next) return ERROR；
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;
if(L->next == NULL) return OK;
L->next = NULL;
return OK;

}

/**
【题目】试写一算法，实现带头结点单链表的求表长度操作。
单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList; // 结点和结点指针类型
*/
int ListLength_L(LinkList L)
/ 求带头结点单链表L的长度，并返回长度值。/
/ 若L不是带头结点单链表，则返回-1。 /
{ LNode p;
int i = 0;
if(NULL == L) 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。 /
{
if(i == 0 ) return ERROR;
LinkList p,q,p1,a,b;
int j = 0 ,k=0;
q = (LNode)malloc(sizeof(LNode)) ;
q->data = e;
q->next = NULL;
p1 = L;
b=L;
while(b !=NULL)
{
a = b;
b = a->next;
k++;
}
if(k < i ) return ERROR;
while(j next;
j++;


}
q->next = p->next;
p->next = q;
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。 /
{
LinkList p,q1,q2,q3;
int j=0;
p=L;
while(p->next){
q1 = p;
p=q1->next;
if(j==i-1)
{
q2 = q1;
q3 = p;
}
++j;
}
if(i== 0||jdata;
q2->next = q3->next;
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。 /
{
if(i<=0||L==null) {
Li==null;
return ERROR;
}
LinkList a,b,c;
int j=0,k=0;
Li=(LNode)malloc(sizeof(LNode));
Li->next=null;
a=L;
b=L;
while(a->next!=null){
j++;
a=a->next;
}
if(jnext;
k++;
}
c=b->next;
Li->next=c;
b->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。 /
{ LinkList p1,p2,p3;
int j=0,k=0;
p2 =L;
p1=L;
p3=L;
if(NULL == L||L->next ==NULL) return ERROR;
while(p3->next!=null){
p3=p3->next;
j++;
}
if(j < i||i==0) return ERROR;

while(knext;
k++;
}
p1->next=null;
return OK;
}

/**
【题目】试写一算法，删除带头结点单链表中所有值
为x的元素，并释放被删结点空间。
单链表类型定义如下：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
**/
Status DeleteX_L(LinkList L, ElemType x)
/ 删除带头结点单链表L中所有值为x的元素， /
/ 并释放被删结点空间，返回实际删除的元素个数。/
{ LinkList p1,p2,p3;
int j = 0;
if(NULL ==L) return ERROR;
p1=p2=L;
while(p2!=NULL){
p2 = p1->next;
if(p2->data == x){
p3 = p2;
p2 = p3->next;
p1->next = p2;
free(p3);
j++;
}
else if(p2->data!=x)
{
p1 = p2;
p2 = p1->next;
}


}

return j;
}

/**
【题目】试写一算法，删除带头结点单链表中所有值
小于x的元素，并释放被删结点空间。
单链表类型定义如下：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
**/
Status DeleteSome_L(LinkList L, ElemType x)
/ 删除带头结点单链表L中所有值小于x的元素， /
/ 并释放被删结点空间，返回实际删除的元素个数。/
{ LinkList p1,p2,p3;
int j = 0; p1=p2=L;
if(NULL == p1) return j;

while(p2!=NULL){
p2 = p1->next;
if(p2->data < x &&p2!=null){
p3 = p2;
p2 = p3->next;
p1->next = p2;
free(p3);
j++;
}
else if(p2->data >= x)
{
p1 = p2;
p2 = p1->next;
}


}

return j;

}

/**
【题目】试以顺序表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 = 1; i<L.length; i++){
if(L.rcd[i+1].key < L.rcd[i].key) {
L.rcd[0] = L.rcd[i+1];
j = i+1;
do{
j–;L.rcd[j+1] = L.rcd[j];
} while(L.rcd[0].key<L.rcd[j-1].key);
L.rcd[j] = L.rcd[0];
}
}

}


/**
【题目】如下所述，改写教材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 i,change,j,k;
for(i = L.length,change = 0;i>1;i–)
{
change = i;
for(j = 1;j<i;++j)
{
if(GT(L.rcd[j],L.rcd[j+1]))
{
Swap(L.rcd[j],L.rcd[j+1]);
k++;
change = j+1;
}

}
while(L.rcd[change].key == L.rcd[change-1].key)
{ //用while来跳过那些相同关键字
change = change - 1;
}
i = change;
if(k == 0) i = 1; //当有一次比较没有交换时使i= 1结束操作

k=0;
}
}

/**
【题目】已知记录序列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]; // r[0]闲置
int length;
} RcdSqList;
**/
void CountSort(RcdSqList &L)
/ 采用顺序表存储结构，在函数内自行定义计数数组c /
{
int k = L.length ;
RcdSqList L1;
int c[27];
int i,j;
for(i = 1;i <= L.length ;i++)
for(j = 1;j <= L.length;j++)
{
if(L.rcd[i].key<L.rcd[j].key)
c[i]++;
}

for(i = 1;i<=L.length ;i++)
{
L1.rcd[c[i]+1].key = L.rcd[i].key;
}
for(i = 1;i<=L.length ;i++)
{
L.rcd[L.length-i+1].key = L1.rcd[i].key;
}
}


/**
【题目】已知某哈希表的装载因子小于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,size;
char c;
for(c=’A’;c<=’Z’;c++){
for(i=0;inext) {
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,k,j;
HLink p,q,p1;
H.rcd = (HLink)malloc(7sizeof(HLink));
H.size = 7;
H.count = 0;
for(i = 0;es[i] >= ‘A’;i++)
{
p = (HNode)malloc(sizeof(HNode));
p->next = NULL;
p->data = es[i];
k = Hash( H, p->data) ;
if(NULL !=H.rcd[k])
{ // 判断其中是否有相同的HKeyType
p1 = H.rcd[k];
while(NULL != p1)
{ //用j作为标记，如果j = 0表示没有相同的，插入p
if(p1->data == p->data)
j = 1;
p1 = p1->next;
}
if(j == 0)
{
q = H.rcd[k];
p->next = q;
H.rcd[k] = p;

}
j = 0;
}
else
H.rcd[k] = p; //为什么H.rcd[k]->next = p;不会报错
H.count++;
}
}

/**
【题目】试编写如下定义的递归函数的递归算法:
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(m<0||n<0)="" return="" -1;="" else="" if(m="=0&&n">=0)
return 0;
else if(m>0&&n>=0)
return G(m-1,2n)+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;="" else="" if(n="=0)" n+1;="">0) return nF(n/2);

}

/**
【题目】求解平方根 的迭代函数定义如下：
sqrt(A,p,e) = p 当|pp-A|=e
其中，p是A的近似平方根，e是结果允许误差。试写出相
应的递归算法。
**/
float Sqrt(float A, float p, float e)
{ if(fabs(pp-A)<e)
return p;
else
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;="" if(m="=0)" n+1;="" else="" if(m!="0&&n==0)" akm(m-1,1);="" akm(m-1,akm(m,n-1))="" ;="" }="" **********="" 【题目】试写出求递归函数f(n)的非递归算法：="" f(n)="n+1" 当n="0">0
**/
int F(int n)
/ 如果 n<0则返回-1 /
{ int i = n,count=1;
if(n<0) return="" -1;="" else="" if(n="=0)" n+1;="" for(;i="">0;i=i/2)
count = counti ;
return count;
}

/**
【题目】求解平方根 的迭代函数定义如下：
sqrt(A,p,e) = p 当|pp-A|=e
其中，p是A的近似平方根，e是结果允许误差。试写出相
应的非递归算法。
**/
float Sqrt(float A, float p, float e)
{ float mp=p;
if(fabs(pp-A)<e)
return p;
else
while(fabs(mpmp-A)>=e)
{
mp=(mp+A/mp)/2 ;
}
return mp;

}

/**
【题目】假设以二维数组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 /
{
if(i0>m||j0>n)//初次调用时下标不合法
{
return;
}
int color;
color=g[i0][j0];
g[i0][j0]=c;
if(i0-1>=1)//判断是否越界，下同
{
if(g[i0-1][j0]==color)
{
ChangeColor(g,m,n,c,i0-1,j0);
}
}
if(i0+1<=m)
{
if(g[i0+1][j0]==color)
{
ChangeColor(g,m,n,c,i0+1,j0);
}
}
if(j0-1>=1)
{
if(g[i0][j0-1]==color)
{
ChangeColor(g,m,n,c,i0,j0-1);
}
}
if(j0+1<=n)
{
if(g[i0][j0+1]==color)
{
ChangeColor(g,m,n,c,i0,j0+1);
}
}
}

/**
【题目】若两棵二叉树T1和T2皆为空，或者皆不空
且T1的左、右子树和T2的左、右子树分别相似，则
称二叉树T1和T2相似。试编写算法，判别给定两棵
二叉树是否相似。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild, rchild;
} BiTNode, BiTree;
**/
Status Similar(BiTree T1, BiTree T2)
/ 判断两棵二叉树是否相似的递归算法 /
{ if(T1==null&&null==T2) return true;
else if(T1&&T2){
if(ERROR== Similar(T1->lchild, T2->lchild))return ERROR;
if(ERROR== Similar(T1->rchild, T2->rchild))return ERROR;
}else return ERROR;
return true;
}

/**
【题目】编写递归算法，求对二叉树T先序遍历时
第k个访问的结点的值。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild, rchild;
} BiTNode, BiTree;
**/
TElemType PreOrderK(BiTree T, int k)
/ 求对二叉树T先序遍历时第k个访问的结点的值。/
/ 若失败，则返回’#’ /
{

int i=0,count=0; //i为循环变量、count为记录根结点的左子树的结点个数
TElemType d; //定义一个返回值变量d
BiTree a[20],b; //a[20]记录左子树的根结点,b为一个中间变量
if(k<=0||!T) return ‘#’; //当k为0或者T空时，没有找到结点，返回’#’
if(k==1) return T->data; //当k从给定的数减到1时，表示找到，返回bt->data
d=PreOrderK(T->lchild,k-1); //左子树递归
if(d!=’#’) //当找到T时，返回T
return(d);
b=T->lchild; //没有找到，继续找
while(b||i) //下面是计算左子树有多少个结点的算法，并记录在count中
{
if(b) //当左子树非空时，
{
a[i]=b; //记录第i个结点在a[i]中，用来计算本结点的右子树用的
i++; //计算下一个结点的序号
b=b->lchild; //对下一个结点操作
count++; //记录结点数
}
else
{
i–; //如果b空，表示执行到最左的叶子，现在要找到上一个结点的右子树
b=a[i]; //把上一个结点赋给b
b=b->rchild; //使b指向右子树
}
}
d=PreOrderK(T->rchild,k-count-1); //递归右子树,并返回k-count-1，表示要找的结点可能在右子树的第k-count-1的位置
if(d!=’#’) //对T判断，当T不为’#’时，表示找到，返回T
return (d);
else //否则返回 ‘#’表示没有找到
return ‘#’;
}

/**
【题目】编写递归算法，计算二叉树T中叶子结点的数目。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild, rchild;
} BiTNode, BiTree;
**/

int Leaves(BiTree T)
/ 计算二叉树T中叶子结点的数目/
{ if(!T) return 0; /空树没有叶子/
else if(!T->lchild&&!T->rchild) return 1; /叶子结点/
else return Leaves(T->lchild)+Leaves(T->rchild);/左子树的叶子数加上右子树的叶子数/

}


/**
【题目】试利用栈及其基本操作写出二叉树T的非递归
的先序遍历算法。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild,rchild;
} BiTNode, BiTree;
可用栈类型Stack的相关定义：
typedef BiTree SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
**/

void PreOrder(BiTree T, void (visit)(TElemType))
/ 使用栈，非递归先序遍历二叉树T， /
/ 对每个结点的元素域data调用函数visit /
{ Stack s;
InitStack(s);
BiTree p = T;
while(p){
visit(p->data);
if(p->rchild)
Push(s,p->rchild);
if(p->lchild)
p = p->lchild;
else
if(StackEmpty(s)!=true) Pop(s, p);
else
p = null;
}

}


/**
【题目】试利用栈及其基本操作写出二叉树T的非递归
的后序遍历算法(提示：为分辨后序遍历时两次进栈的
不同返回点，需在指针进栈时同时将一个标志进栈）。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild,rchild;
} BiTNode, BiTree;
可用栈类型Stack的相关定义：
typedef struct {
struct BiTNode ptr; // 二叉树结点的指针类型
int tag; // 0..1
} SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
**/
void PostOrder(BiTree bt, void (visit)(TElemType))
/ 使用栈，非递归后序遍历二叉树T， /
/ 对每个结点的元素域data调用函数visit /
{
Stack S;
InitStack(S);
SElemType e;
BiTree p=bt;
int tag=0;
if(bt){
e.tag=0;
while(!StackEmpty(S)||p==bt){
while(p&&!tag){
e.ptr=p;
if(p->lchild){//如果存在左子树
p=p->lchild;
e.tag=0;
}
else{//否则为右子树
p=p->rchild;
e.tag=1;
}
Push(S,e);
}//while
GetTop(S,e);
if(!StackEmpty(S)&&e.tag){
Pop(S,e); //叶子结点出栈
p=e.ptr;
visit(p->data);//输出该结点
}
if(!StackEmpty(S)){
Pop(S,e); //得到上一层结点
p=e.ptr;
if(e.tag){//右子树已经入栈
visit(p->data);
p=NULL;
}
else{//右子树没入过栈
if(p->rchild){
p=p->rchild;
tag=0;
e.tag=1;
Push(S,e);
}
else{//没有右子树
visit(p->data);
p=NULL;
}
}
}
else{//栈空则，p为NULL
p=NULL;
}
}//while
}//if
}


/**
【题目】二叉树采用三叉链表的存储结构，试编写
不借助栈的非递归中序遍历算法。
三叉链表类型定义：
typedef struct TriTNode {
TElemType data;
struct TriTNode parent, lchild, rchild;
} TriTNode, TriTree;
**/
void InOrder(TriTree PT, void (visit)(TElemType))
/ 不使用栈，非递归中序遍历二叉树PT， /
/ 对每个结点的元素域data调用函数visit /
{
TriTree p,pr;
if(PT!=NULL)
{
p = PT;
while(p!=NULL)
{ if(p->lchild==NULL) visit(p->data);
//输出有右子树的结点
if(p->lchild) p = p->lchild;
else
if(p->rchild) p = p->rchild;
else
{

do{
pr = p;
p = p->parent;
if(p->rchild!=pr) //如果pr是p的右子树则不输出
visit(p->data);
}while(p!=NULL&&(p->rchild==pr||NULL==p->rchild));
if(p!=NULL) p = p->rchild;
}
}
}
}

/**
【题目】假设在三叉链表的结点中增设一个标志域
(mark取值0,1或2)以区分在遍历过程中到达该结点
时应继续向左或向右或访问该结点。试以此存储结
构编写不用栈辅助的二叉树非递归后序遍历算法。
带标志域的三叉链表类型定义：
typedef struct TriTNode {
TElemType data;
struct TriTNode lchild, rchild, parent;
int mark; // 标志域
} TriTNode, TriTree;
**/
void PostOrder(TriTree T, void (visit)(TElemType))
/ 不使用栈，非递归后序遍历二叉树T， /
/ 对每个结点的元素域data调用函数visit /
{
TriTree p,pr;
if(T!=NULL)
{
p = T;
while(p!=NULL)
{
if(p->lchild) p = p->lchild;
else
if(p->rchild) p = p->rchild;
else
{
do{
pr = p;
visit(pr->data);
p = p->parent;
}while(p!=NULL&&(p->rchild==pr||NULL==p->rchild));
if(p!=NULL) p = p->rchild;
}
}
}

}


/**
【题目】编写递归算法，将二叉树中所有结点的
左、右子树相互交换。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild, rchild;
} BiTNode, BiTree;
**/
void ExchangeSubTree(BiTree &T)
/ 将二叉树中所有结点的左、右子树相互交换 /
{ BiTree p;
if(!T) return;
if(T->lchild) ExchangeSubTree(T->lchild);
if(T->rchild) ExchangeSubTree(T->rchild);
p = T->lchild;
T->lchild = T->rchild;
T->rchild = p;

}

/**
【题目】编写递归算法：求二叉树中以元素值
为x的结点为根的子树的深度。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild, rchild;
} BiTNode, BiTree;
**/
int BirTreeDepth(BiTree T){
int depthLeft,depthRight;
if(null==T) return 0;
else {
depthLeft = BirTreeDepth(T->lchild);
depthRight = BirTreeDepth(T->rchild);
return 1+(depthLeft > depthRight?depthLeft:depthRight);
}
}
int Findx(BiTree T,BiTree &p,TElemType x){
if(T){
if(T->data==x){
p=T;
return 0;
}
else{
Findx(T->lchild,p,x);
Findx(T->rchild,p,x);
}
}
}

int Depthx(BiTree T, TElemType x)
/ 求二叉树中以值为x的结点为根的子树深度/
{
BiTree p=NULL;
Findx(T,p,x);
return BirTreeDepth(p);
}


/**
【题目】编写递归算法：对于二叉树中每一个元素值为x
的结点，删去以它为根的子树，并释放相应的空间。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild, rchild;
} BiTNode, BiTree;
**/
void Destroy(BiTree &T){
if(T){
Destroy(T->lchild);
Destroy(T->rchild);
free(T);
}
}
/BiTree find(BiTree &T, char x){
if(!T) return null;
if(T->data == x) return T;
find(T->lchild,x); find(T->rchild,x);
} /

void ReleaseX(BiTree &T, char x)
/ 对于二叉树T中每一个元素值为x的结点，/
/ 删去以它为根的子树，并释放相应的空间 /
{
if(!T) return ;
if(T->data==x)
Destroy(T);
ReleaseX(T->lchild, x);
ReleaseX(T->rchild, x);

}

/**
【题目】编写复制一棵二叉树的递归算法。
二叉链表类型定义：
typedef char TElemType; // 设二叉树的元素为char类型
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild, rchild;
} BiTNode, BiTree;
**/
void CopyBiTree(BiTree T, BiTree &TT)
/ 递归复制二叉树T得到TT /
{
if(!T) return ;
TT = (BiTree)malloc(sizeof(BiTNode));
if(!TT) return ;
TT->data = T->data;
if(T->lchild) CopyBiTree(T->lchild,TT->lchild);
if(T->rchild) CopyBiTree(T->rchild,TT->rchild);
}

/**
【题目】编写算法判别给定二叉树是否为完全二叉树。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild, rchild;
} BiTNode, BiTree;
可用队列类型Queue的相关定义：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e);
Status DeQueue(Queue &Q, QElemType &e);
Status GetHead(Queue Q, QElemType &e);
Status QueueEmpty(Queue Q);
**/

Status CompleteBiTree(BiTree bt)
/ 判别二叉树T是否为完全二叉树/
{ Queue Q;
QElemType p;
int tag=0;
EnQueue(Q,bt);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
if(!p) tag=1; //如果到最后输出都为空，表示已经遍历完成，确认是完全树
else if(tag) return ERROR;
else
{
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild);
}
}
return OK;
}

/**
【题目】试编写一个二叉排序树的判定算法。
二叉排序树的类型BSTree定义如下：
typedef struct {
KeyType key;
… … // 其他数据域
} TElemType;
typedef struct BiTNode {
TElemType data;
struct BSTNode lchild, rchild;
}BSTNode, BSTree;
**/
Status IsBSTree(BSTree t)
/ 判别二叉树T是否为二叉排序树。/
/ 若是，则返回TRUE，否则FALSE /
{
BSTree p,q;
if(t)
{ p=t->lchild;
q=t->rchild;
if(p&&p->data.key>=t->data.key)
return FALSE;
if(q&&q->data.key<=t->data.key)
return FALSE;

if (IsBSTree(p))
return IsBSTree(q);
return FALSE;

}
return TRUE;
}

/**
【题目】编写递归算法，从大到小输出给定二叉排序树
中所有关键字不小于x的数据元素。
二叉排序树的类型BSTree定义如下：
typedef struct {
KeyType key;
… … // 其他数据域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode lchild,rchild;
}BSTNode, BSTree;
**/
void OrderOut(BSTree t, KeyType x, void(visit)(TElemType))
/ 调用visit(T->data)输出 /
{ KeyType key = t->data.key;

if(!t)
{
return;
}
if(key>=x)
{
OrderOut(t->rchild,x,visit);
visit(t->data);
OrderOut(t->lchild,x,visit);
}
else
{
OrderOut(t->rchild,x,visit);
}
}

/**
【题目】试写一非递归算法，在二叉查找树T中插入元素e。
二叉查找树的类型BSTree定义如下：
typedef struct {
KeyType key;
… … // 其他数据域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode lchild,rchild;
} BSTNode, BSTree;
**/
Status InsertBST_I(BSTree &T, TElemType k)
/ 在二叉查找树T中插入元素e的非递归算法/
{ BSTree p,L,q = T ;
p = (BSTree)malloc(sizeof(BSTNode));
if(p == NULL) return FALSE;
p->data = k; p->lchild = NULL; p->rchild = NULL;
while(q!=NULL)
{
if(q->data.key == k.key) return FALSE;
if(q->data.key > k.key)
{
if(q->lchild!=NULL) q = q->lchild;
else q->lchild = p;
}
if(q->data.key < k.key)
{
if(q->rchild!=NULL) q = q->rchild;
else q->rchild = p;
}
}

}

/**
【题目】试编写算法，求二叉树T中结点a和b的最近共同祖先。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild,rchild;
} BiTNode, BiTree;
可用栈类型Stack的相关定义：
typedef struct {
BiTNode ptr; // 二叉树结点的指针类型
int tag; // 0..1
} SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
int StackLength(SqStack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
**/
void findElem(BiTree T,TElemType e,Stack &s)
{
BiTree t=T;
BiTNode bip;
SElemType se;
while(t)
{
while(t->lchild)
{
if(t->data==e) return ;
se.ptr=t;se.tag=1;
Push(s,se);
t=t->lchild;
}
if(t->data==e) return ;
if(t->rchild) {se.ptr=t;se.tag=1;Push(s,se);t=t->rchild;}
else
{
bip=t;Pop(s,se);t=se.ptr;
while(t->rchild==bip||!t->rchild)
{
bip=t;
if(t!=T) {Pop(s,se);t=se.ptr;}
else return;
}
se.ptr=t;se.tag=1;
Push(s,se);
t=t->rchild;
}
}
}



BiTree CommAncestor(BiTree T, TElemType a, TElemType b)
/ 求二叉树T中结点a和b的最近共同祖先/
{ Stack sa,sb,st;
SElemType sea,seb;
BiTree bi,bii;

InitStack(sa);InitStack(sb);InitStack(st);
findElem(T,a,sa);
findElem(T,b,sb);

while(!StackEmpty(sa))
{
Pop(sa,sea);
bi=sea.ptr;
st=sb;
while(!StackEmpty(st))
{
Pop(st,seb);
bii=seb.ptr;
if(bi->data==bii->data)return bi;
}
}

}


/**
【题目】在二叉排序树的每个结点中增设一个lsize域，
其值为该结点的左子树中的结点数加1。试编写时间复杂
度为O(logn)的算法，求树中第k小的结点的位置。
二叉排序树的类型BSTree定义如下：
typedef char KeyType;

typedef struct BSTNode {
KeyType key;
struct BSTNode lchild,rchild;
int lsize; // 新增域，值为左子树的结点数+1
} BSTNode, BSTree;
**/


BSTNode Ranking(BSTree T, int k)
/ 在含lsize域的二叉排序树T中，/
/ 求指向T中第k小的结点的指针 /
{ if(!T) return null;
if(T->lsize==k) return T;
else if(T->lsize>k) return Ranking(T->lchild, k) ;
else return Ranking(T->rchild, k-T->lsize);

}

/**
【题目】假设二叉排序树T的每个结点的平衡因子域bf当前
均为0。试编写算法，求二叉排序树T的深度，并为每个结点
的bf域赋予正确的平衡因子值。
平衡二叉排序树的类型BBSTree定义如下：
typedef char KeyType;
typedef struct BBSTNode {
KeyType key;
int bf; // 平衡因子
struct BBSTNode lchild,rchild;
} BBSTNode, BBSTree;
**/
/int depth(BBSTree t){
int l;
int r;
if(!t) return 0;
else {
l = depth(t->lchild);
r = depth(t->rchild);
return 1+(l>r?l:r);
}
} /

int Depth_BF(BBSTree T)
/ 求二叉排序树T的深度，并为每个结点/
/ 的bf域赋予正确的平衡因子值。 /
{ int l,r;
if(!T) return 0;
else {
l = Depth_BF(T->lchild);
r = Depth_BF(T->rchild);
T->bf = l-r;
return 1+(l>r?l:r);
}
}


/**
【题目】编写平衡二叉排序树的右平衡处理算法。
平衡二叉排序树的类型BBSTree定义如下：
typedef char KeyType;
typedef struct BBSTNode {
KeyType key;
int bf; // 平衡因子
struct BBSTNode lchild,rchild;
} BBSTNode, BBSTree;
可调用下列旋转调整操作：
void L_Rotate(BBSTree &p); // 对最小失衡子树p做左旋调整
void R_Rotate(BBSTree &p); // 对最小失衡子树p做右旋调整
**/

void RightBalance(BBSTree &T)
/ 实现对二叉树T的右平衡处理/
{
BBSTree lc,rd;
rd = T->rchild;
switch(rd->bf){
case RH:
T->bf = rd->bf = EH; L_Rotate(T); break;
case LH:
lc = rd->lchild;
switch(lc->bf){
case LH: T->bf = EH; lc->bf = EH; break;
case EH: T->bf = rd->bf = EH;break;
case RH: T->bf=LH; lc->bf = EH; break;
}
lc->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
}

}

/**
【题目】试编写算法，对一棵以孩子兄弟链表表示
的树统计叶子的个数。
孩子兄弟链表类型定义：
typedef struct CSTNode {
TElemType data;
struct CSTNode firstChild, nextSibling;
} CSTNode, CSTree;
**/
void Count(CSTree T, int &n){
if(T){
if(!T->firstChild) n++;
Count(T->firstChild, n);
Count(T->nextSibling, n);
}
}

int Leave(CSTree T) / 统计树T的叶子数/
{
int n =0;
Count(T , n);
return n;
}

/**
【题目】试编写算法，求一棵以孩子兄弟链表表示的树的度。
孩子兄弟链表类型定义：
typedef struct CSTNode {
TElemType data;
struct CSTNode firstChild, nextSibling;
} CSTNode, CSTree;
**/

int Degree(CSTree T) / 求树T的度/
{
int ds,dt,d;
CSTree p;
if(!T) return 0;
else { ds=0;dt=0;
for( p = T->firstChild; p ; p= p->nextSibling){
dt++;
d= Degree(p);
if(d>ds) ds =d;
}

return ds>dt?ds:dt;
}

}


/**
【题目】试编写算法，对以双亲表示法存储的树计算深度。
typedef struct {
TElemType data;
int parent; // 双亲位置
} PTNode; // 结点类型
typedef struct {
PTNode nodes[MAX_TREE_SIZE]; // 结点存储空间
int n, r; // 结点数和根的位置
} PTree;
**/
int PTreeDepth(PTree T) / 求树T的深度/
{
int maxdep = 0,i,dep,j;
for(i=0; i0; j=T.nodes[j].parent) dep++;
if(dep>maxdep) maxdep = dep;
}
return maxdep+1;

}


/**
【题目】试编写算法，对以双亲孩子表示法存储的树计算深度。
孩子链表类型定义：
typedef struct ChildNode { // 孩子结点
int childIndex;
struct ChildNode nextChild;
} ChildNode; // 孩子结点类型
typedef struct {
TElemType data;
int parent; // 双亲位置
struct ChildNode firstChild; // 孩子链表头指针
} PCTreeNode; // 结点类型
typedef struct {
PCTreeNode nodes; // 结点存储空间
int n, r; // 结点数和根的位置
} PCTree;
**/

int fun(PCTree T, int pos)
{
if(T.nodes[pos].firstChild == NULL) return 1;
ChildNode temp = T.nodes[pos].firstChild;
int depth = 1, max = 1;

while(temp != NULL)
{
if( T.nodes[temp->childIndex].firstChild != NULL)
{
depth = fun(T, temp->childIndex);
if(depth > max)
max = depth;
}
temp = temp->nextChild;
}

return max + 1;

}
int PCTreeDepth(PCTree T) / 求树T的深度/
{
int depth;
depth = fun(T, T.r);
return depth;
}


/**
【题目】试编写算法，对以孩子-兄弟链表表示的树计算深度。
孩子兄弟链表类型定义：
typedef struct CSTNode {
TElemType data;
struct CSTNode firstChild, nextSibling;
} CSTNode, CSTree;
**/
int TreeDepth(CSTree T)
/ 求树T的深度/
{
int dep1,dep2,dep;
if(!T) dep=0;
else{
dep1 = TreeDepth(T->firstChild);
dep2 = TreeDepth(T->nextSibling);
dep = dep1+1>dep2?dep1+1:dep2;
}
return dep;
}


/**
【题目】已知一棵树的由根至叶子结点按层次输出的
结点序列及每个结点的度。试编写算法，构造此树的
孩子兄弟链表。
孩子兄弟链表类型定义：
typedef struct CSTNode {
TElemType data;
struct CSTNode firstChild, nextSibling;
} CSTNode, CSTree;
**/
CSTree CreateCSTNode(char e) {
CSTNode p = NULL;
p = (CSTNode)malloc(sizeof(CSTNode));
p->data = e;
p->firstChild = NULL;
p->nextSibling = NULL;
return p;
}


void BuildCSTree(CSTree &T, char node, int degree)
/ 由结点的层序序列node和各结点的度degree构造树的孩子兄弟链表T /
{
int i, j, present=1;
CSTree Tree[50];

if(NULL == node) {
return;
}
Tree[0] = CreateCSTNode(node[0]);
T = Tree[0];
for(i=0; node[i]!=’\0’; i++) {
if(degree[i]!=0) {
Tree[present] = CreateCSTNode(node[present]);
Tree[i]->firstChild = Tree[present];
present ++;
for(j=2; j<=degree[i]; j++) {
Tree[present] = CreateCSTNode(node[present]);
Tree[present-1]->nextSibling = Tree[present];
present ++;
}
}
}
}


/**
【题目】试编写非递归算法，实现并查集带路径压缩的
查找操作。
并查集的类型定义如下：
typedef struct {
int parent;
int n;
} MFSet;
**/
int find(MFSet S, int i)
/ 并查集带路径压缩的查找的非递归实现 /
{ if(i<0||i>=S.n) return -1;
if(S.parent[i]<0) return i;
S.parent[i] = find(S,S.parent[i]);
return S.parent[i];
}


/**
【题目】编写算法，创建有向图的邻接数组存储结构。
图的邻接数组存储结构的类型定义如下：
#define UNVISITED 0
#define VISITED 1
#define MAX_VEX_NUM 4
#define INFINITY MAXINT // 计算机允许的整数最大值，即∞
typedef int VRType;
typedef char InfoType;
typedef char VexType;
typedef enum {DG,DN,UDG,UDN} GraphKind; // 有向图,有向网,无向图,无向网
typedef struct {
VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；
// 对带权图，则为权值类型
InfoType info; // 该弧相关信息的指针(可无)
}ArcCell;//,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
ArcCell arcs[MAX_VEX_NUM][MAX_VEX_NUM]; // 关系数组
VexType vexs[MAX_VEX_NUM]; // 顶点数组
int n, e; // 顶点数和边（弧）数
GraphKind kind; // 图的类型
} MGraph; // 邻接数组类型
typedef struct {
VexType v, w;
int inf;
} ArcInfo;
可调用以下基本操作：
Status InitGraph(MGraph &G, GraphKind kind, int n);
// 初始化含n个顶点空间的kind类的空图G
int LocateVex(MGraph G, VexType v); // 查找顶点v在图G中的位序
**/
Status CreateDG(MGraph &G, VexType vexs, int n,
ArcInfo arcs, int e)
/ 创建含n个顶点和e条边的有向图G，vexs为顶点信息，arcs为边信息/
{ int i,j,k;
VexType v,w;
if((OVERFLOW==InitGraph(G, G.kind, n))) return ERROR;
G.n = n;G.e = e;
for(i = 0; i=G.n) return -1;
if(G.vexs[k].firstArc != NULL)
p = G.vexs[k].firstArc;
for( ; p!=NULL;p = p->next)
{
j++;
}
return j;

}

/**
【题目】编写算法，计算以邻接表方式存储的有向图G中
k顶点的入度。
图的邻接表存储结构的类型定义如下：
#define UNVISITED 0
#define VISITED 1
#define INFINITY MAXINT // 计算机允许的整数最大值，即∞
typedef char VexType;
typedef enum {DG,DN,UDG,UDN} GraphKind; // 有向图,有向网,无向图,无向网
typedef struct AdjVexNode {
int adjvex; // 邻接顶点在顶点数组中的位序
struct AdjVexNode next; // 指向下一个邻接顶点（下一条边或弧）
int info; // 存储边（弧）相关信息，对于非带权图可不用
} AdjVexNode, AdjVexNodeP; // 邻接链表的结点类型
typedef struct VexNode {
VexType data; // 顶点值，VexType是顶点类型，由用户定义
struct AdjVexNode firstArc; // 邻接链表的头指针
} VexNode; // 顶点数组的元素类型
typedef struct {
VexNode vexs; // 顶点数组，用于存储顶点信息
int n, e; // 顶点数和边（弧）数
GraphKind kind; // 图的类型
int tags; // 标志数组
} ALGraph; // 邻接表类型
**/
int inDegree(ALGraph G, int k)
/ 求有向图G中k顶点的入度。若k顶点不存在，则返回-1 /
{
int i ,j;
AdjVexNodeP p;
if(k<0||k>=G.n) return -1;
for(i = 0,j=0;inext)
if(p->adjvex == k)
j++;
}
}
return j;
}

/**
【题目】编写算法，创建有向图的邻接表存储结构。
图的邻接表存储结构的类型定义如下：
#define UNVISITED 0
#define VISITED 1
#define MAX_VEX_NUM 4
#define INFINITY MAXINT // 计算机允许的整数最大值，即∞
typedef char VexType;
typedef enum {DG,DN,UDG,UDN} GraphKind; // 有向图,有向网,无向图,无向网
typedef struct AdjVexNode {
int adjvex; // 邻接顶点在顶点数组中的位序
struct AdjVexNode next; // 指向下一个邻接顶点（下一条边或弧）
int info; // 存储边（弧）相关信息，对于非带权图可不用
} AdjVexNode, AdjVexNodeP; // 邻接链表的结点类型
typedef struct VexNode {
VexType data; // 顶点值，VexType是顶点类型，由用户定义
struct AdjVexNode firstArc; // 邻接链表的头指针
} VexNode; // 顶点数组的元素类型
typedef struct {
VexNode vexs[MAX_VEX_NUM]; // 顶点数组，用于存储顶点信息
int n, e; // 顶点数和边（弧）数
GraphKind kind; // 图的类型
int tags; // 标志数组
} ALGraph; // 邻接表类型

可调用以下基本操作：
int LocateVex(ALGraph G, VexType v); // 查找顶点v在图G中的位序
**/
Status CreateDG(ALGraph &G, VexType vexs, int n,
ArcInfo arcs, int e)
/ 创建含n个顶点和e条边的有向图G，vexs为顶点信息，arcs为边信息/
{
int i,j,k;
VexType v,w;
AdjVexNodeP p;
G.n = n; G.e = e;
// G.vexs = (VexNode)malloc(sizeof(VexNode)n);
G.tags = (int)malloc(sizeof(int)n);
for(i = 0;i<G.n;i++)
{
G.tags[i] = UNVISITED;
G.vexs[i].data = vexs[i];
G.vexs[i].firstArc = NULL;
}
for(k = 0;k<G.e;k++)
{
v = arcs[k].v; w=arcs[k].w;
i = LocateVex(G,v); j = LocateVex(G,w);
if(i<0||j<0) return ERROR;

p = (AdjVexNode)malloc(sizeof(AdjVexNode));
if(NULL == p) return ERROR;
p->adjvex = j;
p->next = G.vexs[i].firstArc;
G.vexs[i].firstArc = p;

}
}

/**
【题目】编写算法，创建无向图的邻接表存储结构。
图的邻接表存储结构的类型定义如下：
#define UNVISITED 0
#define VISITED 1
#define MAX_VEX_NUM 4
#define INFINITY MAXINT // 计算机允许的整数最大值，即∞
typedef char VexType;
typedef enum {DG,DN,UDG,UDN} GraphKind; // 有向图,有向网,无向图,无向网
typedef struct AdjVexNode {
int adjvex; // 邻接顶点在顶点数组中的位序
struct AdjVexNode next; // 指向下一个邻接顶点（下一条边或弧）
int info; // 存储边（弧）相关信息，对于非带权图可不用
} AdjVexNode, AdjVexNodeP; // 邻接链表的结点类型
typedef struct VexNode {
VexType data; // 顶点值，VexType是顶点类型，由用户定义
struct AdjVexNode firstArc; // 邻接链表的头指针
} VexNode; // 顶点数组的元素类型
typedef struct {
VexNode vexs[MAX_VEX_NUM]; //vexs; 顶点数组，用于存储顶点信息
int n, e; // 顶点数和边（弧）数
GraphKind kind; // 图的类型
int tags; // 标志数组
} ALGraph; // 邻接表类型

可调用以下基本操作：
int LocateVex(ALGraph G, VexType v); // 查找顶点v在图G中的位序
**/
Status CreateUDG(ALGraph &G, VexType vexs, int n,
ArcInfo arcs, int e)
/ 创建含n个顶点和e条边的无向图G，vexs为顶点信息，arcs为边信息/
{
int i,j,k;
VexType v,w;
AdjVexNodeP p,q;
G.n = n; G.e = e;
// G.vexs = (VexNode)malloc(sizeof(VexNode)n);
G.tags = (int)malloc(sizeof(int)n);
for(i = 0;i<G.n;i++)
{
G.tags[i] = UNVISITED;
G.vexs[i].data = vexs[i];
G.vexs[i].firstArc = NULL;
}
for(k = 0;k<G.e;k++)
{
v = arcs[k].v; w=arcs[k].w;
i = LocateVex(G,v); j = LocateVex(G,w);
if(i<0||j<0) return ERROR;
p = (AdjVexNode)malloc(sizeof(AdjVexNode));
if(NULL == p) return ERROR;
p->adjvex = j;
p->next = G.vexs[i].firstArc;
G.vexs[i].firstArc = p;


q = (AdjVexNode*)malloc(sizeof(AdjVexNode));
if(NULL == q) return ERROR;
q->adjvex = i;
q->next = G.vexs[j].firstArc;
G.vexs[j].firstArc = q;
}
}
赏

你的鼓励，是使我前进的力量

微信
|阅读量()

扫一扫，分享到微信

微信分享二维码
总访问量: 总访客:

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>我只是个使用者，感谢litten<br>谢谢大家