【王道笔记-计算机组成原理】第二章 线性表
文章目录
一、顺序表
- 结点定义(静态):
- 结点定义(动态):
二、链表
分为单链表(分为普通单链表、单循环链表)、双链表(分为普通双链表、双循环链表)
三、静态链表
静态链表借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域 next,与前面所讲的链表中的指针不同的是,这里的指针是结点的相对地址(数组下标),又称游标。和顺序表一样,静态链表也要预先分配一块连续的内存空间。当指针域为-1时表示链表结束。
四、链表和顺序表的比较
注意:
- 对于查找来说,顺序表的按下标查找的时间复杂度为O(1),按内容查找时间复杂度为O(n);链表的查找时间复杂度为O(n)。
- 对于插入、删除等运算,顺序表的时间复杂度一般为O(n),链表的时间复杂度为O(1)。
附:王道课后习题笔记
1.给定有n个元素的一维数组,建立一个有序单链表的最低时间复杂度是(O(nlog2n))。
2.为了方便插入和删除数据,可以使用双链表存放数据。
3.将两个有n个元素的有序表归并成一个有序表,其最少比较次数为(n)。
4.线性表的静态链表存储结构与顺序存储结构相比,其优点是(便于插入和删除)。
5.对于一个线性表,既要求能够快速地进行插入和删除,又要求存储结构能够反映数据元素之间的逻辑关系,则应采用(链式)存储结构。
6.
7.
8.
9.
10.
11.
12.