分类:Linux C

Home / 分类:Linux C

层序遍历

2014-12-17 23:40:01 | Linux C | 没有评论

本来以为四种遍历方法用递归都很容易解决,谁知看上去最直观的层序遍历不是太容易,参考了下通过链式队列的实现算法,完成了这项遍历

首先将根结点数据输出,并将根结点入队列,然后前端结点出队列,并输出该结点的数据域,如果该结点的左右孩子结点存在,也入队列,由于一个结点的孩子结点在该结点所在层的下一层,而且左孩子结点会在右孩子结点之前入队列,所以如此就能满足层序遍历的顺序,持续地出队列,输出数据域,入队列过[……]

Read more

二叉树遍历

2014-12-17 00:57:32 | Linux C | 没有评论

二叉树的遍历方式有多种,名字天花乱坠,没必要去死记,不管是前序,后序等等,关键以双亲结点为中心,所谓前序还是后序实质上就是一个双亲结点和左右子结点为一个小的集体中双亲结点是先遍历还是后遍历,然后许多这样的小集体不停递归的过程,知道了这点,根据不同的遍历方式,首先认准双亲结点啥时候遍历,然后找好先后关系,很容易就能够画出来遍历结果,下面这些情况也就迎刃而解了

前序遍历:先访问根结点,然后前序遍历左子[……]

Read more

2014-12-17 00:54:16 | Linux C | 没有评论

普通的树有很多种表示方法

双亲表示法,data是数据域,存储结点的数据信息,而parent是指针域,存储该结点的双亲在数组中的下标

树的双亲表示法数据结构:

typedef int TElemType;

typedef struct PTNode {

    TElemType data;

    int parent;

}PTnode;[……]

Read more

双向链表

2014-12-14 01:20:52 | Linux C | 没有评论

单链表总是从头到尾来寻找结点,有了next指针,需要查找下一个结点的时间复杂度为O(1),但是如果要查找的是上一个结点的话,最坏的时间复杂度是O(n),原因是因为每次都必须要从头开始遍历查找

双向链表是在单链表的每个结点中,再设置一个指针,因此每个结点都有指针,分别指向直接后继和直接前驱,所以从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱和后继结点

双向链表数据结构

typedef s[……]

Read more

malloc

2014-12-12 00:51:29 | Linux C | 没有评论

在内存的动态存储区中分配一定长度的连续空间,返回一个指向所分配的连续存储空间的起始地址的指针;动态分配是在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法;动态内存分配不像数组等静态内存分配方法那样预先分配存储空间,而是由系统根据程序的需要即时分配,而且分配的大小是程序要求的大小

malloc库函数的参数是一个无符号整型,当函数没有成功分配存储空间的时候,就会返回一个NULL指针,因此在[……]

Read more

查询驱动支持的网卡类型

2014-12-11 00:51:24 | Linux C | 没有评论

首先查询该机器的网卡类型,通过命令可以查看到各种类型网卡

# lspci | grep Net
02:00.0 Ethernet controller: Intel Corporation I350 Gigabit Network Connection (rev 01)
02:00.1 SCSI storage controller: Intel Corporation I350 Gigabit Ne[……]

Read more

串的存储结构

2014-12-9 00:49:36 | Linux C | 没有评论

串是由零个或者多个字符组成的有序序列,又叫字符串

串的逻辑结构和线性表相似,但是串针对的是字符集,也就是串中的元素都是字符,更关注的是查找子串的位置,得到,替换指定位置的子串,线性表更关注的是单个字符的操作,比如查找,插入,删除一个元素

串顺序存储结构是用一组地址连续的存储但愿来存储串种的字符序列的,按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区,一般是用定长数组来定义

顺序串数据结[……]

Read more

队列链式存储结构

2014-12-7 23:48:17 | Linux C | 没有评论

队列的链式存储结构其实就是线性表的单链表,只不过它只能尾进头出而已,为了方便,将队列头指针指向队列的头结点,队尾指针指向终端结点

空队列时,front和rear都指向头结点,此时已经有一个结点了,所以有一点要注意的就是在出队的时候,都是讲头结点的后继结点出队,这一点刚在写的时候一直出错

链式队列数据结构:

typedef int QElemType;

