Question

c++链表排序

（1） 创建一个包含n个学生结点的链表（n值自定），动态构成学生花名册，学生数据包括：学号、姓名、性别、专业、宿舍号。n个学生的的数据存放在文件c:\data\studentdata.txt中。
（2） 对所创建的学生花名册（链表）按学号的增序方式排序（调整结点位置）。
（3） 按学号（从键盘输入）在链表中查询，并输出查询结果。

Answer 1

虽然分很少.但是我给你做出来了.而且我不重视这分的.只是把这题当作作业自己做做.代码如下:
#include "iostream"
#include "fstream"
#include "string"
using namespace std;
//class List;
struct Student{
string ID;
string name;
string gender;
string speciality;
string RoomId;
};

class ListNode{
public:
//friend class List;
ListNode(){}
ListNode(Student a):data(a),link(NULL){}
void SetNode(ListNode *temp){this->link=temp;}
friend int find(string ID2);
friend void sort();
friend void changeNode(ListNode *a,ListNode *b);
friend void printf();
friend void read();
private:
Student data;
ListNode *link;
};
ListNode *first;

void printf(){
ListNode *a=first;
while(a)
{
cout<<a->data.ID<<" "<<a->data.name<<" "<<a->data.gender<<" "<<a->data.speciality
<<" "<<a->data.RoomId<<endl;
a=a->link;
}
}

void changeNode(ListNode *a,ListNode *b){
Student temp;
temp=a->data;a->data=b->data;b->data=temp;
}

int find(string ID2){
ListNode *a=first;
while(a)
{if(a->data.ID==ID2){cout<<"Find:"<<endl;
cout<<a->data.ID<<" "<<a->data.name<<" "<<a->data.gender<<" "<<a->data.speciality
<<" "<<a->data.RoomId<<endl;
return 1;
}
else a=a->link;
}
cout<<"无此记录!"<<endl;
return 0;
}

void sort(){
ListNode *a=first,*b,*c;
while(a)
{ c=a;
b=a->link;
while(b)
{
if(c->data.ID>b->data.ID)c=b;
b=b->link;
}
if(a!=c)changeNode(a,c);
a=a->link;
}
printf();
}

/*class list{
public:
list(Listnode a){first=a;}
private:
ListNode *first;
};*/

void read(){
string s;
Student head;
head.gender="0";
head.ID="0";
head.name="0";
head.RoomId="0";
head.speciality="0";
ListNode *headNode=new ListNode(head);
first=headNode;
ifstream input;
input.open("c:\\data\\studentdata.txt");
if(!input)cout<<"error!"<<endl;
else while(input>>s)
{ Student newstudent;
newstudent.ID=s;
input>>s;
newstudent.name=s;
input>>s;
newstudent.gender=s;
input>>s;
newstudent.speciality=s;
input>>s;
newstudent.RoomId=s;
ListNode *newnode=new ListNode(newstudent);
headNode->SetNode(newnode);
headNode=headNode->link;

}
first=first->link;

}
int main()
{
read();
cout<<"读取完毕!"<<endl;
printf();
while(1){
cout<<"1.我要查询"<<endl;
cout<<"2.我要排序"<<endl;
cout<<"3.我要退出"<<endl;
int n;
cin>>n;
if(n==1){string findID;
cout<<"请输入要查询的学号:";
cin>>findID;
find(findID);
}
else if(n==2){sort();}
else if(n==3)exit(0);
}
}
在VC++2008编译上通过.本人花了二小时做出来的,绝对达到你的要求了.在别的编译器上有问题的可以自己调试,应该问题不大.别忘了记得建立文件.而且文件里的格式如下:
004 wk M computer 116
001 dd F computer 114
002 as F english 113
003 aq M computer 114

Answer 2

#include

