第二章 线性表.ppt

1、第2章线性表1线性表的ADT定义2线性表的顺序表示3线性表的连锁存储和运算实现4顺序表与连锁表的比较，1线性表的ADT定义1、线性表的基本概念1、线性表的逻辑定义线性表(Linear List )是n(n0)个数据要素(节点)的数据要素的个数n被定义为表的长度对于非空线性表(n0)，(a1，a2，an )数据元素ai(1in )是抽象的符号，其具体含义根据情况而不同。 【例1】英文字母(a，b，z )为线性表，表中的各字符为一个数据要素(节点) 【例2】有作为一个扑克的点数(2，3，10，j，q，k，)的终端节点an，只有一个，没有直接后继，只有一个直接前进an 二、线性表的ADT定义ADT

2、List数据对象： D=ai|aiElemSet，I=1，2，n，n=0数据关系： R=|ai-1，aiD， maxlen:线性表的最大长度。 是常数。 四、顺序线性表的实现1、顺序网站数据库结构#define LIST_INIT_SIZE 100 /表存储空间的初始分配量#define LISTINCREMENT 10 /表存储空间的分配增量用c类描述/类/当前长度int listsize； /当前分配的存储容量(sizeof(ElemType )单位Sqlist 2、顺序表的初始化操作、Status Initlist_sq(Sqlist )， 4、在第I个元素之前插入元素(a1)，在插入2

3、41720253540134679|8n 2172025354013679|之后插入n、status ListInsert_sq(Sqlist， 5、假定在顺序线性表的删除操作、241720253540135679| 17n 2420253540135789|删除17之后在nstaal表的任意位置(1jn )插入元素的概率是1/n，则移动元素的期望值是、6、插入删除数据元素假定将元素插入线性表的第一位置的概率是Pj、线性表的长度、1n，分别假定在表中的任意位置(1jn )删除元素的概率是1/n，则移动元素的期待值是： (2)假定在线性表的第一位置删除元素的概率，n是线性表的长度、1n， 7 .

4、顺序存储器结构的评价(1)优点a )网站数据库结构简单，网站数据库任意要素的时间一定，不使用存取速度快的b )指针，存储器密度大。 (2)缺点a ) b )需要连续的存储器摇滾乐的分配；(c )插入可能向上溢出；(c )为了防止向上溢出，需要留下大的连续存储器摇滾乐，浪费；(d )插入和删除大量移动的数据元素； 2.3线性表的连锁存储和运算实现顺序表的存储特征通过实现物理邻接的逻辑性邻接，需要用连续的存储手段依次存储线性表的各要素，因此顺序表的插入删除需要通过移动数据要素来实现，影响执行效率。在本节中，与逻辑性相邻的两个数据元素不需要在物理上相邻，通过“链”来建立数据元素之间的逻辑性关系，因此

5、不需要将数据元素移动到线性表的插入、删除，从而不需要在地址连续的存储单元中实现线性表链2.3.1单网络链接表网络链接表将线性表中的数据要素用任意的存储器单元的定径套来存储，为了构筑如何表现数据要素间的线性关系、数据要素间的线性关系，对于各数据要素ai，除了数据要素自身的信息ai以外， 必须存储后续ai 1与ai一起所在的存储器单元的地址，这两条信息构成一个“节点”，节点的结构如图2.6所示，每个元素都是这样。 存储数据元素信息的称为数据结构域，随后存储地址的称为指针结构域。 因此，通过n个要素的线性表，各节点的指针字段成为“链”，称为链表。 每个节点只有一个后续指针，因此称为单网络链接表。图2

6、.6单网络链接表节点结构、网络链接表由一个节点构成，节点定义如下： typedef struct node datatype data； 结构节点*下一个； LNode、*链接列表； 通常用“标头指针”来识别单网络链接表。 例如，单网络链接表l、单网络链接表h等表示一个网络链接表的第一个节点的地址位于指针变量l，h上，标头指针为空的表。 头指针变量包括链路列表h； 图2.7是与线性表(a1、a2、a3、a4、a5、a6、a7、a8)对应的链存储器结构的示意图。 当然，第一个节点的地址160必须位于如h的指针变量中。 最后一个节点不后续。 那个指针字段必须为空。 这张表到此为止。 现在，可以从第

