自个的linux学习步骤-白红宇

自个的linux学习步骤

阅读量：5302 次

发布时间：2019-06-14

本文共 22714 字，大约阅读时间需要 75 分钟。

1、Linux 基础

安装Linux操作系统

Linux文件系统（windows的文件共享）

Linux的基本命令及使用

Linux启动过程详解

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

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

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

Linux基本命令实践

设置Linux环境变量

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

使用Emacs编辑文件

使用其他编辑器

2、Shell 编程基础

Shell简介

认识后台程序

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

熟悉Linux下的各种Shell

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

熟悉Emacs的基本操作

比较不同shell的区别

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

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

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

3、Linux 下的 C 编程基础

linux C语言环境概述 <------------------------------ok

Gcc使用方法 <------------------------------ok

Gdb调试技术 <------------------------------ok

Autoconf

Automake

Makefile <------------------------------ok

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

熟悉Gcc编译器

熟悉Makefile规则编写Hello,World程序<------------------------------ok

使用 make命令编译程序 <------------------------------ok

编写带有一个循环的程序 <------------------------------ok

调试一个有问题的程序 <------------------------------ok

4、嵌入式系统开发基础

嵌入式系统概述

交叉编译

配置TFTP服务

配置NFS服务

下载Bootloader和内核

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

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

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

编译并下载U-boot

编译并下载Linux内核

编译并下载Linux应用程序

嵌入式系统移植

Linux内核代码

平台相关代码分析

ARM平台介绍

平台移植的关键技术

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

能够移植Linux内核移植Linux2.6内核到 ARM9开发板

【1 配置编译Linux内核

1.1 Linux内核源代码结构

1.2 Linux内核编译选项解析

1.3 Linux内核编译链接

2.0 Linux启动过程源代码分析

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

5、嵌入式 Linux 下串口通信

串行I/O的基本概念

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

Linux系统的文件和设备

与文件相关的系统调用

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

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

编写多串口通信程序

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

Linux系统进程概述

嵌入式系统的进程特点

进程操作 <------------------------------ok

守护进程

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

能够编写多进程程序编写多进程程序 <------------------------------ok

编写一个守护进程程序

sleep系统调用任务管理、同步与通信 Linux任务概述 <------------------------------ok

任务调度

管道

信号 <------------------------------ok

共享内存

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

熟悉进程间通信的几种方式 <------------------------------ok

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

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

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

