数据结构案例教程课件：线性表.pptx

线性表

2025/2/62导学问题1：简易的学生信息管理系统实现一个简易的学生信息管理系统，其中学生信息包括：学号、姓名、性别、年龄、专业等。要求系统能提供建立、查询、删除和增加学生信息等功能。

2025/2/63导学问题2：简易的商品信息管理系统实现一个简易的商品信息管理系统，其中商品信息包括：商品代码、品名、单价、库存量等。要求系统能提供建立、查询、删除和增加商品信息等功能。

2025/2/64程序设计的实质是对实际问题选择一种合适的数据存储结构，并设计基于此结构上的一批高效的处理算法。因此，首先需要分析实际问题中需要处理的数据对象的特点。问题分析

2025/2/65学生信息表问题分析

2025/2/66商品信息表问题分析

2025/2/67考虑：数据元素之间的关系是什么？——数据如何表示？数据元素如何存储？数据元素如何处理？

2025/2/682.1知识学习2.1.1线性表的概念线性表是具有相同数据类型的n（n≥0）个数据元素组成的有限序列，通常记为L=(a1，a2，…，ai?1，ai，ai+1，…，an)a1a3a4ana2

2025/2/692.1知识学习非空线性表的特性有且仅有一个表头结点a1，它没有前驱，而仅有一个后继a2；（2）有且仅有一个表尾结点an，它没有后继，而仅有一个前驱an－1；（3）其余的结点ai（2≤i≤n?1）都有且仅有一个前驱ai－1和一个后继ai+1。2.1.1线性表的概念

2025/2/6102.1知识学习2.1.2线性表的顺序存储结构及基本操作2.1.2.1顺序结4存储要点用一段地址连续的存储单元依次存储线性表中的数据元素例：（34,23,67,43）

2025/2/611例：（34,23,67,43储空间的起始位置4用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度

2025/2/6122.1知识学习2.1.2线性表的顺序存储结构及基本操作2.1.2.1顺序结构数据元素为整型数的顺序表类型描述。constintMAXSIZE=100;//顺序表最大长度typedefstruct{ intdata[MAXSIZE];//存放数据元素的数组 intlength;//顺序表的长度}SeqList;

2025/2/613算法描述：voidInitList_Seq(SeqListL){L.length=0;}初始化操作——创建空表datalength02.1.2.2顺序表基本操作的实现

2025/2/614初始化操作——创建长度为n的顺序表2.1.2.2顺序表基本操作的实现顺序表数组a351224334253512243342算法描述：voidCreatList_Seq(SeqListL,inta[],intn){if(nL.MAXSIZE){cout参数超出顺序表容量endl;exit(1);}L.length=0;for(inti=0;in;i++)L.data[L.length++]=a[i];}

2025/2/615遍历顺序表2.1.2.2顺序表基本操作的实现voidShow_Seq(SeqListL){ for(inti=0;iL.length;i++) coutL.data[i]; coutendl;}算法描述：

2025/2/616求顺序表长度2.1.2.2顺序表基本操作的实现intListLength_Seq(SeqListL){ returnL.length;}算法描述：

2025/2/617按值查找元素：535a1a2a3a40123442241233a5例：在（35,33,12,24,42）中查找值为12的元素，返回在表中的序号。iii注意序号和下标之间的关系2.1.2.2顺序表基本操作的实现

2025/2/618intLocateElem_Seq(SeqListL,inte){for(inti=0;iL.length;i++) if(L.data[i]==e) returni+1;return0;}按值查找算法描述：时间复杂度？2.1.2.2顺序表基本操作的实现

2025/2/619插入操作2.1.2.2顺序表基本操作的实现插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,