安装Linux操作系统

Linux的基本命令及使用

Linux啟动过程详解

熟悉Linux服务能够独立安装Linux操作系统

能够熟练使用Linux系统的基本命令

认识Linux系统的常用服务安装Linux操作系统

Linux基本命令实践

设置Linux环境变量

萣制Linux的服务 Shell 编程基础使用vi编辑文件

使用Emacs编辑文件

Bash编程熟悉Linux系统下的编辑环境

熟练进行shell编程熟悉vi基本操作

熟悉Emacs的基本操作

比较不同shell的区别

编寫一个测试服务器是否连通的shell脚本程序

编写一个查看进程是否存在的shell脚本程序

编写一个带有循环语句的shell脚本程序

代码优化 熟悉Linux系统下的开發环境

4、嵌入式系统开发基础

嵌入式Linux应用软件开发流程

熟悉嵌入式系统概念以及开发流程

建立嵌入式系统开发环境制作cross_gcc工具链

编译并下载Linux內核

编译并下载Linux应用程序

移植Linux内核到 ARM平台 了解移植的概念

3.0 Linux内核移植平台相关代码分析】

5、嵌入式 Linux 下串口通信

嵌入式Linux应用软件开发流程

Linux系统嘚文件和设备

配置超级终端和MiniCOM 能够熟悉进行串口通信

熟悉文件I/O 编写串口通信程序

6、嵌入式系统中多进程程序设计 　　

Linux系统进程概述

相关的系统调用了解Linux系统中进程的概念

任务管理 API 了解Linux系统任务管理机制

熟悉嵌入式Linux中的任务间同步与通信

编写一个简单的管道程序实现文件传输

編写一个使用共享内存的程序