#include
struct Node//双向链表的节点定义
{
int data;
struct Node* next;//后继
struct Node* prev;//前驱
};
struct Node* create_list(int N)//建立双向链表
{
struct Node *head = NULL;
struct Node *p = NULL, *q = NULL;
int i = 0, data = 0;
for (i = 0; i < N; i++)
{
printf("请输入结点%d的值：", i+1);
scanf("%d", &data);
p = (struct Node*)malloc(sizeof(struct Node));//申请空间
p->next = NULL;
p->data = data;
if (i == 0)//头结点的特殊情况是与众不同的
{
head = p; //对头结点赋值
p->prev = NULL;//因为头结点前驱为 NULL
}
else
{
p->prev = q;//指明前驱和后继
q->next = p;
}
q = p;//用q来记录当前节点的前驱
}
return head;
}
void free_list(struct Node* head)//释放链表的各个节点
{
struct Node* p = head;
struct Node* q = NULL;
while (p != NULL)//直到链表为空
{
q = p;
p = p->next;
delete q;//从头结点开始逐个删除
}
}
void display_list(struct Node* head)//打印单链表
{
struct Node* p = head;//注意打印时不能改变链表的值 所以用另外的节点来替代头结点
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;//指向下一个
}
printf("\n");
}
struct Node* get_max_node(struct Node* node)//获取至最大的节点
{
struct Node* max_node = node;//对头结点赋值 避免后面的操作改变链表本身的值
while (node != NULL)
{
if (node->data > max_node->data)
{
max_node = node;
}
node = node->next;//指向下一个节点
}//这个找最大值的过程 自己理解 就是一个循环遍历
return max_node;
}
void swap_node(struct Node* node1, struct Node* node2)//交换两个节点的值
{
int temp;
if (node1 == node2)//如果相等不用交换 保持稳定性
{
return;
}
temp = node1->data;//交换两个节点的值
node1->data = node2->data;
node2->data = temp;
}
void sort_list(struct Node* head)//排序
{
struct Node* max_node = NULL;
struct Node* current = NULL;
current = head;
while (current != NULL)//基本思想就是在一个插入排序的实现先找到未排序链表的最大值 然后和头节点交换
{//头节点在向下移一个 直到链表遍历完
max_node = get_max_node(current);
swap_node(current, max_node);
current = current->next;
}
}
int main()
{
struct Node *head = NULL;
int N = 0;
printf("请输入双向链表的结点个数：");
scanf("%d", &N);
head = create_list(N);
display_list(head);
sort_list(head);
display_list(head);
free_list(head);
return 0;
}

Answer 3

/*按照那个排序，要求讲的不清楚，不过也写了一个就是分别按照学号升序与成绩升序排序*/
#include
using namespace std;

#define OK 1
#define ERROR 0

typedef long LElemType; //学号变量类型
typedef float FElemType; //成绩变量类型

typedef int Status; //返回值的类型

typedef struct student
{
LElemType num;
FElemType score;
student *next;

}node;

typedef struct LIST
{
node *head,*tail;

}link;

node *MakeNode(long num, float score) //生成存放学生信息的节点
{
node *p=(node *)malloc(sizeof(node));
p->num = num; //存放学号
p->score = score; //存放分数
p->next = NULL; //刚生成的节点下一个为空
return p;
}

Status Create(link *s,int n)
{
long num;
float score;
s->head = s->tail = MakeNode(0,-1); //头结点num用来存放学生信息条数。score空着不用
if(NULL == s->head)
{
cout<<"分配失败!"<<endl;
return ERROR;
}
for(int i=0; i<n; i++) //录入n个学生的信息
{
cout<<"请输入第"<<(i+1)<<"个学生的信息(学号与成绩): ";
cin>>num>>score;
node *p = MakeNode(num,score);
s->tail->next = p;
s->tail = p;
s->head->num++; //修改头结点中存放学生信息条数每增加一个节点就要++1
}
return OK;
}

Status display(link *s)
{
node *p = s->head->next; //让p指针指向头结点的下一个节点，因为头结点只用来存放了学生的人数
while(p)//只要p指针指向不为空就要输出
{
cout<num<<" "<score<<endl;
p = p->next;
}
return OK;
}

Status SortByNum(link *s) //按照学号升序排序
{
int n = s->head->num;
node *p,*cur,*next;
for(int i=0; i<n-1; i++)
{
p= s->head;
cur=p->next;
next = cur->next;
for(int j=0; j<n-1-i; j++)
{
if(next->numnum)
{
p->next=next; //若前面的大于后面的就要交换前后两个值
cur->next = next->next;
next->next = cur;

p=next; //交换之后要修改当前指针与当前指针与下一个指针的位置
next=cur->next;

}else{ //挨着的两个值，前面的不大于后面的只要将指针往后面移动
p=cur;
cur = next;
next = next->next;
}
}

}

return OK;
}
//按照成绩升序排序 方法与按照学号排序是一样的
Status SortByScore(link *s)
{
int n = s->head->num;
node *p,*cur,*next;
for(int i=0; i<n-1; i++)
{
p= s->head;
cur=p->next;
next = cur->next;
for(int j=0; j<n-1-i; j++)
{
if(next->scorescore)
{
p->next=next;
cur->next = next->next;
next->next = cur;

p=next;
next=cur->next;
}else{
p=cur;
cur = next;
next = next->next;
}
}

}

return OK;
}

int main()
{
link s;
int n;
cout<<"你想录入多少学生的记录：n=";
cin>>n;
Create(&s,n);
cout<<"所有学生的信息(学号与成绩): "<<endl;
display(&s);

SortByScore(&s);
cout<<"按成绩升序排序好的所有学生的信息(学号与成绩): "<<endl;
display(&s);

SortByNum(&s);
cout<<"按学号升序排序好的所有学生的信息(学号与成绩): "<<endl;
display(&s);
return OK;
}

