计算机软件基础(自考本科线性表)

1、1.线性表的逻辑结构线性表的逻辑结构（1）线性表：是由）线性表：是由n（n 0）个数据节点个数据节点 a0，a1 ,，an-1组成的组成的有限有限序列。序列。（2）线性表的逻辑结构特征：）线性表的逻辑结构特征：对于非空线性表：对于非空线性表：有且仅有一个开始节点，该节点有且仅有一个直有且仅有一个开始节点，该节点有且仅有一个直接的后继；接的后继；有且只有一个终结节点，该节点有且仅有一个直有且只有一个终结节点，该节点有且仅有一个直接的前驱；接的前驱；其余内部节点有且仅有一个直接前驱和一个直接其余内部节点有且仅有一个直接前驱和一个直接后继。后继。（2）线性表的逻辑结构特征：）线性表的逻辑结构特征：同

2、一个线性表中的数据节点具有相同的属性。同一个线性表中的数据节点具有相同的属性。线性表长度：线性表中数据节点的个数。线性表长度：线性表中数据节点的个数。 2. 线性表的存储结构线性表的存储结构（1）顺序存储结构：顺序表结构；）顺序存储结构：顺序表结构；（2）链式存储结构：链表结构；）链式存储结构：链表结构；1.顺序表顺序表（1）顺序表：）顺序表： 把线性表中的数据节点按其逻辑顺序依次存把线性表中的数据节点按其逻辑顺序依次存放到计算机内存中的放到计算机内存中的一连续空间一连续空间中，将这一连续中，将这一连续空间称为顺序表。空间称为顺序表。（2）顺序表中数据节点地址的计算）顺序表中数据节点地址的计算

3、Loc(ai)=loc(a0)+i*d (0in-1)1.顺序表顺序表（3）用一维数组描述顺序表）用一维数组描述顺序表2.顺序表的基本运算顺序表的基本运算查找查找例例8-1在长度为在长度为n的线性表的线性表L中顺序查找内容为中顺序查找内容为X的节点。的节点。要求：写出类要求：写出类C语言算法，求成功的平均查找长度及时语言算法，求成功的平均查找长度及时间复杂度间复杂度T(n)。一个完整的查找程序：一个完整的查找程序：一个完整的查找程序（续）：一个完整的查找程序（续）：顺序表查找运算的顺序表查找运算的结论结论：（1）查找成功的平均查找次数为）查找成功的平均查找次数为：(表长表长+1)/2。（2）时

4、间复杂度：表长越长，查找所消耗时间越多，）时间复杂度：表长越长，查找所消耗时间越多，所以，时间复杂度与所以，时间复杂度与n有关，即：有关，即：T(n)=O(n)。3.顺序表的基本运算顺序表的基本运算插入插入step1:判断表是否满？如果已满，则输出判断表是否满？如果已满，则输出表满表满 ；否则进行第二步；否则进行第二步；step2:判断要插入的位置是否在表内？如果不在，则判断要插入的位置是否在表内？如果不在，则输出输出位置不对位置不对；否则进行第三步；否则进行第三步；step3:从第从第n-1个节点到第个节点到第i个节点全部后移个节点全部后移1位；位；step5:将顺序表的表长加将顺序表的表长

5、加1；step4:在顺序表的第在顺序表的第i个位置插入个位置插入x；例例8-2在长度为在长度为n的线性表的线性表L中第中第i(0in)个位置上插入个位置上插入内容为内容为x的数据节点。要求：写出类的数据节点。要求：写出类c语言算法，求节语言算法，求节点平均移动次数及时间复杂度点平均移动次数及时间复杂度T(n)。一个完整的插入运算程序一个完整的插入运算程序一个完整的插入运算程序（续）一个完整的插入运算程序（续）一个完整的插入运算程序（续）一个完整的插入运算程序（续）顺序表插入运算的顺序表插入运算的结论结论：（1）在线性表中插入一个数据节点需要移动顺序表）在线性表中插入一个数据节点需要移动顺序表的

6、一半节点，即的一半节点，即：n/2。（2）时间复杂度：插入运算的时间复杂度与）时间复杂度：插入运算的时间复杂度与n有关，有关，即：即：T(n)=O(n)。3.顺序表的基本运算顺序表的基本运算删除删除step1:判断表是否为空？如果为空，则输出判断表是否为空？如果为空，则输出无法删除无法删除 ；否则进行第二步；否则进行第二步；step2:判断要删除的位置是否在表内？如果不在，则判断要删除的位置是否在表内？如果不在，则输出输出位置不对位置不对；否则进行第三步；否则进行第三步；step3:从第从第i+1个节点到第个节点到第n-1个节点全部前移个节点全部前移1位（位（采采用覆盖的形式删除用覆盖的形式删

7、除）；）；step4:将顺序表的表长减去将顺序表的表长减去1；例例8-3在表长为在表长为n的线性表的线性表L中删除第中删除第i(0in一一1)个节点。个节点。 要求：写出类要求：写出类c语言算法，求节点平均移动次数及时间复语言算法，求节点平均移动次数及时间复杂度杂度T(n)。一个完整的删除运算程序一个完整的删除运算程序一个完整的删除运算程序（续）一个完整的删除运算程序（续）一个完整的删除运算程序（续）一个完整的删除运算程序（续）顺序表删除运算的顺序表删除运算的结论结论：（1）在线性表中删除一个数据节点需要移动顺序表）在线性表中删除一个数据节点需要移动顺序表的一半节点，即的一半节点，即：n/2。

8、（2）时间复杂度：删除运算的时间复杂度与）时间复杂度：删除运算的时间复杂度与n有关，有关，即：即：T(n)=O(n)。1.单链表的形态单链表的形态非空表：非空表：空表：空表：2.线性表顺序存储结构与链式存储结构的异同点线性表顺序存储结构与链式存储结构的异同点顺序存储结构顺序存储结构链式存储结构链式存储结构存储空间存储空间连续的存储空间连续的存储空间可以连续，可以不连续（可以连续，可以不连续（分散）的存储空间分散）的存储空间节点间的相节点间的相邻关系邻关系逻辑上的相邻关系与存逻辑上的相邻关系与存储结构上的相邻关系一储结构上的相邻关系一致。致。逻辑上是相邻的，在存储逻辑上是相邻的，在存储结构上是不

9、相邻的。结构上是不相邻的。空间使用空间使用在使用前，事先分配存在使用前，事先分配存储空间。储空间。只在使用时才申请存储空只在使用时才申请存储空间，使用过后其存储空间间，使用过后其存储空间可以删除。可以删除。3.单链表运算符号的说明单链表运算符号的说明4. 单链表上的简单运算单链表上的简单运算例例8-4 求单链表的表长求单链表的表长（不包括表头节点）（不包括表头节点）。例例8-5 在单链表中查找内容为在单链表中查找内容为x的节点（的节点（find）7.插入运算（插入运算（insert）-插入已知插入已知地址地址的节点的节点如：在如：在p指针所指节点后面插入已知指针所指节点后面插入已知地址为地址为

10、s的节点的节点7.插入运算（插入运算（insert）-插入已知插入已知内容内容的节点的节点如：在如：在p指针所指节点后面插入已知指针所指节点后面插入已知内容为内容为x的节点的节点8.删除运算（删除运算（delete）如：删除如：删除p指针所指节点的下一个节点指针所指节点的下一个节点1.单循环链表的形态单循环链表的形态非空表：非空表：空表：空表：注意：注意：单链表只能沿着链表从前向后访问单链表只能沿着链表从前向后访问表中的各节点，表中的各节点，无法找到某节点前无法找到某节点前面的其他节点面的其他节点；单循环链表可以通过任一节点访问单循环链表可以通过任一节点访问表中的其他节点。表中的其他节点。2.

11、单循环链表的删除运算单循环链表的删除运算例如：一个单循环链表，没有头指针只有尾指针例如：一个单循环链表，没有头指针只有尾指针r，试，试写出删除尾指针写出删除尾指针r的前一个节点。的前一个节点。2.单循环链表的删除运算单循环链表的删除运算Step1：找出：找出r节点前前的那个节点节点前前的那个节点p；Step2：让：让p指向指向 q的下一个节点；的下一个节点；Step3：从链表中删除：从链表中删除q所指向的节点；所指向的节点；Step3：回收：回收q。2.单循环链表的删除运算单循环链表的删除运算1.双循环链表的形态双循环链表的形态非空表：非空表：空表：空表：2.双循环链表的类型定义双循环链表的类

12、型定义每个节点有每个节点有3个成员：个成员：prior：左链域，存放直接前驱节点的地址；：左链域，存放直接前驱节点的地址；next ：右链域，存放直接后继节点的地址；：右链域，存放直接后继节点的地址；data ： 数据域，存放本节点的信息内容。数据域，存放本节点的信息内容。2.双循环链表的类型定义双循环链表的类型定义3.双循环链表的特点双循环链表的特点:p-prior-next=p-next-prior=p4.双循环链表的基本运算双循环链表的基本运算-插入插入例如：在例如：在p所指节点的前面插入地址为所指节点的前面插入地址为s的节点。的节点。4.双循环链表的基本运算双循环链表的基本运算-插入插

13、入例如：在例如：在p所指节点的前面插入地址为所指节点的前面插入地址为s的节点。的节点。4.双循环链表的基本运算双循环链表的基本运算-删除删除例如：删除例如：删除p指针所指的节点指针所指的节点1.尾插法尾插法依次输入依次输入abc时，以尾插法建立的单链表为：时，以尾插法建立的单链表为：2.头插法头插法依次输入依次输入abc时，以头插法建立的单链表为：时，以头插法建立的单链表为：例例8-10依次输入一串字符依次输入一串字符abc，以，以*作为结束标志，建立并作为结束标志，建立并输出如下单链表：输出如下单链表：例例8-11 依次输人一串字符依次输人一串字符abc，以，以*为结束标记，为结束标记，建立

14、并输出如下单链表：建立并输出如下单链表：一、时间性能一、时间性能1)若经常进行的运算为查找运算，以顺序存储为宜。若经常进行的运算为查找运算，以顺序存储为宜。2若经常进行的运算为插入，删除运算，以链式存储为宜。若经常进行的运算为插入，删除运算，以链式存储为宜。实例：用链表制作通信录实例：用链表制作通信录 1定义通信录结构定义通信录结构 2编写显示联系人信息模块编写显示联系人信息模块 3编写添加联系人模块编写添加联系人模块 4编写查找联系人模块编写查找联系人模块 5编写删除联系人模块编写删除联系人模块 6编写主模块编写主模块1.（2010.4单选）对顺序存储的线性表，其长度为单选）对顺序存储的线性表，其长度为n，在等概率情况下，插入一个数据节点需要移动数据节在等概率情况下，插入一个数据节点需要移动数据节点的平均次数是（点的平均次数是（ ）。）。A n/2 B n-1 C (n+1)/2 D (n-1)/22.（2010.4单选）线性表采用链式存储时，其存储空间单选）线性表采用链式存储时，其存储空间是（是（ ）。）。A 必须是连续的必须是连续的 B 一定是不连续的一定是不连续的 C 可连续，也可不连续可连续，也可不连续 D 多个节点地址必须连续多个节点地址必须连续3.（2010.4填空）已知