Java编程

学堂在线数据结构第四章答案

我国各大院校一般都把国内外通用的权威教科书作为本科生和研究生学习专业课程的参考教材,这些教材甚至被很多考试(特别是硕士和博士入学考试)和培训项目作为指定参考书。为了帮助读者更好地学习专业课,我们有针对性地编著了一套与国内外教材配套的复习资料,并提供配套的名师讲堂和题库。

李春葆所著的《数据结构教程》(第4版,清华大学出版社)是我国高校采用较多的计算机专业优秀教材,也被众多高校指定为计算机专业考研参考书目。

作为该教材的辅导书,本书具有以下几个方面的特点:

学堂在线数据结构第四章答案

1.整理名校笔记,浓缩内容精华。在参考了国内外名校名师讲授李春葆《数据结构教程》的课堂笔记基础上,本书每章的复习笔记部分对该章的重难点进行了整理,同时对重要知识点进行点拨,因此,本书的内容几乎浓缩了配套教材的知识精华。

2.解析课后习题,提供详尽答案。本书参考大量数据结构相关资料对该教材的重难点课(章)后习题进行了详细的分析和解答,并对相关重要知识点进行了延伸和归纳。

第1章 绪 论

1.1 复习笔记

一、数据结构概述

1.数据结构的定义

(1)基本概念

数据是描述客观事物的数和字符的集合,是计算机能操作的对象的总称,也是计算机处理信息的某种特定的符号表示形式。

(2)相关术语

①数据元素

数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候,一个数据元素可以由若干个数据项组成。

②数据项

数据项又称字段或域,它是具有独立含义的最小数据单位。

③数据对象

数据对象是性质相同的数据元素的集合,它是数据的子集。

(3)数据结构的内容

①数据元素之间的逻辑关系,即数据的逻辑结构,它是数据结构在用户面前呈现的形式。

②数据元素及其关系在计算机存储器中的存储方式,即数据的存储结构,又称数据的物理结构。

③施加在数据上的操作,即数据的运算。

(4)逻辑结构

数据的逻辑结构是从逻辑关系(主要是指数据元素的相邻关系)上描述数据的,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

(5)存储结构

数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示(又称映像),也就是逻辑结构在计算机中的存储方式,它是依赖于计算机语言的。一般只在高级语言(例如C/C++语言)的层次上讨论存储结构。

数据的运算最终需在对应的存储结构上用算法实现。

总之,数据结构是一门讨论“描述现实世界实体的数学模型(通常为非数值计算)及其之上的运算在计算机中如何表示和实现”的学科。

(6)数据结构的表示

对于一种数据结构,其逻辑结构总是惟一的,但它可能对应多种存储结构,并且在不同的存储结构中,同一运算的实现过程可能不同。

描述数据结构通常采用二元组表示:

B=(D,R)

其中,B是一种数据结构,它由数据元素的集合D和D上二元关系的集合R组成,即:

1≤i≤n,n≥0}

1≤j≤m,m≥0}

其中di表示集合D中的第i个数据元素(或节点),n为D中数据元素的个数,特别地,若n=0,则D是一个空集。rj表示集合R中的第j个关系,m为R中关系的个数,特别地,若m=0,则R是一个空集,表明集合D中的数据元素间不存在任何关系,彼此是独立的,这和数学中集合的概念是一致的。

R中的一个关系r是序偶的集合,对于r中的任一序偶 x,y (x,y∈D),把x称作序偶的第一节点,把y称作序偶的第二节点,称序偶的第一节点为第二节点的前驱节点,称第二节点为第一节点的后继节点。若某个节点没有前驱节点,则称该节点为开始节点;若某个节点没有后继节点,则称该节点为终端节点。

对于对称序偶,即 x,y ∈R,且 y,x ∈R(x,y∈D),可用圆括号代替尖括号,即(x,y)∈R。

数据结构还可以利用图形形象地表示出来,图形中的每个节点对应一个数据元素,两节点之间的连线对应关系中的一个序偶。

2.逻辑结构类型

(1)集合

集合是指数据元素之间除了“同属于一个集合”的关系外,别无其他关系。

(2)线性结构

线性结构是指该结构中的节点之间存在一对一的关系。其特点是开始节点和终端节点都是惟一的,除了开始节点和终端节点以外,其余节点都有且仅有一个前驱,有且仅有一个后继。线性表就是一种典型的线性结构。

(3)树形结构

树形结构是指该结构中的节点之间存在一对多的关系。其特点是每个节点最多只有一个前驱,但可以有多个后继,且终端节点可以有多个。二叉树就是一种典型的树形结构。

(4)图形结构

图形结构是指该结构中的节点之间存在多对多的关系。其特点是每个节点的前驱和后继的个数都可以是任意的。图形结构可能没有开始节点和终端节点,也可能有多个开始节点、终端节点。

树形结构和图形结构统称为非线性结构。

3.存储结构类型

(1)顺序存储结构

①存储方式

该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元里,节点之间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于计算机程序设计语言的数组来描述的。

a.节省存储空间;

b.可实现对节点的随机存取。

不便于修改,对节点进行插入、删除运算时,可能要移动一系列的节点。

(2)链式存储结构

①存储方式

该结构不要求逻辑上相邻的节点在物理位置上也相邻,节点间的逻辑关系是由附加的指针字段表示的。通常链式存储结构要借助于计算机程序设计语言的指针类型来描述。

便于修改,在进行插入、删除运算时,仅需修改相应节点的指针域,不必移动节点。

a.与顺序存储方法相比,链式存储方法的主要缺点是存储空间的利用率较低;

b.由于逻辑上相邻的节点在存储空间中不一定相邻,所以不能对节点进行随机存取。

(3)索引存储结构

①存储方式

该结构通常是在存储节点信息的同时,还建立附加的索引表。索引表中的每一项称为索引项,索引项的一般形式是:(关键字,地址),其中关键字惟一标识一个节点,地址是指向节点的指针。

a.这种带有索引表的存储结构可以大大提高数据查找的速度;

b.可以对节点进行随机访问;

c.仍保持较高的数据修改运算效率。

进思学习网提供下载:

李春葆数据结构教程第4版笔记和课后答案

在线阅读完整版 /Ebook/88771.html

相关资料

李春葆《数据结构教程》(C++语言描述)配套题库[名校考研真题+课后习题+章节题库+模拟试题]

李春葆《数据结构教程》(C++语言描述)笔记和课后习题详解

李春葆《数据结构教程》(第4版)笔记和课后习题详解

李春葆《数据结构教程》(第4版)配套题库[名校考研真题+课后习题+章节题库+模拟试题]

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注