2、4、 void LinkList_reverse(Linklist &L) //链表的就地逆置;为简化算法,假设表长大于2 {
p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) {
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头 }
q->next=p;s->next=q;L->next=s;}//LinkList_reverse
3、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#define true 1#define false 0typedef struct node
{datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag）// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。
{ if（t!=null && flag）
{ Judgebst（t->llink,flag）；// 中序遍历左子树
if（pre==null）pre=t；// 中序遍历的第一个结点不必判断 else if（pre->data else{flag=flase；} //不是完全二叉树 Judgebst （t->rlink,flag）；// 中序遍历右子树}//JudgeBST算法结束 4、编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。 5、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。 int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数; AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v) {visited [v]=1; num++; //访问的顶点数＋1 if (num==n) {printf(“%d是有向图的根。\\n”,v);num=0;}//if p=g[v].firstarc; while (p) {if (visied[p->adjvex]==0) dfs (p->adjvex);p=p->next;} //while visited[v]=0; num--; //恢复顶点v}//dfs void JudgeRoot() //判断有向图是否有根，有根则输出之。{static int i ; for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。{num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot 算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。 6、假设K1，…，Kn是n个关键词，试解答： 试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn时，用算法建立一棵以LLINK / RLINK 链接表示的 二叉查找树。 7、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。 int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数; AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v) {visited [v]=1; num++; //访问的顶点数＋1 if (num==n) {printf(“%d是有向图的根。\\n”,v);num=0;}//if p=g[v].firstarc; while (p) {if (visied[p->adjvex]==0) dfs (p->adjvex);p=p->next;} //while visited[v]=0; num--; //恢复顶点v}//dfs void JudgeRoot() //判断有向图是否有根，有根则输出之。{static int i ; for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。{num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot 算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。 8、编程实现单链表的就地逆置。23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个. 9、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。 48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡） 10、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。void union(int A[],B[],C[],m,n) //整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。 {i=0; j=n-1; k=0;// i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始 while(i if(a[i] 4、要求二叉树按二叉链表形式存储。15分 （1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。 BiTree Creat() //建立二叉树的二叉链表形式的存储结构{ElemType x；BiTree bt; scanf(“%d”,&x); //本题假定结点数据域为整型if(x==0) bt=null;else if(x>0) {bt=(BiNode *)malloc(sizeof(BiNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat();} else error(“输入错误”)；return(bt);}//结束 BiTree int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 {int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1); QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队while (!QueueEmpty(Q)) {p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队 else {if (p->lchild) return 0; //前边已有结点为空，本结点不空 else tag=1; //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队else if (p->rchild) return 0; else tag=1;} //while return 1; } //JudgeComplete 11、编程实现单链表的就地逆置。23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个. 12、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。typedef struct {BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问}stack; stack s[],s1[];//栈，容量够大 BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0) {while(bt!=null && bt!=p && bt!=q) //结点入栈{s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。 for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配{pp=s[i].t; for (j=top1;j>0;j--) if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);}｝ while(top!=0 && s[top].tag==1) top--; //退栈 if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历 }//结束while(bt!=null ||top>0)return(null);//ｑ、p无公共祖先｝//结束Ancestor 13、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。 14、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。 void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2) //将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。{if(h1>=l1) {post[h2]=pre[l1]; //根结点 half=(h1-l1)/2; //左或右子树的结点数 PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列} }//PreToPost 32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。 LinkedList head,pre=null; //全局变量LinkedList InOrder(BiTree bt) //中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树 if(bt->lchild==null && bt->rchild==null) //叶子结点 if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历左子树 pre->rchild=null; //设置链表尾 } return(head); } //InOrder 时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n) 15、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。 void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag[],longest=0; while(p || top>0) { while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历 {if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top;top--;} //保留当前最长路径到l栈，记住最高栈顶指针，退栈 } else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0)}//结束LongestPath 因篇幅问题不能全部显示，请点此查看更多更全内容