数据结构课件(c语言).ppt

1 第2章线性表 2 1线性表的定义及其基本操作2 2线性表的顺序存储2 3线性表的链式存储2 4线性表的存储方式小结 2 线性结构是一种简单的数据结构 这种结构具有以下特点 在数据元素的非空有限集合中 有且只有一个 首 数据元素 有且只有一个 末 数据元素 除 首 数据元素外 其它数据元素有且只有一个直接前驱 除 末 数据元素外 其它数据元素有且只有一个直接后继 线性表属于线性结构的范畴 是最常用的数据结构 2 1线性表的定义及其基本操作 3 线性表 linearlist 是具有相同数据类型的n n 0 个数据元素a1 a2 an组成的有限序列 其中n称为数据元素的个数或线性表的长度 当n 0时称为空表 n 0时称为非空表 通常将非空的线性表记为 a1 a2 ai 1 ai ai 1 an 其中数据元素ai 1 i n 是线性表中第i个数据元素 它是一个抽象的符号 其数据类型可以根据具体情况而定 i称为数据元素ai在线性表中的位序 2 1 1线性表的定义 例2 1大写英文字母表 A B C D Y Z 其中每个字母为一个数据元素 A是字母序列的 首 数据元素 Z是字母序列的 末 数据元素 其它每个字母有且只有一个直接前驱和一个直接后继 这个序列是一个线性表 例2 2教师信息表 其中每位教师的有关信息为一个数据元素 所有教师的信息集合构成一个线性表 5 2 1 2线性表的基本操作 1 InitList L 2 InsItem L i item 3 DelItem L i 4 ClearList L 5 ListEmpty L 6 LenList L 7 LocItem L item 8 GetItem L i item 9 GetPrior L item prior 10 GetNext L item next 6 2 2 1顺序表的定义所谓顺序表 就是在内存中开辟一片连续的存储空间 将线性表中数据元素按照数据元素之间的逻辑顺序依次存放其中 需注意的是该连续存储空间所能容纳的数据元素个数不得小于顺序表的长度 在顺序表中 逻辑关系相邻的两个元素在物理位置上也相邻 线性表的顺序存储结构很容易确定每个数据元素在存储单元中起始地址的相对位置 假设线性表中元素为 a1 a2 ai 1 ai ai 1 an 设第一个元素a1的内存地址为LOC a1 而每个元素在计算机内占t个存贮单元 则第i个元素ai的首地址LOC ai 为 LOC ai LOC a1 i 1 t 其中1 i n 2 2线性表的顺序存储 7 例2 3设有顺序表S 其描述如下 typedefstruct charno 10 charname 20 floatgrade 3 floataver Student Studentt 30 线性表中每个数据元素所占存储单元为10 1 20 1 3 4 1 4 46 假设顺序表中第一个数据元素的存储地址为d 则第i个数据元素的存储地址为d i 1 46 8 由于顺序表的表长通常是可变的 因此可定义一个整型变量来记录表长 且需要定义一个足够大的数组来保存数据 defineMAXSIZEmaxlentypedefintelemtype typedefstruct elemtypedata MAXSIZE intlen 顺序表的长度 Sequenlist 9 2 2 2顺序表的基本操作 1 初始化顺序表InitList L 算法说明 创建一个空的顺序表 将该顺序表的表长设为零 算法实现 Sequenlist InitList Sequenlist L L Sequenlist malloc sizeof Sequenlist L len 0 return L L为指向Sequenlist类型的指针变量 10 2 在顺序表中插入数据元素InsItem L i item intInsItem sequenlist L inti elemtypeitem L data 0 中存储表L的第一个数据元素a1 intj if L len MAXSIZE 表满 插入操作失败 printf Thelistisoverflow n returnNULL elseif i L len 1 插入位置设定不合适 插入操作失败 printf Positionisnotcorrent n returnNULL else for j L len 1 j i 1 j L data j 1 L data j L data i 1 item L len 顺序表表长增1 return1 11 else for intj i j len 1 j L data j 1 L data j 元素前移 L len 顺序表表长减1 return1 3 在顺序表中删除数据元素DelItem L i intDelItem Sequenlist L inti intj if L len 0 表空 删除操作失败 printf Listisempty n returnNULL elseif i L len 删除元素位置设定不合适 删除操作失败 printf Deleteitemfail n returnNULL 12 4 定位查找LocItem L item intLocItem Sequenlist L intitem L data 0 中存储表L的第一个数据元素a1 inti j j L len if j 0 表空 定位操作失败 printf Thesequenlistisempty return0 for i 0 i j i 匹配item的值 if L data i item return i 1 printf Theitemisnotinthissequenlist return0 13 2 3线性表的链式存储线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在存储器中物理位置上也是相邻的 数据元素之间的邻接关系由存储单元的邻接关系来体现 通过数据元素与顺序表起始地址之间的相对位置 可方便的随机存取表中任一元素 但当插入 删除数据元素时 则需要移动大量数据元素 如何提高插入 删除数据元素的效率 本节将介绍线性表的另一种存储结构 线性表的链式存储结构 链式存储是通过动态分配存储单元来存储线性表中的元素 这些单元在物理上可以是连续的 也可以是不连续的 为了能正确地描述元素之间的逻辑关系 除了存储元素本身的信息外 还需存储表示元素之间逻辑关系的信息 这两部分信息组成数据元素ai的存储映像 称为结点 在链表中 每个结点所占的存储空间分为两部分 存放数值的域称为数据域 存放结点之间相互关系的域称为指针域 跟据结点的连接方式不同 可分为单链表 双向链表 循环链表 14 2 3 1单链表在定义的链表中 若每个结点除了存储数据元素本身信息的数据域外 只含有一个指针域用来存放其直接后继数据元素的存储地址 称这样的链表为单链表或线性链表 其结点结构如图所示 15 用C语言描述单链表结点结构如下 typedefintelemtype 定义新类型 类型名为elemtype typedefstructnode elemtypedata 数据域 structnode next 指针域 linklist 16 在单链表中 第1个结点的指针域记录着第2个结点的地址 第2个结点的指针域记录着第3个结点的地址 以此类推 第n 1个结点的指针域记录着第n个结点的地址 第n个结点后再没有其他结点 则第n个结点的指针域为NULL 因此 单链表中结点之间的逻辑关系 是通过每个结点的指针域存储的该结点的直接后继结点的地址来体现的 即指针是数据元素之间逻辑关系的映像 例2 4线性表 A B C D E F 的单链表物理存储示意图及逻辑存储示意图如下 17 例2 4线性表 A B C D E F 的单链表物理存储示意图及逻辑存储示意图如下 18 单链表的有关操作如下 1 初始化单链表InitList L linklist InitList linklist L 建立一个带头结点的单链表 L linklist malloc sizeof linklist L next NULL return L 19 2 建立单链表CreatList n linklist creatlist intn intx i 设数据元素的类型为int linklist L r p InitList L 构建头结点空间 r L for i 1 idata x p next NULL r next p r r next 指针r始终指向链表中末数据元素所在位置 return L 20 3 在单链表中插入数据元素InsItem L item i 给定的序号来插入InsItem linklist L elemtypeitem inti intj linklist p p L j 1 t linklist malloc sizeof linklist 生成新结点t t data item if L next NULL if i 0 若L为空表且要求将新结点插入到第0个位置 L next t t next NULL return 1 elsereturn 0 若L为空表且要求将新结点插入到第非0个位置 则操作失败 While p next NULL 21 3 在单链表中插入数据元素InsItem L item i 按给定的值来插入InsItem linklist L elemtypeitem elemtypek linklist q p t t linklist malloc sizeof linklist 生成新结点t t data item if L next NULL 若为空表 则没有值为k的结点 插入操作失败 printf Thelinklistisempty n return 0 else q L p L next while p NULL 查找值为k的结点 if p data k q p p p next elsebreak if p NULL 如p NULL 则没有值为k的结点 插入操作失败 printf Thenode disnotexist n k return 0 else 若找到值为k的结点 则在值为k的结点前插入新结点 q next t t next p return 1 22 4 在单链表中删除数据元素DelItem L i DelItem linklist L inti 删除给定序号的结点 intj linklist p p L j 1 if L next NULL L为空表 无结点可删除 printf Thelinklistisempty n return 0 While p next NULL if p NULL 若没有第i个结点 则删除操作失败 printf Thenode disnotexist n i return 0 else 若找到第i个结点 则删除并释放第i个结点 q p next p next p next next free q return 1 23 删除给定值的结点DelItem linklist L elemtypeitem linklist q p t if L next NULL 若为空表 则没有值为item的结点 删除操作失败 printf Thelinklistisempty n return 0 else q L p L next while p NULL 查找值为item的结点 if p data item q p p p next elsebreak if p NULL 如p NULL 则没有值为item的结点 删除操作失败 printf Thenode disnotexist n k return 0 else 若找到值为item的结点 则删除并释放该结点 q next p next free p return 1 24 2 3 2双向链表 在单链表中 我们可以方便的访问其中某个结点的后继结点 这是因为单链表的结点结构中有一个指针域用来记录结点的后继结点地址 但要想访问某个结点的前驱结点时 则要从头结点开始 顺链查找 这样效率太低 可以通过使用双向链表来提高效率 所谓双向 是指其结点结构中包含两个指针域 分别记录相应结点的直接前驱结点地址和其直接后继结点地址 如图所示 25 用C语言描述单链表结点结构如下 typedefintelemtype 定义新类型 类型名为elemtype typedefstructdouble node elemtypedata 数据域 structdouble node prior next 前驱指针域 后继指针域 double linklist 26 例2 5线性表 A B C D E F 的双向链表物理存储示意图及逻辑存储示意图如下 27 1 初始化双向链表InitDouList L double linklist InitDouList double linklist L 建立一个带头结点的双向链表 L double linklist malloc sizeof double linklist L prior NULL L next NULL return L 28 2 在双向链表中插入数据元素InsDouItem L item i 29 3 在双向链表中删除数据元素DeleDouItem L item i 30 2 3 3循环链表循环链表是一种首尾相接的链式存储结构 在这种存储结构中 每一个结点的指针域都记录着它的下一个结点的地址 最后一个结点的指针域记录头结点的地址 使链表链接呈环状 这样的链表就称之为单循环链表 如图2 9所示 与单循环链表类似 将双向链表中尾结点的后继指针域记录链表的头结点的地址 头结点的前驱指针域记录尾结点的地址 即构造了双向循环链表 如图2 10所示 在循环链表中 从任意一个结点出发均可访问到表中其他结点 31 32 例2 6 已知L1和L2分别为两个单循环链表的头指针 试遍写一算法将链表L2连接在链表L1的后面 连接后形成的单循环链表头指针为L1 linklist Combination linklist L1 linklist L2 linklist p q p L1 next q L2 next while p next L1 p p next while q next L2 q q next p L2 next q next L1 free L2 return L1 33 2 3 4静态链表以上我们提到的线性表的各种链式存储结构 都是根据需要动态分配及释放其结点所占的内存空间 这种链表称为动态链表 还有一种链表叫作静态链表 与动态链表的区别在于静态链表需要预先分配一个较大的空间 以备以后需求 因此 静态链表可用一维数组来实现 其基本结构为 defineMAXSIZEmaxlentypedefintelemtype 定义新类型 类型名为elemtype typedefstructSeqLinkList elemtypedata 数据域 intnext 下标指针域 SLList MAXSIZE 34 例2 6线性表 A B C D E F 的静态链表存储示意图如下 请在第4个数据元素之前插入一新的数据元素G 35 2 4线性表的存储方式小结线性表的存储方式主要分两大类 一类是顺序存储 一类是链式存储 其中链式存储又包括单链表 双向链表 循环链表及静态链表等多种存储结构 不同的存储结构各有其优缺点 顺序存储结构是处理线性表时较常用的一种存储方式 它利用数组来实现数据元素的存储 数据元素的物理存储顺序与数据元素之间的逻辑关系相对应 可以方便的实现对数据的随机存取 是一种随机存储结构 如对一个线性表的主要操作是查询 则可采用这种存储方式 36 但正因为它是利用数组来实现存储 就限定了它需要预先设定好线性表中数据元素可能达到的最大个数 如果对线性表操作过程中 表长变化较大 则设定最大表长就比较困难 也可能造成部分内存空间的浪费 另外 为了保持顺序表中数据元素有序性 在插入或删除数据元素时 需要移动大量的数据 这样对需要频繁进行插入删除操作的线性表来说 效率太低 链式存储结构恰与顺序存储结构互补 组成链表的每个结点所占空间是动态申请及释放的 存储空间的使用更灵活 当线性表表长不确定时 可采用动态链表作为存储结构 链式存储结构中数据元素之间的逻辑顺序是由结点的指针域来控制的 这样在插入或删除数据元素时 只要修改指针域的值即可 不需要移动大量数据 但当每个结点数据域所占空间不是很大时 指针域所占空间就会显得很大 因此 具体使用哪种存储结构 还视实际问题而定