软件基础串讲一

1、计算机软件基础重点知识串讲1第一章 概 述1.1 计算机软件的定义1.2 程序设计语言1.3 操作系统1.4 应用软件21.1 计算机软件的定义1、计算机系统 计算机系统是接收、处理和提供数据的装置，它由硬件和软件两大部分组成。 硬件是组成计算机系统的所有电子的、机械的、磁性的、光学的装置和部件。 5大部件： (运算器控制器)存储器输入设备输出设备32、计算机软件软件程序，开发软件写程序？错误！程序只是软件的一个组成部分写程序只是软件开发的过程中的一个步骤软件是程序、数据以及有关文档资料的集合。（可运行的）思想和内容的数字化思想：算法、规律、办法（程序）内容：图形、图像、数据、声音、文字等（数

2、据）4计算机软件的定义 计算机软件就是指计算机程序、实现此程序功能所采用的方法、规则以及与其相关联的文档和在机器上运行它所需要的数据。53、硬件与软件的关系硬件是计算机系统的物质基础；软件是提高计算机系统效率和方便用户使用计算机的程序；它们二者相互依赖、相互促进、共同发展。好的软件能充分发挥硬件的性能，提升计算机的价值。没有软件的硬件是僵尸，没有硬件的软件是幽灵。 各类软件技术的最终目的就是设计出好的软件，以便最大限度地合理利用和发挥硬件的能力，使计算机系统更好地为用户服务。61.2 程序设计语言程序:是使计算机完成某种任务的一个有序的命令（指令语句）和数据的集合。 程序设计语言发展的三个阶段

3、：机器语言汇编语言高级语言写程序就像写文章，要解决两个问题：1.明确自己要表达的是什么2.用一种语言把它表达出来程序设计语言是编写计算机程序所用的语言。7机器语言 是机器指令的集合，其代码由0、1组成的二进制串表示，不需翻译可直接为机器所接受。 汇编语言 为符号化的机器语言。它用助记符和标识符代替机器指令的操作码和地址码。面向机器的语言。高级语言 是一种与具体的计算机指令系统无关，独立于计算机类型，而且表达方式接近于自然语言或数学语言，容易被人们掌握和书写的语言。如C，Pascal，java。 面向问题的语言。8语言处理程序翻译程序 是把甲种语言程序翻译为等价的乙种语言程序的程序。其中，甲种语

4、言称为源语言。乙种语言称为目标语言。汇编程序 若源语言是汇编语言，目标语言是机器语言，则该翻译程序被称为汇编程序。编译程序 若源语言是高级语言，目标语言是汇编语言或机器语言，则该翻译程序被称为编译程序。解释程序 是翻译程序的另一种形式，它对源程序的语句边解释边执行，不产生目标程序。91.3 操作系统没有安装任何软件的计算机称为裸机。操作系统是直接运行于裸机之上的系统软件，它负责对计算机系统的各种软硬件资源进行管理和分配，为用户提供友好的计算机使用界面和平台。在裸机上配置操作系统之后就构成了操作系统虚拟机。所有其它的程序都在扩充后的机器上运行。10应用程序用户程序操作系统虚拟机操作系统裸 机11

5、软件的分类所有的硬件都是相似的，软件则各有各的不同。但是软件的开发过程存在很多规律和共性，找到并利用这些规律来帮助和指导软件的开发，这正是各类软件技术研究的内容。操作系统 、语言编译器、数据库管理系统财务软件、文字处理软件、用户自己开发的系统等硬 件系统软件应用软件用 户12第二章 数据结构程序中往往要处理大量的数据，这些数据采用什么样的方式来组织、存放才能最大限度地方便应用处理，提高程序效率？数据结构研究数据的组织形式，包括数据的逻辑结构，物理结构以及在该数据结构上所施加的运算。一类数据结构指的是一类数学模型。数据结构是软件技术的基础。132.1 数据结构的基本概念1、基本概念的识记与领会数

6、据：是描述客观事物的数、字符以及所有能输入到计算机中被计算机程序加工处理的信息的集合。数据元素：数据元素是数据的基本单位。是数据集合中的个体。（一个数据项或多个数据项（域）构成）在程序处理中作为一个整体考虑，也称为结点、记录。数据项：数据项是数据的最小单位。数据结构：是指相互有关联的数据元素的集合。描述数据元素之间存在的相互关系的方法称为结构。 14一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后继关系（或直接前趋与直接后继关系）来描述。15（1

7、）数据的逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。即从逻辑结构上描述数据，独立于计算机。如P9表2-1两大类 线性结构：一对一关系。重点：线性表 非线性结构：多对多关系。重点：树结构 16（2）数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后继关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后继关系的信息。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结

8、构，常用的存储结构有顺序、链式、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。17线性表的结构及运算1、 线性表概念线性表（line list）是最简单、最常用的一种数据结构。线性表是怎样一种逻辑结构 线性表是由n(n 0)个数据元素a1, a2, a3, 组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后继。即线性表或是一个空表，或可以表示为(a1, a2, ai, an)，其中ai(i = 1, 2, , n)是属于数据对象的元素，通常也称其为线性表中的一个结点。显然

