[已解决]直接插入排序

乔治爱啃脚趾

进行直接插入排序的同时统计在排序过程中对关键字的比较次数和移动次数，并分别输出排序前的数据序列和排序后的数据序列及其统计结果。
下面是我写的部分代码，请帮我看看。

1. #include<stdio.h>
   
2. #include <stdlib.h>
   
3. #define MAXSIZE 80   //顺序表的最大长度
   
4. typedef  int  KeyType;   // 将关键字类型定义为整型
   
5. typedef  int  InfoType;   // 将其它数据项类型也定义为整型
   
6. struct
   
7. {          int cpn;      //记录比较次数
   
8.         int mvn;     //记录移动次数
   
9. } cm[3];       //分别用来记录三种排序的比较和移动次数，并可将此数组定义为全局变量
   
10. typedef  struct{
    
11.     KeyType   key;              // 关键字项
    
12.     InfoType  otherinfo;        // 其它数据项
    
13. }RedType;                       // 记录类型
    
14. typedef  struct{
    
15.     RedType   r[MAXSIZE+1];   //一般情况将r[0]闲置
    
16.     int       length;        // 顺序表长度
    
17. }SqList;          //顺序表的类型
    
18. void zhijiecharu(SqList &L,int n)
    
19. {
    
20.         int i,e,j;
    
21.         L.r=(RedType)malloc(sizeof(RedType)*MAXSIZE);
    
22.         L.length=1;
    
23.         for(i=1;i<=n;i++)
    
24.         {
    
25.                 scanf("%d",&L.r[i].key);
    
26.                 L.length++;
    
27.         }
    
28.         for(i=1,j=2;j!=L.length;j++)
    
29.         {
    
30.                 if(L.r[i].key>L.r[j].key){
    
31.                         L.r[0].key=L.r[j].key;
    
32.                         while(cm[1].cpn++,L.r[i].key>L.r[0].key)
    
33.                         {
    
34.                                 L.r[i+1].key=L.r[i].key;
    
35.                                 i--;
    
36.                                 cm[1].mvn++;       
    
37.                         }
    
38.                         L.r[i+1]=L.r[0];
    
39.                         i=j;
    
40.                 }
    
41.                 else
    
42.                 {
    
43.                         i++;
    
44.                         cm[1].cpn++;
    
45.                 }
    
46.         }
    
47. }

复制代码

最佳答案

月排行榜 / 总排行榜

FishC

2023-12-13 19:49:56

你的代码有几个问题需要修改：

1. 在定义 `struct` 结构体时，结构体名字缺少了，应该是类似 `struct Counter{...}` 的形式。
2. 定义结构体变量 `cm` 时缺少了结构体名字，应该是 `Counter cm;`。
3. 为了记录比较次数和移动次数，需要在每次比较或移动操作之后，将 `cm.cpn` 或 `cm.mvn` 加一。
4. 在 `zhijiecharu` 函数中，对 `L.r` 进行了动态内存分配，但是没有进行释放。应该在函数结束前加上 `free(L.r);`。

除了上述问题，你的代码基本实现了直接插入排序，并且统计了比较次数和移动次数。

