双向链表,我们曾经拿了一幅非常形象的图片来形容他,就像几个人手拉手围成一个圈一样。在我们代码中的呈现就是每个节点都有一个指向下一个节点的指针,同时也有一个指向上一个节点的指针。就因为新增了这个指向上一个节点指针的特性,它解决了单向循环链表的诸多问题,如下:
循环链表解决约瑟夫问题
循环链表的存在很难想象他的应用范围到底是哪里,本文主要介绍的是通过循环链表处理解决约瑟夫问题,让大家更深刻的理解循环链表的使用和应用场景。
循环链表的增删改查
循环链表与单向链表十分相似,两者唯一不同之处就是,循环链表的尾节点的next属性指向了链表的首节点(非头节点,头节点是没有数据的,头节点的下一个有数据的节点我们称为首节点)。他的表现形式有常见的两种,如下图:
线性表顺序储存
线性表,是一个或多个数据元素的集合,数据之间是连续的一段内存。线性表的特性如下。
- 数据元素之间是有顺序的
- 数据元素个数是有限的
- 数据元素的类型必须相同
STL 常用方法集合
我本想将 STL 中各种容器的实现方法和作用全部写一遍,然后每种容器都发一篇文章,但后来发现这样做的意义不大,在 MSDN 或其他一些帮助文档中,他们比我写的要详细,其实我只需要记住每种容器的常用方法,和在什么场合选择合适的容器。下面这张表是我这里的一些常用方法集合。备用参考。
练习题目“涨工资”
有一个员工文件salary_back.txt,salary_back.txt文件每行 为部门职员的姓名:工资(如tom:20000),题目要求:
- 求出该公司有多少人。
- 从工资文件salary_back.txt中读入全部工人,全部增加100元工资后并保存信息到文件salary.txt中。
- 将加工资之后的所有员工按工资进行降序排序,将排序后的结果选出工资最高TOP10在屏幕上输出。
双向链表创建/插入/删除/排序
双向链表有别于单向链表,对于数据的排列、查找更加方便,但需要付出的小小代价则是在数据结构中增加一个指向上一个节点的指针,除了结构上的变化,对于我们理解也相对复杂了一些。
二分查找(折半查找)法
二分查找的前提是数据一定要有序,否则一切皆为空谈。通过有序的一段数据使用二分查找较常规遍历查找算法速度要快一些。其中二分查找发有两种实现,一种为常规while循环,另外一种为递归。具体的实现步骤如下:
数组快速排序
快速排序是在数据源中抽取一份数据作为样本,与所有需要排列的数据进行对比,根据需要把比样本小的数据放置到数据源的左侧位置,比样本大的数据放置到数据源的右侧位置。以此来对数据进行排序。具体实现如下:
数组冒泡排序
排序算法中的最常见的冒泡排序,简单容易理解,文章中带有冒泡排序的基本示意图,可参考示意图再参考代码学习分析。