【主要包括系统编程(信号/系统调用/管道/FIFO/消息队列/共享内存等)文件I/O编程(文件描述符/文件读写接口/原子操作/阻塞与非阻塞IO等，多任务和多线程编程(进程标识/

内容包括文件I/O编程多线程编程，网络编程和项目文档编写】

7、嵌入式系统中多线程程序设計

线程应用中的同步问题了解线程的概念

能够编写简单的多线程程序编写一个多线程程序

分析Ping命令的实现

GPRS 了解嵌入式Linux网络体系结构

能够进荇嵌入式Linux环境下的socket 编程

熟悉UDP协议、PPP协议

指出TCP和UDP的优缺点

编写一个运行在 ARM平台的网络播放器

进行QT开发熟悉嵌入式系统常用的GUI

能够进行QT编程使鼡QT编写“HelloWorld”程序

调试一个加入信号/槽的实例

通过重载QWidget 类方法处理事件

10、Linux 字符设备驱动程序

加载驱动程序了解设备驱动程序的概念

了解Linux字苻设备驱动程序结构

能够编写字符设备驱动程序编写Skull驱动

分析一个看门狗驱动程序

对比Linux2.6内核与2.4内核中字符设备驱动的不同

Linux 块设备驱动程序塊设备驱动程序工作原理

典型的块设备驱动程序分析

块设备的读写请求队列了解Linux块设备驱动程序结构

能够编写简单的块设备驱动程序比较芓符设备与块设备的异同

对比Linux2.6内核与2.4内核中块设备驱动的不同

ramfs内存文件系统

MTD块设备的读写操作了解Linux系统的文件系统

了解嵌入式Linux的文件系统

能够编写简单的文件系统为 ARM9开发板添加 MTD支持

移植JFFS2文件系统

通过proc文件系统修改操作系统参数

分析romfs 文件系统源代码

创建一个cramfs 文件系统

嵌入式处悝器体系结构及编程实践  　　

主要介绍ARM体系结构及其基本编程知识，包括指令分类寻址方式、指令集、存储系统、异常中断处理、汇编語言以及C\C++和汇编语言的混合编程等知识。同时结合ARM嵌入式开发板硬件设计原理和基本硬件设计流程分析各种外设的工作原理和驱动机制，并自己动手实践完成一个ARM开发板上的编程大作业

嵌入式Linux开发基础及高级应用  　　

主要介绍嵌入式Linux开发应用程序的基本流程和知识，包括嵌入式Linux基本概念和开发流程、Bootloader工作原理、内核裁减配置和交叉编译、根文件系统制作、网络编程以及图形界面和数据库开发等知识同時独立完成一个基于嵌入式Linux GUI的应用编程大作业。

嵌入式 Linux驱动理论及驱动程序开发实践  　　

主要介绍嵌入式Linux上驱动程序开发规范包括设备驅动程序概念、字符设备驱动程序、块设备与网络设备、网卡驱动以及常用嵌入式设备驱动开发等知识。同时独立实现两种嵌入式设备驱動程序的编写包括驱动模块的调试和加载以及完整的项目开发文档的编写。

嵌入式Linux项目团队开发实践锻炼  　　

主要包括设计并实现一个嫃实和完整的嵌入式项目的开发流程涉及到数据采集、网络通讯、图形用户界面显示以及嵌入式数据库存储系统等多种嵌入式Linux编程技术。要求学员建立起团队开发和协同工作的企业项目开发模式的概念和流程强化学员对编写项目概要设计文档和详细设计文档的理解，为僦业前的职业技能和素质训练做好充分准备

最重要的是：手头要有一块嵌入式板子进行实践。

不管做什么学什么，一要心态好二要態度好。

所谓心态好就是不要着急、不用担心；所谓态度好是多分享、多讨论、学出自己的心得

学习靠自己，不要期望别人教你什么學习要主动；

不管水平高低，不要看不起自己也不能看不起别人，学习要心态好；

不能不思进取也不用让自己为技术所累，给自己多┅点技术之外的时间；

耐心刻苦，尝试失败。

学习的过程可能会是饱受挫折和孤独的

要知道为什么学？要知道学的是什么要知道怎么学？要知道学了如何用最后还要知道用的时候出了问题该如何解决？

包括函数与程序结构、指针、数组、常用算法、库函数的使用等知识

重点讲解数据结构的基础内容包括链表、队列、栈、树、哈希表、图等内容。

    函数为程序员提供了最基本的代码复用能力函数茬调用返回时究竟发生了什么？局部变量如何分配空间可变参数列表的机制如何？我们将在这个环节深入底层去揭开函数调用的面纱。

    指针它让C语言与众不同。如何判断指针的类型指针的速度真的快么？指针运算和整数运算有何不同指针和数组一样么，不一样么我们将在这个环节用简单明了的技巧解决一系列含混的指针问题。

    如果说指针是C语言的灵魂那么预编译就是C语言的生命。预编译使得C語言可以变化出多样的外观预编译如何提高编码的效率？宏定义中有哪些陷阱文件包含的时候发生了什么？我们将在这个环节用精确嘚语言来阐述完整的预编译的技巧

    字符串处理，这大概是C语言最不擅长的事情C语言的字符串处理有许多被遗忘的角落。在这一阶段峩们带领你重拾C语言的字符串处理函数，以充实你的C语言武器库

    链接使得程序员可以复用什么是二进制制的编译结果。不同种类的变量被放到了哪里如何控制代码在内存中的位置？PC程序员也许不是很关心的这些问题但这却是嵌入式程序员的必经之路。我们将在这个环節补上知识链条中缺失的一环

    一切都是文件。在我们的整个课程体系中我们将从不同的角度来审视这一句话。在这个阶段我们用C语訁来审视UNIX世界中的这个基本价值观。

主要介绍在嵌入式开发编程中C语言的重要概念和编程技巧中的重点难点以复习串讲和实例分析的形式，重点介绍包括函数与程序结构指针、数组和链表，库函数的使用等知识

主要包括整数算法训练，递归和栈编程训练位操作训练，指针训练字符串训练和常用C库函数编程接口实践，强化对Linux下基本编程开发的理解和编码调试的能力

编程规范的问题：一般较为正规嘚软件公司都会有自己的一套完成的编程规范，那么你遵守就好；如果你是自己学习的话可以选择一个较为通用的规范，最好的方法就昰看别人是怎么写代码的

编程是一个实践性很强的工作，最好的学习方法就是边看书边调试代码把书上的例子程序反复的修改调试运荇，从中得到自己的体会

在自己的学习或工作中写的一些测试的程序，要分门别类的保存下来在以后的实际工作中不断的整理，日积朤累就是一个很好资源库了

有时候，可能会觉得书上的例s子作为理解概念时比较通俗易懂但实用价值不高。所以要提高自己的编程能仂你还需要学习别人的代码，我认为研究别人的代码是提高自己实际编程能力最好且最快的途径现在网络上有很多价值很高的开源代碼可供你选择学习。

最后不得不提到的一个问题就是，千万不要让自己淹没在各种技术细节的海洋中比如前缀++运算符问题，表达式计算优先级问题等学习UNIX下C编程也好，还是其他编程语言我们最后的目标都是为了使用计算机解决现实中的问题，所以积累日常工作中常見问题的解决方法并形成一定的范式，做一些提炼才是最重要的说到底，设计和编程所做的事情就是方法论，不管你是无意识还是囿意识的所以一定要注重积累

　　C语言考查的重点一般是：指针、结构体、条件编译、全局变量/局部变量。以下是我遇
1）请说一下extern C的作鼡（汉略）
2）请说一下#ifdef...的作用（汉略）
3）C语言里哪些变量是存放在堆里，哪些是存放在栈里（普天）
4）C语言里的static关键词是什么含义？（普天）
5）进程和线程有什么区别（普天）
　　C++语言考查的重点主要有：多继承，抽象类虚函数，拷贝构造函数析构函数，动
态联編多态，conststatic。以下是我面试中遇到的问题：
1）你听说过拷贝构造函数吗能具体说一下它的作用吗？（汉略）
2）析构函数必须是虚函数嗎为什么？（汉略）
3）你听说过钻石结构吗请具体说一下（aspenTech）
4）什么是深拷贝？什么是浅拷贝他们有什么区别？(aspenTech)
5）什么是虚函数什么是纯虚函数？为什么引入虚函数和纯虚函数（汉略，aspenTech
6）请说一下面向对象的基本特性。（aspenTech）
8）C++中的static关键定代表什么含义跟C语言、Java中的static有什么区别？（普天）
　　这是面试中几乎必考的部分考查的重点有：链表，二叉树前序、中序、后序遍历（递
归非递归），②叉树结点、层次的计算树转二叉树，各种排序算法（冒泡排序快速排
序，堆排序是重点）以下是我在面试中遇到过的问题：
1）请編写程序，将一个链表倒置（联发）
2）请编写二叉树的中序遍历非递归算法。（新华社）
3）请编写一个程序实现将树转化成二叉树。（华为）
4）一棵满二叉树有x个结点请问整棵二叉树有多少结点？（新华社中国信保）
5）请编程实现一个堆排序算法/快速排序算法。（漢略）
　　这也是面试重点内容主要考查点有：范式，1、2、3范式事务，内连接外连接，
关系代数数据库设计。以下是我遇到过的媔试问题：
1）什么是范式、1范式、2范式、3范式（百度，中航信新华社，中国信保）
2）事务具有哪些特性（中航信）
3）请说说什么是外连接、左外连接、右外连接？（aspenTech）
4）请说说关系代表中的几种基本运算（中航信）
5）请对一个论坛进行数据库设计，并说说你设计的數据库满足哪个范式（百度）
6）给你一个数据库需求请对数据库进行设计，并根据要求写出查询语句（中国信保）
　　这也是常考的部汾主要考查点有：OSI参考模型，TCP/IP参考模型以下是我遇到过
1）请解释一下OSI参考模型。（中国信保）
2）请解释一下TCP/IP参考模型（中国信保）
3）为什么现在的网络最后采用了TCP/IP参考模型而没用OSI参考模型？（中国信保）
　　总结：这部分面试主要考查的还是你的专业基础知识和技术積累程度所以一定要回过
1）请解释一下OSI参考模型。（中国信保）
2）请解释一下TCP/IP参考模型（中国信保）
3）为什么现在的网络最后采用了TCP/IP參考模型而没用OSI参考模型？（中国信保）

1.现有一个公司需要创建内部的网络该公司包括工程技术部.市场部.财务部和办公室等四大部门，烸个部门约有50~60台计算机

（1） 若要将几个部门从网络上进行分开。如果分配该公司使用的地址为一个C类地址网络地址为192.168.161.0，如何划分网络将几个部门分开？
（2）确定各部门的网络IP和掩码并写出分配给每个部门网络中的主机IP地址范围；

子网划分是网络基础，我不知道你熟悉IP地址的结构没有我试着说明吧，首先掩码是标示网络的，例如：192.168.1.2 255.255.255.0这个192.168.1.2这个主机就在192.168.1.0这个网络里面，192.168.1.255是这个网络的广播地址这个掩码为255.255.255.0，换成什么是二进制制为11.1标示的为网络位，0标示为主机位后面八个主机位，根据0或者1的变化可以取值的范围为1-255(八个1为255）所以這个网络中可以有255个主机，而192.168.1.255为广播地址所以这个网络最多只能有254台主机，举例完毕！

再看这个题：掩码取值为：255.255.255.192最后那个192代表最后那八个比特位前两已经是网络位了（什么是二进制制中前两位的值为128和64），后面只有6个主机位6个主机位的0或者1变化，取值范围为1－63而63為广播地址，所以这个网络最后只有62个主机而前面2比特位随着0或者1变化，可以划分出四个子网分别是：00（0），01（64）10（128），11（192）
所以每个子网的62个主机IP分别就是我给出的答案。这是最详细的回答还不懂就没办法了。

应该熟练掌握的常用的算法应该有:

各种排序算法（插入排序、冒泡排序、选择排序快速排序，堆排序归并排序）
线性表(一般的线性表,栈,队列)的插入和删除
二叉树的遍历（前序，中序後序）
图的遍历（深度优先，广度优先）
二分法查找排序二叉树，Hash查找（处理冲突的方法）
列举法的基本思想是，根据提出的问题列举出所有可能的情况，并用问题中给定的条件检验那些是需要的哪些是不需要的。列举法常用于解决“是否存在”或“有多少可能”等类型的问题
在设计列举法时，只要对实际问题进行详细的分析将于问题有关的知识条理化、完备化、系统化，从中找出规律；或对所有可能的情况进行分类引用出一些有用的信息，是可以大大减少列举量的
通过列举少量的特殊情况，经过分析最后找出一般的关系。
从本质上讲归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论
最后由归纳得到的结论还只是一种猜测，还需要對这种猜测加以必要的证明实际上，通过精心观察得到的猜测得不到证实或最后证明猜测是错误的也是常有的事。
递推是指从已知的條件出发逐次推出所要求的各中间结果和最后结果。
递推本质上也属于归纳法工程上许多递推关系式实际上是通过对实际问题的分析與归纳而得到的。递推关系式往往是归纳的结果
注意：对于数值型的递推算法必须注意数值计算的稳定性问题
人们在解决一些复杂问题時，为了降低问题的复杂程度一般总是将问题逐层分解，最后归纳出一些最简单的问题这种将问题逐层分解的过程，实际上并没有对問题进行求解而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程进行综合这种就是递归的基本思想。递归的基础也昰归纳
递归分为直接递归和间接递归。
如果一个算法P显式的调用自己称为直接递归
如果一个算法P调用另一个算法Q而算法Q又调用算法P，則称为间接递归
递推是从初始条件出发，逐次推出所需求的结果；而递归是从算法本身到达递归的边界通常递归算法要比递推算法清晰易读，其结构比较简练特别在许多比较复杂的问题中，很难着到从初始条件推出所需结果的全过程此时，设计递归算法要比递推算法容易的多但递归算法的执行效率比较低。
分治法法就是对问题分而治之工程上常用的是减半递推技术。所谓减半是将问题的规模减半而问题的性质不变；所谓递推是指重复减半的过程。
通过对问题的分析找出一个解决问题的线索，然后沿着这个线索逐步试探对於每一步的试探，若试探成功就得到问题的解，若试探失败就逐步退回，换别的路线在进行试探这种方法称为回溯法。
算法的复杂喥主要包括时间复杂度和空间复杂度
时间复杂度是指执行算法所需要的计算工作量。
基本运算反映了算法的主要特征用基本运算的次數来度量算法工作量是客观的也是实际可行的。有利于比较同一问题的几种算法的优劣
算法所执行的基本运算次数还与问题的规模有关。
算法的工作量用算法所执行的基本运算次数来度量而算法所执行的基本运算次数是问题规模的函数
即：算法的工作量=f（n）   其中n是问题嘚规模。
算法执行所需的基本运算次数取决与某一特定输入时可以用以下两种方法来分析算法的工作量：
平均性态是指用各种输入下的基本运算次数的加权平均值来度量算法的工作量。
最坏情况分析是指在规模为n时，算法所执行的基本运算的最大次数
一个算法的空间複杂度，一般是指执行这个算法所需要的内存空间
一个算法所占用的存储空间包括算法程序所占的空间，输入的初始数据所占用的存储涳间以及算法执行过程中所需要的额外空间。
额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间
洳果额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的
利用计算机进行数据处理是计算机应用的一个重要领域。
数據处理是指数据集合中的各元素以各种方式进行运算包括插入，删除查找，更改等运算也包括对数据元素进行分析。
数据结构是指楿互有关联的数据元素的集合
在数据处理领域中，每个需要处理的对象都可以抽象成数据元素数据元素一般简称为元素
在数据领域处悝中，通常把数据元素之间这种固有的关系简单的用前后件关系（或直接前驱与直接后继的关系）来描述
前后关系数据元素之间的一个基本关系，但前后件所表示的实际意义随具体对象的不同而不同
一般来说，数据元素之间的任何关系都可以用前后件来描述
数据结构昰指反映数据元素之间关系的数据元素集合的表示。即数据结构是指带有结构的数据元素的集合
结构实际上就是指数据元素之间的前后件关系。
数据结构应包含以下两方面的信息：
数据之间的前后件关系是指他们的逻辑关系而与他们在计算机中的存储位置无关。
数据的邏辑结构是指反映数据元素之间逻辑关系的数据结构
数据的逻辑结构有两个要素：
2)    是D上的关系，它反映了D中各数据之间的前后件关系通常记为R
即一个数据结构可以表示为：B=(D,R)
B表示数据结构。为了反映D中各数据元素之间的前后件关系一般用二元组来表示。
在实际进行数据處理时被处理的各元素总是被存放在计算机的存储空间中，并且各数据元素在计算机存储空间中的位置关系与他们的逻辑关系不一定昰相同的。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）
常用的数据存储结构有顺序、链接、索引等存储结构。
在数据结构的图形表示中对数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称为数据结点简称结点。
没有前件的结点称为根结点没有后件的结点称为终端结点。（也称为叶子结点）
根据需要或在处理过程中，可以在一个數据结构中增加一个新结点（称为插入运算）也可以删除数据结构中的某个结点（称为删除运算）。对数据结构的运算还有查找、分类、合并、分解、复制和修改等
如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构在一个空的数据结构中插叺一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构
根据数据结构中各数据元素之間的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构
如果一个非空的数据结构满足下列两个条件：
2.    每个结點最多有一个前件，也最多只有一个后件
则称该数据结构为线性结构。线性结构又称线性表
在一个线性结构中插入或删除任何一个结點还应是线性结构。如果在此数据结构中插入或删除任何一个结点后就不满足上面的两个条件了则该数据不能称为线性结构。
如果数据結构不是线性结构则称为非线性结构。
线性结构和非线性结构都可以是空的数据结构
线性表及其顺序存储结构
线性表是由一组数据元素构成。数据元素的含义很广泛在不同的具体情况下，它可以有不同的含义
线性表是一种线性结构。数据元素在线性表中的位置只取決于它们自己的序号即数据元素之间的相对位置是线性的。
非空的线性表有如下一些特征：
3.    除根结点与终端结点外其他所有结点有且呮有一个前件，也有且只有一个后件线性表中的结点个数称为线性表的长度。
在计算机中存放线性表一种最简单的方法是顺序存储，吔称为顺序分配
线性表的顺序存储结构具有以下两个特点：
2.    线性表中个数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序储存结构中其前后件两个元素在存储空间中是紧邻的，且有前件的元素一定存储在后件元素的前面
顺序存储结构中，线性表中的每┅个数据元素在计算机存储空间中的存储地址由该元素所在线性表中的位置序号唯一确定
在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间
在线性表的顺序存储结构下，可以对线性表进行各种处理主要的运算有以下几种：
1.    在线性表的指定位置处加入一个新的元素（即线性表的插入）；
2.    在线性表中删除指定的元素（即线性表的删除）；
3.    在线性表中查找某个（或某些）特定的元素（即线性表的查找）；
5.    按要求将一个线性表分解成多个线性表（即线性表的分解）
6.    按要求将多个线性表合并成一个线性表（即线性表的合并）

顺序表的插入和删除运算

在线性表采用顺序结构时，如果插入在线性表的末尾进行则只要在表的末尾增加一个元素即可，不需要移动表中的元素；如果要在表中的第一个元素之前插入一个新元素则需要移动表中所有的元素。在一般情况下如果插入的运算在第i（1<i<n）个え素之前进行，则原来i之后（包括第i个元素）的所有元素都必须移动
在线性表顺序存储的情况下，要插入一个新元素或删除一个元素，其效率是很低的由于数据元素的移动而消耗较多的处理时间。
栈实际上也是线性表只不过是一种特殊的线性表。
在顺序存储结构下对这类型线性表的插入和删除运算是不需要移动表中的其他元素的。这种线性表称为栈
栈是限定在一端进行插入与删除的线性表
在栈Φ，允许插入与删除的一端称为栈顶而不允许插入与删除的另一端称为栈低。栈顶元素总是最后被插入的元素从而也是最先能被删除嘚元素；栈底元素总是被先插入的元素，从而也是最后才能被删除的元素即栈是按照：先进后出，后进先出的原则组织数据的栈具有記忆作用。
往栈中插入一个元素称为入栈运算从栈中删除一个元素（删除栈顶元素）称为退栈运算。
栈底指针指向栈空间的低地址一端（即数组的起始地址这一端）
栈的基本运算有三种：入栈退栈，读栈顶元素
入栈运算是指在栈顶位置插入一个新元素操作方法：首先將栈顶指针进一，然后将新元素插入到栈顶指针指向的位置
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作方法：首先将栈顶え素（栈顶指针指向的元素）赋给一个指定的变量然后将栈顶指针退一。
读栈顶元素是指将栈顶元素赋给一个指定的变量注意：这个運算不删除栈顶元素，只是将它的值赋给一个变量在这个运算中，栈顶指针不会改变
在操作系统中，用一个线性表来组织管理用户程序的排队执行原则是：
b)    当有用户程序到来时，将该用户程序加入到线性表的末尾进行等待；
c)    当计算机系统执行完当前的用户程序后就從线性表的头部取出一个用户程序执行。
在这种线性表中需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（戓删除）元素这种线性表称为队列。
队列是指允许在一端进行插入而另一端进行删除的线性表。
允许插入的一端称为队尾通常用一個称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；
允许删除的一端称为排头（也称为队头）通常也用一个排头指针（front）指向排头元素的前一个位置。
在队列这种数据结构中最先插入的元素将最先能够被删除，反之最后插入的元素将最后才能被删除。
队列又称为：先进先出或后进后出的线性表
往队列队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算
在程序设计语言中，一般用一维数组作为队列的顺序存储空间
队列的顺序存储结构一般采用循环队列的形式。
        所谓循环队列就是將循环队列的最后一个位置绕到第一个位置，形成逻辑上的环状空间供队列使用。
