视频与-算法导论

算法导论2Cc99的一些特性，如变长数组。需要用gcc指定选项-std=c99编译，不支持VC。第2章2.1排#include<stdio.h>#include<time.h>#include<stdlib.h>voidinsertion_sort(void*base,size_em_size,size_tn,int(*comp)(constvoid*,constvoid*)){char*cbase=base;for(size_ti=1;i<n;i++)memcpy(key,&cbase[i*elem_size],/*把base[i]到排好序的base[0..i-1]中*/intj=i-1;while(j>=0&&comp(&cbase[j*elem_size],key)>{memcpy(&cbase[(j+1)*elem_size],&cbase[j*elem_size],elem_size);}memcpy(&cbase[(j+1)*elem_size],key,}}voidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}voidrandomized_in_place(void*array,size_em_size,int{char*carray=for(inti=0;i<n;i++)intindex=rand()%(n-i)+swap(&carray[i*elem_size],&carray[index*elem_size],}}voidprint_array(inta[],int{for(inti=0;i<n;{printf("%d",}}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=p2;if(*pa<*pb)return-1;if(*pa==*pb)returnreturn}int{srand((unsigned)tiintfor(inti=0;i<10;{a[i]=}randomized_in_place(asizeof(int10);print_array(a,insertion_sort(a,sizeof(int10,cmp_int);print_array(a,return}2.3#include<stdio.h>#include<stdlib.h>#include<time.h>voidmerge(void*base,size_em_size,size_tleft,size_tmiddle,size_tright,void*max,int(*comp)(constvoid*,constvoid*),void*buff){char*cbuff=size_tleft_length=middle-left+1;size_tright_length=right-middle;char*left_buff=cbuff;char*right_buff=&cbuff[(left_length+1)*elem_size];for(size_ti=0;i<left_length;i++){memcpy(&left_buff[i*&cbase[(left+i)*elem_size],}for(size_ti=0;i<right_length;i++){memcpy(&right_buff[i*&cbase[(middle+1+i)*elem_size],}memcpy(&right_buff[right_length*elem_size],max,elem_size);for(size_tk=left,i=0,j=0;k<=right;k++){<=0)memcpy(&cbase[k*elem_size],&left_buff[i*elem_size],}elsememcpy(&cbase[k*}}}voidmerge_sort_buff(void*base,size_em_size,size_tleft,size_tright,void*max,int(*comp)(constvoid*,constvoid*),void{if(left<right)size_tmiddle=(left+right)/merge_sort_buff(base,elem_size,left,middle,max,comp,buff);merge_sort_buff(base,elem_size,middle+1,right,max,merge(base,elem_size,left,middle,right,max,comp,}}voidmerge_sort(void*base,size_em_size,size_tleft,size_tright,void*max,int(*comp)(constvoid*,constvoid*)){size_tlengthright-left1;*数组的长度charbuff[(length+2)* /*+2是因为要在缓存保存两个最大值merge_sort_buff(base,elem_size,left,right,max,comp,}voidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);voidrandomized_in_place(void*array,size_em_size,int{char*c_array=array;for(inti=0;i<n;i++){intindex=rand()%(n-i)+swap(&c_array[i*elem_size],&c_array[index*elem_size],}}voidprint_array(inta[],int{for(inti=0;i<n;{printf("%d",}}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=p2;if(*pa<*pb)return-if(*pa==*pb)return0;return}int{inta[10];for(inti=0;i<10;{a[i]=}randomized_in_place(asizeof(int10);print_array(a,intmax_int=merge_sort(a,sizeof(int09&max_int,cmp_int);print_array(a,return第5章概率分析和随机算法5.1#include<stdlib.h>#include<stdio.h>#include<time.h>voidhire_assistant(intA[],int{intbest=0;for(inti=0;i<n;{if(A[i]>best){best=A[i];printf("%d",i);}}}int{inta[10];for(inti=0;i<10;{a[i]=rand()%printf("%d",}printf("\n");return}#include#include<limits.h>#include<string.h>#include<stdlib.h>#include<time.h>voidmerge(void*base,size_em_size,size_tleft,size_tmiddle,size_tright,void*max,int(*comp)(constvoid*,constvoid*),void*buff){char*cbuff=size_tleft_length=middle-left+1;size_tright_length=right-middle;char*left_buff=cbuff;char*right_buff=&cbuff[(left_length+1)*for(size_ti=0;i<left_length;{memcpy(&left_buff[i*&cbase[(left+i)*elem_size],}for(size_ti=0;i<right_length;i++){memcpy(&right_buff[i*&cbase[(middle+1+i)*elem_size],}memcpy(&right_buff[right_length*elem_size],max,elem_size);for(size_tk=left,i=0,j=0;k<=right;k++){<=0)memcpy(&cbase[k*elem_size],&left_buff[i*elem_size],}elsememcpy(&cbase[k*}}}voidmerge_sort_buff(void*base,size_em_size,size_tleft,size_tright,void*max,int(*comp)(constvoid*,constvoid*),void{if(left<right)size_tmiddle=(left+right)/merge_sort_buff(base,elem_size,left,middle,max,comp,buff);merge_sort_buff(base,elem_size,middle+1,right,max,merge(base,elem_size,left,middle,right,max,comp,}}voidmerge_sort(void*base,size_em_size,size_tleft,size_tright,void*max,int(*comp)(constvoid*,constvoid*)){size_tlengthright-left1;*数组的长度charbuff[(length+2)* /*+2merge_sort_buff(base,elem_size,left,right,max,comp,}struct{intvoid /*挷定了一个数据的指针intcmp_donstvoid*p1,constvoid{conststructrand_data*pa=p1;conststructrand_data*pb=returnpa->rand_num-pb-}voidpermute_by_sorting(void*base,size_em_size,int{char*cbase=/*把原来的数组一份chardata_copy[elem_size*memcpy(data_copy,base,elem_size*length);structrand_datarand_data_array[length];for(inti=0;i<length;{=rand()%(length*length*length);}structrand_datadata_max={INT_MAX,NULL};merge_sort(rand_data_array,sizeof(structrand_data),0,length-1,&data_max,/*根据按随机数排序的结果把数据回原来的数组*/for(inti=0;i<length;i++){}}voidrandomized_hire_assistant(intA[],int{permute_by_sorting(A,sizeof(int),length);intbest=for(inti=0;i<length;{if(A[i]>best){best=A[i];printf("%d",i);}}}int{inta[10];for(inti=0;i<10;{a[i]=}randomized_hire_assistant(a,return}#include<stdio.h>#include<stdlib.h>#include<time.h>#includevoidswap(void*a,void*b,size_{char /*变长数组memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}voidrandomized_in_place(void*array,size_em_size,int{char*carray=for(inti=0;i<length;i++)intrand_index=rand()%(length-i)+swap(&carray[i*elem_size],&carray[rand_index*elem_size],}}voidrandomized_hire_assistant(intA[],int{randomized_in_place(A,sizeof(int),n);intbest=0;for(inti=0;i<n;{if(A[i]>{best=A[i];printf("%d",i);}}}int{inta[10];for(inti=0;i<10;{a[i]=}randomized_hire_assistant(a,return}5.4.4雇用问#include<stdio.h>#include<stdlib.h>#include<math.h>#include<time.h>#includeinton_line_um(intA[],intn,int{for(inti=0;i<k;i++){if(A[i]>{best_score=}}for(inti=k;i<n;{if(A[i]>{return}}returnn-}int{inta[10];for(inti=0;i<10;{a[i]=rand()%}intn=on_line_um(a,10,10/boolflag=true;for(inti=0;i<10;{if(a[i]>a[n]){flag=false;}}return0;}第6章#include<stdio.h>#include<time.h>#include<stdlib.h>intparent(inti){return(i-1)/}intleft_child(int{returni*2+}intright_child(int{returni*2+}voidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}voidmax_heapify(void*base,size_em_size,inti,intheap_size,int(*comp)(constvoid*,constvoid*)){char*cbase=base;intleft=left_child(i);intright=right_child(i);intlargest=i;if(left<&cbase[left*elem_size])<0){largest=}if(right<&cbase[right*elem_size])<0){largest=}if(largest!=i)swap(&cbase[i*elem_size],&cbase[largest*elem_size],max_heapify(base,elem_size,largest,heap_size,}}voidbuild_max_heap(void*base,size_em_size,intlength,int(*comp)(constvoid*,constvoid*)){intheap_size=for(inti=parent(length-1);i>=0;i--{max_heapify(base,elem_size,i,heap_size,}}voidheap_sort(void*base,size_em_size,intlength,int(*comp)(constvoid*,constvoid*)){char*cbase=build_max_heap(base,elem_size,length,comp);intheap_size=length;for(inti=length-1;i>0;i--)swap(&cbase[i*elem_size],&cbase[0*elem_size],--max_heapify(base,elem_size,0,heap_size,}}voidrandomized_in_place(void*array,size_em_size,int{char*carray=for(inti=0;i<length;i++)intn_rand_index=rand()%(length-i)+swap(&carray[i*elem_size],&carray[n_rand_index*elem_size],}}voidprint_array(inta[],int{for(inti=0;i<length;{printf("%d",}}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=p2;if(*pa<*pb)return-1;if(*pa==*pb)returnreturn}int{inta[10];for(inti=0;i<10;{a[i]=}randomized_in_place(asizeof(int10);print_array(a,heap_sort(a,sizeof(int10,cmp_int);print_array(a,return}#include<stdio.h>#include<stdlib.h>#includestructpriority_queue_type{voidint(*comp)(constvoid*,constvoidintparent(int{return(i-1)/}intleft_child(int{returni*2+}intright_child(int{returni*2+}voidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}voidheapify(priority_queuepq,int{intleft=left_child(i);intright=right_child(i);intlargest=i;if(left<pq-{largest=}if(right<pq-&&pq->comp(pq->array[largest],pq->array[right])<0)largest=}if(largest!=i)swap(&pq->array[i],&pq->array[largest],sizeof(void*));heapify(pq,largest);}}voidfix_up(priority_queuepq,int{{swap(&pq->array[parent(i)],&pq->array[i],sizeof(void*));i=parent(i);}}priority_queuepriority_queue_create(intint(*comp)(constvoid*,constvoid{priority_queuepq=malloc(sizeof(structpriority_queue_type));pq->array=malloc(sizeof(void*)*n_length);pq->heap_size=0;pq->comp=comp;returnpq;}void*priority_queue_top(priority_queue{returnpq-}/*去掉并返回堆的第一个元素void*priority_queue_extract_top(priority_queue{swap(&pq->array[0],&pq->array[pq->heap_size-1],sizeof(voidheapify(pq,0);returnpq->array[pq-}/*把元素key队列voidpriority_queue_insert(priority_queuepq,void{inti=pq->heap_size-memcpy(&pq->array[i],&key,sizeof(void*));fix_up(pq,i);}boolpriority_queue_is_empty(priority_queue{}voidpriority_queue_destroy(priority_queuepq,void(*free_key)(void{while(!priority_queue_is_empty(pq))void*p=priority_queue_extract_top(pq);}}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=p2;if(*pa<*pb)return-1;if(*pa==*pb)returnreturn}int{priority_queuepq=priority_queue_create(10,cmp_int);for(inti=0;i<10;i++){int*p=*p=i;}printf("最大堆结果while(!priority_queue_is_empty(pq))printf("%d",*p);}return0;}#include<stdio.h>#include<limits.h>#include<stdlib.h>#include<string.h>struct{intheap_size;intint*index_pos_array;/**/void*data_array;size_int(*comp)(constvoid*,constvoidstaticintparent(int{return(i-1)/}staticintleft_child(int{returni*2+}staticintright_child(int{returni*2+}voidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}staticvoidswap_index(priority_queuepq,inti,int{swap(&pq->index_pos_array[i],&pq->index_pos_array[j],sizeof(int));pq->index_array[pq->index_pos_array[i]]=i;pq->index_array[pq->index_pos_array[j]]=}staticboolcompare(priority_queuepq,intleft,int{returnfalse;char*pc_array=pq-&pc_array[right*pq->elem_size])>0;}staticvoidheapify(priority_queuepq,int{intleft=left_child(i);intright=right_child(i);intlargest=i;if(left<pq-{largest=}if(right<pq-{largest=}if(largest!=i)heapify(pq,largest);}}staticvoidfix_up(priority_queuepq,int{while(i>{swap_index(pq,pq->index_array[parent(i)],pq-i=}}priority_queuepriority_queue_create(void*p_data_array,size_intlength,int(*comp)(constvoidconstvoid{pq->index_array=malloc(sizeof(int)*length);pq->index_pos_array=malloc(sizeof(int)*length);pq->data_array=p_data_array;pq->heap_size=0;pq->comp=comp;returnpq;}voidpriority_queue_destroy(priority_queue{}intpriority_queue_top(priority_queue{returnpq-}/*去掉并返回堆的第一个元素intpriority_queue_extract_top(priority_queue{swap_index(pq,pq->index_array[0],pq->index_array[pq->heap_size-heapify(pq,0);returnpq->index_array[pq-}/*把元素的索引队列voidpriority_queue_insert(priority_queuepq,int{inti=pq->heap_size-pq->index_array[i]=pq->index_pos_array[index]=i;fix_up(pq,i);}boolpriority_queue_is_empty(priority_queue{}/*index的数据修改了，调用这个函数来修复索引堆*/voidpriority_queue_change_index(priority_queuepq,intindex){fix_up(pq,pq->index_pos_array[index]);heapify(pq,pq-}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=p2;if(*pa<*pb)return-1;if(*pa==*pb)returnreturn}intmain(){priority_queuepqfor(inti=0;i<10;i++){g_array[i]=/*把索引i到索引堆pq*/priority_queue_insert(pq,i);}/*chang_index,修过索引上的数据，然后修复索引堆*/intchange_index=5;g_array[change_index]=printf("最小堆结果while(!priority_queue_is_empty(pq))printf("%d",}return0;}第7章#include<stdio.h>#include<time.h>#include<stdlib.h>#includevoidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}intpartition(void*base,size_em_size,intp,intr,int(*comp)(constvoid*,constvoid{char*cbase=void*key=&cbase[r*elem_size];inti=p-1;for(intj=p;j<r;j++)if(comp(&cbase[j*elem_size],key)<=0)swap(&cbase[i*elem_size],&cbase[j*elem_size],}}swap(&cbase[(i+1)*elem_size],key,elem_size);returni+1;}voidquick_sort(void*base,size_em_size,intp,intint(*comp)(constvoid*,constvoid{if(p<r)intq=partition(base,elem_size,p,r,comp);quick_sort(base,elem_size,p,q-1,comp);quick_sort(base,elem_size,q+1,r,comp);}}voidrandomized_in_place(void*array,size_em_size,int{char*carray=for(inti=0;i<length;i++)intrand_index=rand()%(length-i)+swap(&carray[i*elem_size],&carray[rand_index*elem_size],}}voidprint_array(inta[],int{for(inti=0;i<length;{printf("%d",}}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=p2;if(*pa<*pb)return-1;if(*pa==*pb)returnreturn}int{inta[10];for(inti=0;i<10;{a[i]=}randomized_in_place(asizeof(int10);print_array(a,quick_sort(a,sizeof(int0,9cmp_int);print_array(a,return}7.3#include<stdio.h>#include<time.h>#include<stdlib.h>#includevoidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}intpartition(void*base,size_em_size,intp,intr,int(*comp)(constvoid*,constvoid{char*cbase=void*key=&cbase[r*elem_size];inti=p-1;for(intj=p;j<r;j++)if(comp(&cbase[j*elem_size],key)<=0)swap(&cbase[i*elem_size],&cbase[j*elem_size],}}swap(&cbase[(i+1)*elem_size],key,elem_size);returni+1;}intrandomized_partition(void*base,size_em_size,intp,intr,int(*comp)(constvoid*,constvoid*)){char*cbase=inti=rand()%(r-p+1)+swap(&cbase[r*elem_size],&cbase[i*elem_size],elem_size);returnpartition(base,elem_size,p,r,comp);}voidrandomize_quick_sort(void*base,size_em_size,intp,intr,int(*comp)(constvoid*,constvoid*)){if(p<r)intq=randomized_partition(base,elem_size,p,r,comp);randomize_quick_sort(base,elem_size,p,q-1,comp);randomize_quick_sort(base,elem_size,q+1,r,comp);}}voidrandomized_in_place(void*array,size_em_size,int{char*carray=for(inti=0;i<length;i++)intn_rand_index=rand()%(length-i)+swap(&carray[i*elem_size],&carray[n_rand_index*elem_size],}}voidprint_array(inta[],int{for(inti=0;i<length;{printf("%d",}}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=p2;if(*pa<*pb)return-1;if(*pa==*pb)returnreturn}int{inta[10];for(inti=0;i<10;{a[i]=}randomized_in_place(asizeof(int10);print_array(a,print_array(a,return}第8章线性时间排序#include<stdio.h>#include<stdlib.h>#include<time.h>voidcounting_sort(intA[],intn,int{int*C=malloc(sizeof(int)*(k+1));for(inti=0;i<=k;i++){C[i]=}for(inti=0;i<n;i++)}for(inti=1;i<=k;{C[i]+=C[i-}int*B=malloc(sizeof(int)*n);for(inti=n-1;i>=0;i--){B[C[A[i]]-1]=--}for(inti=0;i<n;{A[i]=}}voidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}voidrandomized_in_place(void*array,size_em_size,int{char*c_array=array;for(inti=0;i<n;i++){intindex=rand()%(n-i)+swap(&c_array[i*elem_size],&c_array[index*elem_size],}}voidprint_array(inta[],int{for(inti=0;i<n;{printf("%d",}}int{inta[10];for(inti=0;i<10;i++)a[i]=rand()%}randomized_in_place(asizeof(int10);print_array(a,print_array(a,10);return}#include<stdio.h>#include<string.h>#include<stdlib.h>#include<time.h>#include<math.h>intdigit(intn,int{staticintifbase_array[0] //求进制位的基值{base_array[0]=for(inti=1;i<20;i++)base_array[i]=base_array[i-1]*}}intn_base=base_array[w-1];returnn/n_base%10;}voidcounting_sort(intA[],intn,intk,int{int*C=malloc(sizeof(int)*(k+1));for(inti=0;i<=k;i++){C[i]=}for(inti=0;i<n;i++)}for(inti=1;i<=k;{C[i]+=C[i-}int*B=malloc(sizeof(int)*n);for(inti=n-1;i>=0;i--){B[C[digit(A[i],w)]-1]=}for(inti=0;i<n;{A[i]=}}voidradix_sort(intA[],intn,int{for(inti=1;i<=d;{counting_sort(A,n,9,}}voidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}voidrandomized_in_place(void*array,size_em_size,int{char*c_array=array;for(inti=0;i<n;i++){intindex=rand()%(n-i)+swap(&c_array[i*elem_size],&c_array[index*elem_size],}}voidprint_array(inta[],int{for(inti=0;i<n;{printf("%d",}}int{inta[10];for(inti=0;i<10;{a[i]=}randomized_in_place(asizeof(int10);print_array(a,radix_sort(a,10,3);print_array(a,10);return}#include<stdio.h>#include<stdlib.h>#include<time.h>structnode{floatstructnodevoidnode_ini(structnode*pnode,float{pnode->value=value;pnode->next=}voidinsert_node(structnode*head,structnode{structnode*p=head;while(p->next!=NULL){{}elsep=p-}}p->next=pnode;}voidbucket_sort(floatA[],int{structnode*node_array=malloc(sizeof(structnode)*n);for(inti=0;i<n;i++)for(inti=0;i<n;i++){structnode*p=malloc(sizeof(structnode));node_ini(p,A[i]);insert_node(&node_array[(int)(n*A[i])],p);}intk=for(inti=0;i<n;i++)for(structnode*p=node_array[i].next;p!={A[k++]=p->value;structnode*del=p;p=p->next;}}}voidswap(void*a,void*b,size_{if(a==NULL||b==NULL||a==b)chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}voidrandomized_in_place(void*array,size_em_size,int{char*c_array=array;for(inti=0;i<n;i++){intindex=rand()%(n-i)+swap(&c_array[i*elem_size],&c_array[index*elem_size],}}voidprint_array(floata[],int{for(inti=0;i<n;{printf("%.2f",}}int{floata[10];for(inti=0;i<10;i++)a[i]=rand()/}randomized_in_place(asizeof(int10);print_array(a,bucket_sort(a,10);print_array(a,10);return}第9章中位数和顺序统计学#include<stdio.h>#include<stdlib.h>#include<time.h>#includeintminimum(intA[],int{intmin=for(inti=1;i<n;{if(min>A[i]){min=A[i];}}returnvoidmin_and_max(intA[],intn,int*min,int{intif(n%2==1)*min=i=1;}elseif(A[0]>A[1])*max=*min=}else*max=*min=}i=}for(;i<n;i+=2)if(A[i]>A[i+1])if(A[i]>*max)*max=}if(A[i+1]<*min)*min=A[i+}}elseif(A[i+1]>*max)*max=A[i+}if(A[i]<*min)*min=}}}}voidprint_array(inta[],int{for(inti=0;i<n;{printf("%d",}int{inta[10];for(inti=0;i<10;{a[i]=rand()%}intmin;intmax;printf("最小和最大元素是}#include<stdio.h>#include<stdlib.h>#include<time.h>#includevoidswap(void*a,void*b,size_{chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}intpartition(void*base,size_em_size,intp,intr,int(*comp)(constvoid*,constvoid{char*cbase=void*key=&cbase[r*elem_size];inti=p-1;for(intj=p;j<r;j++)if(comp(&cbase[j*elem_size],key)<=0)swap(&cbase[i*elem_size],&cbase[j*elem_size],}}swap(&cbase[(i+1)*elem_size],key,elem_size);returni+1;}intrandomized_partition(void*base,size_em_size,intp,intr,int(*comp)(constvoid*,constvoid*)){char*cbase=inti=rand()%(r-p+1)+swap(&cbase[r*elem_size],&cbase[i*elem_size],elem_size);returnpartition(base,elem_size,p,r,comp);}void*randomized_select(void*base,size_em_size,intp,intr,inti,int(*comp)(constvoid*,constvoid*)){if(p==r)return&cbase[p*intq=randomized_partition(base,elem_size,p,r,comp);intk=q-p+1;if(i==k)return&cbase[q*}elseif(i<k)returnrandomized_select(base,elem_size,p,q-1,i,}elsereturnrandomized_select(base,elem_size,q+1,r,i-k,}}voidprint_array(inta[],int{for(inti=0;i<length;{printf("%d",}}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=if(*pa<return-1;if(*pa==returnreturn}voidrandomize_quick_sort(void*base,size_em_size,intp,intr,int(*comp)(constvoid*,constvoid*)){if(p<r)intq=randomized_partition(base,elem_size,p,r,comp);randomize_quick_sort(base,elem_size,p,q-1,comp);randomize_quick_sort(base,elem_size,q+1,r,comp);}}int{inta[10];for(inti=0;i<10;{a[i]=rand()%}print_array(a,10);intorder=int*select_value=randomized_select(a,sizeof(int),0,9,order,cmp_int);randomize_quick_sort(a,sizeof(int),0,9,cmp_int);*select_valuea[order1]相等不相等return}9.3情况线性时间的选#include<stdio.h>#include<stdlib.h>#include<time.h>#includevoidinsertion_sort(void*base,size_em_size,size_tn,int(*comp)(constvoid*,constvoid*)){char*cbase=base;for(size_ti=1;i<n;i++)memcpy(key,&cbase[i*elem_size],/*把base[i]到排好序的base[0..i-1]中*/intj=i-1;while(j>=0&&comp(&cbase[j*elem_size],key)>{memcpy(&cbase[(j+1)*elem_size],&cbase[j*elem_size],elem_size);}memcpy(&cbase[(j+1)*elem_size],key,}}voidswap(void*a,void*b,size_{if(a==NULL||b==NULL||a==b)chartemp[elem_size]; /**/memcpy(temp,a,elem_size);memcpy(a,b,elem_size);}intpartition(void*base,size_em_size,intp,intr,void*pivot,int(*comp)(constvoid*,constvoid*)){void*key=pivot;inti=p-1;intpivot_posp;/*主元的位置*/for(intj=p;j<r;j++){if(comp(&cbase[j*elem_size],key)==0)pivot_pos=j;/*记录主元的位置if(comp(&cbase[j*elem_size],key)<=0)swap(&cbase[i*elem_size],&cbase[j*elem_size],}}swap(&cbase[(i+1)*elem_size],&cbase[pivot_pos*elem_size],returni+}void*select(void*base,size_em_size,intp,intr,intorder,int(*comp)(constvoid*,constvoid*)){if(p==r)intn=r-p+1;intarray_count=n%5==0?n/5:n/5+1;chararray[elem_size*array_count];for(inti=0;i<array_count;{intbegin=p+i*intend=begin+4<r?begin+4:r;end-begin+1,comp);intmiddle=begin+(end-begin)/2;memcpy(&array[i*elem_size],&cbase[middle*elem_size],}void*xselect(array,elem_size,0,array_count-1,(array_count+1)/2,/*xA，保证对数组的划分是好的划分*/intq=partition(base,elem_size,p,r,x,comp);intk=q-p+1;if(order==k)return&cbase[q*}elseif(order<k)returnselect(base,elem_size,p,q-1,order,}elsereturnselect(base,elem_size,q+1,r,order-k,}}voidprint_array(inta[],int{for(inti=0;i<length;{printf("%d",}}intcmp_int(constvoid*p1,constvoid{constint*pa=p1;constint*pb=p2;if(*pa<*pb)return-1;if(*pa==*pb)returnreturn}int{inta[10];for(inti=0;i<10;{a[i]=rand()%}print_array(a,10);intorder=int*select_value=select(a,sizeof(int),0,9,order,cmp_int);insertion_sort(a,sizeof(int),10,cmp_int);*select_valuea[order1]相等不相等return}第10章栈#include<stdio.h>#include<stdlib.h>typedefstructstack_type*stack;structstack_type{inttop;voidstackstack_create(int{stacks=malloc(sizeof(structstack_type));s->top=-1;s->num=s->array=malloc(sizeof(void*)*num);returns;}boolstack_is_empty(stack{returns->top==-}boolstack_is_full(stack{returns->top==s->num-}voidstack_push(stacks,void{s->array[++s->top]=}void*stack_pop(stack{returns->array[s->top--}voidstack_destroy(stacks,void(*free_key)(void{while{void*p=stack_pop(s);}}int{stacks=stack_create(10);for(inti=0;i<10;i++)int*p=*p=i;}printf("stackisfull?%s\n",stack_is_full(s)?"true":"false");while(!stack_is_empty(s)){int*p=stack_pop(s);printf("%d",*p);}printf("\n");return0;}#include<stdio.h>#include<stdlib.h>typedefstructstack_type*stack;structstack_node{voidstructstack_nodestructstack_typestructstack_nodevoidstack_node_ini(structstack_node*n,void{n->key=n->next=}stack{stacks=malloc(sizeof(structreturns;}boolstack_is_empty(stack{}voidstack_push(stacks,void{structstack_node*node=malloc(sizeof(structstack_node));stack_node_ini(node,x);s->head=node;}void*stack_pop(stack{structstack_node*p=s->head;s->head=s->head->next;return}voidstack_destroy(stacks,void(*free_key)(void{ {void*p=stack_pop(s);}}int{stacks=stack_create();for(inti=0;i<10;i++){int*p=*p=i;}while{int*p=stack_pop(s);printf("%d",*p);}printf("\n");return0;}#include<stdio.h>#include<stdlib.h>typedefstructqueue_type*queue;structqueue_type{intnum;inthead;inttail;voidqueuequeue_create(int{queueq=malloc(sizeof(structq->num=num+1;q->head=q->tail=q->array=malloc(sizeof(void*)*num);returnq;}boolqueue_is_empty(queue{returnq->head==q-}boolqueue_is_full(queue{returnq->head==(q->tail+1)%q-}voidqueue_en_queue(queueq,void{q->array[q->tail++]=q->tail=q->tail%q-}void*queue_de_queue(queue{q->head=q->head%q->num;returnx;}voidqueue_destroy(queueq,void(*free_key)(void{while(!queue_is_empty(q)){void*p=queue_de_queue(q);}}int{queueq=queue_create(10);for(inti=0;i<10;i++){int*p=*p=i;queue_en_queue(q,p);}printf("queueisfull?:%s\n",queue_is_full(q)?"true":"false");while(!queue_is_empty(q)){int*p=queue_de_queue(q);printf("%d",*p);}printf("\n");return0;}#include<stdio.h>#include<stdlib.h>typedefstructqueue_type*queue;structqueue_node{voidstructqueue_nodestructqueue_typestructqueue_node*head;structqueue_node*tail;voidqueue_node_ini(structqueue_node*node,void{node->key=key;}queue{queueq=malloc(sizeof(structqueue_type));q->head=NULL;returnq;}boolqueue_is_empty(queue{returnq->head==}voidqueue_en_queue(queueq,void{structqueue_node*p=malloc(sizeof(structqueue_node));queue_node_ini(p,x);if(q->head=={q->head=q->tail=}elseq->tail=p;}}void*queue_de_queue(queue{void*key=q->head->key;structqueue_node*p=q->head;q->head=q->head->next;free(p);returnkey;}voidqueue_destroy(queueq,void(*free_key)(void{while(!queue_is_empty(q)){void*p=queue_de_queue(q);}}int{queueq=queue_create();for(inti=0;i<10;i++)int*p=*p=i;queue_en_queue(q,p);}while(!queue_is_empty(q)){int*p=queue_de_queue(q);printf("%d",*p);}printf("\n");return0;}#include<stdio.h>#includetypedefstructlist_type*list;structlist_node{voidstructlist_nodestructlist_typestructlist_nodevoidlist_node_ini(structlist_node*p,void{p->key=p->next=}list{listl=malloc(sizeof(structlist_type*));l->head=NULL;return}voidlist_destroy(listl,void(*free_key)(void{structlist_node*x=l->head;while(x!=NULL){structlist_node*del=x;x=x->next;}}structlist_node*list_search(listl,voidint(*comp)(constvoid*,constvoid{structlist_node*x=l-while(x!=NULL&&comp(x->key,k)!={x=x-}return}voidlist_insert(listl,structlist_node{x->next=l-if(l->head!={l->head->prev=}l->head=x->prev=}voidlist_deleistl,structlist_node{if(x->prev!=NULL)x->prev->next=x-}elsel->head=x-}if(x->next!=NULL)x->next->prev=x-}}voidlist_display(listl,void(*print_key)(constvoid{structlist_node*x=l->head;while(x!=NULL){x=x->next;}}intcmp_int(constvoid*p1,constvoid{constint*pa=constint*pb=p2;if(*pa<*pb)return-1;if(*pa==returnreturn}voidprint_key(constvoid{constint*p=key;printf("%d",*p);}int{listl=for(inti=0;i<10;i++)structlist_node*n=malloc(sizeof(structlist_node));int*p=malloc(sizeof(int));*p=i;list_node_ini(n,p);list_insert(l,n);}list_display(l,print_key);intk=0;structlist_node*nodelist_search(l&kcmp_int);printf("查找关键字:%d的结果:%s\n",k,nodeNULL成功失败printf("删除关键字:%d的结果:\nk);list_dele,node);list_display(l,print_key);return0;}#include<stdio.h>#includetypedefstructlist_circle_type*list;struct{voidstructlist_nodestructlist_circle_typestructlist_node*nil;/*NULLvoidlis