|
|
一开始还以为二分法是什么难懂的算法，今天看了程序，原来二分法首先得利用磁盘文件排序里面的快速排序法，查找排好序的数据，并不难理解，源代码如下： #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM 4 struct Data
{
char name[20];
char city[20];
char sex[10];
char age[10];
char job[10];
}; struct Data SDatas[NUM]=
{
"Sun","Weifang","Male","24","student",
"Tom","Beijing","Male","31","doctor",
"Marry","Shanghai","Female","19","techer",
"Willing","Tianjing","Female","21","worker"
}; void qs_struct(items,left,right);
void quick_struct(items,count);
int BinarySeach(items,name,n);
void print_data(point); int main(void)
{
char name[30];
int i;
printf("将原始数据排序\n");
quick_struct(SDatas,NUM);
printf("请输入要查找人的名字：\n");
scanf("%s",name);
i = BinarySeach(SDatas,name,NUM);
if(i == -1)
{
printf("没有查找到该人信息\n");
return 0;
}
printf("查找结果：\n");
print_data(&SDatas[i]);
return 1;
} void quick_struct(items,count)
struct Data items[];
int count;
{
qs_struct(items,0,count-1);
} void qs_struct(items,left,right)
struct Data items[];
int left;
int right;
{
register int i,j;
char *x;
struct Data temp;
i = left;
j = right;
x = items[(left+right/2)].name;
do
{
while((strcmp(items[i].name,x)<0)&&(i<right))
i++;
while((strcmp(items[j].name,x)>0)&&(j>left))
j--;
if(i<=j)
{
temp = items[i];
items[i] = items[j];
items[j] = temp;
i++;
j--;
}
}while(i<=j);
if(left<j)
qs_struct(items,left,j);
if(i<right)
qs_struct(items,i,right);
} int BinarySeach(items,name,n)
struct Data items[];
char name[];
int n;
{
int low,high,mid;
low = 0;
high = n-1;
while(low<=high)
{
mid = (low+high)/2;
if((strcmp(items[mid].name,name)==0))
return mid;
else if((strcmp(items[mid].name,name)<0))
low = mid+1;
else high = mid-1;
}
return -1;
} void print_data(point)
struct Data *point;
{
if(point ==NULL)
return;
printf(" 姓名：%s\n",point->name);
printf(" 城市：%s\n",point->city);
printf(" 性别：%s\n",point->sex);
printf(" 年龄：%s\n",point->age);
printf(" 工作：%s\n",point->job);
} 看过的最简单的查找方式，建立链表，然后按顺序从上往下一个个数据对比查找，不用多说，贴源码： #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM 4 struct chain
{
char name[20];
char city[20];
char sex[10];
char age[10];
char job[10];
struct chain *next;
}; struct chain *create();
struct chain *SequelSeach(head,name);
void print_data(point); struct chain Datas[NUM]=
{
"Sun","Weifang","Male","24","student",NULL,
"Tom","Beijing","Male","31","doctor",NULL,
"Marry","Shanghai","Female","19","techer",NULL,
"Willing","Tianjing","Female","21","worker",NULL
}; int main(void)
{
struct chain *head;
struct chain *p;
char name[30];
head = create();
printf("请输入要查找的人名\n");
scanf("%s",name);
p = SequelSeach(head,name);
print_data(p);
return 0;
} struct chain *create()
{
struct chain *head, *tail, *p;
int i;
head = tail = NULL;
printf("将名单数据输入到链表中:\n");
for(i= 0;i < NUM; i++)
{
p = (struct chain *)malloc (sizeof (struct chain));
strcpy(p->name, Datas[i].name);
strcpy(p->city,Datas[i].city);
strcpy(p->sex,Datas[i].sex);
strcpy(p->age,Datas[i].age);
strcpy(p->job,Datas[i].job);
p->next = NULL;
if(head == NULL)
head = tail = p;
else
tail ->next = p; //此处调换次序更好理解
tail = p;
// tail = tail ->next;
// tail ->next = p;
}
return head;
} struct chain *SequelSeach(head,name)
struct chain *head;
char name[];
{
struct chain *temp;
temp = head;
for(temp=head;temp!=NULL;)
{
if(strcmp(temp->name,name) == 0)
break;
else
temp = temp->next;
}
if(temp ==NULL)
printf("没有查找到该人资料\n");
return temp;
} void print_data(point)
struct chain *point;
{
if(point ==NULL)
return;
printf("查找结果：\n");
printf(" 姓名：%s\n",point->name);
printf(" 城市：%s\n",point->city);
printf(" 性别：%s\n",point->sex);
printf(" 年龄：%s\n",point->age);
printf(" 工作：%s\n",point->job);
} 提取文件中的字符串，并利用快速排序法（quick sort）进行排序。 快速排序法的基本思想是分区。一般过程是先选一个称为比较数的值，把数组分成两段。大于或等于分区值的元素都放到一边，小于分区值的元素放到另一边，然后对数组的另一段重复上述过程，直到该数组完成排序。 源代码如下： #include <stdio.h>
#include <stdlib.h>
#include <string.h> #define NUM 4 struct data
{
char name[20];
char school[20];
char city[20];
char province[20];
}info; struct data addrs[NUM]=
{
"WenHai","BIT","JiLin","JiLin",
"TongWei","BIT","ZhengJiang","JiangSu",
"SunYou","BIT","WeiFang","ShangDong",
"XiaoMing","PKU","TaiYuan","ShanXi" };
/*对后面要用到的函数进行声明*/
void quick_disk(FILE *fp,int count);
void qs_disk(FILE *fp,int left,int right);
void exchangedata(FILE *fp,long i, long j);
char *get_name(FILE *fp, long rec);
void print_data(struct data *p);
struct data *get_data(FILE *fp,long rec); int main(void)
{
int i;
FILE *fp; /*文件指针*/
/*以读写方式生成文本文件fp*/
if((fp = fopen("datalist.txt","w+")) == NULL)
{
printf("打开文件失败\n");
exit(1);
}
printf("将未排序的数据写入文件\n");
/*将数组Sdata[NUM]写入文件中*/
fwrite(addrs,sizeof(addrs),1,fp);
/*将文件中的数组Sdata[NUM]依次取出并打印*/
for(i=0;i<NUM;i++)
{
struct data *p;
p = get_data(fp,i); /*得到Sdata[i]的指针*/
print_data(p); /*将结构体Sdata[i]各个成员变量打印出*/
printf("\n");
} fclose(fp); /*关闭文件指针*/
/*以二进制方式再次打开文件datalist.txt*/
if((fp=fopen("datalist.txt","rb+"))==NULL)
{
printf("不能以读写方式打开文件\n");
exit(1);
} printf("将文件数据排序\n");
/*调用字符串排序函数将文本中的字符串结构体排序*/
quick_disk(fp,NUM); printf("排序结束\n");
/*将排序结束后的数组数据打印出来*/
for(i=0;i<4;i++)
{
struct data *p;
p = get_data(fp,i);
print_data(p);
printf("\n");
}
fclose(fp); return 0;
}
/*应用快速排序方法对字符串进行排序*/
void quick_disk(FILE *fp,int count)
{
qs_disk(fp,0,count-1);
}
/*排序函数*/
void qs_disk(FILE *fp,int left,int right)
{
long int i,j;
char x[30];
i = left;
j = right;
/*比较字符串x为Sdata数组中间一个结构变量的name成员变量*/
strcpy(x,get_name(fp,(long)(i+j)/2));
do
{ /*比较当前结构变量的name成员变量于比较字符串x的大小*/
while((strcmp(get_name(fp,i),x)<0)&&(i<right))
i++;
while((strcmp(get_name(fp,j),x)>0)&&(j>left))
j--;
if(i<=j)
{
exchangedata(fp,i,j); /*交换i和j对应的数据*/
i++;
j--;
}
}while(i<j); if(left<j) /*反复调用此排序函数，直到j达到数据的最左端*/
qs_disk(fp,left,(int)j);
if(i<right) /*反复调用此排序函数，直到i达到数据的最右端*/
qs_disk(fp,(int)i,right);
}
/*交换i和j在文件中对应的数据*/
void exchangedata(FILE *fp,long i,long j)
{
char a[sizeof(info)],b[sizeof(info)];
fseek(fp,sizeof(info)*i,SEEK_SET); /*找到i在文件中对应的数据位置*/
fread(a,sizeof(info),1,fp); /*将该位置数据读到字符串数组a中*/ fseek(fp,sizeof(info)*j,SEEK_SET); /*找到j在文件中对应的数据位置*/
fread(b,sizeof(info),1,fp); /*将该位置数据读到字符串数组b中*/ fseek(fp,sizeof(info)*j,SEEK_SET); /*找到j在文件中对应的数据位置*/
fwrite(a,sizeof(info),1,fp); /*将刚才读入a中的数据写入到该位置*/
fseek(fp,sizeof(info)*i,SEEK_SET); /*找到i在文件中对应的数据位置*/
fwrite(b,sizeof(info),1,fp); /*将刚才读入b中的数据写入到该位置*/
/*完成文件中i和j处对应数据的交换*/
}
/*得到文件fp中变量rec对应的结构体变量的name成员变量*/
char *get_name(FILE *fp,long rec)
{
struct data *p;
p = &info;
rewind(fp);
/*找到该结构体变量得的位置*/
fseek(fp,rec*sizeof(struct data),SEEK_SET);
/*将其读到指针p*/
fread(p,sizeof(struct data),1L,fp);
return p->name; /*返回该结构体变量的name成员变量*/
}
/*得到文件fp中变量rec对应的结构体变量的指针*/
struct data *get_data(FILE *fp,long rec)
{
struct data *p;
p = &info;
rewind(fp);
/*找到该结构体变量得的位置*/
fseek(fp,rec*sizeof(info),SEEK_SET);
/*将其读到指针p*/
fread(p,sizeof(info),1,fp);
return p; /*返回该结构体指针*/
}
/*将指针p对应的结构体的各个成员变量打印出来*/
void print_data(struct data *p)
{
printf("姓名：%s\n",p->name);
printf("学校：%s\n",p->school);
printf("城市：%s\n",p->city);
printf("省 ：%s\n",p->province);
} 归并排序中最重要的方法：二路归并排序。二路归并的含义是把两个有序的序列合并成为一个有序的序列，其排序的基本思想是将有n个记录的原始序列看作n个有序的子序列，每个子序列的长度为1，然后从第一个子序列开始，把相邻的子序列两两合并，得到[n/2]个长度为2或1的子序列（当子序列个数为奇数是，最后一组合并达到的序列长度为1），把这一过程成为一次归并排序。对第一次归并排序后的[2/n]个子序列采用上述方法继续顺序成对归并，如此重复，当最后得到长度为n的一个子序列时，该子序列便是原始序列归并排序后的有序序列。 程序源代码： #include <stdio.h> void Mpass(int x[],int y[],int k,int n); /*声明其为函数*/
void Msort(int x[],int y[],int n); /*声明其为函数*/ int main(void)
{
/*要排序整型数据序列*/
int a[] = {10,9,8,7,6,5,4,3,2,1};
int y[10]; /*用于暂时存储数据*/
int i;
printf("源数据为： "); /*将源数据打印出来*/
for(i = 0;i<10;i++)
printf("[%2d]",a[i]);
Msort(a,y,10); /*对源数据进行合并排序*/
printf("\n排序后的数据为: ");
for(i = 0;i<10;i++) /*将排序结果打印出来*/
printf("%4d",a[i]);
printf("\n");
return 0;
} void Mpass(x,y,k,n)
int x[]; /*要排序的数组*/
int y[]; /*用于存储临时数据的数组*/
int k; /*表示当前序列中有若干长度为k的相邻有序子序*/
int n; /*要排序序列的长度为n*/ {
int i,j;
int strat1,end1; /*对应第一个有序子序列L1起始和终止位置号*/
int strat2,end2; /*对应第二个有序子序列L2起始和终止位置号*/
int m; /*表示输入y中当前记录应放置的位置号*/
strat1 = 0;
m = 0;
while(strat1+k<=n-1) /*当第一个子序列没有占据整个x数组*/
{
strat2 = strat1+k; /*为两个有序子序列起始终止位置号赋值*/
end1 = strat2-1;
/*如果第二的子序列长度不够k，则其终止位置号为n-1*/
end2 = (strat2+k-1<=n-1)?strat2+k-1:n-1;
for(i = strat1,j = strat2;i<=end1&&j<=end2;m++) //子序列间排序
{
if(x[i]<=x[j])
{
y[m] = x[i];
i++;
}
else
{
y[m] = x[j];
j++;
}
}
while(i<= end1) //把剩余的列链到y列上
{
y[m] = x[i];
m++;
i++;
}
while(j<= end2)
{
y[m] = x[j];
m++;
j++;
}
strat1 = end2+1;
}
/*将另一个序列中剩余的所有记录依次放到数组y中*/
for(i=strat1;i<n;i++,m++)
y[m] = x[i];
} void Msort(x,y,n)
int x[]; /*要排序的数组*/
int y[]; /*用于存储临时数据的数组*/
int n; /*数组长度*/
{
int i,k,count;
k = 1;
count = 1;
while(k<n) /*当子序列比整个序列小时*/
{
Mpass(x,y,k,n); /*归并两有序子序列*/
for(i= 0;i<n;i++)
x[i] = y[i]; /*返回数据*/
printf("\n第%2d步后的结果==> ",count++);
for(i = 1;i<n+1;i++)
{
if((i ==n)&&((i%(2*k)!=0))) //最后一个元素
printf("%4d]",x[i-1]);
else
{
if((i%(2*k)==1)) //归并后生成有序子列的第一个元素
printf("[%2d",x[i-1]);
else if((i%(2*k))==0) //归并后生成的有序子列的最后一个元素
printf("%4d]",x[i-1]);
else //既不是第一个也不是最后一个
printf("%4d",x[i-1]);
}
}
k = 2*k; /*一次归并后新的有序子序列的长度*/
}
} 运行结果： 
堆排序，一个让我懵了几天的算法，今天总算有所领悟，但还不能说能运用自如。首先说说为什么要用这个算法，原因很简单，算法优越呗，堆排序与直接插入排序对比，直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。而堆排序可通过树形结构保存部分比较结果，可减少比较次数。 堆排序要解决的两个问题：1.如何由一个无序序列建成一个堆（大根堆或小根堆）；2.如何在输出堆顶元素后，调整剩余元素成为一个新堆。 用大根堆排序的基本思想：
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区；
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key；
③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。 大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。 堆排序的算法：
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i；
BuildHeap(R)； //将R[1-n]建成初始堆
for(i=n;i>1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换
Heapify(R，1，i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质
} //endfor
} //HeapSort ① Heapify函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。
"筛选法"调整堆
R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。 ②BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为 ， -1，…，1的结点作为根的子树都调整为堆即可。 大根堆排序法动画演示 以下是看得懂的程序： #include <stdio.h>
#define MARK 0 //占据a[0]更好理解，不起实际作用 static a[16] = {MARK,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int count = 1;
void heap(int n); //建立堆函数
void adjust(int i,int n); //辅助，筛选 int main(void)
{
int i;
printf("源数据为：");
for(i = 1;i<16;i++)
printf("%5d",a[i]);
heap(15);
printf("\n排序后的数据为：");
for(i = 1;i<16;i++)
printf("%5d",a[i]);
printf("\n");
return 0;
} void heap(n)
int n;
{
int i,j,t;
for(i =n/2;i>0;i--)
adjust(i,n); //将第i个节点变为堆
printf("\n初始化成堆===> ");
for(i = 1;i < 16;i++)
printf("%5d",a[i]);
for(i = n-1;i>0;i--)
{//将堆序列中堆顶的值与末排序列中最后一个数对换
t = a[i+1];
a[i+1] = a[1];
a[1] = t;
adjust(1,i); //重新生成堆序列
printf("\n第%2d步操作结果===>",count++);
for(j = 1;j<16;j++)
printf("%5d",a[j]);
}
} void adjust(i,n)
int i,n;
{
int j,k,done=0;
k = a[i]; //暂存a[i]的值
j = 2*i;
while((j<=n)&&(done==0)) //从上往下逐级比较
{
if(j<n) //找出a[2i]和a[2i+1]中较大的一个
{
if(a[j]<a[j+1])
j++;
}
if(k>=a[j]) //如果a[i]>=a[2i]和a[2i+1]
done = 1; //跳出while循环
else
{
a[j/2] = a[j];
j = 2* j;
}
}
a[j/2] = k;
} 堆排序思想： 前提：给定一个数列（线性表） 过程：将给数列看成有序部分和无序两部分 开始数列完全是无序的；
将无序的部分调整成堆
从堆中取出堆的根，放入有序部分（可以通过交换实现）
取出后，从新将无序部分调整成堆；知道所有的元素都放入有序部分。 核心是堆的调整过程，有插入法和筛选法两种。 筛选法的核心是：根结点和孩子结点中大的那个进行比较，（大根堆）小则同孩子交换，直至找到合适的位置。
|
|
|
|
Tools 
Help