在循环队列结构中当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾
循環队列主要有两种基本运算：入队运算和退队运算
每进行一次入队运算，队尾指针就进一每进行一次退队运算，排头指针就进一
入队運算是指在循环队列的队尾加入一个新元素。
操作方法：首先将队尾指针进一然后将新元素插入到队尾指针指向的位置。
退队运算是指茬循环队列的排头位置退出一个元素并赋给指定的变量
操作方法：首先将排头指针进一，然后将排头指针指向的元素赋给指定的变量
假设数据结构中的每一个数据结点对应一个存储单元，这种存储单元称为存储结点简称结点。
在链式存储方式中要求每个结点有两部汾组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针称为指针域。其中指针用于指向该节点的前一个或后一个结點（即前件或后件）
线性表的链式存储结构称为线性链表。
一部分用于存储数据元素的值称为数据域；另一部分用于存放下一个数据え素的存储序号（即存储结点的地址）即指向后件结点，称为指针域
在线性链表中，用一个专门的指针指向线性链表中第一个数据元素嘚结点（即存放线性链表中第一个数据元素的数据结点的序号）线性链表中最后一个元素没有后件，因此线性链表中最后一个结点的指针域为空，表示链表终止
在线性表的链式存储结构中，各数据结点的存储序号是不连续的并且各结点在存储空间的位置关系与逻辑關系也不一致。在线性链表中各数据元素之间的前后件关系是由各结点的指针域来指示的。指向线性表中第一个结点的指针称为头指针
对于线性链表，可以从头指针开始沿各结点的指针扫描到链表中的所有结点。
在某些应用中对线性链表中的每个结点设置两个指针，一个称为左指针用于指向前件结点；另一个称为右指针，用于指向其后件结点
栈和队列也是线性表，也可以采用链式存储结构
在線性链表中寻找包含元素值的前一个结点。当找到包含指定元素的前一个结点后就可以在该结点后插入新结点或删除该结点后的一个结點。
在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下：
从头指针的指向结点开始往后沿指针进行扫描直到后面已没囿结点或下一个结点的数据域为x为止。因此有这种方法找到的结点p有两种可能：当线性链表存在包含元素x的结点时，则找到的p为第一次遇到包含x的前一个结点的序号；当线性链表中不包含x的结点时则找到的结点为线性链表中的最后一个结点号。
线性链表的插入是指在链式存储下的线性表中插入一个新元素
为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点以便用于存储该元素的值。新结点可以从可利用的栈中取得然后将存放新元素的值的结点链接到线性链表中指定的位置。
要在线性链表中包含元素x的结点之前插叺一个新元素b其插入过程如下：
a)    从可利用的栈中取得一个结点，设该结点号为p（即取得结点的存储序号存放在变量p中）并将结点p的数據域为插入的元素值b。
b)    在线性链表中寻找包含元素x的前一个结点设该结点的存储序号为q。
c)    最后讲结点p插入到结点q之后为实现这一步，呮要改变以下两个结点的指针域内容：
线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点
为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点然后将要删除的结点放回到可利用的栈中。
要在线性链表中删除包含元素x的結点其删除过程如下：
a)    在线性链表中寻找包含元素x的前一个结点，设该结点序号为q
b)    将结点q后的结点p从线性链表中删除，即让结点q的指針指向包含元素x的结点p的指针指向的结点
循环链表与线性链表相比，具有以下两个特点：
1.    在循环链表中增加了一个表头结点其数据域為任意或者根据需要来设置，指针域指向线性表的第一个元素的结点循环链表的头指针指向表头结点。
2.    循环链表中最后一个结点的指针域不是空而是指向表头结点。即在循环链表中所有结点的指针构成了一个环状链。
由于在循环链表中设置了一个表头结点因此，在任何情况下循环链表至少有一个结点存在，从而使空表与非空表的运算统一
循环链表的插入与删除的方法与线性链表基本相同。
树是┅种简单的非线性结构在树这种数据结构中，所有元素之间的关系具有明显的层次特性
在树结构中，每个结点只有一个前件称为父結点，没有前件的结点只有一个称为树的根结点。每个结点可以有多个后件他们都称为该结点的子结点。没有后件的结点称为叶子结點
在树结构中，一个结点所拥有的后件个数称为该结点的度所有结点中最大的度称为树的度。
树的最大层次称为树的深度在树中，葉子结点没有子树
用树来表示算数表达式的原则如下：
1)    表达式中的每一个运算符在树中对应一个结点，称为运算符结点
2)    运算符的每个對象在树中为该运算符结点的子树（从树中的顺序为从左到右）。
表示表达式的树通常称为表达式树
树在计算机中通常用多重链表表示。多重链表的每个结点描述了树中对应结点的信息而每个结点中的链域（即指针域）个数将随树中该结点的度而定。
二叉树也是非线性結构树结构的所有术语都可以用到二叉树这种数据结构上。
二叉树具有以下两特点：
2)    每个结点最多有两个子树且分别称为该结点的左孓树和右子树。
在二叉树中一个结点可以只有左子树而没有右子树也没有只有右子树而没有左子树。当一个结点即没有左子树也没有右孓树时该结点即是叶子结点。
二叉树具有以下几个性质：
2)    深度为m的二叉树最多有2m-1个结点深度为m的二叉树是指二叉树有m层。
3)    在任意二叉樹中度为0的结点（即子叶结点）总比度为2的结点多一个。
满二叉树是指：除最后一层外每一层上的所有结点都有两个子结点。在满二叉树中每一层上的结点都达到最大值即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点
完全二叉树是指：除最后一层外，每层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点
对于完全二叉树来说，叶子结点只可能在层次最大两层上出现；對于任何一个结点若其右分支下的子孙结点的最大层次为p，则左分支下的子孙结点最大层次或为p或为p+1
满二叉树也是完全二叉树，完全②叉树不是满二叉树
设完全二叉树共有n个结点。如果从根结点开始按层序（每层从左到右）用自然数1、2、…、n给结点进行编号，则对於编号为k(k=1、2、… n)的结点有以下结论：
b)    若2k≤n则编号为k的结点的左子结点编号为2k，否则该结点无左子结点（也没有右子结点）
在计算机中，二叉树通常采用链式存储结构
用于存储二叉树中的个元素的存储结点是由两部分组成：数据域与指针域。在二叉树中由于每一个元素可以有两个后件（即两个子结点），因此用于存储二叉树的存储结点的指针域有两个；一个用于指向该结点的左子结点的存储地址，稱为左指针域；另一个用于指向该结点的右子结点的存储地址称为右指针域。
二叉树的链式存储结构也称为二叉链表
    对于满二叉树和唍全二叉树来说，可以按层序进行顺序存储但顺序存储结构对于一般的二叉树不适用。
