初级程序员讲座（1）：软件基础知识

　　 在软件专业技术水平考试中，软件基础知识试题所占的比重较大。数据结构、操作系统和数据库系统等知识点始终是考核的重点。考生在复习时应紧扣大纲，把握重点，注意新增
　　的和调整的知识点，如数据库结构化查询语言SQL、操作系统Windows95/98、上网软件、字处理软件Word97的使用和多媒体基本知识。
　　一、基本数据结构:
　　 数据结构基本上是每年必考的知识点。数据结构是指数据和数据之间的联系。数据结构一般包括数据的逻辑结构、存储结构和对数据的基本操作3个方面的概念。
　　 数据的逻辑结构反映的是数据元素之间的逻辑关系，并不依赖于计算机。数据的荐储结构(物理结构)是数据结构在计算机存储器中的表示。对数据的基本操作包括插入、删除、修改、查找和排序等，这些都是各种算法的基础。
　　 数据的基本电位是数据元素(又称结点、记录等)，村个数据元素可有多种偶性，每个脑性就是数据项，即数据元素由一个或多个数据项组成。数据项是数据处理的接小单位。
　　 初级程序员考试涉及的内容主要是:线性表 (包括数组、记录、表、队列和栈)的定义和存储操作。
　　(1)主要知识点:
　　数组、记录的定义、存储和操作
　　 1·数组。数组是一组具有相同类型的变量，其中各个元素共用一个数组名，但用不同的下标来访问(引用)。一维数组描述了一个向量，维数组描述了一个矩阵。数组被存放在一片连续的内存单元中。一维数组从下标为0的元素开始连续荐放。
　　 二维数组有按行优先和按列优先两种行储刀式。绝人多数编程语言，如c语言，郁是按行优先存储的。使用数组在处理一一批同类型数据时极为力便。
　　 2·记录。记录由若干个数据项组成，而各个数据项可具有各自的数据类型。能惟一标识记录的数据项称为主键。每个记录本鼻一般是连续存储的，而各个记录之间应根据需要连续荷储，或采用链式存储。记录的基本操作包括:在己有记录的尾部插入一个新的记录，按指定的主键值查找并读出一个记录，按指定的主键值删除一个记录，按指定的主键值史新一个记录，以及对已存储的记录按主键值的升序或降序进行排列等。
　　线性表、队列和栈的描述和操作
　　I·线性表
　　 线性表是最常用且最简单的一种数据结构，也称为线性结构。一个线性表是n(n≥0)个具有相同属性的数据元素的有限序列，其中的各个数据元素有着依次相邻 (串接)的逻辑关系。当n=0时该线性表称为空表，n>0时该线性表可记为:
　　 {a1 , a2 , a3 … , an }
　　其中，a1称为起点，an称为终点。
　　 线性表的存储结构分为两种:顺序存储结构和链式存储结构。
　　 顺序存储结构就是用一组地址连续的存储单元依次存储该线性表中的各个元素。由于表中各个元素具有相同的属性，所以占用的存储空间相同。因此，在内存中可以通过地址计算直接存取线性表中的任一元素。这种结构的特点是逻辑上相邻的元素物理上也相邻。用顺序结构存储的线性表称作顺序表。
　　 线性表按链式存储时，每个数据元素 (结点)的存储包括数据区和指针区两个部分。数据区存放结点本身的数据，指针区存放其后继元素的地址 (没有后继元素时设置为空字符(Null).。只要知道该线性表的起始地址 (记录在头指针中)，表中的各个元素就可通过其间的链接关系逐步找到，这种链表称为单向链表。对于单向链表有插入和删除等基本操作。
　　 在线性表中查找指定元素通常采用顺序查找法和二分法。顺序查找法是从第一个元素开始，逐个元素地顺序查找，属于线性查找，它比较的次数较多，效率低。二分法查找适合于按键值排序的存储结构。查找时，每次取中间一个元素进行判断，若己找到满足条件的数据，则停止查找，否则需要决定取其前一半还是后一半数据元素继续查找。因此，二分法不是线性查找，效率高一些，但它只适合于己经排序的顺序存储结构，而顺序查找对顺序存储和链式存储均适用。
　　2·队列 (队)
　　 队列是只能在表的一端进行插入，而在另一端进行删除的线性表。它是一种先进先出(FIFO)的线性结构。队列的基本操作包括创建一个队列、入队、出队、读取队首元素、判断队空、清空队列、求出当前队列中的元素个数和撤销一个队列等。
　　 队列的存储结构有顺序存储结构和链式存储结构两种。顺序存储的队列中的各个元素在存储区中连续存储，链式存储的队列中的各个元素独立存储，依靠指针链接建立相邻的逻辑关系。
　　3·栈
　　 栈是一种特殊的线性表，这种表只能在其一端 (称为栈顶为P)进行插入和删除操作，因此栈的存取特征是后进先出(LIFO)。栈的基本操作包括创建一个栈、迸栈 (PuSh)、出栈 (Top)、读取栈顶元素、判断栈空、栈清空 (初始化)、求当前栈中元素的个数和撤销一个栈等。
　　 栈的存储结构也有顺序存储结构和链式存储结构两种。顺序存储的栈中的各个元素在存储区中连续存储;链式存储栈中各个元素独立存储，依靠指针链接建立相邻的逻辑关系。
　　 一个栈的最大数据容量称为栈的深度。当进行进栈操作时，首先判断该栈是否己满，若栈满时，迸栈就会出现溢出(上溢)现象。在进行退栈时，首先要判断栈是不是为空，若为
　　空，那么退栈同样出现溢出(下溢)现象。
　　 在一个程序申需要同时使用具有相同成分类型的两个栈时，为了避免造成存储空间的浪费，多采用双栈进栈操作。其操作方法是:为两个栈共同开辟一个连续的存储空间，让一个栈的栈底为该存储空间的始端，另一个栈的栈底为该存储空间的末端，即将两个栈的栈底安排在这个存储空间的两端，当元素迸栈时都从此存储空间的两端向中间"增长"。这种设计操作将增加内存空间的使用率"这样，只有当这两个栈的栈顶在该存储空间的某处相遇时，才发生上溢现象。
　　

原文转自：http://www.ltesting.net