【主要包括系统编程(信号/系统调用/管道/FIFO/消息队列/共享内存等)，文件I/O编程(文件描述符/文件读写接口/原子操作/阻塞与非阻塞IO等，多任务和多线程编程(进程标识/ 用户标识/fork与vfork/多线程概念/线程同步等)，网络编程(网络基本概念/套接口编程/网络字节次序/Client/Server结构/UDP编程)；掌握Linux下Socket编程的开发流程，熟悉网络编程的调用接口函数和相关数据结构，<------------------------------ok

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

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

线程的基础知识

多线程编程方法

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

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

8、嵌入式 Linux 网络编程

网络基础知识

嵌入式Linux中TCP/IP网络结构

socket 编程

常用 API函数

分析Ping命令的实现

基本UDP套接口编程

许可证管理

PPP协议

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

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

熟悉UDP协议、PPP协议

熟悉GPRS 使用socket 编写代理服务器

使用socket 编写路由器

编写许可证服务器

指出TCP和UDP的优缺点

编写一个web服务器

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

9、GUI 程序开发

GUI基础

嵌入式系统GUI类型

编译QT

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

能够进行QT编程使用QT编写“Hello，World”程序

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

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

10、Linux 字符设备驱动程序

设备驱动程序基础知识

Linux系统的模块

字符设备驱动分析

fs_operation结构

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

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

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

编写键盘驱动

编写I/O驱动

分析一个看门狗驱动程序

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

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

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

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

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

编写MMC卡驱动程序

分析一个文件系统

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

11、文件系统

虚拟文件系统

文件系统的建立

ramfs内存文件系统

proc文件系统

devfs 文件系统

MTD技术简介

MTD块设备初始化

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

了解嵌入式Linux的文件系统

了解MTD技术

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

移植JFFS2文件系统

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

分析romfs 文件系统源代码

创建一个cramfs 文件系统

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

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

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

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

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

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

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

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

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

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

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

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

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

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

耐心，刻苦，尝试，失败。

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

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

What How Why

2 Linux C语言

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

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

函数

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

函数的类型和返回值

函数的参数传递

函数调用过程中的栈帧结构

可变参数列表

递归函数调用

3学时指针

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

判断指针的类型

指针的运算

数组和指针的同异

指向函数的指针

指针与抽象

3学时预编译

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

对象宏和函数宏

宏定义技巧和常见错误

#和##运算符

条件编译

文件包含

3学时字符串

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

C风格字符串

标准C字符串库函数一览

重点函数实现解析

C字符串处理范例

3学时链接

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

链接和elf文件格式概述

程序的存储映像

链接脚本和嵌入式程序的存储

3学时文件IO

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

流和IO重定向

文本文件与二进制文件

用标准C库进行文件操作

标准C和系统调用

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

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

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

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

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

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

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

2、C

　　C语言考查的重点一般是：指针、结构体、条件编译、全局变量/局部变量。以下是我遇

见过的面试问题：

1）请说一下extern C的作用（汉略）

2）请说一下#ifdef...的作用（汉略）

3）C语言里，哪些变量是存放在堆里，哪些是存放在栈里？（普天）

4）C语言里的static关键词是什么含义？（普天）

5）进程和线程有什么区别？（普天）

3、C++

　　C++语言考查的重点主要有：多继承，抽象类，虚函数，拷贝构造函数，析构函数，动

态联编，多态，const，static。以下是我面试中遇到的问题：

1）你听说过拷贝构造函数吗？能具体说一下它的作用吗？（汉略）

2）析构函数必须是虚函数吗？为什么？（汉略）

3）你听说过钻石结构吗？请具体说一下（aspenTech）

4）什么是深拷贝？什么是浅拷贝？他们有什么区别？(aspenTech)

5）什么是虚函数，什么是纯虚函数？为什么引入虚函数和纯虚函数？（汉略，aspenTech，

普天）

6）请说一下面向对象的基本特性。（aspenTech）

7）C++中的const关键定代表什么含义？跟C语言中的const有什么区别？(aspenTech)

8）C++中的static关键定代表什么含义？跟C语言、Java中的static有什么区别？（普天）

4、数据结构

　　这是面试中几乎必考的部分。考查的重点有：链表，二叉树前序、中序、后序遍历（递

归，非递归），二叉树结点、层次的计算，树转二叉树，各种排序算法（冒泡排序，快速排

序，堆排序是重点）。以下是我在面试中遇到过的问题：

1）请编写程序，将一个链表倒置。（联发）

2）请编写二叉树的中序遍历非递归算法。（新华社）

3）请编写一个程序，实现将树转化成二叉树。（华为）

4）一棵满二叉树有x个结点，请问整棵二叉树有多少结点？（新华社，中国信保）

5）请编程实现一个堆排序算法/快速排序算法。（汉略）

5、数据库

　　这也是面试重点内容。主要考查点有：范式，1、2、3范式，事务，内连接，外连接，

关系代数，数据库设计。以下是我遇到过的面试问题：

1）什么是范式、1范式、2范式、3范式？（百度，中航信，新华社，中国信保）

2）事务具有哪些特性？（中航信）

3）请说说什么是外连接、左外连接、右外连接？（aspenTech）

4）请说说关系代表中的几种基本运算？（中航信）

5）请对一个论坛进行数据库设计，并说说你设计的数据库满足哪个范式（百度）

6）给你一个数据库需求，请对数据库进行设计，并根据要求写出查询语句（中国信保）

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地址范围；

工程技术部：192.168.161.1－62 掩码：255.255.255.192

市场部：192.168.161.65－126 255.255.255.192

财务部：192.168.161.129－190 255.255.255.192

办公室：192.168.161.193－254 255.255.255.192

子网划分是网络基础，我不知道你熟悉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，换成二进制为11111111.11111111.11111111.00000000，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）

这四个了网的网络ID分别为：192.168.161.0，192.168.161.64，192.168.161.128，192.168.1.192

所以，每个子网的62个主机IP分别就是我给出的答案。这是最详细的回答，还不懂就没办法了。

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

各种排序算法（插入排序、冒泡排序、选择排序，快速排序，堆排序，归并排序）

线性表(一般的线性表,栈,队列)的插入和删除

二叉树的遍历（前序，中序，后序）

图的遍历（深度优先，广度优先）

二分法查找，排序二叉树，Hash查找（处理冲突的方法）。

常用的几种算法：

1. 列举法：

列举法的基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验那些是需要的，哪些是不需要的。列举法常用于解决“是否存在”或“有多少可能”等类型的问题。

在设计列举法时，只要对实际问题进行详细的分析，将于问题有关的知识条理化、完备化、系统化，从中找出规律；或对所有可能的情况进行分类，引用出一些有用的信息，是可以大大减少列举量的。

2. 归纳法：

通过列举少量的特殊情况，经过分析，最后找出一般的关系。

从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。

最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察得到的猜测得不到证实或最后证明猜测是错误的，也是常有的事。

3. 递推：

递推是指从已知的条件出发，逐次推出所要求的各中间结果和最后结果。

递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的。递推关系式往往是归纳的结果。

注意：对于数值型的递推算法必须注意数值计算的稳定性问题

4. 递归：

人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归纳出一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程进行综合，这种就是递归的基本思想。递归的基础也是归纳。

递归分为直接递归和间接递归。

如果一个算法P显式的调用自己称为直接递归

如果一个算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归。

递推与递归的区别：

递推是从初始条件出发，逐次推出所需求的结果；而递归是从算法本身到达递归的边界。通常递归算法要比递推算法清晰易读，其结构比较简练。特别在许多比较复杂的问题中，很难着到从初始条件推出所需结果的全过程，此时，设计递归算法要比递推算法容易的多。但递归算法的执行效率比较低。

5. 减半递推技术：

分治法法就是对问题分而治之。工程上常用的是减半递推技术。所谓减半是将问题的规模减半，而问题的性质不变；所谓递推是指重复减半的过程。

6. 回溯法：

通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步退回，换别的路线在进行试探。这种方法称为回溯法。

算法的复杂度

算法的复杂度主要包括时间复杂度和空间复杂度。

? 算法的时间复杂度

时间复杂度是指执行算法所需要的计算工作量。

基本运算反映了算法的主要特征。用基本运算的次数来度量算法工作量是客观的也是实际可行的。有利于比较同一问题的几种算法的优劣。

算法所执行的基本运算次数还与问题的规模有关。

算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数

即：算法的工作量=f（n）其中n是问题的规模。

算法执行所需的基本运算次数取决与某一特定输入时，可以用以下两种方法来分析算法的工作量：

1) 平均性态（Average Behavior）

