typedef char datatype; typedef struct node{ datatype data; struct node * next; } listnode;typedef listnode* linklist;
/*--------------------------------------------*/ /* 删除单链表中重复的结点 */
/*--------------------------------------------*/ linklist deletelist(linklist head)
{ listnode *p,*s,*q; p=head->next; while(p) {s=p; q=p->next;
while(q)
if(q->data==p->data)
{s->next=q->next;free(q); q=s->next;} else
{ s=q; /*找与P结点值相同的结点*/ q=q->next; }
p=p->next; }
return head; }
11、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找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
12、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。 13、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[];
scanf( \"%d%d\输入边数和顶点数。 for (i=1;i<=e;i++) //输入e条边：顶点，权值。
scanf(\"%d%d%d\" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。 {edge[0]=edge[i]; j=i-1;
while (edge[j].wwhile (eg>=n) //破圈，直到边数e=n-1.{if (connect(k)) //删除第k条边若仍连通。
{edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边
}//while }//算法结束。
connect()是测试图是否连通的函数，可用图的遍历实现，
14、设计一个尽可能的高效算法输出单链表的倒数第K个元素。
15、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。 #include typedef char datatype; typedef struct node{ datatype data; struct node * next; } listnode;typedef listnode* linklist;
/*--------------------------------------------*/ /* 删除单链表中重复的结点 */
/*--------------------------------------------*/ linklist deletelist(linklist head)
{ listnode *p,*s,*q; p=head->next; while(p) {s=p; q=p->next;
while(q)
if(q->data==p->data)
{s->next=q->next;free(q); q=s->next;} else
{ s=q; /*找与P结点值相同的结点*/ q=q->next; }
p=p->next; }
return head; }
