太原理工大学数据结构实验报告1.设有 n 个人围坐在一个圆桌周围，现从第 s 个人开始报数，数到第 m 的人出列，然后从出列的下一个人重新开始报数，数到 m 的人又出列，如此重复，直到所有的人全部出列为止。Josephus 问题是：对于任意给定的 n，m，s，求出按出列次序得到的 n 个人员的顺序表。
# include stdio.h # include malloc.htypedefstructnode {//单链表的节点结构int date； 结构节点*下一步； }节点，*nodelink； void make (节点链路头，int n )//n创建一个包含在圆桌前面的人数) /长度为n的单链表，并填写与每个节点对应的数字) /将指向链表最后一个元素的指针与头部节点指向的位置相对应nodelink p，q； p=head； for(I=0； in； I ) q=(nodelink ) malloc ) sizeof ) node )； //申请内存p-next=q的q-date=i 1； 问-下一步=头下一步； p=p-next； }数到}voiddequeue(nodelinkhead，nodelink line，int n，int m，int s )/m的人离开队伍) /从第s个人开始报告几个int i； nodelink p，q，r； p=head-next； //循环是指p开始报告数据的人的for(I=1； is； I ) { p=p-next； q=p； 巡视//链表，将对应位置的链表保存在新的链表中，r=line； //line是新链表的开头指针do{for(I=1； im； (I )//寻找退出团队的因素) q=p； p=p-next； } q-next=p-next； //Q和p都指向退出团队的要素p-next=NULL； //将查找的元素设为新链表的最后一个元素r-next=p； //r始终位于新链表的末尾，并将新元素连接在链表后面的r=r-next； p=q-next； //P面向以下要素，开始新的出场(While ) ) p！=p-next； //在只剩下一个要素时，结束循环r-next=p的r-next-next=NULL； }voidwrite(nodelinkline，int n ) ) int n； nodelink p； p=line-next； for(I=0； in； I，p=p-next(/新链表的元素printf ) ' %d '，p-date )按顺序输出； (}int main ) ) { nodelink head，line； int m，n，s； head=(nodelink ) malloc ) sizeof (node )； line=(nodelink ) malloc ) sizeof (node )； //保存显示顺序printf (输入总人数n: )的scanf('%d '，n )； make(head，n )； printf (开始输入的人s: )； 扫描(' % d '，s )； printf ()要计数的数字m: )； scanf('%d '，m )； dequeue(head，line，n，m，s )； 写入(line，n )； printf((n ) n ) )； } 2.编写递归算法，在二叉树中求位于先序序列中第 K 个位置的结点。
# include stdio.h # include stdlib.h # include stdbool.htypedefstructbitnode { chardata； struct BiTNode *Lchild，*Rchild； }BiTNode，*BiTree；//第k个元素boolfind_k(bitreeB1，int *i，int k ) ) if ) B1==null )返回假； (I )； if(k==*I ) printf )、B1-data )； 返回真； }
if(Find_K(B1->Lchild,i,k) || Find_K(B1->Rchild,i,k)) return true; return false;}// create Binary TreeBiTree CreateBiTree(BiTree T){ char ch; scanf("%c", &ch); if(ch == '.') T = NULL; else{ if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) return false; T->data = ch; T->Lchild = CreateBiTree(T->Lchild); T->Rchild = CreateBiTree(T->Rchild); } return T;}int main(){ BiTree T1 = NULL,B1; int k; scanf("%d",&k); B1 = CreateBiTree(T1); printf("success !n"); scanf("%d",&k); int a = 0; if(Find_K(B1,&a,k)){ printf("find K!"); }else{ printf("sorry, can't find K!"); } return 0;}3.采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。
#include<stdio.h>#include<malloc.h>int n;struct VNode{ //顶点 int position;struct VNode*next;};struct ArcNode{ //弧 int gxdxh; struct VNode*first;};void DFS(struct ArcNode*v,struct ArcNode*w){ //深度优先搜索 struct VNode*L; w->gxdxh=1; L=w->first; while(L!=NULL){ if((v+(L->position))->gxdxh==0){ DFS(v,(v+L->position)); //递归调用 } L=L->next; }}int main(){ int i,j,k; int num=0; struct ArcNode*p; struct VNode*temp; struct VNode*flag; printf("n请输入顶点个数n:"); scanf("%d",&n); while(n<1){ printf("你输入的值不合理，请重新输入:n"); scanf("%d",&n); } p=(struct ArcNode*)malloc(n*sizeof(struct ArcNode)); for(i=0;i<n;i++){ //创建无向图 printf("n请输入以V%d为弧尾的所有弧，并以-1结束输入n",i+1); scanf("%d",&k); if(k==-1){ p[i].gxdxh=0; p[i].first=NULL; } else{ temp=(struct VNode*)malloc(sizeof(struct VNode)); temp->position=k; temp->next=NULL; p[i].first=temp; p[i].gxdxh=0; flag=temp; scanf("%d",&k); while(k!=-1){ temp=(struct VNode*)malloc(sizeof(struct VNode)); temp->position=k; temp->next=NULL; flag->next=temp; flag=temp; scanf("%d",&k); } } } i=0; while(p[i].gxdxh==0){ //计算连通分量的个数 DFS(p,(p+i)); num++; i=0; while(p[i].gxdxh!=0&&i<n){ i++; } } printf("此图的连通分量个数为：%dn",num); return 0;}4.编写程序实现下面运算：在二叉排序树中查找关键字为 key 的记录。
#include <stdio.h>#include <stdlib.h>#define ENDKEY 0typedef int KeyType;typedef struct node{ KeyType key ; /*关键字的值*/ struct node *lchild,*rchild;/*左右指针*/}BSTNode, *BSTree;void InsertBST(BSTree *bst, KeyType key)/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/{ BSTree s; if (*bst == NULL)/*递归结束条件*/ { s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/ s-> key=key; s->lchild=NULL; s->rchild=NULL; *bst=s; } else if (key < (*bst)->key) InsertBST(&((*bst)->lchild), key);/*将s插入左子树*/ else if (key > (*bst)->key) InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/}void CreateBST(BSTree *bst)/*从键盘输入元素的值，创建相应的二叉排序树*/{ KeyType key; *bst=NULL; scanf("%d", &key); while (key!=ENDKEY) /*ENDKEY为自定义常量*/ { InsertBST(bst, key); scanf("%d", &key); }}void PreOrder(BSTree root)/*中序遍历二叉树, root为指向二叉树根结点的指针*/{ if (root!=NULL) { PreOrder(root->lchild); /*中序遍历左子树*/ printf("%d ",root->key); /*输出结点*/ PreOrder(root->rchild); /*中序遍历右子树*/ }}/*BSTree SearchBST(BSTree bst, KeyType key)/ *在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指针* /{ if (!bst) return NULL; else if (bst->key == key) return bst;/ *查找成功* / else if (bst->key > key) return SearchBST(bst->lchild, key);/ *在左子树继续查找* / else return SearchBST(bst->rchild, key);/ *在右子树继续查找* /}*/BSTree SearchBST(BSTree bst, KeyType key)/*在根指针bst所指二叉排序树bst上，查找关键字等于key的结点，若查找成功，返回指向该元素结点指针，否则返回空指针*/{ BSTree q; q=bst; while(q) { if (q->key == key) return q; /*查找成功*/ if (q->key > key) q=q->lchild; /*在左子树中查找*/ else q=q->rchild; /*在右子树中查找*/ } return NULL; /*查找失败*/}/*SearchBST*/int main(){ BSTree T; int k; BSTree result; printf("建立二叉排序树，请输入序列以0结束:n"); CreateBST(&T); printf("先序遍历输出序列为:"); PreOrder(T); printf("n请输入要查找的元素:"); fflush(stdin); scanf("%d",&k); result = SearchBST(T,k); if (result != NULL) printf("已查到"); else printf("未找到!n");}