平均性态是指用各种输入下的基本运算次数的加权平均值来度量算法的工作量。

2) 最坏情况复杂性（Worst – Case Complexity）

最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。

? 算法的空间复杂度

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间，输入的初始数据所占用的存储空间，以及算法执行过程中所需要的额外空间。

额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。

如果额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的。

数据结构的基本概念

利用计算机进行数据处理是计算机应用的一个重要领域。

? 数据结构的定义：

数据处理是指数据集合中的各元素以各种方式进行运算，包括插入，删除，查找，更改等运算，也包括对数据元素进行分析。

数据结构是指相互有关联的数据元素的集合。

在数据处理领域中，每个需要处理的对象都可以抽象成数据元素。数据元素一般简称为元素

在数据领域处理中，通常把数据元素之间这种固有的关系简单的用前后件关系（或直接前驱与直接后继的关系）来描述。

前后关系数据元素之间的一个基本关系，但前后件所表示的实际意义随具体对象的不同而不同。

一般来说，数据元素之间的任何关系都可以用前后件来描述。

1) 数据的逻辑结构

数据结构是指反映数据元素之间关系的数据元素集合的表示。即数据结构是指带有结构的数据元素的集合。

结构实际上就是指数据元素之间的前后件关系。

数据结构应包含以下两方面的信息：

1) 表示数据元素的信息。

2) 表示各数据元素之间的前后件关系。

