赞
踩
本题要求实现基于顺序表的直接选择排序算法,要求打印出每一趟的排序结果。
学习答案:
- void SelectSort(SqList *L)
- {
- int i, j, min;
-
- for(i = 0; i < L->length-1; i++)
- {
- min = i; // 假设无序表的第一个位置为最小值的索引
- for (j = i+1; j < L->length; j++) // 从无序表的第一个位置的下一个位置开始遍历
- {
- if (L->list[min] > L->list[j]) // 如果找到比当前最小值更小的值
- {
- min = j; // 更新最小值的索引
- }
- }
- if (min != i) // 如果最小值的索引不等于无序表的第一个位置的索引,说明找到了更小的值,需要交换
- {
- swap(L, i, min); // 交换无序表的第一个位置和最小值位置的元素
- }
- TraverList(*L); // 打印当前趟的排序结果
- }
- }
顺序表的结构体定义如下
- typedef int DataType;
- #define LISTSIZE 100
- typedef struct
- {
- DataType list[LISTSIZE];
- int length;
- }SqList;
void BubbleSort(SqList *L);
L
是用户传入的参数,代表待排序的顺序表,也是排序后返回的顺序表。要求打印出每一趟的排序结果。
- #include <stdio.h>
- 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 <= 0)
- {
- return 1;
- }
- else
- {
- return 0;
- }
- }
- /****** 向顺序表插入元素 ******/
- int ListInsert(SqList* L, int pos, DataType item)
- { // L为指向顺序表的指针,pos为插入位置,item为待插入的数据元素
- int i;
- if (L->length >= LISTSIZE) // 判断顺序表是否已满
- {
- printf("顺序表已满,无法插入\n");
- return 0;
- }
- if (pos <= 0 || 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 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
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。