第3个回答 2009-07-16
数据结构(本)课程辅导与练习-第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
注意:
在顺序表中,每个结点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)表的容量难以扩充.
● 算法分析
① 问题的规模
表的长度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 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) 尾插法建表
算法思路:从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止.
头结点是在链表的开始结点之前附加一个结点.它具有两个优点:
(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个结点.
③具体算法实现
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(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).
链表上实现的插入和删除运算,无须移动结点,仅需修改指针.
五,顺序表和链表的比较
顺序表和链表各有优缺点.在实际应用中究竟选用哪一种存储结构呢 这要根据具体问题的要求和性质来决定.通常有以下几方面的考虑:
顺序表
链表
基
于
空
间
考
虑
分
配
方
式
静态分配.程序执行之前必须明确规定存储规模.若线性表长度n变化较大,则存储规模难于预先确定估计.过大将造成空间浪费,估计太小又将使空间溢出机会增多.
动态分配只要内存空间尚有空闲,就不会产生溢出.因此,当线性表的长度变化较大,难以估计其存储规模时,以采用动态链表作为存储结构为好.
存
储
密
度
为1.当线性表的长度变化不大,
易于事先确定其大小时,为了节约存储空间,宜采用顺序表作为存储结构.
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
B.p->next=q
C.p->next=q->next
D.q->next=NULL
(二)填空题
1.已知L是无表头结点的单链表,且P结点既不是首结点也不是尾结点,试添加合适的语句序列.
(1)在P结点后插入S结点的语句序列是
(2)在P结点前插入S结点的语句序列是
(3)在表首结点之前插入S结点的语句序列是
(4)在表尾结点之前插入S结点的语句序列是
2.在单链表中设置头结点的作用是 .
3.带头结点的单链表L中只有一个元素结点的条件是 .
4.顺序表中,逻辑上相邻的元素物理位置 相邻;单链表中逻辑上相邻的元素物理位置 相邻.
5.带头结点的单链表head为空的判定条件是 .
6.已知p为单链表中的非首尾结点,在p结点后插入s结点的语句为 .
练习题答案
(一)单项选择题
1.D 2.D 3.B 4.B 5.A 6.A 7.C 8.B 9.C 10.C
(二)填空题
1.设pre为P结点的前驱结点.
(1)S->next=P->next;p->next=S;
(2)pre=L;while(pre->next!=P)pre=pre->next;
S->next==pre->next;pre->next=S;
(3)S->next=L;L=S;
(4)P=L;while(P-.next->next!NULL) P=P->next;
S->next==P->next;P->next=S;
2.不管单链表是否为空,头结点的指针均不空,并使得对单链表的操作(如插入和删除)在各种情况下统一.
3.L->next->next==NULL
4.一定 不一定
5.head->next=NULL
6.s->next=p->next;p->next=s;
在王立柱所著《C/C++与数据结构》第8章链表（132页）好像有提到，如需要此资料联系。