数据结构讲义5

《数据结构》讲义什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。

其中建立数学模型的实质：找出操作对象之间的关系。

例1. 图书馆书目检索——对应线性关系例2. 博奕树——对应树型关系例3. 交叉路口交通灯管理——对应图状结构。

数据结构是一门研究非数值计算的程序设计问题中（地计算机的操作对象及它们之间的关系和操作等的学科。

位）数据结构的基本概念和术语1. 数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。

包括数值、字符、声音、图象等。

2. 数据元素（Data Element）数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。

一个数据元素可由若干个数据项组成（Data Item）。

3. 数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。

由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。

综上1~3所述，再分析数据概念：4. 结构（Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。

(1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

(2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。

(3) 树形结构：结构中的数据元素之间存在着一对多的层次关系。

(4) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

1．下面关于串的的叙述中，哪一个是不正确的？（ E ）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行concat(replace (S1,substr (S1,length(S2), length(S3)), S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（E ）A．ABC###G0123 B．ABCD###2345 C．ABC###G2345D．ABC###2345 E．ABC###G1234 F．ABCD###1234G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）。

A．求子串B．联接C．匹配D．求串长4．已知串S=‘aaab’,其Next数组值为（A ）。

A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（C ）。

A．012345678999 B．012121111212C．011234223456 D．01230123223456．字符串‘ababaabab’的nextval 为（A）。

A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（D ）， nextval数组的值（F）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 18．若串S=‘software’，其子串的数目是（B ）。

《数据结构》讲义数据结构是计算机科学和编程中非常重要的概念之一。

它是指在计算机中存储和组织数据的方法和原则。

一、介绍数据结构在计算机科学领域中具有重要的地位。

它涉及到如何存储和组织数据，以便于对其进行检索和操作。

数据结构可以分为两种基本类型：线性结构和非线性结构。

线性结构包括数组、链表、栈和队列，而非线性结构包括树和图。

二、线性结构1. 数组数组是一种用来存储多个相同类型的元素的数据结构。

它具有固定长度和连续的内存空间。

数组可以通过索引访问元素，可以快速地插入和删除元素，但是其长度固定不变。

2. 链表链表是一种由节点组成的数据结构，每个节点都包含一个值和指向下一个节点的指针。

链表可以在任意位置插入和删除节点，但是访问节点的时间复杂度较高。

3. 栈栈是一种具有特定操作限制的线性结构。

它遵循“先进后出”的原则，即最后插入的元素最先被访问和删除。

栈可以用来实现递归、回溯和表达式求值等功能。

4. 队列队列也是一种具有特定操作限制的线性结构。

它遵循“先进先出”的原则，即最先插入的元素最先被访问和删除。

队列可以用来实现任务调度、缓冲区等功能。

三、非线性结构1. 树树是一种由节点组成的非线性结构。

它包含一个根节点和多个子节点，每个节点可以有任意数量的子节点。

树可以用来表示层次关系、排序和搜索等功能。

2. 图图是一种由节点和边组成的非线性结构。

节点表示实体，边表示节点之间的关系。

图可以用来表示网络、关系和路径等信息。

四、常用数据结构在实际编程中，还有一些常用的数据结构：1. 哈希表：通过哈希函数将元素映射到不同的位置，实现快速的查找和插入操作。

2. 堆：一种特殊的树结构，可以快速找到最大或最小的元素。

3. 二叉搜索树：一种有序的二叉树，可以高效地进行搜索和插入操作。

五、应用场景数据结构在实际开发中有广泛的应用场景，包括但不限于以下几个方面：1. 数据库系统中的索引结构：为了快速检索数据，数据库系统使用各种数据结构来组织数据。

第四章图4.1图的概念1．图的定义图是由一个顶点集V和一个弧集R构成的数据结构。

2.图的重要术语；（1）无向图：在一个图中，如果任意两个顶点构成的偶对（v,w）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。

（2）有向图：在一个图中，如果任意两个顶点构成的偶对（v,w）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。

（3）无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。

在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

（4）有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。

在一个含有n个顶点的有向完全图中，有n(n-1)条边。

（5）稠密图、稀疏图：若一个图接近完全图，称为稠密图；称边数很少（e<nlogn）的图为稀疏图。

（6）顶点的度、入度、出度：顶点的度（degree）是指依附于某顶点v的边数，通常记为TD(v)。

在有向图中，要区别顶点的入度与出度的概念。

顶点v的入度是指以顶点为终点的弧的数目，记为ID(v)；顶点v出度是指以顶点v为始点的弧的数目，记为OD(v)。

TD(v)=ID(v)＋OD(v)。

（7）边的权、网图：与边有关的数据信息称为权（weight）。

在实际应用中，权值可以有某种含义。

边上带权的图称为网图或网络（network）。

如果边是有方向的带权图，则就是一个有向网图。

（8）路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp,vi1,vi2,…,vim,vq.。

其中，（vp,vi1），(vi1,vi2)，…,(vim,.vq)分别为图中的边。

路径上边的数目称为路径长度。

（9）简单路径、简单回路：序列中顶点不重复出现的路径称为简单路径。

除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。

（10）子图：对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。