目录

第六章.数据结构与算法基础(重点)

第一节.数组及稀疏矩阵

第二节.数据结构的定义及线性表的概念

第三节.顺序存储与链式存储的比较

第四节.线性表——队列与栈

第五节.广义表

第六节.非线性结构——树与二叉树(import)

第七节.非线性结构——图

第八节.算法基础

第九节.查找——顺序查找、二分查找、散列表

第十节.数据的排序

上午下午都会考，且难度最高

重点：线性表、树与二叉树、排序与查找、算法基础及常见算法

数组

主要考察一维二维数组存储地址的计算

一维数组存储地址的计算：a+i*len ；i为索引号，len是每个位置所占的内存大小

二维数组存储地址的计算(分为按行优先和按列优先)：如五行五列的二维数组a中各个元素占两个字节，则元素a[2][3]按行优先存储的存储地址为：13*2+a

稀疏矩阵

即元素先以上下三角矩阵方式排列，然后将其存入数组

考察：计算矩阵中某一个元素对应的数组的下标

数据结构

1.数据结构的概念：数据结构即计算机存储、组织数据的方式

2.数据逻辑结构：分为线性结构与非线性结构；非线性结构又可以分为树型结构(不存在环路)和“图”(可能存在环路)。

线性表的概念

1.线性表的概念：线性表是线性结构的基本表现

2.线性表常见的存储结构——顺序表(连续的空间下存储数据)：开辟一系列的连续的空间，然后采用一维数组的方式来顺次存储信息

3.线性表常见的存储结构——链表(不连续的空间下存储数据)：每一个存储单元都包含了存储数据的空间及存储指针的空间(因为这一系列的空间不一定是连续的,指针的作用则是作为箭头，在两个空闲的空间之中起到指引作用)

4.三种不同的链表——单链表：即只有一种指针在空间之间依次指向的链表，在单链表中用头指针作为栈顶指针时，入栈和出栈都不需要遍历链表

5.三种不同的链表——循环链表：把尾元素的指针指向头结点(好处是：若当前结点是在尾元素，想要再次经过之前的某个元素，则可以继续next往下走，，直至遇到那个元素，而无需重新定位)的链表

6.三种不同的链表——双向链表：是可以双向的移动的链表(绝大部分结点都必须要有两个指针)，即可以通过头节点往尾结点移动，也可以通过尾结点向头节点移动的链表

7.链表的特点

(1)查询慢：链表中地址不是连续的，每次查询元素都必须从头开始

(2)增删快：链表结构，增加/删除一个元素，对链表整体结构没有影响，所以增删快

(3)结点：链表中的每一个结点包含了一个数据源(存储数组)，两个指针域(存储地址)，两个指针分别存储当前结点的位置和下一个结点的位置，在单链表中，两个结点之间有一条链子连接，但是只是单箭头指向，即从a到b，但不能从b到a，而双向链表则是在两个结点之间架设两条链子，互相指向，此时结点a可以到b，结点b也可以到a

链表的基本操作

1.单链表的删除结点：如a1——>a2——>a3；这三个结点，若要删除a2，则是让指针P的next=指针Q的next；P的next表示指针P(指向a1的指针)的下一个指针。

2.单链表的插入结点：如a1——>a2；若要在a1与a2之间插入一个结点a3；则是令S(指向a3的指针)的next=P的next以及P的next=S

3.双向链表的删除结点

4.双向链表的插入结点

空间性能的比较

1.存储密度：顺序存储的存储密度为1(更优)，而链式存储的密度则小于1

2.容量分配：顺序存储需要事先确定，而链式存储则是动态更改(更优)

时间性能的比较

1.查找运算：普遍情况下二者时间复杂度一样，但特殊情况下顺序表更为方便

2.读运算：顺序存储更优

3.插入运算：链表更优

4.删除运算：链表更优

队列与栈的概念

1.队列的概念及特点：结点的存储及读取遵循先进先出的规律，原因是队列可以对两端进行操作

2.栈的概念及特点：结点的存储及读取遵循先进后出的规律，原因是栈只能对一端进行操作

3.特殊队列——循环队列：即一种呈圆形的队列，尾指针会随着结点的依次存储而逐渐后移直至与头指针重合；因此：队满条件=队空条件=“头指针等于尾指针”;解决队满与队空判断条件容易混淆的方法：方法(1)少存一个结点：此时的队满条件为(tail+1)%size=head

队列与栈的练习