第二次学习笔记

                                      数据结构

一、数据结构（概念）：是相互之间存在一种或者多种特定关系的数据元素的集合。
（1）逻辑结构：是指数据对象中数据元素之间的相互关系。
a.集合结构（集合结构中的数据元素除了同属于一个集合外，它们之间没有任何特定的关系，类似于数学当中的集合关系）
b.线性结构（数据元素之间是一对一的关系）
c.树形结构（数据元素之间存在一种一对多的层次关系）
d.图形结构（数据元素之间是多对多的关系）
（2）物理结构：就是数据的逻辑结构在计算机中的存储形式。
a.顺序存储结构（数据元素存储在地址连续的存储单元中）
b.链式存储结构（是把数据元素存放在任意的存储单元里，这组存储单元可以使任意的，也可以是连续的）
抽象数据类型：类比结构体的概念，抽象数据类型是指一个数学模型及定义在该模
型上的一组操作，不仅可以指已经定义的数据类型，还可以是用户
自己定义的数据类型。
二、数据结构与算法的关系
程序=数据结构+算法
算法时间复杂度：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数进而分析T(n)随n的变化情况而确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作T(n)=O(f(n))
由于f(n)仅考虑最高阶项，因此其中有三个常见的阶：
Ｏ(1)：常数阶
Ｏ(n)：线性阶
O(n^2)：平方阶
三、线性表
概念：零个或多个数据元素的有限序列
（1）顺序存储结构 （指用一段地址连续的存储单元依次存储线性表的数据元素）

描述顺序存储结构需要三个元素：
存储空间的起始位置
线性表的最大存储容量
线性表的当前长度
顺序存储结构的插入和删除：
插入算法的思路：
如果插入的位置不合理，抛出异常
如果线性表的长度大于等于数组长度，则抛出异常或动态增加容量
从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置
将要插入元素 填入到位置i处
表长加1
删除算法的思路：
如果删除位置不合理，抛出异常
取出删除元素
从删除元素位置开始遍历到最后一个元素的位置，分别将它们都向前移动一个位置
表长减1
（2）链式存储结构
在顺序结构里，我们只需要存数据元素的信息就可以了，但在链式结
构里，我们对于每一个数据元素，除了它的信息，还需存储它的后继
元素的地址。我们将存储数据元素信息的域称为数据域，将存储后继
元素地址的域成为指针域。两部分共称为结点。这样一个关于结点的序列，我们称为链表。
单链表：结点中只包含一个指针域的链表称为单链表。
a.单链表的读取：
为获取第i个元素，对于单链表而言，算法思路为：

初始化：声明结点p指向链表第一个结点，声明计数器j，从0开始，j=1则p指向第一个结点，计数器的序号与结点序号一致

当j<i时，遍历链表，让p的指针向后移动，不断指向下一结点，j++

若后移至表尾，p->NULL，则说明链表中不存在第i个元素，若否，查找成功，返回结点p的数据
b.单链表的插入：
若想在第i个位置后插入新元素e（后插），即把结点s插入到p和p->next
之间，部分算法思路为：

先让p->next成为s的后继结点，即s->next=p->next；

再让结点s成为p的后继结点，即p->next=s；

将数据元素e赋值给s->data；
**c.**单链表的删除：
若想删除第i个元素，即结点q，部分算法思路为：

创建结点p指向第i-1个元素，令其成为q的前驱；

获取第i个结点q，即q=p->next

将结点p后继的后继结点（q的后继结点）赋值成为p的后继结点，
p->next=p->next->next / p->next=q->next

释放结点q的空间，free(q)
**d.**单链表的整表创建：
若想整表创建一个单链表（头插法），思路为：
声明一结点p和计数变量i；
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环：
生成一新结点赋值给p，赋p的数据域p->data；
将p插入到头结点和前一个结点之间。
e.单链表的整表删除：
单链表的整表删除，算法思路为：
判断头结点是否为空，若非空，证明表内有元素，需要进行删除
声明结点p，使p成为头结点：p=L->next
令p的后继成为头结点，即不断使元素前移：L->next=p->next
释放p结点的空间，free§
静态链表：
静态链表用数组描述，不需要使用指针。数组的每个元素由两个数据域组成，data&cur。data用于存放数据元素，cur存放该元素的后继在数组中的下标，可称游标域。 我们对数组第一个和最后一个元素做特殊处理，数据域中不存放任何数据。没有存储数据的数组元素称为备用链表。其游标域中，在数组第一个元素（下标为0的元素）存放备用链表的第一个结点的下标。数组的最后一个元素的cur存放静态链表的第一个结点的下标
循环链表：
对单链表结构，我们令终端结点的指针指向头结点的话，就使整个单链表构成了一个环，这种头尾相连的结构我们称为循环链表。
双向链表：
在单链表的基础上，我们可以增加一个指针域，用于存储前驱元素的
地址。我们把结点中包含两个指针域，一个指向直接前驱，一个指向
直接后继的结构称为双向链表。
———————————————————————————————————
目前为止栈和队列还未学完…所以后面的内容就没写出来了