/* * Copyright (c)2017,煙臺大學計算機與控制工程學院 * All rights reserved. * 文件名稱：項目1-3.cbp * 作 者：孫仁圓 * 完成日期：2017年12月26日 * 版 本 號：v1.0 * 問題描述：驗證歸并排序和基數排序。 * 輸入描述：無 * 程序輸出：測試數據 */ //歸并排序 #include <stdio.h> #include <malloc.h> #define MaxSize 20 typedef int KeyType; //定義關鍵字類型 typedef char InfoType[10]; typedef struct //記錄類型 { KeyType key; //關鍵字項 InfoType data; //其他數據項,類型為InfoType } RecType; //排序的記錄類型定義 void Merge(RecType R[],int low,int mid,int high) { RecType *R1; int i=low,j=mid+1,k=0; //k是R1的下標,i、j分別為第1、2段的下標 R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //動態分配空間 while (i<=mid && j<=high) //在第1段和第2段均未掃描完時循環 if (R[i].key<=R[j].key) //將第1段中的記錄放入R1中 { R1[k]=R[i]; i++; k++; } else //將第2段中的記錄放入R1中 { R1[k]=R[j]; j++; k++; } while (i<=mid) //將第1段余下部分復制到R1 { R1[k]=R[i]; i++; k++; } while (j<=high) //將第2段余下部分復制到R1 { R1[k]=R[j]; j++; k++; } for (k=0,i=low; i<=high; k++,i++) //將R1復制回R中 R[i]=R1[k]; } void MergePass(RecType R[],int length,int n) //對整個數序進行一趟歸并 { int i; for (i=0; i+2*length-1<n; i=i+2*length) //歸并length長的兩相鄰子表 Merge(R,i,i+length-1,i+2*length-1); if (i+length-1<n) //余下兩個子表,后者長度小于length Merge(R,i,i+length-1,n-1); //歸并這兩個子表 } void MergeSort(RecType R[],int n) //自底向上的二路歸并算法 { int length; for (length=1; length<n; length=2*length) //進行log2n趟歸并 MergePass(R,length,n); } int main() { int i,n=10; RecType R[MaxSize]; KeyType a[]= {57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7}; for (i=0; i<n; i++) R[i].key=a[i]; printf("排序前:"); for (i=0; i<n; i++) printf("%d ",R[i].key); printf("\n"); MergeSort(R,n); printf("排序后:"); for (i=0; i<n; i++) printf("%d ",R[i].key); printf("\n"); return 0; } #include <stdio.h> #include <malloc.h> #include <string.h> #define MAXE 20 //線性表中最多元素個數 #define MAXR 10 //基數的最大取值 #define MAXD 8 //關鍵字位數的最大取值 typedef struct node { char data[MAXD]; //記錄的關鍵字定義的字符串 struct node *next; } RecType; void CreaLink(RecType *&p,char *a[],int n); void DispLink(RecType *p); void RadixSort(RecType *&p,int r,int d) //實現基數排序:*p為待排序序列鏈表指針,r為基數,d為關鍵字位數 { RecType *head[MAXR],*tail[MAXR],*t; //定義各鏈隊的首尾指針 int i,j,k; for (i=0; i<=d-1; i++) //從低位到高位循環 { for (j=0; j<r; j++) //初始化各鏈隊首、尾指針 head[j]=tail[j]=NULL; while (p!=NULL) //對于原鏈表中每個結點循環 { k=p->data[i]-'0'; //找第k個鏈隊 if (head[k]==NULL) //進行分配 { head[k]=p; tail[k]=p; } else { tail[k]->next=p; tail[k]=p; } p=p->next; //取下一個待排序的元素 } p=NULL; //重新用p來收集所有結點 for (j=0; j<r; j++) //對于每一個鏈隊循環 if (head[j]!=NULL) //進行收集 { if (p==NULL) { p=head[j]; t=tail[j]; } else { t->next=head[j]; t=tail[j]; } } t->next=NULL; //最后一個結點的next域置NULL //以下的顯示并非必要 printf(" 按%d位排序\t",i); DispLink(p); } } void CreateLink(RecType *&p,char a[MAXE][MAXD],int n) //采用后插法產生鏈表 { int i; RecType *s,*t; for (i=0; i<n; i++) { s=(RecType *)malloc(sizeof(RecType)); strcpy(s->data,a[i]); if (i==0) { p=s; t=s; } else { t->next=s; t=s; } } t->next=NULL; } void DispLink(RecType *p) //輸出鏈表 { while (p!=NULL) { printf("%c%c ",p->data[1],p->data[0]); p=p->next; } printf("\n"); } int main() { int n=10,r=10,d=2; int i,j,k; RecType *p; char a[MAXE][MAXD]; int b[]= {57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7}; for (i=0; i<n; i++) //將b[i]轉換成字符串 { k=b[i]; for (j=0; j<d; j++) //例如b[0]=75,轉換后a[0][0]='7',a[0][1]='5' { a[i][j]=k%10+'0'; k=k/10; } a[i][j]='\0'; } CreateLink(p,a,n); printf("\n"); printf(" 初始關鍵字\t"); //輸出初始關鍵字序列 DispLink(p); RadixSort(p,10,2); printf(" 最終結果\t"); //輸出最終結果 DispLink(p); printf("\n"); return 0; }

總結

以上是生活随笔為你收集整理的第十五周 项目一 (3)验证交换排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。