2016年事業(yè)單位招聘計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)算法筆記

2016年事業(yè)單位招聘計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)算法筆記、數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)1、排序算法集錦1、直接插入排序：代碼：//插入排序。//時間復(fù)雜度：0(口)。空間復(fù)雜度：0(1)。為穩(wěn)定排序。#include<stdio.h>#include<stdlib.h>voidInsertSort(inta[],intn){//對順序表做直接插入排序。intj,k;for(j=2;j<=n;j++)if(a[j]<a[j-1]){//<，需將其插入順序表。a[0]=a[j];//復(fù)制為哨兵。a[j]=a[j-1];for(k=j-2;a[0]<a[k];k--)a[k+1]=a[k];//記錄后移。a[k+1]=a[0];//插入到正確位置。))intmain(){inta[100],n,i;printf(”請輸入要進(jìn)行排序的數(shù)的個數(shù)n:\n");scanf("%d",&n);printf("請輸入這n個數(shù):\n");for(i=1;i<=n;i++)scanf("%d”,&a[i]);InsertSort(a,n);printf("排序后的n個數(shù)是：\n");for(i=1;i<=n;i++)printf("%4d",a[i]);printf("\n");system("pause");)數(shù)據(jù)測試：■3C:\U■3C:\Uqers\xiajun\Des 入排序,日乂日標(biāo)輸入這n個數(shù):32154附序后的n個數(shù)是：1 2 3 4 5意鍵繼續(xù).2、折半插入排序代碼：〃折半插入排序。//時間復(fù)雜度：0(口)。空間復(fù)雜度：0(1);#include<stdio.h>#include<stdlib.h>voidBInsertSort(inta[],intn){//對順序表做折半插入排序。intj,k;for(j=2;j<n;j++){a[0]=a[j];intlow=1,high=j-1;while(low<=high){〃在a[low..high]中折半查找正確插入位置。intm=(low+high)/2;if(a[0]<a[m])high=m-1;elselow二m+1;)for(k二j-1;k>=high+1;k--)//記錄后移。a[k+1]=a[k];a[high+1]=a[0];//插入。))intmain(){inta[100],n,i;printf(”請輸入要進(jìn)行排序的數(shù)的個數(shù)n:\n");scanf("%d",&n);printf("請輸入這n個數(shù):\n");for(i=1;i<=n;i++)scanf("%d”,&a[i]);BInsertSort(a,n);printf("排序后的n個數(shù)是：\n");for(i=1;i<=n;i++)printf("%4d",a[i]);printf("\n");system("pause");)數(shù)據(jù)測試:3、希爾排序：代碼：//希爾排序。//時間復(fù)雜度：0(口1。8口)?？臻g復(fù)雜度：0(1)。為不穩(wěn)定算法。#inc1ude<stdio.h>#inc1ude<std1ib.h>voidShellInsert(inta[],intn,intdk){〃對順序表a[]做一趟希爾插入排序。intj,k;for(j=dk+1;j<=n;j++)if(a[j]<a[j-dk]){a[0]=a[j];for(k=j-dk;k>0&&a[0]<a[k];k-=dk)a[k+dk]=a[k];a[k+dk]=a[0];))voidShellSort(inta[],intn,intdlta[],int。{//按增量序列dlta口對順序表做希爾排序。intm;for(m=0;m<t;m++)ShellInsert(a,n,dlta[m]);)intmain(){inta[100],dlta[20],n,t,i;printf(”請輸入要進(jìn)行排序的數(shù)的個數(shù)n:\n");scanf("%d",&n);printf("請輸入這n個數(shù):\n");for(i=1;i<=n;i++)scanf("%d”,&a[i]);printf(”請輸入增量序列數(shù)的個數(shù)t:\n");scanf("%d",&t);printf(”請輸入增量序列:\n");for(i=0;i<t;i++)scanf("%d”,&dlta[i]);ShellSort(a,n,dlta,t);printf("排序后的n個數(shù)是：\n");for(i=1;i<=n;i++)printf("%4d",a[i]);printf("\n");system("pause");)數(shù)據(jù)測試：4、冒泡排序代碼：//起泡排序。//時間復(fù)雜度：0(口人2)?？臻g復(fù)雜度：0(1)。為穩(wěn)定排序算法。#include<stdio.h>#include<stdlib.h>voidBubbleSort(inta[],intn){inti,j,temp;for(i=1;i<=n-1;i++){for(j=1;j<=n-i;j++){if(a[j]>a[j+1]){temp二a[j];a[j]=a[j+1];a[j+1]=temp;)intmain(){inta[100],n,i;printf(”請輸入要進(jìn)行排序的數(shù)的個數(shù)n:\n");scanf("%d",&n);printf("請輸入這n個數(shù):\n");for(i=1;i<=n;i++)//注意數(shù)組的起始位置。scanf("%d”,&a[i]);BubbleSort(a,n);printf("排序后的n個數(shù)是：\n");for(i=1;i<=n;i++)printf("%4d",a[i]);printf("\n");system("pause");)數(shù)據(jù)測試:5、快速排序:代碼：//快速排序。//時間復(fù)雜度：。(口匕8口八空間復(fù)雜度：O(logn)。為不穩(wěn)定算法。#include<stdio.h>#include<stdlib.h>intPartition(inta[],intn,intlow,inthigh){//返回樞軸所在位置。intpivotkey;a[0]=a[low];pivotkey=a[low];while(low<high){while(low<high&&a[high]>pivotkey)high--;a[low]=a[high];while(low<high&&a[low]<pivotkey)low++;a[high]=a[low];)a[low]=a[0];returnlow;)voidQuickSort(inta[],intn,intlow,inthigh){//遞歸形式快排。intpivotloc;if(low<high){pivotloc二Partition(a,n,low,high);QuickSort(a,n,low,pivotloc-1);QuickSort(a,n,pivotloc+1,high);))intmain(){inta[100],n,i;printf(”請輸入要進(jìn)行排序的數(shù)的個數(shù)n:\n");scanf("%d",&n);printf("請輸入這n個數(shù):\n");for(i=1;i<=n;i++)//注意數(shù)組的起始位置。scanf("%d”,&a[i]);QuickSort(a,n,1,n);printf("排序后的n個數(shù)是：\n");for(i=1;i<=n;i++)printf("%4d",a[i]);printf("\n");system("pause");)數(shù)據(jù)測試：6、簡單選擇排序代碼：〃簡單選擇排序。//時間復(fù)雜度：0(口人2)?？臻g復(fù)雜度：0(1)#include<stdio.h>#include<stdlib.h>intSelectMinKey(inta[],intn,inti){intj,min;min=i;for(j=i+1;j<=n;j++){if(a[j]<a[min])min=j;)returnmin;)voidSelectSort(inta[],intn){inti,j,temp;for(i=1;i<n;i++){j=SelectMinKey(a,n,i);if(i!=j){temp二a[i];a[i]=a[j];a[j]=temp;)))intmain(){inta[100],n,i;printf(”請輸入要進(jìn)行排序的數(shù)的個數(shù)n:\n");scanf("%d",&n);printf("請輸入這n個數(shù):\n");for(i=1;i<=n;i++)//注意數(shù)組的起始位置。scanf("%d”,&a[i]);SelectSort(a,n);printf("排序后的n個數(shù)是：\n");for(i=1;i<=n;i++)printf("%4d",a[i]);printf("\n");system("pause");)數(shù)據(jù)測試：7、堆排序代碼；數(shù)據(jù)測試：8、歸并排序代碼：//歸并排序。//時間復(fù)雜度：0(口1。8口)。空間復(fù)雜度：O(n)。#inc1ude<stdio.h>#inc1ude<std1ib.h>voidMerge(intSR[],intTR[],intn,inti,intm,intt){〃將有序的a[i..m]ffa[m+1..t]合并為有序的TR[i..t]。intj,k;for(j=m+1,k=i;i<=m&&j<=t;k++){if(SR[i]<=SR[j])TR[k]=SR[i++];elseTR[k]=SR[j++];)if(i<=m)while(i<=m)TR[k++]=SR[i++];if(j<=t)while(j<=t)TR[k++]=SR[j++];)voidMSort(intSR[],intTR[],intn,ints,intt){〃將SR[s..t]歸并排序?yàn)門R[s..t]。intm,TR1[100];if(s==t)TR[s]=SR[s];else(m=(s+t)/2;MSort(SR,TR1,n,s,m);//遞歸地將SR[s..m]歸并為有序的TR1[s..m]。MSort(SR,TR1,n,m+1,t);//遞歸地將SR[m+1..t]歸并為有序的TR1[m+1..t]。Merge(TR1,TR,n,s,m,t);//將TR1[s..m]、TR1[m+1..t]歸并至UTR1[s..t];))voidMergeSort(inta[],intn){MSort(a,a,n,1,n);)intmain(){inta[100],n,i;printf(”請輸入要進(jìn)行排序的數(shù)的個數(shù)n:\n");scanf("%d",&n);printf("請輸入這n個數(shù):\n");for(i=1;i<=n;i++)//注意數(shù)組的起始位置。scanf("%d”,&a[i]);MergeSort(a,n);printf("排序后的n個數(shù)是：\n");for(i=1;i<=n;i++)printf("%4d",a[i]);printf("\n");system("pause");)數(shù)據(jù)測試：2、鏈表與數(shù)組1、假定數(shù)組A[N]的n個元素中有多個零元素，編寫算法將A中所有的非零元素依次移到A的前端?！救A中科技大學(xué)，06年】代碼：#include<stdio.h>#include<stdlib.h>intmain(){inta[100],n,i;while(1){printf("pleaseinputthenumberofthearray:\n");scanf("%d",&n);printf("pleaseinputeveryvalueinthearray:\n");for(i=0;i<n;i++)scanf("%d”,&a[i]);intp=-1,q=0,m=0;for(i=0;i<n;i++)if(a[i]==0){if(!q)p=i;//p記錄第一個零元素的位置。q++;//q記錄已經(jīng)遍歷到的零元素的個數(shù)。m++;)else{if(p>0&&q>0){a[p]=a[i];//移動非零元素至前面。//a[i]=0;q--;//零元素個數(shù)減1。if(q>0)p++;)elseif(m>0)a[i-m]=a[i];)printf("thevaluesafterremoving:\n");for(i=0;i<n;i++)printf("%4d",a[i]);printf("\n");)system("pause");)數(shù)據(jù)測試：2、順序存儲的線性表，其數(shù)據(jù)元素為整型，試編寫一算法，將A拆分成B和C兩個表，使A中的元素值大于等于0的存入B，小于0的存入C中。要求：(1)表B和C另外設(shè)置存儲空間。⑵表B和C不另外設(shè)置，而利用A的空間。(1)代碼：#include<stdio.h>#include<stdlib.h>intmain(){intA[10]={1,2,3,-4,-7,5,7,-9,8,-2};intB[10],C[10];inti,j,k;i=j=k=0;for(i=0;i<10;i++)if(A[i]>=0)B[j++]=A[i];elseC[k++]=A[i];printf("拆分前：\n");printf("A:");for(i=0;i<10;i++)printf("%4d",A[i]);printf("\n");printf("拆分后：\n");printf("B:");for(i=0;i<j;i++)printf("%4d",B[i]);printf("\n");printf("C:");for(i=0;i<k;i++)printf("%4d",C[i]);printf("\n");system("pause");)數(shù)據(jù)測試：⑵代碼：#include<stdio.h>#include<stdlib.h>intmain(){intA[10]={1,2,3,-4,-7,5,7,-9,8,-2};inti=0,j=9,temp,t=0;printf("拆分前：\n");printf("A:");for(t=0;t<10;t++)printf("%4d",A[t]);printf("\n");while(i<=j){while(A[i]>=0)i++;while(A[j]<0)j--;if(i<j){temp二A[i];A[i]=A[j];A[j]=temp;}}printf("拆分后：\n");printf("B:");for(t=0;t<i-1;t++)printf("%4d",A[t]);printf("\n");printf("C:");for(t=i;t<9;t++)printf("%4d",A[t]);printf("\n");system("pause");)數(shù)據(jù)測試：3、逆置單鏈表無頭節(jié)點(diǎn)單鏈表，節(jié)點(diǎn)：數(shù)據(jù)域data、指針域next,表頭指針h。通過遍歷鏈表，將所有的指針方向逆轉(zhuǎn)，其中表頭指針指向最后一個節(jié)點(diǎn)。算法：voidInverse(&h){if(h==null)return;p=h->next;pr=null;while(p){h->next=pr;pr=h;h=p;p=p->next;))4、刪除順序表中元素長度為n的線性表A采用順序存儲方式，寫算法刪除線性表中所有值為item的數(shù)據(jù)元素。要求：時間復(fù)雜度為。(口)，空間復(fù)雜度為0(1)。5、將數(shù)組偶數(shù)移至奇數(shù)之前設(shè)計(jì)將數(shù)組A[n]中所有的偶數(shù)移到奇數(shù)之前的算法。要求：不增加存儲空間，且時間復(fù)雜度為0(n)。代碼：#include<stdio.h>#include<stdlib.h>intmain(){intA[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};inti,j,x;//x=A[0];i=0;j=19;while(i<j){x=A[i];while(A[j]%2==1)j--;if(i<j){A[i]=A[j];i++;}if(i<j)while(A[i]%2==0)i++;if(i<j){A[j]=A[i];j-;}A[i]=x;}for(i=0;i<20;i++)printf("%d",A[i]);printf("\n");system("pause");}數(shù)據(jù)測試：6、逆序輸出單鏈表各元素代碼：#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}list;typedeflist*link;linkCreate(){//創(chuàng)建鏈表。charch;list*p;linkhead;head=NULL;ch=getchar();while(ch!='\n'){p=(list*)malloc(sizeof(list));p->data=ch;p->next二head;head=p;ch=getchar();)returnhead;)voidDisplay(linkhead){list*p;p=head;printf("頭插法建立的鏈表的輸出結(jié)果:\n");while(p){printf("%c”,p->data);p=p->next;)intmain(){linkhead;printf("請輸入鏈表的內(nèi)容:\n");head=Create();Display(head);system("pause");)數(shù)據(jù)測試：7、合并兩個單鏈表(I)A為遞增有序的單鏈表，長度為n。B為遞減有序的單鏈表，長度為m。編寫程序，利用原表的存儲空間，將A、B合并成為一個遞增有序的單鏈表。要求：時間復(fù)雜度為O(m+n)。算法：//先將單鏈表B逆轉(zhuǎn)：voidReverse(Node*r){Node*q=r,*p=null,*temp;while(q){temp=q;q=q->next;temp->next=p;p=temp;)r=p;)〃再合并兩個非遞減的單鏈表：Node*Merge(Node*a,Node*b){Node*s,*r;Node*p=a,*q二b;while(p!=NULL&&q!=NULL){if(p->data<q->data){if(p==a){s=a;r=a;)elser->next=p;p=p->next;)else{if(q==b){s=b;r=b;)elser->next=q;q=q->next;)r=r->next;)if(p==NULL&&q!=NULL)r->next=q;if(q==NULL&&p!=NULL)r->next=p;returns;)//主方法。合并題目所給的兩個單鏈表。Node*MergeFunc(Node*a,Node*b){Reverse(b);Node*result二Merge(a,b);resultresult;)8、合并兩個單鏈表(II)單鏈表A、B,數(shù)據(jù)都為整型有序，編寫程序，利用原節(jié)點(diǎn)，將A和B中具有相同數(shù)據(jù)的節(jié)點(diǎn)刪除，并將B中與原A表不同數(shù)據(jù)的節(jié)點(diǎn)插入A中，保持A的遞增有序。算法：voidMerge(Node*a,Node*b){Node*p,*q,*previous;Node*temp1,*temp2;//假設(shè)a、b帶頭節(jié)點(diǎn)。p=a->next;q=b->next;previous=a;while(p!=NULL&&q!=NULL){if(p->data<q->data){previous=p;//previous指示p的前驅(qū)。p=p->next;)elseif(p->data==q->data){temp1=p;p=p->next;previous->next=p->next;deletetemp;)else{temp2=q;q=q->next;previous->next二temp;temp->next=p;previous二previous->next;))if(p==NULL&&q!=NULL)previous->next=q;)9、兩個單鏈表求n和u已知2個按元素非遞減的單鏈表A和B,設(shè)計(jì)一算法利用原表節(jié)點(diǎn)空間形成連續(xù)的新鏈表A和B’，使得A'=AUB,B’=AAB。算法：voidAdjust(LinkList&A,LinkList&B){//假設(shè)A、B帶頭結(jié)點(diǎn)。pa=A;pb=B;while(pa->next!=NULL&&pb->next!=NULL){if(pa->next->data<pb->next->data)pa=pa->next;elseif(pa->next->data==pb->next->data){pa=pa->next;pb=pb->next;)else{temp二pb->next;pb->next=temp->next;temp->next=pa->next;pa->next二temp;pa=temp;)if(pb->next){pb->next=pa->next;pa->next二NULL;))3、棧1、Ackermann函數(shù)遞歸與非遞歸實(shí)現(xiàn)Ackermann函數(shù)定義如下：Ack(m,n)=n+1，當(dāng)m=0時；Ach(m,n)=Ack(m-1,1),當(dāng)m!=0,n=0時；Ack(m,n)=Ack(m-1,Ack(m,n-1))，當(dāng)m!=0,n!=0時。寫出Ack(m,n)的非遞歸算法。算法：//棧非遞歸實(shí)現(xiàn)Ackermann函數(shù)。intAck(m,n){inti,j;if(m==0)returnn+1;push(m);push(n);while(StackNoEmpty()){i=pop();if(!StackNoEmpty())returni;elsej=pop();if(j=0)push(i+1);elseif(i==0){push(j-1);push(1);)else{push(j-1);push(j);push(i-1);2、順序棧的基本操作實(shí)現(xiàn)代碼：//順序棧的基本操作實(shí)現(xiàn)#include<stdio.h>#include<stdlib.h>#defineMaxLen100typedefstruct{intdata[MaxLen];inttop;}stack;//數(shù)據(jù)結(jié)構(gòu)定義。voidinit(stack*st){st->top=0;}voidpush(stack*st,int乂){〃入棧。if(st->top==MaxLen){printf("Error:Bufferoverflowed!\n");}else{st->top++;st->data[st->top]=x;}}intpop(stack*st){//出棧。if(!st->top)printf("Error:thestackisempty!\npopoperationfailed!\n");returnst->data[st->top--];}intStackEmpty(stack*st){〃判斷棧為空。if(st->top==0)return1;elsereturn0;}intgetTop(stack*st){//獲取棧頂?shù)脑刂?。if(st->top==0)return0;elsereturnst->data[st->top];}voiddisplay(stack*st){//輸出棧中的元素。for(inti=st->top;i>0;i--)printf("%4d”,st->data[i]);printf("\n");}intmain(){stackst;intn,i,e,f,g,select;init(&st);printf("pleaseenterthelengthofthestack:");scanf("%d",&n);for(i=1;i<=n;i++){printf("the%dthvalueofthestack:",i);scanf("%d",&e);push(&st,e);)while(1){printf("select1:display()\n");printf("select2:push()\n");printf("select3:pop()\n");printf("select4:gettop()\n");printf("inputayourselect(1-4):\n");prints按0退出程序！\n");scanf("%d",&select);switch(select){case0:exit(1);{display(&st);break;){printf("pleaseinputthevaluethatyouwanttopush:");scanf("%d",&f);push(&st,f);printf("thestackafterpushingis:");display(&st);break;){g=pop(&st);printf("thevaluethatarepopedis%d\n",g);printf("thestackafterpopingis:\n");display(&st);break;){printf("thevalueofthetopofthestackis%d:\n",getTop(&st));break;))system("pause");)數(shù)據(jù)測試：3、前綴表達(dá)式計(jì)算算法利用一個棧，從左到右，邊掃描邊求值。⑴從左到右掃描前綴表達(dá)式：a、遇到運(yùn)算符，則運(yùn)算符入棧，轉(zhuǎn)到(1)；b、遇到操作數(shù)，如果棧為空，則將該操作數(shù)返回，退出；如果棧不空：bl、當(dāng)棧頂是一個運(yùn)算符時，將該操作數(shù)入棧。轉(zhuǎn)到(1)；b2、當(dāng)棧頂是一個操作數(shù)時，兩次取棧頂(第二次取得的應(yīng)該是運(yùn)算符)，并按照運(yùn)算符對操作數(shù)進(jìn)行運(yùn)算(其中從棧中取得的操作數(shù)為第一操作數(shù))。所得計(jì)算結(jié)果為操作數(shù)，將新操作數(shù)入棧。轉(zhuǎn)到(1)。(2)掃描結(jié)束，正確的情況下，輸出結(jié)果應(yīng)該在b處返回，并退出。否則出錯。4、快速排序的非遞歸實(shí)現(xiàn)算法：〃快速排序的非遞歸形式--棧實(shí)現(xiàn)。#definemax100typedefstructnode{inta,b;}data;intPartition(intA[],intlength,inti,intj){/返回樞軸所在位置。intpivot=A[i];while(i<j){while(i<j&&A[j]>=pivot)j--;if(i<j)A[i++]=A[j];while(i<j&&A[i]<=pivot)i++;if(i<j)A[j--]=A[i];}A[i]=pivot;returni;}voidQuickSort(intA[],intlength){//非遞歸形式快速排序--棧實(shí)現(xiàn)。intp=Partition(A,length,0,length-1);data*temp=(data*)malloc(sizeof(data)),newdata;temp->i=0;temp->j=p-1;push(*temp);temp->i=p+1;temp->j=length-1;push(*temp);while(StackNotEmpty()){temp=pop();p=Partition(temp->i,temp->j);if(p>temp->i){newdata->i=temp->i;newdata->j=p-1;push(newdata);)if(p<temp->j){newdat