当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 学习笔记 > 数据结构基础知识大全(学霸笔记)

数据结构基础知识大全(学霸笔记) 时间:2018-08-09      来源:未知

一、学习知识点:

1、顺序表、链表

2、顺序栈、链栈

3、顺序队列、链式队列

4、树

5、图&哈希表

二、学习内容

1、

(1)顺序表:简记:立个flag标记最后有效元素的位置。特点:查找快,删、增慢。插入的元素从前面逐个插入。

(2)链表:头插、尾插。单向或双向循环链表要注意头结点与尾节点的连接

在链表操作中经常出现段错误的原因:当用指针进行地址操作时由于指针是个变量,可以表示某个地址也可表示NULL,因为操作时对指针变量进行的赋值操作可能会导致指针被赋予NULL,再对此时的指针进行地址偏移操作就会产生段错误。另一个需要注意的问题:指针不仅要关注被赋予的是不是地址,大小是否匹配,在链表操作中还要关注操作对象

2、

(1) 顺序栈:也是立个int 型 flag,像操作数组一样 -1为空,N-1时为满,flag自增时放数据,删除时先把数据取出记录,flag自减

(2) 链栈:一、只有链表 先把头结点的下家初始为空,然后采取头插法,只是头结点的下家为空时栈空,之后头结点一直往栈顶升。删除:先用个指针把头结点的下家记录下来,再把头结点的下家的信息记录下来,然后头结点与头结点下家的下家连接上后就可删除了

3、

(1) 顺序队列:立两个flag(头和尾),头尾相等时为空,尾加1对数组长度取模等于头满

(2) 链式队列:用链表操作,一个结构体记录信息和下家,另一个结构体为节点类型的指针分别用于指向头和尾节点,此队列只有空没有满的情况。申请空间的时候先为有两个节点类型的指针的结构体申请,然后通过指针解引用申请一个节点类型的空间,用这两个指针接收地址,接着将指向头结点的指针的下家初始化为NULL,其实就是初始化链表,当头节点的下家为空时队列为空。

4、

(1)树的创建和前序(根 左 右)、中序(左 根 右)都采用递归的方法

(2)树的层次遍历:用链式队列操作,主要是将树的某个节点的数据和左右子节点封装成一个数据,再让其充当链表操作中的数据元素的位置。

(3)非递归先序遍历树:用链栈操作 做法与树的层次遍历相同。

(4)完全二叉树:也采用递归的方式创建,在创建的时候传两个参数,一个是节点总数,一个是传进去的节点号(节点内的数据等于节点号时),然后利用节点的左子节点为节点的节点号*2,右节点为节点的节点号*2+1判断条件,满足左右子节点都小于等于最大节点号则递归创建,不满足则返回空。

5、

图分为有向图和无向图,有向图是单向的,无向图是双向的。图的算法有深度优先算法(相当于树的前序遍历)、广度优先算法(相当于树的层次遍历)

哈希表 用链表操作 一个存放普通数据数组 一个节点类型数组:初始化数组成员数据为0,指针next为空,这个节点类型的数组相当于一排并排的头结点,位置由数组下标标示。然后将数组中的数据对数组长度取模计算数据存放下标,后面就是链表的操作。

三、经验小结

例:球钟问题 将这个问题的各种可重复单一功能封装成函数,后期调用即可,在main函数中写逻辑调用即可。这种做法类似于文件io操作,别人提供的库函数就是实现某一可重复单一功能,将要的任务在main中写逻辑,遇到相应的要做的功能直接调用即可。

编写代码时常犯错误:

头文件忘记打(带有退出状态)

全局变量一般不在头文件中定义,在头文件中定义头文件的话就不能将头文件初始化为0,数组要加static

一个程序本质上都是由 bss段、data段、text段三个组成的。在采用段式内存管理的架构中(比如intel的80x86系统),bss段(Block Started by Symbol segment)通常是指用来存放程序中未初始化的全局变量的一块内存区域,一般在初始化时bss 段部分将会清零。bss段属于静态内存分配,即程序一开始就将其清零了。

比如,在C语言之类的程序编译完成之后,已初始化的全局变量保存在.data 段中,未初始化的全局变量保存在.bss 段中。

全局变量,静态变量默认初始化

数组的初始化只能在定义时用,特别要注意结构体指针内有数组,为其malloc申请空间时

未定义错误;

指针的定义 例:int *a,*b;(a,b都是指针)

int *a,b;(a是指针,b不是)在定义指针时,将

*与变量当做一个整体来看以表示是一个指针变量;

将结构体成员没有解引用或引用就直接使用造成未定义错误

C语法错误:例如:指针 按照c的规则,静态的指针赋值操作或偏移操作是没有错误的,但在程序中,常用变量来代替值,而一个程序中的变量经常会变,例当指针的值在某一刻被赋空值又对这个指针进行偏移操作或其他不应有的操作就会出现断错误,也属于c语法错误,在编程中要关注编写时指针变量对应的地址,大小,对象以及程序运行后变量的值发生的变化,以及发生了变化后对其进行的操作

链接错误:忘记链接库

在编程时对一个变量的关注的:1.变量类型,普通类型,结构体类型,指针类型,数组,变量的值会发生变化,对发生变化后的变量进行的操作可能造成的结果

对不同类型的变量的使用要符合语法

数据类型是对取值范围和运算方式的限定

队列和栈本质都是线性表

头文件:函数声明,函数实现,结构体定义

不能对表达式和常量赋值

结构体指针:->

结构体:.

顺序表:数组是存储数据的容器,为这个容器定义一些

增删查改的运算,把这个集合称为顺序表

段错误:空指针,非法指针

$?(返回上一条shell指令执行的结果)

exit()终止进程 头文件

return 让当前函数返回

main函数return 后面也有一个exit

char * p;

%p ,p 打印p的值

printf()语句是从右往左执行的

顺序表查找快,插入删除慢,链表相反

要关注指针指向的对象。

可以百度关于链表的面试题。

栈本质上是一个实现后进先出的线性表

上一篇:QT开发入门基础及界面的建立原理

下一篇:库及i/o函数的课堂笔记

热点文章推荐
华清学员就业榜单
高薪学员经验分享
热点新闻推荐
前台专线:010-82525158 企业培训洽谈专线:010-82525379 院校合作洽谈专线:010-82525379 Copyright © 2004-2022 北京华清远见科技集团有限公司 版权所有 ,京ICP备16055225号-5京公海网安备11010802025203号

回到顶部