行业知识
数据结构(C语言版)(复习自用)(持续更新中)
参���课本:数据结构(C语言版)(清华大学出版社)
一、绪论
1、算法特性:
有穷性;确定性;可行性;输入;输出
2、算法应具备以下要求:
正确性;可行性;健壮性;效率与低存储需求
3、算法效率的度量(采用事前分析估计法):
(1)时间复杂度
①时间复杂度只依赖于问题的规模n;
②一般情况,算法中操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作:
T(n) = O(f(n));
③一般情况,对一个问题(或一类算法)只需选择一种基本操作来讨论算法的时间复杂度即可,有事也需要同时考虑几种基本操作,甚至可以对不同的操作赋予不同权值,以反映执行不同操作所需的相对时间,这种做法便于综合比较解决同一问题的两种完全不同的算法(应对考试题目实际上只需要选择时间复杂度中阶最高的一项作为答案即可,记得去掉系数)
④常见阶的大小排序:
1(常量阶)
(2)空间复杂度
①S(n) = O(f(n)),其中n为问题的规模;
②一个上机执行的差唔徐除了需要除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外,也需要以一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。重要的是需要分析输入数据所占空间与除输入和程序之外的额外空间的关系,由于空间复杂度不是考察重点,这里不做赘述
二、线性表
1、线性表的类型定义
(1)本质特性:有且仅有一个直接前驱和后继
(2)若线性表中没有元素,则为空表(注意空表也事先分配空间,并不是不占用空间)
注:具体算法实例请见课本(实例中传参出现了&,其并非取地址,而是双向传参的作用,需要修改并返回该参数则加&,否则不需要,本书中伪代码传参中&均为这一作用;实例中还有一些抽象数据类型等(一串英文单词,对于英语不太好的uu们确实是晦涩6难懂了,不过学完这本书就畅行无阻啦),为了便于理解,读者在阅读的时候可以自行脑补数据类型等)
2、线性表的顺序表示和实现
(1)线性表的顺序表示:用一组连续的存储单元依次存储线性表的数据元素
(2)地址表示:LOC(ai) = LOC(a1) + (i - 1) * L
(3)在插入和删除元素时,注意检查内存是否够插入一个元素或删除内存中的元素
(4)在实现元素动态插入内存不够时,注意不要在原先内存的基础上直接加内存,很有可能会数据溢出,所以要使用relloc函数重新申请一块地址,并将原先地址中所有数据复制到新申请的内存中,再添加要插入的元素,这也是线性表的顺序表示的缺点之一
(5)优点:
顺序存储;好理解;占用存储空间小;访问方便;存储密度大
(6)缺点:
插入和删除时间复杂度高;需要预先分配空间,造成空间浪费或数据溢出
3、线性表的链式表示和实现
淡化“位序”概念,强调“位置”概念
(1)特点:用一组任意的存储单元存储线性表的数据元素
(2)数据元素成为节点,节点内包括数据域和指针域,多个节点构成链表
(3)头指针:可指向头节点或首元节点
头节点:其数据域可以不存任何信息,也可以存储如线性表的长度等的附加类信息,指向首元节点,不计入表长
首元节点:正式第一个记录数据的节点
(4)大量地使用malloc和free会把内存分成很多碎块,有可能会造成内存浪费(数据对齐等原因造成),因此不建议无限制使用,可以使用堆来代替(后续会提到)
(5)静态链表:
a.由于动态链表查找元素的时间复杂度较高,无法达到O(1),以及有些高级语言不具有指针,因此诞生了静态链表
b.数据域 + 指示域(实际上就是取代了指针的功能,让人更好理解且调用了)
c.采用结构型数组,在插入和删除元素时只需要修改指示器,且查找元素比指针型链表更加快速
d.与指针型链表最大不同是动态链表由于不使用内存地址作为指示域,所以在分配空间以及删除元素后再添加元素时出现麻烦(例如,删除了两个元素,那么再添加一个元素的时候应该添加在哪里?指示域编号是多少?),所以需要人工搭建具有和malloc和free函数具有相同功能的函数,具体例子见课本P33
(6)循环链表
a.正常指针型链表的尾结点的指针域为NULL(因此要单独处理尾结点,不能写入循环内部),而循环链表尾结点的指针指向头节点或首元节点,可以达到循环遍历的效果(当然不只是这一个目的)
b.特别地,因为循环链表的尾结点指向了头节点或首元节点,因此头指针的作用与尾结点指针域重复,所以可以设立尾指针而不设头指针,这样在将两个线性表合并成一个表时,仅需将一个表的表尾和另一个表的表头相接,这样的操作仅需改变两个指针值(将A链表的尾结点指针指向B链表的头节点或首元节点,将B的尾结点指向A的头节点或首元节点,注意变量传递时的顺序)
(7)双向链表
a.单链表在查找某一节点的下一节点时时间复杂度为O(1),但是查找其上一节点时时间复杂度为O(n),因此诞生了双向链表(两个指针分别指向前驱和后继),加快了查找上一节点的速度,提高运行效率
b.在插入和删除元素时,注意指针更改顺序:
设在p和p->next之间插入元素q
q -> next = p -> next;p -> next -> prior = q;//这两步必须在p -> next = q;之前p -> next = q; q -> prior = p;
注:虽然双向链表的弥补了单链表和循环链表的缺点,但是在实际使用的过程中,仍要综合考虑使用哪种线性表,不能盲目使用双链表,因为节点内存储的链表信息越复杂的线性表对空间的牺牲越大,况且链表本身就是一种以牺牲空间换取时间的数据结构
上一篇:新硬盘如何检测坏道?
下一篇:主机前面封闭怎么安装散热器