数据之间的前后件关系是指他们的逻辑关系，而与他们在计算机中的存储位置无关。

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。

数据的逻辑结构有两个要素：

1) 数据元素的集合，通常记为D；

2) 是D上的关系，它反映了D中各数据之间的前后件关系，通常记为R

即一个数据结构可以表示为：B=(D,R)

B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。

2) 数据的存储结构

在实际进行数据处理时，被处理的各元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置关系与他们的逻辑关系不一定是相同的。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。

常用的数据存储结构有顺序、链接、索引等存储结构。

? 数据结构的图形表示

在数据结构的图形表示中，对数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称为数据结点，简称结点。

没有前件的结点称为根结点，没有后件的结点称为终端结点。（也称为叶子结点）。

根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除运算）。对数据结构的运算还有查找、分类、合并、分解、复制和修改等。

? 线性结构与非线性结构

如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在一个空的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构。

根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。

如果一个非空的数据结构满足下列两个条件：

1. 有且只有一个根结点；

2. 每个结点最多有一个前件，也最多只有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。

在一个线性结构中插入或删除任何一个结点还应是线性结构。如果在此数据结构中插入或删除任何一个结点后就不满足上面的两个条件了，则该数据不能称为线性结构。

如果数据结构不是线性结构，则称为非线性结构。

线性结构和非线性结构都可以是空的数据结构。

线性表及其顺序存储结构

? 线性表的基本概念

线性表是由一组数据元素构成。数据元素的含义很广泛，在不同的具体情况下，它可以有不同的含义。

线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。

非空的线性表有如下一些特征：

1. 有且只有一个根结点。它无前件。

2. 有且只有有关终端结点，它无后件。

3. 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中的结点个数称为线性表的长度。

? 线性表的顺序存储结构

在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。

线性表的顺序存储结构具有以下两个特点：

1. 线性表中的所有元素所占的存储空间是连续的；

2. 线性表中个数据元素在存储空间中是按逻辑顺序依次存放的。

在线性表的顺序储存结构中，其前后件两个元素在存储空间中是紧邻的，且有前件的元素一定存储在后件元素的前面。

顺序存储结构中，线性表中的每一个数据元素在计算机存储空间中的存储地址由该元素所在线性表中的位置序号唯一确定。

在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。

在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有以下几种：

1. 在线性表的指定位置处加入一个新的元素（即线性表的插入）；

2. 在线性表中删除指定的元素（即线性表的删除）；

3. 在线性表中查找某个（或某些）特定的元素（即线性表的查找）；

4. 对线性表中的元素进行整序（即线性表的排序）

5. 按要求将一个线性表分解成多个线性表（即线性表的分解）

6. 按要求将多个线性表合并成一个线性表（即线性表的合并）

7. 复制一个线性表（即线性表的复制）

8. 逆转一个线性表（即线性表的逆转）

顺序表的插入和删除运算

在线性表采用顺序结构时，如果插入在线性表的末尾进行，则只要在表的末尾增加一个元素即可，不需要移动表中的元素；如果要在表中的第一个元素之前插入一个新元素，则需要移动表中所有的元素。在一般情况下，如果插入的运算在第i（1<i<n）个元素之前进行，则原来i之后（包括第i个元素）的所有元素都必须移动。

在线性表顺序存储的情况下，要插入一个新元素，或删除一个元素，其效率是很低的，由于数据元素的移动而消耗较多的处理时间。

栈和队列

? 栈及其基本运算

1. 什么是栈

栈实际上也是线性表，只不过是一种特殊的线性表。

在顺序存储结构下，对这类型线性表的插入和删除运算是不需要移动表中的其他元素的。这种线性表称为栈

栈是限定在一端进行插入与删除的线性表。

在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈低。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是被先插入的元素，从而也是最后才能被删除的元素。即栈是按照：先进后出，后进先出的原则组织数据的。栈具有记忆作用。

往栈中插入一个元素称为入栈运算，从栈中删除一个元素（删除栈顶元素）称为退栈运算。

2. 栈的顺序存储及其运算

栈底指针指向栈空间的低地址一端（即数组的起始地址这一端）

栈的基本运算有三种：入栈，退栈，读栈顶元素

