c语言数据结构基数排序算法

╰+哭是因爲堅強的太久メ 2022-01-21 23:47 258阅读 0赞

/\*  
\*基数排序算法的大概思想:  
\*首先创建一个链表用于存储待排序数组 arraynode链表  
\*创建一个储存头结点的数组 用来储存分配好的节点 0-9  
\*进行分配 即给group数组进行赋值数据  
\*首先进行分配的是 次关键字的操作 然后进行主关键字的操作（最高位）  
\*分别对分配好的数组进行收集 将头节点的指针返回值传回  
\*最后进行将主关键字的收集链表的头指针进行传回之后  
\*将链表的所有节点移动到原始数组a中  
\*输出数组中的数据  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #define RADIX 10//基数的数目
    typedef  struct node
    {
        int key;//关键字
        struct node*next;//指向下一个节点的指针
    
    }Node;//链表节点的结构体
    void  Arrange(Node*arraynode,Node *group[],int level);//链表节点分组函数
    void Radix_Sort(int a[],int n);//基数排序函数
    Node* collect(Node*group[]);//对分组的数据进行收集  返回链表的头指针
    int resolve(int key,int level);//对关键字进行  划分为主关键字 和次关键字
    void main()
    {
       int m;//数据的个数
       int n[100];//待排序的数组
       int i;//循环变量
       printf("请输入数据的个数:\n");
       scanf("%d",&m);
         printf("请依次输入数据:\n");
         for(i=0;i<m;i++)
              scanf("%d",&n[i]);
              printf("==========基数排序算法==========\n");
              Radix_Sort(n,m);
              for(i=0;i<m;i++)
                 printf("%d\t",n[i]);
    }
    void Radix_Sort(int a[],int n)//基数排序函数
    {
        int i,j;//循环变量
        int  level;//划分的层次
        Node*pnode;//中间指针
        Node*postnode;//指向最后节点的中间指针
        Node*group[RADIX];
        //定义一个分组指针数组  存储每个分组的头指针的指针
        Node*arraynode=(Node*)malloc(sizeof(Node)*n);
        //定义一个存储待排序数组的链表
        //初始化指针数组
          for(i=0;i<RADIX;i++)
             group[i]=NULL;
            //初始化待排序数据链表
               for(j=0;j<n;j++)
               {
                   arraynode[j].key=a[j];
                   arraynode[j].next=&arraynode[j+1];
               }
               arraynode[j-1].next=NULL;//创建一个完整的链表
              //为待排序的链表节点进行分组操作
               for(level=1;level<=2;level++)
               {
                   while(arraynode!=NULL)
                  {
                    pnode=arraynode->next;
                    Arrange(arraynode,group,level);
                    arraynode=pnode;
                  }
                  arraynode=collect(group);
    
               }
               pnode=arraynode;
               j=0;//再次初始化循环变量
               while(pnode)
               {
                   a[j++]=pnode->key;
                   pnode=pnode->next;
               }
               free(arraynode);//释放链表的空间
    }
    int resolve(int key,int level)//对关键字进行  划分为主关键字 和次关键字
    {
        switch(level)
        {
            case 1: key=key%10;break;//得到是次关键字
             case 2: key=(key%100)/10;break;//得到的是主关键字
        }
        return key;
    }
    void  Arrange(Node*arraynode,Node *group[],int level)//链表节点分组函数
    {
        int index;
        //Node*pnode;
        Node*postnode;//指向最后一个节点的指针
        index=resolve(arraynode->key,level);
        //pnode=arraynode;
        if(group[index]==NULL)
        {
            group[index]=arraynode;
            arraynode->next=NULL;
        }
        else
        {
            postnode=group[index];//分组操作就是对group数组的创建过程
            while(postnode->next)//将postnode指针移动到最后一个节点处
            {
                postnode=postnode->next;
            }
            postnode->next=arraynode;
            arraynode->next=NULL;
        }
    }
    Node* collect(Node*group[])//对分组的数据进行收集
    {
        int i;
        Node*pnode=NULL;
        Node*postnode=NULL;//指向最后一个节点的指针
        Node*pHead=NULL;//要返回的链表的头指针 对其进行初始化
        for(i=0;i<RADIX;i++)
        {
              if(group[i]==NULL)
                continue;//分组中没有数据  继续进行循环操作
                pnode=group[i];
                if(pHead==NULL)//头指针为空  进行赋初值的操作
                {
                    postnode=pHead=pnode;
                }
                else
                {
                    postnode->next=pnode;//将其插入到链表的最后一个节点的后面
                    pnode->next=NULL;
                    //为下一次的链表的最后一个节点后面插入元素创造条件
                }
                while(postnode->next)
                {
                    postnode=postnode->next;
                }
                group[i]=NULL;//释放group数组的空间
    
        }
              return pHead;//返回链表
    }