请教关于链表的排序？求找错！！ - C语言论坛

楼主

已结贴√ 问题点数：10 回复次数：14

请教关于链表的排序？求找错！！

程序代码：


typedef struct st
{
    char name[50];
    int score;
    struct st *pnext;
}SC, *PSC;

/*排序函数*、
void sort(PSC phead)
{
    PSC p, s, t;
    int i, n, j;
    if ((p=phead->pnext)==NULL||(s=p->pnext)==NULL)
    {
        exit(0);
    }

    t = phead;
    for (i=1; i<cnt; i++)
    {
        p = phead->pnext;
        t = phead;
        for (j=0; j<cnt-i; j++)
        {
            s = p->pnext;
            if (p->score > s->score)
            {
                t->pnext = s;
                p->pnext = s->pnext;
                s->pnext = p;
                s = p;            
                p = t->pnext;      
            }
            t = p;
            p = s;
        }
    }
    p = phead;
    while(p!= NULL)
    {
        printf("\t\t\t%s\t\t%d\n", p->name, p->score);
        p = p->pnext;
    }
    system("pause");

}

搜索更多相关主题的帖子: 函数　 void　

第 2 楼

得分:0

程序代码：

typedef struct st
{
    char name[50];
    int score;
    struct st *pnext;
}SC, *PSC;
/*排序函数*/
void sort(PSC phead)
{
    PSC p, s, t;
    int i, n, j;
    if ((p=phead->pnext)==NULL||(s=p->pnext)==NULL)
    {
        exit(0);
    }

    t = phead;
    for (i=1; i<cnt; i++)
    {
        p = phead->pnext;
        t = phead;
        for (j=0; j<cnt-i; j++)
        {
            s = p->pnext;
            if (p->score > s->score)
            {
                t->pnext = s;
                p->pnext = s->pnext;
                s->pnext = p;
                s = p;            
                p = t->pnext;      
            }
            t = p;
            p = s;
        }
    }
    p = phead;
    while(p!= NULL)
    {
        printf("\t\t\t%s\t\t%d\n", p->name, p->score);
        p = p->pnext;
    }
    system("pause");

}

第 3 楼

得分:2

我没细看，有一点，每生成一个新结点不都是要分配一块内存吗？（在你的程序中就是 (PSC)malloc(sizeof(SC)); ）你的在哪？

三十年河东，三十年河西，莫欺少年穷！

第 4 楼

得分:2

链表可以这样排序的么？

授人以渔，不授人以鱼。

第 5 楼

得分:0

我又改了一个还是有问题？？

程序代码：

void sort(PSC phead)        //链表的排序
{    
    PSC p1,p2, p3,p;
    p1=p2=phead;
    while(p1 ->pnext != NULL)
    {
        p3 = p1->pnext;
        if(p1->score < p3->score)
        {
            p2=p1->pnext;  
            p1->pnext=p2->pnext;  
            p2->pnext=p1;
            p2=p1;
        }
        else
        {
            p2=p1=p1->pnext;  
        }
    }

    p = phead;   // 输出
    while(p!= NULL)
    {
        printf("\t\t\t%s\t\t%d\n", p->name, p->score);
        p = p->pnext;
    }
    system("pause");
}

第 6 楼

得分:0

回复 4楼 TonyDeng

那下面这个怎样？

第 7 楼

得分:0

你不要幻想用冒泡那样的算法来排序链表，最好先搞清楚链表到底是什麽概念。其实最简单直接的办法，是把链表复制到数组中用你熟悉的排序算法排序，然后再把数组重新放到新构建的链表中取代原先那个。又或者自己写一个专门用于交换链表节点的函数，才能使用这个排序算法。

[ 本帖最后由 TonyDeng 于 2013-5-26 13:46 编辑 ]

授人以渔，不授人以鱼。

第 8 楼

得分:2

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef struct node
{
    int data;
    struct node * pnext;
}NODE,*PNODE;

PNODE init();
void append(PNODE);
void traverse(PNODE);
int length(PNODE);
void sort(PNODE);

int main(void)
{
    PNODE phead = NULL;

    phead = init();
    append(phead);
    traverse(phead);
    length(phead);
    sort(phead);
    traverse(phead);

    return 0;
}

PNODE init()
{
    PNODE phead = (PNODE)malloc(sizeof(NODE));

    if(phead == NULL)
    {
        printf("内存分配失败，程序终止！");
        exit(-1);
    }
    phead->pnext = NULL;
    return phead;
}

void append(PNODE phead)
{
    int n,val;
    printf("请输入要添加几个节点");
    scanf("%d", &n);
    PNODE ptail = phead;
    for(int i =0; i < n; i++)
    {
        printf("请输入第%d个节点的值", i+1);
        scanf("%d", &val);
        PNODE pnew = (PNODE)malloc(sizeof(NODE));
        if(phead == NULL)
        {
            printf("内存分配失败，程序终止！");
            exit(-1);
        }
        pnew->data = val;
        ptail->pnext = pnew;
        pnew->pnext = NULL;
        ptail = pnew;
    }
}

void traverse(PNODE phead)
{
    PNODE p = phead->pnext;
    while(p != NULL)
    {
        printf("%d ", p->data);
        p = p->pnext;
    }
    printf("\n");
}

int length(PNODE phead)
{
    PNODE p = phead->pnext;
    int len = 0;
    while(NULL != p)
    {
        len++;
        p = p->pnext;
    }
    return len;
}

void sort(PNODE phead)
{
    int t =0, i,j;
    PNODE p =NULL, q = NULL;

    for(i = 0,p = phead->pnext; i < length(phead)-1; i++,p = p->pnext)
    {
        for(j = i+1,q = p->pnext; j < length(phead); j++,q = q->pnext)
        {
            if(p->data > q->data)
            {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
}

/*
2013年5月26日13:41:55
在VC++6.0中的运行结果

请输入要添加几个节点5
请输入第1个节点的值36
请输入第2个节点的值41
请输入第3个节点的值25
请输入第4个节点的值75
请输入第5个节点的值1
36 41 25 75 1
1 25 36 41 75
Press any key to continue
*/

第 9 楼

得分:0

回复 7楼 TonyDeng

可以写，我想尝试一下！

第 10 楼

得分:0

欢迎大家补充！