数据结构习题及答案与实验指导(线性表)2.pdf资源-CSDN文库

版权申诉

149 浏览量 2022-11-12 13:08:26 上传评论收藏 958KB PDF 举报

资源推荐

资源详情

资源评论

第 2 章线性表

线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章

主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺

序、链式两种存储结构上基本运算的实现。

重点提示：

 线性表的逻辑结构特征

 线性表的顺序存储和链式存储两种存储结构的特点

 在两种存储结构下基本操作的实现

2-1 重点难点指导

2-1-1 相关术语

1．线性表

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a

,…,a

)，

其中 n 为表长，n=0 时称为空表。

要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。

2．顺序表

顺序存储的线性表。

要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：

用物理上的相邻实现逻辑上的相邻。

3．链表

用链表存储的线性表。

要点：链表是通过每个结点的链域将线性表的n 个结点按其逻辑顺序链接在一起的，对

每个结点的地址是否连续没有要求。

4．单链表

每个结点除了数据域外还有一个指向其后继的指针域。

要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后

继结点的指针表示线性表的逻辑结构。

5．头指针

要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个

链表。如链表 H，链表 L 等，表示链表中第一个结点的地址存放在指针变量H、L 中。通常

用头指针来惟一标识一个链表。

6．头结点

要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个

非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。

7．头结点的作用

要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位

置上的操作和在其他位置上的操作一致，无需特殊处理。

2-1-2 线性表的顺序存储

1．顺序表

顺序存储的线性表称为顺序表。其特点是：用一组地址连续的存储单元来依次存放线性

表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。

具体实现：在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储

区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。考虑到线性表的运

算有插入、删除等，即表长是可变的，因此，数组的容量需设计得足够大，设用 data[MaxSize]

来表示，其中 MaxSize 是一个根据实际问题定义的足够大的整数，线性表中的数据从 data[0]

开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MaxSize 个，因此需用一个

变量 last 记录当前线性表中最后一个元素在数组中的位置，即 last 起一个指针的作用，

始终指向线性表中最后一个元素，因此，表空时last=-1。

这种存储思想的具体实现可以是多样的。

方法一：可以用一个数组和表示长度的变量共同完成上述思想，如：

#define MaxSize ……

//MaxSize为根据实际问题定义的足够大的整数

DataType data[MaxSize];

int last;

这样表示的顺序表如图 2-1 所示。数据元素分别存放在data[0]到 data[last]中。

这样使用简单方便，但有时不便管理。

MaxSize

0 1 …

i …

data a

… a

i-1

i+1

… a

last

…

图 2-1 线性表的顺序存储示意图

方法二：从结构上考虑，通常将 data 和 last 封装成一个结构作为顺序表的类型：

#define MaxSize ……

//MaxSize为根据实际问题定义的足够大的整数

typedef struct{

DataType data[MaxSize];

int last; //表示线性表最后一个元素位置。

}SeqList;

定义一个顺序表变量：SeqList L ;

这样表示的线性表如图 2-2（a）所示。表长为 L.last+1，线性表中的数据元素a

分别

存储在 L.data[0]~L.data[L.last]中。

方法三：由于教科书中的算法用Visual C++语言描述，根据 Visual C++语言中的一些规

则，有时定义一个指向 SeqList 类型的指针更为方便：

SeqList *L ；

L 是一个指针变量，线性表的存储空间通过 L=new SeqList 操作（Visual C++语句，

不同的语言版本可能有所不同）来获得。

L 中存放的是顺序表的地址，这样表示的线性表如图2-2（b）所示。表长表示为（*L）.last+1

或 L-＞last+1，线性表中数据元素的存储空间为：

L-＞data[0] ~ L-＞data[L-＞last]。

读者通过上述介绍的几种表示方式，进一步体会顺序存储的“理念”，做题时根据题意

灵活掌握，在读写算法时注意相关数据结构的类型说明。

L.data

L.last

…

MaxSize-1

（a）表长为 L.last+1

MaxSize-1

（b）表长为 L->last+1

L->last

L->length

L->data

…

图 2-2 线性表的顺序存储示意图

2．顺序表的优缺点

优点 1：顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。

设 a

１

的存储地址为 Loc(a

１

)，每个数据元素占 d 个存储地址，则第 i 个数据元素的地址为：

Loc(a

)=Loc(a

１

)+(i-1)*d 1≤i≤n

这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i 个数

据元素的地址来，这就是顺序表具有按数据元素的序号随机存取的特点。

优点 2：存储密度高。

缺点 1：在顺序表中做插入和删除运算时，平均需移动大约表中一半的元素；

缺点 2：顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，

