鱼C论坛

 找回密码
 立即注册
查看: 624|回复: 4

[已解决]直接插入排序

[复制链接]
发表于 2023-12-13 19:49:18 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
进行直接插入排序的同时统计在排序过程中对关键字的比较次数和移动次数,并分别输出排序前的数据序列和排序后的数据序列及其统计结果。
下面是我写的部分代码,请帮我看看。
#include<stdio.h> 
#include <stdlib.h>
#define MAXSIZE 80   //顺序表的最大长度
typedef  int  KeyType;   // 将关键字类型定义为整型
typedef  int  InfoType;   // 将其它数据项类型也定义为整型
struct
{          int cpn;      //记录比较次数
        int mvn;     //记录移动次数
} cm[3];       //分别用来记录三种排序的比较和移动次数,并可将此数组定义为全局变量
typedef  struct{ 
    KeyType   key;              // 关键字项
    InfoType  otherinfo;        // 其它数据项
}RedType;                       // 记录类型
typedef  struct{
    RedType   r[MAXSIZE+1];   //一般情况将r[0]闲置
    int       length;        // 顺序表长度
}SqList;          //顺序表的类型
void zhijiecharu(SqList &L,int n)
{
        int i,e,j;
        L.r=(RedType)malloc(sizeof(RedType)*MAXSIZE);
        L.length=1;
        for(i=1;i<=n;i++)
        {
                scanf("%d",&L.r[i].key);
                L.length++;
        }
        for(i=1,j=2;j!=L.length;j++)
        {
                if(L.r[i].key>L.r[j].key){
                        L.r[0].key=L.r[j].key;
                        while(cm[1].cpn++,L.r[i].key>L.r[0].key)
                        {
                                L.r[i+1].key=L.r[i].key;
                                i--;
                                cm[1].mvn++;        
                        }
                        L.r[i+1]=L.r[0];
                        i=j;
                }
                else
                {
                        i++;
                        cm[1].cpn++;
                }
        }
}
最佳答案
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);`。

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

下面是修复后的代码:
#include <stdio.h>#include <stdlib.h>#define MAXSIZE 80   //顺序表的最大长度typedef int KeyType;   // 将关键字类型定义为整型typedef int InfoType;   // 将其它数据项类型也定义为整型struct Counter {    int cpn;      //记录比较次数    int mvn;     //记录移动次数};       //分别用来记录三种排序的比较和移动次数,并可将此数组定义为全局变量typedef struct {     KeyType key;              // 关键字项    InfoType otherinfo;        // 其它数据项} RedType;                       // 记录类型typedef struct {    RedType *r;   //一般情况将r闲置    int length;        // 顺序表长度} SqList;          //顺序表的类型void zhijiecharu(SqList &L, int n){    int i, j;    L.r = (RedType*)malloc(sizeof(RedType) * MAXSIZE);    L.length = 0;        for (i = 1; i <= n; i++) {        scanf("%d", &(L.r[i].key));    }        Counter cm = {0, 0}; // 初始化比较次数和移动次数        for (i = 2; i <= n; i++) {        if (L.r[i].key < L.r[i-1].key) {            L.r[0] = L.r[i]; // 复制为哨兵            L.r[i] = L.r[i-1]; // 后移一个元素            cm.mvn++;                        for (j = i-2; L.r[0].key < L.r[j].key; --j) {                L.r[j+1] = L.r[j];                cm.mvn++;                cm.cpn++;            }                        L.r[j+1] = L.r[0]; // 插入到正确位置            cm.mvn++;        } else {            cm.cpn++;        }    }        printf("排序前的数据序列:");    for (i = 1; i <= n; i++) {        printf("%d ", L.r[i].key);    }    printf("\n");        printf("排序后的数据序列:");    for (i = 1; i <= n; i++) {        printf("%d ", L.r[i].key);    }    printf("\n");        printf("比较次数:%d\n", cm.cpn);    printf("移动次数:%d\n", cm.mvn);        free(L.r);}
希望对你有帮助!

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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);`。

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

