计算机软件基础2006讲义.doc

第部分 数据结构第一章 绪论 计算机应用相当普遍，计算机的应用已不再局限于科学计算，而更多用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了编写出一个好的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。这就是数据结构学科形成和发展的背景。1.1 数据结构一般来说， 用计算机解决一个问题时，需要经过如下几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个对此数学模型进行操作的算法，最后编写出程序直至得到解答。 例l： 图书馆的书目检索系统。当你想借阅一本参考书时，你需要到图书馆去查阅图书目录卡片。如果利用计算机实现自动检索，则计算机处理的对象便是这些目录卡片上的书目信息，列在卡片上的一本书的书目信息可由登录号、书名、作者名、分类号、出版单位和出版时间等各项组成。每一本书都有唯一的一个登录号。在书目自动检索系统中建立一张按登录号顺序排列的书目文件，如图1.1，这个文件就是书目自动检索系统中的数学模型。计算机的主要操作就是按照某个特定要求(如给定书名)对书目文件进行查询。 001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02图1.11.2 基本概念1.2.1 数据 是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。如数值、字符串、图像、声音都是数据。1.2.2 数据元素 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理单位，通常个数据元素可由若干个数据项组成。如书目文件中一本书的书目信息就是一个数据元素。书目信息中的每一项(如书名、作者名)为一个数据项，数据项是不可分割的最小单位。 1.2.3 数据对象是性质相同的数据元素的集合，是数据的子集。1.2.4 数据结构 简单的说，是相互之间存在一种或多种特定关系的数据元素的集合。数据结构没有一个明确的定义，它包括三个要素： 1. 数据的逻辑结构 数据的逻辑结构抽象地反映数据元素之间的逻辑关系，而不管这种逻辑关系在计算机中是如何表示的。数据的逻辑结构分为线性结构和非线性结构。若各个数据元素之间的逻辑关系可以用一个线性序列简单的表示出来，则称之为线性结构，否则称为非线性结构。如书目文件中表示一个数据元素，书目文件可表示成（,），所以它是一个线性结构。如图二：数据元素之间的逻辑关系不能用一个线性序列表示出来，所以数据的逻辑结构是非线性结构。 图二2. 数据的存储结构 数据的存储结构是逻辑结构在计算机存储器里的实现。数据的逻辑结构在存储器中的映像应包括数据元素自身值和数据元素之间关系的表示。这样在存储器中，某个结点有两个域，一个是存放自身值的域，用标识符info表示这个域;另一个是存放该结点与其它结点关系的域，用标识符1ink表示这个域。3. 数据的运算 数据的运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。数据的各种逻辑结构都有相应的运算，常用的运算有检索、插入、删除、更新和排序等。 1.3 主要的数据存储方式数据之间的逻辑关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，相应的得到两种不同的存储结构：顺序存储结构和链式存储结构。 1.3.1 顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里。特点：只有信息域，没有指针域。可以通过计算直接确定第i个结点的存储地址。，其中是第一个结点的存储地址，m是每个结点所占用的存储单元数。插入操作和删除操作不方便。 1.3.2 链式存储结构 链式存储结构就是每个结点至少包括一个指针域，用指针来体现数据元素之间的逻辑关系。特点：除了有信息域，还有指针域；逻辑上相邻，物理上不必相邻；插人操作和删除操作方便。1. 4C语言简介第二章 线性表2.1 线性表 1. 定义 线性表的逻辑结构是个数据元素的有限序列，()，其中，称为空表，称为始结点，称为终结点，其余的结点有且仅有一个后继结点，有且仅有一个前趋结点。 2. 线性表具有以下特性（1）线性表中所有数据元素，其性质是相同的，即数据类型是一致的。（2）数据元素之间的相对位置是线性的。3. 对线性表经常进行的一些操作 (l) 查找操作 l 查找第i个结点l 查找值为x的结点(2) 插入操作l 在线性表的第i个结点前面插入一个新结点l 在线性表的第i个结点后面插入一个新结点l 在线性表的值为x的结点前面插入一个新结点l 在线性表的值为x的结点后面插入一个新结点(3) 修改操作l 用新结点替换线性表中的第i个结点l 用新结点替换线性表中值为x结点(4) 排列操作 l 按结点值递增的顺序重新排列线性表的结点l 按结点值递减的顺序重新排列线性表的结点这是常见的对线性表进行的几种操作。2.2 线性表的顺序存储结构用一连续的存储空间依次存储线性表的所有元素。在C语言中顺序存储的线性表是一个一维数组，这样，在C语言中用如下形式来说明一个顺序存储的线性表。int nodemax; 对顺序存储的线性表进行的操作主要有查找、插入和删除。1.下面是顺序表的查找算法：int find(int x) int i,findi; int flag; findi=0； flag=0； i=0; WHILE( (i=p;i- ) nodei+1:=nodei; nodep:=x; last:=last+1; 3.下面是顺序表的删除算法首先看一个例子如表，将3号单元结点删除，把单元4到6之间的所有结点向前移动一个单元。035167283310841255140621578910035167288312541405215678910下面是删除一个结点的算法：void delete (int p )int i; IF (p last-1)| (p0) printf (“position is wrong”); ELSE FOR( i= p+1; idata=b； IF （head= =NIL） head=s； snext=NIL； ELSE IF （headdata= =a） snext=head；head=s； ELSEp=head； WHILE(pdataa) & (pnext!=NIL) q=p； p=pnext； IF Pdata=a qnext=s snext=p； ELSE pnext=s； snext=p； RETURE(head)；下面是对单向链接表进行删除操作的算法：从单向链接表head中删去值为的结点；如果找不到，则打印出错信息。 (struct node *) deletelink (struct node * head；int a) struct node * q , p ； IF （head= =NIL） printf(“this is a emptylist”) ELSE IF （headdata= =a） p=head；head= headnext；free(p); ELSEp=head； WHILE(pdataa) & (pnext!=NIL) q=p； p=pnext； IF Pdata=a qnext= pnext ； free(p)； ELSE printf(“no this node in the list”) RETURE(head)；2. 双链表 在单链表中通过每一个结点的指针域只能查到该结点的后继结点，不能查到该结点的前趋结点，这样一些操作很不方便，如果采用双链表，就可以克服上述缺点。在双链表中，每一个结点有两个指针域，有一个线性表()，它对应的双链表的形式如下： 图2.3在C语言中，结点的类型定义如下：struct node int data; struct node * llink;struct node * rlink;设某个结点的地址为p，它的前趋结点的地址是pllink，它的后继结点的地址是prlink，它的信息域的内容是pdata。对双链表的操作有插入和删除，在地址为p的结点后面插人一个新结点，算法如下： void insert(struct node *p , int x) struct node *r，*q； IF (p=nil) printf(void insert)； ELSE q=( struct node *)malloc (sizeof(struct node )； qdata=x； r=prlink； rllink=q； qrlink=r； q llink=p； prignt=q； 删除地址为p的结点算法如下：void delete(struct node *p) struct node *l,*r； IF （p=nil） printf(“void delete”)； ELSE 1=pllink； r=prlink； lrlink=r; rllink=1； free(p)； 在双链表上插人和删除结点的操作如图2.4和图2.5。prq图2.4p图2.52.3 栈和队列无论线性表的链式存储结构还是线性表的顺序存储结构，插入和删除运算都比较麻烦。在顺序结构中将导致数据元素的大量移动，在链式结构中要逐个结点查询，把插入和删除操作限制在一端进行。2.3.1 栈限定只能在一端进行插入和删除操作的线性表为栈。进行插入和删除的一端为栈顶，表的另一端为栈底。栈的操作在日常生活中经常见到。栈的存储结构有两种：栈的线性存储结构：用stack n 表示栈，n是栈中允许最多的元素的个数，top指向栈顶元素所在的位置，stacktop表示栈顶元素，当top=-1时表示栈空，当top=n-1时表示栈满，栈空时不能做出栈操作，栈满时不能作入栈操作。栈的顺序存储的算法void instack(int top ,int x)if (top= =n-1)printf (“overflow”)else top=top+1;stack top=xvoid outstack(int top,) int y;if (top= =-1)printf(“underflow”);elsey=stack top; top=top-1;栈的链式存储结构：栈的入栈和出栈操作实际是对链表的表头进行插入和删除操作。用top表示一个栈的栈顶指针。struct node int data; struct node * next;下面给出两个过程，其中inlinks的功能是将元素x插入到栈顶；outlinks的功能是删除栈顶元素，并将此元素送给y。(struct node *) inlinks(struct node *top ,int x) struct node *q;q=( struct node *)malloc (sizeof(struct node )；qdata=x;qnext=top; top=q; return(top); （struct node *）outlinks(struct node * top) int y;struct node *q;IF (top=nil) printf(“underfIow”); ELSE q=top;y=qdata;top=qnext；free(q);return(top); 2.3.2 队列 队列是限定在一端进行插入操作，在另一端进行删除操作的线性表。插入的一端为队尾，删除的一端为队首。队列的存储结构有两种：队列的顺序存储结构，队列的链式存储结构。1. 队列的线性存储结构：队列可以用一个向量qm表示，front、rear分别表示排头指针和排尾指针；front指向实际排头元素的前一个位置(表格中用指针F表示)，rear指向实际排尾元素所在的位置(表格中用指针R表示)。初始条件是F=R=-1。下面看一下队列进排出排的情况。可以看出队列上溢的条件是R=m-1，而下溢的条件是R=F。从图2.6中看出，当R=4时若有需要加人队列中，这时满足上溢条件，拒绝进入队列，但此时队列还有三个空额，这种现象称为假溢出。如何避免假溢出现象呢?我们把队列看成一个循环表，假设qm为循环数组，则视q0接在qm-1之后形成循环。如图2.7假定循环队列以顺时针方向伸长，头指针总是在顺时针方向落后于队列中的第一个元素的一个位置，尾指针指向最后加入的元素位置。初始状态（队列为空）时front=rear=m-1，每加入一个元素时，尾指针向顺时针方向移动一个位置，即rear=rear+1;if rear=m;then rear=1;同样，每删除一个元素时，头指针便向顺时针方向移动一个位置。front=front+1;if front=m;then front=1;在循环队列中如何判别是空还是满呢？当队列为空或满时，都有front=rear，一种办法就是尾指针从后面追上头指针，作为队列满的特征；另一种办法设一个标志位以区别是空还是满。在C语言中定义队列类型：struct queue int itemmax; int front ; int rear ; struct queue q;其中数据项item定义一个容量为0max-1顺序分配的队列，队列中结点的数据是整数，q.front和q.rear分别是排首和排尾的指针。 其中，itemmax: item0itemmax-1;初始有：q.front=q.rear=m-1，q.rear=-1；下面的两个程序insersq和removesq，描述了在用数组表示的顺序分配的队列中，执行进排和出排操作算法。在insersq中它是把数据x添加到已知的队列中去。在removesq中，它把当前队列中的排首结点出排，并把出排结点的数据存人变量y中。设q.rear=-1表示栈空，初始时有q.rear=-1，q.front为0max-1之间的任意一个值。顺序分配的队列上的进排操作算法如下：void insertq (struct queue q ,int x) if(q.rear=q.front) printf(“queue is full”); else if(q.rear=-1)q.rear=q.front; if(q.rear=max-1)q.rear=0;else q.rear=q.rear+1 q.itemq.rear=x; 顺序分配的队列上的出排操作算法如下：void removeq (struct queue q) int y; if (q.rear=-1)printf(“queue is empty”); else if(q.front=max-1) q.front=0; else q.front=q.front+1; y=q.itemq.front;if(q.front=q.rear) q.rear=-1;2. 队列的链式存储结构：在队列的链接表示法中，每个结点由两个域data和next组成，还有两个指针变量front和rear来指示队列的排首和排尾，如图2.8。在队列上执行进排操作，实际上是在rear指向的链接表的表尾处插入一个结点，出排操作实际是在front指向的链接表的表首删除一个结点，一旦front=nil，即发出队列为空的信息。图2.8链接分配队列上的插入操作算法：void insertlq（struct node *front, struct node * rear, int x） struct node *p;p=( struct node *)malloc (sizeof(struct node )；pdata=x;pnext=nil;if(front= = nil ) front=p;else rearnext=p;rear=p;链接分配队列上的删除操作算法：void removelp(struct node *front, struct node * rear) int y;struct node *p; if(front= =nil) printf(“queue is empty”); else p=front; front=pnext; y=pdata;free(p); 第三章 树树形结构是一类重要的非线性结构3.l 树及二叉树3.1.1 树的定义 树是一个结点或多个结点有限集合，有一个特定的结点称为根，其余的结点分为个不相交集合，每个集合又是一棵树，称为子树。如图3.1：ABCDEFGHIJ图3.1 子女：结点的各个子树的根称为该结点的子女； 双亲：该结点是其子女的双亲； 兄弟：具有相同双亲的结点称为兄弟； 结点的度：一个结点子树的个数； 叶：度为0的结点为叶结点； 分支结点：度不为0的结点为分支结点； 结点的层数：根结点的层数为0，其余结点的层数等于其双亲结点的层数加1；树林或森林：0棵或多棵不相交的树的集合。3.1.2 二叉树的定义 二叉树是结点的有限集合，这个集合或者为空，或者由一个根结点及两棵不相交的称为根的左子树和右子树的二叉树组成，注意二叉树不是树的特殊情况，二叉树的子树有左右之分，而树没有左右之分。如图3.2：ABECFGDHIJ图3.2完全二叉树 如果一棵二叉树最多只有最下两层结点的度可以小于2，并且最下层结点都集中在该层的最左边的若干位置上，则称此二叉树为完全二叉树。3.1.3 树的二叉树表示 特点：每一棵树都能唯一地转换到它所对应的二叉树。 转换方式：凡是兄弟都用连线连起来。只留下双亲到第一个子女的连线，双亲到其余子女的连线都去掉。 意义：由于树的二叉树表示可以有利于树的存储和运算，所以把对树的处理转换成对二叉树的处理。3.2 二叉树和树的周游 周游：周游一棵树形结构就是按一定次序系统地访问该结构中的所有结点，使每个结点恰好被访问一次。3.2.1 二叉树的周游 通常二叉树的周游一般有三种算法：前序遍历法、中序遍历法、后序遍历法。1. 中序遍历法中序遍历法的递归定义为： 若二叉树为空，则退出，否则： （1）遍历左子树 （2) 访问根结点 （3) 遍历右子树 （4) 返回 图3.2是一棵二叉树，按照中序法遍历此二叉树，得到如下的表达式：EFBGCHIJDA。2. 前序遍历法 前序遍历法的递归定义为： 若二叉树为空，则退出，否则：（1） 访问根结点； （2）遍历左子树； （3）遍历右子树； （4）返回。 图3.2是一棵二叉树，按照前序法遍历此二叉树，得到如下的表达式： ABEFCGDHIJ。 3. 后序遍历法 后序遍历法的递归定义为： 若二叉树为空，则退出，否则： （1） 遍历左子树 （2） 遍历右子树 （3）访问根结点 （4） 返回图3.2是一棵二叉树，按照后序法遍历此二叉树，得到如下的表达FEGJIHDCBA。 3.2.2 树和森林的周游 可以按深度优先方式，也可以按广度优先方式周游树和森林。 按深度优先方式有两种主要的周游次序。 1. 先根次序周游： 访问第一棵树的根，按先根次序周游第一棵树的子树，按先根次序周游其他的树。 2. 后根次序周游： 按后根次序周游第一棵树的子树，访问第一棵树的根，按先根次序周游其他的树。 图3.1是一棵树，按先根次序周游，结点排列的次序是ABEFCGDHIJ。按后根次序周游，结点排列的次序是EFBGCHIJDA。 值得一提的是图3.2的二叉树是图3.1的树转换过来的，对树的先根次序周游正好等同于对对应的二叉树的前序法周游；对树的后根次序周游正好等同于对对应的二叉树的中序法周游。3.3树、二叉树的存储1二叉树的Rlink-Llink表示法二叉树采用链式存储方法来存储，二叉树结点三个域：Info信息域，Llink存放左子女的指针，Rlink存放右子女的指针，二叉树这种表示方法称为Rlink-Llink表示法,树的存储可以转换成对二叉树的存储。2线索二叉树有N个节点的二叉树，共有2N个指针域，其中N-1个指针域利用上了，但还有N+1个指针域没有利用上，把这样的指针域利用起来，用以存放指向该结点前驱或后继的指针。设每个指针域有一个特征位tag,左指针域特征位为Ltag,右指针域的特征位为Rtag当Ltag=0，表示指向它的左子女。Ltag=1，表示指向它的前驱。当Rtag=0，表示指向它的右子女。Rtag=1，表示指向它的后继。3完全二叉树的顺序存储由于完全二叉树结构上的特点，通常采用顺序方式存储。首先把完全二叉树的所有结点按照从上到下，从左到右的次序，从1到n编号，得到一个线性序列，把此线性序列按顺序方式存储，即用一个一维数组来存储。完全二叉树的运算是周游：顺次访问向量中的各个数据元素，即从上到下，从左到右周游一棵完全二叉树。知道某一结点的编号i,可以知道其双亲及左右子女的编号。双亲编号 i/2 左子女 2i (2i=n,i=n/2,否则无左子女。)右子女 2i+1 (2i+1=n,idata)； IF ( p-rlink!=nil) top=top+1; stop=p-rlink; p=p-llink; IF( top！= -1) p=stop; top=top+1; while(p！=nil)|(top！ = -1) 3.4二叉树前序遍历非递归调用子程序 void order(struct node *t) struct node *p； struct node *smax; int top; top=-1; p=t;do WHILE (p!=nil) top=top+1; stop=p； p=p-llink; IF( top！= -1) p=stop; top=top+1;printf(“%d”,p-data)； p=p-rlink; while(p！=nil)|(top！ = -1) 3.5 树结构的应用树结构有着广泛的应用。树结构可以表示通信及数据传送中的二进制编码，还可用于信息检索和排序。3.5.1 二叉排序树定义 如果一棵二叉排序树的每个结点对应于一个码值，整个二叉树各个结点对应的码值组成一个码值集合，此码值集合中各个元素在二叉树中是按一定次序排列的，则称此二叉树为二叉排序树。其中的次序是这样的：规定二叉排序树里每个结点的左子树中结点的码值都小于该结点的码值，而右子树中结点的码值都大于此结点的码值。 按下列原则建立一棵二叉排序树。 (1)令R1是二叉树的根 (2)若R2data=x) f=1;else if(xdata) p=p-llink; else p=p-rlink; if(f) q=p; else q=nil; return(q);3.5.3 在二叉排序树中插人结点(1)在二叉排序树中插入结点例子如图3.3，在二叉排序树中插入值为243和614两个结点。插人的结点一定为二叉排序树的叶结点。（2）给出二叉排序树中插入一个值为x的新结点的算法 二叉排序树中的插入结点的算法 在二叉排序树中插入一个节点算法void insertree(struct node *tree, int x ) struct node *p,*q; if(tree=nil) p= (struct node *)malloc(sizeof(struct node); p-data=x; p-rlink=nil; p-llink=nil; tree=p; else p=tree; while(p!=nil) q=p; if (xdata) p=p-llink; else p=p-rlink; p=(struct node *)malloc(sizeof(struct node);p-data=x; p-rlink=nil; p-llink=nil;if (xdata) q-llink=p;else q-rlink=p; 3.5.3 在二叉排序树中删除结点 在二叉排序树中删除结点是指删除指定的结点，而不是把以这个结点为根的子树都删掉，删除结点后还要保持二叉树的性质。 设p为被删除结点，f为p的双亲结点。 (1)被删除的结点没有左右孩子，则可直接删去p； (2)被删除的结点p没有左子树，则可用右子树根结点s取代结点p的位置；(3)被删除的结点没有右子树则可用左子树的根结点取代结点的位置；(4)被删除结点P有左右子树，则要找出右子树中码值最小的结点s，用s取代p，如图3.4。二叉排序树结点p的删除算法void detree(struct node *t, struct node *f, struct node *p) struct node *q,*s; int bool; bool=0; if(p-llink=nil)|(p-rlink=nil) if(p-llink=nil) if(p= =t) t=p-rlink;else s=p-rlink; bool=1; else if(p= =t) t=p-llink;else s=p-llink; bool=1; (if) else q=p; s=q-rlink; while(s-llink!=null) q=s; s=s-llink; s-llink=p-llink; if (q!=p) q-llink=s-rlink; s-rlink=p-rlink; if (p=t) t=s; else bool=1; if (bool=1) if(p=f-llink) f-rlink=s; else f-rlink=s; free(p);q=p; s=q-llink; while(s-rlink!=null) q=s; s=s-rlink; s-rlink=p-rlink; if (q!=p) q-rlink=s-llink; s-llink=p-llink; 第二部分 操作系统第一章 绪论 计算机发展到今天，无论是个人计算机，还是巨型计算机系统，毫无例外都配置一种或多种操作系统。1.1 操作系统任何一个计算机系统都有由两部分组成：计算机硬件和计算计算机软件。计算机硬件通常由中央处理机、存储器、输入设备和输出设备等组成，它是计算机系统的物质基础。计算机软件是为了方便用户和充分发挥计算机效率的各种程序及有关的文档的总称，包括汇编程序、解释程序、编译程序、操作系统、诊断程序、数据库管理系统及各种用户应用程序。没有任何软件支持的计算机称为裸机，它仅仅构成了计算机的物质基础，而实际呈现在用户面前的计算机系统是经过若干层软件改造的计算机。如图1.1，裸机在最里层，它的外面是操作系统。图1.1经过操作系统提供的资源管理功能和方便用户的各种服务功能把裸机改造成功能更强、使用更为方便的机器，通常称为虚拟机。1.1.1 操作系统定义 操作系统是控制、管理计算机的软硬件资源，合理的组织计算机工作流程及方便用户的程序集合。1.1.2 操作系统的功能操作系统所具有的功能从三个方面来看。1. 从资源管理角度来看 操作系统是用来控制管理计算机资源的，并调度对系统中各类资源的使用。资源包括软件资源和硬件资源。硬件资源有中央处理机、内存储器、外部设备。软件资源包括系统程序、应用程序和数据文件。操作系统对各种资源的管理如下：(1)处理机管理：对系统中的各台处理机及其状态进行登记、管理各作业(进程)对处理机的要求，并按一策略将系统中的各台处理机分给要求的作业(进程)使用。(2)存储器管理：用合理的数据结构形式记录系统中主存储器的使用情况，并按照一定策略在提出存储请求的各作业之间分配主存空间，保护主存储器中的信息不被其它作业(进程)有意或无意破坏(3)输人输出设备管理：记住系统中各类设备及其状态，按各类设备的特点和不同的策略把设备分给要求的作业使用。许多系统还注意优化设备的调度，以提高设备的利用率。(4)信息管理：操作系统中的信息管理功能主要涉及文件的逻辑组织和物理组织、目录的结构以及对文件的操作，近年来还特别注意对文件中信息的保护和保密措施。2. 从合理组织计算机流程的观点来看操作系统首先看一个例子，设有A、B、C三个程序，Ai、Ac、Ao、Bi、Bc、Bo、Ci、Cc、Co分别表示各程序的输入、计算和输出程序段，则各程序段的执行顺序如图1.2。从例子可以看出各个程序段之间是相互制约的、又是相互推进的。如何组织协调好各程序段之间的执行是操作系统的又一大功能图1.2 3 . 从用户角度来看在计算机发展初期，是没有操作系统的，每当用户使用计算机处理它的作业，首先把用户程序在内存中定位(直接参与内存的分配)，当他所需的内存空间超过内存的容量时，用户的要求得不到满