求教c语言的动态链表排序,C\C++交流,编程语言专区,鱼C论坛

ssg 发表于 2018-4-14 16:29:10

求教c语言的动态链表排序

struct Postgraduate { //研究生
int num; //学号
char name; //姓名
char sex1; //性别
int score；
structPostgraduate *next;
}*head;

例如head有 3个数据，|01小明男 66 | 02小甲鱼99 | 03 大甲鱼 88|NULL

然后怎么才能按照分数由大到小排好？？？

人造人 发表于 2018-4-14 22:30:19

ssg 发表于 2018-4-14 19:17
没有人吗？？？？？

^_^

今天先就写到这里，我明天有事，要早点睡觉
Swap函数已经调试到完美，希望没有什么问题了，^_^
就剩下 void SortList(struct Postgraduate *head) 这个函数了
你先试着写一写，看看能不能写出来，如果明天有时间，我再来写，不过真的建议你先写一写

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

typedef struct Postgraduate // 研究生
{
int num; // 学号
char name; // 姓名
char sex1; // 性别
int score;
structPostgraduate *prior;
structPostgraduate *next;
} Node;

struct Postgraduate *CreateListDebug(struct Postgraduate arr[], int count)
{
// 头结点不存储数据
struct Postgraduate *head = malloc(sizeof(Node));;
head->num = 0;
head->name = '\0';
head->sex1 = '\0';
head->score = 0;
head->prior = NULL;
head->next = NULL;

Node *p = head;
for(int i = 0; i < count; ++i)
{
Node *n = malloc(sizeof(Node));

n->num = arr.num;
strcpy(n->name, arr.name);
strcpy(n->sex1, arr.sex1);
n->score = arr.score;
n->prior = NULL;
n->next = NULL;

p->next = n;
n->prior = p;
p = p->next;
}

return head;
}

void Swap(Node *a, Node *b)
{
// a和b紧挨着的时候需要另一种方法
if((a->next == b) || (b->next == a))
{
// a在b的前面和b在a的前面不能使用同一种方法
if(b->next == a) // 让a始终在b的前面
{
structPostgraduate *temp = a;
a = b;
b = temp;
}

structPostgraduate *a_prior = a->prior;
structPostgraduate *b_next = b->next;

if(b_next == NULL) // b是尾结点
{
a_prior->next = b;
b->prior = a_prior;
a->next = b_next;
a->prior = b;
b->next = a;
}
else
{
a_prior->next = b;
b->prior = a_prior;
a->next = b_next;
a->prior = b;
b->next = a;
b_next->prior = a;
}
}
else
{
structPostgraduate *a_prior = a->prior;
structPostgraduate *a_next = a->next;
structPostgraduate *b_prior = b->prior;
structPostgraduate *b_next = b->next;

if((a_next == NULL) || (b_next == NULL)) // 这两个结点中有一个是尾结点
{
if(a_next == NULL) // 让b成为尾结点
{
structPostgraduate *temp = a;
a = b;
b = temp;

// update
a_prior = a->prior;
a_next = a->next;
b_prior = b->prior;
b_next = b->next;
}

a_prior->next = b;
b->prior = a_prior;
a->next = b_next;
a->prior = b_prior;
a_next->prior = b;
b_prior->next = a;
b->next = a_next;
}
else
{
a_prior->next = b;
b->prior = a_prior;
a->next = b_next;
a->prior = b_prior;
a_next->prior = b;
b_prior->next = a;
b->next = a_next;
b_next->prior = a;
}
}
}

void SortList(struct Postgraduate *head)
{

}

int main(void)
{
struct Postgraduate arr[] =
{
{0, "小红", "女", 100},
{1, "小明", "男", 10},
{2, "小玲", "女", 50},
{3, "小丽", "女", 40},
{4, "小林", "男", 90},
{5, "小张", "男", 5}
};
int arr_count = sizeof(arr) / sizeof(arr);

struct Postgraduate *head = CreateListDebug(arr, arr_count);

Swap(head->next, head->next->next->next);
Swap(head->next->next->next, head->next);

Swap(head->next, head->next->next);
Swap(head->next->next, head->next);

Swap(head->next, head->next->next->next->next->next->next);
Swap(head->next->next->next->next->next->next, head->next);

Swap(head->next->next->next->next->next, head->next->next->next->next->next->next);
Swap(head->next->next->next->next->next->next, head->next->next->next->next->next);
return 0;
}

下面是前一个版本，未完成的版本，正因为有下面这个版本，才会有双向链表的这个版本，如果有兴趣，你可以参考
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Postgraduate // 研究生
{
int num; // 学号
char name; // 姓名
char sex1; // 性别
int score;
structPostgraduate *next;
} Node;