typedef struct QNode {

[……]

Read more

循环队列

2014-12-7 01:24:36 | Linux C | 没有评论

一晚上到处转弯,本来顺序队列说好的出队之后,所有元素都要相应移动的,这会又突然出来一个循环队列,看样子不是这规矩

队列如果后面满了,就再从头开始,也就是头尾相接的循环,这种头尾相接的顺序存储结构为循环队列

由于空队列的时候,front等于rear,可如今这样队列后面满了就从头开始的,那么整个队列满了的时候front也等于rear,就会产生矛盾,弄一个flag不太方便,所以设定队列为空的条件还是fr[……]

Read more

顺序队列出队列的特点

2014-12-6 23:47:43 | Linux C | 没有评论

上篇草草了事以为OK,实际上根本没弄清楚FIFO的特点,那段程序输出的结果是从下标3开始的,也就是0,1,2三个元素给pop了之后,原封不动地将其他元素输出来,本以为自己做完了,其实一开始就错了

队列的入队只需要队尾插入一个元素,然后下标加1;但是队列的出队是在队头,也就是下标为0的位置,如果有元素出队,其它所有的元素都必须要向前移动,以保证队列的队头,也就是下标为0的位置不能为空

队列出队列一定[……]

Read more

队列顺序存储结构

2014-12-6 23:14:05 | Linux C | 没有评论

公司的产品比较核心的地方用到了一个FIFO,虽然从没有去看看到底有多么复杂,但自己摸索下简单的队列还是可以滴,队列只允许在一端来进行插入操作,而在另一端来进行删除操作的线性表,也就是一种先进先出的线性表,First In First Out,所以就叫FIFO,插入的一端为队尾,删除的一端为队头,这样比较符合思维

数据结构:

typedef int QElemType;

typedef struct[……]

Read more

栈链式存储结构

2014-12-6 00:26:45 | Linux C | 没有评论

栈顶用来做插入和删除操作,而单链表有个头指针,并且栈顶指针也是必须的,所以将它们合二为一,将栈顶放在单链表的头部,由于有了栈顶在头部,单链表中比较常用的头节点也没什么意义了,因此一般来说链栈不需要头结点,链栈为空也就是top=NULL

链栈数据结构:

typedef struct {

    StackElemType data;

   [……]

Read more

栈顺序存储结构

2014-12-4 00:53:10 | Linux C | 没有评论

栈是限定仅在表尾来进行插入和删除操作的线性表,能够插入和删除的一端称为栈顶,它是一个特殊的线性表,但也有前驱后继关系

由于限定了插入和删除的位置,始终只在栈顶来进行,因此栈底是固定的,最新进栈的元素肯定在栈底,因此用数组下标为0的一端作为栈底比较好,因为首元素都在栈底,变化最小

定义一个变量top来表示栈顶元素在数组中的位置,由于栈顶是可以随意操作的,因此top就像可以来回移动一样,变大或者变小,[……]

Read more

处理简单单链表

2014-11-30 20:39:18 | Linux C | 没有评论

果然是看代码容易,写起来麻烦,一个普通的链表处理,被一堆指针符号和结构体绕来绕去,写惯脚本语言再来研究这些真麻烦,勉强写完了,刚本来rand()给data赋值,结果编译通过了没问题以为完工,然后测试了一把,没用rand()直接赋值,果然结果是错的(因为rand是不清楚到底给链表赋值的对不对),菜鸟就先不要计较代码质量了,能出来再说,(-__-)b

#include <stdio.h>
#[……]

Read more

线性表链式存储结构

2014-11-30 12:52:45 | Linux C | 没有评论

顺序存储结构最大的缺点就是在插入和删除时需要移动大量的元素耗费较多时间,原因是相邻的两元素的存储位置也是相邻关系,也就是在内存中的位置也是挨着的,中间没有空隙,当然就无法快速介入,删除后当中会留下空隙,需要弥补

通俗思路:我们反正也是要相邻元素之间留有足够余地,干脆所有的元素都不考虑相邻位置了,哪有空位置就到哪里,只是让每个元素知道它下一个元素的位置在哪里,这样,可以在第一个元素就知道第二个元素的[……]

Read more

指针

2014-11-29 15:48:19 | Linux C | 没有评论

将《让你不再害怕指针》又扫了一遍,菜鸟每次都有不同的收获

指针的值是指针本身存储的数值,这个值将被编译器当作一个地址,而不是一个一般的数值。在32位程序里,所有类型的指针的值都是一个32位整数,因为32位程序里内存地址全都是32位长。指针所指向的内存区就是从指针的值所代表的那个内存地址开始。长度为sizeof(所指向的类型)的一片内存区。一个指针的值是XX,就相当于说该指针指向了以XX为首地址的一[……]

Read more

线性表顺序存储结构

2014-11-28 00:06:39 | Linux C | 没有评论

顺序存储结构有三属性:

1:存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置

2:线性表的最大存储容量:数组长度MaxSize

3:线性表的当前长度:length

#define MAXSIZE 20

typedef int ElemType;

typedef struct

{

    ElemType data[MAXSIZE];

 &[……]

Read more

算法复杂度

2014-11-26 22:35:14 | Linux C | 没有评论

每天学习一点,不求囫囵吞枣,只求坚持

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作

时间复杂度比较好算,大小关系依次:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

空间复杂度通过计算算法所需[……]

Read more

结构,类型

2014-11-25 23:39:47 | Linux C | 没有评论

最近感觉数据结构方面实在欠缺,对于菜鸟来说,得每晚努力学习学习,可以说数据结构从来就没懂过,逼着补补课

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合

 

逻辑结构

1:集合结构

集合结构中的数据元素除了同属于一个集合之外,它们之间就没有其他关系。我的感觉就是所有元素同属于一个类似数学中集合

2:线性结构

线性结构中的数据元素之间是一对一的关系。

3:树形结构

树形结构中的数[……]

Read more

编译器优化的能力和局限性

2014-11-1 12:17:24 | Linux C | 没有评论

记得3年前涛哥来面试的时候,就被提问到关于O2,O0编译的问题,我当时听起来就是天书。gcc给用户提供了一些使用优化的控制,制定优化级别,-O1是使用一组基本的优化,-O2或者-O3会使用更全面的优化,这样做可以提高性能,但是也会使得标准的调试工具更难对程序进行调试。平时一般程序运行都是-O2,debug的时候Makefile里修改为-O0然后进行

 

下面部分摘自《深入理解[……]

Read more