计算机软件基础ppt课件.ppt

计算机软件基础 第二篇数据结构基础 第八章线性表 linearlist 1 一 线性表的概念 1 线性表的逻辑结构 1 线性表 是由n n 0 个数据节点a0 a1 an 1组成的有限序列 2 线性表的逻辑结构特征 对于非空线性表 有且仅有一个开始节点 该节点有且仅有一个直接的后继 有且只有一个终结节点 该节点有且仅有一个直接的前驱 其余内部节点有且仅有一个直接前驱和一个直接后继 2 一 线性表的概念 2 线性表的逻辑结构特征 同一个线性表中的数据节点具有相同的属性 线性表长度 线性表中数据节点的个数 2 线性表的存储结构 1 顺序存储结构 顺序表结构 2 链式存储结构 链表结构 3 二 顺序表 1 顺序表 1 顺序表 把线性表中的数据节点按其逻辑顺序依次存放到计算机内存中的一连续空间中 将这一连续空间称为顺序表 2 顺序表中数据节点地址的计算 Loc ai loc a0 i d 0 i n 1 4 二 顺序表 1 顺序表 3 顺序表C语言描述 structsequenlist datatypea listsize 表示线性表有 a0 a1 an 1 intlength length表示线性表的实际长度 5 二 顺序表 2 顺序表的基本运算 查找 structsequenlist 构建sequenlist型 datatypedata listsize intlength structsequenlistL 定义sequenlist变量L intfind structsequenlistL datatypex 定义find函数 inti 0 while i L length 如果找不到 则返回数值0 6 二 顺序表 一个完整的查找程序 include definelistsize50structsequenlist 构建sequenlist型 intdata listsize intlength structsequenlistL 定义sequenlist变量L intfind structsequenlistL intx 定义find函数 inti 0 while i L length 7 二 顺序表 一个完整的查找程序 续 main inti j y structsequenlista scanf d 8 二 顺序表 顺序表查找运算的结论 1 查找成功的平均查找次数为 表长 1 2 2 时间复杂度 表长越长 查找所消耗时间越多 所以 时间复杂度与n有关 即 T n O n 9 二 顺序表 3 顺序表的基本运算 插入 step1 判断表是否满 如果已满 则输出 表满 否则进行第二步 step2 判断要插入的位置是否在表内 如果不在 则输出 位置不对 否则进行第三步 step3 从第n 1个节点到第i个节点全部后移1位 step5 将顺序表的表长加1 step4 在顺序表的第i个位置插入x 10 二 顺序表 插入运算的类C语言算法 voidinsert structsequenlistL datatypex inti 定义insert函数 intj if L length listsze printf overflow n elseif iL length printf positionisnocorrect n else for j L length 1 j i j L data j 1 L data j L data i x L length 11 二 顺序表 一个完整的插入运算程序 include definelistsze10structsequenlist 构建sequenlist型 intdata listsze intlength structsequenlistL 12 二 顺序表 一个完整的插入运算程序 续 voidinsert structsequenlistL intx inti 定义insert函数 intj if L length listsze printf overflow n elseif iL length printf positionisnocorrect n else for j L length 1 j i j L data j 1 L data j L data i x L length for j 0 j L length j printf d L data j 13 二 顺序表 一个完整的插入运算程序 续 main inti j y structsequenlista scanf d 14 二 顺序表 顺序表插入运算的结论 1 在线性表中插入一个数据节点需要移动顺序表的一半节点 即 n 2 2 时间复杂度 插入运算的时间复杂度与n有关 即 T n O n 15 二 顺序表 3 顺序表的基本运算 删除 step1 判断表是否为空 如果为空 则输出 无法删除 否则进行第二步 step2 判断要删除的位置是否在表内 如果不在 则输出 位置不对 否则进行第三步 step3 从第i 1个节点到第n 1个节点全部前移1位 采用覆盖的形式删除 step4 将顺序表的表长减去1 16 二 顺序表 删除运算的类C语言算法 voiddelete structsequenlistL inti 定义delete函数 intj if L length 0 printf Emptylist cannotdelete n elseif i L length printf positionisnocorrect n else for j i 1 j L length j L data j 1 L data j L length 17 二 顺序表 一个完整的删除运算程序 include 调用头文件 stidio h definelistsze10structsequenlist 构建sequenlist型 intdata listsze intlength structsequenlistL 定义sequenlist变量L 18 二 顺序表 一个完整的删除运算程序 续 voiddelete structsequenlistL inti 定义delete函数 intj if L length 0 printf Emptylist cannotdelete n elseif i L length printf positionisnocorrect n else for j i 1 j L length j L data j 1 L data j L length for j 0 j L length j printf d L data j 19 二 顺序表 一个完整的删除运算程序 续 main 定义主函数 inti j structsequenlista 定义顺序表a scanf d 调用delete 函数 20 二 顺序表 顺序表删除运算的结论 1 在线性表中删除一个数据节点需要移动顺序表的一半节点 即 n 2 2 时间复杂度 删除运算的时间复杂度与n有关 即 T n O n 21 三 线性表的链式存储结构 1 线性表顺序存储结构与链式存储结构的异同点 22 三 线性表的链式存储结构 2 单链表的形态 非空表 头节点 第一个数据节点 最后一个数据节点 head 空表 头节点 head Data域 next域 23 三 线性表的链式存储结构 3 单链表类型定义 structnode datatypedata 节点的数据域structnode next 节点的指针区 24 5 求单链表的表长 1 单链表的表长 单链表中数据节点的个数 不包括头节点 2 算法 intlength head head是指向单链表的头指针 intn 0 节点个数计数器赋初值0structnode p 定义一个node型指针pp head p指针指向表头节点while p next null p指针所指节点不是链表的最后一个节点 p p next p指针前进一个节点n 节点个数加1 return n 返回表长n 25 6 查找运算 find structnode find head x structnode p p head next p指针指向第一个数据节点while p next null 没找到该节点 则返回null 空 26 7 插入运算 insert 插入已知地址的节点 如 在p指针所指节点后面插入已知地址为s的节点 p P next s 1 s next p next 2 p next s 27 7 插入运算 insert 插入已知内容的节点 如 在p指针所指节点后面插入已知内容为x的节点 p P next s 1 s next p next 2 P next s s structnode malloc sizeof structnode s data x x 28 8 删除运算 delete 如 删除p指针所指节点的下一个节点 p p next next p next q p next q q next p next p next next 或p next q next free q 29 四 单循环链表 1 单循环链表的形态 非空表 head 空表 head r 注意 单链表只能沿着链表从前向后访问表中的各节点 无法找到某节点前面的其他节点 单循环链表可以通过任一节点访问表中的其他节点 30 四 单循环链表 2 单循环链表的删除运算 例如 一个单循环链表 没有头指针只有尾指针r 试写出删除尾指针r的前一个节点 r 31 四 单循环链表 2 单循环链表的删除运算 r Step1 找出r节点前前的那个节点p Step2 让q指向p的下一个节点 Step3 从链表中删除q所指向的节点 Step3 回收q p p next q p next next 32 四 单循环链表 2 单循环链表的删除运算 voiddelete r structnode p q 定义两个node型指针p和qp r next 让p指向r的后继节点 给p赋初值 while p next next r 找r节点的前前节点 p p next q p next 将要删除节点的地址保存到q中p next r 从链表中删除qfree q 回收被删除节点q的空间 33 五 双循环链表 1 双循环链表的形态 h a b c 非空表 h 空表 34 五 双循环链表 2 双循环链表的类型定义 每个节点有3个成员 prior 左链域 存放直接前驱节点的地址 next 右链域 存放直接后继节点的地址 data 数据域 存放本节点的信息内容 35 五 双循环链表 2 双循环链表的类型定义 structnode datatypedata 节点的数据域structnode prior next 直接前驱 后继的指针 3 双循环链表的特点 p prior next p next prior p 36 五 双循环链表 4 双循环链表的基本运算 插入 例如 在p所指节点的前面插入地址为s的节点 p p prior s 2 1 3 4 37 五 双循环链表 4 双循环链表的基本运算 插入 例如 在p所指节点的前面插入地址为s的节点 1 s prior p prior 2 s next p 3 p prior next s 4 p prior s 38 五 双循环链表 4 双循环链表的基本运算 删除 例如 删除p指针所指的节点 p p prior p next 1 2 1 p prior next p next 2 p next prior p prior 3 free p 39 六 链表的建立 1 尾插法 依次输入abc时 以尾插法建立的单链表为 head 2 头插法 依次输入abc时 以头插法建立的单链表为 head 40 历年真题演练 1 2010 4单选 对顺序存储的线性表 其长度为n 在等概率情况下 插入一个数据节点需要移动数据节点的平均次数是 An 2Bn 1C n 1 2D n 1 2 2 2010 4单选 线性表采用链式存储时 其存储空间是 A必须是连续的B一定是不连续的C可连续 也可不连续D多个节点地址必须连续 41 历年真题演练 3 2010 4填空 已知q指向单链表中一个节点 若在q指向的节点之后插入一个s指向的新节点 则所