第1章 绪论
1．4 试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：
通过参数表中的参数显式传递。
通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。
void polyvalue()
{
int n,p,i,x,xp,sum;
float a[];
float *p=a;
printf("Input number of terms:");
scanf("%d",&n);
printf("Input the %d coefficients from a0 to a%d:\n",n,n);
for(i=0;i<=n;i++) scanf("%f",p++);
printf("Input value of x:");
scanf("%f",&x);
p=a;xp=1;sum=0; //xp用于存放x的i次方
for(i=0;i<=n;i++)
{
sum+=xp*(*p++);
xp*=x;
}
printf("Value is:%f",sum);
}//polyvalue
第二章 线性表
2．4设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。
Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中
{
if(va.length+1>va.listsize) return ERROR;
va.length++;
for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
return OK;
}//Insert_SqList
2．6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。
Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素
{
p=L;
while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素
if(p->next)//如果还有比mink更大的元素
{
q=p->next;
while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素
p->next=q;
}
}//Delete_Between
2．7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。
以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。
（2）以单链表作存储结构。
void reverse(SqList &A)//顺序表的就地逆置
{
for(i=1,j=A.length;i<j;i++,j--)
A.elem[i]<->A.elem[j];
}//reverse
2．8假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C。
while(pa||pb)
{
if(pa->data<pb->data||!pb)
{
pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
}
pre=pc;
}
C=A;A->next=pc; //构造新表头
}//reverse_merge
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.
2．9假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱
{
p=s;
while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p
p->next=s;
return OK;
}//Delete_Pre
2．10已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.
{
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));p=A;
B=(CiList*)malloc(sizeof(CiLNode));q=B;
C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点
while(s)
{
if(isalphabet(s->data))
{
p->next=s;p=s;
}
else if(isdigit(s->data))
{
q->next=s;q=s;
}
else
{
r->next=s;r=s;
}
}//while
p->next=A;q->next=B;r->next=C; //完成循环链表
}//LinkList_Divide
2．11设线性表A=(a1,a2,…,am)，B=(b1,b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a1,b1,…,am,bm,bm+1,…,bn) 当m≤n时；
或者 C= (a1,b1,…,an,bn,an+1,…,am) 当m>n时。
线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q; //将B的元素插入
if(s)
{
t=q->next;q->next=s; //如A非空,将A的元素插入
}
p=s;q=t;
}//while
}//merge1
2．12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。
void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B
{
p=L->next;
A=(PolyNode*)malloc(sizeof(PolyNode));
B=(PolyNode*)malloc(sizeof(PolyNode));
pa=A;pb=B;
while(p!=L)
{
if(p->data.exp!=2*(p->data.exp/2))
{
pa->next=p;pa=p;
}
else
{
pb->next=p;pb=p;
}
p=p->next;
}//while
pa->next=A;pb->next=B;
}//Divide_LinkedPoly
2．14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。
float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值
{
PolyTerm *q;
xp=1;q=P.data;
sum=0;ex=0;
while(q->coef)
{
while(ex<q->exp) xp*=x0;
sum+=q->coef*xp;
q++;
}
return sum;
}//GetValue_SqPoly
第3章 限定性线性表——栈和队列
3．5试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
InitStack(s);
while((e=getchar())!='&')
push(s,e);
while((e=getchar())!='@')
{
if(StackEmpty(s)) return 0;
pop(s,c);
if(e!=c) return 0;
}
if(!StackEmpty(s)) return 0;
return 1;
}//IsReverse
3．6假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new
{
p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号
InitStack(s); //s为运算符栈
while(*p)
{
if(*p是字母)) *q++=*p; //直接输出
else
{
c=gettop(s);
if(*p优先级比c高) push(s,*p);
else
{
while(gettop(s)优先级不比*p低)
{
pop(s,c);*(q++)=c;
}//while
push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则
}//else
}//else
p++;
}//while
}//NiBoLan //参见编译原理教材
3．7假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q
{
Q=(CiLNode*)malloc(sizeof(CiLNode));
Q->next=Q;
}//InitCiQueue
void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素
{
p=(CiLNode*)malloc(sizeof(CiLNode));
p->data=x;
p->next=Q->next; //直接把p加在Q的后面
Q->next=p;
Q=p;//修改尾指针
}
Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x
{
if(Q==Q->next) return INFEASIBLE; //队列已空
p=Q->next->next;
x=p->data;
Q->next->next=p->next;
free(p);
return OK;
}//DeCiQueue
3．8要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法
{
if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0表示"空",1表示"满"
return OVERFLOW;
Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXSIZE;
if(Q.front==Q.rear) Q.tag=1; //队列满
}//EnCyQueue
Status DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法
{
if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE;
Q.front=(Q.front+1)%MAXSIZE;
x=Q.base[Q.front];
if(Q.front==Q.rear) Q.tag=1; //队列空
return OK;
}//DeCyQueue
分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.
第4章 串
4．2编写算法，实现串的基本操作StrReplace(S,T,V)。
StrCat(S,T)； SubString(Sub,S,pos,len)。
int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数
{
for(n=0,i=1;i<=S[0]-T[0]+1;i++)
{
for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);
if(k>T[0]) //找到了与T匹配的子串:分三种情况处理
{
if(T[0]==V[0])
for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换
S[i+l-1]=V[l];
else if(T[0]<V[0]) //新子串长度大于原子串时:先将后部右移
{
for(l=S[0];l>=i+T[0];l--)
S[l+V[0]-T[0]]=S[l];
for(l=1;l<=V[0];l++)
S[i+l-1]=V[l];
}
else //新子串长度小于原子串时:先将后部左移
{
for(l=i+V[0];l<=S[0]+V[0]-T[0];l++)
S[l]=S[l-V[0]+T[0]];
for(l=1;l<=V[0];l++)
S[i+l-1]=V[l];
}
S[0]=S[0]-T[0]+V[0];
i+=V[0];n++;
}//if
}//for
return n;
}//String_Replace
4．3假设以块链结构表示串，块的大小为1，且附设头结点。
试编写算法，实现串的下列基本操作：
StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)；
typedef struct{
char ch;
LStrNode *next;
} LStrNode,*LString; //链串结构
void StringAssign(LString &s,LString t)//把串t赋值给串s
{
s=malloc(sizeof(LStrNode));
for(q=s,p=t->next;p;p=p->next)
{
r=(LStrNode*)malloc(sizeof(LStrNode));
r->ch=p->ch;
q->next=r;q=r;
}
q->next=NULL;
}//StringAssign
void StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.
{
for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next)
{
p->ch=q->ch;pre=p;
}
while(q)
{
p=(LStrNode*)malloc(sizeof(LStrNode));
p->ch=q->ch;
pre->next=p;pre=p;
}
p->next=NULL;
}//StringCopy
char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数
{
for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next);
if(!p&&!q) return 0;
else if(!p) return -(q->ch);
else if(!q) return p->ch;
else return p->ch-q->ch;
}//StringCompare
int StringLen(LString s)//求串s的长度(元素个数)
{
for(i=0,p=s->next;p;p=p->next,i++);
return i;
}//StringLen
LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针
{
p=malloc(sizeof(LStrNode));
for(q=p,r=s->next;r;r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
}//for //复制串s
for(r=t->next;r;r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
}//for //复制串t
q->next=NULL;
return p;
}//Concat
LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串
{
p=malloc(sizeof(LStrNode));q=p;
for(r=s;start;start--,r=r->next); //找到start所对应的结点指针r
for(i=1;i<=len;i++,r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
} //复制串t
q->next=NULL;
return p;
}//Sub_String
4．10写算法，实现顺序串的基本操作StrCompare(s,t)。
char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数
{
for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);
if(i>s[0]&&i>t[0]) return 0;
else if(i>s[0]) return -t[i];
else if(i>t[0]) return s[i];
else return s[i]-t[i];
}//StrCompare
4．11写算法，实现顺序串的基本操作StrReplace(&s,t,v)。
int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数
{
for(n=0,i=0;i<=S.length-T.length;i++)
{
for(j=i,k=0;k<T.length&&S.ch[j]==T.ch[k];j++,k++);
if(k==T.length) //找到了与T匹配的子串:分三种情况处理
{
if(T.length==V.length)
for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换
S.ch[i+l-1]=V.ch[l-1];
else if(T.length<V.length) //新子串长度大于原子串时:先将后部右移
{
for(l=S.length-1;l>=i+T.length;l--)
S.ch[l+V.length-T.length]=S.ch[l];
for(l=0;l<V.length;l++)
S[i+l]=V[l];
}
else //新子串长度小于原子串时:先将后部左移
{
for(l=i+V.length;l<S.length+V.length-T.length;l++)
S.ch[l]=S.ch[l-V.length+T.length];
for(l=0;l<V.length;l++)
S[i+l]=V[l];
}
S.length+=V.length-T.length;
i+=V.length;n++;
}//if
}//for
return n;
}//HString_Replace
实习题一、已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。
利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。
（2）以顺序串作为存储结构来实现。
void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r
{
StrAssign(r,'');
for(i=1;i<=Strlen(s);i++)
{
StrAssign(c,SubString(s,i,1));
for(j=1;j<i&&StrCompare(c,SubString(s,j,1));j++); //判断s的当前字符c是否第一次出现
if(i==j)
{
for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中
if(k>Strlen(t)) StrAssign(r,Concat(r,c));
}
}//for
}//String_Subtract
第5章 数组和广义表
5．3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法
{
C.mu=A.mu;C.nu=A.nu;C.tu=0;
pa=1;pb=1;pc=1;
for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法
{
while(A.data[pa].i<x) pa++;
while(B.data[pb].i<x) pb++;
while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素
{
if(A.data[pa].j==B.data[pb].j)
{
ce=A.data[pa].e+B.data[pb].e;
if(ce) //和不为0
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=ce;
pa++;pb++;pc++;
}
}//if
else if(A.data[pa].j>B.data[pb].j)
{
C.data[pc].i=x;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++;pc++;
}
else
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e
pa++;pc++;
}
}//while
while(A.data[pa]==x) //插入A中剩余的元素(第x行)
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e
pa++;pc++;
}
while(B.data[pb]==x) //插入B中剩余的元素(第x行)
{
C.data[pc].i=x;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++;pc++;
}
}//for
C.tu=pc;
}//TSMatrix_Add
实习题若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。
void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点
{
for(i=0;i<m;i++)
{
for(min=A[i][0],j=0;j<n;j++)
if(A[i][j]<min) min=A[i][j]; //求一行中的最小值
for(j=0;j<n;j++)
if(A[i][j]==min) //判断这个(些)最小值是否鞍点
{
for(flag=1,k=0;k<m;k++)
if(min<A[k][j]) flag=0;
if(flag)
printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]);
}
}//for
}//Get_Saddle
第6章 树和二叉树
6．12已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数
}//LeafCount_BiTree
6．13编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
void Del_Sub_x(Bitree T,int x)//删除所有以元素x为根的子树
{
if(T->data==x) Del_Sub(T); //删除该子树
else
{
if(T->lchild) Del_Sub_x(T->lchild,x);
if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找
}//else
}//Del_Sub_x
void Del_Sub(Bitree T)//删除子树T
{
if(T->lchild) Del_Sub(T->lchild);
if(T->rchild) Del_Sub(T->rchild);
free(T);
}//Del_Sub
6．14分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
BTNode *PreOrder_Next(BTNode *p)//在先序后继线索二叉树中查找结点p的先序后继,并返回指针
{
if(p->lchild) return p->lchild;
else return p->rchild;
}//PreOrder_Next
分析:总觉得不会这么简单.是不是哪儿理解错了?
Bitree PostOrder_Next(Bitree p)//在后序后继线索二叉树中查找结点p的后序后继,并返回指针
{
if(p->rtag) return p->rchild; //p有后继线索
else if(!p->parent) return NULL; //p是根结点
else if(p==p->parent->rchild) return p->parent; //p是右孩子
else if(p==p->parent->lchild&&p->parent->tag)
return p->parent; //p是左孩子且双亲没有右孩子
else //p是左孩子且双亲有右孩子
{
q=p->parent->rchild;
while(!q->ltag||!q->rtag)
{
if(!q->ltag) q=q->lchild;
else q=q->rchild;
} //从p的双亲的右孩子向下走到底
return q;
}//else
}//PostOrder_Next
6．16编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
int LeafCount_CSTree(CSTree T)//求孩子兄弟链表表示的树T的叶子数目
{
if(!T->firstchild) return 1; //叶子结点
else
{
count=0;
for(child=T->firstchild;child;child=child->nextsib)
count+=LeafCount_CSTree(child);
return count; //各子树的叶子数之和
}
}//LeafCount_CSTree
6．17对以孩子-兄弟链表表示的树编写计算树的深度的算法。
int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T的深度
{
if(!T) return 0; //空树
else
{
for(maxd=0,p=T->firstchild;p;p=p->nextsib)
if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度
return maxd+1;
}
}//GetDepth_CSTree
6．18已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; //有mark域的结点指针类型
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈
{
PMType a;
InitStack(S); //S的元素为PMType类型
Push (S,{T,0}); //根结点入栈
while(!StackEmpty(S))
{
Pop(S,a);
switch(a.mark)
{
case 0:
Push(S,{a.ptr,1}); //修改mark域
if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树
break;
case 1:
Push(S,{a.ptr,2}); //修改mark域
if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树
break;
case 2:
visit(a.ptr); //访问结点,返回
}
}//while
}//PostOrder_Stack
分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作.
6．21已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
InitStack(S);
Push(S,T); //根指针进栈
while(!StackEmpty(S))
{
while(Gettop(S,p)&&p)
{
visit(p->data);
push(S,p->lchild);
} //向左走到尽头
pop(S,p);
if(!StackEmpty(S))
{
pop(S,p);
push(S,p->rchild); //向右一步
}
}//while
}//PreOrder_Nonrecursive
6．24二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。
void Bitree_Revolute(Bitree T)//交换所有结点的左右子树
{
T->lchild<->T->rchild; //交换左右子树
if(T->lchild) Bitree_Revolute(T->lchild);
if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树
}//Bitree_Revolute
第7章 图
7．5编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表
{
InitALGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //顶点数不能为负
G.vexnum=v;
scanf("%d",&a);
if(a<0) return ERROR; //边数不能为负
G.arcnum=a;
for(m=0;m<v;m++)
G.vertices[m].data=getchar(); //输入各顶点的符号
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);
q->nextarc=p;
}
p->adjvex=j;p->nextarc=NULL;
}//while
return OK;
}//Build_AdjList
7．6试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v)，InsertArc(G,v,w),DeleteVertex(G,v)和DeleteArc(G,v,w)。
//本题中的图G均为有向无权图,其余情况容易由此写出
Status Insert_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上插入顶点v
{
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;
G.vexs[++G.vexnum]=v;
return OK;
}//Insert_Vex
Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(i==j) return ERROR;
if(!G.arcs[i][j].adj)
{
G.arcs[i][j].adj=1;
G.arcnum++;
}
return OK;
}//Insert_Arc
Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v
{
n=G.vexnum;
if((m=LocateVex(G,v))<0) return ERROR;
G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点
for(i=0;i<n;i++)
{
G.arcs[i][m]=G.arcs[i][n];
G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换
}
G.arcs[m][m].adj=0;
G.vexnum--;
return OK;
}//Delete_Vex
分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加,
Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.arcs[i][j].adj)
{
G.arcs[i][j].adj=0;
G.arcnum--;
}
return OK;
}//Delete_Arc
7．7试用邻接表存储结构重做题7.6。
//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出,
Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;p->nextarc=NULL;
if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc)
if(q->adjvex==j) return ERROR; //边已经存在
q->nextarc=p;
}
G.arcnum++;
return OK;
}//Insert_Arc
7．8试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
int visited[MAXSIZE]; //指示顶点是否在当前路径上
int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if(i==j) return 1; //i就是j
else
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
7．9同上题要求。试基于图的广度优先搜索策略写一算法。
int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
int visited[MAXSIZE];
InitQueue(Q);
EnQueue(Q,i);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
visited[u]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(k==j) return 1;
if(!visited[k]) EnQueue(Q,k);
}//for
}//while
return 0;
}//exist_path_BFS
7．10试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。
void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G
{
int visited[MAXSIZE];
InitStack(S);
Push(S,GetVex(S,1)); //将第一个顶点入栈
visit(1);
visited=1;
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
j=FirstAdjVex(G,i);
if(j&&!visited[j])
{
visit(j);
visited[j]=1;
Push(S,j); //向左走到尽头
}
}//while
if(!StackEmpty(S))
{
Pop(S,j);
Gettop(S,i);
k=NextAdjVex(G,i,j); //向右走一步
if(k&&!visited[k])
{
visit(k);
visited[k]=1;
Push(S,k);
}
}//if
}//while
}//Straverse_Nonrecursive
分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
7．11采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
{
if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求
else if(k>0)
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一
}//for
visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中
}//else
return 0; //没找到
}//exist_path_len
7．13已知一棵以二叉链表作存储结构的二叉树，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。
void LayerOrder(Bitree T)//层序遍历二叉树
{
InitQueue(Q); //建立工作队列
EnQueue(Q,T);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
visit(p);
if(p->lchild) EnQueue(Q,p->lchild);
if(p->rchild) EnQueue(Q,p->rchild);
}
}//LayerOrder
第8章 查找
8．8试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。
int last=0,flag=1;
int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0
{
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->data<last) flag=0; //与其中序前驱相比较
last=T->data;
if(T->rchild&&flag) Is_BSTree(T->rchild);
return flag;
}//Is_BSTree
8．14写一时间复杂度为O(log2n+m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。
void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间
{
if(T->rchild) Delete_NLT(T->rchild,x);
if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
q=T;
T=T->lchild;
free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根
if(T) Delete_NLT(T,x); //继续在左子树中执行算法
}//Delete_NLT
8．15在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(log n)的算法，确定数中第k个结点的位置。
typedef struct {
int data;
int bf;
int lsize; //lsize域表示该结点的左子树的结点总数加1
BlcNode *lchild,*rchild;
} BlcNode,*BlcTree; //含lsize域的平衡二叉排序树类型
BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针
{
if(!T) return NULL; //k小于1或大于树结点总数
if(T->lsize==k) return T; //就是这个结点
else if(T->lsize>k)
return Locate_BlcTree(T->lchild,k); //在左子树中寻找
else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k的值
}//Locate_BlcTree
第9章 内部排序
9．6编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。
void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法
{
low=0;high=n-1; //冒泡的上下界
change=1;
while(low<high&&change)
{
change=0;
for(i=low;i<high;i++) //从上向下起泡
if(a[i]>a[i+1])
{
a[i]<->a[i+1];
change=1;
}
high--; //修改上界
for(i=high;i>low;i--) //从下向上起泡
if(a[i]<a[i-1])
{
a[i]<->a[i-1];
change=1;
}
low++; //修改下界
}//while
}//Bubble_Sort2
9．7编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
采取顺序存储结构，至多使用一个记录的辅助存储空间；
算法的时间复杂度O(n)；
讨论算法中记录的最大移动次数。
void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前
{
low=0;high=n-1;
while(low<high)
{
while(low<high&&a[high]>=0) high--; //以0作为虚拟的枢轴记录
a[low]<->a[high];
while(low<high&&a[low]<0) low++;
a[low]<->a[high];
}
}//Divide
9．8试以单链表为存储结构实现简单选择排序的算法
void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法
{
for(p=L;p->next->next;p=p->next)
{
q=p->next;x=q->data;
for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点
if(r->next->data<x)
{
x=r->next->data;
s=r;
}
if(s!=q) //找到了值比q->data更小的最小结点s->next
{
p->next=s->next;s->next=q;
t=q->next;q->next=p->next->next;
p->next->next=t;
} //交换q和s->next两个结点
}//for
}//LinkedList_Select_Sort
9．9假设含n个记录的序列中，其所有关键字为值介于v和w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。
void Enum_Sort(int a[ ],int n)//对关键字只能取v到w之间任意整数的序列进行排序
{
int number[w+1],pos[w+1];
for(i=0;i<n;i++) number[a[i]]++; //计数
for(pos[0]=0,i=1;i<n;i++)
pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置
for(i=0;i<n;i++) //构造有序数组c
c[pos[a[i]]++]=a[i];
for(i=0;i<n;i++)
a[i]=c[i];
}//Enum_Sort
分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用,
9．10已知两个有序序列(a1,a2,...,am)和(am+1,am+2,...,an),并且其中一个序列的记录个数少于s,且s=?√n?,试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。
void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列
{
start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置
for(i=0;i<l1;i++) //插入第i个元素
{
for(j=start2;j<l1+l2&&a[j]<a[start1+i];j++); //寻找插入位置
k=j-start2; //k为要向右循环移动的位数
RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位
start1+=k+1;
start2=j; //修改两序列尚未归并部分的起始位置
}
}//SL_Merge
void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18
{
len=end-start+1;
for(i=1;i<=k;i++)
if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p
for(i=0;i<p;i++) //对p个循环链分别进行右移
{
j=start+i;l=start+(i+k)%len;temp=a[j];
while(l!=start+i)
{
a[j]=temp;
temp=a[l];
a[l]=a[j];
j=l;l=start+(j-start+k)%len; //依次向右移
}
a[start+i]=temp;
}//for
}//RSh
9．12设计一个用链表表示的直接选择排序算法。
void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法
{
for(p=L;p->next->next;p=p->next)
{
q=p->next;x=q->data;
for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点
if(r->next->data<x)
{
x=r->next->data;
s=r;
}
if(s!=q) //找到了值比q->data更小的最小结点s->next
{
p->next=s->next;s->next=q;
t=q->next;q->next=p->next->next;
p->next->next=t;
} //交换q和s->next两个结点
}//for
}//LinkedList_Select_Sort
9．16已知（k1,k2,…，kn）是堆，写一个算法将（k1,k2,…，kn，kn+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。
void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法
{
for(i=2;i<n;i++)
{ //此时从H.r[1]到H.r[i-1]已经是大顶堆
j=i;
while(j!=1) //把H.r[i]插入
{
k=j/2;
if(H.r[j].key>H.r[k].key)
H.r[j]<->H.r[k];
j=k;
}
}//for
}//Build_Heap
1．4 试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：
通过参数表中的参数显式传递。
通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。
void polyvalue()
{
int n,p,i,x,xp,sum;
float a[];
float *p=a;
printf("Input number of terms:");
scanf("%d",&n);
printf("Input the %d coefficients from a0 to a%d:\n",n,n);
for(i=0;i<=n;i++) scanf("%f",p++);
printf("Input value of x:");
scanf("%f",&x);
p=a;xp=1;sum=0; //xp用于存放x的i次方
for(i=0;i<=n;i++)
{
sum+=xp*(*p++);
xp*=x;
}
printf("Value is:%f",sum);
}//polyvalue
第二章 线性表
2．4设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。
Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中
{
if(va.length+1>va.listsize) return ERROR;
va.length++;
for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
return OK;
}//Insert_SqList
2．6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。
Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素
{
p=L;
while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素
if(p->next)//如果还有比mink更大的元素
{
q=p->next;
while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素
p->next=q;
}
}//Delete_Between
2．7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。
以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。
（2）以单链表作存储结构。
void reverse(SqList &A)//顺序表的就地逆置
{
for(i=1,j=A.length;i<j;i++,j--)
A.elem[i]<->A.elem[j];
}//reverse
2．8假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C。
while(pa||pb)
{
if(pa->data<pb->data||!pb)
{
pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
}
pre=pc;
}
C=A;A->next=pc; //构造新表头
}//reverse_merge
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.
2．9假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱
{
p=s;
while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p
p->next=s;
return OK;
}//Delete_Pre
2．10已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.
{
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));p=A;
B=(CiList*)malloc(sizeof(CiLNode));q=B;
C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点
while(s)
{
if(isalphabet(s->data))
{
p->next=s;p=s;
}
else if(isdigit(s->data))
{
q->next=s;q=s;
}
else
{
r->next=s;r=s;
}
}//while
p->next=A;q->next=B;r->next=C; //完成循环链表
}//LinkList_Divide
2．11设线性表A=(a1,a2,…,am)，B=(b1,b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a1,b1,…,am,bm,bm+1,…,bn) 当m≤n时；
或者 C= (a1,b1,…,an,bn,an+1,…,am) 当m>n时。
线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
{
p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q; //将B的元素插入
if(s)
{
t=q->next;q->next=s; //如A非空,将A的元素插入
}
p=s;q=t;
}//while
}//merge1
2．12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。
void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B
{
p=L->next;
A=(PolyNode*)malloc(sizeof(PolyNode));
B=(PolyNode*)malloc(sizeof(PolyNode));
pa=A;pb=B;
while(p!=L)
{
if(p->data.exp!=2*(p->data.exp/2))
{
pa->next=p;pa=p;
}
else
{
pb->next=p;pb=p;
}
p=p->next;
}//while
pa->next=A;pb->next=B;
}//Divide_LinkedPoly
2．14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。
float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值
{
PolyTerm *q;
xp=1;q=P.data;
sum=0;ex=0;
while(q->coef)
{
while(ex<q->exp) xp*=x0;
sum+=q->coef*xp;
q++;
}
return sum;
}//GetValue_SqPoly
第3章 限定性线性表——栈和队列
3．5试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
InitStack(s);
while((e=getchar())!='&')
push(s,e);
while((e=getchar())!='@')
{
if(StackEmpty(s)) return 0;
pop(s,c);
if(e!=c) return 0;
}
if(!StackEmpty(s)) return 0;
return 1;
}//IsReverse
3．6假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new
{
p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号
InitStack(s); //s为运算符栈
while(*p)
{
if(*p是字母)) *q++=*p; //直接输出
else
{
c=gettop(s);
if(*p优先级比c高) push(s,*p);
else
{
while(gettop(s)优先级不比*p低)
{
pop(s,c);*(q++)=c;
}//while
push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则
}//else
}//else
p++;
}//while
}//NiBoLan //参见编译原理教材
3．7假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q
{
Q=(CiLNode*)malloc(sizeof(CiLNode));
Q->next=Q;
}//InitCiQueue
void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素
{
p=(CiLNode*)malloc(sizeof(CiLNode));
p->data=x;
p->next=Q->next; //直接把p加在Q的后面
Q->next=p;
Q=p;//修改尾指针
}
Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x
{
if(Q==Q->next) return INFEASIBLE; //队列已空
p=Q->next->next;
x=p->data;
Q->next->next=p->next;
free(p);
return OK;
}//DeCiQueue
3．8要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法
{
if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0表示"空",1表示"满"
return OVERFLOW;
Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXSIZE;
if(Q.front==Q.rear) Q.tag=1; //队列满
}//EnCyQueue
Status DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法
{
if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE;
Q.front=(Q.front+1)%MAXSIZE;
x=Q.base[Q.front];
if(Q.front==Q.rear) Q.tag=1; //队列空
return OK;
}//DeCyQueue
分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.
第4章 串
4．2编写算法，实现串的基本操作StrReplace(S,T,V)。
StrCat(S,T)； SubString(Sub,S,pos,len)。
int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数
{
for(n=0,i=1;i<=S[0]-T[0]+1;i++)
{
for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);
if(k>T[0]) //找到了与T匹配的子串:分三种情况处理
{
if(T[0]==V[0])
for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换
S[i+l-1]=V[l];
else if(T[0]<V[0]) //新子串长度大于原子串时:先将后部右移
{
for(l=S[0];l>=i+T[0];l--)
S[l+V[0]-T[0]]=S[l];
for(l=1;l<=V[0];l++)
S[i+l-1]=V[l];
}
else //新子串长度小于原子串时:先将后部左移
{
for(l=i+V[0];l<=S[0]+V[0]-T[0];l++)
S[l]=S[l-V[0]+T[0]];
for(l=1;l<=V[0];l++)
S[i+l-1]=V[l];
}
S[0]=S[0]-T[0]+V[0];
i+=V[0];n++;
}//if
}//for
return n;
}//String_Replace
4．3假设以块链结构表示串，块的大小为1，且附设头结点。
试编写算法，实现串的下列基本操作：
StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)；
typedef struct{
char ch;
LStrNode *next;
} LStrNode,*LString; //链串结构
void StringAssign(LString &s,LString t)//把串t赋值给串s
{
s=malloc(sizeof(LStrNode));
for(q=s,p=t->next;p;p=p->next)
{
r=(LStrNode*)malloc(sizeof(LStrNode));
r->ch=p->ch;
q->next=r;q=r;
}
q->next=NULL;
}//StringAssign
void StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.
{
for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next)
{
p->ch=q->ch;pre=p;
}
while(q)
{
p=(LStrNode*)malloc(sizeof(LStrNode));
p->ch=q->ch;
pre->next=p;pre=p;
}
p->next=NULL;
}//StringCopy
char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数
{
for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next);
if(!p&&!q) return 0;
else if(!p) return -(q->ch);
else if(!q) return p->ch;
else return p->ch-q->ch;
}//StringCompare
int StringLen(LString s)//求串s的长度(元素个数)
{
for(i=0,p=s->next;p;p=p->next,i++);
return i;
}//StringLen
LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针
{
p=malloc(sizeof(LStrNode));
for(q=p,r=s->next;r;r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
}//for //复制串s
for(r=t->next;r;r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
}//for //复制串t
q->next=NULL;
return p;
}//Concat
LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串
{
p=malloc(sizeof(LStrNode));q=p;
for(r=s;start;start--,r=r->next); //找到start所对应的结点指针r
for(i=1;i<=len;i++,r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
} //复制串t
q->next=NULL;
return p;
}//Sub_String
4．10写算法，实现顺序串的基本操作StrCompare(s,t)。
char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数
{
for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);
if(i>s[0]&&i>t[0]) return 0;
else if(i>s[0]) return -t[i];
else if(i>t[0]) return s[i];
else return s[i]-t[i];
}//StrCompare
4．11写算法，实现顺序串的基本操作StrReplace(&s,t,v)。
int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数
{
for(n=0,i=0;i<=S.length-T.length;i++)
{
for(j=i,k=0;k<T.length&&S.ch[j]==T.ch[k];j++,k++);
if(k==T.length) //找到了与T匹配的子串:分三种情况处理
{
if(T.length==V.length)
for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换
S.ch[i+l-1]=V.ch[l-1];
else if(T.length<V.length) //新子串长度大于原子串时:先将后部右移
{
for(l=S.length-1;l>=i+T.length;l--)
S.ch[l+V.length-T.length]=S.ch[l];
for(l=0;l<V.length;l++)
S[i+l]=V[l];
}
else //新子串长度小于原子串时:先将后部左移
{
for(l=i+V.length;l<S.length+V.length-T.length;l++)
S.ch[l]=S.ch[l-V.length+T.length];
for(l=0;l<V.length;l++)
S[i+l]=V[l];
}
S.length+=V.length-T.length;
i+=V.length;n++;
}//if
}//for
return n;
}//HString_Replace
实习题一、已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。
利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。
（2）以顺序串作为存储结构来实现。
void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r
{
StrAssign(r,'');
for(i=1;i<=Strlen(s);i++)
{
StrAssign(c,SubString(s,i,1));
for(j=1;j<i&&StrCompare(c,SubString(s,j,1));j++); //判断s的当前字符c是否第一次出现
if(i==j)
{
for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中
if(k>Strlen(t)) StrAssign(r,Concat(r,c));
}
}//for
}//String_Subtract
第5章 数组和广义表
5．3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法
{
C.mu=A.mu;C.nu=A.nu;C.tu=0;
pa=1;pb=1;pc=1;
for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法
{
while(A.data[pa].i<x) pa++;
while(B.data[pb].i<x) pb++;
while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素
{
if(A.data[pa].j==B.data[pb].j)
{
ce=A.data[pa].e+B.data[pb].e;
if(ce) //和不为0
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=ce;
pa++;pb++;pc++;
}
}//if
else if(A.data[pa].j>B.data[pb].j)
{
C.data[pc].i=x;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++;pc++;
}
else
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e
pa++;pc++;
}
}//while
while(A.data[pa]==x) //插入A中剩余的元素(第x行)
{
C.data[pc].i=x;
C.data[pc].j=A.data[pa].j;
C.data[pc].e=A.data[pa].e
pa++;pc++;
}
while(B.data[pb]==x) //插入B中剩余的元素(第x行)
{
C.data[pc].i=x;
C.data[pc].j=B.data[pb].j;
C.data[pc].e=B.data[pb].e;
pb++;pc++;
}
}//for
C.tu=pc;
}//TSMatrix_Add
实习题若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。
void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点
{
for(i=0;i<m;i++)
{
for(min=A[i][0],j=0;j<n;j++)
if(A[i][j]<min) min=A[i][j]; //求一行中的最小值
for(j=0;j<n;j++)
if(A[i][j]==min) //判断这个(些)最小值是否鞍点
{
for(flag=1,k=0;k<m;k++)
if(min<A[k][j]) flag=0;
if(flag)
printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]);
}
}//for
}//Get_Saddle
第6章 树和二叉树
6．12已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数
}//LeafCount_BiTree
6．13编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
void Del_Sub_x(Bitree T,int x)//删除所有以元素x为根的子树
{
if(T->data==x) Del_Sub(T); //删除该子树
else
{
if(T->lchild) Del_Sub_x(T->lchild,x);
if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找
}//else
}//Del_Sub_x
void Del_Sub(Bitree T)//删除子树T
{
if(T->lchild) Del_Sub(T->lchild);
if(T->rchild) Del_Sub(T->rchild);
free(T);
}//Del_Sub
6．14分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
BTNode *PreOrder_Next(BTNode *p)//在先序后继线索二叉树中查找结点p的先序后继,并返回指针
{
if(p->lchild) return p->lchild;
else return p->rchild;
}//PreOrder_Next
分析:总觉得不会这么简单.是不是哪儿理解错了?
Bitree PostOrder_Next(Bitree p)//在后序后继线索二叉树中查找结点p的后序后继,并返回指针
{
if(p->rtag) return p->rchild; //p有后继线索
else if(!p->parent) return NULL; //p是根结点
else if(p==p->parent->rchild) return p->parent; //p是右孩子
else if(p==p->parent->lchild&&p->parent->tag)
return p->parent; //p是左孩子且双亲没有右孩子
else //p是左孩子且双亲有右孩子
{
q=p->parent->rchild;
while(!q->ltag||!q->rtag)
{
if(!q->ltag) q=q->lchild;
else q=q->rchild;
} //从p的双亲的右孩子向下走到底
return q;
}//else
}//PostOrder_Next
6．16编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
int LeafCount_CSTree(CSTree T)//求孩子兄弟链表表示的树T的叶子数目
{
if(!T->firstchild) return 1; //叶子结点
else
{
count=0;
for(child=T->firstchild;child;child=child->nextsib)
count+=LeafCount_CSTree(child);
return count; //各子树的叶子数之和
}
}//LeafCount_CSTree
6．17对以孩子-兄弟链表表示的树编写计算树的深度的算法。
int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T的深度
{
if(!T) return 0; //空树
else
{
for(maxd=0,p=T->firstchild;p;p=p->nextsib)
if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度
return maxd+1;
}
}//GetDepth_CSTree
6．18已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; //有mark域的结点指针类型
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈
{
PMType a;
InitStack(S); //S的元素为PMType类型
Push (S,{T,0}); //根结点入栈
while(!StackEmpty(S))
{
Pop(S,a);
switch(a.mark)
{
case 0:
Push(S,{a.ptr,1}); //修改mark域
if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树
break;
case 1:
Push(S,{a.ptr,2}); //修改mark域
if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树
break;
case 2:
visit(a.ptr); //访问结点,返回
}
}//while
}//PostOrder_Stack
分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作.
6．21已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
InitStack(S);
Push(S,T); //根指针进栈
while(!StackEmpty(S))
{
while(Gettop(S,p)&&p)
{
visit(p->data);
push(S,p->lchild);
} //向左走到尽头
pop(S,p);
if(!StackEmpty(S))
{
pop(S,p);
push(S,p->rchild); //向右一步
}
}//while
}//PreOrder_Nonrecursive
6．24二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。
void Bitree_Revolute(Bitree T)//交换所有结点的左右子树
{
T->lchild<->T->rchild; //交换左右子树
if(T->lchild) Bitree_Revolute(T->lchild);
if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树
}//Bitree_Revolute
第7章 图
7．5编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表
{
InitALGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //顶点数不能为负
G.vexnum=v;
scanf("%d",&a);
if(a<0) return ERROR; //边数不能为负
G.arcnum=a;
for(m=0;m<v;m++)
G.vertices[m].data=getchar(); //输入各顶点的符号
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);
q->nextarc=p;
}
p->adjvex=j;p->nextarc=NULL;
}//while
return OK;
}//Build_AdjList
7．6试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v)，InsertArc(G,v,w),DeleteVertex(G,v)和DeleteArc(G,v,w)。
//本题中的图G均为有向无权图,其余情况容易由此写出
Status Insert_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上插入顶点v
{
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;
G.vexs[++G.vexnum]=v;
return OK;
}//Insert_Vex
Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(i==j) return ERROR;
if(!G.arcs[i][j].adj)
{
G.arcs[i][j].adj=1;
G.arcnum++;
}
return OK;
}//Insert_Arc
Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v
{
n=G.vexnum;
if((m=LocateVex(G,v))<0) return ERROR;
G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点
for(i=0;i<n;i++)
{
G.arcs[i][m]=G.arcs[i][n];
G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换
}
G.arcs[m][m].adj=0;
G.vexnum--;
return OK;
}//Delete_Vex
分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加,
Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.arcs[i][j].adj)
{
G.arcs[i][j].adj=0;
G.arcnum--;
}
return OK;
}//Delete_Arc
7．7试用邻接表存储结构重做题7.6。
//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出,
Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;p->nextarc=NULL;
if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc)
if(q->adjvex==j) return ERROR; //边已经存在
q->nextarc=p;
}
G.arcnum++;
return OK;
}//Insert_Arc
7．8试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
int visited[MAXSIZE]; //指示顶点是否在当前路径上
int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if(i==j) return 1; //i就是j
else
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
7．9同上题要求。试基于图的广度优先搜索策略写一算法。
int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
int visited[MAXSIZE];
InitQueue(Q);
EnQueue(Q,i);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
visited[u]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(k==j) return 1;
if(!visited[k]) EnQueue(Q,k);
}//for
}//while
return 0;
}//exist_path_BFS
7．10试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。
void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G
{
int visited[MAXSIZE];
InitStack(S);
Push(S,GetVex(S,1)); //将第一个顶点入栈
visit(1);
visited=1;
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
j=FirstAdjVex(G,i);
if(j&&!visited[j])
{
visit(j);
visited[j]=1;
Push(S,j); //向左走到尽头
}
}//while
if(!StackEmpty(S))
{
Pop(S,j);
Gettop(S,i);
k=NextAdjVex(G,i,j); //向右走一步
if(k&&!visited[k])
{
visit(k);
visited[k]=1;
Push(S,k);
}
}//if
}//while
}//Straverse_Nonrecursive
分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
7．11采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
{
if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求
else if(k>0)
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一
}//for
visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中
}//else
return 0; //没找到
}//exist_path_len
7．13已知一棵以二叉链表作存储结构的二叉树，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。
void LayerOrder(Bitree T)//层序遍历二叉树
{
InitQueue(Q); //建立工作队列
EnQueue(Q,T);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
visit(p);
if(p->lchild) EnQueue(Q,p->lchild);
if(p->rchild) EnQueue(Q,p->rchild);
}
}//LayerOrder
第8章 查找
8．8试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。
int last=0,flag=1;
int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0
{
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->data<last) flag=0; //与其中序前驱相比较
last=T->data;
if(T->rchild&&flag) Is_BSTree(T->rchild);
return flag;
}//Is_BSTree
8．14写一时间复杂度为O(log2n+m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。
void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间
{
if(T->rchild) Delete_NLT(T->rchild,x);
if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
q=T;
T=T->lchild;
free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根
if(T) Delete_NLT(T,x); //继续在左子树中执行算法
}//Delete_NLT
8．15在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(log n)的算法，确定数中第k个结点的位置。
typedef struct {
int data;
int bf;
int lsize; //lsize域表示该结点的左子树的结点总数加1
BlcNode *lchild,*rchild;
} BlcNode,*BlcTree; //含lsize域的平衡二叉排序树类型
BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针
{
if(!T) return NULL; //k小于1或大于树结点总数
if(T->lsize==k) return T; //就是这个结点
else if(T->lsize>k)
return Locate_BlcTree(T->lchild,k); //在左子树中寻找
else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k的值
}//Locate_BlcTree
第9章 内部排序
9．6编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。
void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法
{
low=0;high=n-1; //冒泡的上下界
change=1;
while(low<high&&change)
{
change=0;
for(i=low;i<high;i++) //从上向下起泡
if(a[i]>a[i+1])
{
a[i]<->a[i+1];
change=1;
}
high--; //修改上界
for(i=high;i>low;i--) //从下向上起泡
if(a[i]<a[i-1])
{
a[i]<->a[i-1];
change=1;
}
low++; //修改下界
}//while
}//Bubble_Sort2
9．7编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
采取顺序存储结构，至多使用一个记录的辅助存储空间；
算法的时间复杂度O(n)；
讨论算法中记录的最大移动次数。
void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前
{
low=0;high=n-1;
while(low<high)
{
while(low<high&&a[high]>=0) high--; //以0作为虚拟的枢轴记录
a[low]<->a[high];
while(low<high&&a[low]<0) low++;
a[low]<->a[high];
}
}//Divide
9．8试以单链表为存储结构实现简单选择排序的算法
void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法
{
for(p=L;p->next->next;p=p->next)
{
q=p->next;x=q->data;
for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点
if(r->next->data<x)
{
x=r->next->data;
s=r;
}
if(s!=q) //找到了值比q->data更小的最小结点s->next
{
p->next=s->next;s->next=q;
t=q->next;q->next=p->next->next;
p->next->next=t;
} //交换q和s->next两个结点
}//for
}//LinkedList_Select_Sort
9．9假设含n个记录的序列中，其所有关键字为值介于v和w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。
void Enum_Sort(int a[ ],int n)//对关键字只能取v到w之间任意整数的序列进行排序
{
int number[w+1],pos[w+1];
for(i=0;i<n;i++) number[a[i]]++; //计数
for(pos[0]=0,i=1;i<n;i++)
pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置
for(i=0;i<n;i++) //构造有序数组c
c[pos[a[i]]++]=a[i];
for(i=0;i<n;i++)
a[i]=c[i];
}//Enum_Sort
分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用,
9．10已知两个有序序列(a1,a2,...,am)和(am+1,am+2,...,an),并且其中一个序列的记录个数少于s,且s=?√n?,试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。
void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列
{
start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置
for(i=0;i<l1;i++) //插入第i个元素
{
for(j=start2;j<l1+l2&&a[j]<a[start1+i];j++); //寻找插入位置
k=j-start2; //k为要向右循环移动的位数
RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位
start1+=k+1;
start2=j; //修改两序列尚未归并部分的起始位置
}
}//SL_Merge
void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18
{
len=end-start+1;
for(i=1;i<=k;i++)
if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p
for(i=0;i<p;i++) //对p个循环链分别进行右移
{
j=start+i;l=start+(i+k)%len;temp=a[j];
while(l!=start+i)
{
a[j]=temp;
temp=a[l];
a[l]=a[j];
j=l;l=start+(j-start+k)%len; //依次向右移
}
a[start+i]=temp;
}//for
}//RSh
9．12设计一个用链表表示的直接选择排序算法。
void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法
{
for(p=L;p->next->next;p=p->next)
{
q=p->next;x=q->data;
for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点
if(r->next->data<x)
{
x=r->next->data;
s=r;
}
if(s!=q) //找到了值比q->data更小的最小结点s->next
{
p->next=s->next;s->next=q;
t=q->next;q->next=p->next->next;
p->next->next=t;
} //交换q和s->next两个结点
}//for
}//LinkedList_Select_Sort
9．16已知（k1,k2,…，kn）是堆，写一个算法将（k1,k2,…，kn，kn+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。
void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法
{
for(i=2;i<n;i++)
{ //此时从H.r[1]到H.r[i-1]已经是大顶堆
j=i;
while(j!=1) //把H.r[i]插入
{
k=j/2;
if(H.r[j].key>H.r[k].key)
H.r[j]<->H.r[k];
j=k;
}
}//for
}//Build_Heap
