数据结构复习笔记
作者: 网络转载发布日期: 无
数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。
数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。
比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。
而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。)
第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。
弄清了以上三个问题，就可以弄清数据结构这个概念。
--------------------------------------------------------------------------------
通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解)
数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。--------------------------------------------------------------------------------
下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。
常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。
时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。
数据结构习题一
--------------------------------------------------------------------------------
1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
◆数据：指能够被计算机识别、存储和加工处理的信息载体。
◆数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。
◆数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
◆数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
◆逻辑结构：指各数据元素之间的逻辑关系。
◆存储结构：就是数据的逻辑结构用计算机语言的实现。
◆线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。
◆非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
--------------------------------------------------------------------------------
1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
◆例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。
那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。(所以各位赶快学C语言吧)。
最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。
--------------------------------------------------------------------------------
1.3 常用的存储表示方法有哪几种?
常用的存储表示方法有四种:
◆顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
◆链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
◆索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
◆散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
--------------------------------------------------------------------------------
1.4 设三个函数f,g,h分别为f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 请判断下列关系是否成立：
(1) f(n)=O(g(n))
(2) g(n)=O(f(n))
(3) h(n)=O(n^1.5)
(4) h(n)=O(nlgn)
◆(1)成立。
◇这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C·f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。第(1)题中两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
◆（2）成立。
◆（3）成立。
◆（4）不成立。
--------------------------------------------------------------------------------
1.5 设有两个算法在同一机器上运行，其执行时间分别为100n^2和2^n,要使前者快于后者，n至少要多大?
◆15
◇最简单最笨的办法就是拿自然数去代呗。假定n取为10，则前者的值是10000，后者的值是1024,小于前者，那我们就加个5，用15代入得前者为22500，后者为32768，已经比前者大但相差不多，那我们再减个1，用14代入得，前者为19600,后者为16384，又比前者小了，所以结果得出来就是n至少要是15.
--------------------------------------------------------------------------------
1.6 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
1.6 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0
while(i { k=k+10*i;i++;
} ◆T(n)=n-1
∴T(n)=O(n)
◇这个函数是按线性阶递增的
(2) i=0; k=0;
do{
k=k+10*i; i++;
}
while(i ◆T(n)=n
∴T(n)=O(n)
◇这也是线性阶递增的
(3) i=1; j=0;
while(i+j<=n)
{
if (i else i++;
} ◆T(n)=n/2
∴T(n)=O(n)
◇虽然时间函数是n/2,但其数量级仍是按线性阶递增的。
(4)x=n; // n>1
while (x>=(y+1)*(y+1))
y++; ◆T(n)=n1/2
∴T(n)=O(n1/2)
◇最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(5) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++; ◆T(n)=O(1)
◇这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。--------------------------------------------------------------------------------
1.7 算法的时间复杂度仅与问题的规模相关吗?
◆No,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。
--------------------------------------------------------------------------------
1.8 按增长率由小至大的顺序排列下列各函数：2^100, (2/3)^n，(3/2)^n，n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2)
◇分析如下：2^100 是常数阶；(2/3)^n和(3/2)^n是指数阶,其中前者是随n的增大而减小的；n^n是指数方阶；√n 是方根阶, n! 就是n(n-1)(n-2)... 就相当于n次方阶；2^n 是指数阶，lgn是对数阶,n^lgn是对数方阶, n^(3/2)是3/2次方阶。根据以上分析按增长率由小至大的顺序可排列如下：
◆(2/3)^n < 2^100 < lgn < √n < n^(3/2) < n^lgn < (3/2)^n < 2^n < n! < n^n
--------------------------------------------------------------------------------
1.9 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=
2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?
函数大"O"表示优劣
(1) T1(n)=5n^2-3n+60lgn ◆5n^2+O(n) ◆较差
(2) T2(n)=3n^2+1000n+3lgn ◆3n^2+O(n) ◆其次
(3) T3(n)=8n^2+3lgn ◆8n^2+O(lgn) ◆最差
(4) T4(n)=1.5n^2+6000nlgn ◆1.5n^2+O(nlgn) ◆最优
第一章概论复习要点
本章的复习要点是：
数据、数据元素、数据结构(包括逻辑结构、存储结构)以及数据类型的概念、数据的逻辑结构分为哪两大类，及其逻辑特征、数据的存储结构可用的四种基本存储方法。
时间复杂度与渐近时间复杂度的概念，如何求算法的时间复杂度。
可能出的题目有选择题、填空题或简答题。如：
.........是数据的基本单位，.........是具有独立含义的最小标识单位。
什么是数据结构?什么是数据类型?
数据的............与数据的存储无关，它是独立于计算机的。
数据的存储结构包括顺序存储结构、链式存储结构.......................、...........................
设n为正整数，利用大O记号，将该程序段的执行时间表示为n的函数，则下列程序段的时间复杂度可表示为：(....)
x=91;y=100;
while(y>10)
if(x>100){x=x-10;y--;}
else x++;
A. O(1)
B.O(x)
C.O(y)
D.O(n)
等等。
顺便一提，基本概念和基本理论的掌握是得分的基本手段。
第二章：线性表(包括习题与答案及要点)
转摘https://www.doczj.com/doc/836032838.html,
--------------------------------------------------------------------------------
本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。
要求达到<识记>层次的内容有:线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。
要求达到<综合应用>层次的内容有：顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析，解决简单应用问题。
链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。
要求达到<领会>层次的内容就是顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。
--------------------------------------------------------------------------------
线性表的逻辑结构特征是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个开始结点，有且只能有一个终端结点，其它的结前后所相邻的也只能是一个结点(直接前趋和直接后继)。
关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。
--------------------------------------------------------------------------------
线性表的逻辑结构和存储结构之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。
在顺序表中实现的基本运算主要讨论了插入和删除两种运算。相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。
--------------------------------------------------------------------------------
线性表的链式存储结构。它与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。所以为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。
一个单链表由头指针的名字来命名。
对于单链表，其操作运算主要有建立单链表(头插法、尾插法和在链表开始结点前附加一个头结点的算法)、查找(按序号和按值)、插入运算、删除运算等。以上各运算的平均时间复杂度均为O(n).其主要时间是耗费在查找操作上。
--------------------------------------------------------------------------------
循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点)，形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表了。
判别链表终止的条件也不同于单链表，它是以指针是否等于某一指定指针如头指针或尾指针来确定。
--------------------------------------------------------------------------------
双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,这样形成的链表就有两条不同方向的链。使得从已知结点查找其直接前趋结点可以和查找其直接后继结点的时间一样缩短为O(1)。
双链表一般也由头指针head惟一确定。双链表也可以头尾相链接构成双(向)循环链表。
--------------------------------------------------------------------------------
关于顺序表和链表的比较，请看下表：
具体要求顺序表链表
基于空间适于线性表长度变化不大，易于事先确定其大小时采用。适于当线性表长度变化大，难以估计其存储规模时采用。
基于时间由于顺序表是一种随机存储结构，当线性表的操作主要是查找时，宜采用。链表
中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。
第二章线性表习题及答案
--------------------------------------------------------------------------------
一、基础知识题
(答案及点评) 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
一、基础知识题
2.1 答：
开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。
--------------------------------------------------------------------------------
(答案及点评) 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
2.2 答：
在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
--------------------------------------------------------------------------------
(答案及点评) 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
2.3.答：
在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。
--------------------------------------------------------------------------------
(答案及点评) 2.4 为什么在单循环链表中设置尾指针比设置头指针更好?
2.4. 答：
尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。
若用头指针来表示该链表，则查找终端结点的时间为O(n)。
--------------------------------------------------------------------------------
(答案及点评) 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?
2.5 答：
我们分别讨论三种链表的情况。
1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。
3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
--------------------------------------------------------------------------------
(答案及点评) 2.6 下述算法的功能是什么?
LinkList Demo(LinkList L){ // L 是无头结点单链表
ListNode *Q,*P;
if(L&&L->next){
Q=L;L=L->next;P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}// Demo
第三章：栈和队列(包括习题与答案及要点)
转摘https://www.doczj.com/doc/836032838.html,
--------------------------------------------------------------------------------
本章介绍的是栈和队列的逻辑结构定义及在两种存储结构(顺序存储结构和链式存储结构)上如何实现栈和队列的基本运算。本章的重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。
--------------------------------------------------------------------------------
1.栈的逻辑结构、存储结构及其相关算法(综合应用):
栈的逻辑结构和我们先前学过的线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继),但是栈的运算规则与线性表相比有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out).
栈的基本运算有六种：
构造空栈：InitStack(S)、
判栈空: StackEmpty(S)、
判栈满：StackFull(S)、
进栈：Push(S,x)、可形象地理解为压入，这时栈中会多一个元素
退栈：Pop(S) 、可形象地理解为弹出，弹出后栈中就无此元素了。
取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。
--------------------------------------------------------------------------------
由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。
--------------------------------------------------------------------------------
我们要了解的是，在顺序栈中有"上溢"和"下溢"的概念。顺序栈好比一个盒子，我们在里头放了一叠书，当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^)，那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算，哼哼)，这时就是"上溢","上溢"也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，我们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是"下溢"。"下溢"本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。
链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
以上两种存储结构的栈的基本操作算法是不同的，我们主要要学会进栈和退栈的基本算法以解决简单的应用问题。
--------------------------------------------------------------------------------
2.队列的逻辑结构、存储结构及其相关算法(综合应用)。
队列(Queue,念Q音)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头(Front) ,队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)
队列的基本运算也有六种：
置空队：InitQueue(Q)
判队空：QueueEmpty(Q)
判队满：QueueFull(Q)
入队：EnQueue(Q,x)
出队：DeQueue(Q)
取队头元素：QueueFront(Q),不同与出队，队头元素仍然保留
--------------------------------------------------------------------------------
队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。
对于顺序队列，我们要理解"假上溢"的现象。
我们现实中的队列比如人群排队买票，队伍中的人是可以一边进去从另一头出来的，除非地方不够，总不会有"溢出"的现象，相似地，当队列中元素完全充满这个向量空间时，再入队自然就会上溢，如果队列中已没有元素，那么再要出队也会下溢。
那么"假上溢"就是怎么回事呢?
因为在这里，我们的队列是存储在一个向量空间里，在这一段连续的存储空间中，由一个队列头指针和一个尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空，也就是说，队列是由两个指针中间的元素构成的。在队列中，入队和出队并不是象现实中，元素一个个地向前移动，走完了就没有了,而是指针在移动，当出队操作时，头指针向前(即向量空间的尾部)增加一个位置，入队时，尾指针向前增加一个位置，在某种情况下，比如说进一个出一个，两个指针就不停地向前移动，直到队列所在向量空间的尾部，这时再入队的话，尾指针就要跑到向量空间外面去了，仅管这时整个向量空间是空的，队列也是空的，却产生了"上溢"现象，这就是假上溢。
为了克服这种现象造成的空间浪费，我们引入循环向量的概念，就好比是把向量空间弯起来，形成一个头尾相接的环形，这样，当存于其中的队列头尾指针移到向量空间的上界(尾部)时，再加1的操作(入队或出队)就使指针指向向量的下界，也就是从头开始。这时的队列就称循环队列。
通常我们应用的大都是循环队列。由于循环的原因，光看头尾指针重叠在一起我们并不能判断队列是空的还是满的，这时就需要处理一些边界条件，以区别队列是空还是满。方法至少有三种，一种是另设一个布尔变量来判断(就是请别人看着，是空还是满由他说了算)，第二种是少用一个元素空间，当入队时，先测试入队后尾指针是不是会等于头指针，如果相等就算队已满，不许入队。第三种就是用一个计数器记录队列中的元素的总数，这样就可以随时知道队列的长度了，只要队列中的元素个数等于向量空间的长度，就是队满。
以上是顺序队列，我们要掌握相应算法以解决简单应用问题。
--------------------------------------------------------------------------------
队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。
--------------------------------------------------------------------------------
3.栈和队列的应用(领会)
教材中举了几个例子，对于我们初学者来说，看上去比较繁，我们只要掌握一点，那就是，对于什么情况下用栈和队列作为解决问题的数据结构。
判断的要点就是：如果这个问题满足后进先出(LIFO)的原则，就可以使用栈来处理。如果这个问题满足先进先出(FIFO)的原则，就可以使用队列来处理。
比如简单的说，有一个数组序列，我们输入时按顺序输入，但是输出时需要逆序输出，那么
它就可以利用栈来处理，把这个数组存入一个栈中就可以容易地按逆序输出结果了。
第三章线性表习题及答案
--------------------------------------------------------------------------------
一、基础知识题
(答案及点评) 3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?
(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。
(3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
--------------------------------------------------------------------------------
(答案及点评) 3.2 链栈中为何不设置头结点?
答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
--------------------------------------------------------------------------------
(答案及点评) 3.3 循环队列的优点是什么? 如何判别它的空和满?
3.3 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。
--------------------------------------------------------------------------------
(答案及点评) 3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
3.4答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
第四章：串(包括习题与答案及要点)
转摘https://www.doczj.com/doc/836032838.html,
--------------------------------------------------------------------------------
本章介绍了串的逻辑结构，存储结构及串上的基本运算，由于在高级语言中已经提供了较全善的串处理功能，因此本章的重点是掌握在串上实现的模式匹配算法。同时这也是本章的难点。但是从全书来讲，这属于较简单的一章内容。
--------------------------------------------------------------------------------
1.串及其运算(领会)(这些内容比较容易理解，不用死记)
串就是字符串，是一种特殊的线性表，它的每个结点仅由一个字符组成。
空串：是指长度为零的串，也就是串中不包含任何字符(结点)。
空白串：指串中包含一个或多个空格字符的串。不同与空串，它的结点就是一个空格字符。
1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录就是一个结点，对于整个表来说，只有一个开始结点和一个终端结点，其他的结点则各有一个也只有一个直接前趋和直接后继。这几个关系就确定了这个表的逻辑结构。
那么我们怎样把这个表中的数据存储到里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。。
最后，我们有了这个表，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。
客观题 第一章绪论 一、判断题 (1）数据的逻辑结构与数据元素本身的内容和形式无关。 (2）数据元素是数据的最小单位。 (3）算法是对解题方法和步骤的描述。 (4）程序和算法原则上没有区别，在讨论数据结构时可以通用。 (5）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 (6）数据的存储结构是数据的逻辑结构的存储映像。 二、选择题 (l）数据结构通常是研究数据的（）及它们之间的相互联系。 A．存储结构和逻辑结构 B．存储和抽象 C．联系和抽象 D．联系与逻辑(2) 下列与数据元素有关的叙述中错误的是（）。 A．数据元素是有独立含义的数据最小单位 B．数据元素是描述数据的基本单位C．数据元素可以称做结点 D．数据元素可以称做记录 (3）数据结构中，在逻辑上可以把数据结构分成：( ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 (4）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为 ( ）。 A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构 (5）非线性结构的数据元素之间存在（）。 A．一对一关系 B．一对多关系 C．多对多关系 D. B 或 C (6）在非线性结构中，每个结点（）。 A. 无直接前驱 B．只有一个直接前驱和个数不受限制的直接后继 C．只有一个直接前驱和直接后继 D．有个数不受限制的直接前驱和直接后继 (7）除了考虑存储数据结构本身所占用的空间外，实现算法所用的辅助空间的多少称为算法的（）。 A．时间效率 B．空间效率 C．硬件效率 D．软件效率(8)以下属于顺序存储结构优点的是（）。 A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 (9)数据结构研究的内容是（）。 A．数据的逻辑结构 B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面 (10)链式存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 (11)一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。 A．确定性、可行性、有穷性 B．易读性、确定性、有效性 C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性(12)以下关于数据的逻辑结构的叙述中正确的是（）。 A．数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构反映了数据在计算机中的存储方式
数据库设计实例分析 一、需求分析实例 现要开发高校图书管理系统。经过可行性分析和初步的需求调查，确定了系统的功能边界，该系统应能完成下面的功能： （1）读者注册。 （2）读者借书。 （3）读者还书。 （4）图书查询。 1、数据流图 顶层数据流图反映了图书管理系统与外界的接口，但未表明数据的加
工要求，需要进一步细化。根据前面图书管理系统功能边界的确定，再对图书管理系统顶层数据流图中的处理功能做进一步分解，可分解为读者注册、借书、还书和查询四个子功能，这样就得到了图书管理系统的第0层数据流图 从图书管理系统第0层数据流图中可以看出，在图书管理的不同业务中，借书、还书、查询这几个处理较为复杂，使用到不同的数据较多，因此有必要对其进行更深层次的分析，即构建这些处理的第1层数据流图。下面的图8-7分别给出了借书、还书、查询子功能的第1层数据流图
2、数据字典 2.1 数据项 数据项名称：借书证号 别名：卡号 含义说明：惟一标识一个借书证 类型：字符型 长度：20 …… 2.2 数据结构 （1）名称：读者类别 含义说明：定义了一个读者类别的有关信息 组成结构：类别代码+类别名称+可借阅数量+借阅天数+超期罚款额（2）名称：读者 含义说明：定义了一个读者的有关信息 组成结构：+性别+所在部门+读者类型 （3）名称：图书 含义说明：定义了一本图书的有关信息 组成结构：图书编号+图书名称+作者++价格 …… 2.3 数据流 （1）数据流名称：借书单 含义：读者借书时填写的单据 来源：读者 去向：审核借书 数据流量：250份/天
组成：借书证编号+借阅日期+图书编号 （2）数据流名称：还书单 含义：读者还书时填写的单据 来源：读者 去向：审核还书 数据流量：250份/天 组成：借书证编号+还书日期+图书编号 …… 2.4 数据存储 （1）数据存储名称：图书信息表 含义说明：存放图书有关信息 组成结构：图书+库存数量 说明：数量用来说明图书在仓库中的存放数 （2）数据存储名称：读者信息表 含义说明：存放读者的注册信息 组成结构：读者+卡号+卡状态+办卡日期 说明：卡状态是指借书证当前被锁定还是正常使用（3）数据存储名称：借书记录 含义说明：存放读者的借书、还书信息 组成结构：卡号+书号+借书日期+还书日期 说明：要求能立即查询并修改
第7章数据库设计 1．试述数据库设计过程。 答：这里只概要列出数据库设计过程的六个阶段：( l ）需求分析；( 2 ）概念结构设计；( 3 ）逻辑结构设计；( 4 ）数据库物理设计；( 5 ）数据库实施；( 6 ）数据库运行和维护。这是一个完整的实际数据库及其应用系统的设计过程。不仅包括设计数据库本身，还包括数据库的实施、运行和维护。设计一个完善的数据库应用系统往往是上述六个阶段的不断反复。 2 ．试述数据库设计过程各个阶段上的设计描述。 答：各阶段的设计要点如下：( l ）需求分析：准确了解与分析用户需求（包括数据与处理）。( 2 ）概念结构设计：通过对用户需求进行综合、归纳与抽象，形成一个独立于具体DBMS 的概念模型。( 3 ）逻辑结构设计：将概念结构转换为某个DBMS 所支持的数据模型，并对其进行优化。( 4 ）数据库物理设计：为逻辑数据模型选取一个最适合应用环境的物理结构（包括存储结构和存取方法）。( 5 ）数据库实施：设计人员运用DBMS 提供的数据语言、工具及宿主语言，根据逻辑设计和物理设计的结果建立数据库，编制与调试应用程序，组织数据入库，并进行试运行。( 6 ）数据库运行和维护：在数据库系统运行过程中对其进行评价、调整与修改。 3 ．试述数据库设计过程中结构设计部分形成的数据库模式。 答：数据库结构设计的不同阶段形成数据库的各级模式，即：( l ）在概念设计阶段形成独立于机器特点，独立于各个DBMS 产品的概念模式，在本篇中就是 E 一R 图；( 2 ）在逻辑设计阶段将 E 一R 图转换成具体的数据库产品支持的数据模型，如关系模型，形成数据库逻辑模式，然后在基本表的基础上再建立必要的视图( Vi 娜），形成数据的外模式；( 3 ）在物理设计阶段，根据DBMS 特点和处理的需要，进行物理存储安排，建立索引，形成数据库内模式。 4 ．试述数据库设计的特点。 答：数据库设计既是一项涉及多学科的综合性技术又是一项庞大的工程项目。其主要特点有：( l ）数据库建设是硬件、软件和干件（技术与管理的界面）的结合。( 2 ）从软件设计的技术角度看，数据库设计应该和应用系统设计相结合，也就是说，整个设计过程中要把结构（数据）设计和行为（处理）设计密切结合起来。 5 ．需求分析阶段的设计目标是什么？调查的内容是什么？ 答：需求分析阶段的设计目标是通过详细调查现实世界要处理的对象（组织、部门、企业等），充分了解原系统（手工系统或计算机系统）工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。调查的内容是“数据’夕和“处理”，即获得用户对数据库的如下要求：( l ）信息要求，指用户需要从数据库中获得信息的内容与性质，由信息要求可以导出数据要求，即在数据库中需要存储哪些数据；( 2 ）处理要求，指用户要完成什么处理功能，对处理的响应时间有什么要求，处理方式是批处理还是联机处理；( 3 ）安全性与完整性要求。 6 ．数据字典的内容和作用是什么？ 答：数据字典是系统中各类数据描述的集合。数据字典的内容通常包括：( l ）数据项；( 2 ）数据结构；( 3 ）数据流；( 4 ）数据存储；( 5 ）处理过程五个部分。其中数据项是数
数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------
很详细的系统架构图--专业推荐 2013.11.7
1.1.共享平台逻辑架构设计 如上图所示为本次共享资源平台逻辑架构图，上图整体展现说明包括以下几个方面： 1 应用系统建设 本次项目的一项重点就是实现原有应用系统的全面升级以及新的应用系统的开发，从而建立行业的全面的应用系统架构群。整体应用系统通过SOA面向服务管理架构模式实现应用组件的有效整合，完成应用系统的统一化管理与维护。 2 应用资源采集 整体应用系统资源统一分为两类，具体包括结构化资源和非机构化资源。本次项目就要实现对这两类资源的有效采集和管理。对于非结构化资源，我们将通过相应的资源采集工具完成数据的统一管理与维护。对于结构化资源，我们将通过全面的接口管理体系进行相应资源采集模板的搭建，采集后的数据经过有效的资源审核和分析处理后进入到数据交换平台进行有效管理。 3 数据分析与展现 采集完成的数据将通过有效的资源分析管理机制实现资源的有效管理与展现，具体包括了对资源的查询、分析、统计、汇总、报表、预测、决策等功能模块的搭建。 4 数据的应用 最终数据将通过内外网门户对外进行发布，相关人员包括局内各个部门人员、区各委办局、用人单位以及广大公众将可以通过不同的权限登录不同门户进行相关资源的查询，从而有效提升了我局整体应用服务质量。 综上，我们对本次项目整体逻辑架构进行了有效的构建，下面我们将从技术角度对相
关架构进行描述。 1.2.技术架构设计 如上图对本次项目整体技术架构进行了设计，从上图我们可以看出，本次项目整体建设内容应当包含了相关体系架构的搭建、应用功能完善可开发、应用资源全面共享与管理。下面我们将分别进行说明。 1.3.整体架构设计 上述两节，我们对共享平台整体逻辑架构以及项目搭建整体技术架构进行了分别的设计说明，通过上述设计，我们对整体项目的架构图进行了归纳如下：
数据结构中常用的逻辑结构和存储结构 一、概念 数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。 数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系即逻辑结构，而物理上的数据结构反映成分数据在计算机内部的存储安排即存储结构。数据结构是数据存在的形式。 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。因而研究数据结构的逻辑结构与存储结构显得十分重要。 二、结构分析 （一）逻辑结构 数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。 逻辑结构元素决定输入、存储、发送、处理和信息传递的基本操作功能，常将逻辑结构元素称为逻辑模块。逻辑结构元素可以是计算机操作系统、终端模块、通信程序模块等。逻辑结构元素还可以是相关的几个逻辑模块联合起来的更复杂的实体。分析逻辑结构元素的相互作用，应考虑整个系统的操作，研究处理与信息流有关的进程（操作系统中的一个概念，表示程序的一次执行），并决定系统的逻辑资源。 逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法能够用这两种数据结构来设计实现。 一、基本分类 数据的逻辑结构指数据元素之间的逻辑关系，分两种，线性结构和非线性结构。 线性结构：有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。）线性表就是一个典型的线性结构它有四个基本特征：1．集合中必存在唯一的一个"第一个元素"； 2．集合中必存在唯一的一个"最后的元素"； 3．除最后元素之外，其它数据元素均有唯一的"后继"； 4．除第一元素之外，其它数据元素均有唯一的"前驱"。 相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个直接后继。常见的非线性结构有：树(二叉树等)，图(网等)。 二、常用结构
架构设计之-逻辑架构 逻辑架构=模块划分+接口定义+领域模型 逻辑架构关注职责划分和接口定义。不同粒度的职责需要被关注，它们可能是逻辑层、功能子系统、模块、关键类等。不同通用程度的职责要分离，分别封装到专门模块、通用模块或通用机制中。 图-1 逻辑架构的设计内容 【设计任务】一、模块划分 面对“技术复杂性”和“管理复杂性”这样的双重困难，以架构为中心的开发方法是有效的途径。软件架构从大局着手，就技术方面的重大问题作出决策，构造一个具有一定抽象层次的解决方案，而不是将所有细节统统展开，从而有效地控制了“技术复杂性”。 通过 定义“如何划分模块、模块间如何通过接口交互”，架构提供了团队开发的基础，如图
2所示，可以把不同模块分配给不同小组分头开发，接口就是小组间合作的“契约”，每个小组的工作覆盖了“整个问题的一部门”。这样一来，模块的技术细节被局部化到了小组内部，内部的细节不会成为小组间协作沟通的主要内容，也就理顺了沟通的层次。另外，对“人尽其才”也有好处，不同小组的成员需要精通的技术各不相同。 图2 软件架构奠定团队开发基础 模块划分是架构师的看家本领，有多种手段可以促进合理划分模块： 1、从需求层面的“功能树”，启发“功能模块”的划分 2、水平分层，促进模块分解 3、通用模块和通用机制的识别 4、现代的用例驱动的模块划分过程 5、传统的模块化分思维 6、…… 【设计任务】二、接口定义 正确的设计思路是“协作决定接口”。架构师设计接口时，要考虑的重点是“为了实现软件系统的一系列功能，这个软件单元要和其他哪些单元协作、如何协作”。此时，可以使
用（一组）序列图辅助进行设计。 【设计任务】三、领域模型细化 逻辑架构设计的粒度，一般推荐设计到模块一级，但如下4种“关键类”可以在架构设计时就明确： 1、接口定义类 2、Facade实现类 3、核心控制类 4、另外，就是对系统可扩展性有根本影响的构成领域模型的那些类
数据库逻辑存储结构 数据库的物理存储结构对应一系列的物理文件,这部分主要描述的是数据存储的实际位置,不过数据如果存储,是以什么结构存储到数据文件中,则取决于数据库的逻辑存储结构. Oracle数据库在执行操作时,并不是以数据文件为单位,而是从逻辑上定义出一组结构,操作的数据可以一步步细分不同的存储单元,oracle 操作数据的过程,实际上就是对这些不同级别的存储单元进行维护和管理的过程. 逻辑存储概述 --块(block)块是逻辑存储结构中最小存储单位,所有数据的存储都是以块为单位进行.初始化参数文件中BLOCK_SIZE来指定一个块的大小,也就是说oracle的块大小在数据库创建时指定,一经指定就无法修改,除非重建数据库. --区(extent) 区是oracle数据库的最小分配单位,由一组连续的块组成,这些块在物理上可能并不连续(也就是OS块),但是必需都存在于一个物理文件,单个区在分配时不能跨文件分配(这个文件应该是数据文件).在创建对象时,最少会为该对象分配一个区,这个区叫做初始区(initial extent) 在随着对象的不断扩展,超出初始区后,oracle就会再为其分配扩展区(incremental extent)扩展区不一定要与初始区连续存放,甚至大小也可以与初始区不同,不过扩展区也必需是由连续的块组成. 段(segment)从逻辑的角度看,段由一个或多个区组成,它是一个真正逻辑结构. 可以将段看作是对象的全部或某个部分 例如：一个普通的堆组织表(不含分区,LOB类型及索引等)那么该表就对应一个段,不管这个表中被存放多少记录,它都仍然只对应一个段,不过如果该表创建了索引,那么索引数据会存放专门的索引段,如果该表有LOB类型,LOB数据也会被存入单独的数据段. --表空间(tablespace)从逻辑上定义,是由一个或多个段组成,从物理上定义是由一个或多个数据文件组成.表空间是oracle数据库中空间分配的最大逻辑单位,在往上就是数据库级别. 平时进行的创建对象的操作,都是在表空间一级进行. **提示:如创建存储对象时只能指定存储到哪个表空间,而不能指定存储到更细粒度的逻辑结构,如段,区,块.也不能指定存储到某个数据文件中. *注意*:在创建存储对象时,只需要指定存储所在的表空间(如果未指定,则存储到用户当前的默认表空间中),其他一切由oracle自动处理图: 每层结构都是一对多的关系 逻辑结构对应关系图
数据的逻辑结构：分为线性结构个非线性结构 数据的存储结构：存储结构是逻辑结构在计算机存储器里得实现。 数据的运算：数据的运算是定义在数据的逻辑结构上的但运算的具体实现要在存储结构上进行多媒体就是多重媒体的意思，可以理解为直接作用于人感官的文字、图形、图像、动画、 音和视频等各种媒体的统称，即多种信息载体的表现形式和传递方式。多媒体技术是利用计算机对文本、图形、图像、声音、动画、视频等多种信息综合处理、建立逻辑关系和人机交互作用的技术。主要包括: ·音频技术:音频采样、压缩、合成及处理、语音识别等。·视频技术:视频数字化及处理。图像技术:图像处理、图像、图形动态生成。·图像压缩技术:图像压缩、动态视频压缩。·通信技术:语音、视频、图像的传输。·标准化:多媒体标准化。多媒体技术涉及的内容多媒体数据压缩：多模态转换、压缩编码；多媒体处理：音频信息处理，如音乐合成、语音识别、文字与语音相互转换；图像处理，虚拟现实；多媒体数据存储：多媒体数据库； 系统软件. 操作软件 软件是程序以及开发、使用和维护所需要的所有文档的总称,而程序是软件的一部分及软件=程序+文档=数据结构+算法+文档是满足用户需求的一种程序。程序不一定是软件，而软件包含了很多个程序。程序包括软件和病毒！软件就是行为合法的程序集！软件是由程序组成 1首先编译器进行语法分析，此时一个语句作为一串记号流有语法分析器进行处理按照语言的文法检查每个语法分析树，判断是否为合乎语法的句子。 2然后进行语义分析，是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。 3最后生成中间代码。中间代码是向目标代码即机械语言的代码过度的一种编码其形式其形式尽可能与机械的汇编语言相似，以便生成下一步代码。 4优化。对中间代码进行局部和全局的优化目的式运算的速度更快占内存更小。 5再经过链接器的链接就可以生成目标代码最后的产生EXE文件了。 有些时候需要把多个文件产生的目标文件进行链接，产生最后的代码。这一过程称为交叉链接。 操作系统(Operating System，简称OS)是管理计算机系统的全部硬件资源包括软件资源及数据资源；控制程序运行；改善人机界面；为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。资源管理程序控制人机交互进程管理内存管理虚拟内存用户接口 如果顺序查找表的元素按照关键字的值有序存放，那么可利用高效的二分查找来完成查询。条件假定元素按关键字的值升序排列，将给定的数据与有序表中间位置的元素做比较，若两者相等则查找成功；若前者小于后者则在中间位置左边的元素中继续查找；若前者大于后者则在中间位置右边的元素中继续查找。不断重复这一过程直到查找成功，或者直到查找区间缩小为一个元素时却仍未找到目标，则查找失败。 ?#include 1.数据库应用系统的设计步骤 按规范设计的方法可将数据库设计分为以下六个阶段 （1）需求分析; （2）概念结构设计; （3）逻辑结构设计; （4）数据库物理设计; （5）数据库实施; （6）数据库运行和维护。 2.需求分析 需求收集和分析是数据库应用系统设计的第一阶段。明确地把它作为数据库应用系统设计的第一步是十分重要的。这一阶段收集到的基础数据和一组数据流图（DataFlowDiaˉgram———DFD）是下一步设计概念结构的基础。概念结构对整个数据库设计具有深刻影响。 而要设计好概念结构，就必须在需求分析阶段用系统的观点来考虑问题、收集和分析数据及其处理。如何分析和表达用户需求呢？在众多的分析方法中，结构化分析（StructuredAnalysis，简称SA方法）是一个简单实用的方法。SA方法用自顶向下、逐层分解的方式分析系统。用数据流图，数据字典描述系统。然后把一个处理功能的具体内容分解为若干子功能，每个子功能继续分解，直到把系统的工作过程表达清楚为止。在处理功能逐步分解的同时，它们所用的数据也逐级分解。形成若干层次的数据流图。数据流图表达了数据和处理过程的关系。处理过程的处理逻辑常常用判定表或判定树来描述。数据字典（DataDictionary，简称DD）则是对系统中数据的详尽描述，是各类数据属性的清单。对数据库应用系统设计来讲，数据字典是进行详细的数据收集和数据分析所获得的主要结果。数据字典是各类数据描述的集合，它通常包括以下5个部分： （1）数据项，是数据最小单位。 （2）数据结构，是若干数据项有意义的集合。 （3）数据流，可以是数据项，也可以是数据结构。表示某一处理过程的输入输出。 （4）数据存储，处理过程中存取的数据。常常是手工凭证、手工文档或计算机文件。 （5）处理过程。 3."概念结构设计 如同软件工程中重视需求分析与规范说明的思想一样，数据库设计中同样十分重视数据分析、抽象与概念结构的设计。概念结构的设计，是整个数据库设计的关键之 一。"概念结构独立于数据库逻辑结构，独立于支持数据库的DBMS，也独立于具体计算机软件和硬件系统。归纳总结，其主要特点是： （1）能充分地反映现实世界，包括实体和实体之间的联系，能满足用户对数据处理的要求，是现实世界的一个真实的模型，或接近真实的模型。 （2）易于理解，从而可以和不熟悉计算机的用户交换意见。用户的积极参与是数据库应用系统设计成功与否的关键。 （3）易于更动。当现实世界改变时容易修改和扩充，特别是软件、硬件环境变化时更应如此。 （4）易于向关系、网状或层次等各种数据模型转换。概念结构是各种数据模型的共同基础，它比任意一种数据模型更独立于机器，更抽象，从而更加稳定。描述概念结构的有力工具是E-R模型。P.P.S.Chen把用E-R模型定义的概念结构称为组织模式。设计概念结构的策略有3种： （1）自顶向下首先定义全局概念结构的框架，然后逐步细化。 （2）自底向上首先定义各局部应用的概念结构，然后将它们集成，得到全局概念结构。 数据库逻辑结构设计 该系列计划包括5部分：完整性约束理论及应用、范式理论及应用、需求分析、概念结构设计、逻辑结构设计。本文是第五部分，介绍逻辑结构设计的内容，包括E-R图向关系模型的转换、数据模型的优化、用户子模式的设计等问题。1．逻辑设计概述 概念结构是独立于任何一种数据模型的，在实际应用中，一般所用的数据库环境已经给定（如SQL Server或Oracel或MySql），本文讨论从概念结构向逻辑结构的转换问题。 由于目前使用的数据库基本上都是关系数据库，因此首先需要将E-R图转换为关系模型，然后根据具体DBMS的特点和限制转换为特定的DBMS支持下的数据模型，最后进行优化。 2．E-R图向关系模型的转换 2.1 一个例子 E-R图如何转换为关系模型呢？我们先看一个例子。 图2.1是学生和班级的E-R图，学生与班级构成多对一的联系。根据实际应用，我们可以做出这个简单例子的关系模式： 学生（学号，姓名，班级） 班级（编号，名称） “学生.班级”为外键，参照“班级.编号”取值。 这个例子我们是凭经验转换的，那么里面有什么规律呢？在2.2节，我们将这些经验总结成一些规则，以供转换使用。 2.2 转换规则 (1) 一个实体型转换为一个关系模式 一般E-R图中的一个实体转换为一个关系模式，实体的属性就是关系的属性，实体的码就是关系的码。 (2) 一个1:1联系可以转换为一个独立的关系模式，也可以与任意一端对应 的关系模式合并。 图2.2是一个一对一联系的例子。根据规则（2），有三种转换方式。 联系单独作为一个关系模式 此时联系本身的属性，以及与该联系相连的实体的码均作为关系的属性，可以选择与该联系相连的任一实体的码属性作为该关系的码。结果如下： 职工（工号，姓名） 产品（产品号，产品名） 负责（工号，产品号） 其中“负责”这个关系的码可以是工号，也可以是产品号。 )与职工端合并 职工（工号，姓名，产品号） 产品（产品号，产品名） 其中“职工.产品号”为外码。 i)与产品端合并 职工（工号，姓名） 产品（产品号，产品名，负责人工号） 其中“产品.负责人工号”为外码。 (3) 一个1:n联系可以转换为一个独立的关系模式，也可以与n端对应的关 系模式合并。 数据库逻辑结构设计 该系列计划包括5部分:完整性约束理论及应用、范式理论及应用、需求分析、概念结构设计、逻辑结构设计。本文就是第五部分,介绍逻辑结构设计的内容,包括E-R图向关系模型的转换、数据模型的优化、用户子模式的设计等问题。1.逻辑设计概述 概念结构就是独立于任何一种数据模型的,在实际应用中,一般所用的数据库环境已经给定(如SQL Server或Oracel或MySql),本文讨论从概念结构向逻辑结构的转换问题。 由于目前使用的数据库基本上都就是关系数据库,因此首先需要将E-R图转换为关系模型,然后根据具体DBMS的特点与限制转换为特定的DBMS支持下的数据模型,最后进行优化。 2.E-R图向关系模型的转换 2、1 一个例子 E-R图如何转换为关系模型呢？我们先瞧一个例子。 图2、1就是学生与班级的E-R图,学生与班级构成多对一的联系。根据实际应用,我们可以做出这个简单例子的关系模式: 学生(学号,姓名,班级) 班级(编号,名称) “学生、班级”为外键,参照“班级、编号”取值。 这个例子我们就是凭经验转换的,那么里面有什么规律呢？在2、2节,我们将这些经验总结成一些规则,以供转换使用。 2、2 转换规则 (1) 一个实体型转换为一个关系模式 一般E-R图中的一个实体转换为一个关系模式,实体的属性就就是关系的属性,实体的码就就是关系的码。 (2) 一个1:1联系可以转换为一个独立的关系模式,也可以与任意一端对应 的关系模式合并。 图2、2就是一个一对一联系的例子。根据规则(2),有三种转换方式。 联系单独作为一个关系模式 此时联系本身的属性,以及与该联系相连的实体的码均作为关系的属性,可以选择与该联系相连的任一实体的码属性作为该关系的码。结果如下: 职工(工号,姓名) 产品(产品号,产品名) 负责(工号,产品号) 其中“负责”这个关系的码可以就是工号,也可以就是产品号。 )与职工端合并 职工(工号,姓名,产品号) 产品(产品号,产品名) 其中“职工、产品号”为外码。 i)与产品端合并 职工(工号,姓名) 产品(产品号,产品名,负责人工号) 其中“产品、负责人工号”为外码。 (3) 一个1:n联系可以转换为一个独立的关系模式,也可以与n端对应的关 系模式合并。 Oracle数据库逻辑结构 2.1.1Oracle系统体系结构 话说与其他数据库产品不同，Oracle有其自己独特的系统体系结构。Oracl e系统体系结构是整个Oracle服务器系统的框架，是管理和应用Oracle数据服务器的基础和核心。 Oracle系统体系结构由三部分组成：逻辑结构、物理结构和实例。其中，实例是维系物理结构和逻辑结构的核心，如图2-1和图2-2所示。图2-1表明了数据库三级模式及其物理文件之间的关系。 图2-1 数据库模式及其物理文件关系示意图 图2-2 Oracle系统体系结构与功能 不论是Oracle的应用开发还是数据库管理都是以实例作为切入点的。只不过Oracle的应用程序开发主要是以数据库的逻辑对象为主(如表、索引和视图等),而数据库管理则是针对数据库的全部内容。Oracle数据库由构成物理结构的各种文件组成，如数据文件、控制文件和重做日志文件等；实例是Oracle在内存中分配的一段区域SGA和服务器后台进程的集合。Oracle数据库服务器就是数据库和实例的组合。 2.1.2Oracle逻辑结构 Oracle的逻辑结构是一种层次结构。主要由：表空间、段、区和数据块等概念组成。逻辑结构是面向用户的，用户使用Oracle开发应用程序使用的就是逻辑结构。数据库存储层次结构及其构成关系,结构对象也从数据块到表空间形成了不同层次的粒度关系，如图2-3和图2-4所示。 图2-3 Oracle 10g数据库层次结构图图2-4 段、区和数据块之间的关系 1.数据块 Oracle数据块（Data Block）是一组连续的操作系统块。分配数据库块大小是在Oracle数据库创建时设置的，数据块是Oracle读写的基本单位。数据块的大小一般是操作系统块大小的整数倍，这样可以避免不必要的系统I/O操作。从Oracle9i开始，在同一数据库中不同表空间的数据块大小可以不同。数据块是O racle最基本的存储单位，而表空间、段、区间则是逻辑组织的构成成员。在数据库缓冲区中的每一个块都是一个数据块，一个数据块不能跨越多个文件。 数据块的结构主要包括： ·标题：包括一般的块信息，如块地址，段类型等。 ·表目录：包括有关表在该数据块中的行信息。 ·Oracle体系结构第2章 行目录：包括有关在该数据块中行地址等信息。 ·行数据：包括表或索引数据。一行可跨越多个数据块。 数据库逻辑结构图 一、实体的关系模型 1）、管理员（用户名，密码） 2）、个人（帐号，密码，姓名，年龄，出生日期，电话号码）3）、备忘录（时间，地点，事件） 4）、通讯录（姓名，城市，备注，工作地点，联系方式） 5）、日记（日期，地点，人物，事情） 6）、财务（标志，消费项目，消费时间，消费金额，剩余金额，总收入） 其中有下划线的是主键。 二、关系模型合并 1）、管理员（用户名，密码） 2）、个人（帐号，密码，姓名，年龄，出生日期，电话号码）3）、备忘录（时间，地点，事件） 4）、通讯录（姓名，城市，备注，工作地点，联系方式） 5）、日记（日期，地点，人物，事情） 6）、财务（标志，消费项目，消费时间，消费金额，剩余金额，总收入） 三、关系模型的函数依赖关系 1）、用户名——>密码 2）、（帐号，密码）——>姓名，（帐号，密码）——>年龄，（帐号，密码）——>出生日期，（帐号，密码）——>电话号码 3）、时间——>地点，时间——>事件 4）、姓名——>城市，姓名——>备注，姓名——>工作地点，姓名——>联系方式； 5）、日期——>地点，日期——>人物，日期——>事情 6）、标志——>消费时间，消费时间——>消费项目，消费时间——>消费金额，标志——>总收入，标志——>剩余金额。 其中6不是第一范式其他都是第一范式，且6为第二范式. 四、优化 1）、管理员（用户名，密码） 2）、个人（帐号，密码，姓名，年龄，出生日期，电话号码）3）、备忘录（时间，地点，事件） 4）、通讯录（姓名，城市，备注，工作地点，联系方式）5）、日记（日期，地点，人物，事情） 6）、财务（标志，消费时间，剩余金额，总收入） 消费（消费时间，消费项目，消费金额） 1、关系模型与ER模型：（一个关系就是一张二维表） 关系模式：→二维表 ER模型：→ER图 2、关系模型的基本概念： 教师（教师编号，A, B, 姓名，性别，所在系）--主表 课程（课程号，课程名，上课教师，教师编号）--从表 关系名：实体与实体间的联系 元组----记录---行（非空） 字段----数据项---列（属性） 键----关键字----标识属性（主键，外键，候选键） 主从关系：以该属性为主键的表就是主表，以该属性为外键的表就是从表。 3、将ER模型转换成二维表，以下面为例： ER模型： 实体： 教师（教师编号，姓名，性别，所在系） 课程（课程号，课程名，教师编号，上课教室） 学生（学号，姓名，年龄，班级） 联系： 讲授（教师编号，课程号） 选修（学号，课程号，成绩） 二维表： ①将实体转为关系表 （实体名--关系名，实体属性--关系属性，即列，实体键--关系键） ②将实体的联系转为关系表（关系模式） 1:1的联系--可以转为一个独立的关系模式，也可以与任一实体合并 1:n的联系--可以转为一个独立的关系模式，也可以与n端实体合并 m:n的联系--可以转为一个关系模式 3个或3个以上实体之间的多元化的联系--可以转为一个关系模式 相同的键的关系模式可以合并 4、关系规范化：（5个等级----5个范式-----1NF→5NF）Form ①规范化原因：消除不合适的数据依赖，即关系模式中会存在以下弊端： 数据重复（冗余） 数据不一致性 数据插入异常 数据删除异常…. ②范式规范化的判定条件： 1NF:实体中的属性不能再分解 实例： 学生1（学号，姓名，性别，出生日期，系部代码，入学时间，家庭成员）不属于1NF 更改后： 学生1（学号，姓名，性别，出生日期，系部代码，入学时间，家庭） 家庭（学号，家庭成员姓名，亲属关系） 2NF:实体中的非键属性完全依赖键属性 实例： 属于1NF，不属于2NF 分析： 系部代码----由学号决定，出生日期---由学号决定，成绩---由学号+课程号决定 更改后： 3NF:没有一个非键属性传递依赖于键（关键字→非关键字1....→非关键字n） 实例： 属于2NF 分析： 姓名，性别，出生日期，入学时间---由学号唯一决定 系部代码，系名，系宿舍楼----不是由学号唯一决定，相互递推出来不属于3NF （例如：系部代码----由学号或者系名或者系宿舍楼推出） 更改后： DATABASE-->TABLESPACES-->SEGMENTS-->EXENTS-->BLOCKS Oracle的逻辑存储结构单元从小到大依次分为数据块、区、段和表空间四种 数据块：由磁盘上特定数量的字节组成，是数据库中最小的逻辑存储单元，也是最小的I/O单元 区：有两个或更多个连续的数据块组成，是数据库中最小的存储分配单元。 段：是由若干个区形成的，是相同类型数据的存储分配区域 表空间：一个或多个数据文件的集合，通常由若干个相关联的段组成，是最大的逻辑存储单元，所有的表空间构成一个数据库。 表空间 一个表空间对应一个或多个数据文件，一个数据文件只能从属于一个表空间。 表空间是存储模式对象的容器，一个数据库对象只能存储在一个表空间中（分区表和分区索引除外），但可以存储在该表空间所对应的一个或多个数据文件中。 表空间管理的意义： 使用多个表空间，可以使得在执行数据库操作时非常方便灵活，比如： 可以控制整个数据库占用空间的大小、 可以控制用户所占用的存储空间的大小 用户数据与数据字典数据分开，减少I/O冲突 一个表空间脱机时，其他表空间保持联机 TABLESPACE(表空间）分类 PERMANENT 永久表空间 UNDO 撤销表空间 TEMPORARY 临时表空间 永久性表空间是指该表空间用于存放永久性数据库对象如SYSTEM系统表空间和USERS 用户表空间。 临时性表空间是指该表空间仅用于存放临时对象，任何永久性对象都不能驻留于临时表空间中。在建立用户时，如果不指定表空间，默认的临时表空间是TEMP。在数据库实例运行过程中，执行排序、管理索引和访问视图等操作时会产生大量的临时数据，这些临时数据将保存在临时表空间中。 撤销表空间存储撤销段(回退段)，由例程自动处理撤销表空间中的撤销段。这样可以减轻DBA的工作负担。撤销段主要用于显式或隐式的回退一个事务；从逻辑错误中恢复等方面 创建表空间 创建表空间可以使用OEM或利用CREATE TABLESPACE命令方式 需要注意的是，一般情况下，建立表空间是特权用户或是dba来执行的，如果用其它用户来创建表空间，则用户必须要具有create tablespace的系统权限。 OEM例：创建永久性表空间“Stu_space”，区管理方式为“本地管理”，状态为“读写”。其对应数据文件“stu01.dbf”大小为10MB，数据文件允许自动增长，增长增量大小为10MB，最大限制为100MB，其他参数采用默认值。 在建立数据库后，为便于管理表，最好建立自己的表空间 createtablespace data01 datafile 'd:\test\dada01.dbf' size 20m uniform size 128k; 说明：执行完上述命令后，会建立名称为data01 的表空间，并为该表空间建立名称为data01.dbf 的数据文件，区的大小为128k 使用数据表空间 create table mypart(deptno number(4), dname varchar2(14), loc varchar2(13)) tablespace data01; 表空间的管理方式： 重点是段的管理方式和区的管理方式是在建立表空间时确定的。 段管理方式有AUTO和MANUAL两种，区管理方式有本地管理和字典管理（已淘汰）两种。 SQL> select tablespace_name,contents ,extent_management,segment_space_management from dba_tablespaces; 建一个使用缺省值的表空间 SQL> create tablespace a datafile '/u01/oradata/timran11g/a01.dbf' size 10m; 段、区和块 段是表空间中指定类型的逻辑结构，由一个或多个区间组成。一个单独的表可以是一个段。按照段中存储数据的特征，可以将段分为4种类型：数据段、索引段、回退段和临时段。 区间是由一系列物理上连续的数据块组成的存储结构。在创建表时，Oracle将为表创建一个数据段，并为数据段分配一个初始区间。当向表中添加数据时，初始区中的块将逐渐被写满，写满后，Oracle将为数据段再分配一个新的区间。数据库设计各阶段
数据库逻辑结构设计
数据库逻辑结构设计
数据库逻辑结构大全(精)
数据库逻辑结构图
数据库-逻辑结构设计
数据库逻辑结构
相关主题
文本预览