1. 入栈运算

入栈运算是指在栈顶位置插入一个新元素。操作方法：首先将栈顶指针进一，然后将新元素插入到栈顶指针指向的位置。

2. 退栈运算

退栈运算是指取出栈顶元素并赋给一个指定的变量。操作方法：首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针退一。

3. 读栈顶元素

读栈顶元素是指将栈顶元素赋给一个指定的变量。注意：这个运算不删除栈顶元素，只是将它的值赋给一个变量，在这个运算中，栈顶指针不会改变。

? 队列及其基本运算

1. 什么是队列

在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：

a) 初始时线性表为空

b) 当有用户程序到来时，将该用户程序加入到线性表的末尾进行等待；

c) 当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。

在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（或删除）元素，这种线性表称为队列。

队列是指允许在一端进行插入，而另一端进行删除的线性表。

允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；

允许删除的一端称为排头（也称为队头），通常也用一个排头指针（front）指向排头元素的前一个位置。

在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。

队列又称为：先进先出或后进后出的线性表。

往队列队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。

在程序设计语言中，一般用一维数组作为队列的顺序存储空间。

2. 循环队列及其运算

队列的顺序存储结构一般采用循环队列的形式。

所谓循环队列，就是将循环队列的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列使用。

在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

循环队列主要有两种基本运算：入队运算和退队运算

每进行一次入队运算，队尾指针就进一。每进行一次退队运算，排头指针就进一。

? 入队运算

入队运算是指在循环队列的队尾加入一个新元素。

操作方法：首先将队尾指针进一，然后将新元素插入到队尾指针指向的位置。

? 退队运算

退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。

操作方法：首先将排头指针进一，然后将排头指针指向的元素赋给指定的变量。

线性链表

假设数据结构中的每一个数据结点对应一个存储单元，这种存储单元称为存储结点，简称结点。

在链式存储方式中，要求每个结点有两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该节点的前一个或后一个结点（即前件或后件）。

? 线性链表

线性表的链式存储结构称为线性链表。

一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（即存储结点的地址）即指向后件结点，称为指针域。

在线性链表中，用一个专门的指针指向线性链表中第一个数据元素的结点（即存放线性链表中第一个数据元素的数据结点的序号）。线性链表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空，表示链表终止。

在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间的位置关系与逻辑关系也不一致。在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的。指向线性表中第一个结点的指针称为头指针。

对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。

在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用于指向前件结点；另一个称为右指针，用于指向其后件结点。

? 带链的栈和带链的队列

栈和队列也是线性表，也可以采用链式存储结构。

线性链表的基本运算

? 在线性链表中查找指定的元素

在线性链表中寻找包含元素值的前一个结点。当找到包含指定元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。

在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下：

从头指针的指向结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，有这种方法找到的结点p有两种可能：当线性链表存在包含元素x的结点时，则找到的p为第一次遇到包含x的前一个结点的序号；当线性链表中不包含x的结点时，则找到的结点为线性链表中的最后一个结点号。

1. 线性链表的插入

线性链表的插入是指在链式存储下的线性表中插入一个新元素。

为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值。新结点可以从可利用的栈中取得。然后将存放新元素的值的结点链接到线性链表中指定的位置。

要在线性链表中包含元素x的结点之前插入一个新元素b。其插入过程如下：

a) 从可利用的栈中取得一个结点，设该结点号为p（即取得结点的存储序号存放在变量p中），并将结点p的数据域为插入的元素值b。

b) 在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。

c) 最后讲结点p插入到结点q之后。为实现这一步，只要改变以下两个结点的指针域内容：

i. 使结点p指向包含元素x的结点（即结点q的后件结点）

ii. 使结点q的指针域内容该为指向结点p

2. 线性链表的删除

线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。

为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除的结点放回到可利用的栈中。

要在线性链表中删除包含元素x的结点，其删除过程如下：

a) 在线性链表中寻找包含元素x的前一个结点，设该结点序号为q。

b) 将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元素x的结点p的指针指向的结点。

c) 将包含元素x的结点p送回可利用的栈。

循环链表及其运算

循环链表与线性链表相比，具有以下两个特点：

1. 在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。

