《2010青海省数据库入门入门》由会员分享，可在线阅读，更多相关《2010青海省数据库入门入门（6页珍藏版）》请在金锄头文库上搜索。
1、1、编程实现单链表的就地逆置。23在数组 A1.n中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.2、二路插入排序是将待排关键字序列r1.n中关键字分二路分别按序插入到辅助向量d1.n前半部和后半部（注:向量d可视为循环表），其原则为，先将rl赋给d1，再从r2 记录开始分二路插入。编写实现二路插入排序算法。3、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。#include ty
2、pedef 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; /*找
3、与P结点值相同的结点*/ q=q-next; p=p-next; return head; 4、编写一个过程，对一个nn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。5、约瑟夫环问题（Josephus问题）是指编号为1、2、，n的n（n0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedef int datatype;typedef struct nodedatatype data; struc
4、t 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个结点*/
5、 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 (n1) printf(ndata=n; r
6、=head; for (i=n-1;i0;i-) /*建立剩余n-1个结点*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ 6、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。void union(int A,B,C,m,n)/整型数组A和B各有m和n个元素，前者递增有序，后者递减有
7、序，本算法将A和B归并为递增有序的数组C。i=0; j=n-1; k=0;/ i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i=0) if(aibj) ck+=ai+ else ck+=bj-;while(i=0) ck+=bj-;算法结束4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTree Creat() /建立二叉树的二叉链表形式的存储结构ElemType x；BiTree bt;scanf(“%d”,&x); /本题假定结点数据域为整型if(x=0) bt=null;else i
8、f(x0) bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“输入错误”)；return(bt);/结束 BiTreeint JudgeComplete(BiTree bt) /判断二叉树是否是完全二叉树,如是，返回1，否则，返回0int tag=0; BiTree p=bt, Q; / Q是队列，元素是二叉树结点指针，容量足够大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针入
9、队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; /whilereturn 1; /JudgeComplete7、 连通图的生成树包括图中的全部n个顶点和足
10、以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;i+) /输入e条边：顶点，权值。 scanf
11、(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按边上的权值大小，对边进行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到边数e=n-1. if (connect(k) /删除第k条边若仍连通。 edgek.w=0; eg-; /测试下一条边edgek，权值置0表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，8、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。
12、确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedef struct int lvl; /层次序列指针，总是指向当前“根结点”在层次序列中的位置int l,h; /中序序列的下上界int f; /层次序列中当前“根结点”的双亲结点的指针int lr; / 1双亲的左子树 2双亲的右子树qnode; BiTree Creat(datatype in,level,int n)/由二叉树的层次序列leve