void GetString(char *buff, int max_count)
{
fgets(buff, max_count, stdin);
int len = strlen(buff);
buff = '\0';
}

struct Postgraduate *CreateListDebug(struct Postgraduate arr[], int count)
{
struct Postgraduate *head = NULL;
Node *p;

for(int i = 0; i < count; ++i)
{
Node *n = malloc(sizeof(Node));

n->num = arr.num;
strcpy(n->name, arr.name);
strcpy(n->sex1, arr.sex1);
n->score = arr.score;
n->next = NULL;

if(head == NULL)
{
head = n;
p = head;
continue;
}

p->next = n;
p = p->next;
}

return head;
}

struct Postgraduate *CreateList(void)
{
struct Postgraduate *head = NULL;
Node *p;
int count = 5;

do
{
Node *n = malloc(sizeof(Node));

printf("学号：");
scanf("%d", &n->num);
getchar();
printf("姓名：");
GetString(n->name, 10);
printf("性别：");
GetString(n->sex1, 4);
printf("成绩：");
scanf("%d", &n->score);
getchar();
n->next = NULL;

if(head == NULL)
{
head = n;
p = head;
continue;
}

p->next = n;
p = p->next;
}
while(--count);

return head;
}

void Swap(Node *a, Node *b)
{
structPostgraduate *temp_a;
structPostgraduate *temp_b;

temp_a = a->next;
a->next = b->next;
temp_b = b->next->next;
b->next->next = temp_a;
b->next->next->next = temp_b;
}

void SortList(struct Postgraduate *head)
{

}

int main(void)
{
struct Postgraduate arr[] =
{
{0, "小红", "女", 100},
{1, "小明", "男", 10},
{2, "小玲", "女", 50},
{3, "小丽", "女", 40},
{4, "小林", "男", 90},
{5, "小张", "男", 5}
};
int arr_count = sizeof(arr) / sizeof(arr);

//struct Postgraduate *head = CreateList();
struct Postgraduate *head = CreateListDebug(arr, arr_count); // 为debug方便，使用数组录入数据，每次都要手动输入太要命了，^_^

//Swap(head, head->next);
//Swap(head->next, head->next->next);
Swap(head, head->next->next);
return 0;
}

BngThea 发表于 2018-4-14 16:58:36

比较每一个节点的score值大小即可

ssg 发表于 2018-4-14 16:59:32

BngThea 发表于 2018-4-14 16:58
比较每一个节点的score值大小即可

emmm我想实现把排序好的顺序放到 head2 去，怎么写？？

BngThea 发表于 2018-4-14 17:01:51

将head2的next指针指向头节点即可

ssg 发表于 2018-4-14 17:03:11

BngThea 发表于 2018-4-14 17:01
将head2的next指针指向头节点即可

那循环的条件语句怎么写，我c语言很菜{:5_100:}

ssg 发表于 2018-4-14 17:03:46

BngThea 发表于 2018-4-14 17:01
将head2的next指针指向头节点即可

我写好几个星期了，还没写好这程序{:5_107:}

ssg 发表于 2018-4-14 19:17:42

没有人吗？？？？？

ssg 发表于 2018-4-15 08:40:05

人造人发表于 2018-4-14 22:30
^_^

今天先就写到这里，我明天有事，要早点睡觉

谢谢层主，膜拜，，，我昨天用冒泡写了一下，暂时搞定了 {:5_105:}

ssg 发表于 2018-4-15 08:41:55

人造人发表于 2018-4-14 22:30
^_^

今天先就写到这里，我明天有事，要早点睡觉

又学到双向链表这好东西了{:5_109:}

人造人 发表于 2018-4-15 09:58:39

ssg 发表于 2018-4-15 08:41
又学到双向链表这好东西了

^_^
我也写完了

应该没有问题了
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Postgraduate // 研究生
{
int num; // 学号
char name; // 姓名
char sex1; // 性别
int score;
structPostgraduate *prior;
structPostgraduate *next;
} Node;

struct Postgraduate *CreateListDebug(struct Postgraduate arr[], int count)
{
// 头结点不存储数据
struct Postgraduate *head = malloc(sizeof(Node));;
head->num = 0;
head->name = '\0';
head->sex1 = '\0';
head->score = 0;
head->prior = NULL;
head->next = NULL;

Node *p = head;
for(int i = 0; i < count; ++i)
{
Node *n = malloc(sizeof(Node));

n->num = arr.num;
strcpy(n->name, arr.name);
strcpy(n->sex1, arr.sex1);
n->score = arr.score;
n->prior = NULL;
n->next = NULL;

p->next = n;
n->prior = p;
p = p->next;
}

return head;
}

