数据结构课件第2章3.ppt

四、静态链表 有些高级语言中没有“指针”数据类型，要想发挥链表结构的长处，可用一个一维数组空间来模拟链表结构，称为静态链表。 静态链表的构造方法是用一维数组的一个分量表示一个结点，结点中的数据域(data)仍用来存储数据元素本身的信息，同时设一个下标域(cursor)来取代表中的指针域(next)，该下标域存放直接后继结点在数组中的位置序号。 数组中的第0个分量可看成固定的头结点，其下标域指示静态链表中的第一个数据结点位置。最后一个结点的下标域填0来标记该结点的尾结点。 静态链表的特点： 静态链表的存储结构仍需要预先分配一个较大的空间。这点类似于顺序表。 静态链表的插入删除操作时不需要移动元素，只需修改指针，类似于单链表。仍具有链式存储结构的主要优点。 静态链表的C语言描述 //线性表的静态链表存储结构 # define MAXSIZE 100 //链表的最大长度 typedef struct { ElemType data; int cur; } component, SLinkList [MAXSIZE]; SLinkList S; //S[0].cur指示第一个结点在数组中的位置 双向链表的C语言表示 typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱的指针域 struct DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList; 课堂练习 1. 以下说法正确的是（ ） 顺序存储方式的优点是存储密度大且插入、删除运算效率高。 链表的每个结点中都恰好包含一个指针。 线性表的顺序存储结构优于链式存储结构。 顺序存储结构属于静态结构而链式结构属于动态结构。 2. 说法错误的是（ ） 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低。 顺序存储的线性表可以随机存取。 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。 线性表的链式存储结构优于顺序存储结构。 3. 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 p-next-prior=p-prior; p-prior-next=p-next; 4. 以下说法错误的是（ ） 对循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表。 对单链表来说，只有从头结点开始才能扫描表中全部结点。 双链表的特点是找结点的前趋和后继都很容易。 对双链表来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针中。 5. 从表中任一结点出发都能扫描整个表的是（ ），便于插入删除的是（ ） 单链表 顺序表 双向链表 循环链表 答案：C,D A,C,D 写出带头结点的双向循环链表L为空表的 条件： 答案：(L==L-next)(L==L-prior) 判断题 1. 在具有头结点的链式存储结构中，头指针指向链表中的数据结点。（ ） 2. 顺序存储的线性表可以随机存取。（ ） 3. 在单链表中，要访问某个结点，只要知道该结点的指针即可，因此，单链表是一种随机存取结构。（ ） 4. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（ ） 问答题 线性表有两种存储结构，一是顺序表，二是链表，试问： 如果有n个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？ 答：由于链式结构可以用任意的存储空间来存储各数据元素，且存储空间可以是连续的，也可以不连续。此外，这种结构对于元素进行插入和删除操作时都无需移动元素，仅修改指针即可。很适用于线性表容量变化的情况。 2. 若线性表的总是基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，那么应采用哪种存取结构？为什么? 答：由于顺序存储结构一旦确定了起始位置，线性表中的任何一个元素都可以进行随机存取，即存取速度较高；并且，由于线性表的总数基本稳定，且很少进行插入和删除，故这一特点恰好避开了顺序存储结构的缺点。因此，应选用顺序存储结构。 3. 在单链表和双向链表中，能否从当前结点出发访问到任一结点？ 答：在单链表中只能由当前结点访问其后继的任一结点，但因其没有指向前驱的指针而无法访问其前驱结点。在双向链表中，由于当前