2. 循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。

由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表至少有一个结点存在，从而使空表与非空表的运算统一。

循环链表的插入与删除的方法与线性链表基本相同。

树的基本概念

树是一种简单的非线性结构。在树这种数据结构中，所有元素之间的关系具有明显的层次特性。

在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。每个结点可以有多个后件，他们都称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件个数称为该结点的度。所有结点中最大的度称为树的度。

树的最大层次称为树的深度。在树中，叶子结点没有子树。

用树来表示算数表达式的原则如下：

1) 表达式中的每一个运算符在树中对应一个结点，称为运算符结点。

2) 运算符的每个对象在树中为该运算符结点的子树（从树中的顺序为从左到右）。

3) 运算中的单变量均为叶子结点。

表示表达式的树通常称为表达式树。

树在计算机中通常用多重链表表示。多重链表的每个结点描述了树中对应结点的信息，而每个结点中的链域（即指针域）个数将随树中该结点的度而定。

二叉树及其基本性质

1. 二叉树定义

二叉树也是非线性结构。树结构的所有术语都可以用到二叉树这种数据结构上。

二叉树具有以下两特点：

1) 非空二叉树只有一个根结点；

2) 每个结点最多有两个子树，且分别称为该结点的左子树和右子树。

在二叉树中一个结点可以只有左子树而没有右子树，也没有只有右子树而没有左子树。当一个结点即没有左子树也没有右子树时，该结点即是叶子结点。

2. 二叉树的基本性质

二叉树具有以下几个性质：

1) 在二叉树的k层上，最多有2k-1（k≥1）

2) 深度为m的二叉树最多有2m-1个结点。深度为m的二叉树是指二叉树有m层。

3) 在任意二叉树中，度为0的结点（即子叶结点）总比度为2的结点多一个。

4) 具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。

3. 满二叉树与完全二叉树

1) 满二叉树

满二叉树是指：除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中每一层上的结点都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。

2) 完全二叉树

完全二叉树是指：除最后一层外，每层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

对于完全二叉树来说，叶子结点只可能在层次最大两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则左分支下的子孙结点最大层次或为p或为p+1。

满二叉树也是完全二叉树，完全二叉树不是满二叉树。

设完全二叉树共有n个结点。如果从根结点开始，按层序（每层从左到右）用自然数1、2、…、n给结点进行编号，则对于编号为k(k=1、2、… n)的结点有以下结论：

a) 若k=1则该结点为根结点，它没有父结点；若k>1，则该结点的父结点为INT（k/2）。

b) 若2k≤n，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点（也没有右子结点）。

c) 若2k+1≤n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。

完全二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。

用于存储二叉树中的个元素的存储结点是由两部分组成：数据域与指针域。在二叉树中，由于每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个；一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。

二叉树的链式存储结构也称为二叉链表。

对于满二叉树和完全二叉树来说，可以按层序进行顺序存储，但顺序存储结构对于一般的二叉树不适用。

二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有结点。

在遍历二叉树的过程中，一般先遍历左子树，然后在遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可分为三种：前序遍历，中序遍历，后序遍历。

1. 前序遍历

前序遍历是指在访问根结点，遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历二叉树的过程是一个递归过程。

2. 中序遍历

中序遍历是指：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左，右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历二叉树也是一个递归的过程。

3. 后序遍历

后序遍历是指：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左，右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。后序遍历二叉树也是一个递归的过程。

查找技术

所谓查找是指在一个给定的数据结构中查找某个指定的元素。

1. 顺序查找

顺序查找又称为顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：

从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到（即查找成功）；若线性表中的所有元素与被查找元素进行了比较但都不相等，则表示线性表中没有要查找的元素（即查找失败）。

顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：

a) 如果线性表是无序表（即表中的元素排列是无序的），则不管是顺序存储结构海是链式存储结构，都只能用数序查找。

b) 即使是有序性表，如果采用链式存储结构，也只能用顺序存储结构。

2. 二分查找

二分法查找只适用顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，允许相邻元素值相等）。

设有序线性表的长度为n，被差元素为x，则对分查找的方法如下：

将x与线性表的中间项进行比较：

若中间项的值等于x，则说明查找到，查找结束；

