算法

技术2022-05-11 50

冒泡： #include < stdio .h> #include < string .h> bubble( strings , count ) char * strings ; int count ; { register int m , n ; register char s ; for ( m = 1; m < count ; m ++) for ( n = count -1; n >= m ;-- n ) { if ( strings [ n -1]> strings [ n ]) { s = strings [ n -1]; strings [ n -1] = strings [ n ]; strings [ n ] = s ; } } } int main ( void ) { int count ; char str [200]; printf ( " 请输入字符串： /n" ); gets ( str ); count = strlen ( str ); bubble( str , count ); printf ( " 排序之后的字符串是： /n" ); printf ( "%s./n" , str ); return 0; } 堆排序： #include < stdio .h> #define MARK 0 static a [8] = { MARK ,25,4,36,1,60,10,58,}; int count = 1; void heap ( int n ); void adjust ( int i , int n ); int main ( void ) { int i ; printf ( " 源数据为： " ); for ( i = 1; i <8; i ++) printf ( "]" , a [ i ]); heap (7); printf ( "/n 排序后的数据为： " ); for ( i = 1; i <8; i ++) printf ( "]" , 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 ); printf ( "/n 初始化成堆 ===> " ); for ( i = 1; i < 8; i ++) printf ( "]" , 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 第 - 步操作结果 ===>" , count ++); for ( j = 1; j <8; j ++) printf ( "]" , a [ j ]); } } void adjust ( i , n ) int i , n ; { int j , k , r , done =0; k = r = a [ i ]; j = 2* i ; while (( j <= n )&&( done ==0)) { if ( j < n ) { if ( a [ j ]< a [ j +1]) j ++; } if ( k >= a [ j ]) done = 1; else { a [ j /2] = a [ j ]; j = 2* j ; } } a [ j /2] = r ; }文件排序： #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); } 链表搜索： #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 = 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); } 二分法查找： #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 tree { char name [20]; char city [20]; char sex [10]; char age [10]; char job [10]; struct tree * left ; struct tree * right ; }; struct tree Datas [ NUM ]= { "Willing" , "Tianjing" , "Female" , "21" , "worker" , NULL , NULL , "Tom" , "Beijing" , "Male" , "31" , "doctor" , NULL , NULL , "Sun" , "Weifang" , "Male" , "24" , "student" , NULL , NULL , "Marry" , "Shanghai" , "Female" , "19" , "techer" , NULL , NULL }; struct tree * construct ( struct tree * root , struct tree * r , struct tree * Data ) { if (! r ) { r = ( struct tree *) malloc ( sizeof ( struct tree )); if (! r ) { printf ( " 内存分配失败！ " ); exit (0); } r -> left = NULL ; r -> right = NULL ; strcpy ( r -> name , Data -> name ); strcpy ( r -> city , Data -> city ); strcpy ( r -> sex , Data -> sex ); strcpy ( r -> age , Data -> age ); strcpy ( r -> job , Data -> job ); if (! root ) return r ; if ( strcmp ( Data -> name , root -> name )<0) root -> left = r ; else root -> right = r ; return r ; } if ( strcmp ( Data -> name , r -> name )<0) construct ( r , r -> left , Data ); else construct ( r , r -> right , Data ); return root ; } struct tree * Search ( root , name ) struct tree * root ; char name []; { struct tree * p ; if ( root == NULL ) printf ( " 该树为空 /n" ); p = root ; while ( strcmp ( p -> name , name )!=0) { if ( strcmp ( p -> name , name )>0) p = p -> left ; else p = p -> right ; if ( p == NULL ) break ; } return ( p ); } void print ( struct tree * r ) { if (! r ) return ; print ( r -> left ); printf ( "%s/n" , r -> name ); print ( r -> right ); } void print_currentData ( struct tree * 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 ); } int main ( void ) { int i ; char c [10]; char swap [20]; char name [20]; struct tree * root ,* p ; struct tree * temp ; p = NULL ; temp = NULL ; root = NULL ; for ( i = 0; i < NUM ; i ++) root = construct ( root , root ,& Datas [ i ]); printf ( " 现有人员资料： /n" ); print ( root ); printf ( " 请输入要查找的人的名字 /n" ); scanf ( "%s" , name ); p = Search ( root , name ); if ( p == NULL ) { printf ( " 没有该人资料 /n" ); printf ( " 是否要插入该人资料 [y/n]/n" ); scanf ( "%s" , c ); if ( strcmp ( c , "y" )==0) { temp = ( struct tree *) malloc ( sizeof ( struct tree )); if (! temp ) { printf ( " 内存分配失败！ " ); exit (0); } printf ( " 请输入该人姓名： /n" ); scanf ( "%s" , swap ); strcpy ( temp -> name , swap ); printf ( " 请输入该人所在城市： /n" ); scanf ( "%s" , swap ); strcpy ( temp -> city , swap ); printf ( " 请输入该人性别 [Male/Female] ： /n" ); scanf ( "%s" , swap ); strcpy ( temp -> sex , swap ); printf ( " 请输入该人年龄： /n" ); scanf ( "%s" , swap ); strcpy ( temp -> age , swap ); printf ( " 请输入该人工作： /n" ); scanf ( "%s" , swap ); strcpy ( temp -> job , swap ); temp -> left = NULL ; temp -> right = NULL ; root = construct ( root , root , temp ); print_currentData ( temp ); printf ( " 现有人员资料： /n" ); root = root ; print ( root ); } else return 0; } print_currentData ( p ); return 1; }

专利

最新回复(0)