一×、软设笔记数据结构-线性表、栈、队列、串

一、线性表

1.线性表定义：

线性表是n个元素的有限序列，通常记为（a1,a2,...,an）.

特点：

*存在唯一的表头和表尾

*除了表头外，表中的每一个元素均只有唯一的直接前驱。

*除了表尾外，表中的每一个元素均只有唯一的直接后继。

2.线性的存储结构

（1）顺序存储

是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。

*优点：可以随机存取表中的元素

*缺点：插入和删除操作需要移动大量的元素。

在线性表的顺序存储结构中，第i个元素ai的存储位置为：

LOC(ai)=LOC(ai)+(i-1)*L

其中LOC(a1)是表中的第一个元素的存储位置，L是表中的每个元素所占的空间

（2）链式存储

链式存储是指用结点来存储数据元素，结点的空间可以是连续的，也可以是不连续的，因此存储数据元素的同事必须存储元素之间的逻辑关系。

结点空间只有在需要的时候才申请，无须事先分配。

*优点：插入和删除操作不需要移动元素，操作方便。

*缺点：增加了存储空间的开销，不能随机访问任一结点。

其他几种链表结构：

(1)双向链表：每个结点包含两个指针，指明直接前驱和直接后继元素，可在两个方向上遍历链表。

(2)循环链表：表尾结点的指针指向表中的第一个结点，可在任何位置上开始遍历整个链表。

(3)静态链表：借助数组来描述线性表的链式存储结构。

3.线性表的插入和删除运算

(1)基于顺序存储结构的运算

插入元素前要移动元素以挪出空的存储单元，然后再插入元素：删除元素时同样需要移动元素，以填充被删除出来的存储单元。

(2)基于链式存储结构的运算

在链式存储结构下进行插入和删除，其实质是对相关指针的修改。

二、栈

(1)栈是只能通过一端来实现数据存储和检索的一种线性表。栈进行插入和删除操作的一端称为栈顶，另一端称为栈底。栈的修改是按先进后出的原则进行的。又称为先进后出的线性表。

(2)栈的存储结构

栈的存储结构有顺序存储和链式存储。

*栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈顶的数据元素，同时附设指针top指示栈顶元素的位置。

*用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必设置头结点，链表的头指针就是栈顶指针。

三、队列

队列是一种先进先出(FIFO)的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。

在队列中，允许插入元素的一端称为队尾(rear)，允许删除元素的一端称为对头(front)。

(1)队列的存储结构

队列的存储结构有顺序存储和链式存储两种。

*队列的顺从存储结构是利用一组地址连续的存储单元存放队列中的元素，由于队列中的元素的插入和删除限定在队列的两端进行，因此设置对头指针和队尾指针，分别指示当前的队首元素和队尾元素。

*用链表表示的队列简称为链队列。

*为了便于操作，给链队列添加一个头结点，并令头指针指向头结点。队列为空的判定条件是：头指针和为指针的值相同，且均指向头结点。

四、串的几个基本概念：

*空串：长度为零的串，空串不包含任何字符。

*空格串：由一个或多个空格组成的串。

*子串：由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。

主串：abcbcc

子串：cb

串相等：指两个串长度相等且对应位置上的字符也相同。

串比较：两个串比较大小时以字符的ASCII码作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCII码值大者为大，若其中一个串先结束，则以串长较大者为大。

串的存储结构：

每个字符串的最后要增加个串结束标志 \0。

(1)串的顺序存储：

用一组地址连续的存储单元来存储串值的字符序列。

(2)串的链式存储

当用链表存储串中的字符时，每个结点中可以存储一个字符，也可以存储多个字符，要考虑存储密度问题。