Qz 学算法 - 数据结构篇 (链表、栈)
链表(Linked List)
链表是有序的列表,但是它在内存中是存储如下
介绍
链表是以节点的方式来存储,是链式存储
每个节点包含 data 域,next 域:指向下一个节点.
如图:发现链表的各个节点不一定是连续存储
链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定
1.单链表
单链表(带头结点)逻辑结构示意图如下
1.1 单链表的创建和遍历
添加
先创建一个 head 头节点,作用就是表示单链表的头
后面我们每添加一个节点,就直接加入到链表的最后
遍历
通过一个辅助变量遍历,帮助遍历整个链表
代码实现
要创建两个对象一个是节点对象,一个是链表对象
做 add 添加时,先找到链表的最后,如果这个链表没有最后,那么我们加入的这个 node 节点就是这次的头指针指向下一个节点
1.2 按顺序插入
代码实现
这里我们把 hero.next=temp.next 操作是因为,我们要插入一个节点,那么就需要让索引后移一维,即插入位置的后一个节点指向临时变量节点指向的后一个节点,临时变量指向的节点等于要插入的节点
我们按照 1423 的顺序插入
1.3 修改节点信息
代码实现
1.4 删除节点
思路
我们先找到需要删除的这个节点的前一个节点 temp
temp.next =temp.next.next
被删除的节点,将不会有其它引用指向,会被垃圾回收机制回收
代码实现
2.双向链表
2.1 单链表的缺点
单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到 temp 的下一个节点来删除的
2.2 双向链表的操作思路
遍历方式和单链表一样,只是可以向前查找.也可以向后查找
添加(默认添加到双线链表的最后)
先找到双线链表的最后这个节点
temp.next = newHeroNode
newHeroNode.pre=temp
修改思路和原来的单向链表一样
删除
因为是双向链表,因此,我么可以实现自我删除某个节点
直接找到要删除的这个节点,比如 temp
temp.pre.next = temp.next
temp.next.pre = temp.pre
2.3 代码实现
3.环形链表和约瑟夫问题
3.1 引入
Josephus(约瑟夫、约瑟夫环)问题
Josephus 问题为:设编号为 1,2,…n 的 n 个人围坐一圈,约定编号为(1<=k<=n)的人从 1 开始报数,数到 m 的那个人出列,它的下一位又从 1 开始报数,数到 m 的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
提示:
用一个不带头结点的循环链表来处理 Josephus 问题:先构成一个有个结点的单循环链表,然后由结点起从 1 开始计数,计到 m 时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从 1 开始计数,直到最后一个结点从链表中册则除算法结束。
3.2 思路
构建一个单向的环形链表思路
先创建第一个节点,让 first 指向该节点,并形成环形
后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可
遍历环形链表
先让一个辅助指针(变量)curBoy,指向 first 节点
然后通过一个 while 循环遍历该环形链表即可 curBoy.next=first 结束
3.3 代码实现(构建环形链表和遍历)
3.4 代码实现(出圈操作)
1.需求创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点补充:小孩报数前,先让 first 和 helper 移动 k-1 次 2.当小孩报数时,让 first 和 helper 指针同时的移动 m-1 次 3.这时就可以将 first 指向的小孩节点出圈 first = first.nexthelper.next=first 原来 fist 指向的节点就没有任何引用,就会被回收
栈
需求引入
计算式:[7*2*2-5+1-5+3-3]
请问:计算机底层是如何运算得到结果的?注意不是简单的把算式列出运算,因为我们看这个算式 7*2*2-5,但是计算机怎么理解这个算式的(对计算机而言,它接收到的就是一个字符串),我们讨论的是这个问题。=>栈
1.介绍
栈的英文为(stack)
栈是一个先入后出(FILO-First In LastOut))的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另端为固定的一端,称为栈底(Bottom)。
根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除
出栈和入栈的概念(如图所示)
2.应用场景
子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中。
处理递归调用:和子程序的调用类似,只是除了储存下一个指令的地址外,也将参数、区域变量等数据存入堆栈中。
表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
二叉树的遍历。
图形的深度优先(depth 一 first)搜索法:
3.思路分析
使用数组来模拟栈
定义一个 top 来表示栈顶,初始化为 1
入栈的操作,当有数据加入到栈时,top++;stack[top]=data;
出栈的操作,int value=stack[top];top--,return value;
4.代码实现
版权声明: 本文为 InfoQ 作者【浅辄】的原创文章。
原文链接:【http://xie.infoq.cn/article/985d2d098a52ee30f85db8f0b】。文章转载请联系作者。
评论