调试程序时出错了 请高手指点下啊
这是主函数#include<iostream.h>
#include <stdlib.h>
#include <string>
#include <time.h>
#include "mylist.h"
using namespace std;
//箱子排序
//归并的思想
//如果待排序的数组有n个元素，则创建n个箱子。然后将输入数组
//中的第一个元素放入第一个箱子中。从输入数组中的第二个元素
//开始按顺序搜索输入数组中的元素；如果该元素大于第一个箱子
//中的最后一个元素，则将其放入到第一个箱子的后面。否则放入
//第二个箱子里。之后的所有大于第二个箱子里最后一个元素的元
//素放入第二个箱子里。依次类推，每当新取出的元素小于当前正
//正在使用的箱子里最后一个元素时，将下一个箱子作为当前箱子
//直到所有的元素都放入到箱子里。并记录下最后使用的箱子的次
//次序。最终所有使用了的箱子里的元素都是有序的。
//然后把使用过的箱子归并为一个有序的序列。归并过程可以这样
//首先把前两个箱子中的有序序列归并到第二个箱子里，然后再把
//第二个箱子归并到第三个箱子里。直到把所有箱子里的元素都归
//并到最后使用的一个箱子里。
//标记排序的思想
//如果待排序的数组有n个元素，每个元素含有一个可以映射到
//0 - n的属性码。则创建n个箱子，使用链表这种动态申请内存
//的结构可以节省内存。箱子放入有序数组中，箱子数组的顺序
//和输入数组的每一个元素的属性码按顺序对应。然后把输入数
//组中的元素删除到箱子中。或着记录属性码。此时箱子数组中
//有序的存储（标记）了各个不同值的元素。再把箱子中的元素
//按顺序倒回输入数组,或者根据标记的属性码值将输入数组重新
//排序。
//对于输入数组中存储的是复杂结构的情况十分有效。在这种情
//况下即使输入数组中的元素的属性值都是一样的。浪费的内存
//相对于有效使用了的内存是很小的。箱子中应该存储的是输入
//数组的属性值，而不是输入数组，这样能节省内存。
//说他来自于标记排序。是因为这和用一个辅助数组记录输入数
//组中各元素的名次，然后再插入到相应位置是一样的思想。
//箱子排序的效率与箱子的实现方式有很大的关系，不太容易分
//析。此外归并思想比标记思想的算法更具通用性。
//归并思想的实现
//将La中的元素归并到Lb中,前提La，Lb中的元素都是有序的
//且随着下标的增大而变大
int merger(LIST * La,LIST * Lb)
{
NODE *pa,*pbf,*pbs;
pa = La->head;
pbf = Lb->head;
//如果La表的第一个元素小于Lb的第一个元素
//则替换La和Lb的第一个元素。
//这是因为，若将La中的某节点插入到Lb的第
//一个元素之前，需要调整Lb的表头指针；若
//不是插在Lb的第一元素之前，又不需要调整
//表头指针。这样就不能构造循环。
//又，不可能使La中的所有元素都插在Lb的表
//头前。所以就让La的所有节点都插在Lb的表
//头之后。这样就都不需要调整表头指针。
//在交换完成后还需要恢复La和Lb的头指针的
//指向及pa和pbf的指向。
//替换将间接地引起一个问题。
//这个问题的原因是：当Lb只有一个元素，而
//La有多于一个元素，且同时出现La的第一个
//元素小于Lb的第一个元素和Lb中的第一元素
//大于La中第一个之后的某个或几个元素时。
//此时一开始pbs就会指向Lb的空尾。则会执行
//交换Lb的空尾和pa指向的链表。设置这种交换
//是为了节省时间的，却有这个问题。
//这个问题在这里解决会大量增加元素移动的
//次数。
//解决之道就是保证Lb中的元素个数多于La中
//的元素个数。此时Lb中当然就有多于一个元
//素了。
if ( first_min(&(pa->data),&(pbf->data)) )
{
pbs = pa->next;
pa->next = pbf->next;
pbf->next = pbs;
La->head = pbf;
Lb->head = pa;
pa = La->head;
pbf = Lb->head;
}
//让pbs指向Lb中当前判断的节点
//pbf指向该节点之前使插入更加容易
pbs = pbf->next;
//选择La中表头元素的插入位置，并更新La表头的指向
while (La->size > 0)
{
//如果pbs没有到Lb的结尾，则在判断是否应插入到
//pbs之前。如果pbs到达结尾if里边的判断是无效的
while ( pbs != Lb->tail && !first_min(&(pa->data),&(pbs->data)) )
{
pbf = pbs;
pbs = pbs->next;
}
//如果pbs没有到达结尾，将pa插入到pbs之前
//更新两链表信息。
//并使pbs指向pa，因为新加入的元素pa也需要参与比较
if (pbs != Lb->tail)
{
La->head = pa->next;
pa->next = pbs;
pbf->next = pa;
pbs = pa;
La->size--;
Lb->size++;
pa = La->head;
}
//如果pbs到达了Lb的结尾，则交换Lb的空尾和pa指向的
//所有节点。
else
{
La->tail = La->head = Lb->tail;
Lb->size += La->size;
La->size = 0;
pbf->next = pa;
}
}
return 0;
}
void BinSort(int * a, int n)
{
LIST *bin;
LIST *tmp_bin,*tmp_bin_f,*tmp_bin_s;
int i,j=0;
bin = new LIST[n];
//初始化各个链表
for (i = 0; i < n ; i++)
{
init_list(&(bin[i]));
}
//第一个元素存入第一个箱子
insert_tail(&(bin[0]),a);
//逐个元素放入箱子
for (i = 1; i < n ; i++)
{
if (a[i]>=a[i-1])
insert_tail(&(bin[j]),a+i);
else
{
j++;
insert_tail(&(bin[j]),a+i);
}
}
//归并所有使用了的箱子
//保证Lb中的元素个数多于La中的元素个数
//是为了解决归并函数引起的问题。
tmp_bin_f = bin;
for (i = 1; i <= j; i++)
{
tmp_bin_s = bin+i;
if (get_size(tmp_bin_f) < 2)
{
tmp_bin = tmp_bin_f;
tmp_bin_f = tmp_bin_s;
tmp_bin_s = tmp_bin;
}
merger(tmp_bin_s,tmp_bin_f);
}
for (i = 0; i < n ; i++)
{
delete_head(tmp_bin_f,a+i);
}
for (i = 0; i < n ; i++)
{
release_list(&(bin[i]));
}
delete [] bin;
}
int main()
{
const unsigned SIZE = 1000;
int i;
int *a = new int[SIZE];
clock_t start,end;
srand(time(0));
for(i = 0;i < SIZE;i++)
a[i] = rand();
start = clock();
BinSort(a,SIZE);
end = clock();
cout <<"我们用了 "<< (end -start) <<"个CPU时钟的时间来排序\n"
<<"下面将输出排序的结果：" <<endl;
system("pause");
for (i=0;i<SIZE;i++)
{
cout.width(8);
cout.setf(std::ios::left);
cout << a[i];
}
cout<<endl;
return 0;
}
这是mylist中的
#ifndef MYLIST_H_
#define MYLIST_H_ 1
/*
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
*/
/**
*作者 tr0217 （尧思齐 齐尧）
*
*此文件可以在TC2.0、vc6.0和gcc5.4.3中编译成功
*/
/*此文件文件包含了list_def.h，所以此文件不可在没有list_def.h时使用*/
/*******************************************
* *
* 警告！！！！ *
* *
*******************************************/
/*
* 警告：请仔细阅读下面一段话！！！！
*
*此文件可以在TC2.0、vc6.0和gcc5.4.3中编译成功
*/
/**
* 为了可扩展使用，下面的结点结构中用TYPE指定数据
* 类型，使用时请按照需要在list_def.h中把TYPE定义为合
* 适的类型，并且提供三个原型如下的函数
* void assign(TYPE * a,const TYPE * b);
* int is_equal(const TYPE * a,const TYPE * b);
* void print_data(const TYPE * b);
* 第一个用来为TYPE类型的数据赋值，第二个判断两个TYPE
* 类型的数据是否相等，第三个用来打印(显示)TYPE类型的
* 数据。
* 在list_def.h文件中，已经使用把TYPE定义为int类型
* (#define TYPE int);也按int类型提供了上述三个函数,如
* 需要其它类型只需做出适当的修改。
* 特别说明，也可把"TYPE定义为自己定义的结构体等其
* 它自定义类型。
* 本链表为单向链表，非常有效。可以用作队列，堆栈
* 等一些非常有用的数据结构。
**/
#include <stdio.h>
#include <stdlib.h>
/*不可缺少的宏定义和函数文件*/
#include "list_def.h"
typedef struct _NODE
{
TYPE data;
struct _NODE *next;
}NODE;
typedef struct _LIST
{
NODE *head, *tail;
unsigned size;
}LIST;
/**
*初始化链表，定义一个链表后必须初始化，
*警告！一个链表只允许调用一次
**/
void init_list(LIST *list)
{
list->tail = list->head = (NODE*)malloc(sizeof(NODE));
list->head->next = NULL;
list->size = 0;
}
/*释放链表所占用的资源，在链表使用结束后必须调用*/
void release_list(LIST *list)
{
NODE *p1,*p2;
p1 = p2 = list->head;
while(p1->next != NULL)
{
p2 = p1->next;
free(p1);
p1 = p2;
}
}
/*为又一次的使用更新链表*/
void update_list(LIST *list)
{
release_list(list);
init_list(list);
}
/*获取链表的长度,可用来测试链表是否为空*/
unsigned get_size(LIST *list)
{
return list->size;
}
/*显示链表中的元素*/
void print_list(const LIST *list)
{
NODE *p;
p = list->head;
while(p != list->tail)
{
print_data(&(p->data));
p = p->next;
}
}
/*在链表头添加元素*/
void insert_head(LIST *list,const TYPE * data)
{
NODE *p;
p = (NODE*)malloc(sizeof(NODE));
assign(&(p->data) ,data);
p->next = list->head;
list->head = p;
list->size++;
}
/*在链表尾添加元素*/
void insert_tail(LIST *list,const TYPE * data)
{
NODE *p;
assign(&(list->tail->data) ,data);
p = (NODE*)malloc(sizeof(NODE));
list->tail->next = p;
list->tail = p;
list->tail->next = NULL;
list->size++;
}
/**
*删除链表头部元素到data中
*如果删除的元素不需要存储传入NULL即可
**/
void delete_head(LIST *list,TYPE * data)
{
NODE *p;
if(data != NULL)
assign(data,&(list->head->data));
p = list->head->next;
free(list->head);
list->head = p;
list->size--;
}
/**
*删除链表尾部元素到data中
*如果删除的元素不需要存储传入NULL即可
*使用该函数前一定要测试链表是否为空
*该函数效率不高，且无法优化
*一定要尽量避免使用该函数
**/
void delete_tail(LIST *list,TYPE * data)
{
NODE *p = list->head;
unsigned i = 1;
while(i < list->size)
{
p = p->next;
i++;
}
free(list->tail);
list->tail = p;
if(data != NULL)
assign(data,&(p->data));
list->size--;
}
/**
*查找某元素是否在链表中，
*如果在，则返回其指针；位置应从1开始
*否则返回NULL，本函数同样效率不高，且无法优化
*由于使用单向链表，只能用顺序查找法，
*使用该函数应十分小心，将该函数放到等号的左边，
*即作为左值，可以改变链表中index
*处的值。如果没有此意图，请注意。
**/
NODE * find(LIST *list,const TYPE *data)
{
int flag = 1;
NODE *p = list->head;
while(flag||p != list->tail)
{
if(is_equal(&(p->data),data))
{
flag = 0;
}
else p = p->next;
}
if(p == list->tail)
p = NULL;
return p;
}
/**
*返回链表中第index个位置处的元素的指针
*使用该函数应十分小心，将该函数放到等号的左边，
*即作为左值，可以改变链表中index
*处的值。如果没有此意图，请注意。
*i值从1开始，index<= list->size
**/
TYPE * get_at(LIST *list,unsigned index)
{
NODE *p = list->head;
unsigned i = 1;
while(i < index)
{
p = p->next;
i++;
}
return &(p->data);
}
#endif
这是list_def中的
#ifndef LIST_DEF_H_
#define LIST_DEF_H_ 1
/*定义TYPE为合适的类型*/
#define TYPE int
/*提供所需的赋值函数*/
inline void assign(TYPE * a,const TYPE * b)
{
*a = *b;
}
/*提供所需的判断相等函数*/
inline int is_equal(const TYPE * a,const TYPE * b)
{
if(*a == *b)
return 1;
else return 0;
}
/*提供所需的判断相等函数*/
inline int first_max(const TYPE * a,const TYPE * b)
{
if(*a > *b)
return 1;
else return 0;
}
/*提供所需的判断相等函数*/
inline int first_min(const TYPE * a,const TYPE * b)
{
if(*a < *b)
return 1;
else return 0;
}
/*提供所需的打印(显示)函数*/
inline void print_data(const TYPE * b)
{
printf("%-10d",*b);
}
#endif
