《大学计算机基础》课件第4章

4.1数据结构4.2文件结构4.3数据库

4.1.1数据结构的基本概念

1．数据与数据结构

2．数据的逻辑结构

3．数据的存储结构

4．数据的运算

5．线性结构与非线性结构

4.1数据结构

4.1.2线性表

1．线性表的定义和逻辑特征

2．线性表的顺序存储结构

4.1.3栈

1．栈的定义

如图4-1所示，栈中有元素a1，a2，…，an，a1称为栈底元素。新元素进栈要置于an之上，删除或出栈必须先对an进行操作。图4-1栈结构2．栈的顺序存储方式

3．栈的基本运算

4.1.4队列

1．队列的定义

队列(Queue)是允许在一端进行插入、而在另一端进行删除的线性表，如图4-2所示。

2．循环队列

为了克服“假溢出”现象采用循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供循环队列使用，如图4-3所示。

3．循环队列的基本运算

图4-2队列的示意图图4-3循环队列存储空间示意图4.1.5线性链表

1．结点结构

在链式存储方式中，每个结点由两部分组成：一部分用于存放数据元素的值，称为数据域；另一部分用于存放指针，称为指针域，用于指向该结点的后继结点的指针，如图4-4所示。图4-4结点的结构

2．单链表

用链式存储结构存储的线性表称作链表。图4-5所示的就是一个单链表。

3．双向链表

在单链表中，每一个结点只有一个指针域，由这个指针只能找到其后继结点，而不能找到其前趋结点。因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针(llink)，指向其前趋结点；另一个称为右指针(rlink)，指向其后继结点，这种链表称为双向链表，其结点结构如图4-6所示，逻辑结构如图4-7所示。图4-5单链表示意图图4-6双向链表的结点结构图4-7双向链表示意图

4．循环链表

5．链式栈

6．链式队列

7．线性链表主要基本运算

线性链表的插入过程是先向系统申请一个新结点(由指针q指向)，并赋值，然后利用查找算法找到待插入位置的前一结点的指针p并修改两个指针即可：先将结点q的指针域内容改为结点p的原后继结点，再将结点p的指针域内容改为指向结点q，线性链表的插入如图4-8所示。

图4-8线性链表的插入

(3)删除结点。先判断线性链表是否为空，然后对非空表利用查找算法找到待删除位置的前一结点的指针p，用另一指针q暂时保存结点p的后继结点(即待删除结点)，再把p结点的后继直接链接在q结点的后继结点上，最后释放q结点所分配的内存空间，如图4-9所示。

8．循环链表及基本运算

图4-9线性链表的删除4.1.6树与二叉树

树形结构是一种简单的非线性结构，在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性，它体现了数据元素之间的“一对多”的联系。树和二叉树是最常用的树形结构。

1．树的基本概念

在图4-10中，结点A为根结点。图4-10树的表示

2．二叉树的基本概念

因此，二叉树具有五种基本形态，分别是空二叉树，只有一个根结点的二叉树，只有左子树的二叉树，只有右子树的二叉树，左、右子树都有的二叉树，如图4-11所示。图4-11二叉树的五种形态(a)空二叉树；(b)只有一个根结点的二叉树；、(c)只有左子树的二叉树；(d)只有右子树的二叉树；(e)左、右子树都有的二叉树

3．二叉树的性质

4．二叉树的存储

二叉树的存储常采用链接方式，它是指用链表来表示的一棵二叉树，即用链来指示元素的逻辑关系。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左子树和右子树所在的链结点的存储地址。二叉树结点的存储结构如图4-12所示。图4-12二叉树结点的存储结构

5．二叉树的遍历

遍历是树形结构的一种重要运算。遍历一个树形结构就是按一定的次序访问该结构中的所有结点，使每个结点恰好被访问一次。可以按多种不同的次序遍历树形结构，在这里仅介绍三种重要的二叉树遍历的方法。

图4-13树的结构4.2.1操作系统的文件管理功能

1．计算机文件的基本概念

2．文件管理

3．文件的分类

4．文件的结构

4.2文件结构4.2.2顺序文件

1．连续结构顺序文件

图4-14给出了连续结构文件的图形说明。图中，一个逻辑块号为0、1、2、3的文件依次存放在物理块15、16、17、18中。图4-14连续结构文件的示意图

2．链结构顺序文件

图4-15给出了链结构文件的物理结构。使用链结构时，不必在文件说明信息中指明文件的长度，只要指明该文件的第一个块号就可以按链指针检索整个文件。链结构的另一个特点是文件长度可以动态地增长，只要调整链指针就可在任何一个信息块之间插入或删除一个信息块。图4-15链结构文件的示意图4.2.3文本文件

文本文件是一种典型的顺序文件，其文件的逻辑结构又属于流式文件。

4.2.4索引文件

索引结构如图4-16所示。图4-16索引结构文件的示意图通常有的文件很大，文件索引表也就较大。如果索引表的大小超过了一个物理块，可以采用间接索引(多重索引)，也就是在索引表所指的物理块中存放的不是文件信息，而是装有这些信息的物理块地址。这样，如果一个物理块可装下n个物理块地址，则经过一级间接索引，可寻址的文件长度将变为n×n块。如果文件长度还大于n×n块，还可以进行类似的扩充，即二级间接索引，其原理如图4-17所示。图4-17文件的多级索引结构4.2.5哈希文件

在日常生活和工作中，经常会遇到查找操作，如在列车时刻表中查找某次列车的开车时间、在学生成绩表中查找某位学生的成绩等。4.3.1数据库技术的发展

计算机对数据的管理是指对数据的组织、分类、编码、存储、检索和维护提供操作手段。

1．人工管理阶段

2．文件系统阶段

3．数据库系统阶段

4.3数据库4.3.2数据库的基本概念

1．数据库系统的基本概念

1)数据库

2)数据库管理系统

3)数据库管理员

4)数据库系统

5)数据库应用系统

图4-18所示为数据库应用系统的组成示意图。图4-18数据库应用系统的组成示意图

2．数据库管理系统的基本功能

3．数据库系统的基本特点

4.3.3数据模型

1．什么是数据模型

2．E-R模型

3．关系数据模型

表4-1给出的学生考试成绩表便是一个关系模型。在这张表中，每一列的命名都与学生的信息有关系，每一列是同一属性，每一行称为一条记录。

表4-1学 生 信 息 表4.3.4数据库的安全

数据库的安全是数据库系统的生命。

1)用户身份认证

2)存取控制

3)数据加密

4)审计追踪与攻击检测4.3.5数据库设计

数据库设计方法中比较著名的有新奥尔良(NewOrleans)方法，它将数据库设计过程分为4个阶段：需求分析、概念结构设计、逻辑结构设计和物理结构设计，如图4-1