数据结构（C语言描述）教学课件斯庆巴拉第2章线性表.ppt

《数据结构（C语言描述）教学课件斯庆巴拉第2章线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表学习重点：线性表的概念及表示方法线性表的顺序存储方式及操作的实现算法线性表的链式存储方式及操作的实现算法第2章线性表2.1实例：学生信息的存储2.2线性表的逻辑结构2.3线性表的顺序存储2.4线性表的链式存储2.5动态存储管理2.6应用举例：线性表的建立、合并本章总结2.1实例：学生信息的存储2.1.1问题描述2.1.2问题的分析2.1.3实现算法2.1.1问题描述对在校生信息的管理是一项庞大的工程,它要求能够完成新、老学生信息的输入、修改、插入和删除工作等等。下面就给出一张学生基本情况登记表如表2-1所示：学号姓名性别年龄民族出生日期

2、家庭地址照片035001范云女18汉1986-6-5北京市朝阳区略035002杨杰男20汉1984-10-6北京市朝阳区略035003刘倩女21回1983-9-9天津市海河区略035004张峰男19汉1985-1-23天津市东河区略┆┆┆┆┆┆┆┆2.1.2问题的分析学生基本情况登记表中包含每个学生的基本情况，如学号、姓名、性别等等。在此表中学生的基本信息的排列是以学号为依据，从小到大排列。从数据结构的定义来讲，可将表看成是以学生记录为元素，以学号的升序排列为关系，经常进行插入、删除和查找等操作的数据结构（线性结构）。要用计算机解决此问题需要做以下

3、工作：第一，信息以什么形式表示并存储到计算机中；第二，各种操作的具体实现方法（算法）。三个方面学生情况登记表是一个由多条记录组成的表格，可用编程语言的结构体类型表示，此时记录中的每个数据项对应结构体中的一个成员，多条记录可定义成一个结构体数组。定义如下：structstudent{intnum;//表示学号charname[12];//表示姓名┆//其余省略}；对信息进行存储时，元素以数组形式存放在连续的存储空间中，以物理位置来体现关系。但随时存在退学、转学等情况，所以分配时应多分配一些存储空间，并用一个整型变量给出元素个数。定义如下：#defin

4、esizemaxsize//分配的存储单元个数structList{studentstu[size];//保存学生记录intlen;//学生人数}顺序存储方式2.1.3实现算法以删除操作为例，则实现步骤为：第一步，在数组中查找给定学号的学生记录。第二步，对数组元素进行删除。因给数组分配的单元是连续的，所以删除一个元素需要把删除元素后面的所有元素都往前移一位。实现算法：删除学号为num的学生记录，并保存到t中。voidDeleteList(List&L,intnum,student&t){inti,j;for(i=1;i<=L.len;i++){if

5、(L.stu[i].num==num)//进行比较{t=L.stu[i];//保存所删学生记录for(j=i+1;j<=L.len;j++)L.stu[j-1]=L.stu[j];//进行元素移位L.len--;//长度减1return;}}if(i>L.len)printf("找不到此学生记录！");}结论：1给定的学生登记表中的记录以学号的从小到大排列，记录间是一对一的关系线性结构。2除了第一条记录和最后一条记录以外，所以记录都只有唯一的前驱记录和后继记录。2.2线性表的逻辑结构2.2.1线性表的逻辑结构2.2.2线性表的基本操作线性表是一

6、种线性结构，它具有以下特点：l构成线性表的数据元素之间的关系是一对一的关系l有且仅有一个第一个元素和一个最后一个元素l除第一个元素外，所有元素有且仅有一个前驱元素l除最后一个元素外，所有元素有且仅有一个后继元素2.2.1线性表的逻辑结构线性表是相互间存在一对一关系的相同类型元素的有限集。（元素个数是确定的）线性表表示为：（a1,a2,a3,┄,ai-1,ai,┄,an）其中，ai∈Elemtype代表线性表的元素类型,n为线性表的元素个数，通常称n为线性表的长度(n≥0)，n=0线性表是空表，否则为非空表。a1为线性表的第一个元素，an为线性表的最

7、后一个元素。它是一个由n个元素组成的以逻辑顺序表示元素间关系的线性结构。例：线性表2=（‘A’，‘B’，‘C’，‘D’）分析：线性表2是一个元素类型为字符型的由4个元素组成的有限集。‘A’是线性表的第一个元素，‘D’是线性表的最后一个元素。元素之间的关系：‘B’的前一个元素是‘A’，后面元素是‘C’，所以称‘A’是‘B’的前驱元素，而‘C’是‘B’的后继元素。除了‘A’以外所有元素都有唯一的前驱，除了‘D’以外所有元素都有唯一的后继。2.2.2线性表的基本操作线性表的常用操作有以下几种：InitList(L)初始化。（建立一个空表L）LengthL

8、ist(L)求长度。求线性表L中的元素个数。GetList(L,i,elem)取元素。EmptyList(L)判空表。Lo