一、基本知识点
1.逻辑结构和物理结构的区别和联系：
（1）逻辑结构
数据元素之间的逻辑关系称为数据的逻辑结构。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。从数学的角度观察，逻辑结构可形式化定义为（D，R），D是数据元素的集合，R是D上关系的有限数据元素的集合。数据的逻辑结构是对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。逻辑结构主要分为线性结构和非线性结构。
线性结构：一对一，比如线性表、栈、队列等。
非线性结构：一对多，细分为树和图。
（2）物理结构
数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。物理结构可分为以下4种类型。
1.顺序存储结构：
顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
优点：随机存取表中元素、储存密度大。缺点：插入和删除操作需要移动多个元素。2.链式存储结构：
链式存储结构，又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
特点：
（1）比顺序存储结构的存储密度小（链式存储结构中每个结点都由数据域与指针域两部分组成，相比顺序存储结构增加了存储空间）。－--链表的存储密度小于1（重点）
（2）逻辑上相邻的节点物理上不必相邻。
（3）插入、删除灵活（不必移动节点，只要改变节点中的指针）。
（4）查找结点时链式存储要比顺序存储慢。
（5）每个节点是由数据域和指针域组成。
3.线性表
线性表是具有相同特性数据元素的一个有限序列。该序列中所含元素个数叫做线性表的长度，用n（n>=0）表示。n=0时，线性表是一个空表。
线性表是一种简单的数据结构，可以想象成一队学生。学生人数对应线性表的长度，学生人数是有限的，这体现了线性表是一个有限序列；队伍中所有人的身份都是学生，这体现了线性表中数据元素具有相同的特性；线性表可以是有序的，也可以是无序的，学生可以按照身高来排队，体现了线性表的有序性。学生也可以没有依据地排队，这体现了线性表的无序性。
逻辑特性：除表头元素没有前驱，表尾元素没有后继外，其他元素都是只有一个前驱，只有一个后继。
存储结构：线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表，后者称为链表。
顺序表：把线性表中的所有元素按照其逻辑顺序，依次存储到从指定的存储位置开始的一块连续的存储空间中。这样，线性表中的第一个元素的存储位置就是指定的存储位置，第i+1个元素的存储位置紧接在第i个元素的存储位置的后面。
链表：在链表存储中，每个结点不仅包含所存元素的信息，还包含元素之间逻辑关系的信息，如单链表中前驱结点包含后继结点的地址信息，这样就可以通过前驱结点中的地址信息找到后继结点的位置。
1、单链表：在每个结点中除了包含数据域外，还包含一个指针域，用以指向其后继结点。由于只有尾指针，只能由开始结点走向终端结点，而不能由终端结点走向开始结点。判空操作：head->next=NULL（带头结点）；head=NULL（不带头结点）；
2、双链表：双链表就是在单链表的基础上增加了一个指针域，指向当前结点的前驱，这样方便其由后继结点来找到其前驱，从而实现输出终端节点到开始结点的数据序列。判空操作：head->next=NULL（带头结点）；head=NULL（不带头结点）；
3、循环单链表：在单链表的基础上，把最后一个结点的指针域指向链表中的第一个结点即可。循环单链表可以实现从任意一个结点出发访问链表中的任何结点。判空操作：head->next=head（带头结点）；head=NULL（不带头结点）；
4、循环双链表：在双链表的基础上，将终端节点的next指针指向链表的第一个结点，将链表中的第一个结点的prior指针指向终端结点。判空操作：head==head->prior或者 head==head->next（带头结点）； head==NULL；
5、静态链表：由一个结构体数组表示，数组中每一个结点含有两个分量；数据元素分量data和指针分量。
顺序表和链表的比较：
（1）基于空间的比较：
1.存储分配的方式：顺序表的存储空间是一次性分配的，链表的存储空间是多次分配 的。2.存储密度：顺序表的存储密度=1，链表的存储密度<1.
（2）基于时间的比较：
1.存取方式：顺序表可以随机存取，也可以顺序存取；链表只能顺序存取。