2023青海省数据库入门入门

1、1、编程实现单链表的就地逆置。23在数组 A1.n中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.2、二路插入排序是将待排关键字序列r1.n中关键字分二路分别按序插入到辅助向量d1.n前半部和后半部注:向量d可视为循环表，其原那么为，先将rl赋给d1，再从r2 记录开始分二路插入。编写实现二路插入排序算法。3、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保存一个。#include typ

2、edef 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的nn0个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedef int datatype;typedef struct nodedatatype data; struct nod

4、e *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=

5、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=head

6、; 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 if(x0) bt=(

8、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); /初始化队列，根结点指针入队while (!Q

9、ueueEmpty(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个顶点和足以使图连通的n-1条边

10、，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，那么将该边恢复。假设仍连通，继续向下删；直到剩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(%d%d%d ,

11、&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

13、; / 1双亲的左子树 2双亲的右子树qnode; BiTree Creat(datatype in,level,int n)/由二叉树的层次序列leveln和中序序列inn生成二叉树。 n是二叉树的结点数if (ndata=level0; p-lchild=null; p-rchild=null; /填写该结点数据for (i=0; ilchild=null; s.lvl=+R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); else if (i=n-1) /根结点无右子树，遍历序列的1n-1是左子树p-rchild=null; s.lvl=+

14、R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); else /根结点有左子树和右子树s.lvl=+R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);/左子树有关信息入队列s.lvl=+R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);/右子树有关信息入队列while (!empty(Q) /当队列不空，进行循环，构造二叉树的左右子树 s=delqueue(Q); father=s.f; for (i=s.l; idata=levels.lvl; p-lchild=n

15、ull; p-rchild=null; /填写该结点数据 if (s.lr=1) father-lchild=p; else father-rchild=p； /让双亲的子女指针指向该结点 if (i=s.l)p-lchild=null; /处理无左子女s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); else if (i=s.h) p-rchild=null; /处理无右子女 s.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); elses.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);/左子树有关信息入队列 s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); /右子树有关信息入队列 /结束while (!