数据结构知识点总结（详细无题目）

数据结构知识点总结

内容概要：

基本概念——线性表——栈与队列——树与二叉树——图——查找算法——排序算法

一、 基本概念

1、数据元素是数据的基本单位。

2、数据项是数据不可分割的最小单位。 3、数据结构的 逻辑结构（抽象的，与实现无关） 物理结构（存储结构） 顺序映像（顺序存储结构）位置“相邻” 非顺序映像（链式存储结构）指针表示关系 4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出 正确性：能按设计要求解决具体问题，并得到正确的结果。

有穷性：任何一条指令都只能执行有限次，即算法必须在执行有限步后结束。 确定性：算法中每条指令的含义必须明确，不允许由二义性

可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。

输入：一个算法的输入可以包含零个或多个数据。 输出：算法有一个或多个输出 5、算法设计的要求：

（1）正 确 性：算法应能满足设定的功能和要求 。 （2）可 读 性：思路清晰、层次分明、易读易懂 。

（3）健 壮 性：输入非法数据时应能作适当的反应和处理。 （4）高 效 性（时间复杂度）：解决问题时间越短，算法的效率就越高。 （5）低存储量（空间复杂度）：完成同一功能，占用存储空间应尽可能少。

二、 线性表

1、线性表 List：最常用且最简单的数据结构。

含有大量记录的线性表称为文件。

2、线性表是n个数据元素的有限序列。

线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。

3、顺序表——线性表的顺序存储结构

特点

a) 逻辑上相邻的元素在物理位置上相邻。 b) 随机访问。

1) typedef struct{ DataType elem[MAXSIZE]; int length;

} SqList;

0

1

...

MAXSIZE-1

L.elem[] L.elem[] L.elem[] L.length==0

L.length==MAXSIZE

0

4、线性表的链式存储结构

1) 类型定义

简而言之，“数据 + 指针”。

typedef struct LNode { DataType data; struct LNode *next; } LNode, *LinkList;

data next 2) 不带头结点的空表判定为 L= =null

带头结点的空表判定为 L->next= =null 循环单链表为空的判定条件为 L.next= =L 线性链表的最后一个结点的指针为NULL

头结点的数据域为空，指针域指向第一个元素的指针。

5、顺序表和单链表的比较

顺序表 以地址相邻表示关系 随机访问，取元素O(1) 插入、删除需要移动元素O(n) 用指针表示关系 单链表 顺序访问，取元素O(n) 插入、删除不用移动元素O(n)(用于查找位置) 6、顺序存储：优点：存储密度大，可随机存储

缺点：大小固定；不利于增减节点;存储空间不能充分利用；容量

难扩充

链式存储：优点：易于插入删除；可动态申请空间；表容量仅受内存空间限

制

缺点：增加了存储空间的开销；不可以随机存储元素

三、 栈与队列 1、栈

栈：限定仅在表尾进行插入或删除操作的线性表。 栈顶：表尾端 栈底：表头

栈是先进后出的线性表。

插入栈顶元素称为入栈，删除栈顶元素称为出栈。

2、栈分为链栈和顺序栈

·链栈

用不带头结点的单链表实现。

S

an an-1 ... a1 /\\ ·顺序栈

类似于顺序表，插入和删除操作固定于表尾。

进栈:进栈运算是在栈顶位置插入一个新元素x。算法思想：(a)判栈是否为满，若栈满，作溢出处理，并返回0；(b)若栈未满，栈顶指针top加1；(c)将新元素x送入栈顶，并返回1。算法实现：intPush (SeqStack*s，datatypex){ if （s->top= =MAXLEN–1）return 0；// 栈满不能入栈，且返回0else { s->top++；s->data[s->top]=x；// 栈不满，则压入元素xreturn 1；} // 进栈成功，返回1}出栈:出栈运算是指取出栈顶元素，赋给某一个指定变量x。算法步骤：(a)判栈是否为空，若栈空，作下溢处理，并返回0；(b) 若栈非空，将栈顶元素赋给变量x；(c)指针top减1，并返回1。算法实现：datatypePop（SeqStack*s）{ datatypex;if (SEmpty( s ) ) return 0；// 若栈空不能出栈，且返回0else { x=s->data[s->top]；// 栈不空则栈顶元素存入*xs->top --；return x；} // 出栈成功，返回1}

3、队列

先进先出的线性表。 队尾入队 对头出队

允许插入的一端叫做队尾 允许删除的一端叫做对头

4、链队列

typedefstructqueuenode{datatypedata; structqueuenode*next;}queuenode; // 链队结点的类型datatypetypedefstruct{queuenode*front,*rear;}linkqueue; // 将头指针、尾指针封装在一起的链队frontAB…J^prear·

图4-6 链队列示意图

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构知识点总结（详细无题目）在线全文阅读。