下面是修复后的代码:
#include <stdio.h>#include <stdlib.h>#define MAXSIZE 80   //顺序表的最大长度typedef int KeyType;   // 将关键字类型定义为整型typedef int InfoType;   // 将其它数据项类型也定义为整型struct Counter {    int cpn;      //记录比较次数    int mvn;     //记录移动次数};       //分别用来记录三种排序的比较和移动次数,并可将此数组定义为全局变量typedef struct {     KeyType key;              // 关键字项    InfoType otherinfo;        // 其它数据项} RedType;                       // 记录类型typedef struct {    RedType *r;   //一般情况将r闲置    int length;        // 顺序表长度} SqList;          //顺序表的类型void zhijiecharu(SqList &L, int n){    int i, j;    L.r = (RedType*)malloc(sizeof(RedType) * MAXSIZE);    L.length = 0;        for (i = 1; i <= n; i++) {        scanf("%d", &(L.r[i].key));    }        Counter cm = {0, 0}; // 初始化比较次数和移动次数        for (i = 2; i <= n; i++) {        if (L.r[i].key < L.r[i-1].key) {            L.r[0] = L.r[i]; // 复制为哨兵            L.r[i] = L.r[i-1]; // 后移一个元素            cm.mvn++;                        for (j = i-2; L.r[0].key < L.r[j].key; --j) {                L.r[j+1] = L.r[j];                cm.mvn++;                cm.cpn++;            }                        L.r[j+1] = L.r[0]; // 插入到正确位置            cm.mvn++;        } else {            cm.cpn++;        }    }        printf("排序前的数据序列:");    for (i = 1; i <= n; i++) {        printf("%d ", L.r[i].key);    }    printf("\n");        printf("排序后的数据序列:");    for (i = 1; i <= n; i++) {        printf("%d ", L.r[i].key);    }    printf("\n");        printf("比较次数:%d\n", cm.cpn);    printf("移动次数:%d\n", cm.mvn);        free(L.r);}
希望对你有帮助!

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-12-13 19:57:49 | 显示全部楼层
你的代码有一些小错误,但是你的整体思路是对的。将关键字进行比较,移动到合适的位置。

根据你的代码,我帮你调整一下,核心部分不变。
#include<stdio.h>
#include <stdlib.h>

#define MAXSIZE 80  // 顺序表的最大长度

typedef int KeyType; // 将关键字类型定义为整型
typedef int InfoType; // 将其它数据项类型定义为整型

struct {
    int cpn;  //记录比较次数
    int mvn;  //记录移动次数
} cm[3];  //分别记录三种排序的比较和移动次数,全局变量

typedef struct {
    KeyType  key;  // 关键字项
    InfoType otherinfo; // 其它数据项
} RedType;  //记录类型

typedef struct {
    RedType  r[MAXSIZE+1]; // r[0]闲置
    int length;  // 顺序表长度
} SqList; //顺序表的类型

void zhijiecharu(SqList &L)
{
    int i,j;
    for(i=2; i<=L.length; i++)
    {
        if(L.r[i].key < L.r[i-1].key){
            L.r[0] = L.r[i];
            L.r[i] = L.r[i-1];
            j = i-2;
            cm[1].cpn++;
            while(j>0 && L.r[0].key<L.r[j].key)
            {
                L.r[j+1] = L.r[j];
                j--;
                cm[1].mvn++;          
            }
            L.r[j+1]=L.r[0];
        }
    }
}

int main()
{
    SqList L;
    int n;
    int i;
    printf("请输入元素个数:\n");
    scanf("%d", &n);
    L.length = n;
    printf("请输入需要排序的数据:\n");
    for(i=1; i<=n; i++)
    {
        scanf("%d", &L.r[i].key);
    }
    printf("排序前的数据序列为:\n");
    for(i=1; i<=n; i++)
    {
        printf("%d ", L.r[i].key);
    }
    printf("\n");
    zhijiecharu(L);
    printf("排序后的数据序列为:\n");
    for(i=1; i<=n; i++)
    {
        printf("%d ", L.r[i].key);
    }
    printf("\n关键字的比较次数:%d\n", cm[1].cpn);
    printf("关键字的移动次数:%d\n", cm[1].mvn);
    return 0;
}


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

不需要提示语可以去掉。

求最佳答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-12-13 20:06:32 | 显示全部楼层
6
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-12-14 14:12:07 | 显示全部楼层
@FishC 用c语言回答下述问题
假设以一个带权有向图表示某一区域的公交线路网,图中顶点代表一些区域中的重要场所,弧代表已有的公交线路,弧上的权表示该线路上的票价(或搭乘所需时间),试设计一个交通指南系统,指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
2)实验要求:利用Dijkstra算法求最低的票价
3) 实现提示:
该问题可以归结为一个求带权有向图中顶点间最短路径的问题。
建立以票价为权的有向图,再利用Dijkstra算法求最短路径及其路径长度。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-22 09:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表