数据结构02 [复制链接]

第二章线性表

了解线性结构的特点

掌握顺序表的定义、查找、插入和删除

掌握链表的定义、查找、插入和删除

能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合

2.1线性表的定义和特点

线性结构的定义：若结构是非空有限集，且有且仅由一个开始结点和一个终端节点，并且所有结点都最多只有一个直接前趋和直接后继。

线性结构可表示为：

线性结构反映结点间的逻辑关系是1:1

线性结构包括：线性表、栈、队列、字符串和数组

线性结构的特点：

在数据元素的非空有限集中

存在唯一的一个被称作为“第一个”的数据元素

存在唯一的一个被称作“最后一个”的数据元素

除第一个外，集合中的每个数据元素均只有一个直接前驱

除最后一个之外，集合中每个数据元素均只有一个直接后继

线性表：n个具有相同特性的数据元素的有限序列

同一线性表中的元素必定具有相同特性

2.2案例引入

2.3线性表的类型定义

线性表的操作主要包括

计算表的长度n

访问第i个元素，1=i=n

将新值赋予第i个元素,1=i=n

将新元素插入第i个位置,1=i=n+1，使原来的第i，i+1，...，n个元素变为第i+1，...，n-1个元素

遍历表的元素

线性表的类型定义

ADTList{数据对象={ai

ai∈ElemSet,i=1,2,...,n,n≥0}数据关系:R={ai-1,ai

ai-1,ai∈D,i=2,...,n}基本操作：InitList(L)操作结果：构造一个空的线性表L。DestroyList(L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回T,否则返回F。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i,e)初始条件：线性表L已存在，1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,
　　
　　　returnOK;}2.销毁单链表LStatusDestroyList_L(LinkListL){LinkListp;while(L){p=L;L=L-next;deletep;}returnOK;}3.清空单链表LStatusClearList(LinkListL){//将L重置为空表LinkListp,q;p=L-next;//p指向第一个结点while(p)//没到表尾{q=p-next;deletep;p=q;}L-next=NULL;//头结点指针域为空returnOK;}4.求单链表L的长度intListLength_L(LinkListL){//返回L中数据元素个数LinkListp;p=L-next;//p指向第一个结点count=0;while(p){//遍历单链表,统计结点数++count;p=p-next;}returncount;}5.判断单链表L是否为空boolListEmpty(LinkListL){//若L为空表，则返回1，否则返回0if(L-next)//非空returntrue;elsereturnfalse;}6.获取单链表L中的某个数据元素内容算法思想：从第1个结点（L-next）顺链扫描，用指针p指向当前扫描到的结点，初始化p=L-next。用j做计数器，累计当前扫描过的结点数，j初值为1。当p指向扫描到的下一结点时，计数器j加1。当j=i时，p所指的结点就是要找的第i个结点。StatusGetElem_L(LinkListL,inti,ElemTypee){//当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORp=L-next;j=1;//初始化while(pji){//向后扫描，直到p指向第i个元素或p为空p=p-next;++j;}if(!p

ji)returnERROR;//第i个元素不存在e=p-data;//取第i个元素returnOK;}7.检索值为e的数据元素LNode*LocateElem_L(LinkListL，Elemtypee){p=L-next;while(pp-data!=e)p=p-next;returnp;//返回L中值为e的数据元素的位置，查找失败返回NULL}8.在单链表L中插入一个数据元素将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间算法思想找到ai-1存储位置p生成一个新结点*s将新结点*s的数据域置为x新结点*s的指针域指向结点ai令结点*p的指针域指向新结点*sStatusListInsert_L(LinkListL,inti,ElemTypee){p=L;j=0;while(pji?1){p=p-next;++j;}//寻找第i?1个结点if(!p

