【PTA】数据结构与算法 |
您所在的位置：网站首页 › 纯虚数函数声明 › 【PTA】数据结构与算法 |
【PTA】数据结构与算法
|
排序题都比较简单，只要掌握算法原理就不难了！ 1.直接选择排序： 直接选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是：每次从待排序的元素中选择最小（或最大）的元素，放到已排序序列的末尾（或开头）。具体实现过程如下： 1. 从待排序序列中选择最小的元素，将其与序列的第一个元素交换位置。 2. 排除第一个元素后，在剩余的元素中选择最小的元素，将其与序列的第二个元素交换位置。 3. 重复以上步骤，直到所有元素都被排序。 直接选择排序的时间复杂度为O(n^2)，不适合处理大规模数据。但是，由于其实现简单，代码易于理解，因此在一些小规模数据的排序中仍然有应用。 排序过程-----------宏观过程 例子： 初始关键字：『 8，5，2，6，9，3，1，4，0，7 』 第一趟排序后：0，『5，2，6，9，3，1，4，8，7』 第二趟排序后：0，1，『2，6，9，3，5，4，8，7』 第三趟排序后：0，1，2，『6，9，3，5，4，8，7』 第四趟排序后：0，1，2，3，『9，6，5，4，8，7』 第五趟排序后：0，1，2，3，4，『6，5，9，8，7』 第六趟排序后：0，1，2，3，4，5，『6，9，8，7』 第七趟排序后：0，1，2，3，4，5，6，『9，8，7』 第八趟排序后：0，1，2，3，4，5，6，7，『8，9』 第九趟排序后：0，1，2，3，4，5，6，7，8，『9』 结果： 『 0，1，2，3，4，5，6，7，8，9 』 【PTA】中的题目： 基于顺序表的直接选择排序 本题要求实现基于顺序表的直接选择排序算法，要求打印出每一趟的排序结果。顺序表的结构体定义如下： typedef int DataType; #define LISTSIZE 100 typedef struct { DataType list[LISTSIZE]; int length; }SqList; 函数接口定义： void SelectSort(SqList *L)L 是用户传入的参数，代表待排序的顺序表，也是排序后返回的顺序表。要求打印出每一趟的排序结果。 裁判测试程序样例： #include typedef int DataType; // 定义具体数据类型 #define LISTSIZE 100 // LISTSIZE 表示顺序表可能的最大数据元素数目 /****** 顺序表存储结构 ******/ typedef struct { DataType list[LISTSIZE]; int length; }SqList; /****** 初始化顺序表 ******/ int InitList(SqList *L) // L为指向顺序表的指针 { L->length = 0; return 1; } /****** 求顺序表表长 ******/ int ListLenth(SqList L) // L为顺序表 { return L.length; } /****** 判断顺序表是否为空 ******/ int ListEmpty(SqList L) // L为顺序表 { if (L.length length >= LISTSIZE) // 判断顺序表是否已满 { printf("顺序表已满，无法插入\n"); return 0; } if (pos L -> length + 1) { // 检查元素插入位置是否在顺序表里 printf("插入位置不合法\n"); return 0; } for (i = L -> length - 1; i >= pos - 1; i--) { // 移动数据元素 L -> list[i + 1] = L -> list[i]; } L -> list[pos - 1] = item; // 插入元素 L -> length++; // 表长加一 return 1; } /****** 遍历顺序表 ******/ int TraverList(SqList L) // L为顺序表 { int i; for(i = 0; i < L.length; i++) { printf("%d ", L.list[i]); } printf("\n"); return 1; } void swap(SqList *L, int i, int j) { DataType temp = L->list[i]; L->list[i] = L->list[j]; L->list[j] = temp; } void SelectSort(SqList *L); int main() { SqList L; DataType x; char ch; int pos = 1; InitList(&L); do { scanf("%d",&x); // 某些编译器要求此处改为scanf_s ListInsert( &L , pos++ , x ); }while ((ch=getchar())!='\n'); SelectSort(&L); printf("The sorted List is\n"); TraverList(L); return 0; } /* 请在这里填写答案 */ 输入样例： 23 45 12 20 31 输出样例： 12 45 23 20 31 12 20 23 45 31 12 20 23 45 31 12 20 23 31 45 The sorted List is 12 20 23 31 45答案解析： void SelectSort(SqList *L) { int i, j, min; int p; for(i=0;ilength-1;i++) { min = i; for(j=i+1;jlength;j++) { if(L->list[j]list[min]) { min = j; } } if(min!=i) { p=L->list[i]; L->list[i]=L->list[min]; L->list[min] = p; } TraverList(*L); } }--------------------------------------------------------------------------------------------------------------------------------- 直接插入排序： 直接插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是：将待排序元素插入到已排序序列中的合适位置，使得插入后仍然保持有序。具体实现过程如下： 1. 将序列的第一个元素视为已排序序列，其他元素视为待排序序列。 2. 从待排序序列中取出第一个元素，与已排序序列中的元素从后往前比较，找到合适的位置插入。 3. 重复以上步骤，直到所有元素都被排序。 直接插入排序的时间复杂度为O(n^2)，同样不适合处理大规模数据。但是，与直接选择排序相比，直接插入排序的比较次数较少，交换次数也较少，因此在一些小规模数据的排序中比直接选择排序更加高效。 【PTA】中题目： 基于顺序表的直接插入排序 本题要求实现基于顺序表的直接插入排序算法，要求打印出每一趟的排序结果。顺序表的结构体定义如下 typedef int DataType; #define LISTSIZE 100 typedef struct { DataType list[LISTSIZE]; int length; }SqList; 函数接口定义： void InsertSort(SqList *L)L 是用户传入的参数，代表待排序的顺序表，也是排序后返回的顺序表。要求打印出每一趟的排序结果。 裁判测试程序样例： #include typedef int DataType; // 定义具体数据类型 #define LISTSIZE 100 // LISTSIZE 表示顺序表可能的最大数据元素数目 /****** 顺序表存储结构 ******/ typedef struct { DataType list[LISTSIZE]; int length; }SqList; /****** 初始化顺序表 ******/ int InitList(SqList *L) // L为指向顺序表的指针 { L->length = 0; return 1; } /****** 求顺序表表长 ******/ int ListLenth(SqList L) // L为顺序表 { return L.length; } /****** 判断顺序表是否为空 ******/ int ListEmpty(SqList L) // L为顺序表 { if (L.length length >= LISTSIZE) // 判断顺序表是否已满 { printf("顺序表已满，无法插入\n"); return 0; } if (pos L -> length + 1) { // 检查元素插入位置是否在顺序表里 printf("插入位置不合法\n"); return 0; } for (i = L -> length - 1; i >= pos - 1; i--) { // 移动数据元素 L -> list[i + 1] = L -> list[i]; } L -> list[pos - 1] = item; // 插入元素 L -> length++; // 表长加一 return 1; } /****** 遍历顺序表 ******/ int TraverList(SqList L) // L为顺序表 { int i; for(i = 0; i < L.length; i++) { printf("%d ", L.list[i]); } printf("\n"); return 1; } void InsertSort(SqList *L); int main() { SqList L; DataType x; char ch; int pos = 1; InitList(&L); do { scanf("%d",&x); // 某些编译器要求此处改为scanf_s ListInsert( &L , pos++ , x ); }while ((ch=getchar())!='\n'); InsertSort(&L); printf("The sorted List is\n"); TraverList(L); return 0; } /* 请在这里填写答案 */ 输入样例： 23 45 12 20 31输出样例： 23 45 12 20 31 12 23 45 20 31 12 20 23 45 31 12 20 23 31 45 The sorted List is 12 20 23 31 45答案解析： void InsertSort(SqList *L) { int i, j; int p; for(i=1;ilength;i++) { p=L->list[i]; for(j=i-1;j>=0&&plist[j];j--) { L->list[j+1] = L->list[j]; } L->list[j+1] = p; TraverList(*L); } }--------------------------------------------------------------------------------------------------------------------------------- 冒泡算法属于最基本的排序算法，但是主要分为两种：重者沉和轻者浮。二者有相似也有不同之处，由于很容易理解就不做图文展示了。 【PTA】中的考题如下： 基于顺序表的冒泡排序（重者沉） 本题要求实现基于顺序表的“重者沉”的冒泡排序算法，就是第一趟排序把最大值排到表尾，第二趟排序把次大值排到表尾倒数第二位，以此类推。最后要求打印出每一趟的排序结果。顺序表的结构体定义如下 typedef int DataType; #define LISTSIZE 100 typedef struct { DataType list[LISTSIZE]; int length; }SqList; 函数接口定义： void BubbleSort(SqList *L);L 是用户传入的参数，代表待排序的顺序表，也是排序后返回的顺序表。要求打印出每一趟的排序结果。 裁判测试程序样例： #include typedef int DataType; // 定义具体数据类型 #define LISTSIZE 100 // LISTSIZE 表示顺序表可能的最大数据元素数目 /****** 顺序表存储结构 ******/ typedef struct { DataType list[LISTSIZE]; int length; }SqList; /****** 初始化顺序表 ******/ int InitList(SqList *L) // L为指向顺序表的指针 { L->length = 0; return 1; } /****** 求顺序表表长 ******/ int ListLenth(SqList L) // L为顺序表 { return L.length; } /****** 判断顺序表是否为空 ******/ int ListEmpty(SqList L) // L为顺序表 { if (L.length length >= LISTSIZE) // 判断顺序表是否已满 { printf("顺序表已满，无法插入\n"); return 0; } if (pos L -> length + 1) { // 检查元素插入位置是否在顺序表里 printf("插入位置不合法\n"); return 0; } for (i = L -> length - 1; i >= pos - 1; i--) { // 移动数据元素 L -> list[i + 1] = L -> list[i]; } L -> list[pos - 1] = item; // 插入元素 L -> length++; // 表长加一 return 1; } /****** 遍历顺序表 ******/ int TraverList(SqList L) // L为顺序表 { int i; for(i = 0; i < L.length; i++) { printf("%d ", L.list[i]); } printf("\n"); return 1; } void swap(SqList *L, int i, int j) { DataType temp = L->list[i]; L->list[i] = L->list[j]; L->list[j] = temp; } void BubbleSort(SqList *L); int main() { SqList L; DataType x; char ch; int pos = 1; InitList(&L); do { scanf("%d",&x); // 某些编译器要求此处改为scanf_s ListInsert( &L , pos++ , x ); }while ((ch=getchar())!='\n'); BubbleSort(&L); printf("The sorted List is\n"); TraverList(L); return 0; } /* 请在这里填写答案 */ 输入样例： 23 45 12 20 31 输出样例： 23 12 20 31 45 12 20 23 31 45 The sorted List is 12 20 23 31 45答案解析： void BubbleSort(SqList* L) { int i, j; int flag ; for (i = 0; i < L->length-1; i++) { flag = 1; for (j = 0; j < L->length - 1 - i; j++) { if (L->list[j + 1] < L->list[j]) { swap(L, j, j + 1); flag = 0; } } if (flag == 1) { break; } TraverList(*L); } } 基于顺序表的冒泡排序（轻者浮） 本题要求实现基于顺序表的“轻者浮”的冒泡排序算法，就是第一趟排序把最小值排到表首，第二趟排序把次小值排到表首第二位，以此类推。最后要求打印出每一趟的排序结果。顺序表的结构体定义如下 typedef int DataType; #define LISTSIZE 100 typedef struct { DataType list[LISTSIZE]; int length; }SqList; 函数接口定义： void BubbleSort(SqList *L);L 是用户传入的参数，代表待排序的顺序表，也是排序后返回的顺序表。要求打印出每一趟的排序结果。 裁判测试程序样例： #include typedef int DataType; // 定义具体数据类型 #define LISTSIZE 100 // LISTSIZE 表示顺序表可能的最大数据元素数目 /****** 顺序表存储结构 ******/ typedef struct { DataType list[LISTSIZE]; int length; }SqList; /****** 初始化顺序表 ******/ int InitList(SqList* L) // L为指向顺序表的指针 { L->length = 0; return 1; } /****** 求顺序表表长 ******/ int ListLenth(SqList L) // L为顺序表 { return L.length; } /****** 判断顺序表是否为空 ******/ int ListEmpty(SqList L) // L为顺序表 { if (L.length length >= LISTSIZE) // 判断顺序表是否已满 { printf("顺序表已满，无法插入\n"); return 0; } if (pos L->length + 1) { // 检查元素插入位置是否在顺序表里 printf("插入位置不合法\n"); return 0; } for (i = L->length - 1; i >= pos - 1; i--) { // 移动数据元素 L->list[i + 1] = L->list[i]; } L->list[pos - 1] = item; // 插入元素 L->length++; // 表长加一 return 1; } /****** 遍历顺序表 ******/ int TraverList(SqList L) // L为顺序表 { int i; for (i = 0; i < L.length; i++) { printf("%d ", L.list[i]); } printf("\n"); return 1; } /* 交换顺序表里下标为i和j的两个结点 */ void swap(SqList* L, int i, int j) { DataType temp = L->list[i]; L->list[i] = L->list[j]; L->list[j] = temp; } /* 本题要求函数 */ void BubbleSort(SqList* L); int main() { SqList L; DataType x; char ch; int pos = 1; InitList(&L); do { scanf("%d", &x); // 某些编译器要求此处改为scanf_s ListInsert(&L, pos++, x); } while ((ch = getchar()) != '\n'); BubbleSort(&L); printf("The sorted List is\n"); TraverList(L); return 0; } /* 请在这里填写答案 */ 输入样例： 23 45 12 20 31 输出样例： 12 23 45 20 31 12 20 23 45 31 12 20 23 31 45 The sorted List is 12 20 23 31 45答案解析： void BubbleSort(SqList* L) { int i, j; int flag; for (i = 0; i < L->length - 1; i++) { flag = 1; for (j = L->length - 1; j > i; j--) { if (L->list[j -1] > L->list[j]) { swap(L, j,j - 1); flag = 0; } } if (flag == 1) { break; } TraverList(*L); } }注意对比二者的差别方便记忆。 |
【本文地址】