以图明志

数据结构

计算机基础:字符,字节与编码

时常出现的乱码仍然困扰着大家
“字符与编码”是一个被经常讨论的话题。即使这样,时常出现的乱码仍然困扰着大家。虽然我们有很多的办法可以用来消除乱码,但我们并不一定理解这些办法的内在原理。而有的乱码产生的原因,实际上由于底层代码本身有问题所导致的。因此,不仅是初学者会对字符编码感到模糊,有的底层开发人员同样对字符编码缺乏准确的理解。

计算机数学与基础

什么是僵尸进程(zombie)?

僵尸进程常见问题
僵尸进程是指一个已经终止、但是其父进程尚未对其进行善后处理获取终止进程的有关信息的进程,这个进程被称为“僵尸进程”(zombie)。 一个进程在调用exit命令结束自己的生命的时候,其实它并没有真正的被销毁,而是留下一个称为僵尸进程(Zombie)的数据结构。

计算机算法

算法导论:选择排序的原理与实现

swf动画图解
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

数据结构

结构之美:双向循环链表的结构与定义

从图中直观认识双向链表
双(向)链表中有两条方向不同的链,即每个结点中除next域存放后继结点地址外,还增加一个指向其直接前趋的指针域prior。注意:链表由头指针head惟一确定的。带头结点的双链表的某些运算变得方便。将头结点和尾结点链接起来,为双(向)循环链表。

数据结构

单循环链表的初始化、创建、删除、查找与遍历

单循环链表的基本操作
循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。链表、双链表、单循环链表、双循环链表 的实现代码都差不多,区别只是在对指针域的修改。下面,是对单循环链表的实现。

数据结构

数据结构一些常见术语的中英文对照

建议ctrl + f查找使用本文
数据结构的一些常见术语的中英文对照,很多场合都可以用到,比如编程命名的时候,反正我觉得挺有用的,就收集在这里了。建议ctrl + f查找使用本文。

数据结构

循环链表与约瑟夫环问题

练习单循环链表这个数据结构
约瑟夫问题:编号为1~N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数),开始人选一个正整数作为报数上限值M,从第一个人按顺时针方向自1开始顺序报数,报道M时停止报数。报M的人出列,将他的密码作为新的M值,从他顺时针方向上的下一个人开始从1报数,如此下去,直至所有人全部出列为止。

数据结构

几种常见的循环链表介绍

与单链表相似但有区别
循环链表的运算与单链表的运算基本一致,不同的有以下几点:在建立一个循环链表时,必须使其最后一个节点的指针指向表头节点,而不是像单链表那样置为NULL。此种情况适用于在最后一个节点后插入一个新节点。判断是否到表尾采用判断该节点链域的值是否是表头节点的方法,当链域值等于表头指针时,说明已到表尾,而不是像单链表那样判断链域值是否为NULL。

数据结构

判断两个链表是否相交的思路

合并链表转化为环问题
给出两个单向链表的头指针,比如h1,h2,判断这两个链表是否相交。(如图,假设两个链表均不带环)最直观的解法就是判断第一个链表中的每个节点是否在第二个链表中。这种方法的时间复杂度是O(Length(h1)*Length(h2))。将两个链表首尾相接,判断相接后的链表是否有环,若有环,则说明两个链表相交。

数据结构

用快慢指针判断单链表环,找到环入口

扩展到判断两个链表是否相交
快慢指针在解决单链表环问题的时候是非常有用的,下面来探讨一下单链表的环的一些问题。有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

数据结构

腾讯面试题:快速找到未知长度单链表的中间节点

快慢指针在单链表中很有用处
普通的方法很简单,首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点出发循环L/2次找到单链表的中间节点。算法复杂度为O(L+L/2)=O(3L/2)。能否再优化一下这个时间复杂度呢?有一个很巧妙的方法:设置两个指针*search、*mid都指向单链表的头节点。其中* search的移动速度是*mid的2倍。当*search指向末尾节点的时候,mid正好就在中间了。这也是标尺的思想。

数据结构

结构之美:获取单链表倒数第N个结点值

距离——标尺的方法
这是一个比较常见的面试算法题:一次遍历找链表倒数第n个节点。不管是顺数n个还是倒数n个,其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量,我们能够判断倒数第一个节点,因为他的next==NULL。如果我们用两个指针,并保持他们的距离为n,那么当这个线段的右端指向末尾节点时,左端节点就指向倒数第n个节点。

数据结构

结构之美:判断单链表中是否有环

两种判定方法介绍
有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过6之后,会重新回到3,那么我们可以在遍历时使用两个指针,看两个指针是否相等。方法一:使用p、q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样。

数据结构

结构之美:单链表逆序

让单链表逆序输出
题目:已知单向链表的头结点head,写一个函数把这个链表逆序 (Intel)。这个题目算是考察数据结构的最基础的题目了,下面我们一步步解析这个算法步骤。首先我们创建一个新结点 current p1,并且让它指向首元结点,即 current p1 = L -> next;然后我们创建另外一个新结点 pnext p2,用来保存当前节点的下一个节点,即 pnext p2 = current p1 -> next;

数据结构

《编程之美》3.4:没有头结点的单链表如何删除结点

一个巧妙的思路
题目:假设有一个没有头结点的单链表。一个指针指向此单链表中间的一个节点(非第一个节点, 也非最后一个节点)。请将该节点从单链表中删除。典型的“狸猫换太子”, 若要删除该节点,正常情况下,应该要知道该节点的前面节点的指针,但是由于单链表中没有头结点,所以无法追溯到该节点前面的那个节点,因此,这里采用了“移花接木”的方法。

数据结构

结构之美:删除单链表指定位置的数据

单链表删除结点
删除单链表指定的某个结点是单链表的一个基本操作。删除操作大致分为如下三种:删除p所指向结点的后继结点(假设存在),删除p所指向的结点。删除线性表中值为x的数据元素。大致算法思想:删除运算是将表的第i个结点删去。删除结点算法的时间复杂度和插入结点一样,也是O(n)。链表上实现的插入和删除运算,无须移动结点,仅需修改指针。
20 / 22 首页 < Prev 18 19 20 21 22 Next > 尾页 页码: