计算机软件基础(1)

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）顺序表）顺序表C语言描述：语言描述： 2.顺序表的基本运算顺序表的基本运算查找查找 一个完整的查找程序：一个完整的查找程序： 一个完整的查找程序（续）：一个完整的查找程序（续）： 顺序表查找运算的顺序表查找运算的结论结论： （1）查找成功的平均查找次数为）查找成功的平均查找次数为：(表长表长+1)/2。 （2）时间复杂度：表长越长，查找所消耗时间越多，）时间复杂度：表长越长，查找所消耗时间越多， 所以，时间复杂度与所以，时间复杂度与n有关，即：有关，即：T(n)=O(n)

4、。 3.顺序表的基本运算顺序表的基本运算插入插入 step1:判断表是否满？如果已满，则输出判断表是否满？如果已满，则输出“表满表满” ； 否则进行第二步；否则进行第二步； step2:判断要插入的位置是否在表内？如果不在，则判断要插入的位置是否在表内？如果不在，则 输出输出“位置不对位置不对”；否则进行第三步；否则进行第三步； step3:从第从第n-1个节点到第个节点到第i个节点全部后移个节点全部后移1位；位； step5:将顺序表的表长加将顺序表的表长加1； step4:在顺序表的第在顺序表的第i个位置插入个位置插入x； 插入运算的类插入运算的类C语言算法：语言算法： 一个完整的插入运算

5、程序一个完整的插入运算程序 一个完整的插入运算程序（续）一个完整的插入运算程序（续） 一个完整的插入运算程序（续）一个完整的插入运算程序（续） 顺序表插入运算的顺序表插入运算的结论结论： （1）在线性表中插入一个数据节点需要移动顺序表）在线性表中插入一个数据节点需要移动顺序表 的一半节点，即的一半节点，即：n/2。 （2）时间复杂度：插入运算的时间复杂度与）时间复杂度：插入运算的时间复杂度与n有关，有关， 即：即：T(n)=O(n)。 3.顺序表的基本运算顺序表的基本运算删除删除 step1:判断表是否为空？如果为空，则输出判断表是否为空？如果为空，则输出“无法删除无法删除” ； 否则进行第二

6、步；否则进行第二步； step2:判断要删除的位置是否在表内？如果不在，则判断要删除的位置是否在表内？如果不在，则 输出输出“位置不对位置不对”；否则进行第三步；否则进行第三步； step3:从第从第i+1个节点到第个节点到第n-1个节点全部前移个节点全部前移1位（位（采采 用覆盖的形式删除用覆盖的形式删除）；）； step4:将顺序表的表长减去将顺序表的表长减去1； 删除运算的类删除运算的类C语言算法：语言算法： 一个完整的删除运算程序一个完整的删除运算程序 一个完整的删除运算程序（续）一个完整的删除运算程序（续） 一个完整的删除运算程序（续）一个完整的删除运算程序（续） 顺序表删除运算的顺

7、序表删除运算的结论结论： （1）在线性表中删除一个数据节点需要移动顺序表）在线性表中删除一个数据节点需要移动顺序表 的一半节点，即的一半节点，即：n/2。 （2）时间复杂度：删除运算的时间复杂度与）时间复杂度：删除运算的时间复杂度与n有关，有关， 即：即：T(n)=O(n)。 1.线性表顺序存储结构与链式存储结构的异同点线性表顺序存储结构与链式存储结构的异同点 相邻相邻 关系关系 的相邻关系一致。的相邻关系一致。 储结构上是储结构上是 不相邻的。不相邻的。 2.单链表的形态单链表的形态 非空表：非空表： 空表：空表： 3.单链表类型定义单链表类型定义 5.求单链表的表长求单链表的表长 (1)单

