农村商业银行事业部:求C语言常用和基本结构类型

来源:百度文库 编辑:中科新闻网 时间:2024/03/29 17:57:53
如冒泡排序
选择排序
检索(查找)算法
无序数据序列的查找
有序数据序列的查找(二分法查找)
遍历算法
一维数组和二维数组的遍历
单向链表的遍历
文件的遍历
其它基本算法
以上算法最好带几个典型的例子不错的追加50分先在这谢谢大家帮忙找找

#include"stdio.h"
#include"malloc.h"
#include"math.h"
#define MAXSIZE 20

typedef struct{
int key; //关键字项
}redtype;

typedef struct{
redtype r[MAXSIZE+1];
int length; //顺序表长度
}sqlist; //顺序表类型

/* 直接插入 */
void insertsort(sqlist &L){
int i,j;
for(i=2;i<=L.length;++i)
if(L.r[i].key < L.r[i-1].key){
L.r[0] = L.r[i];
L.r[i] = L.r[i-1];
for(j=i-2;L.r[0].key < L.r[j].key;--j)
L.r[j + 1] = L.r[j] ;
L.r[j+1] = L.r[0];
}
for(i=1; i < L.length+1; i++)
printf("%d,",L.r[i].key);
}

/* 折半插入 */
void binsertsort(sqlist &L){
int low,m,high,i,j;
for(i=2;i<=L.length;++i){
L.r[0] = L.r[i];
low=1; high=i-1;
while(low <= high){
m = (low+high)/2;
if(L.r[0].key < L.r[m].key)
high = m-1;
else low = m+1;
}
for(j=i-1;j>=high+1;--j)
L.r[j+1] = L.r[j];
L.r[high+1] = L.r[0];
}
for(i=1; i < L.length+1; i++)
printf("%d,",L.r[i].key);
}

/* 希尔排序 */
void shellinsert(sqlist &L,int d){
int i,j;
for(i=d+1;i<=L.length;++i)
if(L.r[i].key < L.r[i-d].key){
L.r[0] = L.r[i];
for(j=i-d;j>0 && L.r[0].key<L.r[j].key;j=j-d)
L.r[j+d] = L.r[j];
L.r[j+d] = L.r[0];
}
}
void shellsort(sqlist &L,int dl[],int t){
int k,i;
for(k=0;k<t;++k)
shellinsert(L,dl[k]);
for(i=1; i < L.length+1; i++)
printf("%d,",L.r[i].key);
}

/* 冒泡排序 */
void bubble(sqlist &L){
int i,j;
for(j=0;j<L.length;++j)
for(i=1;i<L.length-j;++i)
if(L.r[i].key > L.r[i+1].key){
L.r[0] = L.r[i];
L.r[i] = L.r[i+1];
L.r[i+1] = L.r[0];
}
for(i=1; i < L.length+1; i++)
printf("%d,",L.r[i].key);
}

/* 快速排序 */
int partition(sqlist &L,int low,int high){
int pivotkey;
L.r[0] = L.r[low];
pivotkey = L.r[low].key;
while(low<high){
while(low<high && L.r[high].key>=pivotkey) --high;
L.r[low].key = L.r[high].key;
while(low<high && L.r[low].key<=pivotkey) ++low;
L.r[high].key = L.r[low].key;
}
L.r[low] = L.r[0];
return low;
}
void qsort(sqlist &L,int low,int high){
int pivotloc,i;
if(low < high){
pivotloc = partition(L,low,high);
qsort(L,low,pivotloc-1);
qsort(L,pivotloc+1,high);
}
}

/* 简单选择排序 */
void selectsort(sqlist &L){
int i,j,k,temp;
for(i=1; i<L.length; ++i){
k = i;
for(j = i+1;j <= L.length; ++j)
{
if(L.r[k].key > L.r[j].key)
k = j;
}
if(k != i){
temp = L.r[i].key;
L.r[i].key = L.r[k].key;
L.r[k].key = temp;
}
}
}