若x的值小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；

若x的值大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。

这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。

排序技术

排序技术是指将无序序列整理成按值非递减顺序排列的有序序列。

? 交换类排序法

交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序和快速排序都属于交换类排序法。

1. 冒泡排序法

它是通过相邻元素的交换逐步将线性表变成有序。

冒泡排序法的基本过程如下：

首先，从表头开始往后扫描线性表，在扫描的过程中逐次比较相邻两个元素的大小。若两个元素中，前面的元素大于后面的元素，则将它们互换，称之为削除了一个逆序。然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较两个相邻元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换。对于剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已变为有序。

2. 快速排序法

快速排序法的基本思想如下：

从线性表中选取一个元素，设为T，将线性表后面小于体的元素移到前面，而前面大于他的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分隔。对分隔后的各子表在按上述原则进行分隔，直到所有子表为空为止。

对于线性表或子表进行实际分隔，可以按如下步骤进行：

首先，在表的第一个，中间一个与最后一个元素中选取中项，设为P(k)，并将P(k)赋给T，再将表中的第一个元素移到P(k)位置上。

然后设置两个指针i和j分别指向表的起始与最后位置。反复操作以下两步：

1) 将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)<T为止，将P(j)移到P(i)的位置上。

2) 将i逐渐增大，并逐次比较P(i)与T，直到发现一个P(i)>T为止，将P(i)移到P(j)的位置上。

上述两个操作交替进行，直到指针i与j指向同一个位置（即i=j）为止，此时将T移到P(i)的位置上。

? 插入类排序法

1. 简单插入排序法

插入排序法是指将无序序列的各元素依次插入到有序的线性表中。

简单插入排序法的基本思想是：

在线性表中，只包含第一个元素的子表显然可以看成是有序表。从线性表的第二个元素开始直到最后一个元素，逐次将其中的每个元素插入到前面有序的子表中。

假设线性表中前j-1个元素已经有序，现在将线性表中的第j个元素插入到前面有序的子表中，实际插入过程如下：

首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T插入到刚移出的空位置上，有序子表的长度就变为j了。

2. 希尔排序法(Shell Sort)

希尔排序法的基本思想是：

将整个无序序列分割成若干小的子序列分别进行插入。

? 选择类排序法

1. 简单选择排序法

选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表为空为止。

2. 堆排序法

结构化分析方法

? 关于结构化分析方法

结构化分析就是使用数据流程图（DFD）、数据字典（DD），结构化英语、判定表和判定树等工具，来建立一种新的，称为结构化规格说明的目标文档。

结构化分析方法的实质是着眼于数据流，自顶向下，逐层分析，建立系统的处理流程。以数据流程图和数据字典为主要工具，建立系统的逻辑模型。

结构化分析的步骤如下：

1) 通过对用户的调查，以软件需求为线索，获得当前系统的具体模型；

2) 去掉具体模型中非本质因素，抽象出当前系统的逻辑模型；

3) 根据计算机的特点分析当前系统与目标系统的差别，建立目标系统的逻辑模型；

4) 完善目标系统并补充细节，写出目标系统的软件需求规格说明；

5) 评审直到确认完全符合用户对软件的需求。

? 结构化分析的常用工具

1. 数据流程图

数据流程图是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模。

建立数据流程图的步骤如下：

1) 有外向里：先画系统的输入和输出，然后画系统内部。

2) 自顶向下：顺序完成顶层、中间层、底层数据流图。

3) 逐层分解。

为保证构造的数据流程图表达完整、准确、规范、应遵循以下数据流程图的构造规则和注意事项：

a) 对加工处理建立唯一，层次性的编号，且每个加工处理通常要求既有输出有有输入；

b) 数据存储之间不应该有数据流；

c) 数据流图的一致性。它包括数据守恒和数据文件的使用，即某个处理用于产生输出的数据没有输入，即出现遗漏，另一种是一个处理的某些输入并没有在处理中使用以产生输出；数据存储（文件）应被数据流程图中的处理读和写，而不是仅读不写或仅写不读；