测试：
你想录入多少学生的记录：n=5
请输入第1个学生的信息(学号与成绩): 222 86
请输入第2个学生的信息(学号与成绩): 555 65
请输入第3个学生的信息(学号与成绩): 111 88
请输入第4个学生的信息(学号与成绩): 333 50
请输入第5个学生的信息(学号与成绩): 444 99
所有学生的信息(学号与成绩):
222 86
555 65
111 88
333 50
444 99
按成绩升序排序好的所有学生的信息(学号与成绩):
333 50
555 65
222 86
111 88
444 99
按学号升序排序好的所有学生的信息(学号与成绩):
111 88
222 86
333 50
444 99
555 65
Press any key to continue

Answer 4

c++链表排序？Copyright © 1999-2020, CSDN.NET, All Rights Reserved


 登录
简单选择排序（C++单链表实现） 原创
2018-12-14 22:36:17
 7点赞

song-10 

码龄3年

关注




具体实现过程为：

1、将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序所有记录。

2、在无序区中选取关键码最小记录，将它与无序区中的第一个记录交换，使得有序区扩展了一个记录，同时无序区减少了一个记录。

3、不断重复2，直到无序区只剩下一个记录为止。此时所有记录已经按关键码从小到大的顺序排列。

c++单链表实现如下：

#include<iostream>
using namespace std;
const int length(10);
struct Note
{
int data;
Note *next;
};
class Insert
{
public:
Insert(int a[],int n);//初始化单链表
void Swap(Note *m,Note *n);//交换节点data值
//void Swap(int &a,int &b);//异或交换整形变量值的情况
void InsertSortup();//升序排序
//void InsertSortdown();降序排序
void PrintList();//输出链表元素
private:
Note *first,*p,*q;
};
Insert::Insert(int a[],int n)//头插法初始化单链表
{
first=new Note;first->next=NULL;
for(int i=0;i<n;i++)
{ Note *s;
s=new Note;s->data=a[i];
s->next=first->next;first->next=s;
}
}
void Insert::PrintList()//输出单链表序列
{
p=first->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
void Insert::Swap(Note *m,Note *n)//交换两个结点的data值
{
int t;
t=m->data;
m->data=n->data;
n->data=t;
}
/*
void Insert::Swap(int &a,int &b)//常引用传入参数，更改形参值得同时，实参也会受到影响
{
a=a^b;
b=a^b;
a=a^b;//整形变量通过异或运算进行值交换
}
*/
void Insert::InsertSortup()//直接插入法升序排序，每一次排序从有序区第一个元素开始比较，而不是最后一个元素
{
p=first->next;
q=p->next;
while(q!=NULL)//控制趟，判断无序区是否还有元素
{
first->data=q->data;//充当哨兵角色
while(p!=q)
{
if(p->data<=first->data)p=p->next;//p指针后移，比较有序区下一个元素；降序排序仅if(p->data>=first->data)不一样
else
{
Swap(p,q);//异或交换时Swap的调用为：Swap（p->data,q->data);
p=p->next;//交换后p指针后移，比较有序区下一个元素
}
}
q=q->next;p=first->next;//q指针后移，指向无序区第一个元素。p指针初始化，指向有序区第一个元素
}
}

int main()
{
int a[length];// = { 10,9,8,7,6,5,4,3,2,1 };
int n;
L:cout << "请输入待排序序列的元素个数：";
cin >> n;
if (n > length) { cout << "请输入小于 " << length << "个元素" << endl; goto L; }
system("cls");
cout << "请输入待排序的序列：";
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
system("cls");
Insert test(a, n);
cout << "排序前的序列：";
test.PrintList();
test.InsertSortup();
cout << "排序后的升序序列：";
test.PrintList();
return 0;
}

Answer 5

给你提个思路吧

先拿出第一个节点，然后看第后面的节点，根据大小，不停地插入到第一个节点的前后就可以了

给你一个插入节点的函数

stu
*inserlistnode(stu
*phead,stu
*pstu)
{
stu
*pcur;
stu
*ppre;
pcur=phead;
if(null==phead)
{
phead=pstu;
pstu->m_pnext=null;
g_icount=g_icount+1;
return
phead;
}
while(pstu->m_num>pcur->m_num&&pcur->m_pnext!=null)
{
ppre=pcur;
pcur=pcur->m_pnext;
}
if(pstu->m_num<pcur->m_num)
{
if(phead==pcur)
{
phead=pstu;
}
else
{
ppre->m_pnext=pstu;
}
pstu->m_pnext=pcur;
g_icount=g_icount+1;
}
else
if(pstu->m_num==pcur->m_num)
{
cout<<"same
node!!!"<<endl;
}
else
if(null==pcur->m_pnext)
{
pcur->m_pnext=pstu;
pstu->m_pnext=null;
g_icount=g_icount+1;
}
return
phead;
}

你用一个递归调用吧

要不你就定义一个结构体数组也可以，排好之后按大小存放各节点

比如结构体数组叫stu[50]，然后stu[0].pnext=stu[1];stu[1].pnext=stu[2];

如此循环，排好之后就是一个有序的链表了。。