【一】一起算法

2023-03-20 06:22| 来源: 网络整理| 查看: 265

纸上得来终觉浅，绝知此事要躬行。大家好！我是霜淮子，欢迎订阅我的专栏《算法系列》。

学习经典算法和经典代码，建立算法思维；大量编码让代码成为我们大脑的一部分。

算法指的是一组定义清晰、有限、可执行的操作序列，用于解决特定问题或完成特定任务。算法通常以计算机程序的形式实现，并且可以应用于各种领域，如数学、计算机科学、工程学等。如果想要进一步了解算法的要求以及特性可以点击文章《算法---程序的灵魂》。

前言

1.1、链表

1.1.1、动态链表

1.1.2、静态链表

1.1.3、STL list

前言

以约瑟夫问题为例，分别给出动态链表、静态链表、STL链表的方案。

1.1、链表

链表的概念

链表：用一组任意的存储单元存储线性表的数据元素（存储单元可以连续也可以不连续）。链表操作：初始化、添加、遍历、插入、删除、查找、排序、释放等。单向链表和双向链表

链表的实现方式有多种，最基本的有单向链表和双向链表两种。单向链表中每个节点只包含一个指向下一个节点的指针，而双向链表中每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。

链表的优点在于可以动态添加或删除节点，不需要预先分配固定大小的存储空间。但是，由于链表不支持随机访问，需要通过遍历整个链表才能找到特定的节点，因此在某些场合下可能会影响性能。此外，在使用链表时需要注意链表的头节点，尾节点和指针的处理，避免出现死循环或内存泄漏等问题。

1.1.1、动态链表

动态单项链表

临时分配链表结点、使用完毕后释放链表结点。优点：能及时释放空间，不使用多余内存。缺点：容易出错。

动态单链表实现代码

*//* 题目：有n个人，编号为1-n,按顺序围成一圈，从第1个开始报数，数到m的人出列，在由下一个人重新从1开始报数，数到m的人在出列，以此类推，直到所有的人都出列，请依次输出出列人的序号输入：两个整数n和m，1next=NULL; //分配第一个结点，数据置为1 now = head; //当前指针是头 for(int i=2;idata = i; p->next = NULL; //p是新结点 now->next = p; //把申请的新结点连到前面的链表上 now = p; //尾指针后移一个 } now->next = head; //尾指针指向头：循环链表建立完成 //以上是建立链表，下面是本题的逻辑和流程。后面4种代码，逻辑流程完全一致。 now = head, prev = head; //从第1个开始数 while((n--) >1 ){ for(int i=1;inext; } printf("%d ", now->data); //输出第m结点，带空格 prev->next = now->next; //跳过这个结点 delete now; //释放结点 now = prev->next; //新的一轮 } printf("%d", now->data); //打印最后一个，后面不带空格 delete now; //释放最后一个结点 return 0; } 1.1.2、静态链表

静态链表使用预先分配的一段连续空间储存链表。

用连续空间实现链表，在逻辑上是成立的，具体有两种做法：

定义链表结构体数组，和动态链表的结构差不多；使用一维数组，直接在数组上进行链表操作。

给出使用一维数组实现单向静态链表的代码

#include int nodes[150]; int main(){ int n, m; scanf("%d%d", &n, &m); for(int i=1;i1){ for(int i = 1; i < m; i++){ //数到m，停下 prev = now; now = nodes[now]; //下一个 } printf("%d ", now); //带空格 nodes[prev] = nodes[now]; //跳过结点now，即删除now now = nodes[prev]; //新的now } printf("%d", now); //打印最后一个，不带空格 return 0; } 1.1.3、STL list

list是双向链表，由标准模板库（Standard Template Library,STL）管理，通过指针访问节点数据，高效率的插入和删除。

给出list实现约瑟夫问题的代码：

#include using namespace std; int main(){ int n, m; cin>>n>>m; listnode; for(int i=1;i1){ //list的大小由STL自己管理 for(int i=1;i

【本文地址】

公司简介

联系我们