本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS,因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器,本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI,请尽量通过 HTTPS 访问本站,谢谢!
大话数据结构 笔记 第三章
我的笔记均包含大量个人理解内容,存在一定偏差。如果您发现错误,请留言提出,谢谢!
线性表(List)是指的零个或者多个数据元素组成的有限序列。它的特点体现在有序和有限上。用数学描述则有:
若将线性表记作 $(a_1, a_2, …, a_{i-1}, a_i, a_{a+i}, …, a_n)$, 则表中 $a_{i-1}$ 领先于 $a_i$, $a_i$ 领先于 $a_{i+1}$, 称 $a_{i_1}$ 是 $a_i$ 的直接前驱元素,$a_{i+1}$ 是 $a_i$ 的直接后继元素。 当 $ i = 2, 3, …, n$ 时, $a_i$ 有且只有一个直接前驱;如图所示:
线性表的元素有两个重要的特点:
我们知道抽象数据类型包括有共性的数据和一系列对数据的操作。那线性表的 ADT 呢?设想我们有一个队列,首先我们需要排队的人,其次我们需要指挥排队的人加入,离开,统计排队的人总数等等。这其实就是一个线性表操作的合集。我们用前面的 ADT 格式来定义线性表就是:
ADT List
DATA
线性表是一系列数据对象集合, 每个元素的类型均为 DataType。 除了第一个元素以外,其他元素有且只有一个直接前驱元素;除了最后一个元素外,每个元素有且只有一个直接后驱元素;元素之前的关系是一对一关系。
Operations
InitList(*L): 初始化操作,建立一个空的List L。
ListEmpty(L): 表空返回 true, 否则返回 false。
ClearList(*L): 清空 List。
GetElem(L,i,*e): 将 List 中的第 i 个元素返回给 e。
LocateElem (L, e): 在 List 中查找与 e 相同的元素; 成功返回该元素,失败则返回 0。
ListInsert(*L, i, *e): 在 List 的第 i 个位置插入新元素 e。
ListDelete(*L, i, *e): 删除 List 中第 i 个元素,用 e 返回被删除元素的值。
ListLength(L): 返回 List 元素的个数。
end ADT
上述基本是最基本的操作,我们可由这些基本操作组合衍生出一系列复杂的运算。
线性表的顺序存储结构就是指用线性表中的元素在存储单元里是地址连续的。这样的存储方式需要有三个属性:
容量和长度是两个概念。容量指 List 最多能容纳元素,既占用的内存空间;而长度是指现阶段元素的个数,很可能会增长或者减少。我们可以看出来,长度在任意时间都是小于等于容量的。
线性表的起始元素下标为 '0' 。每个元素对应的存储单元都有自己的起始地址;因此我们可以通过这样计算出第 i 个元素的地址:
//LOC是求址函数, c表示元素所占内存单元个数
LOC(a(i+1)) = LOC(a(i)) + c;
LOC(a(i)) = LOC(a(1)) + (i - 1)*c;
我们可以看到无论存取哪个元素,只需要在常数时间内完成。我们通常把有这种特点的存储结构成为随机存储结构。
要实现获取元的方法很简单,直接访问下标 i-1
即可。这个函数可以分两步骤设计:
if (L.length == 0 || i < 1 || i > L.length) {
return -1;
}
return L.data[i-1];
有个很形象的词可以用来形容线性表的插入操作:加塞。想一想如果你加塞,那么你后面所有的排队的都得往后排一位。线性表的插入操作也是如此。我们来详细分析一下这个函数:
i
个元素,把这些元素分别往后移动一位。i
的位置插入新元素。
if(L.length == MAXSIZE) //check if list is full
return -1;
if(i < 1|| i > L.length + 1) //check if i is out of range
return -1;
if (i < L.length) {// i is in range and not the last element
for (auto k = L.length -1; k >= i - 1; --k)
L.data[k+1] = L.data[k]; //from end to i, move every element backward with 1 unit
}
L.data[i-1] = e; // insert data
++L.length; // renew the length
还是刚才的例子。试想一下如果那个加塞的人被人赶出去了,那么所有的人都会往前站一位。
算法的思路如下:
if (i < 1 || i > L.length) //check if element is in range
return -1;
if ( i < L.length) { if element is not at end of List.
for (auto k = i; k < L.length, ++k)
L.data[k-1] = L.data[k]; // move all element in range forward.
--L.length;
return 0;
我们来看一看插入删除的各种情况:
显然 List 的读取存储操作都是 $O(1)$,而插入删除都是 $O(n)$。 这说明物理结构相邻的 List 更适用于元素不太变化,但会进行大量存取的应用。
引申一下,我们可以得知其主要优缺点:
相比起物理结构为线性的 List, 链式存储结构则采用了类似于上下线的关系来处理 List 的物理结构,也就是逻辑上连续,物理上不连续。为了表示 $a_i$ 和 $a_{i+1}$ 的关系,我们必须需要一个数据使得我们可以从 $a_i$ 找到 $a_{i+1}$ 。在 C 语言中这个信息被称为指针。所以链式存储中,我们的元素实际上分成了两部分:数据部分和指针部分。我们把每一个这样的元素称为一个节点(node), 而所有这些节点串起来,就形成了一个链式的线性表,简称链表(linked_list):
对于线性表来说,总会有头和有尾。我们把链表中第一个存储位置叫做头指针,整个链表的存取必须从头指针这里开始。而最后一个元素意味着不用再指向下一个元素,所以最后一个节点的里的指针应该是 NULL 指针。
实际操作中为了方便,我们会定义一个不带任何数据的头结点,只包含指针的信息(或者附带链表的长度信息等等)。
根据上面的描述,我们需要先定义链表的 Data 模型:具有数据部分和指针部分。我们可以用结构体 / 类来定义这个存储结构:
struct Node {
int data;
struct Node *next; //next point to the element after i
}
从我们先前对链表的理解来看,它的存储结构很松散;而我们也注意到对链表的插入/删除并不会对其他节点造成内存地址上的改动。这些特性让我们可以对链表进行动态的数据分配,即可以以很小的代价对表进行扩大,缩小,而内存的分配也会按照需要的大小来添加删除。
因此,链表的穿件过程是一个动态生成的过程,我们需要从空表的状态出发,一个个的链接节点,直到满足我们的要求为止。
创建链表的思路大概如下:
Linklist p, r;
*L = (LinkList)malloc( sizeof(Node)); //apply memory for LinkList
r = *L; //r point to the tail note
for (i = 0; i < n; ++i) {
p = (Node *) malloc(sizeof(Node)); //generate a new Node;
p.data() = rand(); //assign a random value for p
r -> next = p; // link currently node to the end;
r = p;//renew the pointer to the end
}
r -> next = NULL; //linklist finished
r → next = p 在这里是将表尾终端的指针指向新的节点p。 而 r = p
是将 r
指向 p
所在的节点,从而保证了 r
始终指向尾节点。而循环结束后,我们需要将链表的指针域置空,所以有 r → next = NULL。这样再次遍历的时候,我们就可以通过判断节点的指针是否非空,来判断它是不是尾部节点了。
由于链表中的元素除了第一个元素,其他的元素都需要自己的前驱来确定自己的位置;因此单链表的读取必须从头开始,通过遍历来找到所需要的元素。我们的思路大概如下:
p
。这个节点用于读取第 i
个元素的内容。我们初始化的时候用该节点指向链表 L
的下一个节点。i
个)时,我们不断的移动 p
的指针,让 p
指向下一个节点。p
的数据部分为空,那证明没有找到第 i
个元素。i
的元素应该存到了 p
里面,这时我们返回 p
的值就可以。
LinkList p;
p = (*L).next();
j = 1;
while(p && j < i) {
p = p.next();
++j;
if ( !p || j>i) {
return -1; //element not exist
}
return p.data() // got element content from i
}
相比起链表的读取和存储,单链表的插入和删除操作都显得简单了许多:
大致的顺序是:
用代码可以表示为:
new -> next = front -> next; // copy the pointer info from front node to new node, use the info point to the rear node
front -> next = new; // then let front point to the new node
注意,这里不能交换操作的顺序。试想一下如果我们先让前驱结点指向新节点,那么指向 rear
的指针信息会被新节点的信息覆盖,从而造成链表断链。
p
并指向链表的第一个节点。j
, 当 j < i
(未达到插入位置)的时候, 让 p
的指针向后移动,并累加 j
。p
依然为空,证明该链表没有第 i
个元素,返回错误。s
。s
。s
进行插入操作(详见上述代码)。0
。
单链表的删除则更简单了,只需要把要删除的节点的前驱结点直接指向要删除节点的后置节点就可以:
用代码可以表示为:
front -> next = new -> next;
注意:被删除的节点必须要释放内存。
实现链表删除第 $i$ 个数据的的流程如下:
p
指向链表第一个节点,初始化 j
从 1
开始。j < i
时就遍历链表,让 p
的指针往后移动,不断指向下一个节点, j
自加。p
为空,证明第 i
个元素不存在。链表的删除和创建一样也需要遍历,同时也需要挨个的释放节点的内存。算法思路大概如下:
p
和 节点 q
,p
在这里总是代表当前需要释放的节点, q
则代表了下一个节点。p
指向第一个节点。q
指向 p
指向的节点的下一个节点。p
指向的节点。q
指向的节点给 p
,使该节点在下一轮循环中被释放。学习完了线性表和链表,我们可以明确几个注意点: