顺序表和链表都属于线性结构,那么首先需要明白什么是线性结构。
线性结构的特点:
1)同一线性表中元素具有相同特性(元素的“均一性”)。 2)相邻数据元素之间存在序偶关系。 (即,除第一个元素外,其他每一个元素有且仅有一个直接前驱;除最后一个元素外,其他每一个元素有且仅有一个直接后继。) 3)元素在线性表中的“下标”唯一地确定该元素在表中的相对位置(元素的“索引性”)。
常用的线性结构有:线性表,栈,队列,双队列,数组,串。
常见的非线性结构有:二维数组,多维数组,广义表,树(二叉树等),图。
(对比常见的线性结构和非线性结构的特点就很容易理解什么是线性结构啦!)。
顺序表与链表
顺序表与链表是非常基本的数据结构,它们可以被统称为线性表。
线性表(Linear List)是由 n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1] 组成的有限序列。
顺序表和链表,是线性表的不同存储结构。它们各自有不同的特点和适用范围。针对它们各自的缺点,也有很多改进的措施。
一、顺序表
顺序表一般表现为数组,使用一组地址连续的存储单元依次存储数据元素,如图 1 所示。它具有如下特点:
- 长度固定,必须在分配内存之前确定数组的长度。
- 存储空间连续,即允许元素的随机访问。
- 存储密度大,内存中存储的全部是数据元素。
- 要访问特定元素,可以使用索引访问,时间复杂度为 O(1)。
- 要想在顺序表中插入或删除一个元素,都涉及到之后所有元素的移动,因此时间复杂度为 O(n)。
图 1 顺序表
顺序表最主要的问题就是要求长度是固定的,可以使用倍增-复制的办法来支持动态扩容,将顺序表变成“可变长度”的。
具体做法是初始情况使用一个初始容量(可以指定)的数组,当元素个数超过数组的长度时,就重新申请一个长度为原先二倍的数组,并将旧的数据复制过去,这样就可以有新的空间来存放元素了。这样,列表看起来就是可变长度的。
一个简单的实现如下所示,初始的容量为 4。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <string.h> struct sqlist {
int *items, size, capacity;
sqlist():size(0), capacity(4) {
// initial capacity = 4
items = new int [capacity];
}
void doubleCapacity() {
capacity *= 2;
int * newItems = new int [capacity];
memcpy (newItems, items, sizeof ( int )*size);
delete [] items;
items = newItems;
}
void add( int value) {
if (size >= capacity) {
doubleCapacity();
}
items[size++] = value;
}
}; |
这个办法不可避免的会浪费一些内存,因为数组的容量总是倍增的。而且每次扩容的时候,都需要将旧的数据全部复制一份,肯定会影响效率。不过实际上,这样做还是直接使用链表的效率要高,具体原因会在下一节进行分析。
二、链表
链表,类似它的名字,表中的每个节点都保存有指向下一个节点的指针,所有节点串成一条链。根据指针的不同,还有单链表、双链表和循环链表的区分,如图 2 所示。
图 2 链表
单链表是只包含指向下一个节点的指针,只能单向遍历。
双链表即包含指向下一个节点的指针,也包含指向前一个节点的指针,因此可以双向遍历。
循环单链表则是将尾节点与首节点链接起来,形成了一个环状结构,在某些情况下会非常有用。
还有循环双链表,与循环单链表类似,这里就不再赘述。
由于链表是使用指针将节点连起来,因此无需使用连续的空间,它具有以下特点:
- 长度不固定,可以任意增删。
- 存储空间不连续,数据元素之间使用指针相连,每个数据元素只能访问周围的一个元素(根据单链表还是双链表有所不同)。
- 存储密度小,因为每个数据元素,都需要额外存储一个指向下一元素的指针(双链表则需要两个指针)。
- 要访问特定元素,只能从链表头开始,遍历到该元素,时间复杂度为 O(n)。
- 在特定的数据元素之后插入或删除元素,不涉及到其他元素的移动,因此时间复杂度为 O(1)。双链表还允许在特定的数据元素之前插入或删除元素。
在上一节说到,利用倍增-复制的办法,同样可以让顺序表长度可变,而且效率比链表还要好,下面就简单的实现一个单链表来验证这一点,至于元素插入的顺序就不要在意了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <stdio.h> #include <time.h> struct node {
int value;
node *next;
}; struct llist {
node *head;
void add( int value) {
node *newNode = new node();
newNode->value = value;
newNode->next = head;
head = newNode;
}
}; int main() {
int size = 100000;
sqlist list1;
llist list2;
long start = clock ();
for ( int i = 0;i < size;i++) {
list1.add(i);
}
long end = clock ();
printf ( "sequence list: %d\n" , end - start);
start = clock ();
for ( int i = 0;i < size;i++) {
list2.add(i);
}
end = clock ();
printf ( "linked list: %d\n" , end - start);
return 0;
} |
在我的电脑上,链表的耗时大约是顺序表的 4~8 倍。会这样,是因为数组只需要很少的几次大块内存分配,而链表则需要很多次小块内存分配,内存分配操作相对是比较慢的,因而大大拖慢了链表的速度。这也是为什么会出现内存池。
因此,链表并不像理论分析的那样美好,在实际应用中要受很多条件制约,一般情况下还是安心用顺序表的好。
三、静态链表
为了弥补链表在内存分配上的不足,出现了静态链表这么一个折中的办法。静态链表比较类似于内存池,它会预先分配一个足够长的数组,之后链表节点都会保存在这个数组里,这样就不需要频繁的进行内存分配了。
当然,这个方法的缺点是需要预先分配一个足够长的数组,肯定会导致内存的浪费。数组不够长到不是什么大不了的,使用第一节的动态扩容方法就是了。
静态链表一般是由两个链表组成,一个保存数据的链表,一个空闲节点的链表,如图 3 所示。
图 3 静态链表
当需要向链表中添加节点时,就从空闲链表中摘下一个使用。从链表中删除节点时,就将被删除的节点归还到空闲链表中。
在实现上,由于静态链表的节点都是存储在数组中的,所以经常使用数组索引代替指针,如果数组扩容了,也不会影响现有的节点。下面简单的实现了一个静态双向链表,没有添加动态扩容的能力。
静态链表的效率几乎跟数组一样,极大的提升了链表的效率。不过因为链表的效率受内存分配影响,不同的语言可能有不同的表现,具体情况还需要实验分析才可以。
四、块状链表
块状链表则是链表和顺序表的结合体,将多个顺序表以链表连接起来,如图 4 所示。
图 4 块状链表
这种数据结构的优点是结合了顺序表和链表的优点,长度可变,而且插入、删除也比较迅速(不必移动全部元素,只需要移动某一个或几个块中的元素),时间复杂度约为 O(n−√),内存的占用也不会像链表那么多。
但是缺点也很明显,就是实现起来过于复杂,要想让时间复杂度达到 O(n−√),需要令块的个数和每块中存储的元素个数都接近 n−√ 才行,这进一步限制了块状链表的应用。
STL 中的 deque 结构比较类似于块状链表,只不过它记录每一块使用的仍然是数组,而不是链表。同时 deque 只允许在两端进行插入和删除,实现上就容易很多。
五、跳表
跳表是针对有序链表进行优化的一种数据结构。它通过为链表节点随机化的添加前进链接,得以快速的跳过部分列表,如图 5 所示。
图 5 跳表
跳表会分为很多层,最底层就是普通的链表,高层则是用来快速获取后面的节点的。查找的时候,会从顶层的头节点开始向后查找,直到找到小于或等于目标的最后一个节点(链表是有序的,这是前提条件)。如果未能找到元素,则从下层链表接着找,最底层的普通链表保证一定能找到目标元素。
以上图为例,现在要查找元素 d4,那么首先会沿着顶层链表查找,找到 d3,接着沿着第二层链表查找,下一个元素是 d5 > d4,那么就只能沿着底层链表查找,成功找到元素 d4。动画演示可见图 6。
图 6 跳表查找过程
跳表的效率还是很高的,可以比拟二叉查找树(O(logn)),而且实现起来比二叉查找树要简单一些,属于以空间换时间的数据结构(需要很多额外的链表指针)。
相关推荐
顺序表和链表是两种常见的数据结构,分别用于存储和管理顺序排列的数据和链式排列的数据。 顺序表 顺序表是一种线性表,元素按顺序存储在连续的内存空间中。顺序表的优点是可以快速地访问和查找元素,但缺点是插入...
在这个实验中,我们将专注于两种基本的数据结构:链表和顺序表。这两种结构在编程和算法设计中起着至关重要的作用。 首先,我们来看**链表**。链表是一种线性数据结构,与数组不同,它在内存中不是连续存储的。每个...
顺序表是一种线性数据结构,其中元素在内存中按顺序存储。这种表的操作通常涉及到数组,因为数组提供了随机访问的能力。在顺序表中,第i个元素的地址可以通过第一个元素的地址加上i乘以每个元素的大小来计算。这使得...
在本资源"C语言:定义一个包含学生信息(学号,姓名,成绩)的顺序表和链表.zip"中,我们将探讨如何使用C语言实现两种常见的数据结构——顺序表和链表,用于存储和管理学生信息。 首先,我们来理解顺序表。顺序表是...
首先,顺序表是一种线性数据结构,它的特点是元素在内存中是连续存储的。在C++中,通常使用数组来实现顺序表。`sqlist.cpp`可能是顺序表的实现,我们可以在其中找到关于动态数组操作,如插入、删除和查找等操作的...
顺序链表,也称为单链表,是另一种线性数据结构,但与顺序表不同,它的元素不必须存储在连续的内存位置。每个元素(节点)包含两个部分:数据域,存储实际数据;指针域,存储指向下一个节点的引用。由于不需要保持...
数据结构顺序表、链表和数组是逻辑结构还是物理(存储)结构? 数据结构是计算机科学中的一门重要学科,它研究的是计算机中数据的组织、存储和处理方式。数据结构可以分为逻辑结构和物理结构两种。 逻辑结构是指...
顺序表是一种线性数据结构,它的特点是元素在内存中是连续存储的,可以通过索引快速访问任意位置的元素。这种结构简单直观,易于理解和操作。在C语言中,我们可以使用数组来实现顺序表。数组是一种固定大小的数据...
本主题将深入探讨两种常用的数据结构——顺序表和链表,并展示如何使用C语言来实现这两种数据结构来连接表。顺序表和链表各有优缺点,理解和掌握它们对于优化算法和提高程序效率至关重要。 首先,我们来讨论顺序表...
顺序表和链表是两种基本且常用的数据结构,它们在理解和实现各种算法时起着至关重要的作用。下面将详细介绍这两种数据结构以及在VC++6.0环境下如何进行相关操作。 **顺序表** 是一种线性数据结构,它的元素在内存中...
了解并熟练掌握顺序表、链表和静态链表的原理和特性,是成为一名优秀程序员的基础,它们是数据结构和算法设计的基石,广泛应用于各种软件开发中,包括操作系统、数据库管理系统、编译器等。通过深入学习和实践,能够...
本资源专注于"顺序表"中的"链表"部分,这是一组相关数据元素的集合,其内部组织方式不同于传统的数组。链表不依赖于内存中的连续空间,而是通过节点之间的引用连接来存储数据。 链表由一系列节点构成,每个节点包含...
其中,顺序表和链表是最基本且重要的两种线性数据结构。 #### 顺序表 顺序表是一种线性的数据结构,其特点是元素在内存中的存储位置是连续的,可以通过下标直接访问到任意一个元素。顺序表的基本操作包括插入、...
顺序表和链表是两种常见的线性数据结构,它们在不同的场景下各有优势。本篇将详细介绍这两种数据结构及其应用。 首先,顺序表是一种在内存中连续存储元素的数据结构,它的每个元素都有一个固定的索引,索引通常从0...
顺序表是一种线性数据结构,它在内存中连续存储元素,每个元素都有一个固定的索引位置。这种结构的特点是访问速度快,因为元素的位置固定,可以直接通过索引计算出其在内存中的地址。但是,插入和删除操作可能需要...
在数据结构中,顺序表和链表是两种重要的线性数据结构。线性表是由n个具有相同特性数据元素的有限序列组成,逻辑上呈现线性顺序,但在物理存储上可以是连续或非连续的。顺序表和链表是线性表的两种常见实现方式。 1...
单链表是一种线性数据结构,每个元素(节点)包含两个部分:数据域和指针域。数据域存储实际的数据,而指针域指向下一个节点的地址。单链表的头节点通常用来初始化链表,其指针域指向第一个元素。插入和删除操作...
顺序表是一种线性数据结构,它在内存中按顺序连续存储元素。这种结构非常适合初始化时就知道元素数量的情况,因为它的插入和删除操作主要依赖于元素的位置。顺序表的操作通常包括: 1. 插入元素:在指定位置插入...
《基于线性表的图书管理系统》是一个典型的C语言实现的数据结构应用案例,它结合了顺序表和链表这两种基本的线性数据结构。这个系统旨在模拟图书馆中的图书管理操作,如添加、删除、查找和显示图书信息。在这个系统...
链表是一种常见的线性数据结构,由一系列节点组成,每个节点包含一个数据域和一个指向下一个节点的指针。 - **创建链表** (`LinkedListCreat`):初始化链表头指针。 - **销毁链表** (`LinkedListDestroy`):释放...