void Swap(Node *a, Node *b)
{
// a和b紧挨着的时候需要另一种方法
if((a->next == b) || (b->next == a))
{
// a在b的前面和b在a的前面不能使用同一种方法
if(b->next == a) // 让a始终在b的前面
{
structPostgraduate *temp = a;
a = b;
b = temp;
}

structPostgraduate *a_prior = a->prior;
structPostgraduate *b_next = b->next;

if(b_next == NULL) // b是尾结点
{
a_prior->next = b;
b->prior = a_prior;
a->next = b_next;
a->prior = b;
b->next = a;
}
else
{
a_prior->next = b;
b->prior = a_prior;
a->next = b_next;
a->prior = b;
b->next = a;
b_next->prior = a;
}
}
else
{
structPostgraduate *a_prior = a->prior;
structPostgraduate *a_next = a->next;
structPostgraduate *b_prior = b->prior;
structPostgraduate *b_next = b->next;

if((a_next == NULL) || (b_next == NULL)) // 这两个结点中有一个是尾结点
{
if(a_next == NULL) // 让b成为尾结点
{
structPostgraduate *temp = a;
a = b;
b = temp;

// update
a_prior = a->prior;
a_next = a->next;
b_prior = b->prior;
b_next = b->next;
}

a_prior->next = b;
b->prior = a_prior;
a->next = b_next;
a->prior = b_prior;
a_next->prior = b;
b_prior->next = a;
b->next = a_next;
}
else
{
a_prior->next = b;
b->prior = a_prior;
a->next = b_next;
a->prior = b_prior;
a_next->prior = b;
b_prior->next = a;
b->next = a_next;
b_next->prior = a;
}
}
}

void SortList(struct Postgraduate *head)
{
for(Node *i = head->next; i != NULL; i = i->next)
{
for(Node *j = i->next; j != NULL; j = j->next)
{
if(i->score > j->score)
{
Swap(i, j);

Node *temp = i;
i = j;
j = temp;
}
}
}
}

int main(void)
{
struct Postgraduate arr[] =
{
{0, "小红", "女", 100},
{1, "小明", "男", 10},
{2, "小玲", "女", 50},
{3, "小丽", "女", 40},
{4, "小林", "男", 90},
{5, "小张", "男", 5}
};
int arr_count = sizeof(arr) / sizeof(arr);

struct Postgraduate *head = CreateListDebug(arr, arr_count);

/*Swap(head->next, head->next->next->next);
Swap(head->next->next->next, head->next);

Swap(head->next, head->next->next);
Swap(head->next->next, head->next);

Swap(head->next, head->next->next->next->next->next->next);
Swap(head->next->next->next->next->next->next, head->next);

Swap(head->next->next->next->next->next, head->next->next->next->next->next->next);
Swap(head->next->next->next->next->next->next, head->next->next->next->next->next);*/

SortList(head);

return 0;
}

溯影发表于 2018-4-15 12:17:38

其实链表的排序挺简单的，但是楼主说的动态链表是要重新指向么，那个就有一些复杂了，但是单单排序非循环单链表的话这个就是和平常的数组的排序一个思想
下面是一个C++代码
有错请联系俺，会更正，
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <assert.h>
using namespace std;

class Student{
public:
class LinkNode{
public:
int data;
char name;
LinkNode* next;
};
typedef LinkNode* NodePointer;

Student();//构造默认函数
void insert(int i, char *inputName, int value);
friend ostream& operator<<(ostream& out, Student &other);
friend void sortTheData(Student s1);

private:
NodePointer head;
};

Student::Student(){
head = NULL;
}

void Student::insert(int i, char *inputName, int value){
if (i == 1){
NodePointer s = new LinkNode;
strcpy(s->name, inputName);
s->data = value;
s->next = head;
head = s;
cout << "头结点插入成功" << endl;
return;
}

int j = 1;
NodePointer p = head;
NodePointer s;
while (p && j < i - 1){
j++;
p = p->next;//找到前驱
}
s = new LinkNode;
strcpy(s->name, inputName);
s->data = value;
s->next = p->next;
p->next = s;
cout << "插入成功" << endl;
return;
}

ostream& operator<<(ostream& out, Student &other){
Student::NodePointer p = other.head;
while (p){
out << "姓名:" << p->name << "\t" << "数据:" << p->data << endl;
p = p->next;
}
return out;
}

void sortTheData(Student s1){
Student::NodePointer p = s1.head;
while (p){
Student::NodePointer s = p;
while (s){
if (s->data > p->data){
int temp = s->data;
s->data = p->data;
p->data = temp;

char tempName;
strcpy(tempName, s->name);
strcpy(s->name, p->name);
strcpy(p->name, tempName);
}
s = s->next;
}
p = p->next;
}
}

int main(void){
Student s1;
int data;
char name;
for (int i = 1; i <= 3; i++){
cout << "请输入姓名:";
cin >> name;
cout << "请输入数据:";
cin >> data;

s1.insert(i, name, data);
}

cout << "*****************************" << endl;
cout << "s1是:" << endl;
cout << s1 << endl;

cout << "*****************************" << endl;
cout << "排序后的s1是:" << endl;
sortTheData(s1);
cout << s1;
return 0;
}

其中的67到86行就是排序的了，，，，

溯影发表于 2018-4-15 12:23:08

其中这个程序里只能插入三个结点，要是想插入任意个数结点的话就可以在main函数里修改一下就行了
下面是运行结果
请输入姓名:小甲鱼
请输入数据:89
头结点插入成功
请输入姓名:大甲鱼
请输入数据:67
插入成功
请输入姓名:周西瓜
请输入数据:100
插入成功
*****************************
s1是:
姓名:小甲鱼数据:89
姓名:大甲鱼数据:67
姓名:周西瓜数据:100

*****************************
排序后的s1是:
姓名:周西瓜数据:100
姓名:小甲鱼数据:89
姓名:大甲鱼数据:67
请按任意键继续. . .

ssg 发表于 2018-4-15 21:03:47

溯影发表于 2018-4-15 12:17
其实链表的排序挺简单的，但是楼主说的动态链表是要重新指向么，那个就有一些复杂了，但是单单排序非循环单 ...

谢谢大佬，我学习下

llj_llj 发表于 2018-4-16 10:10:35

思路:按照分数排序，链表不变，把链表里面的数据交换。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Postgraduate    //研究生
{
   int num;       //学号
   char name; //姓名
   char sex1; //性别
   int score;
   structPostgraduate *next;
};

struct Postgraduate *CreateList()
{
struct Postgraduate *head = (struct Postgraduate *)malloc(sizeof(struct Postgraduate));
struct Postgraduate *xiaoming = (struct Postgraduate *)malloc(sizeof(struct Postgraduate));
struct Postgraduate *xiaojiayu = (struct Postgraduate *)malloc(sizeof(struct Postgraduate));
struct Postgraduate *dajiayu = (struct Postgraduate *)malloc(sizeof(struct Postgraduate));

xiaoming->num = 1;
strcpy(xiaoming->name, "小明");
strcpy(xiaoming->sex1, "男");
xiaoming->score = 66;

xiaojiayu->num = 2;
strcpy(xiaojiayu->name, "小甲鱼");
strcpy(xiaojiayu->sex1, "男");
xiaojiayu->score = 99;

dajiayu->num = 3;
strcpy(dajiayu->name, "大甲鱼");
strcpy(dajiayu->sex1, "女");
dajiayu->score = 88;

head->next = xiaoming;
xiaoming->next = xiaojiayu;
xiaojiayu->next = dajiayu;
dajiayu->next = NULL;

return head;
}

void Log(struct Postgraduate *head)
{
while(head->next != NULL)
{
head = head->next;
printf("%d---%s---%s---%d\n", head->num, head->name, head->sex1, head->score);
}
}

void sort(struct Postgraduate *list)
{
struct Postgraduate *p = NULL;
struct Postgraduate *q = NULL;
int t = 0;
char Tp;
memset(Tp, 0, 32);
p = list->next;
for(; p!=NULL; p=p->next)
{
   for(q=p->next; q!=NULL; q=q->next)
   {
         if(p->score < q->score)
         {
            t = q->num;
            q->num = p->num;
            p->num = t;

strcpy(Tp, q->name);
strcpy(q->name, p->name);
strcpy(p->name, Tp);
memset(Tp, 0, 32);

strcpy(Tp, q->sex1);
strcpy(q->sex1, p->sex1);
strcpy(p->sex1, Tp);
memset(Tp, 0, 32);

            t = q->score;
            q->score = p->score;
            p->score = t;

         }
   }
}
return;
}

int main()
{
struct Postgraduate *head = CreateList();
Log(head);
sort(head);
printf("++++++++++++++++++++++++++\n");
Log(head);
return 0;
}

页: [1]

鱼C论坛's Archiver

求教c语言的 动态链表排序

求教c语言的动态链表排序