d) 父图、子图关系与平衡规则。子图代表了父图中某个加工的详细描述，父图表示子图间的接口。子图个数不大于父图中的处理个数。所有子图的输入，输出数据流和父图相应处理的输入，输出数据流必须一致。

2. 数据字典

数据字典是对所有与系统相关的数据元素的一个有组织的列表，以及精确的，严格定义的，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有同的理解。

在数据字典编制过程中，常使用定义方式描述数据结构。下面给出了常用的定义式符号：

= 表示等于，定义为，由什么构成。

[…|…] 表示或，即选择括号中用 | 号分隔的各项中的某一项。

+ 表示与，和。

n{}m 表示重复，即括号中的项要重复若干次，n，m是重复次数的上下限。

（…）表示可选，即括号中的项可以没有。

* * 表示注释

.. 连接符

3. 判定树

使用判定树进行描述时，应先从问题定义的文字描述中分清那些是判定条件，那些是判定结论，根据描述材料中的连接词找出判断条件的从属关系，并列关系，选择关系，根据它们构造判定树。

4. 判定表

软件设计的基本概念

? 软件设计的基础

软件设计是软件工程的重要阶段，是把软件需求转换为软件表示的过程。

软件设计的基本目标是用比较抽象的概括方式确定目标系统如何完成预订的任务，即软件设计是确定系统的物理模型。

从技术观点来看，软件设计包括结构设计，数据设计，接口设计，过程设计。

结构设计是定义软件系统各主要部件之间的关系；

数据设计是将分析时创造的模型转化为数据结构的定义；

接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信；

过程设计是把系统结构部件转换成软件的过程性描述。

从工程管理角度来看，软件设计分为两步完成：概要设计和详细设计。

概要设计（又称结构设计）将软件需求转化为软件体系结构，确定系统级接口、全局数据结构或数据库模式；

详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。

软件设计的一般过程是：先进行高层次的结构设计；后进行低层次的过程设计；穿插进行数据设计和接口设计。

? 软件设计的基本原理

1. 抽象

抽象是一种思维工具，就是把事物的本质特性提取出来而不考虑其他细节。

2. 模块化

模块是指把一个待开发的软件分解成若干小的简单部分。

模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。

3. 信息屏蔽

信息屏蔽是指在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。

4. 模块独立性

模块独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。

? 结构还设计方法

结构化设计方法的基本思想是将软件设计成相对独立、单一功能的模块组成的结构。

概要设计

? 概要设计的任务

软件概要设计的基本任务是：

1. 设计软件系统结构

在需求分析阶段，已经把系统分解成层次结构，而在概要设计阶段，需要进一步分解划分为模块以及模块的层次结构。划分的具体步骤是：

1) 采用某种设计方法，将一个复杂的系统按功能划分成模块。

2) 确定每个模块的功能。

3) 确定模块之间的调用关系。

4) 确定模块之间的接口，即模块之间传递的信息。

5) 评价模块之间的质量。

2. 数据结构即数据库设计

数据设计是实现需求定义和规格说明过程中提出的数据对象的逻辑表示

数据设计的具体任务是：

确定输入、输出文件的详细数据结构；结合算法设计，确定算法所必须的逻辑数据结构及其操作；确定对逻辑数据结构所必需的那些操作的程序模块，限制和确定各个数据设计决策的影响范围；需要与操作系统或调度程序接口所必需的控制表进行数据交换时，确定其详细的数据结构和使用规则；数据的保护性设计：防卫性、一致性、沉余性设计。

数据设计中应注意掌握以下设计原则：

1) 用于功能和行为的系统分析原则也应用与数据。

2) 应该标识所有的数据结构以及其上的操作。

3) 应当建立数据字典，并用于数据设计和程序设计。

4) 底层的设计决策应该推迟到设计过程的后期。

5) 只有那些需要直接使用数据结构、内部结构的模块才能看到该数据的表示。

6) 应该开发一个由有用的数据结构和应用与其上的操作组成的库。

7) 软件设计和程序设计语言应该支持抽象数据类型的规格说明和事项。

3. 编写概要设计文档

4. 概要设计文档评审

? 面向数据流的设计方法

面向数据流的设计方法定义了一些不同的映射方法，利用这些映射方法可以把数据流图变换成结构图表示的软件结构。