《数据结构 教学课件 ppt 作者 宗大华 陈吉人 02线性表》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 宗大华 陈吉人 02线性表（84页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,线性表是程序设计中最基本、最常用的一种数据结构。处理是定义在数据的逻辑结构上的，但其实现则有赖于所采用的存储结构。因此，采用不同的存储结构，会对线性表上的处理实现产生直接的影响。,本章主要介绍以下几个方面的内容：, 线性表的基本知识； 线性表的顺序存储实现； 线性表的链式存储实现（单链表、双链表、循环链表）； 线性表的具体应用举例。,2.1 线性表的基本知识,所谓“线性表”，是由具有相同类型的有限多个数据元素组成的一个有序序列。 若把一个线性表取名为L，里面有n（n0）个元素，每个元素用ai（1in）表示， 下标代表该元素在线性表中的位置，那么可以把线性表L记为： L = (a
2、1 , a2, , ai, ai+1, , an1, an ),线性表中数据元素的个数n，称为线性表的“长度”。当n=0时，表示线性表中不包含任何元素，称其为“空表”。若线性表L为空，则记为L =（）或L = 。在线性表中，对任意一对相邻结点ai和ai+1 （1in1），称ai为ai+1的“直接前驱”，称ai+1为ai的“直接后继”。,图2-1 相邻结点间的关系,如果线性表中元素的值与它的位置之间存在联系，那么称这种线性表为“有序线性表”；如果线性表中元素的值与它的位置之间没有特殊的联系，那么称这种线性表为“无序线性表”。,由于线性表的元素间具有线性关系，因此一个非空线性表的特点是： 有且仅有
3、一个起始结点a1，它没有直接前驱，只有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，只有一个直接前驱an1； 其余结点ai（2in1）都有且仅有一个直接前驱ai1和一个直接后继ai+1。,对于一个线性表，可以根据需要在其上定义各种操作处理。经常要求的处理有： 创建一个新的线性表，或删除一个已经存在的线性表； 使线性表增长（即插入一个元素）、使线性表缩短（删除一个元素），增长或缩短后元素间仍将保持线性关系；, 得到当前线性表里拥有的元素个数（测试出线性表的长度）； 查找到所需要的线性表元素的值，读出这个值，或者对这个值进行修改； 从一个元素出发，得到它的前驱结点和后继结点； 要实
4、现如上列出的、定义在线性表上的操作处理，必须与采用的存储实现方式一起来考虑。,2.2 线性表的顺序存储实现,2.2.1 顺序表,采用顺序式存储结构存放一个线性表时，把线性表中的数据结点按其逻辑次序依次存储在内存中的一块地址连续的存储区里。这时，线性表中逻辑上邻接的两个数据结点，其存储结点在物理位置上也是相邻接的。以这种顺序存储结构实现的线性表，被称为“顺序表”。,假定存储结点的数据类型为elemtype，每个存储结点所需的存储量为size。顺序表Sq第1个存储结点a1的起始地址为LOC（a1），那么顺序表Sq的第2个存储结点a2的起始地址LOC(a2)= LOC(a1)+size。顺序表Sq第
5、i个存储结点ai的起始地址LOC（ai）为： LOC(ai)= LOC(a1)+size (i1) （2-1）,图2-2 线性表的顺序存储结构,由于顺序表中任一个存储结点的位置可以通过计算得到，所以对顺序表中的任何一个数据元素的访问，都可以在相同的时间内实现。,由于顺序表需要占用内存中的连续存储区，因此为其分配一块存储区域后，在该区域里能够容纳的数据元素的个数就受到了限制。 由于顺序表中元素之间是一种线性的逻辑关系，因此在往顺序表里插入或删除一个数据元素时，势必要对原有数据元素进行移动，以求维持这种线性关系。,1创建一个顺序表,2.2.2 顺序表的基本算法描述,算法2-1 创建顺序表的算法。
6、创建一个顺序表Sq，算法名称为Create_Sq()，参数为Sq、Sq_num、Sq_max。,Create_Sq (Sq，Sq_num，Sq_max) elemtype SqMAX*size ; /* 通过数组，申请一个连续的存储区 */ Sq_num = 0; /* 将顺序表设置为空表 */ Sq_max = MAX ; /* 将顺序表可容纳的最多元素个数设置为MAX */ return Ok; ,算法2-2 在顺序表指定位置后插入元素的算法。,2往顺序表中插入一个新数据元素,图2-4 顺序表插入前、后的状态示意,在顺序表Sq的第i个位置之后插入新数据元素x，算法名称为Insert_Sq
7、()，参数为Sq、i、x。算法约定：iSq_num时，新数据结点插入在表尾。,Insert_Sq (Sq, i, x) if (Sq_num = Sq_max) /* 顺序表已满，不能再插入 */ printf (“The sequential list is full !“); if (iSq_num) i = Sq_num; /* 插入在表尾 */ for (j=Sq_num; ji; j-) /* 将Sq_num到i+1个元素后移 */ Sqj = Sqj-1 ; Sqj = x ; /* 插入新元素 */ Sq_num+ ; /* 计数单元加1 */ ,算法2-3 删除顺序表指定位置处
8、元素的算法。 删除顺序表Sq中第i个位置处的数据元素，该结点数据域中的值存入变量x，算法名称为Delete_Sq ()，参数为Sq、i、x。,3删除顺序表中的一个数据元素,Delete_Sq (Sq，i，x) if (iSq_num) /* 位置参数i错 */ return ERROR ; x = Sqi ; /* 把欲删除元素的数据存入x */ for (j=i+1; j=Sq_num; j+) /* 将后一个元素往前移动一个位置 */ Sqj-1 = Sqj ; Sq_num=Sq_num-1; /* 表中元素个数减1 */ ,图2-5 顺序表里删除元素示意,算法2-4 查找顺序表中第一个
9、与给定数据相等的元素的算法。 给定数据x，在顺序表Sq中查找第一个与它相等的数据元素。如果查找成功，则返回该元素在表中的位置；如果查找失败，则返回0。算法名称为Locate_Sq ()，参数为Sq、Sq_num和x。,4在顺序表中查找一个数据元素,Locate_Sq (Sq, Sq_num, x) for (i=1; i=Sq_num; i+) if (Sqi = x) /* 查找成功，返回元素位置i */ return (i) ; if (i = Sq_num) /* 查找失败，返回0 */ return (0) ; ,算法2-5 打印顺序表中各结点值的算法。 算法描述 当顺序表Sq不空时，
10、将各个结点的值打印输出。算法名称为Print_Sq()，参数是Sq、Sq_num。,5打印顺序表的各结点值,Print_Sq(Sq, Sq_num) if (Sq_num = 0) printf (“The sequential list is empty !“); else for (i=1; i=Sq_num; i+) printf (“%d“, Sqi); ,算法2-6 获取顺序表现有元素个数的算法。 算法描述：由于顺序表当前的元素个数，在其管理信息单元Sq_num里记录，因此只需将顺序表Sq的Sq_num当前值读出即可。算法名称为Length_Sq()，参数是Sq_num。,6求顺序表
11、的长度,Length_Sq(Sq_num) printf (“The Length of sequential list is =%d“, Sq_num); ,算法2-7 往顺序表末尾添加新元素的算法。 往顺序表Sq的末尾添加一个新的数据元素x。算法名称为Append_Sq()，参数为Sq、Sq_num、Sq_max、x。,7往顺序表末尾添加一个新的数据元素,Append_Sq(Sq, Sq_num, Sq_max, x) if (Sq_num = Sq_max) printf (“The sequential list is full !“); /* 顺序表已满，不能再插入 */ else
12、/* 能够插入 */ SqSq_num+1 = x ; Sq_num = Sq_num+1 ; ,例2-4 设计一个算法，将顺序表： Sq= (a1, a2,., ai, ai+1, , an1, an ) 中的元素进行逆置，即把顺序表Sq中的元素排列顺序改换成： Sq = (an, an1, , ai+1 ，ai, , a2, a1),解：为算法取名Invert_Sq ()，参数是Sq、Sq_num。 Invert_Sq(Sq, Sq_num) if (Sq_num = 0) printf (“The sequential list is full !“); else j = Sq_num
13、; for (i=1; i=j; i+, j-) temp = Sqi; /* 把第i个元素内容暂存于临时单元temp */ Sqi = Sqj; /* 把第j个元素存入表的第i个元素 */ Sqj = temp ; /* 把temp里内容存入表的第j个元素 */ ,图2-6 数据元素间的交换示意,2.3 线性表的链式存储实现,采用链式存储结构存放数据时，数据元素间的邻接关系不是直接通过存储结点间的位置关系反映出来，而是由每个存储结点里的指针来指明。因此，链式存储结构不要求邻接的数据元素在物理位置上也是邻接的。,2.3.1 单链表,以链式存储结构实现的线性表，被称为“链表（Linked Lis
14、t）”。链表里每一个存储结点除了包含数据域外，还必须含有反映数据间逻辑关系的指针域。如果存储结点里只有一个指向表中下一个结点的指针域，那么这样的链表称为“单链表”。,图2-7 单链表中存储结点的示意,单链表采用的链式存储结构，优点是不以表的总存储需求进行存储分配，而是以单个数据存储结点的大小（size）来进行动态存储分配，即当有新的数据元素希望进入链表时，就按照存储结点的大小向系统提出存储请求。,图2-8 单链表示意,单链表表头指针的作用是十分重要的，因为从它可以找到表的第1个存储结点，然后才能够沿着各结点的指针域找到表中的其他所有结点。 当单链表为空（即长度为0）时，其表头指针Head=NU
15、LL。,我们假定，如果指针p指向一个单链表的存储结点，那么“p-Data”表示所指结点的数据域，“p-Next”表示所指结点的指针域。,2.3.2 单链表的基本算法描述,算法2-8 往单链表指定位置后插入新元素的算法。 假定单链表Lk的表头指针为Lk_h，插入的数据值为v，要将它插入到由指针ptr指向的结点的后面，如果所给ptr为空，那么插入在表头指针的后面进行。算法名称为Insert_Lk ()，参数为Lk_h、ptr和v。,1往单链表中插入一个新结点,Insert_Lk (Lk_h, ptr, v) qtr = malloc (size); /* 为新结点申请一个存储结点 */ qtr-D
16、ata = v ; /* 将值v赋给新结点的Data域 */ if (ptr = NULL) /*插入发生在表头指针Lk_h的后面 */ qtr-Next = Lk_h; Lk_h = qtr; else qtr-Next = ptr-Next ; ptr-Next = qtr ; ,图2-9 往单链表指定位置插入一个元素的步骤示意,图2-10 插入在表头指针后进行的示意,图2-11 单链表上的另一种插入方法,算法2-9 删除单链表中指定位置处结点的算法。 假定单链表Lk的表头指针为Lk_h，要将指针ptr指向的结点删除。算法名称为Delete_Lk ()，参数为Lk_h、ptr。,2从单链表中