下面是修复后的代码：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #define MAXSIZE 80   //顺序表的最大长度
4. typedef int KeyType;   // 将关键字类型定义为整型
5. typedef int InfoType;   // 将其它数据项类型也定义为整型
7. struct Counter {
8.     int cpn;      //记录比较次数
9.     int mvn;     //记录移动次数
10. };       //分别用来记录三种排序的比较和移动次数，并可将此数组定义为全局变量
12. typedef struct {
13.     KeyType key;              // 关键字项
14.     InfoType otherinfo;        // 其它数据项
15. } RedType;                       // 记录类型
17. typedef struct {
18.     RedType *r;   //一般情况将r闲置
19.     int length;        // 顺序表长度
20. } SqList;          //顺序表的类型
22. void zhijiecharu(SqList &L, int n)
23. {
24.     int i, j;
25.     L.r = (RedType*)malloc(sizeof(RedType) * MAXSIZE);
26.     L.length = 0;
27.    
28.     for (i = 1; i <= n; i++) {
29.         scanf("%d", &(L.r[i].key));
30.     }
31.    
32.     Counter cm = {0, 0}; // 初始化比较次数和移动次数
33.    
34.     for (i = 2; i <= n; i++) {
35.         if (L.r[i].key < L.r[i-1].key) {
36.             L.r[0] = L.r[i]; // 复制为哨兵
37.             L.r[i] = L.r[i-1]; // 后移一个元素
38.             cm.mvn++;
39.             
40.             for (j = i-2; L.r[0].key < L.r[j].key; --j) {
41.                 L.r[j+1] = L.r[j];
42.                 cm.mvn++;
43.                 cm.cpn++;
44.             }
45.             
46.             L.r[j+1] = L.r[0]; // 插入到正确位置
47.             cm.mvn++;
48.         } else {
49.             cm.cpn++;
50.         }
51.     }
52.    
53.     printf("排序前的数据序列：");
54.     for (i = 1; i <= n; i++) {
55.         printf("%d ", L.r[i].key);
56.     }
57.     printf("\n");
58.    
59.     printf("排序后的数据序列：");
60.     for (i = 1; i <= n; i++) {
61.         printf("%d ", L.r[i].key);
62.     }
63.     printf("\n");
64.    
65.     printf("比较次数：%d\n", cm.cpn);
66.     printf("移动次数：%d\n", cm.mvn);
67.    
68.     free(L.r);
69. }

复制代码

希望对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

你的代码有几个问题需要修改：

1. 在定义 `struct` 结构体时，结构体名字缺少了，应该是类似 `struct Counter{...}` 的形式。
2. 定义结构体变量 `cm` 时缺少了结构体名字，应该是 `Counter cm;`。
3. 为了记录比较次数和移动次数，需要在每次比较或移动操作之后，将 `cm.cpn` 或 `cm.mvn` 加一。
4. 在 `zhijiecharu` 函数中，对 `L.r` 进行了动态内存分配，但是没有进行释放。应该在函数结束前加上 `free(L.r);`。

除了上述问题，你的代码基本实现了直接插入排序，并且统计了比较次数和移动次数。

下面是修复后的代码：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #define MAXSIZE 80   //顺序表的最大长度
4. typedef int KeyType;   // 将关键字类型定义为整型
5. typedef int InfoType;   // 将其它数据项类型也定义为整型
7. struct Counter {
8.     int cpn;      //记录比较次数
9.     int mvn;     //记录移动次数
10. };       //分别用来记录三种排序的比较和移动次数，并可将此数组定义为全局变量
12. typedef struct {
13.     KeyType key;              // 关键字项
14.     InfoType otherinfo;        // 其它数据项
15. } RedType;                       // 记录类型
17. typedef struct {
18.     RedType *r;   //一般情况将r闲置
19.     int length;        // 顺序表长度
20. } SqList;          //顺序表的类型
22. void zhijiecharu(SqList &L, int n)
23. {
24.     int i, j;
25.     L.r = (RedType*)malloc(sizeof(RedType) * MAXSIZE);
26.     L.length = 0;
27.    
28.     for (i = 1; i <= n; i++) {
29.         scanf("%d", &(L.r[i].key));
30.     }
31.    
32.     Counter cm = {0, 0}; // 初始化比较次数和移动次数
33.    
34.     for (i = 2; i <= n; i++) {
35.         if (L.r[i].key < L.r[i-1].key) {
36.             L.r[0] = L.r[i]; // 复制为哨兵
37.             L.r[i] = L.r[i-1]; // 后移一个元素
38.             cm.mvn++;
39.             
40.             for (j = i-2; L.r[0].key < L.r[j].key; --j) {
41.                 L.r[j+1] = L.r[j];
42.                 cm.mvn++;
43.                 cm.cpn++;
44.             }
45.             
46.             L.r[j+1] = L.r[0]; // 插入到正确位置
47.             cm.mvn++;
48.         } else {
49.             cm.cpn++;
50.         }
51.     }
52.    
53.     printf("排序前的数据序列：");
54.     for (i = 1; i <= n; i++) {
55.         printf("%d ", L.r[i].key);
56.     }
57.     printf("\n");
58.    
59.     printf("排序后的数据序列：");
60.     for (i = 1; i <= n; i++) {
61.         printf("%d ", L.r[i].key);
62.     }
63.     printf("\n");
64.    
65.     printf("比较次数：%d\n", cm.cpn);
66.     printf("移动次数：%d\n", cm.mvn);
67.    
68.     free(L.r);
69. }

