数据结构--线性表

1、2022-5-1512022-5-152a1a3a4ana22022-5-1532022-5-1542022-5-1552022-5-156 a1 ai-1 ai an 空闲空闲 dLoc(ai) 0 i-2 i-1 n-1 MaxSize-1 Loc(a1)Loc(ai)=Loc(a1) + (i - -1)d随机存取随机存取：在在O(1)时间内存取数据元素时间内存取数据元素2022-5-1572022-5-1582022-5-1592022-5-15102022-5-1511o 顺序存储出现的问题：线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以快速地存取表

2、中各元素。然而，在做插入或删除元素的操作时，会引起大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。2022-5-1512o 链式存储结构的提出：为解决顺序表所遇到的困难，提出线性表链式存储结构，它不要求逻辑上相邻的元素在物理位置上也相邻。o 链式存储结构：是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。用链式存储结构存储的线性表称为链表。根据链表结点的不同结构，链表分为单链表、循环链表和双链表。2022-5-1513 data next单链表的结点结构：单链表的结点结构：数据域数据域指

3、针域指针域typedef struct LNode /*单链表的存储结构单链表的存储结构*/ DataType data; /*数据域数据域*/ struct LNode * next; /*指针域指针域*/LNode,* LinkList;2022-5-1514上图所示为线性表（Sun，Mon，Tue，Wed，Thu，Fri，Sat）的线性链式存储结构。这种链表有一个头指针（H），如果线性表非空，H指向链表中第一个结点，否则它为空指针（即不指向任何结点的指针，通常用NULL或表示）。由于最后一个结点设有直接后继，所以它的指针域为空。2022-5-15152022-5-15162022-5-1

4、517o 按序号查找o 算法描述：设带头结点的单链表的头指针为L,要查找表中第i个结点,则需从单链表的头指针L出发,从头结点开始,顺着链域扫描。用指针p指向当前扫描到的结点,初值指向第一个结点(p=L-next)。用j做计数器,累计当前扫描过的结点数（初值为1）,当j=i时,指针p所指的结点就是要找的第i个结点。2022-5-1518o 按值查找o 算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有，则返回首次找到的其值为e的结点的地址，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e比较。2022-5-1519o 结点插入到链表的第一

5、个结点前o 算法描述：逆位序输入n个元素的值，建立带头结点的单链表。该方法从一个空表开始，逐个读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上。2022-5-1520o 结点插入到两个结点之间o 算法描述：正位序输入n个元素的值，建立含有几个元素的带头结点的单链表。头插法建立链表的算法虽然简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。2022-5-1521o 结点插入到链表的最后一个结点后o 算法描述：在线性表两个数据元素值分别为a和b的结点间插入值为x的结点，已知p指向a。2022-5-1522o 单链表的删除操作o 算法描述：单链表中删除b，设p指向a。2022-5-15232022-5-1524循环单链表与单链表的结点类型完全相同，循环单链表的运算和单链表基本一样，差别仅在于：当需要从头到尾扫描整个链表时，是否到表尾的条件不同。在单链表L中判断某结点链域值是否为“空”，在循环链表中则判断某结点P的链域值是否等于头指针。struct CNode /*循环链表的存储结构*/ int data; struct CNode* next;CNo