ji?1)returnERROR;//i大于表长+1或者小于1s=newLNode;//生成新结点*ss-data=e;//将结点*s的数据域置为es-next=p-next;//将结点*s插入L中p-next=s;returnOK;}9.删除单链表L中第i个数据目标：将表的第i个结点删去，结果放在e中算法步骤找到ai-1存储位置p临时保存结点ai的地址在r中，以备释放令p-＞next指向ai的直接后继结点将ai的值保留在e中，释放结点ai的空间StatusListDelete_L(LinkListL,inti,ElemTypee){p=L;j=0;while(p-nextji-1){//寻找第i个结点，并令p指向其前驱p=p-next;++j;}if(!(p-next)

ji-1)returnERROR;//删除位置不合理r=p-next;//临时保存被删结点的地址以备释放p-next=r-next;//改变删除结点前驱结点的指针域e=r-data;deleter;//释放结点returnOK;}

初始化单链表：

在单链表L中插入一个数据元素

不能

删除单链表L中第i个数据

单链表的建立

前插法

从一个空表开始，重复读入数据

生成新结点

将读入数据存放到新结点的数据域中，将该结点插入到链表的头部（头结点之后）

voidCreateList_H(LinkListL,intn){L=newLNode;L-next=NULL;//先建立一个带头结点的单链表for(i=n;i0;--i){p=newLNode;//生成新结点cinp-data;p-next=L-next;L-next=p;//插入到表头}}

后插法

从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。

初始时，r通L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点之后，r指向新结点

voidCreateList_R(LinkListL,intn){//正位序输入n个元素的值，建立带表头结点的单链表LL=newLNode;L-next=NULL;r=L;//尾指针r指向头结点for(i=0;in;++i){p=newLNode;//生成新结点　cinp-data;p-next=NULL;r-next=p;//插入到表尾r=p;//r指向新的尾结点}}

链表的运算时间效率分析

查找

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)

插入和删除

因线性链表不需要移动元素，只需要修改指针，一般情况下时间复杂度为O(1)

但是对于指定位置的插入和删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)

链表的优缺点

优点

数据元素的个数可以自由扩充

插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

缺点

存储密度小

存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

循环链表：

将单链表中最后一个结点的指针域指向头结点，整个链表形成一个环。

（a）非空单循环链表

（b）空表

特点：从表中任一结点出发均可找到表中的其他结点。

与单链表的区别：查找结束条件

单链表p-next==NULL

循环链表p-next==head

设立尾指针可以使链表合并简化

开始结点：rear-next-next

终端节点：rear

循环链表的合并

双向链表

typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList

(a)空双向循环链表

(b)双向循环链表

双向链表的插入

s-prior=p-prior

p-prior-next=s

s-next=p

p-prior=s

StatusListInsert_DuL(DuLinkListL,inti,ElemTypee){//在带头结点的双向循环链表L中第i个位置之前插入元素e.p=L-next;j=1;while(p!=Lji){p=p-next;j++;}//在L中确定第i个元素的位置指针pif(p==L

ji)returnERROR;s=newDuLNode;s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;returnOK;}

双向链表的删除

p-prior-next=p-next

p-next-prior=p-next

ListDelete_DuL(DuLinkListL,inti,ElemTypee){//删除带头结点的双向循环链表L的第i个元素。p=L-next;j=1;while(p!=Lji){p=p-next;j++;}if(p==L

ji)returnERROR；e=p-data;p-prior-next=p-next;p-next-prior=p-prior;deletep;returnOK;}

2.6顺序表和链表的比较

存储结构

比较项目

顺序表

链表

空间

存储空间

预先分配，会导致空间闲置或溢出现象

动态分配，不会出现存储空间闲置或溢出现象

存储密度

不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1

需要借助指针来体现元素间的逻辑关系，存储密度小于1

时间

存取元素

随机存取，按位置访问元素的时间复杂度为O(1)

顺序存取，按位置访问元素时间复杂度为O(n)

插入、删除

平均移动约表中一半元素，时间复杂度为O(n)

不需移动元素，确定插入、删除位置后，时间复杂度为O(1)

适用情况

①表长变化不大，且能事先确定变化的范围

②很少进行插入或删除操作，经常按元素位置序号访问数据元素

①长度变化较大

②频繁进行插入或删除操作

2.7线性表的应用

线性表的合并

