1.[问题描述] 

设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。

[输入]

初始字符串，插入位置，插入字符，删除字符。

[输出]

已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。

[存储结构]

采用链式存储结构

[算法的基本思想]

核心思想是利用循环链表完成代码编写，参考部分网络上对于约瑟夫环问题的解决方法，思路如下：先构建循环链表，然后l，s，m，n依次出列，寻找s的位置；用if语句解决m的取值问题，之后进行输出，问题解决。

#include <stdio.h>
#include <malloc.h>
typedef struct node{//单链表节点结构 
    int date;
    struct node *next;
}node,*nodelink;

void make(nodelink head,int n){
    //n为圆桌前围绕的人数 
    //建立长度为n的单链表，对应填入每个节点对应的数字 
    //将链表的最后一个元素的指针指向头节点所指的位置，构成一个循环链表 
    int i;
    nodelink p,q;
    p=head;
    for(i=0;i<n;i++){
        q=(nodelink)malloc(sizeof(node));//申请内存 
        p->next=q;
        q->date=i+1;
        q->next=head->next;
        p=p->next;
    }
}
void dequeue(nodelink head,nodelink line,int n,int m,int s){
    //数到m的人出队
    //从第s个人开始报数 
    int i;
    nodelink p,q,r;
    p=head->next;
    //循环使p指向开始报数的人 
    for(i=1;i<s;i++){
        p=p->next;
        q=p;
    }
    //循环遍历链表，将对应位置上的链表存入新链表中
    r=line;                   //line为 新链表的头指针 
    do{
        for(i=1;i<m; 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;
}
void write(nodelink line,int n){
    int i;
    nodelink p;
    p=line->next;
    for(i=0; i<n; 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:");
    scanf("%d",&s);
    printf("输入要数的数字m:");
    scanf("%d",&m);
    dequeue(head,line,n,m,s);
    write(line,n);
    printf("\n\n");
}

2.

[问题描述]

编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。

[输入]

一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照先序序列的顺序输入该结点的内容。

要查找的结点位置k。

[输出]

若二叉树不空，按先序序列输出。

输出第k个结点的值。

[存储结构]

采用二叉链表存储。

[算法的基本思想]

采用递归方法建立二叉树，首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。先序遍历二叉树，每遍历一个结点，k的值减1，当k的值为0时，则输出当前结点。若k的值大于树中结点的个数，则输出树的结点太少，第K个结点为空。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


typedef struct BiTNode{
    char data;
    struct BiTNode *Lchild, *Rchild;
}BiTNode,*BiTree;
//寻找第k个元素 
bool Find_K(BiTree B1,int *i, int k){
    if(B1 == NULL) return false;
    (*i)++;
    if(k == *i){
        printf("%c\n", B1->data);
        return true;
    }
    if(Find_K(B1->Lchild,i,k) || Find_K(B1->Rchild,i,k))
        return true;
    return false;
}

// create Binary Tree
BiTree 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.

[问题描述]

采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。

[输入]

图的顶点个数N，图中顶点之间的关系及要找的路径的起点A和终点B。

[输出]

图的连通分量个数。

[存储结构]

图采用邻接矩阵的方式存储。 

[算法的基本思想]

采用广度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,...,VAK, 访问遍之后,若没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,...,VA1M，再访问与VA2邻接顶点...，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。实现时采用队列记录被访问过的顶点。每次访问与队头顶点相邻接的顶点，然后将队头顶点从队列中删去。若队空，则说明到不存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来，以便输出时回溯。

#include<stdio.h>
#include<malloc.h>
int n;
struct VNode{           //顶点 
    int position;struct VNode*next;
};
struct ArcNode{             //弧 
    int mark;
    struct VNode*first;
};
void DFS(struct ArcNode*v,struct ArcNode*w){   //深度优先搜索 
    struct VNode*L;
    w->mark=1;
    L=w->first;
    while(L!=NULL){
        if((v+(L->position))->mark==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].mark=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].mark=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].mark==0){            //计算连通分量的个数 
        DFS(p,(p+i));
        num++;
        i=0;
        while(p[i].mark!=0&&i<n){
            i++;
        }
    }
    printf("此图的连通分量个数为：%d\n",num);
    return 0;
}

4.

[问题描述]

编写程序实现下面运算：在二叉排序树中查找关键字为key的记录。

[输入]

输入一组序列，以0结束。

输入要查找的元素。

[输出]

先序遍历输出。

查找成功或失败。

[存储结构]

有序表采用顺序方式存储。

[算法的基本思想]

首先用待查找记录与查找区间中间位置记录比较，若相等则查找成功，返回该记录在表中的位置数，若小于中间位置记录，则修改区间上界为中间位置减 1，若大于中间位置记录，则修改区间下界为中间位置加 1，在新的区间内继续查找。当查找区间下界大于上界，则该记录不存在。

#include <stdio.h>
#include <stdlib.h>
#define ENDKEY 0
typedef 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");
}

