1.线性表的定义
线性表是具有相同数据类型的n个数据元素的有限序列，其中n位表长，当n=0时线性表是一个空表
线性表的特点：
表中元素的个数有限；表中元素具有逻辑上的顺序性，表中元素有其先后次序；表中元素都是数据元素，每个元素都是单个元素；每个元素占有相同大小的存储空间
线性表时一种逻辑结构，表示元素之间一对一的相邻关系，顺序表和链路表时存储结构
2.顺序表的定义
线性表的顺序存储又称顺序表
用一组地址连续的存储单元依次存储线性表中的数据元素
一维数组空间分配
静态分配：数组的大小和时间已经固定，一旦空间占满，再加入新的数据就会产生溢出，程序就会奔溃
动态分配：存储数组的空间是在程序执行过程中通过动态存储分配语句配的
一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间
注意：动态分配仍然是顺序存储结构，物理结构没有变化，依然是随机存取方式只是分配的空间大小可以再运行时决定
特点：随机访问，即通过首地址和元素序号可再时间O(1)内找到指定的元素；存储密度高，每个结点只存取数据元素；逻辑上相邻的元素物理上也相邻，当执行插入和删除操作时，需要移动大量元素
3.单链表
线性表的链式存储又称单链表，它是通过一组人意的存储单元来存储线性表中的数据元素
对每个链表节点，除存放元素自身的信息外，还需要存放一个指向其后继的指针
4.双链表
双链表结点中有两个指针prior和next，分别指向前驱结点和后继结点
5.循环单链表
循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头节点，形成了一个环
6.循环双链表
在循环双链表中，头节点的prior指针还要指向表尾节点
7.静态链表
静态链表借助数组来描述线性表的链式存储结构，静态链表也要预先分配一块连续的内存空间
结点也有数据域data和指针域next，这里的指针是结点的相对地址（数组下标），又称游标
网友评论