数据结构(C语言版CHAP4

装入模块
模块 A …… If () JSR “L” Else JSR L+M
Return 模块 B
内存
K
L-1
0
M-1
L-1 L L+M-1 L+M
Return 模块 C
Return
…… If () JSR K+L Else JSR K+L+M ……
0 N-1
4、1 程序的装入和链接

装入时动态链接（Load-time Dynamic Linking）:
0 A B C
系统区 作业区 空闲区 用户区
4、2 连等待装入 内存的作业排成一个作业队列。当主存储器中 无作业或一个作业执行结束，就可以让作业队 列中的下一个作业装入内存。
地址转换方式：静态重定位 缺点：

（ 1 ）当作业执行中出现了某个等待事件， CPU 处 于空闲状态，不能被充分利用。
0 1 2 3 … 200 … 2500 …
重定位寄存器 1000
…
LOAD R1,2500 … 9 …
+
F1.exe
重定位的实现
• 动态运行时装入方式的特点：
1.为了提高运行速度，需要重定位寄存器的支 持。 2.在装入程序的同时将装入的起始地址写入重 定位寄存器中。 3.程序装入时使用的仍然是逻辑地址；而在程 序运行时才将逻辑地址修改为物理地址。 4.物理地址=重定位寄存器中的地址+逻辑地址 5.装入内存的程序可以移动，将移动后的起始 地址记入重定位寄存器。
在分区使用表中按作业名找到相应的表项：作 业名=结束的作业名&&状态=“已分配”


将状态修改为“未分配”

…
an-1,0 an-1,1
…
an-1,n-1
an-1,0 an-1,1
…
…
Ann
a0,0 a1,0
a0,1 a1,1
… …
a0,n-1 a1,n-1
Ann
a0,0 a1,0
a1,1
…
…
…
an-1,n-1
对称阵
中国网页设计 xin126
下三角矩阵
第5章 数组和广义表
中国网页设计 xin126
数据结构
（C语言版）
严蔚敏、吴伟民编著 清华大学出版社 学习网站：xin126/list.asp?id=301
中国网页设计 xin126
第5章 数组和广义表
主要内容：
一、数组的定义 二、数组的表示和实现 三、矩阵的压缩存储 四、广义表的定义 五、广义表的存储结构
中国网页设计 xin126
第5章 数组和广义表
0 0 0 0 0 0
0 0 0 0 0 0
中国网页设计 xin126
第5章 数组和广义表
(2) 稀疏矩阵的存储： 若按常规方法进行存储，零值元素会占了很大空间 因此对于稀疏矩阵的存储通常采用以下两种方式： 三元组表和十字链表进行存储。
中国网页设计 xin126
第5章 数组和广义表
中国网页设计 xin126
第5章 数组和广义表
以行序为主序的求址公式：
假设每个数据元素占L个存储单元，则二维 数组A中任一元素aij的存储位置可由下式确定： LOC(i, j) = LOC(0, 0) + (n×i + j)*L 式中，LOC(i, j)是aij的存储位置，LOC(0, 0)是a00的存储位置，即二维数组A的起始存储 位置，也称为基地址或基址。b2是数组第二维 的长度，即数组A(m×n)中的列数n。

n(n≥ n0)满足T(n)≤c×f(n) 。
-
16
例1-3 设数组a和b在前边部分已赋值，求如下两个n阶矩 阵相乘运算算法的时间复杂度。
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ c[i][j]=0;
//基本语句1
for(k=0;k<n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j]; //基本语句2
-
4
线性结构：除第一个和最后一个数据元素外，每个
数
数据元素只有一个前驱和一个后继数据元素。
据
的
树结构：除根结点外，每个数据元素只有一个前驱
逻
数据元素，可有０个或若干个后继数据元素。
辑
结
构
图结构：每个数据元素可有０个或若干个前驱数据
元素和０个或若干个后继数据元素。
-
5
线性结构
树结构
-
图结构
6
顺序存储结构：把数据元素存储在一块连续地址空
void BubbleSort(int a[],int n)
{ int i,j,flag=1; int temp;
for(i=1;i<n&&flag==1;i++)
{ flag=0;
for(j=0;j<n-i;j++)
{ if(a[j]>a[j+1])
{ flag=1; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
数据间的逻辑关系表现在结点的链接关系上。
-

3) 一对一关系（1：1）
12
4. 永久关系的建立和编辑
1) 建立
a. 建立两张表的索引 b. 在“数据库设计器”中拖动索引标识
2) 编辑
a. 在“数据库设计器”中双击关系连线 b. 单击连线 数据库 编辑关系
3) 删除
1) 单击连线，按[DEL]键 2) 右击连线 删除关系
13
5. 设置参照完整性规则
第4章 数据库的创建和使用 章
1
4.1 VFP数据库概述 数据库概述
1. 数据库是一个包容器，用来组织和联系表。 数据库是一个包容器，用来组织和联系表。 2. 内容： 内容：
1) 2) 3) 4) 5) 表 表之间的关系 连接 视图 存储过程
2
4.2 数据库的创建
1. 创建数据库
1) 利用“项目管理器”创建 2) 文件 新建或“新建”按钮 3) CREATE DATABASE [数据库名|？]
6
3. 字段的验证规则
1) 2) 3) 4) 用来控制用户输入到字段中的信息类型 实现数据库数据的完整性。 在字段值改变时，激活规则。 可在“表设计器”中设置，
4. 记录的验证规则
1) 用来控制用户输入到记录中的信息。 2) 从数据库中移去具有关联规则的表时，所有属于 该表 的字段级和记录级规则都会从数据库中删除。
14
6. 数据完整性综述
1) 三类完整性
a. 实体完整性：字段级、记录级 b. 参照完整性：表级 c. 用户自定义完整性
2) 通过字段级、记录级和表间三级完整性约束， 有效地实现了数据的完整性和一致性。
15
9
7. 在数据库中添加、移去表 在数据库中添加、
1) 一张表只能属于一个数据库。 2) 数据库处于打开状态且为当前数据库时： a. 系统自动将新建的表添加到当前数据库中 b. ADD TABLE 自由表文件名 [NAME 长表名] ：将已存 在的自由表添加到数据库中 c. 项目管理器中操作 3) REMOVE TABLE 表名 [DELETE] ：从数据库中移动表 [DELETE]项是把表从磁盘上删除