侧边栏壁纸
博主头像
smallkun博主等级

  • 累计撰写 120 篇文章
  • 累计创建 99 个标签
  • 累计收到 36 条评论
标签搜索

目 录CONTENT

文章目录
计算机基础

数据结构——链表

smallkun
smallkun
2022-05-03 / 0 评论 / 0 点赞 / 553 阅读 / 9,580 字
温馨提示：
本文最后更新于 2023-07-25，若内容或图片失效，请留言反馈。部分素材来自网络，若不小心影响到您的利益，请联系我们删除。

链表

链表基础

链表的概念

引例1建立学生信息表

  • 假设需要建立一个学生信息表，学生人数无法估计，而且学生人数经常发生变化应该如何实现？

image-20220503192443902

单链表：线性表的链接存储结构。

存储思想：用一组任意的存储单元存放线性表的元素。

  • 不连续
  • 零散分布

image-20220503193100965

image-20220503193120510

  • 单链表的结点结构
typedef struct node{
    DataType data;//数据域
    struct node * next;//指针域
}Node, *Link;
  • 如何申请一个结点？
p = (Link) malloc(sizeof(Node));
image-20220503193403215
  • 如何引用数据元素？
(*p).data;
p->data;
  • 如何引用指针域？
p->next
  • 什么是存储结构？

重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。

image-20220503193715607

空表

head = NULL;

非空表

image-20220503193643140
  • 空表和非空表不统一，缺点？如何将空表与非空表统一？

头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。

空表

image-20220503193940412

非空表

image-20220503194000007

单链表的实现

单链表的遍历操作

  • 操作接口:void displayNode(Link head);
void display(Link head){
    p = head->next;
    while(p!=NULL){
        printf("%d ", p->data);
        p = p->next;
    }
}

p++能否完成指针后移？

image-20220503194221036

求单链表的元素个数

  • 操作接口:int length(Link head);

image-20220503194600175

image-20220503194614661

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);

image-20220503195143866

单链表带头结点，表头、表中、表尾三种情况的操作语句一致。

  • 插入操作的算法描述如下

image-20220503195345303

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);

  • 头插法：将待插入结点插在头结点的后面。

image-20220503200715976

image-20220503200729944

image-20220503200806532

image-20220503200817401

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)

  • 尾插法：将待插入给点插在终端结点的后面。

image-20220503203446447

image-20220503203605037

image-20220503203622570

image-20220503203631864

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);

image-20220503204053460

  • 查找结点过程中，如何保证p，q指针一前一后？

image-20220503204351830

image-20220503204405130

  • 删除时注意分析边界情况——要删的表为空表

image-20220503204451488

  • 伪代码

image-20220503204517478

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);
  • 将单链表中所有结点的存储空间释放

image-20220503205607000

void cleanLink(Link head){
    while(head != NULL){
        Link q = head;
        head = head->next;
        free(q);
    }
}

循环链表的实现

image-20220503210704531

image-20220503210716682

循环链表的插入

image-20220503210740828

循环链表的特点

image-20220503210800381

双向链表

image-20220503210827941

image-20220503210838823

学生管理系统

  1. 要求完成学生管理的链表程序。具有学生信息增加、显示、修改、删除、查找、学生人数统计功能的程序。增加学生信息时，按照学号排序；根据给定的学号，可以完成指定学号的修改、删除和查找功能。
  2. 阅读教学视频掌握作业要求（请点击下面的“视频链接”查看）。
  3. 在已有的程序框架内完成程序。
#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) 如果其中一个多项式先比较完，那么另一个多项式余下的部分该怎么处理？

作业要求：
阅读视频理解算法思想，然后根据给定的代码模板完成程序。大家可以复制的代码，然后在需要的地方补全代码完成作业：（懒猫老师版权所有，转发请标明出处)

0
算法 数据结构
版权归属： smallkun
本文链接： https://smallkun.cn/archives/shu-ju-jie-gou--lian-biao
许可协议： 本文使用《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》协议授权

评论区