9、，线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。182、线性表的顺序存储 线性表按顺序存储称为顺序表。顺序存储特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间（字节数）相等，线性表中查找某一个元素是很方便的。 假设线性表中的第一个数据元素的存储地址为ADR，一个数据元素占k个字节，则线性表中第i个元素在计算机存储空间中的存储地址为： ADR +(i1)k 即：存储地址由该元素在线性表中的位置序号唯一确定。因此，

10、顺序存储适宜随机存取。193、顺序表上的运算主要的运算有以下几种：1）顺序表中插入运算 在长度为n的线性表中插入一个结点x，其插入过程如下： 首先从最后一个元素开始直到第i个元素，将其中的每一个元素均依次往后移动一个位置，然后将新元素x插入到第i个位置。插入一个新元素后，线性表的长度变成了n+1，202）顺序表删除运算 一个长度为n的线性表顺序存储在长度为maxsize的存储空间中。现在要求删除线性表中的第i个元素。其删除过程如下： 从第i个元素开始直到最后一个元素，将其中的每一个元素均依次往前移动一个位置。此时，线性表的长度变成了n1，214、线性表的链式存储 在一般情况下，要在顺序存储的线

11、性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。在平均情况下，为了在顺序存储的线性表中插入或删除一个元素，需要移动线性表中约一半的元素；在最坏情况下，则需要移动线性表中所有的元素。因此，对于大的线性表，特别是元素的插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率都很低。 22链式存储结构特点： 存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。即把逻辑上相连的元素用指针连接。线性表的链式存储称为链表。有单链

12、表、双链表、循环链表。（1）链表的存储 在线性链表中，各数据元素之间的前后继关系是由各结点的指针域来指示的，指向线性表中第一个结点的指针head称为头指针，当head = NULL（或0）时称为空表。对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。23单链表。每个结点只有一个指针域，由这个指针只能找到后继结点，但不能找到前趋结点。双向链表。每个结点设置两个指针，一个称为左指针（Llink），用以指向其前趋结点；另一个称为右指针（Rlink），用以指向其后继结点。24链表运算 1）单链表的插入线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。为了要在线性链表中插入

13、一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值。然后将存放新元素值的结点链接到线性链表中指定的位置。在p指针后插入新结点，其插入过程如图。线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可， 252）线性链表的删除在线性链表中删除包含元素x的结点，其删除过程如下： 在线性链表中寻找包含元素x的结点。 将其直接前趋节点的指针改为指向其直接后继结点。 将结点r送回存储池。线性链表的删除运算完成。26（3）循环链表在单链表中，只有从头结点出发才能找到链表中的其他结点，当把最后一个结点的链域指向头结点，构成一个环，称为循环链表。在循环链表中，只要指出表中任何一个

14、结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。另外，由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在。 27栈、队 列和数组 1什么是栈 栈是一种特殊的线性表。 栈（stack）是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”的原则组织数据的。 282栈的顺序存储及其运算 栈的基本运算有3种：入栈、退栈与读栈顶元素。下面分别介绍

15、在顺序存储结构下栈的这3种运算。 (a) 有6个元素的栈 (b) 插入X和Y后的栈 (c) 退出一个元素的栈1）入栈运算 入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进1（即top+1），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。292）退栈运算 退栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针退1（即 top1）。当栈顶指针为0时，说明栈空，不可能进行退栈操作。这种

16、情况称为栈“下溢”错误。303、队列 队列（queue）是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为队头。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”（first in first out，FIFO）的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针rear与排头指针front共同反映了队列中元素动态变化的情况。 6个元素的队列示意图31在队列的末尾插入一个元素（入队运算

17、）只涉及队尾指针rear的变化，而要删除队列中的排头元素（退队运算）只涉及排头指针front的变化。（a）一个队列 （b）删除一个元素后的队列 （c）插入一个元素后的队列324循环队列及其运算 所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，队列循环使用，如图所示。 在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。33循环队列的初始状态为空，即rear=front=m循环队列主要有两种基本运算：入队运算和退队运算。 1）入队运算 入队运算是指在循环队列的队尾加入一个

18、新元素。这个运算有两个基本操作：首先将队尾指针加1（即rear + 1），然后将新元素插入到队尾指针指向的位置。当循环队列非空且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，该情况称为“上溢”。 2）退队运算 退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。这个运算有两个基本操作：首先将队头指针进一（即front = front + 1）；然后将排头指针指向的元素赋给指定的变量。当循环队列为空时，不能进行退队运算，这种情况称为“下溢”。34 (a) 循环队列 (b) 加入X、Y的循环队列 (c) 退出一个元素的循环队列355、数组数组一般用顺序存储的方式表示。存储的方式有： 行优先顺序，也就是把数组逐行依次排列。列优先顺序，就是把数组逐列依次排列。地址的计算方法： 按行优先顺序