深圳建设网站哪家好,学校网站下载,可以免费视频的软件哪个最好,网站购买平台一、链表的概述
1.链表与数组对比
遍历数组中的数据#xff0c;查询数据比较方便#xff0c;但往数组中插入、删除数据需要移动大量数据#xff1b;相反。链表遍历、查询数据不方便#xff0c;但是插入、删除数据比较方便#xff0c;不需要移动大量数据#xff0c;直接…一、链表的概述
1.链表与数组对比
遍历数组中的数据查询数据比较方便但往数组中插入、删除数据需要移动大量数据相反。链表遍历、查询数据不方便但是插入、删除数据比较方便不需要移动大量数据直接在指定位置插入或删除指定节点这与链表节点的结构有关数组的一个个元素在内存中是连续的链表的节点间内存不连续。
2.链表节点
2.1链表节点的概念
链表的节点用来保存数据信息的分为数据域、指针域两个部分数据域用来存放核心数据指针域用来存放下一个节点的地址。
链表一般分为无头链表和有头链表 无头链表即由一个指针变量保存首个节点的起始地址有头链表由一个节点的指针域保存首节点的起始地址且该节点没有数据域只有指针域。
2.2链表节点类型定义
链表节点类型定义和结构体一样只不过分为了数据域和指针域指针域是一个结构体指针成员。
代码演示
typedef struct stu
{// 定义数据域int num;char name[32];float score;// 定义指针域struct stu *next;
}STU;二、单向链表应用
1.单向链表
单向链表又叫静态链表它是一个接着一个节点依次单向排列分布的上一个节点的指针域指向下一个节点的起始地址最后一个节点的指针域指向NULL。
创建一个单向链表
int main()
{// 定义5个节点STU stu1 {小明, 18, 90.0f, NULL};STU stu2 {小王, 20, 75.5f, NULL};STU stu3 {小红, 19, 87.0f, NULL};STU stu4 {小当家, 18, 86.5f, NULL};STU stu5 {小魔仙, 21, 88.8f, NULL};// 定义节点头STU *stus stu1;// 构建链表stu1.next stu2;stu2.next stu3;stu3.next stu4;stu4.next stu5;// 遍历链表STU *p stus;while (p ! NULL){printf(姓名%-7s年龄%-2d分数%.2f\n, p-name, p-age, p-score);p p-next;}return 0;
}运行结果
姓名小明 年龄18分数90.00
姓名小王 年龄20分数75.50
姓名小红 年龄19分数87.00
姓名小当家 年龄18分数86.50
姓名小魔仙 年龄21分数88.80说明 定义节点和定义结构体变量一样初始化先将 next 指向 NULL定义一个节点头指针变量指向第一个节点然后第一个节点的 next 指向下一个节点反复执行直到最后一个节点将最后一个节点的 next 指向NULL在遍历链表的时候通过一个临时指针变量保存链表头用这个临时指针变量去遍历因为链表头不能随意改变指向每遍历一个节点就将临时指针变量指向当前节点的下一个节点的起始位置。
2.单向链表综合案例简易的学生信息管理系统
项目要求通过单项链表开发一个简易的学生管理系统系统功能包含学生信息的增删改查等基本操作通过输入关键词命令调用相应的功能函数来满足用户需求。
2.1项目基本框架
在开始具体的功能函数前先整理思路理清大致框架想好需要添加哪些功能然后再逐一去实现这些功能函数。
菜单界面和主函数框架
// 一个简单的学生管理系统
typedef struct stu {// 定义数据域int num;char name[32];float score;// 定义指针域struct stu *next;
} STU;// 定义函数打印菜单界面
void func_list(void) {printf(-----------------------------------\n);printf(--insert:插入学生信息 |\n);printf(--print:遍历信息 |\n);printf(--search:查询某个学生的信息 |\n);printf(--delete:删除某个学生的信息 |\n);printf(--free:删除所有学生 |\n);printf(--reverse:链表逆序 |\n);printf(--sort:链表排序 |\n);printf(--quit:退出整个程序 |\n);printf(-----------------------------------\n);return;
}int main() {// 调用函数打印功能菜单func_list();// 获取指令char cmd[16] ;while(1){printf(请输入要操作的指令);scanf(%s, cmd);if (strcmp(insert, cmd) 0){printf(插入学生信息\n);}else if (strcmp(print, cmd) 0){printf(遍历信息\n);}else if (strcmp(search, cmd) 0){printf(查询某个学生的信息\n);}else if (strcmp(delete, cmd) 0){printf(删除某个学生的信息\n);}else if (strcmp(free, cmd) 0){printf(删除所有学生\n);}else if (strcmp(reverse, cmd) 0){printf(链表逆序\n);}else if (strcmp(sort, cmd) 0){printf(链表排序\n);}else if (strcmp(quit, cmd) 0){printf(程序已经退出\n);break;}else{printf(请输入有效命令\n);}}return 0;
}运行结果
-----------------------------------
--insert:插入学生信息 |
--print:遍历信息 |
--search:查询某个学生的信息 |
--delete:删除某个学生的信息 |
--free:删除所有学生 |
--reverse:链表逆序 |
--sort:链表排序 |
--quit:退出整个程序 |
-----------------------------------
请输入要操作的指令insert
插入学生信息
请输入要操作的指令printf
请输入有效命令
请输入要操作的指令quit
程序已经退出说明 因为学生信息包含的数据类型多样因此通过结构体变量来存储学生信息为了完成增删改查等复杂操作通过链表的形式实现定义一个函数用来打印功能菜单主函数循环获取用户输入的命令条件判断调用相应的功能函数。
2.2插入学生信息
2.2.1主函数
主函数部分
int main() {// 调用函数打印功能菜单func_list();// 定义一个链表头STU *head NULL;// 获取指令char cmd[16] ;while(1){printf(请输入要操作的指令);scanf(%s, cmd);if (strcmp(insert, cmd) 0){// 定义临时变量用于接收输入的学生信息STU stu_temp;int n 0;printf(请输入要添加的学生的个数);scanf(%d, n);printf(请输入学生信息学号 姓名 分数);// 调用函数添加学生信息int i 0;for (i 0; i n; i){scanf(%d %s %f, stu_temp.num, stu_temp.name, stu_temp.score);// 调用函数添加学生信息// head insert_func_head(head, stu_temp); // 头部插入// head insert_func_tail(head, stu_temp); // 尾部插入head insert_func_sequence(head, stu_temp); // 顺序插入}printf(已添加%d位学生信息\n, n);}else if (strcmp(print, cmd) 0){// 调用函数打印学生信息print_func(head);}// .........省略其它功能}
}说明 这里主函数部分列出了插入和打印的功能其它功能代码省略因为很多功能函数都会用到链表头因此把它定义在主函数最外层作用域下为所有功能函数公有插入函数只负责插入功能学生信息的获取在主函数完成也可以单独封装一个获取学生信息的函数将获取到的学生信息通过一个临时结构体变量作为插入函数的实参传入。
2.2.2头部插入学生信息
代码演示
// 定义函数在头部插入学生信息
STU *insert_func_head(STU *head, STU stu_temp)
{// 申请堆区空间存储一个学生的信息STU *new_stu (STU *)malloc(sizeof(STU));if (NULL new_stu){printf(空间申请失败\n);return head;}// 将获取到的学生信息存入申请到的空间*new_stu stu_temp;// 将新的学生节点插入链表// 链表为空if (NULL head){head new_stu;new_stu-next NULL;}// 链表不为空else{new_stu-next head;head new_stu;}return head;
}说明 因为是插入信息需要函数内部改变链表结构或者链表头的指向因此应将 head 的地址传入为一个二级指针。但为了方便操作也可以传入一级指针然后将函数内部的临时局部变量 head 保存的头节点的地址返回主函数用 head 接收保存新的链表头节点位置即使函数调用结束临时局部变量 head 释放也无所谓它释放的只是这个变量保存的地址编号并不会释放地址指向的内存空间主函数的 head 已经保存了新链表的头节点位置可以正常访问如果堆区空间申请失败不要返回 NULL失败相当于不改变链表结构直接原样返回就行否则会将原来的链表丢失还会造成内存泄漏堆区空间无法释放的问题链表头为空的话直接将 head 指向新添加的学生节点就行再将新学生节点指针域指向 NULL链表头不为空的话先将新学生节点的指针域指向 head 指向的节点再将 head 指向新学生节点这里顺序不能颠倒如果颠倒head 指向了新学生节点那之前的链表就丢失了新学生节点的指针域找不到之前 head 指向的头节点。也可以先定义一个临时指针变量指向 head 指向的头节点然后顺序可以颠倒了但感觉多此一举。
2.2.3遍历所有学生信息
代码演示
// 定义函数打印学生信息
void print_func(STU *head)
{// 判断链表是否为空if (NULL head){printf(未添加任何学生信息\n);return;}// 链表不为空遍历学生信息STU *p head;printf(---------------学生信息---------------\n);while(p ! NULL){printf(学号%03d, 姓名%-6s, 分数%.2f\n, p-num, p-name, p-score);p p-next;}printf(---------------末行显示---------------\n);
}说明 遍历所有学生信息是读操作不需要返回值遍历前先判断链表是否为空再遍历否则访问非法内存定义一个临时指针变量并将 head 赋值给它因为读操作节点头不能改变需要一个临时指针变量去改变指向遍历信息。 头部插入运行结果
请输入要操作的指令insert
请输入要添加的学生的个数3
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85
103 王天霸 65.5
已添加3位学生信息
请输入要操作的指令print
---------------学生信息---------------
学号103, 姓名王天霸, 分数65.50
学号102, 姓名小红 , 分数85.00
学号101, 姓名小明 , 分数88.80
---------------末行显示---------------
请输入要操作的指令quit
程序已经退出说明从输出结果可以看出头部插入去遍历的时候类似于先入后出。
2.2.4尾部插入学生信息
代码演示
// 定义函数在尾部插入学生信息
STU *insert_func_tail(STU *head, STU stu_temp)
{// 申请堆区空间存储一个学生的信息STU *new_stu (STU *)malloc(sizeof(STU));if (NULL new_stu){printf(空间申请失败\n);return head;}// 将获取到的学生信息存入申请到的空间*new_stu stu_temp;new_stu-next NULL;// 将新的学生节点插入链表// 链表为空if (NULL head){head new_stu;}// 链表不为空else{STU *p head;while(p-next ! NULL){p p-next;}p-next new_stu;}return head;
}说明 参数传递返回值等操作同头部插入因为是尾部插入新学生节点的指针域一定指向 NULL因此在判断链表是否为空前就可以将指针域指向空new_stu-next NULL;减少重复代码链表不为空时定义一个临时指针变量用于定位到链表的最后一个节点然后将最后一个节点的 next 指向新学生节点即可。 尾部插入运行结果
请输入要操作的指令insert
请输入要添加的学生的个数3
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85
103 王天霸 65.5
已添加3位学生信息
请输入要操作的指令print
---------------学生信息---------------
学号101, 姓名小明 , 分数88.80
学号102, 姓名小红 , 分数85.00
学号103, 姓名王天霸, 分数65.50
---------------末行显示---------------说明从运行结果可以看出尾部插入学生遍历结果类似于先入先出。
2.2.5有序插入学生信息
这里按照学生学号从小到大的顺序排序。
代码演示
// 定义函数按照学号顺序插入
STU *insert_func_sequence(STU *head, STU stu_temp)
{// 申请堆区空间存储一个学生的信息STU *new_stu (STU *)malloc(sizeof(STU));if (NULL new_stu){printf(空间申请失败\n);return head;}// 将获取到的学生信息存入申请到的空间*new_stu stu_temp;new_stu-next NULL;// 将新的学生节点插入链表// 链表为空if (NULL head){head new_stu;}// 链表不为空else{// 定义两个指针pa用于寻找插入位置定位指针pb用于保存pa的上一个节点位置STU *pa head, *pb head;while((pa ! NULL) (pa-num new_stu-num)){pb pa;pa pa-next;}// 插入链表最后一个if (NULL pa){pb-next new_stu;// new_stu pb-next; // 错误写法}// 插入链表第一个else if(pa head){new_stu-next head;head new_stu;}// 插入到链表的中间else{pb-next new_stu;new_stu-next pa;}}return head;
}说明 顺序插入除了链表不为空的情况其它同前面两种方式需要依次比较新学生的学号与链表中其它学生学号的大小确定插入点的位置因此需要定义一个临时指针变量定位考虑到如果是插入的话需要截断以前的链表将截断位置的上一个节点的 next 指向新节点新节点的 next 指向下一个节点下一个节点就是定位指针当前指向的位置但上一个节点不知道因此需要定义另外一个临时指针变量保存定位指针的上一个节点位置通过条件循环定位插入位置当新节点的学号大于当前定位节点的学号且当前节点的next不指向NULL时指针继续后移知道其中一个不满足退出循环循环结束如果NULL pa说明新节点num值最大插入到末尾注意while((pa ! NULL) (pa-num new_stu-num))必须先判断pa ! NULL否则当pa指向NULL时先判断pa-num new_stu-num会访问非法内存注意pb-next new_stu;与new_stu pb-next;是有区别的前者是将pb的 next 指向new_stu后者是将new_stu指向pb的 next 指向的节点注意区分如果循环因为条件pa-num new_stu-num不满足退出当pa head时说明新节点的 num 值最小插入到头部让新节点的 next 指向 head 指向的节点再用 head 指向新节点如果上面情况都不是那插入到中间位置让新节点指向定位指针指向的节点再让定位指针前一个节点的 next 指向新节点这两步位置可调换。 运行结果
请输入要操作的指令insert
请输入要添加的学生的个数3
请输入学生信息(学号 姓名 分数):105 张大炮 85
101 吕小布 83.5
103 王刚 75
已添加3位学生信息
请输入要操作的指令print
---------------学生信息---------------
学号101, 姓名吕小布, 分数83.50
学号103, 姓名王刚 , 分数75.00
学号105, 姓名张大炮, 分数85.00
---------------末行显示---------------说明有序插入不管输入数据的先后结果都是按照规定的顺序插入的。
2.3查询某个学生信息
主函数代码
// ......省略部分代码
else if (strcmp(search, cmd) 0){char name[32] ;printf(请输入要查找的学生姓名);scanf(%s, name);// 定义一个指针变量保存查找到的值STU *ret search_func(head, name);if (ret NULL)printf(未找到该学生信息\n);else{printf(---------------学生信息---------------\n);printf(学号%03d, 姓名%-6s, 分数%.2f\n, ret-num, ret-name, ret-score);printf(---------------末行提示---------------\n);}}
// ......省略部分代码功能函数代码
// 定义函数查找学生信息
STU *search_func(STU *head, char *name)
{STU *p head;// 判断链表是否为空if (NULL head){printf(未添加任何学生信息\n);return NULL;}else{while((strcmp(name, p-name) ! 0) (p-next ! NULL)){p p-next;}if (strcmp(name, p-name) 0)return p;elsereturn NULL;}
}说明 通过姓名查找学生信息返回第一个找到的学生信息。功能函数只负责查找学生姓名的获取在主函数完成定义一个临时指针变量用于保存找到的节点地址函数将找到的节点地址通过返回值返回。
请输入要操作的指令insert
请输入要添加的学生的个数2
请输入学生信息(学号 姓名 分数):101 小明 88.5
102 小红 85
已添加2位学生信息
请输入要操作的指令search
请输入要查找的学生姓名李华
未找到该学生信息
请输入要操作的指令search
请输入要查找的学生姓名小红
---------------学生信息---------------
学号102, 姓名小红 , 分数85.00
---------------末行提示---------------2.4删除某个学生的信息
主函数代码
// ......省略部分代码
else if (strcmp(delete, cmd) 0){int num 0;printf(请输入要删除的学生学号);scanf(%d, num);// 调用函数删除指定学号信息head delete_func(head, num);}
// ......省略部分代码功能函数代码
// 定义函数删除指定学号学生信息
STU *delete_func(STU *head, int num)
{// 定义两个指针一个用于查找另外一个用于STU *pa head, *pb head;// 判断链表是否存在if (NULL head){printf(未添加任何学生信息\n);return head;}else{while ((pa-num ! num) (pa-next ! NULL)){pb pa;pa pa-next;}// 如果要删除的信息存在if (pa-num num){// 节点在头部if (pa head){head head-next;printf(已删除信息%d\n, pa-num);free(pa);}// 节点在尾部
// else if (pa-next NULL)
// {
// pb-next NULL;
// free(pa);
// }// 节点在中尾部else{pb-next pa-next;printf(已删除信息%d\n, pa-num);free(pa);}}// 信息不存在elseprintf(要删除的信息不存在\n);}return head;
}说明 因为删除要修改链表结构或者更改 head 头指向因此需要将处理后的 head 值返回给函数外部 head 变量接收需要定义两个指针变量一个用于查找定位一个用于记录定位指针的上一个元素。因为要删除节点因此需要将被删除节点的上一个节点的 next 指向被删除节点的下一个节点一定要先将被删除节点的上一个节点的 next 指向下一个节点后再删除该节点否则该节点以后的链表丢失节点在中间和节点在尾部时的代码是等价的因此可以合并减少代码量。 运行结果
请输入要操作的指令insert
请输入要添加的学生的个数4
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85
103 张大炮 83.5
104 王刚 75
已添加4位学生信息
请输入要操作的指令print
---------------学生信息---------------
学号101, 姓名小明 , 分数88.80
学号102, 姓名小红 , 分数85.00
学号103, 姓名张大炮, 分数83.50
学号104, 姓名王刚 , 分数75.00
---------------末行显示---------------
请输入要操作的指令delete
请输入要删除的学生学号103 // 删中间
已删除信息103
请输入要操作的指令print
---------------学生信息---------------
学号101, 姓名小明 , 分数88.80
学号102, 姓名小红 , 分数85.00
学号104, 姓名王刚 , 分数75.00
---------------末行显示---------------
请输入要操作的指令delete
请输入要删除的学生学号101 //删开头
已删除信息101
请输入要操作的指令delete
请输入要删除的学生学号104
已删除信息104 // 删末尾
请输入要操作的指令print
---------------学生信息---------------
学号102, 姓名小红 , 分数85.00
---------------末行显示---------------
请输入要操作的指令delete
请输入要删除的学生学号105 // 信息不存在
要删除的信息不存在2.5清空学生信息
主函数代码
// ......省略部分代码
else if (strcmp(free, cmd) 0){unsigned int password 0;printf(请输入密码验证);scanf(%u, password);if (password 123456)head free_func(head);elseprintf(密码错误无权操作\n);}
// ......省略部分代码功能函数代码
// d定义函数清空学生信息
STU *free_func(STU *head)
{STU *p head;// 判断链表是否为空if (NULL head){printf(未添加任何学生信息\n);return head;}while (p ! NULL){head head-next;free(p);p head;}printf(学生信息已清空\n);return NULL;
}说明 释放链表从头到尾逐一释放注意要先将 head 指向下一个节点再释放当前节点链表清空以后记得返回 NULL 给外部 head 变量同时可以为该功能添加权限验证毕竟删除所有学生信息是件很危险的事情。 运行结果
请输入要操作的指令insert
请输入要添加的学生的个数4
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85.5
103 张大炮 75
104 黄天霸 65
已添加4位学生信息
请输入要操作的指令print
---------------学生信息---------------
学号101, 姓名小明 , 分数88.80
学号102, 姓名小红 , 分数85.50
学号103, 姓名张大炮, 分数75.00
学号104, 姓名黄天霸, 分数65.00
---------------末行显示---------------
请输入要操作的指令free
请输入密码验证123456
学生信息已清空
请输入要操作的指令print
未添加任何学生信息2.6链表逆序
主函数代码
// ......省略部分代码
else if (strcmp(reverse, cmd) 0){// 调用函数逆序链表head reverse_func(head);}
// ......省略部分代码功能函数代码
// 定义函数逆序整个链表
STU *reverse_func(STU *head)
{// 定义两个指针变量pa的next用于指向前一个节点pb指向pa下一个节点STU *pa head, *pb head;// 判断链表是否存在if (NULL head){printf(未添加任何学生信息\n);return head;}else{pa head-next;head-next NULL;while(pa ! NULL){pb pa-next;pa-next head;head pa;pa pb;}printf(链表逆序成功\n);}return head;
}说明 这里的逆序不是按照反向排序只是将链表整体颠倒不存在排序的作用逆序链表即将第一个节点的 next 指向 NULL将第二个节点的 next 指向第一个节点第三个节点的 next 指向第二个节点以此类推直到最后一个节点的 next 指向倒数第二个节点将 head 指向最后一个节点由上面推理需要一个指针变量 pa 指向需要改变 next 的节点但当这个节点的 next 指向前一个节点时下一个节点开始就丢失了因此需要定义另外一个指针 pb 指向下一个节点并且要在 pa 的 next 指向上一个节点前将 pb 指向 pa 指向的下一个节点当 pa 指向 pb 指向的节点前先将 head 指向 pa 指向的节点一直重复上面的操作直到 pa 指向 NULL时head 就指向了原始链表的尾部逆序完成如果链表就一个节点那 pa 刚开始就指向 NULL不会进入循环代码也成立不需要分情况判断了。 运行结果
请输入要操作的指令insert
请输入要添加的学生的个数4
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85.5
103 张大炮 75
104 黄天霸 65
已添加4位学生信息
请输入要操作的指令print
---------------学生信息---------------
学号101, 姓名小明 , 分数88.80
学号102, 姓名小红 , 分数85.50
学号103, 姓名张大炮, 分数75.00
学号104, 姓名黄天霸, 分数65.00
---------------末行显示---------------
请输入要操作的指令reverse
链表逆序成功
请输入要操作的指令print
---------------学生信息---------------
学号104, 姓名黄天霸, 分数65.00
学号103, 姓名张大炮, 分数75.00
学号102, 姓名小红 , 分数85.50
学号101, 姓名小明 , 分数88.80
---------------末行显示---------------2.7链表排序
先了解排序的算法。
2.7.1数值数组冒泡排序
冒泡排序正向排序时前后两两比较前一个小于后一个保持不变前一个大于后一个两两交换指针后移一位每循环一次可以将最大的值排到当次排序的末尾。
例如为数组int nums {2 3 1 5 4}排序。
23154numsnums 1
正向排序时遵循相邻比较前小于后不变前大于后交换位置步骤如下
第0轮i 0
21345
找到一个最大值 5 放到数组最后既然 5 已经是本轮最大就没必要参与下一轮比较了。第0轮进行了4次比较。
第1轮i 1
1234
第1轮这里虽然看似已经排序完成了但为了代码的通用性我们需要考虑极端的情况例如int nums {5 4 3 2 1}可以通过这个例子自行推演。第1轮经历了3次比较。
第2轮i 2
123
第2轮经历了2次比较。
第3轮i 3
12
第3轮经历1次比较排序完成。
由上面的推演过程我们可以总结出规律假设一个数值数组有 n 个数会经历 n -1 轮比较每轮比较会经历 (当前排序的元素个数 - 1) 次比较轮数从0开始计算(元素个数 n - 轮数)联立可得(每轮比较次数 n - i - 1)。案例键盘获取10个数为数组赋值通过冒泡排序法排序遍历数组
// 定义函数用于给数组排序
void sort_func(int *nums, int n)
{int i 0;for (i 0; i n - 1; i) // 每循环一次是一轮{int j 0;for (j 0; j n - i - 1; j) // 每轮比较的次数{if(nums[j] nums[j 1]){int temp nums[j];nums[j] nums[j 1];nums[j 1] temp;}}}
}int main()
{// 定义一个数值数组int nums[10] {0};int n sizeof(nums) / sizeof(nums[0]);printf(请输入10个整数);int i 0;for (i 1; i n; i){scanf(%d, nums[i]);}// 调用函数为数组排序sort_func(nums, n);// 遍历数组for (i 1; i n; i){printf(%d , nums[i]);}printf(\n);return 0;
}运行结果
请输入10个整数21 35 12 5 89 74 36 92 9 16
5 9 12 21 35 36 74 89 922.7.2数值数组选择排序
前面的冒泡排序每轮能找出一个最大值这里的选择排序则是每轮找出一个最小值。定义一个最小值变量假设每轮第一个值最小然后第一个数与后面其它数比较小于就继续与下一个比较大于就将 min 指向较小的那一个比较结束如果 min 已经不是第一个元素那么与第一个元素交换位置。
例如为数组int nums {2 3 1 5 4}排序。
23154numsnums 1
第0轮i 0
13254
第1轮i 1
2354
第2轮i 2
354
第3轮i 3
45 由上面的推演过程我们可以总结出规律假设一个数值数组有 n 个数会经历 n -1 轮比较轮数从0开始计算每轮会进行n - i - 1次比较。 代码演示
// 定义函数用于给数组排序
void sort_func(int *nums, int n)
{int i 0;for (i 0; i n - 1; i){// 定义一个最小值索引并假设第一个元素值最小int min 0, j 0;for (min i, j i 1; j n; j){// 依次比较如果min不是最小就定位到最小if (nums[min] nums[j])min j;}// 每轮比较完如果不是假设的第一个值那么就交换两个的值if (min ! i){int temp nums[min];nums[min] nums[i];nums[i] temp;}}
}运行结果
请输入10个整数21 35 12 5 89 74 36 92 9 16
5 9 12 21 35 36 74 89 92说明相比于冒泡排序选择排序交换的次数更少。
2.7.3链表排序实现
链表排序最麻烦的步骤就是两个节点的交换了由上面两种排序方式对比选择排序交换次数较少这里选用选择排序演示。
代码演示
// 定义函数为链表排序
void sort_func(STU *head)
{// 判断链表是否存在if (NULL head){printf(未添加任何学生信息\n);return;}else{STU *p_i NULL;for (p_i head; p_i-next ! NULL; p_i p_i-next){STU *p_min NULL, *p_j NULL;for (p_min p_i, p_j p_i-next; p_j ! NULL; p_j p_j-next){if (p_min-num p_j-num)p_min p_j;}if (p_min ! p_i){// 整体交换节点成员STU temp *p_min;*p_min *p_i;*p_i temp;// 将指针域恢复原样temp.next p_min-next;p_min-next p_i-next;p_i-next temp.next;}}printf(排序完成\n);}
}运行结果
请输入要操作的指令insert
请输入要添加的学生的个数4
请输入学生信息(学号 姓名 分数):105 小明 88.8
101 小红 85.5
103 张伟 90
102 张大炮 65
已添加4位学生信息
请输入要操作的指令print
---------------学生信息---------------
学号105, 姓名小明 , 分数88.80
学号101, 姓名小红 , 分数85.50
学号103, 姓名张伟 , 分数90.00
学号102, 姓名张大炮, 分数65.00
---------------末行显示---------------
请输入要操作的指令sort
排序完成
请输入要操作的指令print
---------------学生信息---------------
学号101, 姓名小红 , 分数85.50
学号102, 姓名张大炮, 分数65.00
学号103, 姓名张伟 , 分数90.00
学号105, 姓名小明 , 分数88.80
---------------末行显示---------------
请输入要操作的指令reverse
链表逆序成功
请输入要操作的指令print
---------------学生信息---------------
学号105, 姓名小明 , 分数88.80
学号103, 姓名张伟 , 分数90.00
学号102, 姓名张大炮, 分数65.00
学号101, 姓名小红 , 分数85.50
---------------末行显示---------------
请输入要操作的指令quit
程序已经退出说明 链表排序和数组排序原理一样只不过把数组是通过下标索引定位具体的元素链表换成了指针变量定位节点数组排序是i操作在链表里换成了p_i - next操作数组的i n换成了链表的p_i - next ! NULL数组的位置交换换成了节点数据域交换注意只是节点数据域交换不是节点交换位置为方便操作先将节点数据整体交换再复原指针域。
三、完整代码演示单文件版
代码演示
#include stdio.h
#include stdlib.h
#include string.h// 一个简单的学生管理系统
typedef struct stu {// 定义数据域int num;char name[32];float score;// 定义指针域struct stu *next;
} STU;// 定义函数打印菜单界面
void func_list(void) {printf(-----------------------------------\n);printf(--insert:插入学生信息 |\n);printf(--print:遍历信息 |\n);printf(--search:查询某个学生的信息 |\n);printf(--delete:删除某个学生的信息 |\n);printf(--free:删除所有学生 |\n);printf(--reverse:链表逆序 |\n);printf(--sort:链表排序 |\n);printf(--quit:退出整个程序 |\n);printf(-----------------------------------\n);return;
}// 定义函数在头部插入学生信息
STU *insert_func_head(STU *head, STU stu_temp)
{// 申请堆区空间存储一个学生的信息STU *new_stu (STU *)malloc(sizeof(STU));if (NULL new_stu){printf(空间申请失败\n);return head;}// 将获取到的学生信息存入申请到的空间*new_stu stu_temp;// 将新的学生节点插入链表// 链表为空if (NULL head){head new_stu;new_stu-next NULL;}// 链表不为空else{new_stu-next head;head new_stu;}return head;
}// 定义函数打印学生信息
void print_func(STU *head)
{// 判断链表是否为空if (NULL head){printf(未添加任何学生信息\n);return;}// 链表不为空遍历学生信息STU *p head;printf(---------------学生信息---------------\n);while(p ! NULL){printf(学号%03d, 姓名%-6s, 分数%.2f\n, p-num, p-name, p-score);p p-next;}printf(---------------末行显示---------------\n);
}// 定义函数在尾部插入学生信息
STU *insert_func_tail(STU *head, STU stu_temp)
{// 申请堆区空间存储一个学生的信息STU *new_stu (STU *)malloc(sizeof(STU));if (NULL new_stu){printf(空间申请失败\n);return head;}// 将获取到的学生信息存入申请到的空间*new_stu stu_temp;new_stu-next NULL;// 将新的学生节点插入链表// 链表为空if (NULL head){head new_stu;}// 链表不为空else{STU *p head;while(p-next ! NULL){p p-next;}p-next new_stu;}return head;
}// 定义函数按照学号顺序插入
STU *insert_func_sequence(STU *head, STU stu_temp)
{// 申请堆区空间存储一个学生的信息STU *new_stu (STU *)malloc(sizeof(STU));if (NULL new_stu){printf(空间申请失败\n);return head;}// 将获取到的学生信息存入申请到的空间*new_stu stu_temp;new_stu-next NULL;// 将新的学生节点插入链表// 链表为空if (NULL head){head new_stu;}// 链表不为空else{// 定义两个指针pa用于寻找插入位置pb用于保存pa的上一个节点位置STU *pa head, *pb head;while((pa ! NULL) (pa-num new_stu-num)){pb pa;pa pa-next;}// 插入链表最后一个if (NULL pa){pb-next new_stu;// new_stu pb-next;}// 插入链表第一个else if(pa head){new_stu-next head;head new_stu;}// 插入到链表的中间else{pb-next new_stu;new_stu-next pa;}}return head;
}// 定义函数查找学生信息
STU *search_func(STU *head, char *name)
{STU *p head;// 判断链表是否为空if (NULL head){printf(未添加任何学生信息\n);return NULL;}else{while((strcmp(name, p-name) ! 0) (p-next ! NULL)){p p-next;}if (strcmp(name, p-name) 0)return p;elsereturn NULL;}
}// 定义函数删除指定学号学生信息
STU *delete_func(STU *head, int num)
{// 定义两个指针一个用于查找另外一个用于STU *pa head, *pb head;// 判断链表是否存在if (NULL head){printf(未添加任何学生信息\n);return head;}else{while ((pa-num ! num) (pa-next ! NULL)){pb pa;pa pa-next;}// 如果要删除的信息存在if (pa-num num){// 节点在头部if (pa head){head head-next;printf(已删除信息%d\n, pa-num);free(pa);}// 节点在尾部
// else if (pa-next NULL)
// {
// pb-next NULL;
// free(pa);
// }// 节点在中尾部else{pb-next pa-next;printf(已删除信息%d\n, pa-num);free(pa);}}// 信息不存在elseprintf(要删除的信息不存在\n);}return head;
}// d定义函数清空学生信息
STU *free_func(STU *head)
{STU *p head;// 判断链表是否为空if (NULL head){printf(未添加任何学生信息\n);return head;}while (p ! NULL){head head-next;free(p);p head;}printf(学生信息已清空\n);return NULL;
}// 定义函数逆序整个链表
STU *reverse_func(STU *head)
{// 定义两个指针变量pa的next用于指向前一个节点pb指向pa下一个节点STU *pa head, *pb head;// 判断链表是否存在if (NULL head){printf(未添加任何学生信息\n);return head;}else{pa head-next;head-next NULL;while(pa ! NULL){pb pa-next;pa-next head;head pa;pa pb;}printf(链表逆序成功\n);}return head;
}// 定义函数为链表排序
void sort_func(STU *head)
{// 判断链表是否存在if (NULL head){printf(未添加任何学生信息\n);return;}else{STU *p_i NULL;for (p_i head; p_i-next ! NULL; p_i p_i-next){STU *p_min NULL, *p_j NULL;for (p_min p_i, p_j p_i-next; p_j ! NULL; p_j p_j-next){if (p_min-num p_j-num)p_min p_j;}if (p_min ! p_i){// 整体交换节点成员STU temp *p_min;*p_min *p_i;*p_i temp;// 将指针域恢复原样temp.next p_min-next;p_min-next p_i-next;p_i-next temp.next;}}printf(排序完成\n);}
}int main() {// 调用函数打印功能菜单func_list();// 定义一个链表头STU *head NULL;// 获取指令char cmd[16] ;while(1){printf(请输入要操作的指令);scanf(%s, cmd);if (strcmp(insert, cmd) 0){// 定义临时变量用于接收输入的学生信息STU stu_temp;int n 0;printf(请输入要添加的学生的个数);scanf(%d, n);printf(请输入学生信息(学号 姓名 分数):);// 调用函数添加学生信息int i 0;for (i 0; i n; i){scanf(%d %s %f, stu_temp.num, stu_temp.name, stu_temp.score);// 调用函数添加学生信息// head insert_func_head(head, stu_temp); // 头部插入head insert_func_tail(head, stu_temp); // 尾部插入// head insert_func_sequence(head, stu_temp); // 顺序插入}printf(已添加%d位学生信息\n, n);}else if (strcmp(print, cmd) 0){// 调用函数打印学生信息print_func(head);}else if (strcmp(search, cmd) 0){char name[32] ;printf(请输入要查找的学生姓名);scanf(%s, name);// 定义一个指针变量保存查找到的值STU *ret search_func(head, name);if (ret NULL)printf(未找到该学生信息\n);else{printf(---------------学生信息---------------\n);printf(学号%03d, 姓名%-6s, 分数%.2f\n, ret-num, ret-name, ret-score);printf(---------------末行提示---------------\n);}}else if (strcmp(delete, cmd) 0){int num 0;printf(请输入要删除的学生学号);scanf(%d, num);// 调用函数删除指定学号信息head delete_func(head, num);}else if (strcmp(free, cmd) 0){unsigned int password 0;printf(请输入密码验证);scanf(%u, password);if (password 123456)head free_func(head);elseprintf(密码错误无权操作\n);}else if (strcmp(reverse, cmd) 0){// 调用函数逆序链表head reverse_func(head);}else if (strcmp(sort, cmd) 0){// 调用函数为链表中学生按照学号排序sort_func(head);}else if (strcmp(quit, cmd) 0){printf(程序已经退出\n);break;}else{printf(请输入有效命令\n);}}return 0;
}说明在实际项目中不会把所有的代码都放入一个文件中一般都是多文件编程main.c里面只放主函数代码其它具体的功能函数会放到某个单独的文件里实现某一类特定功能如func.c然后创建一个头文件func.h将func.c中定义的函数在头文件里声明最后main.c里包含头文件即可#include func.h。