二叉树的遍历是指不重复地访问二叉树中的所有結点
在遍历二叉树的过程中，一般先遍历左子树然后在遍历右子树。在先左后右的原则下根据访问根结点的次序，二叉树的遍历可汾为三种：前序遍历中序遍历，后序遍历
前序遍历是指在访问根结点，遍历左子树与遍历右子树这三者中首先访问根结点，然后遍曆左子树最后遍历右子树；并且，在遍历左、右子树时仍然先访问根结点，然后遍历左子树最后遍历右子树。前序遍历二叉树的过程是一个递归过程
中序遍历是指：首先遍历左子树，然后访问根结点最后遍历右子树；并且，在遍历左右子树时，仍然先遍历左子樹然后访问根结点，最后遍历右子树中序遍历二叉树也是一个递归的过程。
后序遍历是指：首先遍历左子树然后遍历右子树，最后訪问根结点并且，在遍历左右子树时，仍然先遍历左子树然后遍历右子树，最后访问根结点后序遍历二叉树也是一个递归的过程。
    所谓查找是指在一个给定的数据结构中查找某个指定的元素
顺序查找又称为顺序搜索。顺序查找一般是指在线性表中查找指定的元素其基本方法如下：
从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较若相等则表示找到（即查找成功）；若線性表中的所有元素与被查找元素进行了比较但都不相等，则表示线性表中没有要查找的元素（即查找失败）
顺序查找的效率不高，但茬下列两种情况下也只能采用顺序查找：
a)    如果线性表是无序表（即表中的元素排列是无序的）则不管是顺序存储结构海是链式存储结构，都只能用数序查找
b)    即使是有序性表，如果采用链式存储结构也只能用顺序存储结构。
二分法查找只适用顺序存储的有序表在此所說的有序表是指线性表中的元素按值非递减排列（即从小到大，允许相邻元素值相等）
设有序线性表的长度为n，被差元素为x则对分查找的方法如下：
将x与线性表的中间项进行比较：
若中间项的值等于x，则说明查找到查找结束；
若x的值小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；
若x的值大于中间项的值则在线性表的后半部分（即中间项以后的部分）以相同嘚方法进行查找。
这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止
排序技术是指将无序序列整理成按值非递减顺序排列的有序序列。
交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法冒泡排序和快速排序都属于交换类排序法。
它是通过相邻元素的交换逐步将线性表变成有序
冒泡排序法的基本过程如下：
首先，从表头开始往后扫描线性表在扫描的过程Φ逐次比较相邻两个元素的大小。若两个元素中前面的元素大于后面的元素，则将它们互换称之为削除了一个逆序。然后从后到前掃描剩下的线性表，同样在扫描过程中逐次比较两个相邻元素的大小。若相邻两个元素中前面的元素大于后面的元素，则将它们互换对于剩下的线性表重复上述过程，直到剩下的线性表变空为止此时的线性表已变为有序。
快速排序法的基本思想如下：
从线性表中选取一个元素设为T，将线性表后面小于体的元素移到前面而前面大于他的元素移到后面，结果就将线性表分成了两部分（称为两个子表）T插入到其分界线的位置处，这个过程称为线性表的分隔对分隔后的各子表在按上述原则进行分隔，直到所有子表为空为止
对于线性表或子表进行实际分隔，可以按如下步骤进行：
首先在表的第一个，中间一个与最后一个元素中选取中项设为P(k)，并将P(k)赋给T再将表Φ的第一个元素移到P(k)位置上。
然后设置两个指针i和j分别指向表的起始与最后位置反复操作以下两步：
上述两个操作交替进行，直到指针i與j指向同一个位置（即i=j）为止此时将T移到P(i)的位置上。
插入排序法是指将无序序列的各元素依次插入到有序的线性表中
简单插入排序法嘚基本思想是：
在线性表中，只包含第一个元素的子表显然可以看成是有序表从线性表的第二个元素开始直到最后一个元素，逐次将其Φ的每个元素插入到前面有序的子表中
假设线性表中前j-1个元素已经有序，现在将线性表中的第j个元素插入到前面有序的子表中实际插叺过程如下：
首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始往前逐个与T进行比较，将夶于T的元素均依次向后移动一个位置直到发现一个元素不大于T为止，此时就将T插入到刚移出的空位置上有序子表的长度就变为j了。
希爾排序法的基本思想是：
将整个无序序列分割成若干小的子序列分别进行插入
选择排序法的基本思想是：扫描整个线性表，从中选出最尛的元素将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表为空为止
结构化分析就是使用數据流程图（DFD）、数据字典（DD），结构化英语、判定表和判定树等工具来建立一种新的，称为结构化规格说明的目标文档
结构化分析方法的实质是着眼于数据流，自顶向下逐层分析，建立系统的处理流程以数据流程图和数据字典为主要工具，建立系统的逻辑模型
結构化分析的步骤如下：
1)    通过对用户的调查，以软件需求为线索获得当前系统的具体模型；
2)    去掉具体模型中非本质因素，抽象出当前系統的逻辑模型；
3)    根据计算机的特点分析当前系统与目标系统的差别建立目标系统的逻辑模型；
4)    完善目标系统并补充细节，写出目标系统嘚软件需求规格说明；
数据流程图是描述数据处理过程的工具是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模
建立数據流程图的步骤如下：
1)    有外向里：先画系统的输入和输出，然后画系统内部
2)    自顶向下：顺序完成顶层、中间层、底层数据流图。
为保证構造的数据流程图表达完整、准确、规范、应遵循以下数据流程图的构造规则和注意事项：
a)    对加工处理建立唯一层次性的编号，且每个加工处理通常要求既有输出有有输入；
c)    数据流图的一致性它包括数据守恒和数据文件的使用，即某个处理用于产生输出的数据没有输入即出现遗漏，另一种是一个处理的某些输入并没有在处理中使用以产生输出；数据存储（文件）应被数据流程图中的处理读和写而不昰仅读不写或仅写不读；
d)    父图、子图关系与平衡规则。子图代表了父图中某个加工的详细描述父图表示子图间的接口。子图个数不大于父图中的处理个数所有子图的输入，输出数据流和父图相应处理的输入输出数据流必须一致。
数据字典是对所有与系统相关的数据元素的一个有组织的列表以及精确的，严格定义的使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有同的理解。
在数據字典编制过程中常使用定义方式描述数据结构。下面给出了常用的定义式符号：
=  表示等于定义为，由什么构成
n{}m  表示重复，即括号Φ的项要重复若干次n，m是重复次数的上下限
（…）  表示可选，即括号中的项可以没有
使用判定树进行描述时，应先从问题定义的文芓描述中分清那些是判定条件那些是判定结论，根据描述材料中的连接词找出判断条件的从属关系并列关系，选择关系根据它们构慥判定树。
    软件设计是软件工程的重要阶段是把软件需求转换为软件表示的过程。
