软件技术基础实验上机整理

顺序表://定义#defineMAXNUMxxxtypedefstructlist_type_t{ elemtypedata[MAXNUM]; intlength;}list_type;list_typetable;//初始化顺序表list_type*init_table(){ list_type*table; table=(list_type*)malloc(sizeof(list_type)); returntable;}//创建顺序表并输入初始元素内容voidcreat_table(list_type*table){inti,elem;table->length=0;printf("pleaseinputdatasofthetable\n");for(i=0;i<MAXNUM;i++){ scanf("%d",&elem);if(elem==-1)break; table->data[i]=elem; table->length++;}}//将制定元素放入到顺序表的末尾，添加新元素intadd_table(table_t*table,intdata){if(table->length>=MAXNUM) return-1; table->data[table->length]=data; table->length++; return0;}//将指定元素插入到顺序表的指定位置之前intinsert_table(table_t*table,element_tdata,intlocation){ intj;location=location-1; if(location<0) return-1; else{ if(location>table->length) { location=table->length; table->data[location]=data; } else { for(j=table->length-1;j>=location;j--) table->data[j+1]=table->data[j]; table->data[location]=data; table->length++; } return0; }}//将指定元素插入到指定位置voidinsert_table(table_type*table,intlocation,intnew_node){ inti; if(table->length>=MAXNUM) printf("Thetableisfall.\n"); if(location<1||location>table->length+1) printf("Locationerror.\n"); for(i=table->length-1;i>=location-1;i--) table->data[i+1]=table->data[i]; table->data[i+1]=new_node; table->length++;}//将指定位置元素删除voiddelete_table(table_type*table,intlocation){ inti;if(table->length<1)Printf(it’sempty!); else{if(location<1||location>table->length) printf("Locationerror.\n"); else{for(i=location;i<=table->length;i++) table->data[i-1]=table->data[i]; table->length--;}}}//将顺序表的内容输出到屏幕上voidshow_table(table_type*table){ inti;printf("These%drecordsare:\n",table->length); if(table->length<=0) printf("It'sempty!"); for(i=0;i<table->length;i++) printf("%4d",table->data[i]); printf("\nThelengthofthetableis%d\n",table->length);}//实现顺序表在原表上反序voidchange_table(list_type*table){ inti; inttemp; for(i=0;i<table->length/2;i++) { temp=table->data[i]; table->data[i]=table->data[table->length-1-i]; table->data[table->length-1-i]=temp; }}//将指定元素按照从小到大顺序插入到顺序表中voidinsert_table_by_order(table_t*table,intdata){ intlocation,j; for(location=0;location<table->length;location++) { if(table->data[location]>data) break; } for(j=table->length-1;j>=location;j--) {table->data[j+1]=table->data[j]; } table->data[location]=data; table->length=table->length+1;}//删除顺序表中指定关键字的元素intdelete_table(table_t*table,intdata){ inti=0,j=0;for(i=0;i<table->length;i++) { if(table->data[i]==data) break; } if(i==table->length) return-1; for(j=i;j<table->length;j++)table->data[j]=table->data[j+1]; table->length--; return0; }//删除顺序表中小于某个指定值的所有元素voiddelete_table_below(table_t*table,intx){inti=0,j; while(i<table->length) {if(table->data[i]<x) {for(j=i;j<table->length;j++) table->data[j]=table->data[j+1];table->length--; }elsei++; }}//删除顺序表中所有的负数（一趟）voiddelete_negative(list_type*lp){ inti,j,n,temp; n=lp->length; for(i=j=0;i+j<n;) { if(lp->data[i]>=0) i++; if(lp->data[i+j]<0) { j++; lp->length--; if(lp->data[i+j]>=0&&i+j<n) { temp=lp->data[i+j]; lp->data[i+j]=lp->data[i]; lp->data[i]=temp; i++; }}}}//Main函数举例：将顺序表反序。voidmain(){ list_type*table; table=init_table(); creat_table(table); printf("\nBeforechange:\n"); showlist(table); change_table(table); printf("\nAfterchange:\n"); showlist(table);}链表：//定义链点typedefstructnode_type{intdata;structnode_type*next;}node_t;//定义链表typedefstructlink_type{node_t*head;node_t*tail;//很少用intlength;}link_t;//创建链表link_t*creat_link(){ link_t*link; node_t*new_node,*p; intdata,i; link=(link_t*)malloc(sizeof(link_t)); link->head=NULL; link->length=0; printf("请输入整数，输入0结束：\n"); scanf("%d",&data); while(1)//增加链点直到输入0结束{ if(data==0) break;new_node=(node_t*)malloc(sizeof(node_t)); new_node->data=data; new_node->next=NULL;if(link->length<=0) { link->head=new_node; } else { p=link->head; for(i=1;i<link->length;i++) p=p->next; p->next=new_node; } link->length++; scanf("%d",&data); } returnlink;}//创建链表(有表尾)link_t*creat_link(){ link_t*link; node_t*new_node; intdata; link=(link_t*)malloc(sizeof(link_t));//申请链表空间 link->head=NULL; link->tail=NULL; link->length=0; printf("请输入整数，输入0结束：\n"); scanf("%d",&data); while(1){ if(data==0) break;new_node=(node_t*)malloc(sizeof(node_t));//申请链点空间 new_node->data=data; new_node->next=NULL;if(link->length<=0) { link->head=new_node; link->tail=new_node; } else { link->tail->next=new_node; link->tail=new_node; } link->length++; scanf("%d",&data); } returnlink;}//查询元素位置intget_link(link_t*link,intgetdata){ intindex=1; node_t*p; p=link->head;while(p!=NULL) { if(p->data==getdata) break; p=p->next; index++; } if(p==NULL)//未查询到元素 return-1; returnindex;}//插入元素到表尾intadd_link(link_t*link,element_tdata){ inti=1;node_t*new_node; node_t*p; p=link->head;new_node=(node_t*)malloc(sizeof(node_t)); new_node->data=data; new_node->next=NULL; if(link->length<=0) { link->head=new_node; } else { while(i<link->length) { p=p->next;i++; } p->next=new_node; } link->length++; return0;}//插入元素到指定位置intinsert_link(link_t*link,element_tdata,intlocation){inti=2;node_t*new_node;node_t*p;new_node=(node_t*)malloc(sizeof(node_t));new_node->data=data;new_node->next=NULL;if(location>link->length) location=link->length+1;if(location==1){ new_node->next=link->head; link->head=new_node;}else{p=link->head; while(i<location&&p!=NULL) { p=p->next; i++; } new_node->next=p->next; p->next=new_node;}link->length++; return0;}//插入按从小到大顺序intinsert_link_by_order(link_t*link,element_tdata){intlocation=1;node_t*new_node;node_t*p,*last;new_node=(node_t*)malloc(sizeof(node_t));new_node->data=data;new_node->next=NULL;p=link->head;last=NULL;while(p->data<=data&&p!=NULL) { last=p; p=p->next; location++;}if(p==NULL) location=link->length+1;if(location==1){ new_node->next=link->head; link->head=new_node;}else{ new_node->next=last->next; last->next=new_node;}link->length++; return0;}//删除指定位置元素voiddelete_link(link_t*link,intindex){ node_t*p,*last,*temp; inti; p=link->head; if(index>link->length) printf("error!");if(index==1){ link->head=p->next; free(p);}else{ for(i=2;i<index;i++) p=p->next; //if(index==link->length) { temp=p->next; p->next=p->next->next; free(temp); link->tail=p; } else// { temp=p->next; p->next=p->next->next; free(temp); }}link->length--;}//删除指定关键字的元素intdelete_link(link_t*link,intdata){ node_t*p,*last,*temp; intlocation=1; p=link->head; last=NULL;while(1) { if(p->data==data&&p!=NULL) break; last=p; p=p->next; location++; }if(location>link->length) return-1;if(location==1){ link->head=p->next; free(p);}else{ temp=last->next; last->next=last->next->next; free(temp);}link->length--; return0;}//删除小于某个值的所有元素voiddelete_link_below(link_t*link,intx){ node_t*p,*last; p=link->head; last=NULL;while(p!=NULL) { if(p->data<x) {if(last==NULL) { link->head=p->next; free(p); p=link->head; }else { last->next=p->next; free(p); p=last->next; }link->length--; } else{ last=p; p=p->next; } } return;}//在屏幕上显示链表内容voidshow_link(link_t*link){ node_t*p; inti; p=link->head; for(i=1;i<=link->length;i++) { printf("%4d",p->data); p=p->next; }}//实现链表反向（有表尾）voidreverse_list(link_type*list){link_t*last,*current,*continue;last=NULL;current=list->header;continue=current;while(current!=NULL){ continue=current->next; current->next=last; last=current; current=continue;}list->tail=list->header;list->header=last;}//main函数举例voidmain(){ intorder; link_t*link; link=creat_link();delete_link_below(link); printf("\n删除负数后的链表为：\n"); show_link(link); printf("\n\n");free(link);}//双向链表//插入(p指向的是新链点的后一个链点)anew->next=p;p->prior->next=anew;anew->prior=p->prior;p->prior=anew;//删除(p在ai-1处，删除ai)p->next->next->prior=p;p->next=p->next->next;(p在ai处，删除ai)p-->prior->next=p->next;p->next->prior=p->prior;//创建双向链表link_t*creat_link(){ link_t*link; node_t*new_node; intdata; link=(link_t*)malloc(sizeof(link_t));//申请链表空间 link->head=NULL; link->tail=NULL; link->length=0; printf("请输入整数，输入0结束：\n"); scanf("%d",&data); while(1){ if(data==0) break;new_node=(node_t*)malloc(sizeof(node_t));//申请链点空间 new_node->data=data; new_node->next=NULL; new_node->last=NULL;if(link->length<=0) { link->head=new_node; link->tail=new_node; } else { link->tail->next=new_node; new_node->last=link->tail; link->tail=new_node; } link->length++; scanf("%d",&data); } returnlink;}//冒泡排序法从小到大交换链点（双向链表）voidsort_link(link_t*link){ node_t*p,*temp,*teil; teil=NULL; p=link->head; while(p!=teil) { while(p->next!=teil) { if(p->data>p->next->data)//交换 { if(p->last==NULL)//链表头的情况 { temp=p->next; temp->next->last=p; p->next=p->next->next; temp->next=p; temp->last=NULL; p->last=temp; link->head=temp; } else { if(p->next->next==NULL)//链表尾的情况 { temp=p->next; p->next=p->next->next; p->last->next=temp; temp->next=p; temp->last=p->last; p->last=temp; link->tail=temp; } else { temp=p->next; temp->next->last=p; p->next=p->next->next; p->last->next=temp; temp->next=p; temp->last=p->last; p->last=temp; } } } else//不交换 { p=p->next; } }//回到链表头开始下一轮比较 teil=p; p=link->head; }}//循环链表//定义链点typedefstructnode_type{intdata;structnode_type*next;}node_t;//定义链表typedefstructlink_type{node_t*tailintlength;}link_t;//创建循环链表voidcreate_list(list_type*table){ intdata; node_type*temp,*p; table->tail=NULL; table->length=0; table->tail=(node_type*)malloc(sizeof(node_type)); scanf("%d",&data);while(data!=0){ if(table->length==0) { table->tail->data=data; table->tail->next=table->tail; }else { temp=(node_type*)malloc(sizeof(node_type)); temp->data=data; p=table->tail; temp->next=table->tail->next; p->next=temp; table->tail=temp; } table->length++; scanf("%d",&data);}}//显示循环链表voidshow_list(list_type*table){ intcount; node_type*temp; count=1; temp=table->tail->next; while(count<=table->length) { printf("%d,",temp->data); count++; temp=temp->next; } printf("\n");}//插入循环链表voidinsert_list(list_type*table,intnew_node,intlocation){ intcount,i; node_type*new_nodep,*temp; new_nodep=create_node(new_node); count=1; temp=table->tail; if(location>table->length) { for(i=0;i<table->length;i++) temp=temp->next; new_nodep->next=temp->next; temp->next=new_nodep; table->tail=table->tail->next; } else{ while(count<location){ count++; temp=temp->next; } new_nodep->next=temp->next; temp->next=new_nodep; } table->length++; return;}//删除循环链表voiddelete_list(list_type*table,intlocation){ intcount; node_type*temp,*q; count=1; temp=table->tail; while(count<location-1&&temp->next!=NULL){ count++; temp=temp->next; } q=temp->next; temp->next=temp->next->next; free(q); table->length--;}//将两个循环链表相接temp=tail1->next;tail1->next=tail2->next;tail2->next=temp;数组栈//定义typedefstructstack_type{ elemtypedata[MAXNUM]; inttop;//栈顶元素上的新空间}stack_type;//入栈stack.data[stack.top]=new_one;stack.top=stack.top+1;//出栈stack.top=stack.top-1;out=stack.data[stack.top];//栈空stack.top==0;//栈满stack.top==MAXNUM//两个栈共用一个数组typedefstructstack_type{intdata[N]; inttop1; inttop2;}stack_t;//入栈1voidpush_stack1(stack_t*stack1,intnew_one){ if(stack1->data[stack1->top1]!=NULL) printf("栈已满！"); else{ stack1->data[stack1->top1]=new_one; stack1->top1++; }}//入栈2voidpush_stack2(stack_t*stack2,intnew_one){ if(stack2->data[stack2->top2-1]!=NULL) printf("栈已满！"); else{ stack2->top2--; stack2->data[stack2->top2]=new_one; }}intpop_stack1(stack_t*stack1)//出栈1{ intout;if(stack1->top1==0) { printf("栈空！");returnNULL; } else{ stack1->top1--; out=stack1->data[stack1->top1]; stack1->data[stack1->top1]=NULL; returnout; }}intpop_stack2(stack_t*stack2)//出栈2{ intout;if(stack2->top2==N) { printf("栈空！");returnNULL; } else{ out=stack2->data[stack2->top2]; stack2->data[stack2->top2]=NULL; stack2->top2++; returnout; }}voidmain(){ intnew1,new2,i,out=1; stack_t*stack; stack=(stack_t*)malloc(sizeof(stack_t)); for(i=0;i<N;i++) {stack->data[i]=NULL;} stack->top1=0; stack->top2=N;printf("向栈1输入4个数据结束："); for(i=1;i<=4;i++) { scanf("%d",&new1); push_stack1(stack,new1); }printf("向栈2输入2个数据结束："); for(i=1;i<=2;i++) { scanf("%d",&new2); push_stack2(stack,new2); }printf("向栈2输入1个数据："); scanf("%d",&new2); push_stack2(stack,new2);printf("\n从栈1出1个数据："); out=pop_stack1(stack); printf("%d",out);printf("\n向栈2输入1个数据："); scanf("%d",&new2); push_stack2(stack,new2);printf("\n栈1出栈："); out=pop_stack1(stack); while(out!=NULL) { printf("%2d",out); out=pop_stack1(stack); }printf("\n栈2出栈："); out=pop_stack2(stack); while(out!=NULL) { printf("%2d",out); out=pop_stack2(stack); }}链栈//定义链点typedefstructnode{ intdata; structnode*next;}node_type;//定义栈typedefstructlstack_type{ node_type*top; intlength;}lstack_type;//创建栈 stack_type*stack; stack=(stack_type*)malloc(sizeof(stack_type)); stack->length=0; stack->top=NULL; printf("请输入正数，以0结束："); scanf("%d",&data); while(data!=0) { push_stack(stack,data); scanf("%d",&data); }//新元素入栈voidpush_stack(stack_type*stack,intdata){ node_type*new_node; new_node=(node_type*)malloc(sizeof(node_type)); new_node->data=data; new_node->next=stack->top; stack->top=new_node; stack->length++;}//出栈node_type*pop_stack(stack_type*stack){ node_type*out; out=stack->top; if(out==NULL) returnNULL; stack->top=stack->top->next; stack->length--; returnout;}//显示栈的元素voidshow_stack(stack_type*stack){ node_type*p; inti; p=stack->top; for(i=1;i<=stack->length;i++) { printf("%3d",p->data); p=p->next; }}顺序队列//定义typedefstructqueue_type{ elemtypedata[MAXNUM]; intfront; intrear;}queue_type;//出队intdequeue(queue_type*queue){ intout; if(queue->rear==queue->front) { printf("队列空！"); returnNULL; } out=queue->data[queue->front]; queue->front=(queue->front+1)%N; returnout;}//入队voidenqueue(queue_type*queue,intdata){ if((queue->rear+1)%N==queue->front) printf("队列满！"); else{ queue->data[queue->rear]=data; queue->rear=(queue->rear+1)%N; }}//调用出队函数把队列q中的元素一一出队，如果是负数直接抛弃；//如果是正数，则调用入队函数，插入到q的队尾。voidaa(queue_type*q){ inti,data,num; if(q->rear<q->front) num=q->rear+N-q->front; else num=q->rear-q->front; for(i=0;i<num;i++) { data=dequeue(q); if(data<0) {} if(data>0) { enqueue(q,data); } }}//显示队列元素voidshow_queue(queue_type*queue){ inti,tail; if(queue->rear<queue->front) tail=queue->rear+N; elsetail=queue->rear; for(i=queue->front;i<tail;i++) printf("%3d",queue->data[i%N]);}//main函数举例voidmain(){ queue_type*queue; intshuju[10]={2,3,-4,6,-5,8,-9,7,-10,20}; inti; queue=(queue_type*)malloc(sizeof(queue_type)); queue->front=0; queue->rear=0; for(i=0;i<10;i++) enqueue(queue,shuju[i]); printf("原队列：\n"); show_queue(queue); aa(queue); printf("\n现队列：\n"); show_queue(queue);}//front和rear可重叠有标识tagtypedefstructqueue_type{ intdata[N]; intfront; intrear; inttag;}queue_t;//入队voidenqueue(queue_t*queue,intnew_one){ if(queue->front==queue->rear) { if(queue->tag==1) { printf("队列已满！\n"); return;//队列满了 } } queue->data[queue->rear]=new_one; queue->rear=(queue->rear+1)%N; printf("入队成功！\n"); //插入新元素，看看要不要设置队满状态 if(queue->front==queue->rear) { queue->tag=1; }}//出队intdequeue(queue_t*queue){ intout; if(queue->front==queue->rear) { if(queue->tag==0) { printf("队列已空！\n"); return0;//队列空了 } } out=queue->data[queue->front]; queue->front=(queue->front+1)%N; printf("出队成功！\n"); //出元素，看看要不要设置队空状态 if(queue->front==queue->rear) { queue->tag=0; } returnout;}voidmain(){ intnew_one,i,out,choose; queue_t*queue; queue=(queue_t*)malloc(sizeof(queue_t)); queue->tag=0; queue->front=0; queue->rear=0; printf("请选择：\n1、入队\n2、出队\n3、quit"); while(1) { printf("请选择："); scanf("%d",&choose); if(choose==1) { printf("请输入数据："); scanf("%d",&new_one); enqueue(queue,new_one); } elseif(choose==2) dequeue(queue); elsebreak; }}链表队列//定义typedefstructlqueue_type{ node_type*front; node_type*rear; intlength;}//入队new_node->next=NULL;list->rear->next=new_node;list->rear=new_node;if(list->front==NULL){ list->front=new_node;

}//出队temp=list->front;list->front=list->front->next；if(list->front==NULL){ list->rear=NULL;}free(temp);二叉树//定义链点typedefstructtnode_type{ elemtypedata; structtnode_type*Lchild; structtnode_type*Rchild;}tnode_type;//定义二叉树typedefstructtree_type{ tnode_type*root; intnum;}tree_type;//创建并初始化树tree_t*creat_tree(){ tree_t*tree=NULL; tree=(tree_t*)malloc(sizeof(tree_t));tree->root=NULL; tree->num=0; returntree;}//悬空法创建树tnode_type*create_tree(){intx; tnode_type*p; scanf(“%d”,&x); if(x==0)//0表示该指针为0 returnNULL; p=create_node(x); p->Lchild=create_tree(); p->Rchild=create_tree(); returnp;}voidmain（）{tree_type*tree;tree->root=create_tree();}//脚踏实地的建立voidcrt_preorder(root){read(&ch),temp=NULL;if(ch!=0){//0代表该指针为空停止temp=create_node(ch);}root->Lchild=temp;if(root->Lchild!=NULL) crt_preorder(root->Lchild);read(&ch),temp=NULL;if(ch!=0){temp=create_node(ch);}root->Rchild=temp;if(root->Rchild!=NULL) crt_preorder(root->Rchild);}voidcreate_tree(tree){intx; tnode_type*p; scanf(“%d”,&x);if(x==0){//0代表空停止 tree=NULL; return;}p=create_node(x);tree->root=p;crt_preorder（tree->root）;}//排序树的建立（插入新元素）intinsert_BS_tree(tree_t*tree,intdata){tnode_t*new_node,*temp,*last; temp=tree->root; last=NULL; new_node=(tnode_t*)malloc(sizeof(tnode_t)); new_node->data=data; new_node->Lchild=NULL; new_node->Rchild=NULL; if(tree->num==0) { tree->root=new_node; tree->num++; } else { while(temp!=NULL) { if(data>=(temp->data)) { last=temp;temp=temp->Rchild; } else { last=temp;temp=temp->Lchild; } } if(data>=(last->data))last->Rchild=new_node; else {last->Lchild=new_node; }tree->num++; } return0;}//中序遍历voidinorder_tree(tnode_t*root){ if(root->Lchild!=NULL) inorder_tree(root->Lchild);ShowElement(root->data); if(root->Rchild!=NULL) inorder_tree(root->Rchild); return;}//先序遍历voidpreorder_tree(tnode_t*root){ ShowElement(root->data); if(root->Lchild!=NULL) preorder_tree(root->Lchild); if(root->Rchild!=NULL) preorder_tree(root->Rchild); return;}//后序遍历voidpostorder_tree(tnode_t*root){ if(root->Lchild!=NULL) postorder_tree(root->Lchild); if(root->Rchild!=NULL) postorder_tree(root->Rchild);ShowElement(root->data);} //查询指定关键字tnode_t*get_element_tree(tnode_t*root,doublestuID){ tnode_t*ret=NULL; tnode_t*temp1=NULL,*temp2=NULL; if(stuID==root->data.stuID) { ret=root; returnret; } if(root->Lchild!=NULL) temp1=get_element_tree(root->Lchild,stuID); if(root->Rchild!=NULL) temp2=get_element_tree(root->Rchild,stuID);if(temp1!=NULL) returntemp1; elseif(temp2!=NULL) returntemp2; else returnNULL;}//求树的深度intdeep_tree(tnode_t*root){ intdeep1=0,deep2=0; if(root->Lchild==NULL&&root->Rchild==NULL) return1; if(root->Lchild!=NULL) deep1=deep_tree(root->Lchild); if(root->Rchild!=NULL) deep2=deep_tree(root->Rchild); returndeep1>deep2?(deep1+1):(deep2+1);}//树的反序（交换左右子树）voidswap_tree(tnode_t*root){ tnode_t*temp; temp=root->Lchild; root->Lchild=root->Rchild; root->Rchild=temp; if(root->Lchild!=NULL) swap_tree(root->Lchild); if(root->Rchild!=NULL) swap_tree(root->Rchild); return;}//求树的叶节点的个数intleaf_num(tnode_type*root){tnode_type*p;intnum=0;p=root;if(p->Lchild==NULL&&p->Rchild==NULL) return(num+1);else{ if(p->Lchild!=NULL) num=leaf_num(p->Lchild)+num; if(p->Rchild!=NULL) num=leaf_num(p->Rchild)+num;}returnnum;}图的存储//图存储二维数组邻接矩阵定义typedefstructgraph_m{ elemtypenode[MAXNUM]; intarcs[MAXNUM][MAXNUM];}graph_m;//邻接表定义//头结点typedefstructheadnode{ intnode_index; elemtypedata; structadj_node*next_adj;}headnode;//邻接结点typedefstructadj_node{ intnode_index; structadj_node*next_adj;}adj_node;//邻接表typedefstructgraph_l{ headnodenode_list[MAXNUM]; intnode_num;}graph_l;检索//顺序查找intsq_search(table_t*table,intkey){ inti=0; while(i<table->length) { if(table->data[i]==key) break; i++; } if(i<table->length) returni; else { return-1; }}//二分法查找intbin_search(table_t*table,intkey){ intlow,high,mid; low=0; high=table->length-1; while(low<high) { mid=(low+high)/2; if(table->data[mid]==key) break; elseif(table->data[mid]<key) low=mid+1; elsehigh=mid-1; } if(low<high) returnmid; else { return-1; }}//main函数举例voidmain(){ inti,a[]={3,10,13,17,40,43,50,70}; intnum1,num2,loc1,loc2; table_t*table; table=(table_t*)malloc(sizeof(table_t)); table->length=0; for(i=0;i<8;i++) { table->data[i]=a[i]; table->length++; } num1=43; num2=5; loc1=sq_search(table,num1); loc2=sq_search(table,num2); printf("Thisisfromsequentialsearch:\n"); if(loc1>=0) printf("Thelocationfor43is%d\n",loc1); else printf("Theloctionfor43isNOTFIND\n"); if(loc2>=0) printf("Thelocationfor5is%d\n",loc2); else printf("Theloctionfor5isNOTFIND\n");}排序//简单选择法voidselect_sort(table_t*table){ intj,i,head,min,temp; head=0; while(head<table->length) { j=head; min=j; while(j<table->length) { if(table->data[j]<table->data[min]) min=j; j++; } temp=table->data[head];table->data[head]= table->data[min]; table->data[min]=temp; head=head+1; for(i=0;i<table->length;i++) printf("%4d",table->data[i]); printf("\n"); }}//冒泡排序法voidbubble_sort(table_t*table){ intturn,flag,i,j,temp; for(turn=table->length-1;turn>0;turn--) { flag=0; for(i=0;i<turn;i++) if(table->data[i]>table->data[i+1]) { temp=table->data[i]; table->data[i]=table->data[i+1]; table->data[i+1]=temp; flag=1; } if(flag==0) break; for(j=0;j<table->length;j++) printf("%4d",table->data[j]); printf("\n"); }}//直接插入法voidinsert_sort(table_t*table){ inttail,temp,j,i; tail=1;while(tail<table->length){ temp=table->data[tail];j=tail-1;while(j>-1){ if(temp<table->data[j]) table->data[j+1]=table->data[j]; else break; j--;}table->data[j+1]=temp; for(i=0;i<table->length;i++) printf("%4d",table->data[i]); printf("\n");tail=tail+1;}}//快速排序法voidquick_sort(table_t*table,intlow,inthigh){ inti,front,last,temp; front=low; low=low+1; last=high; if(low>=high) return; while(low<high) { while(table->data[high]>table->data[front]&&low<high) high--; while(table->data[low]<table->data[front]&&low<high) low++; if(low<high) { temp=table->data[low]; table->data[low]=table->data[high]; table->data[high]=temp; } } if(table->data[high]<table->data[front]) { temp=table->data[high]; table->data[high]=table->data[front]; table->data[front]=temp; } elsehigh--; for(i=0;i<table->length;i++) printf("%4d",table->data[i]); printf("\n"); quick_sort(table,front,high-1); quick_sort(table,high+1,last);}//main函数举例voidmain(){ inta[]={513,87,512,61,908,170,897,275,653,462}; inti; table_t*table; table=(table_t*)malloc(sizeof(table_t)); table->length=0; for(i=0;i<10;i++) { table->data[i]=a[i]; table->length++; } printf("selectsort:\n"); select_sort(table); table->length=0; for(i=0;i<10;i++) { table->data[i]=a[i]; table->length++; } printf("bubblesort:\n"); bubble_sort(table); table->length=0; for(i=0;i<10;i++) { table->data[i]=a[i]; table->length++; } printf("insertsort:\n"); insert_sort(table); table->length=0; for(i=0;i<10;i++) { table->data[i]=a[i]; table->length++; } printf("quicksort:\n"); quick_sort(table,0,9);}十一、拓展//哈希算法例程#include<stdio.h>#include<malloc.h>#include<string.h>#defineHASH_LEN30//哈希表的长度#defineM30#defineNAME_NO30//人名的个数typedefstructNAME{char*py;//名字的拼音intk;//拼音所对应的整数}NAME;NAMENameList[HASH_LEN];typedefstructhterm//哈希表{char*py;//名字的拼音intk;//拼音所对应的整数intsi;//查找长度}HASH;HASHHashList[HASH_LEN];/*姓名（结构体数组）初始化*/voidInitNameList(){inti;char*f;intr,s0;NameList[0].py="陈红秀";NameList[1].py="罗瑞智";for(i=0;i<NAME_NO;i++)//*求出各个姓名的拼音所对应的整数{s0=0;f=NameList[i].py;for(r=0;*(f+r)!='\0';r++)//方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字s0=*(f+r)+s0;NameList[i].k=-s0;}}/*建立哈希表*/voidCreateHashList(){inti;for(i=0;i<HASH_LEN;i++)//哈希表的初始化{HashList[i].py="";HashList[i].k=0;HashList[i].si=0;}for(i=0;i<NAME_NO;){intsum=0;intadr=(NameList[i].k)%M;//哈希函数intd=adr;if(HashList[adr].si==0)//如果不冲突{HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else//冲突{do{d=(d+1)%30;//伪散列sum=sum+1;//查找次数加1}while(HashList[d].k!=0);HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1;}i++;}}/*查找*/voidFindList(){intr;charname[20]={0};ints0=0;intsum=1;intadr;intd;printf("\n\n请输入姓名：");//输入姓名scanf("%s",name);for(r=0;*(name+r)!='\0';r++)//求出姓名的拼音所对应的整数(关键字)s0=*(name+r)+s0;s0=-s0;adr=(s0)%M;//使用哈希函数d=adr;if(HashList[adr].k==s0)//分3种情况进行判断printf("\n姓名:%s关键字:%d查找长度为:1",HashList[d].py,s0);elseif(HashList[adr].k==0)printf("无该记录!");else{intg=0;do{d=(d+1)%M;//伪散列sum=sum+1;if(HashList[d].k==0||sum==30){printf("无记录!");g=1;}if(HashList[d].k==s0){printf("\n姓名:%s关键字:%d查找长度为:%d",HashList[d].py,s0,sum);g=1;}}while(g==0);}}voidmain(){intchoise;printf("\n哈希表的建立和查找");InitNameList();CreateHashList();while(1){printf("\n\n");printf("1.查找\n");printf("2.退出\n");scanf("%d",&choise);if(choise==1)FindList();elseif(choise==2)break;else{printf("\n请输入正确的选择!");}}}//哈希链地址法例程typedefstructchainnode{intkey;intdata;structchain*next;}chainnode;#defineHashmod12chainnode*tabl