您好,登錄后才能下訂單哦!
C語言中怎么實現(xiàn)鏈式基數(shù)排序,針對這個問題,這篇文章詳細介紹了相對應的分析和解答,希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
C語言中數(shù)據(jù)結(jié)構(gòu)之鏈式基數(shù)排序
實現(xiàn)效果圖:
實例代碼:
#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 //關(guān)鍵字項數(shù)最大值 #define RADIX 10 //關(guān)鍵字基數(shù),此時是十進制整數(shù)的基數(shù) #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]; //關(guān)鍵字 int next; }SLCell; //靜態(tài)鏈表的結(jié)點類型 typedef struct { SLCell r[MAX_SPACE]; //靜態(tài)鏈表的可利用空間,r[0]為頭結(jié)點 int keynum; //記錄當前關(guān)鍵字個數(shù) int recnum; //靜態(tài)鏈表的當前長度 }SLList; //靜態(tài)鏈表類型 typedef int ArrType[RADIX]; //指針數(shù)組類型 /*******************************聲明部分****************************************/ /*******************************函數(shù)部分****************************************/ 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為求后繼函數(shù) 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("請輸入關(guān)鍵字個數(shù):\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("請輸入關(guān)鍵字:\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"); } /*******************************主函數(shù)部分**************************************/ int main() { SLList L; printf("創(chuàng)建靜態(tài)鏈表\n"); CreateSLL(&L); printf("創(chuàng)建完成:\n"); TraverseSLL(L); printf("\n基數(shù)排序:\n"); RadixSort(&L); TraverseSLL(L); return 0; }
關(guān)于C語言中怎么實現(xiàn)鏈式基數(shù)排序問題的解答就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。