/* 堆排序 */
void heapajust(sqlist &L,int s,int m){
int j,temp;
temp = L.r[s].key;
for(j=2*s; j<=m; j*=2){
if(j<m && L.r[j].key<L.r[j+1].key) ++j;
if(temp > L.r[j].key) break;
L.r[s].key = L.r[j].key; s = j;
}
L.r[s].key = temp;
}
void heapsort(sqlist &L){
int i,temp;
for(i=L.length/2; i>0; --i)
heapajust(L,i,L.length);
for(i=L.length; i>1; --i)
{ temp = L.r[1].key;
L.r[1].key = L.r[i].key;
L.r[i].key = temp;
heapajust(L,1,i-1);
}
}

/* 归并排序 */
void merge(sqlist S,sqlist &T,int i,int m,int n){
int j,k;
for(j=m+1, k=i; i<=m && j<=n; ++k){
if(S.r[i].key < S.r[j].key)
T.r[k].key = S.r[i++].key;
else T.r[k].key = S.r[j++].key;
}
while(i <= m) T.r[k++].key = S.r[i++].key;
while(j <= n) T.r[k++].key = S.r[j++].key;
}
void msort(sqlist S,sqlist &T1,int l,int h){
int m;
sqlist T2;
if(l == h) T1.r[l].key = S.r[l].key;
else{
m = (l+h)/2;
msort(S,T2,l,m);
msort(S,T2,m+1,h);
merge(T2,T1,l,m,h);
}
}
void mergesort(sqlist &L){
msort(L,L,1,L.length);
}

/* 基数排序 */
void radixsort(sqlist &L){
int i,j,k,p,q,m;
int f[10][10];
printf("输入的数中最多为几位?");
scanf("%d",&m);
for(j=m; j>0; --j){
for(p=0; p<10; p++)
for(q=0; q<L.length; q++)
f[p][q] = 0; //将数组每位都置0
for(i=1; i<=L.length; ++i){
k = L.r[i].key/(int(pow(10,m-j)))%10;
p = 0; q = 0;
while(p != k) p++;
while(f[p][q] != 0) q++;
f[p][q] = L.r[i].key;
}
i = 1;
for(p=0; p<10; p++)
for(q=0; f[p][q] != 0; q++)
{ L.r[i].key = f[p][q]; i++; }
}
}

void main()
{ sqlist L;
int a,b,n,t;
int dl[10];
printf("Please input the length :") ;
scanf("%d",&L.length);
for(n=1; n < L.length+1; n++)
scanf("%d",&L.r[n].key);
b = 1;
while(b == 1){
printf("\n1.直接插入排序.\n2.折半插入排序.\n3.希尔排序\n4.冒泡排序\n5.快速排序\n6.简单选择排序.\n7.堆排序.\n8.归并排序\n9.基数排序.\n0.退出.\n请选择:");
scanf("%d",&a);
switch(a){
case 1: { printf("直接插入排序结果:");
insertsort(L);
printf("\n");
break; }
case 2: { printf("折半插入排序结果:");
binsertsort(L);
printf("\n");
break; }
case 3: {
printf("请输入希尔排序的基数个数:t = ");
scanf("%d",&t);
printf("\n输入希尔排序的基数:");
for(n=0;n<t;n++)
scanf("%d",&dl[n]);
printf("\n希尔排序结果:");
shellsort(L,dl,t);
printf("\n");
break;
}
case 4: { printf("冒泡排序结果:");
bubble(L);
printf("\n");
break; }
case 5: { printf("快速排序结果:");
qsort(L,1,L.length);
for(n=1; n < L.length+1; n++)
printf("%d,",L.r[n].key);
printf("\n");
break; }
case 6: { printf("简单选择排序结果:");
selectsort(L);
for(n=1; n < L.length+1; n++)
printf("%d,",L.r[n].key);
printf("\n");
break; }
case 7: { printf("堆排序结果:");
heapsort(L);
for(n=1; n < L.length+1; n++)
printf("%d,",L.r[n].key);
printf("\n");
break; }
case 8: { printf("归并排序结果:");
mergesort(L);
for(n=1; n < L.length+1; n++)
printf("%d,",L.r[n].key);
printf("\n");
break; }
case 9: { radixsort(L);
printf("基数排序结果:");
for(n=1; n < L.length+1; n++)
printf("%d,",L.r[n].key);
printf("\n");
break; }
case 0: b = 0; break;
}
}
}

这是基本的几种算法,其他的应该不难。

一次要求太多
还乱。