数据结构
数据结构是描述数据元素及元素间的相互关系。数据结构的概念一般包括三个方面内容:数据之间的逻辑关系、数据在计算机中的存储方式以及在这些数据上定义的运算的集合。
数据的逻辑结构直接称作数据结构,它抽象地反映数据元素间的逻辑关系。数据的逻辑结构有三种基本数据结构:线性表、树和图。这三种基本数据结构又分为线性结构(线性表)和非线性结构(树和图)。
数据的存储结构(亦称为物理结构)是数据的逻辑结构在计算机存储设备中的映象。最常用的二种方式是:顺序存储结构和链接存储结构。大多数据结构的存储表示都采用其中的一种方式,或两种方式的结合。
线性表是最简单的,也是最基本的一种数据结构。栈和队列是两种操作受限的线性表。串也是一种特殊的线性表。
树形结构是一种重要的非线性结构。二叉树是另一种树形结构,二叉树有三种遍历方法,称为先序遍历、中序遍历和后序遍历。二叉树的应用十分广泛,可以用于判定和对策,其中哈夫曼树是一类带权路径长度最短的树。
图是较线性表和树更为复杂的数据结构,同一个图可以有多
种多样的遍历顺序。通常采用的遍历顺序有两种,深度优先搜索和广度优先搜索。它们对有向图和无向图都适用。图的一个重要应用就是求网络的最小生成树。
查找就是在数据结构中找出满足某种条件的数据元素。查找的方法有线性查找和二叉排序树查找等。
排序又称分类,是数据结构中另一种十分重要的运算。其功能就是将一个数据元素的无序序列,按其关键字的大小重新排列,最后变成一个有序序列。
操作系统
操作系统是加在裸机上的第一层软件。它是系统应用程序和用户程序与硬件之间的接口,而且是整个计算机系统的核心,起着控制和管理的中心作用。
根据操作系统提供的服务方式,操作系统可分为批处理系统、分时系统、实时系统、单用户交互系统、网络操作系统及分布式操作系统。
通常,操作系统可被划分为处理机管理、存储器管理、设备管理、文件管理及作业管理五大部分。
处理机管理也称为进程管理。进程管理中重要的问题是处理好进程的同步与互斥,同步是并发进程因相互合作而产生的一种制约关系,互斥是并发进程因共享资源而产生的一种制约关系。 内存管理的基本目的是提高内存利用率以及方便用户使用,它涉及四个基本问题:内存分配、地址映射、内存保护和内存扩充。内存管理有各种方法,有分区管理、分页管理、分段管理和段页式管理等。虚拟存储器是广泛采用的内存扩充技术。
设备管理是操作系统的主要资源管理功能之一,由I/O系统实施,它涉及主机之外的所有外设的管理。设备管理的基本目标是:向用户提供方便的设备使用接口以及充分发挥设备的利用率。
文件管理及作业管理与使用的系统有直接的关系。
软件工程
软件工程是从工程角度来研究软件开发的方法和技术,它是在克服软件危机的过程中产生而发展起来的。软件工程学是自软件工程出现以后形成的一门新兴学科。它包括的主要内容有:软件工程方法学、软件工程环境和软件工程管理等多个分支。
采用工程化的方法和技术开发软件,可以提高软件的可靠性、可维护性、可移植性,其目标是在给定的时间和费用的条件下开发出一个满足用户功能和性能要求的可靠的软件。
一个软件从用户提出开发要求,到废弃不用为止的全过程,称为软件的生存周期。
软件工程采用的生存周期方法学就是从时间角度对软件开发和维护的复杂问题进行分解,将软件的生存周期划分为若干个阶段(如:需求定义、软件设计、编程、测试、运行维护等),每个阶段有相对独立的任务,便于分工协作,使软件开发过程按有秩序能管理的方式组织起来,从而降低软件开发的难度。
第二篇:软件技术基础算法总结
软件技术基础算法总结
第六章图
1、图的遍历
按深度优先遍历图(邻接表)
Void DFS(t) //t为出发点
{if t=null return//如果出发点为空,返回
Print(t); //访问当前节点
Visit[t]=1; //记录访问过当前节点
While(t->visit!=null) //遍历该节点的所有邻接点
{t=t->next //
If (visit[t]!=1) //如果没访问过则深度遍历
{
DFS(t)
}
}
return
}
非递归算法
DFS(T)
标记
入栈
当栈非空
{弹出
访问
邻接点未标记的进栈并标记
}
按广度优先的遍历图(邻接表)
Void BFS(t) //
{入队
标记
如果队非空
{ 出队
访问
将该节点没有访问过的邻接节点入队
}
}
Void BFS(t)
{
If t=null return;
Visit[t]=1;
Getinq(t);
While(!qempty)
{
T=outq;
Vist(t)
While(t!=null)
{
T=t->next
If(visit(t)==0)
{getq(q)
Visti(t)=1
}
}
}
}
2、克鲁斯卡尔方法构造最小代价生成树 Void klsk(t,g,n)
{E(T)=null
For(i=1;i<n;i++)
{找到图中最短边
将最短边在e(g)删除
If(不构成回路)
{
该边添加进E(t)
}
Else i--;
}
3、普莱姆法构造最小代价生成树
{将E(t)=null
U={1}
While(u!=v)
{选出最小边(u,v)u在U中,v在U-V中 E(T)=E(T)U(u,v)
U(T)=UU(u,v)
}
}
4、图的最短路径生成
Floyd
For(k=0;k<n;k++)
{for(0<=i<n)
For(0<=j<n)
{if(a[][]+a[][]<a[][])
{ a[][]=a[][]+a[][];
S[][]=k;
}
}
}
5、DKASLIO
FOR(0<=i<n)
{for(0<=j<n)
V(j)=m[i][j]
While(0<=j<n)
{t=findmin(v)
V(t)=-1
For(0<=l<n)
{
If(re未被找过)
{
是否能更新,能更新则更新 并且修改指示数组 }
}
}
}
6、拓扑排序
Topsort()
{
Stack s
找入度为零对人栈内 For(0<=i<n)
{ 如果非空
弹出并输出
Ptr=k->link
当ptr不为空时
Ptr->count--;
如果为零则压入站内 ptr=->ptr->link
如果空了
就错误
}
}
排序方法总结 简单排序法 选择 插入 冒泡
先进排序法 希尔 快速 其他