复制代码

希望对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sfqxx

你的代码有一些小错误，但是你的整体思路是对的。将关键字进行比较，移动到合适的位置。

根据你的代码，我帮你调整一下，核心部分不变。

1. #include<stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAXSIZE 80  // 顺序表的最大长度
   
5. 
   
6. typedef int KeyType; // 将关键字类型定义为整型
   
7. typedef int InfoType; // 将其它数据项类型定义为整型
   
8. 
   
9. struct {
   
10.     int cpn;  //记录比较次数
    
11.     int mvn;  //记录移动次数
    
12. } cm[3];  //分别记录三种排序的比较和移动次数，全局变量
    
13. 
    
14. typedef struct {
    
15.     KeyType  key;  // 关键字项
    
16.     InfoType otherinfo; // 其它数据项
    
17. } RedType;  //记录类型
    
18. 
    
19. typedef struct {
    
20.     RedType  r[MAXSIZE+1]; // r[0]闲置
    
21.     int length;  // 顺序表长度
    
22. } SqList; //顺序表的类型
    
23. 
    
24. void zhijiecharu(SqList &L)
    
25. {
    
26.     int i,j;
    
27.     for(i=2; i<=L.length; i++)
    
28.     {
    
29.         if(L.r[i].key < L.r[i-1].key){
    
30.             L.r[0] = L.r[i];
    
31.             L.r[i] = L.r[i-1];
    
32.             j = i-2;
    
33.             cm[1].cpn++;
    
34.             while(j>0 && L.r[0].key<L.r[j].key)
    
35.             {
    
36.                 L.r[j+1] = L.r[j];
    
37.                 j--;
    
38.                 cm[1].mvn++;         
    
39.             }
    
40.             L.r[j+1]=L.r[0];
    
41.         }
    
42.     }
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.     SqList L;
    
48.     int n;
    
49.     int i;
    
50.     printf("请输入元素个数：\n");
    
51.     scanf("%d", &n);
    
52.     L.length = n;
    
53.     printf("请输入需要排序的数据：\n");
    
54.     for(i=1; i<=n; i++)
    
55.     {
    
56.         scanf("%d", &L.r[i].key);
    
57.     }
    
58.     printf("排序前的数据序列为：\n");
    
59.     for(i=1; i<=n; i++)
    
60.     {
    
61.         printf("%d ", L.r[i].key);
    
62.     }
    
63.     printf("\n");
    
64.     zhijiecharu(L);
    
65.     printf("排序后的数据序列为：\n");
    
66.     for(i=1; i<=n; i++)
    
67.     {
    
68.         printf("%d ", L.r[i].key);
    
69.     }
    
70.     printf("\n关键字的比较次数：%d\n", cm[1].cpn);
    
71.     printf("关键字的移动次数：%d\n", cm[1].mvn);
    
72.     return 0;
    
73. }

复制代码

这个版本的代码我在主函数里增加了从用户那边获取数据的交互，同时在排序前后都打印了数组的内容，以便于查看排序效果。

不需要提示语可以去掉。

求最佳答案

sfqxx

6

Exusiaii

@FishC 用c语言回答下述问题
假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
2）实验要求：利用Dijkstra算法求最低的票价
3) 实现提示：
该问题可以归结为一个求带权有向图中顶点间最短路径的问题。
建立以票价为权的有向图，再利用Dijkstra算法求最短路径及其路径长度。