链表
链表基础
链表的概念
引例1建立学生信息表
- 假设需要建立一个学生信息表，学生人数无法估计，而且学生人数经常发生变化应该如何实现？
单链表：线性表的链接存储结构。
存储思想：用一组任意的存储单元存放线性表的元素。
- 不连续
- 零散分布
- 单链表的结点结构
typedef struct node{
DataType data;//数据域
struct node * next;//指针域
}Node, *Link;
- 如何申请一个结点？
p = (Link) malloc(sizeof(Node));
- 如何引用数据元素？
(*p).data;
p->data;
- 如何引用指针域？
p->next
- 什么是存储结构？
重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。
空表
head = NULL;
非空表
- 空表和非空表不统一，缺点？如何将空表与非空表统一？
头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。
空表
非空表
单链表的实现
单链表的遍历操作
- 操作接口:
void displayNode(Link head);
void display(Link head){
p = head->next;
while(p!=NULL){
printf("%d ", p->data);
p = p->next;
}
}
p++能否完成指针后移？
求单链表的元素个数
- 操作接口:
int length(Link head);
int length(Link head){
Link p = head->next;
int count = 0;
while(p != NULL){
p = p->next;
count++;
}
return count;
}
单链表的查找操作
bool queryNode(Link head, int x){
Link p = p->next;
while(p!=NULL){
if (p->data == x){
printf("%d\n", p->data);//找到划调用输出函数，并提前返回true
return true;
}
}
//如果循环结束了，说明没有找到
return false;
}
单链表的插入操作
- 操作接口:
void insertNode(Link head,int i, Data Type x);
单链表带头结点，表头、表中、表尾三种情况的操作语句一致。
- 插入操作的算法描述如下
bool insertNode(Link head, int i, int x){
Link p = head; //工作指针p指向头结点
int count = 0;
while(p!=NULL && count < i - 1){//查找第i-1个结点
p = p->next;
count++;
}
if (p == NULL)
return false;//没有找到第i-1个结点
else{
Link node = (Link)malloc(sizeof(Node));//申请一个结点node
node->data = x;
node->next = p->next;
p->next = node;//结点node插入结点p之后
return true;
}
}
创建一个单链表—头插法
-
操作接口:
LinknewList(DataType a[], int n); -
头插法：将待插入结点插在头结点的后面。
Link newList(int a[], int n){
//创建头结点
Link head = (Link)malloc(sizeof(Node));
head->next = NULL;
//创建后续结点
for (int i = 0; i < n; i++)
{
Link node = (Link)malloc(sizeof(Node));
node->data = a[i];
node->next = head->next;
head->next = node;
}
return head;
}
创建一个单链表—尾插法
-
操作接口:
Link newList(DataType a[], int m) -
尾插法：将待插入给点插在终端结点的后面。
Link newList(int a[], int n){
Link head = (Link)malloc(sizeof(Node)); //生成头结点
head->next = NULL;
Link rear = head;
for (int i = 0; i < n; i++) //尾指针初始化
{
Link node = (Link)malloc(sizeof(Node));
node->data = a[i];
rear->next = node;
rear = node;
}
rear->next = NULL;
return head;
}
单链表结点的删除
- 操作接口:
bool deleteNode(Link head, Datatype x);
- 查找结点过程中，如何保证p，q指针一前一后？
- 删除时注意分析边界情况——要删的表为空表
- 伪代码
bool deleteNode(Link head, int x){
if (head == NULL || head->next == NULL){//若链表没有数据
return false;
}
Link p = head->next; //初始化。p，q两个指针一前一后
Link q = head;
while(p != NULL){
if (p->data == x){ //找到x节点，删除这个结点，并提前返回
q->next = p->next;
free(p);
return true;
}else{ //p的data域不等于x，则继续向后找
q = p;
p = p->next;
}
}
//如果循环结束了，说明没有找到和×相等的结点
return false;
}
单链表的释放
- 操作接口:
void clearLink(Link head); - 将单链表中所有结点的存储空间释放
void cleanLink(Link head){
while(head != NULL){
Link q = head;
head = head->next;
free(q);
}
}
循环链表的实现
循环链表的插入
循环链表的特点
双向链表
学生管理系统
- 要求完成学生管理的链表程序。具有学生信息增加、显示、修改、删除、查找、学生人数统计功能的程序。增加学生信息时，按照学号排序；根据给定的学号，可以完成指定学号的修改、删除和查找功能。
- 阅读教学视频掌握作业要求（请点击下面的“视频链接”查看）。
- 在已有的程序框架内完成程序。
#include <stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#define NO_LENGTH 20
#define NAME_LENGTH 11
/* 定义学生结构体的数据结构 */
typedef struct Student{
char studentNo[NO_LENGTH];
char studentName[NAME_LENGTH];
}st;
/* 定义每条记录或节点的数据结构 */
typedef struct node
{
struct Student data; //数据域
struct node *next; //指针域
}Node,*Link; //Node为node类型的别名,Link为node类型的指针别名
//定义提示菜单
void myMenu(){
printf(" * * * * * * * * * 菜 单 * * * * * * * * * *\n");
printf(" 1 增加学生记录 2 删除学生记录 \n");
printf(" 3 查找学生记录 4 修改学生记录 \n");
printf(" 5 统计学生人数 6 显示学生记录 \n");
printf(" 7 退出系统 \n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * *\n");
}
void inputStudent(Link l){
printf("请输入学生学号:");
scanf("%s",l->data.studentNo);
printf("请输入学生的姓名:");
scanf("%s",l->data.studentName);
//每个新创建的节点的next域都初始化为NULL
l->next = NULL;
}
void inputStudentNo(char s[],char no[]){
printf("请输入要%s的学生学号:",s);
scanf("%s",no);
}
void displayNode(Link head){
// 填写代码，根据传入的链表head头指针，扫描链表显示所有节点的信息
Link r = head->next;
while(r != NULL){
printf("%s\t%s\n", r->data.studentNo, r->data.studentName);
r = r->next;
}
}
/* 增加学生记录 */
bool addNode(Link head){
Link p,q; //p,q两个节点一前一后
Link node; //node指针指向新创建的节点
node=(Link)malloc(sizeof(Node));
inputStudent(node);
q = head;
p = head->next; //q指向head后面的第一个有效节点
if(head->next==NULL)
//链表为空时
head->next = node;
else {
//循环访问链表中的所有节点
while(p != NULL){
if (node->data.studentNo < p->data.studentNo){
//如果node节点的学号比p节点的学号小，则插在p的前面，完成插入后，提前退出子程序
q->next = node;
node->next = p;
return true;
}
else{
//如果node节点的学号比p节点的学号大，继续向后移动指针（依然保持pq一前一后）
q = p;
p = p->next;
}
}
//如果没能提前退出循环，则说明之前没有插入，那么当前node节点的学号是最大值，此时插在链表的最后面
q->next = node;
}
return true;
}
bool deleteNode(Link head){
// 按照给定的学号删除学生记录，如果删除成功返回true，如果没找到学号返回false
//输入要处理的学号
char no[NO_LENGTH];
inputStudentNo("删除",no);
Link r = head->next;
Link q = head;
while(r != NULL && strcmp(r->data.studentName, no) == 0){
q = r;
r = r->next;
}
if (r != NULL){
q->next = r->next;
free(r);
return true;
}
return false;
}
bool queryNode(Link head){
// 按照给定的学号查询学生记录，如果查询成功返回true，如果没找到学号返回false
//输入要处理的学号
char no[NO_LENGTH];
inputStudentNo("查找",no);
Link r = head->next;
while(r != NULL && strcmp(r->data.studentName, no) == 0){
r = r->next;
}
if (r != NULL){
printf("%s\t%s\n", r->data.studentNo, r->data.studentName);
return true;
}
return false;
}
bool modifyNode(Link head){
// 按照给定的学号找到学生记录节点，如果修改成功返回true，如果没找到学号返回false
//输入要处理的学号
char no[NO_LENGTH];
inputStudentNo("修改",no);
Link r = head->next;
while(r != NULL && strcmp(r->data.studentName, no) == 0){
r = r->next;
}
if (r != NULL){
char name[NAME_LENGTH];
printf("请输入修改后的名字:");
scanf("%s", name);
strcpy(r->data.studentName, name);
return true;
}
return false;
}
int countNode(Link head){
//统计学生人数，扫描链表统计节点个数，返回节点数
Link p;
int count = 0;
p = head->next;
//填充代码
while(p != NULL){
count++;
p = p->next;
}
return count;
}
void clearLink(Link head){
Link q,p;
//遍历链表，用free语句删除链表中用malloc建立起的所有的节点
}
int main() {
int select;
int count;
Link head; // 定义链表
//建立head头结点，在这个程序中head指向头结点，头结点data部分没有内容，其后续节点才有真正的数据
head = (Link)malloc(sizeof(Node));
head->next = NULL;
while(1)
{
myMenu();
printf("\n请输入你的选择(0-7):"); //显示提示信息
scanf("%d",&select);
switch(select)
{
case 1:
//增加学生记录
if(addNode(head))
printf("成功插入一个学生记录。\n\n");
break;
case 2:
//删除学生记录
if(deleteNode(head))
printf("成功删除一个学生记录。\n\n");
else
printf("没有找到要删除的学生节点。\n\n");
break;
case 3:
//查询学生记录
if(queryNode(head))
printf("成功找到学生记录。\n\n");
else
printf("没有找到要查询的学生节点。\n\n");
break;
case 4:
//修改学生记录
if(modifyNode(head))
printf("成功修改一个学生记录。\n\n");
else
printf("没有找到要修改的学生节点。\n\n");
break;
case 5:
//统计学生人数
count = countNode(head);
printf("学生人数为：%d\n\n",count);
break;
case 6:
//显示学生记录
displayNode(head);
break;
case 7:
//退出前清除链表中的所有结点
clearLink(head);
return 0;
default:
printf("输入不正确，应该输入0-7之间的数。\n\n");
break;
}
}
return 0;
}
约瑟夫环的三种解法
什么是约瑟夫环
描述
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
输入
每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：
0 0
输出
对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号
样例输入
6 2
12 4
8 3
0 0
样例输出
5
1
7
约瑟夫环的四种实现方法
用循环链表实现
#include "stdio.h"
#include "stdlib.h"
struct node{
int data;
struct node * next;
};
int main(void){
int n, m;//猴子个数
int i;
int answer[100]; //保存每次的答案，最后统一输出
int count = 0;//用来控制答案题目答案的下标
struct node *head, *tail, *p, *q;//p指向当前节点， q指向p指针前面一个结点
head = (struct node *)malloc(sizeof(struct node));
head->data = -1;
head->next = NULL;
while(1){
scanf("%d %d", &n, &m);
if (n == 0 || m == 0){
break;
}else{
tail = head;
for (int i = 0; i < n; i++)
{
//采用尾插法构建循环链表，用tail指针指向最后一个节点
p = (struct node *)malloc(sizeof(struct node));
p->data = i+1;//填写猴子编号
tail->next = p;//插到尾部
p->next = head->next;//最后的节点的next域指向第一个有效节点,形成循环链表
tail = p;//tail移动到最后一个有效节点，为下一次插入做准备
}
p = head->next;
q = tail; //p在最前面时，最后一个节点是他的前继节点
i = 1;
while(q != p){//p, q总是一前一后，一旦他们相遇则说明找到最后一个猴子
if (i == m){
//把当前节点从链表中删除
q->next = q->next->next;
free(p);
// 将p移动得到下一有效节点上，i=1重新开始报数字
p = q->next;
i = 1;
}else{
//p, q各自向后移动一个节点，其中q总在p的前面
q = p;
p = p->next;
// 报数加1
i++;
}
}
//head->next = q; //前面删除节点时，当最后两个节点时，删除第一个节点的时候，有可能造成链表不完整，在这道题目中可以不要
answer[count] = p->data;
count++;
free(p);
head->next = NULL;//链表已经清空，只有头节点了，将头节点的next域赋值为NULL，虽然不是必须的，缺是一个好习惯
}
}
for (int i = 0; i < count; i++)
{
printf("%d\n", answer[i]);
}
free(head);
return 0;
}
数组标志位实现
#include "stdio.h"
#include "stdlib.h"
int main(void){
int n, m;//n猴子的个数，报数数到m退出
int number;//记录剩余猴子个数
int count = 1;//代表当前的报数
int i, pos;
while(~scanf("%d %d", &n, &m)){
if (n == 0 || m == 0)
return 0;
number = n;
//monkey数组中存储猴子的编号和状态
//存储-1代表无效无效数组部分，0代表退出的猴子，1至n+1代表还没退出的猴子
int monkey[301] = {0};
for (int i = 0; i < n; i++)
{
monkey[i] = i+1;
}
int pos = 0;//控制当前处理的数组的下标
while (number > 1)
{
if (monkey[pos] > 0){
if (count != m){
count ++;//报数
pos = (pos + 1)%n;//当前处理数组下标+1
}else{
monkey[pos] = 0;//标记为0，设置当前猴子出局
count = 1;//报数重新开始
number --;//猴子个数减一
pos = (pos + 1)%n;//当前处理数组下标+1
}
}else{
pos = (pos + 1)%n;//当前处理数组下标+1
}
}
for (int i = 0; i < n; i++)
{
if (monkey[i] > 0)
printf("%d\n", monkey[i]);
}
}
return 0;
}
数组链接方式实现
#include "stdio.h"
int main(void){
int n, m;//n猴子的个数，报数数到m退出
int number;//记录剩余猴子个数
int count;//代表当前的报数
int i, pos, prior;
while(~scanf("%d %d", &n, &m)){
if (n == 0 || m == 0)
return 0;
int monkey[301] = {0};//数组存储下一个猴子的位置，标识为-1的为退出的猴子
//初始化数组，数组存储下一个猴子的下标
for (i = 0; i < n - 1; i++)
{
monkey[i] = i+1;
}
monkey[i] = 0;//下标为n-1的元素的下一个序号为0，形成循环链表
//monkey[i+1]=-2; //将超过范围的元素标识为-2，方便追踪的时候看数组内存
number = n;
pos = 0;
prior = n - 1;
count = 1;
while (number > 1)//也可以不需要number计数，直接将退出条件设置为prior!=pos
{
if (count != m){
prior = pos;//prior保存pos上一个节点的下标
pos = monkey[pos];//pos移动到下一个有效节点的下标
count++;
}else{
monkey[prior] = monkey[pos];//更改链接关系
monkey[pos] = -1;//猴子出局,标识为-1
pos = monkey[prior];//pos移动到下一个有效节点的下标
number--;//猴子的个数-1
count = 1;
}
}
//找出有效的猴子并输出
printf("%d\n", pos + 1);
}
return 0;
}
多项式加法
题目描述：
实现两个一元n次多项式的加法。例如P(A)=x+3x2-5x5+7，P(B)=2x2+6x3+x5-4x6，求P(A)+P(B)。
提示：
首先弄清楚一元多项式的加法原理，然后明确多项式的存储方法。链表节点存储系数和指数，只存系数非0的项。
讨论内容：
(1) 指针ha和hb分别指向两个多项式中当前进行比较的节点，如果指针ha所指节点的指数小于指针hb所指节点的指数值，该怎么处理？
(2) 如果指针ha所指节点的指数等于指针hb所指节点的指数值，该怎么处理？
(3) 如果指针ha所指节点的指数大于指针hb所指节点的指数值，该怎么处理？
(4) 如果其中一个多项式先比较完，那么另一个多项式余下的部分该怎么处理？
作业要求：
阅读视频理解算法思想，然后根据给定的代码模板完成程序。大家可以复制的代码，然后在需要的地方补全代码完成作业：（懒猫老师版权所有，转发请标明出处)
评论区