数据结构 第2章 线性表

1、第二章线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构2.4复杂性分析2.5线性表的定义和基本操作1 .线性表的定义例1英文字母(a，b，c，z )整数系列() 学号姓名性别年龄健康状况01张军男18一般02陈红女17良好03陈军男表中的每个数据元素由哪个域组成？ 定义线性表：一个线性表是具有相同类型节点的零个或多个有序集合。 通常，(a0，a1，an1 )表示线性表示，n 0(正整数)，ak表示节点，并且0 k n1； n0时，线性表中没有节点，称为空表的n1时，a0为线性表的开头结点(简称表标题)，an1为线性表的尾结点(简称表标题)，ai

2、为ai 1的前驱结点，ai 1为ai的后继结点，其中的0 i n1； 在n 1的情况下，线性表中只有1个节点a0、a0，是标头和脚注两者。 线性表的逻辑结构：线性结构，3，线性表的基本操作(1)创建线性表(2)确定线性表的长度(3)确定线性表是否为空(4)访问线性表的第k个节点的字段值(5)查找指定字段值在表中的位置、第二章线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链路存储结构2.4复杂性分析2.5堆栈2.6队列、2.2线性表的顺序存储结构顺序存储：按逻辑顺序将线性表的节点顺序存储在一系列地址连续字节中。 顺序存储的线性表也称为顺序表。 序表的特点：

3、逻辑顺序与物理顺序相同。 另外，包括四个节点的线性表a-4显示在存储器中，其中每个节点占据两个连续字节，第一个节点a-0的开头地址是302，实现顺序存储器的最有效方式是使用一维阵列。 例如，可以使用数组an存储线性表(a0，a1，an-1 )。 Loc(ak)=Loc (a0) k*c，程序表的类声明templateclasslinearlistprivate : int maxsize。 /顺控表的最大长度int length； /顺序表的实际长度T *element； /存储顺序表的数组public : linear list (intmax list size=10 )； /构造函数。

4、默认最大长度为10线性列表() delete element； /析构函数bool isempty () constreturnlength=0； /判定表是否为空bool is full () constreturnlength=maxsize； /判定表是否为全int Length () const return length。 返回/表的长度，当bool Find (int k，t，按顺序存储的线性表的基本运算1，插入示例位于顺序表(12、13、21、24、28、30、42、77 )中时，线性表的逻辑结构如何变化？ 使用位置关系变化的长度为1，/adl算法来描述语言描述算法Insert(

5、A，k，item) /*，并且在下标为k的节点之后插入值为item的节点。*/I1.插入方法？ if (k0or klength-1 or length=maxsize ) then (打印“插入错误”. return ).I2. for ilength-1 to k1step插入n 1种(可插入n 1个位置)插入成功，在各位置插入的概率中的组合图层性质变更选项。 此时，线性表的逻辑结构如何变化？ 将位置关系变化的长度减1，算法Delete(A，k) /*删除顺序表a中下标为k的节点*/D1.k是否合法？ 将if (k0or klength-1 or length0) then (打印“删除不

6、正确”. return ).d2. fori k1to length-1 doai-1 ai .删除n种(n个位置可删除)删除成功，各位置被删除的概率相等：假设缺点：要插入和删除节点，必须调整一组节点的地址。 问题：由于可以更改线性表中元素的数量，因此在定义数组时应该如何考虑？定义大小适当的数组。第二章线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链路存储结构2.4复杂性分析2.5堆栈2.6队列、链路存储：在任何一组存储单元中存储线性表，其中一个存储单元包括节点数据(或信息)字段的值， 根据还必须记住其逻辑邻接节点的节点指针域，链表主要有单链表、循环链表

7、和双向链表三种实现方法。21、2.3.1将线性表的链接存储结构单链表1、单链表的定义2、单链表的特征3、单链表的实现、示例线性表(a3、a4、a5)以链表的形式存储在存储器中。002、500、单链接表的节点结构：单链接表的定义：每个节点只包含一个链接域的链接表称为单链接表。 链路表的第一个节点称为报头节点(也称为报头)，指向报头节点的指针称为报头指针(head )，链路表的最后一个节点也称为尾指针(也称为尾)2.3.1线性列表单链表的定义2、单链表的特征3、单链表的实现、单链表的存储图像、特征：逻辑顺序可以与物理顺序相同，也可以不同。27、在链表中，只插入或删除一个节点，更改一个或两个相关节点

8、的指针，不影响其他节点。 只需在插入：next(s) next(p) next(p) s，删除：链接表中插入或删除一个节点，并更改一个或两个相关节点的指针，就不会影响其他节点。 q next (p). next (p) next (q) . AVAIL q .单链接表的特性：利用链接域实现线性表元素的逻辑关系.单链接表有头节点、尾节点、头指针。 30、单链表的优点：插入、删除方便，共享空间好：节点可以不连续保存，容易扩展。2.3.1线性列表的链路存储结构单链表1、单链表的定义2、单链表的特征3、单链表的实现、1、单链表节点结构sl node (单链列表/指针域sl node (sl node *下一节点=空) next=下一节点。 /构造函数SLNode (const T，2，单链接表类sl list (单链接列表)的类定义templateclassllistprivate : sl node * head/标头点构造函数/构造函数bool isempty (void ) constreturnheadnext=null，构造函数/构造函数仅构建一个空表(void )节点。 /判断链表是否为空的int length