博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
第二个例子：单链表实现基排序（桶排序）
阅读量：5990 次
发布时间：2019-06-20

本文共 8333 字，大约阅读时间需要 27 分钟。

hot3.png

//单链表基排序（桶排序） //main.c#include
    
     #include
     
      #include
      
       #include "List.h"#include
       
        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
        
         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
         
          #include
          
           #include
           
            /*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

你可能感兴趣的文章
突破瓶颈，对比学习：Eclipse开发环境与VS开发环境的调试对比
查看>>
同步与异步&阻塞与非阻塞-各种解释
查看>>
Android中如何查看内存(上)
查看>>
Jersey2.x框架搭建简单的Restful API
查看>>
Hadoop的实现原理及基本使用方法
查看>>
Qt4.8.6编译mysql驱动-深入了解
查看>>
Oracle中nchar，char，varchar 与nvarchar区别
查看>>
js删除数组里的某个元素
查看>>
XP/win7下maven安装详解
查看>>
【MySql】2.mysql约束
查看>>
JAVA打开指定网页
查看>>
RHEL 5基础篇—常见系统启动类故障
查看>>
mysql_master__(mysql_relay)__(mysql_slave)
查看>>
（1）多线程之Object方法概述
查看>>
Apache与Nginx的优缺点比较
查看>>
pcb线宽对信号的影响怎么处理？
查看>>
Android 组件宽度高度自适应
查看>>
在Web Service中傳送Dictionary
查看>>
Linux shell定时器
查看>>
肤色检测一例-使用rgb颜色模型
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-12-31 05:16:15   当前IP: 18.191.84.179   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我