5.

[问题描述]

1．设计一个用链表表示的直接选择排序算法，并用程序实现。

算法说明：已知待排序初始序列用单链表存贮，头指针head指向第一个结点，从这个待排序列中找出最小结点，插入head之后，用r来指示。r以前为已排序序列，r以后为未排序序列。再从未排序序列中找出最小结点插入r的后面，让r指向这个结点。反复执行这个过程，直到排好序。

[输入]

待排序记录个数n，各待排序记录值。

[输出]

n个记录由小到大排列的结果。

[存储结构]

待排序记录顺序存储。

[算法的基本思想]

快速排序算法每次任取一个记录的关键字为标准，将其余记录分为两组，将所有关键字小于或等于标准的记录都放在它的位置之前，将所有关键字大于标准的记录都放在它的位置之后。对这两组再进行快速排序，直到完全有序。每递归1次，递归深度加1。

#include <stdio.h>
#include <malloc.h>
#include <Windows.h>

int n;
 struct Number{
       int data;
       struct Number* next;
};
 
struct Number* Creat_H(int k){//创建链表   
   struct Number* L;
   struct Number* p;
   int temp,i; 
   p=(struct Number*)malloc(sizeof(struct Number));
   L=p;
   
   printf("请输入数据(数据为整型变量，中间用空格隔开)：\n");
       for(i=1;i<=k;i++){
              scanf("%d",&temp);            
              p->data=temp;
              if(i==k){
                     p->next=NULL;
                     break;
              }
              p->next=(struct Number*)malloc(sizeof(struct Number));
              p=p->next;
       }
       return L;
}

struct Number* Sort(struct Number* p){//排序
   struct Number* max;
   struct Number* min;
   struct Number* temp;
   struct Number* r;
   int flag=0;
   r=p;
       
       do{
              if(flag==0){//第一次找最小数时的初始化
                     temp=min=max=r;
              }
              else{
                     temp=min=max=r->next;
              }
              while(1){//找出最小数
                     if(min->data<=max->next->data){
                            if(max->next->next!=NULL){
                                   max=max->next;
                            }
                            else{
                                   break;
                            }
                     }
                     else{
                            temp=max;//相当于temp->next=min
                            min=max->next;
                            if(max->next->next!=NULL){
                                   max=max->next;
                            }
                            else{
                                   break;
                            }
                     }
              }
              if(temp!=min){
                     if(min->next==NULL){
                            temp->next=NULL;
                     }
                     else{
                            temp->next=min->next;
                     }
                     if(flag==0){
                            r=min;
                            r->next=p;
                            p=r;
                     }
                     else{
                            min->next=r->next;
                            r->next=min;
                            r=min;
                     }
              }
              else{//初始化时min就已经指向了最小数
                     if(flag==0){//第一次找到最小数
                            r=min;
                            p=r;
                     }
                     else{
                            r=min;
                     }
              }
              flag++;//又排好一个数
              if(flag==n-1){
                     return p;
              }
       }while(1);
}

int main(){
      
       struct Number* H;
       printf("你有多少个数据要输入(不得少于2个)：\n");
       scanf("%d",&n);
       while(n<2){
              printf("你输入的数据个数少于2个，请重新输入:\n");
              scanf("%d",&n);
       }
       H=Creat_H(n);      
       H=Sort(H);
       printf("数据排序后的序列为：\n");
       while(H!=NULL){
              printf("%-4d",H->data);
              H=H->next;
       }
       printf("\n");
       system("pause");
       return 0;
       }