第二个例子：单链表实现基排序（桶排序）
2019獨角獸企業重金招聘Python工程師標準>>>
//單鏈表基排序（桶排序） //main.c #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include "List.h" #include<stdbool.h>void Create_barrel(List *L); void input_barrel(List *L,int val); int output_barrel(List *L);int main(void) {int data[]={64,8,216,512,27,729,0,1,343,125}; int JPX_num=0; //基排序進行次數 int j;int i;int WEI; //個十百位 int LEN; // 數組大小 int k;int Yushu; //余數 int power=1; //10的倍數 LEN=sizeof(data)/(sizeof(int)); //數組中數據個數 bool Jiaoyan=1; //最大的位數 List barrel_num[10]; //0-10的桶 while(Jiaoyan){Jiaoyan=0; for(j=0;j<LEN;j++){WEI=(data[j]/power)%10;Jiaoyan=Jiaoyan||WEI; //獲取數組里元素的最高位數 }power*=10;JPX_num++;}JPX_num-=1;for(j=0;j<10;j++){Create_barrel(&barrel_num[j]); //為每個桶生成空鏈表，用于存儲之后數據 }//排序power=1;for(j=0;j<JPX_num;j++){for(i=0;i<LEN;i++){Yushu=(data[i]/power)%10;input_barrel(&barrel_num[Yushu],data[i]); //把數依次入桶 }k=0;for(i=0;i<10;i++){while(!IsEmpty(barrel_num[i])){data[k]=output_barrel(&barrel_num[i]); //入完桶后依次出桶，已準備下一次如同排序 k++;}}power*=10;} for(i=0;i<LEN;i++){printf("%d ",data[i]); //打印排序后的數組 } }void Create_barrel(List *L) {*L=(List)malloc(sizeof(struct Node)); //創建0-9共10個桶 (*L)->Next=NULL; }void input_barrel(List *L,int val) {InsertH(val,*L,*L); //入桶（相當于單鏈表的后插） } int output_barrel(List *L) {List m;m=(*L)->Next;int a=m->Element; //出桶（相當于單鏈表從第一個元素依次刪除） (*L)->Next=(*L)->Next->Next;free(m);return a; } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% //List.h #ifndef _LIST_H_ typedef int ElementType;struct Node;typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position;struct Node {ElementType Element;Position Next; };void CreateList(List *L,int n); void PrintList(List L);List MakeEmpty(List L); int IsEmpty(List L); void CreateEmptyList(List *L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); Position FindPrevious(ElementType X,List L); void Insert(ElementType X,List L,Position P); void InsertH(ElementType X,List L,Position P); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P);#endif %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% //List.c #include "List.h" #include<stdio.h> #include<stdlib.h> #include<malloc.h>/*struct Node {ElementType Element;Position Next; };*/void CreateList(List *L,int n) {Position P,P1;int i;*L=(Position)malloc(sizeof(struct Node));(*L)->Next=NULL;P1=*L;printf("請輸入%d個數據：\n",n); //沒問題 for(i=n;i>0;i--){//P=(Position)malloc(sizeof(struct Node));//scanf("%d",&P->Element); //前插 //P->Next=(*L)->Next;//(*L)->Next=P;P=(Position)malloc(sizeof(struct Node));scanf("%d",&P->Element);P->Next=P1->Next; //后插 P1->Next=P;P1=P;} }void PrintList(List L) {printf("已保存鏈表\n");Position P;P=L->Next;while(P->Next!=NULL){printf("%d ",P->Element); //沒問題 P=P->Next;}printf("%d ",P->Element); }void FatalError(char a[]) {printf("%s",a); //沒問題 }int IsEmpty(List L) {return L->Next==NULL; //沒問題 }int IsLast(Position P,List L) {return P->Next==NULL; }List MakeEmpty(List L) {List q,p;p=L->Next;while(p!=NULL){ //沒問題 q=p->Next;free(p);p=q;}L->Next=NULL;return L; }Position Find(ElementType X,List L) {Position P;P=L->Next;while((P->Next!=NULL)&&(P->Element!=X)) //沒問題 {P=P->Next;}return P; }Position findPrevious(ElementType X,List L) {Position P;P=L;while((P->Next!=NULL)&&(P->Next->Element!=X)) //沒問題 {P=P->Next;}return P; }void Delete(ElementType X,List L) {Position P,TmpCell;P=findPrevious(X,L);if(!IsLast(P,L)){TmpCell=P->Next;P->Next=TmpCell->Next; //沒問題 free(TmpCell);} } void DeleteList(List L) {Position P,Q;P=L->Next;L->Next=NULL;while(P!=NULL){Q=P->Next; //沒問題 free(P);P=Q;} } void Insert(ElementType X,List L,Position P) {if(L==NULL){return;} Position TmpCell;TmpCell=malloc(sizeof(struct Node));if(TmpCell!=NULL){TmpCell->Next=P->Next; //前插，沒問題 TmpCell->Element=X;P->Next=TmpCell;}else{FatalError("out of space!!!");} } void InsertH(ElementType X,List L,Position P) {if(L==NULL){return;} Position TmpCell;List q;TmpCell=malloc(sizeof(struct Node));q=L; //后插，沒問題 while(q->Next!=NULL){q=q->Next;}q->Next=TmpCell;TmpCell->Next=NULL;TmpCell->Element=X; } void CreateEmptyList(List *L) {*L=(Position)malloc(sizeof(struct Node));(*L)->Next=NULL; }//List.h
#ifndef _LIST_H_
typedef int ElementType;
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
?? ?ElementType Element;
?? ?Position Next;
};
void CreateList(List *L,int n);
void PrintList(List L);
List MakeEmpty(List L);
int IsEmpty(List L);
void CreateEmptyList(List *L);
int IsLast(Position P,List L);
Position Find(ElementType X,List L);
void Delete(ElementType X,List L);
Position FindPrevious(ElementType X,List L);
void Insert(ElementType X,List L,Position P);
void InsertH(ElementType X,List L,Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);
#endif
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//List.c
#include "List.h"
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
/*struct Node
{
?? ?ElementType Element;
?? ?Position Next;
};*/
void CreateList(List *L,int n)
{
?? ?Position P,P1;
?? ?int i;
?? ?*L=(Position)malloc(sizeof(struct Node));
?? ?(*L)->Next=NULL;
?? ?P1=*L;
?? ?printf("請輸入%d個數據：\n",n); ? ? ? ? ? ? ? ? ? ?//沒問題?
?? ?for(i=n;i>0;i--)
?? ?{
?? ??? ?//P=(Position)malloc(sizeof(struct Node));
?? ? ? ?//scanf("%d",&P->Element); ? ? ? ? ? ? ? ?//前插?
?? ? ? ?//P->Next=(*L)->Next;
?? ? ? ?//(*L)->Next=P;
?? ??? ?
?? ??? ?P=(Position)malloc(sizeof(struct Node));
?? ??? ?scanf("%d",&P->Element);
?? ??? ?P->Next=P1->Next; ? ? ? ? ? ? ? ? ? ? ? //后插?
?? ??? ?P1->Next=P;
?? ??? ?P1=P;
?? ?
?? ?}
}
void PrintList(List L)
{
?? ?printf("已保存鏈表\n");
?? ?Position P;
?? ?P=L->Next;
?? ?while(P->Next!=NULL)
?? ?{
?? ??? ?printf("%d ",P->Element); ? ? ? ? ? ? ?//沒問題?
?? ??? ?P=P->Next;
?? ?}
?? ?printf("%d ",P->Element);
}
void FatalError(char a[])
{
?? ?printf("%s",a); ? ? ? ? ? ? ? ? ? ? ? ? ? //沒問題?
}
int IsEmpty(List L)
{
?? ?return L->Next==NULL; ? ? ? ? ? ? ? ? ? ? //沒問題?
}
int IsLast(Position P,List L)
{
?? ?return P->Next==NULL;?
}
List MakeEmpty(List L)
{
?? ?List q,p;
?? ?p=L->Next;
?? ?while(p!=NULL)
?? ?{ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//沒問題?
?? ??? ?q=p->Next;
?? ??? ?free(p);
?? ??? ?p=q;
?? ??? ?
?? ?}
?? ?L->Next=NULL;
?? ?
?? ?return L;
}
Position Find(ElementType X,List L)
{
?? ?Position P;
?? ?P=L->Next;
?? ?while((P->Next!=NULL)&&(P->Element!=X)) ? ? ? ?//沒問題?
?? ?{
?? ??? ?P=P->Next;
?? ?}
?? ?
?? ?return P;
}
Position findPrevious(ElementType X,List L)
{
?? ?Position P;
?? ?P=L;
?? ?while((P->Next!=NULL)&&(P->Next->Element!=X)) ? ?//沒問題?
?? ?{
?? ??? ?P=P->Next;
?? ?}
?? ?
?? ?return P;
}
void Delete(ElementType X,List L)
{
?? ?Position P,TmpCell;
?? ?P=findPrevious(X,L);
?? ?if(!IsLast(P,L))
?? ?{
?? ??? ?TmpCell=P->Next;
?? ??? ?P->Next=TmpCell->Next; ? ? ? ? ? ? ? ? ? //沒問題?
?? ??? ?free(TmpCell);
?? ?}
}
void DeleteList(List L)
{
?? ?Position P,Q;
?? ?P=L->Next;
?? ?L->Next=NULL;
?? ?while(P!=NULL)
?? ?{
?? ??? ?Q=P->Next; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //沒問題?
?? ??? ?free(P);
?? ??? ?P=Q;
?? ?}
}
void Insert(ElementType X,List L,Position P)
{
?? ?if(L==NULL)
?? ?{
?? ??? ?return;
?? ?}?
?? ?Position TmpCell;
?? ?TmpCell=malloc(sizeof(struct Node));
?? ?if(TmpCell!=NULL)
?? ?{
?? ??? ?TmpCell->Next=P->Next; ? ? ? ? ? ? ? ? ? //前插，沒問題?
?? ??? ?TmpCell->Element=X;
?? ??? ?P->Next=TmpCell;
?? ?}
?? ?else
?? ?{
?? ??? ?FatalError("out of space!!!");
?? ?}?
}
void InsertH(ElementType X,List L,Position P)
{
?? ?if(L==NULL)
?? ?{
?? ??? ?return;
?? ?}?
?? ?Position TmpCell;
?? ?List q;
?? ?TmpCell=malloc(sizeof(struct Node));
?? ?q=L; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//后插，沒問題?
?? ?while(q->Next!=NULL)
?? ?{
?? ??? ?q=q->Next;
?? ?}
?? ?q->Next=TmpCell;
?? ?TmpCell->Next=NULL;
?? ?TmpCell->Element=X;
}
void CreateEmptyList(List *L)
{
?? ?*L=(Position)malloc(sizeof(struct Node));
?? ?(*L)->Next=NULL;
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//單鏈表基排序（桶排序）?
//main.c
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include "List.h"
#include<stdbool.h>
void Create_barrel(List *L);
void input_barrel(List *L,int val);
int output_barrel(List *L);
int main(void)
{
?? ?int data[]={64,8,216,512,27,729,0,1,343,125};?
?? ?int JPX_num=0; ? ?//基排序進行次數 ? ? ? ? ? ? ?
?? ?int j;
?? ?int i;
?? ?int WEI; ? ?//個十百位?
?? ?int LEN; ? ? ? ?// 數組大小?
?? ?int k;
?? ?int Yushu; ? ? //余數?
?? ?int power=1; ? //10的倍數?
?? ?LEN=sizeof(data)/(sizeof(int)); ? ? ? //數組中數據個數?
?? ?bool Jiaoyan=1; ? ? ?//最大的位數?
?? ?List barrel_num[10]; ? ? //0-10的桶?
?? ? ? ? ? ? ??
?? ?while(Jiaoyan)
?? ?{
?? ??? ?Jiaoyan=0;?
?? ??? ?for(j=0;j<LEN;j++)
?? ??? ?{
?? ??? ??? ?WEI=(data[j]/power)%10;
?? ??? ??? ?Jiaoyan=Jiaoyan||WEI; ? ? ? ? ? ? ? ? ? ? //獲取數組里元素的最高位數?
?? ??? ?}
?? ??? ?power*=10;
?? ??? ?JPX_num++;
?? ?}
?? ?JPX_num-=1;
?? ??
?? ?for(j=0;j<10;j++)
?? ?{
?? ??? ?Create_barrel(&barrel_num[j]); ? ? ? ? ? ? ? ? //為每個桶生成空鏈表，用于存儲之后數據?
?? ?}
?? ?//排序
?? ?power=1;
?? ?for(j=0;j<JPX_num;j++)
?? ?{
?? ??? ?for(i=0;i<LEN;i++)
?? ??? ?{
?? ??? ??? ?Yushu=(data[i]/power)%10;
?? ??? ??? ?input_barrel(&barrel_num[Yushu],data[i]); ? ? ? ? ? ?//把數依次入桶?
?? ??? ?}
?? ??? ?k=0;
?? ??? ?for(i=0;i<10;i++)
?? ??? ?{
?? ??? ??? ?while(!IsEmpty(barrel_num[i]))
?? ??? ??? ?{
?? ??? ??? ??? ?data[k]=output_barrel(&barrel_num[i]); ? ? ? ? ?//入完桶后依次出桶，已準備下一次如同排序?
?? ??? ??? ??? ?k++;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?power*=10;
?? ?}?
?? ?
?? ?for(i=0;i<LEN;i++)
?? ?{
?? ??? ?printf("%d ",data[i]); ? ? ? ? ? ? ? ? ? ? ?//打印排序后的數組?
?? ?}
}
void Create_barrel(List *L)
{
?? ?*L=(List)malloc(sizeof(struct Node)); ? ? ?//創建0-9共10個桶?
?? ?(*L)->Next=NULL;
}
void input_barrel(List *L,int val)
{
?? ?InsertH(val,*L,*L); ? ? ? ? ? ? ? ? ? ?//入桶（相當于單鏈表的后插）?
}?
int output_barrel(List *L)
{
?? ?List m;
?? ?m=(*L)->Next;
?? ?int a=m->Element; ? ? ? ? ? ? ? ? ? ? ?//出桶（相當于單鏈表從第一個元素依次刪除）?
?? ?(*L)->Next=(*L)->Next->Next;
?? ?free(m);
?? ?return a;
}
?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
輸入數組：int data[]={64,8,216,512,27,729,0,1,343,125};?
排序結果：0 1 8 27 64 125 216 343 512 729
--------------------------------
Process exited after 0.03693 seconds with return value 10
請按任意鍵繼續. . .
轉載于:https://my.oschina.net/u/3397950/blog/872539
總結
以上是生活随笔為你收集整理的第二个例子：单链表实现基排序（桶排序）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： DokuWiki 开源wiki引擎程序
- 下一篇： 记账类问题汇总