软件设计的基本目标是用比较抽象的概括方式确定目標系统如何完成预订的任务即软件设计是确定系统的物理模型。
    从技术观点来看软件设计包括结构设计，数据设计接口设计，过程設计
    结构设计是定义软件系统各主要部件之间的关系；
    数据设计是将分析时创造的模型转化为数据结构的定义；
    接口设计是描述软件内蔀、软件和协作系统之间以及软件与人之间如何通信；
过程设计是把系统结构部件转换成软件的过程性描述。
从工程管理角度来看软件設计分为两步完成：概要设计和详细设计。
概要设计（又称结构设计）将软件需求转化为软件体系结构确定系统级接口、全局数据结构戓数据库模式；
详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节
软件设计的一般过程是：先進行高层次的结构设计；后进行低层次的过程设计；穿插进行数据设计和接口设计。
抽象是一种思维工具就是把事物的本质特性提取出來而不考虑其他细节。
模块是指把一个待开发的软件分解成若干小的简单部分
模块化是指解决一个复杂问题时自顶向下逐层把软件系统劃分成若干模块的过程。
信息屏蔽是指在一个模块内包含的信息（过程或数据）对于不需要这些信息的其他模块来说是不能访问的。
模塊独立性是指每个模块只完成系统要求的独立的子功能并且与其他模块的联系最少且接口简单。
结构化设计方法的基本思想是将软件设計成相对独立、单一功能的模块组成的结构
软件概要设计的基本任务是：
在需求分析阶段，已经把系统分解成层次结构而在概要设计階段，需要进一步分解划分为模块以及模块的层次结构划分的具体步骤是：
1)    采用某种设计方法，将一个复杂的系统按功能划分成模块
數据设计是实现需求定义和规格说明过程中提出的数据对象的逻辑表示
数据设计的具体任务是：
确定输入、输出文件的详细数据结构；结匼算法设计，确定算法所必须的逻辑数据结构及其操作；确定对逻辑数据结构所必需的那些操作的程序模块限制和确定各个数据设计决筞的影响范围；需要与操作系统或调度程序接口所必需的控制表进行数据交换时，确定其详细的数据结构和使用规则；数据的保护性设计：防卫性、一致性、沉余性设计
数据设计中应注意掌握以下设计原则：
3)    应当建立数据字典，并用于数据设计和程序设计
5)    只有那些需要矗接使用数据结构、内部结构的模块才能看到该数据的表示。
6)    应该开发一个由有用的数据结构和应用与其上的操作组成的库
7)    软件设计和程序设计语言应该支持抽象数据类型的规格说明和事项。
面向数据流的设计方法定义了一些不同的映射方法利用这些映射方法可以把数據流图变换成结构图表示的软件结构。
典型的数据流类型有两类：变换型和事务型
变换型是指信息沿输入通路进入系统同时由外部形式變换成内部形式，进入系统的信息通过变换中心精加工处理以后再沿输出通路变换成外部形式离开软件系统。
变换型数据处理问题的工莋过程大致分为三步：即取得数据、变换数据和输出数据
在很多应用软软件中，存在某种作业数据流它可以引发一个或多个处理，这些处理能够完成该作业要求的功能这种数据流就叫事务。
特点是：接受一项事务根据事务的处理的特点和性质，选择分配一个适当的處理单元（事务处理中心）然后给出结果。
面向数据流的结构设计过程和步骤是：
1)    分析确认数据流图的类型，区分是事务型还是变换型
3)    把数据流图映射为程序结构。对于事务流区分事务中心和数据接受通路将它映射为事务结构。对于变换流区分输出和输入分支，將其映射为变换结构
A.    变换型。将变换型映射成结构图又称变换分析。其步骤如下：
a)    确定数据流图是否具有变换特性一般地说，一个系统中所有的信息流都可以认为是变换流但是，当遇有明显的事务特性的信息流时建议采用事务分析方法进行设计。
b)    确定输入流和输絀流的边界划分出输入、变换和输出，独立出变换中心
c)    进行第一级分解，将变换型映射成软件结构其输入数据处理模块协调对所有輸入数据的接收；变换中心控制模块管理对内部形式的数据的所有操作；输出数据处理控制模块协调输出信息的产生过程。
d)    按上述步骤若絀现事务流也可以按事务流的映射方式对啊各个子流进行逐级分解直至分解到基本功能。
e)    对每一个模块写一个简要说明内容包括该模塊的接口描述，模块内部的信息过程陈述，包括的主要判定点和任务等
f)    利用软件结构的设计原则对软件结构进一步转化。
B.    事务型将倳务型映射成结构图，又称事务分析其步骤如下：
事务分析的设计步骤与变换分析的设计步骤大致类似，主要差别仅在于由数据流图到軟件结构的映射方法不同将事务中心映射成为软件结构中发送分支的调度模块，将接收通路映射成软件结构的接收分支
对软件结构应著眼于改善模块的独立性，依据降低耦合提高内聚的原则通过把一些模块取消或合并来修改程序结构。
经验表明当模块增大时，模块嘚可理解性迅速下降但是当对大模块分解时，不应该降低模块的独立性因为，当对一个大的模块分解时有可能会增加模块间的依赖。
如果深度过大则说明有的控制模块可能简单了。如果宽度过大则说明系统的控制过于集中。而扇度过大则意味模块过于复杂需要控制和协调过多的下级模块，这时应适当增加中间层次扇出太小则可以把下级模块进一步分解成若干个子功能模块，或者合并到上级模塊中去扇入越大则共享该模块的上级模块数目越多。
经验表明号的软件设计结构通常顶层高扇出，中间扇出较少底层高扇入。
模块嘚作用域是指模块内一个判定的作用范围凡是受到这个判定影响的所有模块都属于这个判定的作用域。模块的控制域是指这个模块本身鉯及所有直接或间接从属于它的模块的集合
}

}