数据结构第二章线性表.pptxVIP

数据结构第二章线性表

CATALOGUE

目录

线性表基本概念与特点

线性表顺序存储结构

线性表链式存储结构

线性表操作算法设计与分析

线性表应用案例剖析

线性表实验指导与编程实践

01

线性表基本概念与特点

线性表定义

线性表是由n（n≥0）个具有相同类型的数据元素（结点）a1，a2，…，an组成的有序集合。

逻辑结构

线性表是一种典型的线性结构，数据元素之间存在一对一的关系。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

均匀性

线性表的每个数据元素具有相同的数据类型。

基本术语

数据元素、结点、长度、空表等。

有序性

数据元素之间存在严格的顺序关系，即每个元素（除第一个外）有且仅有一个直接前驱，每个元素（除最后一个外）有且仅有一个直接后继。

数据对象集合

线性表是n（n≥0）个元素构成的有序序列。

一对一关系

线性表中数据元素之间存在一对一的关系。

相邻关系

线性表中相邻数据元素之间存在序偶关系，即除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

基本操作

初始化操作、插入操作、删除操作、查找操作等。

02

线性表顺序存储结构

顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序表定义

通常使用一维数组来实现顺序表，数组的下标可以表示元素的位置。

实现方式

在指定位置插入一个元素，需要将该位置及其后的元素后移，再插入新元素。

删除指定位置的元素，需要将该位置及其后的元素前移。

通过元素的值查找其位置，可以使用顺序查找或二分查找（针对有序顺序表）。

直接修改指定位置的元素值。

插入操作

删除操作

查找操作

修改操作

应用举例

使用顺序表实现学生成绩管理系统，可以方便地对学生成绩进行增删改查操作。

问题分析

顺序表的插入和删除操作需要移动大量元素，时间复杂度较高。同时，顺序表需要预先分配存储空间，可能会造成空间浪费或空间不足的问题。针对这些问题，可以使用链表等动态数据结构来解决。

03

线性表链式存储结构

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

单链表定义

链表中的数据是以结点来表示的，每个结点的构成包括元素(数据元素的映象)和指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

节点结构描述

构造一个空链表，即头指针为空。

初始化链表

在链表的第i个位置插入一个新节点，需要先将新节点插入到合适的位置，然后修改相邻节点的指针。

插入节点

删除链表的第i个节点，需要先找到该节点的前驱节点，然后修改前驱节点的指针，跳过要删除的节点。

删除节点

从头节点开始，依次访问每个节点，直到尾节点。

遍历链表

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

04

线性表操作算法设计与分析

01

04

05

06

03

02

查找操作

顺序查找：从线性表的一端开始，顺序扫描，直到找到所查元素为止。

二分查找：针对有序线性表，每次与中间元素比较，根据大小关系缩小查找范围，直到找到所查元素或查找区间为空。

插入操作

在指定位置插入元素：将插入位置之后的元素依次后移，腾出插入位置，然后插入新元素。

在有序线性表中插入元素：找到插入位置，然后将该位置之后的元素依次后移，腾出插入位置，最后插入新元素。

删除指定位置的元素

将删除位置之后的元素依次前移，覆盖删除位置，同时释放被删除元素所占空间。

删除指定值的元素

遍历线性表，找到与指定值相同的元素并删除，同时释放被删除元素所占空间。

修改操作

直接通过元素的索引或指针访问该元素，并将其值修改为新的值。

时间复杂度

查找操作的时间复杂度取决于查找算法和线性表的结构。对于顺序查找，时间复杂度为O(n)；对于二分查找，时间复杂度为O(logn)。

插入和删除操作的时间复杂度取决于线性表的结构。对于顺序存储的线性表，插入和删除操作的时间复杂度为O(n)；对于链式存储的线性表，插入和删除操作的时间复杂度为O(1)。

空间复杂度

线性表的空间复杂度主要取决于存储元素的数量和每个元素所占用的空间大小。对于顺序存储的线性表，空间复杂度为O(n)；对于链式存储的线性表，空间复杂度为O(n+m)，其中m为指针或引用所占用的空间大小。

01

02

03

04

05

05

线性表应用案例剖析

使用栈来辅助计算后缀表达式或中缀表达式的值，通过入栈和出栈操作实现运算符和操作数的匹配。

表达式求值

利用栈的特性，对输