假设有两个集合A和B分别用两个线性表LA和LB表示，即线性表中的数据元素即为集合中的成员，先要求一个新的集合

需对线性表作如下操作：

扩大线性表LA，将存在于线性表LB而不存在于线性表LA中的数据元素插入到线性表LA中去

具体操作步骤为：

从线性表LB中取出一个数据元素

依值在线性表LA中进行查询

若不存在，则将它插入到LA中

重复上述三步直到LB为空表为止

容易看出，上述的每一步恰好对应线性表的一个基本操作GetElem(L,i,e);LocateElem(LA,e);ListInsert(LA,n+1,e)　voidunion(ListLa,ListLb){La_len=ListLength(La);//求线性表La的长度Lb_len=ListLength(Lb);//求线性表Lb的长度for(i=1;i=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之}}

有序表的合并

已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列

?具体操作步骤为：

?1.从线性表LA中取出第一个数据元素；

?2.从线性表LB中取出第一个数据元素；

?3.将两个元素进行比较

?4.将较小的元素插入到LC中；

?5.小元素所在线性表指针下移，再取出一个元素，和刚才较大的比较。

?重复第4-5步直至LA和LB的指针均指向最尾端止。
　　

算法要求：已知：线性表A、B，分别由单链表LA,LB存储，其中数据元素按值非递减有序排列，要求：将A，B归并为一个新的线性表C,C的数据元素仍按值非递减排列。设线性表C由单链表LC存储。假设：A=（3，5，8，11），B=（2，6，8，9，11）预测：合并后C=（2,3,5,6,8,8,9,11，11）算法主要包括：搜索、比较、插入三个操作：搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。链式有序表的合并voidMergeList_L(LinkListLa,LinkListLb,LinkListLc){//按值排序的单链表LA,LB，归并为LC后也按值排序pa=La-next;pb=Lb-next;Lc=pc=La；//初始化while(papb)//将pa、pb结点按大小依次插入C中{if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}//whilepc-next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb的头结点}顺序有序表的合并voidMergeList(ListLa,ListLb,ListLc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)(j=Lb_len){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}//if}//whilewhile(i=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}//whilewhile(j=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}//while}//MergeList

2.8案例分析与实现

小结线性表：

一个线性表是n≥0个数据元素a1,a2,…,an的有限序列。

线性表的顺序存储结构

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，乘坐线性表的顺序存储结构

线性表的链式存储结构

线性表的链式存储结构就是用一组任意的存储单元存储线性表的数据元素

表中的每一个数据元素都由数据域和指针域组成

单链表：

指链表中的每一个结点中只包含一个指针域指向直接后继

循环链表：

将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中的其他结点。

双向链表：

每一个结点除了数据域外，还包含两个指针域，一个指针指向该结点的后继结点，另一个指针指向它的前驱结点

判断题：

1.线性表的逻辑顺序与物理顺序总是一致的

错误

2.线性表的顺序存储表示优于链式存储表示

错误

3.线性表若采用链式存储表示时，所有结点的地址可连续可不连续

正确

4.每种数据结构都应具备三种基本运算：插入、删除和搜索

正确

5.线性表的特点是每个元素都有一个前驱和一个后继

错误

6.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好

错误

填空题

线性表（a1,a2,…,an）有两种存储结构：（A）和（B）。（A）存储密度较大，（B）存储利用率较高，（A）可随机存取，（B）不可随机存取，（B）插入和删除操作比较方便。

A.顺序存储结构

B.链式存储结构

在单链表中，删除指针p所指结点的后继结点的语句是：（）

p-next=p-next-next

带头结点的单循环链表Head的判空条件是（）。

Head-next==Head

画出下列数据结构的图示：①顺序表②单链表③双链表④循环链表

在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动（）个元素。

n-i+1

对于双向链表,在两个结点之间插入一个新结点需修改的指针共（）个，单链表为（）个。

42

带头结点的双循环链表L中只有一个元素结点的条件是：（）

L-next-next==L

在单链表L中，指针p所指结点有后继结点的条件是：（）

p-next!=NULL

当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（）存储结构。

顺序