文档库 最新最全的文档下载
当前位置:文档库 › 2011年宁夏回族自治区数据统计基础

2011年宁夏回族自治区数据统计基础

1、设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。
2、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树,下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列,生成一棵用二叉链表表示的二叉树并打印出后序遍历序列,请写出程序所缺的语句。
#define MAX 100
typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE;
char pred[MAX],inod[MAX];
main(int argc,int **argv)
{ TNODE *root;
if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]);
root=restore(pred,inod,strlen(pred));
postorder(root);
}
TNODE *restore(char *ppos,char *ipos,int n)
{ TNODE *ptr; char *rpos; int k;
if(n<=0) return NULL;
ptr->info=(1)_______;
for((2)_______ ; rposk=(3)_______;
ptr->llink=restore(ppos+1, (4)_______,k );
ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);
return ptr;
}
postorder(TNODE*ptr)
{ if(ptr=NULL) return;
postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info);
}

3、本题应使用深度优先遍历,从主调函数进入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。



4、有一个带头结点的单链表,每个结点包括两个域,一个是整型域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;
}

5、有一个带头结点的单链表,每个结点包括两个域,一个是整型域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;
}

6、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
7、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。
int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数
{if(bt==null || k<1) return(0);
BiTree p=bt,Q[]; //Q是队列,元素是二叉树结点指针,容量足够大
int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数
int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针,level 是二叉树的层数
while(front<=rear)
{p=Q[++front];
if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点
if(p->lchild) Q[++rear]=p->lchild; //左子女入队
if(p->rchild) Q[++rear]=p->rchild; //右子女入队
if(front==last) {level++; //二叉树同层最右结点已处理,层数增1
last=rear; } //last移到指向下层最右一元素
if(level>k) return (leaf); //层数大于k 后退出运行
}//while }//结束LeafKLevel

8、我们用l代表最长平台的长度,用k指示最长平台在数组b中的起始位置(下标)。用j记住局部平台的起始位置,用i指示扫描b数组

的下标,i从0开始,依次和后续元素比较,若局部平台长度(i-j)大于l时,则修改最长平台的长度k(l=i-j)和其在b中的起始位置(k=j),直到b数组结束,l即为所求。
void Platform (int b[ ], int N)
//求具有N个元素的整型数组b中最长平台的长度。
{l=1;k=0;j=0;i=0;
while(i{while(iif(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台
i++; j=i; } //新平台起点
printf(“最长平台长度%d,在b数组中起始下标为%d”,l,k);
}// Platform

9、二部图(bipartite graph) G=(V,E)是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图,使得:V1中的任何两个结点在图G中均不相邻,V2中的任何结点在图G中也均不相邻。
(1).请各举一个结点个数为5的二部图和非二部图的例子。
(2).请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图,并分析程序的时间复杂度。设G用二维数组A来表示,大小为n*n(n为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

10、约瑟夫环问题(Josephus问题)是指编号为1、2、…,n的n(n>0)个人按顺时针方向围坐成一圈,现从第s个人开始按顺时针方向报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列,…,如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法,模拟此过程。
#include
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
{linklist k1,pre,p;
int count=1;
pre=NULL;
k1=head; /*k1为报数的起点*/
while (count!=s) /*找初始报数起点*/
{pre=k1;
k1=k1->next;
count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/
{ p=k1; /*从k1开始报数*/
count=1;
while (count!=m) /*连续数m个结点*/
{ pre=p;
p=p->next;
count++;
}
pre->next=p->next; /*输出该结点,并删除该结点*/
printf("%4d",p->data);
free(p);
k1=pre->next; /*新的报数起点*/
}
printf("%4d",k1->data); /*输出最后一个结点*/
free(k1);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n<1) printf("n<0");
else
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/
head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(linklist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*生成循环链表*/
jose(head,s,m); /*调用函

数*/
}
}

11、请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。 二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
12、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。
int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数
{if(bt==null || k<1) return(0);
BiTree p=bt,Q[]; //Q是队列,元素是二叉树结点指针,容量足够大
int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数
int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针,level 是二叉树的层数
while(front<=rear)
{p=Q[++front];
if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点
if(p->lchild) Q[++rear]=p->lchild; //左子女入队
if(p->rchild) Q[++rear]=p->rchild; //右子女入队
if(front==last) {level++; //二叉树同层最右结点已处理,层数增1
last=rear; } //last移到指向下层最右一元素
if(level>k) return (leaf); //层数大于k 后退出运行
}//while }//结束LeafKLevel

13、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。20分
void Hospital(AdjMatrix w,int n)
//在以邻接带权矩阵表示的n个村庄中,求医院建在何处,使离医院最远的村庄到医院的路径最短。
{for (k=1;k<=n;k++) //求任意两顶点间的最短路径
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (w[i][k]+w[k][j]m=MAXINT; //设定m为机器内最大整数。
for (i=1;i<=n;i++) //求最长路径中最短的一条。
{s=0;
for (j=1;j<=n;j++) //求从某村庄i(1<=i<=n)到其它村庄的最长路径。
if (w[i][j]>s) s=w[i][j];
if (s<=m) {m=s; k=i;}//在最长路径中,取最短的一条。m记最长路径,k记出发顶点的下标。
Printf(“医院应建在%d村庄,到医院距离为%d\n”,i,m);
}//for
}//算法结束
对以上实例模拟的过程略。各行中最大数依次是9,9,6,7,9,9。这几个最大数中最小者为6,故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。

1、对图1所示的连通网G,请用Prim算法构造其最小生成树(每选取一条边画一个图)。

14、我们用l代表最长平台的长度,用k指示最

长平台在数组b中的起始位置(下标)。用j记住局部平台的起始位置,用i指示扫描b数组的下标,i从0开始,依次和后续元素比较,若局部平台长度(i-j)大于l时,则修改最长平台的长度k(l=i-j)和其在b中的起始位置(k=j),直到b数组结束,l即为所求。
void Platform (int b[ ], int N)
//求具有N个元素的整型数组b中最长平台的长度。
{l=1;k=0;j=0;i=0;
while(i{while(iif(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台
i++; j=i; } //新平台起点
printf(“最长平台长度%d,在b数组中起始下标为%d”,l,k);
}// Platform

15、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
16、#define maxsize 栈空间容量

void InOutS(int s[maxsize])
//s是元素为整数的栈,本算法进行入栈和退栈操作。
{int top=0; //top为栈顶指针,定义top=0时为栈空。
for(i=1; i<=n; i++) //n个整数序列作处理。
{scanf(“%d”,&x); //从键盘读入整数序列。
if(x!=-1) // 读入的整数不等于-1时入栈。
if(top==maxsize-1){printf(“栈满\n”);exit(0);}
else s[++top]=x; //x入栈。
else //读入的整数等于-1时退栈。
{if(top==0){printf(“栈空\n”);exit(0);}
else printf(“出栈元素是%d\n”,s[top--]);}
}
}//算法结

17、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树,下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列,生成一棵用二叉链表表示的二叉树并打印出后序遍历序列,请写出程序所缺的语句。
#define MAX 100
typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE;
char pred[MAX],inod[MAX];
main(int argc,int **argv)
{ TNODE *root;
if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]);
root=restore(pred,inod,strlen(pred));
postorder(root);
}
TNODE *restore(char *ppos,char *ipos,int n)
{ TNODE *ptr; char *rpos; int k;
if(n<=0) return NULL;
ptr->info=(1)_______;
for((2)_______ ; rposk=(3)_______;
ptr->llink=restore(ppos+1, (4)_______,k );
ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);
return ptr;
}
postorder(TNODE*ptr)
{ if(ptr=NULL) return;
postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info);
}

18、设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右

儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量,且在调用count(t)之前都置为0.
typedef struct node
{int data; struct node *lchild,*rchild;}node;
int N2,NL,NR,N0;
void count(node *t)
{if (t->lchild!=NULL) if (1)___ N2++; else NL++;
else if (2)___ NR++; else (3)__ ;
if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;
}
26.树的先序非递归算法。
void example(b)
btree *b;
{ btree *stack[20], *p;
int top;
if (b!=null)
{ top=1; stack[top]=b;
while (top>0)
{ p=stack[top]; top--;
printf(“%d”,p->data);
if (p->rchild!=null)
{(1)___; (2)___;
}
if (p->lchild!=null)
(3)___; (4)__;
}}}}

19、设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。
20、数组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=0)
if(a[i]while(iwhile(j>=0) c[k++]=b[j--];
}算法结束
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

21、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是

“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。注:圈就是回路。
22、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n。
51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请编写出算法并简要说明算法思想。

23、本题应使用深度优先遍历,从主调函数进入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。



24、二部图(bipartite graph) G=(V,E)是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图,使得:V1中的任何两个结点在图G中均不相邻,V2中的任何结点在图G中也均不相邻。
(1).请各举一个结点个数为5的二部图和非二部图的例子。
(2).请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图,并分析程序的时间复杂度。设G用二维数组A来表示,大小为n*n(n为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

25、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指

针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找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);//q、p无公共祖先
}//结束Ancestor

26、假设K1,…,Kn是n个关键词,试解答:
试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为K1,K2,…,Kn时,用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

27、对一般二叉树,仅根据一个先序、中序、后序遍历,不能确定另一个遍历序列。但对于满二叉树,任一结点的左右子树均含有数量相等的结点,根据此性质,可将任一遍历序列转为另一遍历序列(即任一遍历序列均可确定一棵二叉树)。
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)

28、本题要求建立有序的循环链表。从头到尾扫描数组A,取出A[i](0<=iLinkedList creat(ElemType A[],int n)
//由含n个数据的数组A生成循环链表,要求链表有序并且无值重复结点
{LinkedList h;
h=(LinkedList)malloc(sizeof(LNode));//申请结点
h->next=h; //形成空循环链表
for(i=0;i{pre=h;
p=h->next;
while(p!=h && p->data{pre=p; p=p->next;} //查找A[i]的插入位置
if(p==h || p->data!=A[i]) //重复数据不再输入
{s=(LinkedList)malloc(sizeof(LNode));
s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中
}
}//for
return(h);
}算法结束

29、设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
30、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用llink-rlink法存储。

相关文档
相关文档 最新文档