7、一个节点的地址开始“顺藤触瓜”，找到各个节点。 普通的单网络链接表以图2.8的形式表示，而不是图2.7的形式表示，因为线性表的存储结构之一是在各节点间的逻辑结构上感兴趣，并且不关心每一个节点的实际地址。 的双曲馀弦值。 上面定义的LNode是节点的类型，LinkList是指向LNode类型节点的指针类型。 为了提高计程仪列的易读性，用于标识网络链接表的标头指针通常被描述为LinkList类型的变量(如LinkList L )。 如果定义了l，则值为NULL时表示空表的第一个节点的地址，即网络链接表的标头指针。LNode *类型(LNode *p； 中文： p=malloc(sizeof(LNo

8、de ) )； 申请块Lnode型存储单元的操作完成，其地址被分配给变量p。 如图2.9所示。 p所指的结点是*p，*p的类型是LNode型，该结点的数量是结构域(*p).data或p-data，指针结构域是(*p).next或p-next。 free(p )表示释放p指向的节点.2.3.2实现单网络链接表上的基本运算，1 .创建单网络链接表(1)在网络链接表的开头插入节点来创建单网络链接表，这一点与顺序表不同，是动态管理的存储结构因为插入在网络链接表的开头，所以数据的读入顺序和网络链接表中的逻辑顺序相反。 其算法为：链接列表创建_链接列表1 ()链接列表l=空。 /*空表*/Lnode *s

9、； int x； /*数据元素的类型为int*/scanf(%d，算法2.8，(2)在单网络链接表的末尾插入节点并插入单网络链接表头来创建单网络链接表很简单，但读取的数据元素的顺序与生成的网络链接表中元素的顺序相反因为每次都在网络链接表的末尾插入新节点，所以总是添加指向网络链接表的末尾节点的指针r，如图2.11所示，在网络链接表的末尾插入节点来创建网络链接表的步骤。 算法构想：初期状态：头部指针H=NULL，尾部指针r=NULL； 按照线性表中的元素顺序读取数据元素，如果不是结束标志，则申请节点，将新节点插入到r所指的节点之后，且r指向新节点(其中，与最初节点不同，读者留心到下一算法的相关部分

10、中)。 修正方法如下：链接列表创建链接列表2 ()链接列表l=空。 Lnode *s、* r=空值； int x； /*假设资料元素的类型为int*/scanf(%d )，则上面的算法对第一个节点的处理与其他节点不同。 因为添加第一个节点时网络链接表为空，没有直接前面的节点，所以该地址是整个网络链接表的指针，必须包含在网络链接表的头变量中的其他节点有直接前面的节点，该地址直接前面的节点的指针结构域中。 “第一节点”的问题是，由于在网络链接表中插入节点、在第一位置和其他位置插入节点、从网络链接表中删除节点、删除第一节点和其他节点的处理也不同等、在许多操作中发生的报头节点的追加，而导致“第一节点”

11、的问题报头节点的参与者是为了完全为了运算的方便，而未定义其数据字段，并且指针字段存储第一个数据节点的地址，而在空表的情况下为空。 图2.12(a )、(b )分别是开头节点的单网络链接表空表和非空表的示意图。 2 .求出表长算法的思维方法：设置移动指针和计数器，初始化后，如果指定的节点后面有节点，则向后移动，在计数器上加1。 (1)将l作为开头节点的单一网络链接表(线性表的长度不包含开头节点)。 修正方法如下：链接列表1 (链接列表l )链接节点* p=l。 /* p是指头节点*/、int j=0。 威尔(下一个) p=下一个。 j /* p是指第j个节点*/return j。 (2)将l作为

12、不开头的节点的单网络链接表。 修正方法如下：链接列表2链接节点* p=l。 英特尔； if (p=空)返回0。 /*空表时*/、j=1； /*对于非空表，p是第一个节点*/； 威尔(下一个) p=下一个。 回复j； 在不具有开头节点的单网络链接表空表的情况下，根据算法2.10(b )上的2个算法分别进行处理，在具有开头节点之后不需要。 如果不在以后的算法中添加说明，则认为单网络链接表是开头节点。 校正算法2.10(a )、(b )的时间复杂度都是O(n )。 3 .思维方法搜索操作(Get_Linklist(L，I ) )算法：从网络链接表中的第一个元素节点开始，确定当前节点是否是第I个，如果

13、不是，返回该节点的指针，否则继续进行到下一个，直到表结束。 如果没有第一个节点，则返回null。 修正算法为Lnode * Get_LinkList(LinkList L，Int i )； /*在单网络链接表l中查找第I个元素节点并返回该指针。 否则，返回空*/Lnode * p=L。 int j=0； p -下一个！=空值j； 返回点(j=I )； 激活返回空值； (12)locate_linklist(l，x )算法的思维方法：从网络链接表的第一个元素节点开始，判断当前节点的值是否等于x，否则返回该节点的指针，否则继续进行直到表结束。 如果找不到，则返回空白。 算法在lnode * loc

14、ate _ link list (link list l，datatype x) /*单网络链接表l中找到值为x的节点，如果找到该节点，则返回该指针，否则返回空*/* lnode *的while (p！=空算法2.11(a )、(b )的时间复杂度都是O(n )。 4 .插入(1)后插节点： p指定单个网络链接表中的某个节点，s指定要插入的值为x的新节点，*s插入到*p后面，并且在图2.13中插入示意图。其操作如下： s-next=p-next； 下一个=s； 注意：两个指针的操作顺序不能互换。 (2)前插节点：指向网络链接表中的某个节点，并将应插入值设为x的新节点，将*s插入到*p前面，将图像图插入到图2.14中，但与后插不同的是，先找到*p的前驱*q，然后在*q后面完成插入，这是单个q -下一个！ (p ) q=q -下一个； 寻找/*p的直接前驱物*/s-next=q-next。 下一个=s； 在*p之后插入*s并交换-data和s-data即可，因为后向插入操作的时间复杂度是O(1)，并且由于要查找*p的前驱物，实际上时间性能是O(n )，因此对于数据元素之间的逻辑关系感兴趣。 这满足了逻辑关系，并且可以使时间的复杂性为O(1)。 (3)插入运算Insert_LinkList(L，I，x )关算法构想