C語言中怎么實現鏈式基數排序

C語言中怎么實現鏈式基數排序，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

C語言中數據結構之鏈式基數排序

實現效果圖：

實例代碼：

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1

typedef int Status;
typedef int ElemType;

#define MAX_NUM_OF_KEY 8 //關鍵字項數最大值
#define RADIX 10 //關鍵字基數，此時是十進制整數的基數
#define MAX_SPACE 100 //書上為10000
#define ord(ch) ((ch)-'0')
#define succ(x) ((x)+1)
typedef char KeyType;
typedef struct
{
  KeyType keys[MAX_NUM_OF_KEY]; //關鍵字
  int next;
}SLCell;  //靜態鏈表的結點類型

typedef struct
{
  SLCell r[MAX_SPACE]; //靜態鏈表的可利用空間，r[0]為頭結點
  int keynum; //記錄當前關鍵字個數
  int recnum; //靜態鏈表的當前長度
}SLList;  //靜態鏈表類型
typedef int ArrType[RADIX]; //指針數組類型

/*******************************聲明部分****************************************/



/*******************************函數部分****************************************/
void Distribute(SLCell r[],int i,ArrType f,ArrType e)
{
  int j,p;

  for(j = 0;j<RADIX;++j){
    f[j] = 0;
    e[j] = 0;
  }

  for(p = r[0].next; p ;p = r[p].next){
    j = ord(r[p].keys[i]);
    if(!f[j])
      f[j] = p;
    else
      r[e[j]].next = p;
    e[j] = p;
  }
}

void Collect(SLCell r[],int i,ArrType f,ArrType e)
{
  int j,t;

  for(j = 0; j<RADIX&&!f[j] ; j = succ(j)); //找到第一個非空子表，succ為求后繼函數
  if(j<RADIX){
    r[0].next = f[j];
    t = e[j];
    while(j<RADIX){
      for(j = succ(j) ; j<RADIX-1 && !f[j]; j = succ(j));
        if(f[j] && j<=RADIX-1){
          r[t].next = f[j];
          t = e[j];
        }
    }
    r[t].next = 0;
  }

}

void RadixSort(SLList *L)
{
  int i;
  ArrType f,e;

  for(i = 0;i<L->keynum;i++){
    Distribute(L->r,i,f,e);
    Collect(L->r,i,f,e);
  }
}

void CreateSLL(SLList *L)
{
  char s[100];
  int i,n,ct;
  L->recnum = 0;

 /*  printf("請輸入關鍵字個數：\n");
  scanf("%d",&L->keynum);
  printf("請輸入鏈表長度：\n");
  scanf("%d",&n);*/
  L->keynum = 3;
  n = 10;
  printf("依次輸入:278 109 063 963 589 184 505 269 008 083 \n");
  for(ct = 0;ct<n;ct++){
  //  printf("請輸入關鍵字：\n");

    scanf("%s",&s);
    L->recnum++;
    for(i = 0;i<L->keynum;++i)
      L->r[L->recnum].keys[L->keynum-1-i] = s[i];
  }
  for(i = 0;i<L->recnum;++i)
    L->r[i].next = i+1;
  L->r[L->recnum].next = 0;
}

void TraverseSLL(SLList L)
{
  int i,j;
  for(i = L.r[0].next; i ;i = L.r[i].next){
    for(j = L.keynum-1;j>=0;j--)
      printf("%c",L.r[i].keys[j]);
    printf(" ");
  }
  printf("\n");
}
/*******************************主函數部分**************************************/
int main()
{
  SLList L;
  printf("創建靜態鏈表\n");
  CreateSLL(&L);
  printf("創建完成：\n");
  TraverseSLL(L);

  printf("\n基數排序：\n");
  RadixSort(&L);
  TraverseSLL(L);
  return 0;
}

關于C語言中怎么實現鏈式基數排序問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。