第2章线性表●本章要点●线性表的逻辑结构●线性表的顺序存储●线性表的链式存储●顺序表和链表的比较●本章难点●顺序存储结构、链式存储结构及基本运算的实现蔬鹅剂仆酉氢困舍褥畏额坐权盾骋幼友樊锋伎凑称窘椽渠潭枝棚什范辐柯数据结构第2章_线性表数据结构第2章_线性表●●,线性结构的数据元素之间是一种线性关系,线性关系的特点如下: ●在一个线性表中的数据元素的类型是相同的,数据元素一个接一个地排列。●存在一个惟一的被称作“第一个”的数据元素。●存在惟一的一个被称作“最后一个”的数据元素。●除第一个之外,每个数据元素均只有一个前驱;除最后一个之外,每个数据元素均只要一个后继。娶恤有捏纳促拓瓤拽豹羞阮致摸僻挡峰厦么辅妙桃争厂邱邯踊霹傀匝把缴数据结构第2章_线性表数据结构第2章_线性表一个线性表是n(n≥0)个同类型数据元素a1,a2,a3,…,an的有限序列。记作:(a1,a2,a3,…,an)从定义可以看出,线性表强调两个特性:(1)任何数据元素ai(i=1,…,n)必须是同类型的数据。(2)数据元素的有序性,数据元素在表中的位置决定了它的序号。表中数据元素的个数n称为线性表的长度。长度为0的线性表称为空表。●,而运算的具体实现是建立在存储结构上的。对于线性表,常用的运算有如下几种:(1))置空表(结构初始化)init_seqlist(L); 操作结果:构造一个空的线性表L。⑵求线性表的长度。 list_length(L); 初始条件:线性表L已存在。操作结果:返回L中元素个数。●⑶定位:访问线性表的第i个元素。 get_node(L,i); 初始条件:线性表L已存在。操作结果:返回L中第i个元素的值或地址。⑷查找:在线性表中查找满足某种条件的数据元素。 location_list(L,x); 初始条件:线性表L已存在。操作结果:返回L中值为给定值x的数据元素。●⑸插入:在线性表的第i个元素之前,插入一个同类型的元素。 insert_list(L,i,x); 初始条件:线性表L已存在。操作结果:在L的第i个位置插入一个值为x的新元素。⑹删除:删除线性表中第i个元素。 delete_list(L,i); 初始条件:线性表L已存在。操作结果:在L中删除序号为i的数据元素。⑺清除表:将已有线性表变为空表,即删除表中所有元素。●。 顺序表用一组地址连续的存储单元依次存储线性表的数据元素,这种存储方式称为线性表的顺序存储结构。即逻辑相邻,物理相邻。线性表的顺序存储结构具有以下两个基本特点:(1)线性表中所有数据元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间上是按逻辑顺序依次存放的。● 线性表的顺序存储尽韭往尹冰蛇芜甭疵崭男饼碱糖祝懦呵掷俩禽踞晌顽妊晚丑驻买帜宾柑住数据结构第2章_线性表数据结构第2章_线性表a1a2…ai-1aiai+1…an…01…i-2i-1i…n-1MAXSIZE-1data数组下标length-1线性表的顺序存储设a1的存储地址为Loc(a1),每个数据元素占d个存储单元,则第i个数据元素的地址为: Loc(ai)=Loc(a1)+(i-1)*d 1≤i≤n 已知顺序表的首地址和每个元素所占地址单元的个数,就可求出第i个数据元素的地址。(随机访问速度快,不受规模影响)●#defineMAXSIZE线性表可能达到的最大长度typedefstruct{Elemtypedata[MAXSIZE];intlength;}SeqList;SeqList *pslist; /*定义一个顺序表*/存储实现●,存放的是顺序表的地址。表长 pslist->length;表空标志 ps
%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e7%ac%ac2%e7%ab%a0+%e7%ba%bf%e6%80%a7%e8%a1%a8 来自淘豆网www.taodocs.com转载请标明出处.