因此分配不足则会造成溢出；分配过大，又可能造成存储单元的浪费。

2-1-3 链表

1．单链表

链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间

的线性关系，对每个数据元素 a

，除了存放数据元素自身的信息 a

之外，还需要和 a

一起

存放其后继 a

i+1

所在的存储单元的地址，这两部分信息组成一个

“结点”，结点的结构如图 2-3 所示，每个元素都如此。因此 n

data next

个元素的线性表通过每个结点的指针域拉成了一个“链子”，称

图 2-3 单链表结点结构

之为链表。因为每个结点中只有一个指向后继的指针，所以称其

为单链表。

链表是由一个个结点构成的，结点定义如下：

typedef struct Node{

DataType data;

struct Node *next;

}LNode,*LinkList;

LNode 是结点的类型，*LinkList 是指向 LNode 结点的指针类型。

作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地

址并不关心，所以通常的单链表用图2-4 的形式表示。

…

∧

图 2-4 单链表

通常用“头指针”来标识一个单链表，如单链表L、单链表 H 等，是指某链表的第一个

结点的地址放在了指针变量L、H 中，头指针为“NULL”则表示一个空表。

2．单循环链表

对于单链表而言，最后一个结点的指针域是空指针，如果将该链表的头指针置入该指针

域，则使得链表头尾结点相连，就构成了单循环链表。

对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点

开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变

一下链表的标识方法，不用头指针而用一个指向尾结点的指针R 来标识，可以使操作效率得

以提高。

3．双向循环链表

在单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为

p，其后继结点的指针则为p

>next，而找其前驱结点则只能从该链表的头指针开始，顺着各

结点的 next 域进行，也就是说找后继结点的时间性能是O(1)，找前

驱的时间性能是 O(n)，如果希望找前驱结点的时间性能也达到

O(1)，则只能付出空间的代价：每个结点再加一个指向前驱结点的

指针域，结点的结构如图 2-5 所示，用这种结点组成的链表称为双

向链表。

双向链表结点及指针类型定义如下：

typedef struct DLNode{

DataType data;

struct DLNnode *prior,*next;

}DLNode,*DLinkList;

prior

data

图 2-5 双向链表

和单链表类似，双向链表通常也是用头指针标识。

通过双向链表中某结点的指针 p 既可以直接得到它的后继结点的指针 p

>next，也可以

直接得到它的前驱结点的指针 p

>prior。这样在有些操作中需要找前驱结点时，则勿需再用

循环。

设 p 指向双向循环链表中的某一结点，即p 中是该结点的指针，则 p

>prior

>next 表示

的是 p 所指结点之前驱结点的后继结点的指针，即与p 相等；类似，p

>next

>prior 表示的

剩余17页未读，继续阅读

评论收藏

内容反馈

版权申诉

G11176593

粉丝: 6700
资源: 3万+

数据结构习题及答案与实验指导(线性表)2.pdf

数据结构习题及答案与实验指导(线性表)2.docx

《数据结构》第二章线性表习题及参考答案.pdf

数据结构线性表答案.pdf

数据结构-实验2线性表.pdf

数据结构课后习题答案第二章 线性表.pdf

《数据结构》第二章线性表习题.pdf

《数据结构》习题集：线性表参考.pdf

数据结构教程（第五版）清华大学出版社课后习题答案第2章线性表.pdf

数据结构 学习资料 严蔚敏教材 习题集答案

算法与数据结构线性表答案.pdf

西南交大数据结构习题答案（线性表、栈、字符串）.pdf

数据结构实验一线性表 [数据结构实验报告] .pdf

数据结构实验线性表基本操作.pdf

数据结构实验2线性表答案.doc

数据结构与算法_线性表习题二_艾孜尔江·艾尔斯兰作.pdf

数据结构与算法_线性表习题一_艾孜尔江·艾尔斯兰作.pdf

算法与数据结构习题答案+课件+参考资料 国防工业出版社 张永 李睿

数据结构(C#语言版)

数据结构(C#语言版).

数据结构-实验1-线性表的基本操作.pdf

数据结构实验01-线性表.pdf

【数据结构·C（实验）】线性表的顺序实现.pdf

数据结构实验一题目一线性表实验报告 (2).pdf

考研-数据结构-殷人昆.zip

数据结构第五版课后习题详解

数据结构案例教程(C语言版).rar

[详细完整版]数据结构8.pdf

数据结构习题与解析B级_李春葆

最新资源

数据结构课后习题答案第二章线性表.pdf

数据结构学习资料严蔚敏教材习题集答案

算法与数据结构习题答案+课件+参考资料国防工业出版社张永李睿