第七章：查找
第七章：查找 主关键字：可唯一标识记录的关键字 次关键字：用以识别若干记录的关键字 关键字的平均比较次数，平均查找长度ASL（Average Search Length） $$ASL = \sum_{i=1}^np_ic_i$$ 参数 说明 n 记录的个数 pi 查找到第i个记录的概率 ci 查找到第i个记录所需的比较次数 一、线性表的查找1.顺序查找应用范围：顺序表或线性表表示的静态查找表（表内元素无序） 12345typedef struct { ElemType *R;//表基址 int length;//表长} SSTable;//Sequential Search TableSSTable ST;//定义顺序表ST 注意到每执行一次循环都要进行两次比较， ...
第七章：查找
第七章：查找 主关键字：可唯一标识记录的关键字 次关键字：用以识别若干记录的关键字 关键字的平均比较次数，平均查找长度ASL（Average Search Length） $$ASL = \sum_{i=1}^np_ic_i$$ 参数 说明 n 记录的个数 pi 查找到第i个记录的概率 ci 查找到第i个记录所需的比较次数 一、线性表的查找1.顺序查找应用范围：顺序表或线性表表示的静态查找表（表内元素无序） 12345typedef struct { ElemType *R;//表基址 int length;//表长} SSTable;//Sequential Search TableSSTable ST;//定义顺序表ST 注意到每执行一次循环都要进行两次比较， ...
第五章：IO管理
...
第四章：文件管理
第四章：文件管理 一、文件目录★1.文件控制块文件控制块FCB，File Control...
第三章：内存管理
...
第二章：进程管理
第二章：进程管理 一、进程与线程1.进程概述 （1）进程PCB：进程是进程实体的运行过程，是系统进行资源分配和调度的一个单位。 概念 说明 程序 是指静态的存放在磁盘里、的可执行的文件，实际上为一系列的指令集合 进程 是指动态的、程序的一次执行过程 一个程序可以同时创建多个进程，当进程被创建时操作系统会为该进程分配唯一不重复的身份证号PID。 PCB是进程存在的唯一标志，当进程被创建时系统会为其创建PCB，结束时会收回其PCB。 这些信息都将被保存在一个数据结构PCB（Process Control...
第一章：操作系统概述
...
第一章：绪论
第一章：绪论 一、基本概念1.Data数据Data数据：是能够输入计算机且能被计算机处理的各种符号的集合。 Data数据包括： 数值型数据：整数、实数 非数值型数据：文字、图像、图形、声音等 2.DataElement数据元素DataElement数据元素（元素/记录/结点/顶点）：是Data数据的基本单位，在计算机程序中通常被作为一个整体进行考虑和处理 3.DataItem数据项DataItem数据项：是构成数据元素的不可分割的最小单位。 数据三者之间的关系：数据 > 数据元素 >...
第二章：线性表
第二章：线性表 一、线性表线性表：具有相同特性的数据元素的一个有限序列，数据元素的个数定义为表的长度。 线性表ADT的定义如下： 1234567891011ADT List { 数据对象: D = {ai | ai属于Element, (i = 1, 2, ..., n)} 数据关系: R = {<ai-1, ai> | ai-1, ai属于D, (i = 1, 2, ..., n)} 基本操作: InitList(&L); DestroyList(&L); ListInsert(&L, i, e); ListDelete(&L, i, &e);} ADT...
第三章：栈与队列
第三章：栈与队列 栈Stack和队列是线性表的子集，是限定插入和删除只能在表的端点进行的线性表。 一、顺序栈栈Stack是一个特殊的线性表，限定仅在一端（通常是表尾/栈顶）进行插入和删除操作的线性表。 栈的特点： 逻辑结构：与线性表相同 存储结构：用顺序栈或链栈均可，顺序栈更为常见 运算规则：只能在栈顶进行运算，访问结点时按照后进先出的LIFO原则 实现方式：关键在于入栈与出栈函数，具体实现顺序栈与链栈不同。 栈的相关问题： 数制转换 表达式求值 括号匹配的检验 八皇后问题 迷宫求解 函数调用 递归调用的实现 行编辑程序 1.顺序栈（1）顺序栈表示：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端。 123456#define MAXSIZE 100typedef struct { SElemType *base; SElemType *top; int stackSize;}...