您的位置: 首页  >  文章  >  ☆ C/C++中使用单链表与结构体数组->排序(姓名+学号+分数)

☆ C/C++中使用单链表与结构体数组->排序(姓名+学号+分数)

分类: 文章 • 2024-06-12 11:48:10

对于单链表的排序，这篇文章介绍的是交换节点数据域的方法。

在写的时候仍然遇到了一些很奇怪的问题~（百思不得其解~）

(ㄒoㄒ)

*--->>>已解决~

对于那些相应的问题会附在这篇文章的最后方，

如果解决 ，后续会在下方附加解决方案。

 

****************************************************************************************************************************************

 

★首先附上单链表解决的源代码(复制即可运行~）： 

#include <iostream>
#include <string.h>
#include <malloc.h>
using namespace std;

typedef struct stu_info
{
	char name[20];				//学生姓名
	int sno;					//学生学号
	int score;					//学生成绩
	struct stu_info *link;
}STUDENT;

STUDENT * init_stu(int n)			//初始化学生信息数组并进行插入学生数据
{
	STUDENT * h;				//定义头结点
	STUDENT * S;				//待排序的学生信息，指向头结点的下一个节点
	STUDENT * p;				//和h共同指向头结点
	if (!(h = (STUDENT *)malloc(sizeof(STUDENT))))
	{
		cout << "Memory allocate error!" << endl;
		exit(0);
	}
	h->name[0] = '0';
	h->link = NULL;
	p = h;
	cout << "请输入学生的姓名、学号和分数 " << endl;
	for (int i = 0; i < n; i++)
	{
		if (!(p->link = (STUDENT *)malloc(sizeof(STUDENT))))
		{
			cout << "Memory allocate error!" << endl;
			exit(1);
		}
		S = p->link;
		cin >> p->name;
		cin >> S->sno;
		cin >> S->score;
		S->link = NULL;
		p = S;
	}
	return h;
}

//void student_sort_by_sno(STUDENT * pStu)
void pFunc_2(STUDENT * pStu,int n)
{
	STUDENT *p;							//链表长度
	int temp;
	if (pStu->link == NULL)
		return;

	p = pStu->link;							//p指向结点1，可以得到结点1的数据

	for (int j = 1; j<n; j++)				//冒泡排序
	{
		p = pStu->link;						//每次冒泡过程完毕后，必须返回结点1
		for (int i = n - 1; i >= j; i--)	//一次冒泡过程
		{
			if ((p->sno) >(p->link->sno))	//从小到大排序
			{
				temp = p->sno;
				p->sno = p->link->sno;
				p->link->sno = temp;
			}
			p = p->link;
		}
	}
	p = pStu->link;							//要打印排序好的链表，必须从头开始打印，也是遍历的一个过程
											//打印出排好序的链表(从小到大)
	for (int m = 0; m<n; m++)
	{
		cout << p->sno << endl;
		p = p->link;
	}
	cout << endl;
}

//void student_sort_by_name(STUDENT * pStu ,int n)
void pFunc_1(STUDENT * pStu,int n)
{
	STUDENT *temp;
	temp = (STUDENT*)malloc(sizeof(STUDENT));
	STUDENT * p;
	p = pStu;
	for (int j = 1; j < n; j++)
	{
		p = pStu;
		for (int i = n - 1; i >= j; i--)
		{
			if (strcmp(p->name, p->link->name)>0)    //注意这里需要注明>0，不能直接写表达式
			{
				strcpy(temp->name, p->name);
				strcpy(p->name, p->link->name);
				strcpy(p->link->name, temp->name);
			}
			p = p->link;
		}
	}
	for (int m = 0; m<n; m++)
	{
		cout << pStu->name << endl;
		pStu = pStu->link;
	}
	cout << endl;
}

//void student_sort_by_score(STUDENT * pStu)
void pFunc_3(STUDENT * pStu ,int n)
{
	STUDENT *p;									//链表长度
	int temp;
	if (pStu->link == NULL)
		return;

	p = pStu->link;									//p指向结点1，可以得到结点1的数据

	for (int j = 1; j<n; j++)						//冒泡排序
	{
		p = pStu->link;								//每次冒泡过程完毕后，必须返回结点1
		for (int i = n - 1; i >= j; i--)			//一次冒泡过程
		{
			if ((p->score) >(p->link->score))		//从小到大排序
			{
				temp = p->score;
				p->score = p->link->score;
				p->link->score = temp;
			}
			p = p->link;
		}
	}
	p = pStu->link;									//要打印排序好的链表，必须从头开始打印，也是遍历的一个过程
													//打印出排好序的链表(从小到大)
	for (int m = 0; m<n; m++)
	{
		cout << p->score << endl;
		p = p->link;
	}
	cout << endl;
}

int main()
{
	int n;											//n为输入的学生的个数
	cout << "请输入需要输入的学生个数：" << endl;
	cin >> n;
	cout << endl << "初始化学生信息" << endl << endl;
	STUDENT * pStu;
	pStu = (STUDENT *)malloc(sizeof(STUDENT));
	pStu = init_stu(n);


	//Q1测试
	//cout << endl << pStu->name << " ** " << pStu->sno << endl;


	cout << endl;
	cout << "1:按照姓名排序" << endl;
	cout << "2:按照学号进行排序" << endl;
	cout << "3:按照成绩进行排序" << endl;
	cout << endl;
	cout << "Please choose the function: " ;
	int number = 0;
	cin >> number;
	switch(number)
	{
		case 1:pFunc_1(pStu,n);break;
		case 2:pFunc_2(pStu,n);break;
		case 3:pFunc_3(pStu,n);break;
		default:cout << "Input Error! " << endl;
	}
	return 0;
}

 

 

★程序详细分析部分：

1：首先定义一个学生信息结构体，结构体包含三个部分（学生的姓名、学号与分数），然后定义一个结构体变量STUDENT

typedef struct stu_info
{
	char name[20];				//学生姓名
	int sno;					//学生学号
	int score;					//学生成绩
	struct stu_info *link;
}STUDENT;

2：初始化学生信息数组并进行插入学生数据：

·    这里声明头指针h指空，接着在函数结束时返回该空头指针(在主函数中将返回值赋予一个结构体指针的时候使用)

STUDENT * init_stu(int n)			//初始化学生信息数组并进行插入学生数据
{
	STUDENT * h;				//定义头结点
	STUDENT * S;				//待排序的学生信息，指向头结点的下一个节点
	STUDENT * p;				//和h共同指向头结点
	if (!(h = (STUDENT *)malloc(sizeof(STUDENT))))
	{
		cout << "Memory allocate error!" << endl;
		exit(0);
	}
	h->name[0] = '0';
	h->link = NULL;
	p = h;
	cout << "请输入学生的姓名、学号和分数 " << endl;
	for (int i = 0; i < n; i++)
	{
		if (!(p->link = (STUDENT *)malloc(sizeof(STUDENT))))
		{
			cout << "Memory allocate error!" << endl;
			exit(1);
		}
		S = p->link;
		cin >> p->name;
		cin >> S->sno;
		cin >> S->score;
		S->link = NULL;
		p = S;
	}
	return h;
}

3：按照学号与分数进行排序

      这两种排序的方法是一致的，通过冒泡法将最大的值移到尾部再次循环。

void pFunc_2(STUDENT * pStu, int n)      //按照学号排序
{
	STUDENT *p;							//链表长度
	int temp;
	if (pStu->link == NULL)
		return;

	p = pStu->link;							//p指向结点1，可以得到结点1的数据

	for (int j = 1; j<n; j++)				//冒泡排序
	{
		p = pStu->link;						//每次冒泡过程完毕后，必须返回结点1
		for (int i = n - 1; i >= j; i--)	//一次冒泡过程
		{
			if ((p->sno) >(p->link->sno))	//从小到大排序
			{
				temp = p->sno;
				p->sno = p->link->sno;
				p->link->sno = temp;
			}
			p = p->link;
		}
	}
	p = pStu->link;							//要打印排序好的链表，必须从头开始打印，也是遍历的一个过程
											//打印出排好序的链表(从小到大)
	for (int m = 0; m<n; m++)
	{
		cout << p->sno << endl;
		p = p->link;
	}
	cout << endl;
}


void pFunc_3(STUDENT * pStu, int n)              //按照分数进行排序
{
	STUDENT *p;									//链表长度
	int temp;
	if (pStu->link == NULL)
		return;

	p = pStu->link;									//p指向结点1，可以得到结点1的数据

	for (int j = 1; j<n; j++)						//冒泡排序
	{
		p = pStu->link;								//每次冒泡过程完毕后，必须返回结点1
		for (int i = n - 1; i >= j; i--)			//一次冒泡过程
		{
			if ((p->score) >(p->link->score))		//从小到大排序
			{
				temp = p->score;
				p->score = p->link->score;
				p->link->score = temp;
			}
			p = p->link;
		}
	}
	p = pStu->link;									//要打印排序好的链表，必须从头开始打印，也是遍历的一个过程
													//打印出排好序的链表(从小到大)
	for (int m = 0; m<n; m++)
	{
		cout << p->score << endl;
		p = p->link;
	}
	cout << endl;
}

4：这里的按照姓名排序需要多加注意

      在使用中间变量进行交换的时候，一定要注意表达式的左右值(也就是确保赋值语句的正确性)---->>>

      举个例子：p->name = p->link->name 这个语句是错误的，为什么呢？因为在表达式左侧的name是一个地址常量，不允许                          修改，能修改的只可以是该地址所指向区域的值。

       所以这里采用了字符串复制函数strcpy来进行数据域中的字符串的复制(交换)，但是这里需要注意两点：

      首先是在VS中使用该函数会报警告错误，可以在项目->xxx属性->C/C++->预处理器->预处理器定义->在后面添加：                   _CRT_SECURE_NO_WARNINGS即可；        

       其次是注意两个交换的变量类型需要一致，在本代码中指针域需要赋值给指针域。

void pFunc_1(STUDENT * pStu, int n)                  //按照姓名排序
{
	STUDENT *temp;
	temp = (STUDENT*)malloc(sizeof(STUDENT));
	STUDENT * p;
	p = pStu;
	for (int j = 1; j < n; j++)
	{
		p = pStu;
		for (int i = n - 1; i >= j; i--)
		{
			if (strcmp(p->name, p->link->name)>0)    //注意这里需要注明>0，不能直接写表达式
			{
				strcpy(temp->name, p->name);
				strcpy(p->name, p->link->name);
				strcpy(p->link->name, temp->name);
			}
			p = p->link;
		}
	}
	for (int m = 0; m<n; m++)
	{
		cout << pStu->name << endl;
		pStu = pStu->link;
	}
	cout << endl;
}

这里还需要提到的一点就是在使用strcpy(字符串比较函数)的时候，一定要指明结果是>0还是<0，否则会出现错误；

 

5：最后附上主函数，有疑问的地方也就出现在了这里：

      Q1：下面的代码中注释掉的一部分的输出中：

      为什么头结点指向name的时候会直接指向头结点后面的那个节点的值呢？(第一个输出结果不是空，是它后面的name值，而第二个输出的就是第一个节点的地址…)

int main()
{
	int n;											//n为输入的学生的个数
	cout << "请输入需要输入的学生个数：" << endl;
	cin >> n;
	cout << endl << "初始化学生信息" << endl << endl;
	STUDENT * pStu;
	pStu = (STUDENT *)malloc(sizeof(STUDENT));
	pStu = init_stu(n);


	//Q1测试
	//cout << endl << pStu->name << " ** " << pStu->sno << endl;


	cout << endl;
	cout << "1:按照姓名排序" << endl;
	cout << "2:按照学号进行排序" << endl;
	cout << "3:按照成绩进行排序" << endl;
	cout << endl;
	cout << "Please choose the function: ";
	int number = 0;
	cin >> number;
	switch (number)
	{
	case 1:pFunc_1(pStu, n); break;
	case 2:pFunc_2(pStu, n); break;
	case 3:pFunc_3(pStu, n); break;
	default:cout << "Input Error! " << endl;
	}
	return 0;
}

 

 

 

 

****************************************************************************************************************************************

2018.09.30下午更新上述问题解决方案：

事后想了想从什么方向入手去解决这个问题，

既然头指针指向数据域中的姓名部分出错，而学号、分数部分没有出错，那么问题就应该出现在初始化对name的赋值上，

于是回到那一部分，分析后果然发现问题（未改动问题代码，方便对比发现问题）：

☆ C/C++中使用单链表与结构体数组->排序(姓名+学号+分数)

在初始化语句中，p=h就直接让p指针和h指针一致了，这里应该是当时没注意，

以至于产生了后面的错误。

此处直接将p改为S即可，

到这里问题成功解决ヾ(◍°∇°◍)ﾉﾞ

 

 

 

 

 

****************************************************************************************************************************************

2018.09.30下午更新【使用结构体数组进行排序】部分功能：

 

鉴于该代码是按照要求并经过适当加工，

代码量有点大，这里写在另一篇文章中；

传送门：点我即达(｡･ω･｡)

 

****************************************************************************************************************************************

 

 

 

 

 

 

☆仅仅记录日常编写代码 与 疑问(｀・ω・´)

 

****************************************************************************************************************************************

 

             最快的脚步不是跨越，而是继续，最慢的步伐不是小步，而是徘徊。

 

****************************************************************************************************************************************

相关推荐