8、链表的表长：单链表中数据节点的个数（单链表的表长：单链表中数据节点的个数（不包括不包括 头节点头节点）。）。 (2)算法：算法： 6.查找运算（查找运算（find） 7.插入运算（插入运算（insert）-插入已知插入已知地址地址的节点的节点 如：在如：在p指针所指节点后面插入已知指针所指节点后面插入已知地址为地址为s的节点的节点 7.插入运算（插入运算（insert）-插入已知插入已知内容内容的节点的节点 如：在如：在p指针所指节点后面插入已知指针所指节点后面插入已知内容为内容为x的节点的节点 8.删除运算（删除运算（delete） 如：删除如：删除p指针所指节点的下一个节点指针所指节点的下

9、一个节点 1.单循环链表的形态单循环链表的形态 非空表：非空表： 空表：空表： 注意：注意： 单链表只能沿着链表从前向后访问单链表只能沿着链表从前向后访问 表中的各节点，表中的各节点，无法找到某节点前无法找到某节点前 面的其他节点面的其他节点； 单循环链表可以通过任一节点访问单循环链表可以通过任一节点访问 表中的其他节点。表中的其他节点。 2.单循环链表的删除运算单循环链表的删除运算 例如：一个单循环链表，没有头指针只有尾指针例如：一个单循环链表，没有头指针只有尾指针r，试，试 写出删除尾指针写出删除尾指针r的前一个节点。的前一个节点。 2.单循环链表的删除运算单循环链表的删除运算 Step1

10、：找出：找出r节点前前的那个节点节点前前的那个节点p； Step2：让：让q指向指向 p的下一个节点；的下一个节点； Step3：从链表中删除：从链表中删除q所指向的节点；所指向的节点； Step3：回收：回收q。 2.单循环链表的删除运算单循环链表的删除运算 1.双循环链表的形态双循环链表的形态 非空表：非空表： 空表：空表： 2.双循环链表的类型定义双循环链表的类型定义 每个节点有每个节点有3个成员：个成员： prior：左链域，存放直接前驱节点的地址；：左链域，存放直接前驱节点的地址； next ：右链域，存放直接后继节点的地址；：右链域，存放直接后继节点的地址； data ： 数据域，

11、存放本节点的信息内容。数据域，存放本节点的信息内容。 2.双循环链表的类型定义双循环链表的类型定义 3.双循环链表的特点双循环链表的特点: p-prior-next=p-next-prior=p 4.双循环链表的基本运算双循环链表的基本运算-插入插入 例如：在例如：在p所指节点的前面插入地址为所指节点的前面插入地址为s的节点。的节点。 4.双循环链表的基本运算双循环链表的基本运算-插入插入 例如：在例如：在p所指节点的前面插入地址为所指节点的前面插入地址为s的节点。的节点。 4.双循环链表的基本运算双循环链表的基本运算-删除删除 例如：删除例如：删除p指针所指的节点指针所指的节点 1.尾插法尾

12、插法 依次输入依次输入abc时，以尾插法建立的单链表为：时，以尾插法建立的单链表为： 2.头插法头插法 依次输入依次输入abc时，以头插法建立的单链表为：时，以头插法建立的单链表为： 1.（2010.4单选）对顺序存储的线性表，其长度为单选）对顺序存储的线性表，其长度为n， 在等概率情况下，插入一个数据节点需要移动数据节在等概率情况下，插入一个数据节点需要移动数据节 点的平均次数是（点的平均次数是（ ）。）。 A n/2 B n-1 C (n+1)/2 D (n-1)/2 2.（2010.4单选）线性表采用链式存储时，其存储空间单选）线性表采用链式存储时，其存储空间 是（是（ ）。）。 A 必须是连续的必须是连续的 B 一定是不连续的一定是不连续的 C 可连续，也可不连续可连续，也可不连续 D 多个节点地址必须连续多个节点地址必须连续 3.（2010.4填空）已知填空）已知q指向单链表中一个节点，若在指向单链表中一个节点，若在 q 指向的节点之后插入