《概论线性表》课件

概论线性表线性表的定义和特点定义特点线性表是一种**线性**结构，它由一系列**有限**的**相同类型**每个数据元素都只有一个**直接前驱**，除了第一个元素；每个数据元素组成，这些元素按**线性顺序**排列数据元素都只有一个**直接后继**，除了最后一个元素线性表的基本操作插入删除在表中指定位置插入新的元素从表中删除指定位置的元素查找修改在表中查找指定元素的位置修改表中指定位置元素的值线性表的顺序存储结构顺序存储地址计算线性表中的元素存储在连续的内存单元中，并用一个数组来表示元素的地址可以通过基地址和元素在数组中的索引来计算元素地数组的起始地址称为基地址，每个元素占用的内存空间大小相同址=基地址+元素索引*元素大小链式存储结构链式存储结构是一种非连续存储结构，它通过指针将逻辑上相邻的结点链接在一起每个结点包含数据域和指针域，数据域存储数据元素，指针域指向下一个结点链式存储结构的特点是逻辑上相邻的结点在物理上可以不相邻；存储空间可以动态分配；插入和删除操作比较方便，不需要移动元素顺序表的基本操作插入删除在指定位置插入元素，需要移动后续删除指定位置的元素，需要移动后续元素元素查找根据元素值查找元素所在位置顺序表的插入与删除插入1移动元素删除2覆盖元素链表的基本操作插入删除在指定位置插入新节点，需要修删除指定节点，需要修改指针指改指针指向向以断开连接查找修改遍历链表，比较节点的值，找到找到目标节点，修改其数据域目标节点单链表的插入与删除插入1找到插入位置,修改指针指向删除2找到删除节点,修改指针指向双向链表双向链表是一种链表结构，每个节点包含两个指针，分别指向其前一个节点和后一个节点这使得可以在链表中双向遍历，并且可以快速访问节点的前驱和后继循环链表循环链表是一种特殊的链表，其最后一个节点的指针指向链表的第一个节点，形成一个闭环循环链表的优点是可以在链表中进行循环遍历，例如，可以用于实现一个循环队列静态链表数组存储指针域节省空间利用数组的连续存储空间，模拟链表结构每个结点包含数据域和指针域，指针域指向相比于传统的链表，静态链表可以节省空间下一个结点的位置，避免动态内存分配带来的开销稀疏矩阵的压缩存储减少存储空间提高效率12利用矩阵中非零元素的稀疏性压缩存储可以提高矩阵运算的，减少存储空间的需求效率，减少不必要的存储和计算多种压缩方法3三元组表、十字链表、压缩行存储等方法可根据矩阵的特点选择稀疏矩阵的基本运算加法减法相同位置元素相加相同位置元素相减乘法行向量与列向量相乘多项式的表示和运算多项式表示多项式运算多项式是单个变量的常数或变量的幂的代数和，例如ax2+bx多项式可以进行加减乘除等运算多项式加法和减法是通过合并+c，其中a，b，c是常数，x是变量同类项完成的多项式乘法则是将两个多项式的每一项分别相乘多项式的加法和乘法多项式加法1系数对应相加多项式乘法2每个单项式相乘多项式的除法和求导多项式除法多项式除法是多项式运算中的重要操作之一，用于求解一个多项式除以另一个多项式的商式和余式多项式求导多项式求导是另一种重要的多项式运算，用于求解多项式的导函数，它描述了多项式函数的变化率广义表的定义和性质定义性质广义表是一种递归的数据结构，广义表具有递归性质，这意味着可以看作是线性表的推广它允它可以包含自身作为元素它也许元素为原子或子表可以有多级嵌套结构广义表的存储结构广义表的存储结构主要有两种•**线性存储结构**采用顺序存储的方式，将广义表的所有元素存储在连续的内存空间中，并使用指针来记录各个元素之间的关系•**树形存储结构**采用树形结构存储广义表，用节点来表示广义表中的每个元素，节点之间使用指针连接，体现出广义表的层次关系广义表的基本操作创建广义表插入元素删除元素访问元素创建新的广义表，可以通过输在指定位置插入新的元素，保删除指定位置的元素，同时调获取广义表中指定位置的元素入元素来进行构建持广义表的结构完整性整广义表的结构值队列的定义和特点先进先出单向操作队列遵循先进先出的原则，先进入队队列通常只能在一端插入元素（队尾列的元素将先被取出），从另一端删除元素（队头）应用广泛队列广泛应用于模拟系统、任务调度、缓冲管理等领域队列的顺序存储实现循环队列数据结构解决顺序队列假溢出问题，提高空间利用率用数组实现队列，并用两个指针分别指向队头和队尾，方便进行入队和出队操作队列的链式存储实现链式存储结构利用指针来连接数据元素，克服了顺序存储结构的局限性链式存储结构中的队列，称为链队列，它由两个指针组成队头指针和队尾指针队头指针指向队列的第一个元素，队尾指针指向队列的最后一个元素队列的基本操作入队出队12将一个新元素加入到队尾删除队首元素并返回其值取队首元素判断队列是否为空34返回队首元素的值但不删除它判断队列是否为空，返回真假值栈的定义和特点后进先出LIFO单一入口和出口栈是一种线性数据结构，遵循后栈只有一个入口和出口，称为栈进先出的原则，即最后加入的元顶，所有元素的插入和删除操作素最先被取出都在栈顶进行应用场景栈广泛应用于函数调用、表达式求值、编译器设计等领域栈的顺序存储实现顺序存储方式使用数组来存储栈元素，数组中的第一个元素是栈底，最后一个元素是栈顶栈顶指针指向栈顶元素，当栈为空时，栈顶指针指向数组的第一个元素顺序存储实现方式简单，但是存在空间浪费的问题，因为需要预留足够的空间来存储栈元素栈的链式存储实现链式存储结构，可以动态地申请内存空间，不受数组大小限制，避免溢出问题使用链表存储栈，每个节点包含数据域和指针域，指针指向下一个节点栈顶指针指向链表的第一个节点，实现入栈和出栈操作栈的基本操作入栈出栈将一个元素压入栈顶，栈的大小加1弹出栈顶元素，栈的大小减1取栈顶元素判断栈空获取栈顶元素，但不删除它判断栈是否为空，返回布尔值迭代与递归迭代递归使用循环语句，重复执行相同的代码块，直到满足条件为止函数自己调用自己，直到满足条件为止总结与思考线性表是数据结构中非常基础且重要的内容，是理解更复杂数据结构的基础通过对线性表的学习，我们不仅掌握了线性表的基本概念和操作，更重要的是培养了对数据结构的抽象思维能力和解决问题的能力。