线性表复习知识点(共3页)

1、精选优质文档-倾情为你奉上线性表的两种存储方式（原理，特点、各自的优缺点） 知识点： 顺序存储结构： 原理：使用数组，数组把线性表的数据元素存储在一块连续地址空间的内存单位中 特点：线性表中逻辑上相邻的数据元素在物理地址上也相邻。 优点：算法简单，存储密度大，空间单位利用效率高 缺点：需要预先确定数据元素的最大个数，并且插入和删除操作时需要移动较多的数据元素。（可简化为：插入或删除元素时不方便） 链式存储结构： 原理：把存放数据元素的结点用指针域构造成链。     

2、     特点：数据元素间的逻辑关系表现在结点的连接关系上          优点：不需要预先确定数据元素的最大个数，插入和删除操作是不需要移动数据元素（可简化为：插入或删除元素时很方便，使用灵活。）          缺点：存储密度小，空间单位利用效率低头指针、头结点、首元结点（第一个元素结点）的含义？头结点的作用是什么？ 知识点:&#

3、160;·头指针：指向链表中第一个结点(或为头结点或为首元结点)的指针。 ·头结点：链表的首元结点之前附设的一个结点。即头指针所指的不存放数据元素的第一个结点。 ·首结点：链表中存储线性表中第一个数据元素的结点。  头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。 若设计的链表中带头结点，则无论插入或删除的位置是首元结点还是其他结点，都不会改变头指针的数值，即算法步骤都相同。； 若设计的链表中不带头结点，则算法步骤要分别考虑插入或删除的位置是首元结点还是其他结点，因为两种情况的算法步骤不同。

4、 总结为： 头结点的作用主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。线性表上定义的基本运算：   ·构造空表：Initlist（L）   ·求表长：Listlength（L）   ·取结点：GetNode（L，i）   ·查找：LocateNode（L，x）   ·插入：InsertList（L，x，

5、i）   ·删除：Delete（L，i） 在顺序表中实现的基本运算：   ·插入：平均移动结点次数为n/2；平均时间复杂度均为O（n）。     ·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n）。   线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息（即指针或链）。这两部分信息组成链表中的结点结构假定指针

6、p指向线性链表中的第i个数据元素，则p->next为指向线性链表中第i+1个数据元素的指针。即p->data为ai， p->next ->data为ai+1。 (*p)表示p所指向的结点 (*p).dataÛp->data表示p指向结点的数据域 (*p).nextÛp->next表示p指向结点的指针域头指针、头结点、首元结点（第一个元素结点）的含义？头结点的作用是什么？ 知识点: ·头指针：指向链表中第一个结点(或为头结点或为首元结点)的指针。 ·头结点：链表的首元结点之前附设的一个结点。即头指针所指的不存放数据元素的第一个结点。 ·首结点：链表中存储线性表中第一个数据元素的结点。  头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。 若设计的链表中带头结点，则无论插入或删除的位置是首元结点还是其他结点，都不会改变头指针的数值，即算法步骤都相同。； 若设计的链表中不带头结点，则算法步骤要分别考虑插入或删除的位置是首元结点还是其他结