数据结构（本）辣程帕导与陈习一第2章 线性表 一、相关术语 线性表、直接前影、直接后维、顺序表、链表、指针、指针变量、结点、数据域， 单向链表，单向循环链表、双向循环挂表、插入，副除 二、哉性表的定攵及特点 裁性表(linear lis以)是属于同一个数据对象的数据元素的有限序列。通常表示为： (,出a, 其中n为线性表的长度，当=0时，表示一个空表。 线性表是一种最常用的数据结构。数据元素之间的关系表现为：除第一个元素无直接前 里，最后一个元素无直接后维外，其余元素均有且仪有一个直接前取和一个直接后锥。线性 表的存储结构有两种实现方法式：顺序存储和链式存储。 三、顺序表 1,顺序表的定义 ()顺序存销方法 即把线性表的结.点按逻辑次序依次存放在一组地址连线的存储单元里的方法。 (2)顺序表(Sequential L域》 用顺序存储方法存储的线性表高称为顺序表(Sequential Lis过)， 2,结点的存储地址 不失一般性，设线性表中所有结点的类型相同，则每个结点所吉用存储空阿大小亦相同。 假设表中每个结点占用©个存储单元，其中第一个单元的存储地址则是该结点的存储地址， 并设表中开始结点山的存储地址（简称为基地址》是LOC(),那么结点的存精地址 OC(a)可通过下式计算： LOC (a)LOC (a)+(i-1)te Isign 注意：
数据结构（本）课程辅导与练习－第 2 章 线性表 一、相关术语 线性表、直接前驱、直接后继、顺序表、链表、指针、指针变量 、结点、数据域、 单向链表、单向循环链表、双向循环链表、插入、删除 二、线性表的定义及特点 线性表（linear_list）是属于同一个数据对象的数据元素的有限序列。通常表示为： (a1, a2 ,a3,…,an) 其中 n 为线性表的长度，当 n＝0 时，表示一个空表。 线性表是一种最常用的数据结构，数据元素之间的关系表现为：除第一个元素无直接前 驱，最后一个元素无直接后继外，其余元素均有且仅有一个直接前驱和一个直接后继。线性 表的存储结构有两种实现方法式：顺序存储和链式存储。 三、顺序表 1．顺序表的定义 (1) 顺序存储方法 即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。 (2) 顺序表（Sequential List） 用顺序存储方法存储的线性表简称为顺序表（Sequential List）。 2．结点 ai 的存储地址 不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。 假设表中每个结点占用 c 个存储单元，其中第一个单元的存储地址则是该结点的存储地址， 并设表中开始结点 a1 的存储地址（简称为基地址）是 LOC（a1），那么结点 ai 的存储地址 LOC（ai）可通过下式计算： LOC（ai）= LOC（a1）+（i-1）*c 1≤i≤n 注意：
在顺序表中，每个结点盖的存储地址是该结点在表中的位置的线性函数。只要知道基 地址和每个结点的大小，统可在相同时间内求出任一结点的存精地址，是一种防机存取结构。 3.顺序表类里定义 typedet'struet y突data[MAXSIZE]:*定文线性表为一推数组/ nt length:作ength为线性表当前的长度/ SeqList: 其中d血是一维数组，MXS1Z正是数组da所能容纳元素的最大值，也称为顺序表 的容量：1eng曲是线性表当前的实际长度，线性表中第1,2，，egh个元素分别存放在 数组第0,1，，egh-l的位置上；datatype是线性表元素的类型，应视具体情况而定， 可以是整形、字符型等，例如线性表是英文字母表。则dye就是字符型。 4,顺序表的特点 顺序表的特点是逻辑上相邻的结点其物理位置也相邻。 5,顺序表上实现的基本运算 (1)插入 线性表的插入运算是指在表的第i(1ss+I)个位置上，插入一个新结点x,使长度为 n的线性表： (:，a:a,a》 成长度为+I的线性表： (,…，a1:x,a:.） 在顺序表中，结点的物理顺序必须和结点的逻婚顺序保持一致，因此必须将表中位置为 n,n1,…,i上的结点。依次后移到位置n+l,n,,+1上，空出第i个位置，然后在 该位置上插入新结点X:仅当插入位置=+川时，才无策移动结点，直接将x插入表的末尾。 具体算法描述教材P9【算法21】 线性表的顺序存储具有三个弱点： (1)在做插入或刷除操作时，需委移动大量元素： (2)由于难以估计，。必類预先分配较大的空间，往往使存储空间不能得到充分的利用：
在顺序表中，每个结点 ai 的存储地址是该结点在表中的位置 i 的线性函数。只要知道基 地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。 3．顺序表类型定义 typedef struct { datatype data[MAXSIZE]；/*定义线性表为一维数组*/ int length；/* length 为线性表当前的长度*/ }SeqList； 其中 data 是一维数组，MAXSIZE 是数组 data 所能容纳元素的最大值，也称为顺序表 的容量；length 是线性表当前的实际长度，线性表中第 1，2,…，length 个元素分别存放在 数组第 0，1，…, length -1 的位置上；datatype 是线性表元素的类型，应视具体情况而定， 可以是整形、字符型等，例如线性表是英文字母表，则 datatype 就是字符型。 4．顺序表的特点 顺序表的特点是逻辑上相邻的结点其物理位置也相邻。 5．顺序表上实现的基本运算 （1) 插入 线性表的插入运算是指在表的第 i（1≤i≤n+1）个位置上，插入一个新结点 x，使长度为 n 的线性表： （a1，…，ai-1，ai，…an） 变成长度为 n+1 的线性表： （a1，…，ai-1，x，ai，…an） 在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为 n ，n-1，…，i 上的结点，依次后移到位置 n+1，n，…，i+1 上，空出第 i 个位置，然后在 该位置上插入新结点 x。仅当插入位置 i=n+1 时，才无须移动结点，直接将 x 插入表的末尾。 具体算法描述教材 P9【算法 2-1】 线性表的顺序存储具有三个弱点： （1）在做插入或删除操作时，需要移动大量元素； （2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分的利用；
(3)表的容量难以扩充： ·算法分析 ①问愿的规模 表的长度>lgh(设值为n)是问题的规模。 ②移动结点的次数由表长口和插入位置i决定 算法的时间主要花费在f循环中的结点后移语句上，该语句的执行次数是-+1， 当+1：移动结点次数为0，即算法在最好时间复杂度是01) 当-：移动结点次数为：即算法在最坏情况下时间复杂度是0叫) (5)州除 线性表的酬除运算是指将表的第1(1s)个结点副去，使长度为n的线性表 (…·4:4+1+-·) 变成长度为】的线性表 (:，a盏-，-·a） 在顺序表上实现刷除运算必颈移动结点，才能反肤出结点间的逻辑关系的变化，若用 则只要简单地剩除终端结点，无须移动结点：若1≤n-1,则领将表中位置i+1,+2, n的结点，依次前移到位置，+1，，1上，以填补别除操作造成的空缺。 具体算法描述参见教材P11【算法22】 ·算法分析 ①结点的移动次数由表长n和位置i决定： 时，结点的移动次数为0，即为0(1) -时，结点的移动次数为l,算法时间复杂度分别是0) ②移动结点的平均次数顺序表上做副除运算，平均要移动表中约一半的结点，平均时 间复杂度也是0(n: 四、链表 1,楚接存储方法
（3）表的容量难以扩充。 ● 算法分析 ① 问题的规模 表的长度 L-＞length（设值为 n）是问题的规模。 ② 移动结点的次数由表长 n 和插入位置 i 决定 算法的时间主要花费在 for 循环中的结点后移语句上。该语句的执行次数是 n-i+1。 当 i=n+1：移动结点次数为 0，即算法在最好时间复杂度是 0(1) 当 i=1：移动结点次数为 n，即算法在最坏情况下时间复杂度是 0(n) （5） 删除 线性表的删除运算是指将表的第 i（1≤i≤n）个结点删去，使长度为 n 的线性表 （a1，…，ai-1，ai，ai+1，…，an） 变成长度为 n-1 的线性表 （a1，…，ai-1，ai+1，…，an） 在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若 i=n， 则只要简单地删除终端结点，无须移动结点；若 1≤i≤n-1，则必须将表中位置 i+1，i+2，…， n 的结点，依次前移到位置 i，i+1，…，n-1 上，以填补删除操作造成的空缺。 具体算法描述参见教材 P11【算法 2-2】 ● 算法分析 ①结点的移动次数由表长 n 和位置 i 决定： i=n 时，结点的移动次数为 0，即为 0(1) i=1 时，结点的移动次数为 n-1，算法时间复杂度分别是 0(n) ②移动结点的平均次数,顺序表上做删除运算，平均要移动表中约一半的结点，平均时 间复杂度也是 0(n)。 四、链表 1．链接存储方法
链接方式存钻的线性表简称为性表(Linked L以)。 徒表的具体存储表示为： ①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可 以是不连线的) ②链表中结点的逐辑次序和物理次序不一定相同。为了能正确表示结点间的逐辑关系 在存储每个结点植的同时，还必须存储指示其后胜结点的地址（成位置）信息（称为指针 (pointer)或醚Iink) 注意： 徒式存储是最常用的存储方式之一，它不仅可用米表示战性表，而且可用来表示各种非 线性的数据结构。 2。能表的结点结构 data next d山血域：存放结点值的数据域 境：存成结点的直接后继的地址（位置）的指针域（结域） 注意： ①情表通过每个结点的链拔将线性表的个结点按其逐辑顺序情接在一起的。 ②每个结点只有一个链城的链表称为单链表(Single Linked L域)。 3.mmoc函数和fret函数 ①生成结点变量的标准函数le p-气ListNode ")malloc(sizeof ListNode小：产函数malloc分配一个类型为ListNode 的结点变量的空间，并将其首地址放入指针变量P中 ②释放结点变量空间的标准函数r© fep:件释放p所指的结点变量空间/ 本、单链表的运算 (1)尾括法建表
链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为： ① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可 以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系， 在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针 （pointer）或链(link)） 注意： 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非 线性的数据结构。 2．链表的结点结构 data next data 域：存放结点值的数据域 next 域：存放结点的直接后继的地址（位置）的指针域（链域） 注意： ①链表通过每个结点的链域将线性表的 n 个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表（Single Linked List）。 3．malloc 函数和 free 函数 ①生成结点变量的标准函数 malloc p=( ListNode *)malloc(sizeof(ListNode))；/*函数 malloc 分配一个类型为 ListNode 的结点变量的空间,并将其首地址放入指针变量 p 中*/ ②释放结点变量空间的标准函数 free( free(p)；/*释放 p 所指的结点变量空间*/ 4、单链表的运算 (1） 尾插法建表
算法思路：从一个空表开始.重复读入数据生成新结点将读入数据存放在新结点的数据 域中然后将新结点插入到当懒链表的表尾上，直到读入结束标志为止， 头结点是在益表的开始结点之前附加一个结点。它具有两个优点 ()由于开始结点的位置敲存放在头结点的指针城中，所以在链表的第一个位置上的操作 就和在表的其它位置上操作一致无须进行特殊处理： (2)无论链表是否为空，其头指针都是指向头结点的半空指针（空表中头结点的指针城 空)，因此空表和半空表的处理也就统一了。 具体算法参见教材P15【算法2-3】。 注意 (1)采用尾插法建表，生成的皓表中结点的次序和输入顺序一致 (2)须增加一个尾指针1，使其始终指向当前链表的尾结点 (2)头插法建表 算法思路：从一个空表开始，重复读入数据，生成新结点将读入数据存放在新结点的数据 域中然后将新结点插入到当前链表的表头上直到读入结束标志为止。 具体算法参见教材P17【算法24】。 注意 该方法生成的链表的结点次序与输入顺序相反。 (3)按序号查找 ①链表不是随机存取结构 在链表中，即使如道被访月结点的序号，也不能像顺序表中郑样直接按序号访问结 点，而只能从链表的头指针出发，顺醚域t逐个结点往下搜素。直至瘦索到第1个结点为 止。因此，链表不是随机存取结构。 ②直找的思塑方法 计数器j置为0后，扫描指针P带针从链表的头结点开始顺着鼓扫描：当P扫指下一个 结点时，计数器j相应地加1。当j门时，指针P所指的结点藏是要找的第1个结点。而当P 指针指为1且封时，则表示找不到第1个结点。 注意：头结点可看做是第0个结点
算法思路：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据 域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。 头结点是在链表的开始结点之前附加一个结点。它具有两个优点: (1)由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作 就和在表的其它位置上操作一致,无须进行特殊处理; (2)无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域 空），因此空表和非空表的处理也就统一了。 具体算法参见教材 P15【算法 2-3】。 注意： （1）采用尾插法建表，生成的链表中结点的次序和输入顺序一致 （2）须增加一个尾指针 r,使其始终指向当前链表的尾结点 （2） 头插法建表 算法思路：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据 域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。 具体算法参见教材 P17【算法 2-4】。 注意： 该方法生成的链表的结点次序与输入顺序相反。 （3）按序号查找 ① 链表不是随机存取结构 在链表中，即使知道被访问结点的序号 i，也不能像顺序表中那样直接按序号 i 访问结 点，而只能从链表的头指针出发，顺链域 next 逐个结点往下搜索，直至搜索到第 i 个结点为 止。因此，链表不是随机存取结构。 ② 查找的思想方法 计数器 j 置为 0 后，扫描指针 p 指针从链表的头结点开始顺着链扫描。当 p 扫描下一个 结点时，计数器 j 相应地加 1。当 j=i 时，指针 p 所指的结点就是要找的第 i 个结点。而当 p 指针指为 null 且 j≠i 时，则表示找不到第 i 个结点。 注意：头结点可看做是第 0 个结点
③具体算法实现 List Node GetNode(LinkList head int i) 在带头结点的单链表bea中查找第i个结点，若找到(0si3), 侧返回谈结点的存储位置，否侧赵网山， ntj方 ListNode *p. p-headj0*从头结点开始扫指/ hp->e&j产顺指针向后扫描，直到p>xt为NULL或可为止/ p-p->next j. 价一) return p,/找到了第i个结点/ else return NULL当i0或p0时，找不到第i个结点/ (4)插入运算 思想方法 插入运算是将植为x的新结点插入到表的第引个结点的位置上，即插入到与 之间 具体步骤： 《1)找到a置P (2)生成一个数据域为X的新结点s (3)令结点p的指针城指向新结点 (4)新结点的指针域番向结点
③具体算法实现 ListNode* GetNode(LinkList head,int i) {/*在带头结点的单链表 head 中查找第 i 个结点，若找到（0≤i≤n）， 则返回该结点的存储位置，否则返回 NULL。*/ int j; ListNode *p; p=head;j=0;/*从头结点开始扫描*/ while(p->next&&jnext 为 NULL 或 i=j 为止*/ p=p->next; j++; } if(i==j) return p;/*找到了第 i 个结点*/ else return NULL;/*当 i0 时，找不到第 i 个结点*/ } （4）插入运算 思想方法 插入运算是将值为 x 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1 与 ai 之间。 具体步骤： （1）找到 ai-1 置 p （2）生成一个数据域为 x 的新结点*s （3）令结点*p 的指针域指向新结点 （4）新结点的指针域指向结点 ai
(2)具体算法实现参见数材P18【算法2-5】 (3)算法分析 算法的时间主要耗费在查找操作上，故时间复杂度亦为O)。 (5)酬降运算 思想方法 到除运算是将表的第í个结点副去。 具体步囊 (1)找到的存储位置p(因为在单链表中结点的存储地址是在其直接前趋结点 A的折针城neu中) (2)令p->ext指向高的直接后莲结点〔即把a从鲢上摘下) (3)释放结点刚的空间，将其自还给“存储泡”。 几体算法实现参见数材P20【算法26】 注意： 设单链表的长度为n,则副去第i个结点仅当1ss时是合法的. 当+1到，虽然被到结点不存在，们其前趋结点却存在，它是终端结点。因此被到结 点的直接前趋p存在并不意味着被剩结点就一定存在，仅当p存在（即p!NU山》且P 不是终瑞结点（即p>et!=NUL)时，才能确定核删结点存在◆ 线性表的债式存储结构一般来说克服了顺序存储结构的三个弱点，首先，插入和到除操 作不需要移动元素，只修改指针：其次，不需要预先分配空间。可根据需要动态申请空间： 其三是表容量贝受可用内存空间的限制： ·算法分断析 算法的时间复桑度也是O(n》。 链表上实现的括入和副除运算，无须移动站点，仅需修改指针， 五、顺序表和链表的比较 顺序表和硫表各有优缺点，在实际应用中究竟选用哪一种存储结构呢？这要根据具体间 恩的要求和性质来决定。通常有以下几方面的考虑：
（2）具体算法实现参见教材 P18【算法 2-5】 （3）算法分析 算法的时间主要耗费在查找操作上，故时间复杂度亦为 O(n)。 （5）删除运算 思想方法 删除运算是将表的第 i 个结点删去。 具体步骤： （1）找到 ai-1 的存储位置 p（因为在单链表中结点 ai 的存储地址是在其直接前趋结点 ai-1 的指针域 next 中） （2）令 p-＞next 指向 ai 的直接后继结点（即把 ai 从链上摘下） （3）释放结点 ai 的空间，将其归还给"存储池"。 具体算法实现参见教材 P20【算法 2-6】 注意： 设单链表的长度为 n，则删去第 i 个结点仅当 1≤i≤n 时是合法的。 当 i=n+1 时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结 点的直接前趋*p 存在并不意味着被删结点就一定存在，仅当*p 存在（即 p！=NULL）且*p 不是终端结点（即 p-＞next！=NULL）时，才能确定被删结点存在。 线性表的链式存储结构一般来说克服了顺序存储结构的三个弱点，首先，插入和删除操 作不需要移动元素，只修改指针；其次，不需要预先分配空间，可根据需要动态申请空间； 其三是表容量只受可用内存空间的限制。 ● 算法分析 算法的时间复杂度也是 O（n）。 链表上实现的插入和删除运算，无须移动结点，仅需修改指针。 五、顺序表和链表的比较 顺序表和链表各有优缺点。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问 题的要求和性质来决定。通常有以下几方面的考虑：
顺序表 链表 分 基 静态分配。程序执行之前必须明确规定存 配 储规模。若线性表长度变化较大，则存储规 动态分配具要内存空间尚有空闲，就不会产生溢 于 方 核难于预先确定估计，过大将造成空间浪费。 出。因此。当线性表的长度变化较大，难以估计其存 估计太小又将使空间溢出机会增多。 储规模时，以采用动态鼓表作为存储结构为好。 空 式 间 存 储 为1，当线性表的长度变化不大， 考 密 易于事先确定其大小时，为了节约存储空 <1 间。宜采用顺序表作为存储结构。 度 格 随机存取结构，对表中任一结点都可在0 取 (1)时间内直接取得 顺序存取结构，链表中的结点，需从头指针起顺 暴 方 线性表的提作主要是进行查找，额少做插 着链扫描才修取得。 入和酬除操作时，采用顺序表做存储结构为宜。 法 时 插 间 入 酬 在顺序表中进行插入和刚除，平均要移动 在链表中的任何位置上进行插入和刷除，都只需 要修政指针。对于领繁进行插入和制除的战性表，宜 表中近一半的结点，尤其是当每个结点的信息 除 采用桂表做存储结构。若表的插入和剧障主要发生在 量较大时，移动结点的时间开销就相当可观。 表的首尾两璃，则采用尾粉针表示的单循环链表为宜 操 作 六，练习题 (一)单项选择题 1线性表在链式存储中各结点之间的陆址《)。 A.必须连线 B。部分地址必须连线
顺序表 链表 基 于 空 间 考 虑 分 配 方 式 静态分配。程序执行之前必须明确规定存 储规模。若线性表长度 n 变化较大，则存储规 模难于预先确定估计。过大将造成空间浪费， 估计太小又将使空间溢出机会增多。 动态分配只要内存空间尚有空闲，就不会产生溢 出。因此，当线性表的长度变化较大，难以估计其存 储规模时，以采用动态链表作为存储结构为好。 存 储 密 度 为 1。当线性表的长度变化不大， 易于事先确定其大小时，为了节约存储空 间，宜采用顺序表作为存储结构。 <1 基 于 时 间 考 虑 存 取 方 法 随机存取结构，对表中任一结点都可在 O （1）时间内直接取得 线性表的操作主要是进行查找，很少做插 入和删除操作时，采用顺序表做存储结构为宜。 顺序存取结构，链表中的结点，需从头指针起顺 着链扫描才能取得。 插 入 删 除 操 作 在顺序表中进行插入和删除，平均要移动 表中近一半的结点，尤其是当每个结点的信息 量较大时，移动结点的时间开销就相当可观。 在链表中的任何位置上进行插入和删除，都只需 要修改指针。对于频繁进行插入和删除的线性表，宜 采用链表做存储结构。若表的插入和删除主要发生在 表的首尾两端，则采用尾指针表示的单循环链表为宜 六、练习题 （一）单项选择题 1.线性表在链式存储中各结点之间的地址（ ）。 A．必须连续 B．部分地址必须连续
C.不能违续 D.连续与否无所谓 2.有关线性表的正确说法是()。 A。每个元素都有一个直接前图和一个直接后继 B.线性表至少要求一个元素 C,表中的元素必领按由小到大或由大到下排序 D,除了一个和最后一个元素外，其余元素军有一个且仅有一个直接前距和一个直 接后继 3.一个战性表第一个元煮的存储地址是100，每个元煮的长度为4，则第5个元者的地 址是《) A.110 B.116 C.100 D.120 4在一个长度为n的顺序存销线性表中，向第1个元素(1E)之前插入一个新元素 时，香要依次后移《)个元素。 A.ni B.n-i+l C.n-i-1 D.i 5.在一个长度为n的顺序存储线性表中，酬除第i个元素(1E正)，需要前移() 个元素， A.ni B.n-i+l C.n-i-l
C．不能连续 D．连续与否无所谓 2．有关线性表的正确说法是（ ）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表至少要求一个元素 C．表中的元素必须按由小到大或由大到下排序 D．除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直 接后继 3．一个线性表第一个元素的存储地址是 100，每个元素的长度为 4，则第 5 个元素的地 址是（ ）。 A．110 B．116 C．100 D．120 4.在一个长度为 n 的顺序存储线性表中，向第 i 个元素（1£ i£n）之前插入一个新元素 时，需要依次后移（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 5. 在一个长度为 n 的顺序存储线性表中，删除第 i 个元素（1£ i£n），需要前移（ ） 个元素。 A．n-i B．n-i+1 C．n-i-1
D.i 6.做表不具有的特点是()。 A。可随机访问任一元素 B。插入别除不雷要移动元素 C,不必要事先估计存精空间 D。所需空间与线性表长度成正比 7,用链表表示线性表的优点是()。 A。便于随机存取 B,花费的存铺空间较顺序存储少 C,便于括入和酬除 D。数据元素的物理顺序和逻辑顺序相同 8,带头结点的链表为空的判断条作是()（设头指针为d), A.head--NULL B.head->next==NULL C.head->next=mhead D.headl-NULL 9.非空的单向循环链表的尾结点满足(）（设头指针为ed,指针p指向尾结点）。 A.p->next==NULL B.p--NULL C.p->next=head D.p=head I0.在一个单链表中，P、q分别指白表中两个相g的结点，且q所指结点是P所指结 点的直接后谁，现要制除q所指结点，可用语句() A.pq->next
D．i 6．链表不具有的特点是（ ）。 A．可随机访问任一元素 B．插入删除不需要移动元素 C．不必要事先估计存储空间 D．所需空间与线性表长度成正比 7．用链表表示线性表的优点是（ ）。 A．便于随机存取 B．花费的存储空间较顺序存储少 C．便于插入和删除 D．数据元素的物理顺序和逻辑顺序相同 8．带头结点的链表为空的判断条件是（ ）（设头指针为 head）。 A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL 9．非空的单向循环链表的尾结点满足（ ）（设头指针为 head，指针 p 指向尾结点）。 A．p->next==NULL B．p==NULL C．p->next==head D．p==head 10．在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结 点的直接后继，现要删除 q 所指结点，可用语句（ ）。 A．p=q->next