如何自己构造_RecordsetPtr数据集_百度知道
如何自己构造_RecordsetPtr数据集
我要做一个水晶报表的开发，把数据集塞给水晶报表的时候是塞的一个_RecordsetPtr数据集，我想自己在程序中构造出一个数据集如何来做？我这样写的但是总是有错误，高手帮忙看看 _RecordsetPtr m_pR m_pRecordset.CreateInstance(&ADODB.Recordset&); m_pRecordset-&Fields-&_Append(&UserID&,adVarChar,100,adFldIsNullable); m_pRecordset-&Fields-&_Append(&GroupByName&,adVarChar,100,adFldIsNullable);m_pRecordset-&AddNew(); m_pRecordset-&PutCollect(&UserID&,_variant_t(&方忠君&)); m_pRecordset-&PutCollect(&GroupByName&,_variant_t(&方忠君1&)); MessageBox(&11&); while(!m_pRecordset-&adoEOF) {
_variant_t vID;
vID = m_pRecordset-&GetCollect(&UserID&);
MessageBox(_bstr_t(vID));
m_pRecordset-&MoveNext();
如果我自己构造数据集 就是不想用 _ConnectionPtr ，有什么办法没有
提问者采纳
没有 完整的代码 也不好说，不过一般与_ConnectionPtr 类型的变量一起用
m_pRecordSet-&Open(&SELECT * FROM car_info&,
// 查询DemoTable表中所有字段
m_pConnection.GetInterfacePtr(),
// 获取库接库的IDispatch指针_ConnectionPtr 类型变量
adOpenDynamic,
adLockOptimistic,
adCmdText);
提问者评价
谢谢。但是没有解决
其他类似问题
数据集的相关知识
您可能关注的推广回答者：
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁3. 选择键和索引(数据库逻辑设计)
键选择原则：
1) 键设计4 原则
为关联字段创建外键。
所有的键都必须唯一。
避免使用复合键。
外键总是关联唯一的键字段。
2) 使用系统生成的主键
设计数据库的时候采用系统生成的键作为主键，那么实际控制了数据库的索引完整性。这样，数据库和非人工机制就有效地控制了对存储数据中每一行的访问。采用系统生成键作为主键还有一个优点：当拥有一致的键结构时，找到逻辑缺陷很容易。
3) 不要用用户的键(不让主键具有可更新性)
在确定采用什么字段作为表的键的时候，可一定要小心用户将要编辑的字段。通常的情况下不要选择用户可编辑的字段作为键。
4) 可选键有时可做主键
把可选键进一步用做主键，可以拥有建立强大索引的能力。
索引使用原则：
索引是从数据库中获取数据的最高效方式之一。95%的数据库性能问题都可以采用索引技术得到解决。
1) 逻辑主键使用唯一的成组索引，对系统键(作为存储过程)采用唯一的非成组索引，对任何外键列采用非成组索引。考虑数据库的空间有多大，表如何进行访问，还有这些访问是否主要用作读写。
2) 大多数数据库都索引自动创建的主键字段，但是可别忘了索引外键，它们也是经常使用的键，比如运行查询显示主表和所有关联表的某条记录就用得上。
3) 不要索引memo/note 字段，不要索引大型字段(有很多字符)，这样作会让索引占用太多的存储空间。
4) 不要索引常用的小型表
不要为小型数据表设置任何键，假如它们经常有插入和删除操作就更别这样作了。对这些插入和删除操作的索引维护可能比扫描表空间消耗更多的时间。
4. 数据完整性设计(数据库逻辑设计)
1) 完整性实现机制：
实体完整性：主键
参照完整性：
父表中删除数据：级联删除;受限删除;置空值
父表中插入数据：受限插入;递归插入
父表中更新数据：级联更新;受限更新;置空值
dbms对参照完整性可以有两种方法实现：外键实现机制(约束规则)和触发器实现机制
用户定义完整性：
2) 用约束而非商务规则强制数据完整性
采用数据库系统实现数据的完整性。这不但包括通过标准化实现的完整性而且还包括数据的功能性。在写数据的时候还可以增加触发器来保证数据的正确性。不要依赖于商务层保证数据完整性;它不能保证表之间(外键)的完整性所以不能强加于其他完整性规则之上。
3) 强制指示完整性
在有害数据进入数据库之前将其剔除。激活数据库系统的指示完整性特性。这样可以保持数据的清洁而能迫使开发人员投入更多的时间处理错误条件。
4) 使用查找控制数据完整性
控制数据完整性的最佳方式就是限制用户的选择。只要有可能都应该提供给用户一个清晰的价值列表供其选择。这样将减少键入代码的错误和误解同时提供数据的一致性。某些公共数据特别适合查找：国家代码、状态代码等。
5) 采用视图
为了在数据库和应用程序代码之间提供另一层抽象，可以为应用程序建立专门的视图而不必非要应用程序直接访问数据表。这样做还等于在处理数据库变更时给你提供了更多的自由。
5. 其他设计技巧
1) 避免使用触发器
触发器的功能通常可以用其他方式实现。在调试程序时触发器可能成为干扰。假如你确实需要采用触发器，你最好集中对它文档化。
2) 使用常用英语(或者其他任何语言)而不要使用编码
在创建下拉菜单、列表、报表时最好按照英语名排序。假如需要编码，可以在编码旁附上用户知道的英语。
3) 保存常用信息
让一个表专门存放一般数据库信息非常有用。在这个表里存放数据库当前版本、最近检查/修复(对access)、关联设计文档的名称、客户等信息。这样可以实现一种简单机制跟踪数据库，当客户抱怨他们的数据库没有达到希望的要求而与你联系时，这样做对非客户机/服务器环境特别有用。
4) 包含版本机制
在数据库中引入版本控制机制来确定使用中的数据库的版本。时间一长，用户的需求总是会改变的。最终可能会要求修改数据库结构。把版本信息直接存放到数据库中更为方便。
5) 编制文档
对所有的快捷方式、命名规范、限制和函数都要编制文档。
采用给表、列、触发器等加注释的数据库工具。对开发、支持和跟踪修改非常有用。
对数据库文档化，或者在数据库自身的内部或者单独建立文档。这样，当过了一年多时间后再回过头来做第2 个版本，犯错的机会将大大减少。
6)测试、测试、反复测试
建立或者修订数据库之后，必须用用户新输入的数据测试数据字段。最重要的是，让用户进行测试并且同用户一道保证选择的数据类型满足商业要求。测试需要在把新数据库投入实际服务之前完成。
7) 检查设计
在开发期间检查数据库设计的常用技术是通过其所支持的应用程序原型检查数据库。换句话说，针对每一种最终表达数据的原型应用，保证你检查了数据模型并且查看如何取出数据。
1&&&&&Tags：
看了“在应用环境中如何构造最优的数据库模式（三）”的网友还看了:
数据库设计(Database Design)的概念：数据库设计是指对于一个给定的应用环境，构造最优的数据库模式，建立数据库及其应用系统，使之能够有效地存储数据，满足各种用户的应用需求(信息要求和处理要求)。(在数据库领域内，经常把使用数据库的各类系统统称为数据库应用系统)。一、数据库和信息系统…… - [] - []
4.物理设计阶段：根据DBMS特点和处理的需要，进行物理存储安排，建立索引，形成数据库内模式六、数据库设计技巧1. 设计数据库之前(需求分析阶段)1) 理解客户需求，询问用户如何看待未来需求变化。让客户解释其需求，而且随着开发的继续，还要经常询问客户保证其需求仍然在开发的目的之中。2) 了解企…… - [] - []
上一篇文章： 下一篇文章：
&相关MSSQL文章6.4 FORMALIZING THE SPECIFICATION
The glimpse of data abstraction presented so far is too informal to be of durable use. Consider again our staple example: a stack, as we now understand it, is defined in terms of the a but then we need to define these operations!
Informal descriptions as above (put pushes an element “on top of ” the stack, remove pops the element “last pushed” and so on) do not suffice. We need to know precisely how these operations can be used by clients, and what they will do for them.
(putremove)
An abstract data type specification will provide this information. It consists of four paragraphs, explained in the next sections:
o FUNCTIONS.
o PRECONDITIONS.
These paragraphs will rely on a simple mathematical notation for specifying the properties of an abstract data type (ADT for short).
The notation — a mathematical formalism, not to be confused with the software notation of the rest of this book even though for consistency it uses a similar syntactic style — has no name and is not a
it could serve as the starting point for a formal specification language, but we shall not pursue this avenue here, being content enough to use self-explanatory conventions for the unambiguous specification of abstract data types.
Specifying types
The TYPES paragraph indicates the types being specified. In general, it may be convenient to specify several ADTs together, although our example has only one, STACK.
By the way, what is a type? The answer to this question will combine all the ideas developed in the
a type is a collection of objects characterized by functions, axioms and preconditions. If for the moment you just view a type as a set of objects, in the mathematical sense of the word “set” — type STACK as the set of all possible stacks, type INTEGER as the set of all possible integer values and so on — you are not guilty of any terrible misunderstanding. As you read this discussion you will be able to refine this view. In the meantime the discussion will not be too fussy about using “set” for “type” and conversely.
setSTACKINTEGER””””
On one point, however, you should make sure to avoid any confusion: an abstract data type such as STACK is not an object (one particular stack) but a collection of objects (the set of all stacks). Remember what our real goal is: finding a good basis for the modules of our software systems. As was noted in the previous chapter, basing a module on one particular object — one stack, one airplane, one bank account — would not make sense. O-O design will enable us to build modules covering the properties of all stacks, all airplanes, all bank accounts — or at least of some stacks, airplanes or accounts.
An object belonging to the set of objects described by an ADT specification is called an instance of the ADT. For example, a specific stack which satisfies the properties of the STACK abstract data type will be an instance of STACK. The notion of instance will carry over to object-oriented design and programming, where it will play an important role in explaining the run-time behavior of programs.
ADTADTinstanceSTACKSTACK
The TYPES paragraph simply lists the types introduced in the specification. Here:
Our specification is about a single abstract data type STACK, describing stacks of objects of an arbitrary type G.
Genericity
In STACK [G], G denotes an arbitrary, unspecified type. G is called a formal generic parameter of the abstract data type STACK, and STACK itself is said to be a generic ADT. The mechanism permitting such parameterized specifications is we already encountered a similar concept in our review of package constructs.
STACK [G]GGSTACK(formal generic parameter)STACKADT
It is possible to write ADT specifications without genericity, but at the price of unjustified repetition. Why have separate specifications for the types “stack of bank accounts”, “stack of integers” and so on? These specifications would be identical except where they explicitly refer to the type of the stack elements — bank accounts or integers. Writing them, and then performing the type substitutions manually, would be tedious. Reusability is desirable for specifications too — not just programs! Thanks to genericity, we can make the type parameterization explicit by choosing some arbitrary name, here G, to represent the variable type of stack elements.
As a result, an ADT such as STACK is not quite a type, but r to obtain a directly usable stack type, you must obtain some element type, for example ACCOUNT, and provide it as actual generic parameter corresponding to the formal parameter G. So although STACK is by itself just a type pattern, the notation STACK [ACCOUNT] is a fully defined type. Such a type, obtained by providing actual generic parameters to a generic type, is said to be generically derived.
ADTSTACKACCOUNTGactual generic parameterSTACKSTACK [ACCOUNT]generically derived
The notions just seen are applicable recursively: every type should, at least in principle, have an ADT specification, so you may view ACCOUNT as being itself a also, a type that you use as actual generic parameter to STACK (to produce a generically derived type) may itself be generically derived, so it is perfectly all right to use STACK [STACK [ACCOUNT]] specifying a certain abstract data type: the instances of that type are stacks, whose elements a the elements of these latter stacks are bank accounts.
ADTACCOUNTSTACK
STACK [STACK [ACCOUNT]]
As this example shows, the preceding definition of “instance” needs some qualification. Strictly speaking, a particular stack is an instance not of STACK (which, as noted, is a type pattern rather than a type) but of some type generically derived from STACK, for example STACK [ACCOUNT]. It is convenient, however, to continue talking about instances of STACK and similar type patterns, with the understanding that this actually means instances of their generic derivations.
STACKSTACKSTACK [ACCOUNT]STACK
Similarly, it is not quite accurate to talk about STACK being an ADT: the correct term is “ADT pattern”. For simplicity, this discussion will continue omitting the word “pattern” when there is no risk of confusion.
STACKADTADT
The distinction will carry over to object-oriented design and programming, but there we will need to keep two separate terms:
oThe basic notion will be the class; a class may have generic parameters.
oDescribing actual data requires types. A non-generic class is also a type, but a generic class is only a type pattern. To obtain an actual type from a generic class, we will need to provide actual generic parameters, exactly as we derive the ADT STACK [ACCOUNT] from the ADT pattern STACK.
·typesADTSTACKSTACK [ACCOUNT]
Later chapters will explore the notion of genericity as applied to classes, and how to combine it with the inheritance mechanism.
Listing the functions
After the TYPES paragraph comes the FUNCTIONS paragraph, which lists the operations applicable to instances of the ADT. As announced, these operations will be the prime component of the type definition — describing its instances not by what they are but by what they have to offer.
TYPESFUNCTIONSADT
Below is the FUNCTIONS paragraph for the STACK abstract data type. If you are a software developer, you will find the style familiar: the lines of such a paragraph evoke the declarations found in typed programming languages such as Pascal or Ada. The line for new resembles a
the others resemble routine headers.
STACKdeclarationsPascalAdanew
Each line introduces a mathematical function modeling one of the operations on stacks. For example function put represents the operation that pushes an element onto the top of a stack.
Why functions? Most software people will not naturally think of an operation such as put as a function. When the execution of a software system applies a put operation to a stack, it will usually modify that stack by adding an element to it. As a result, in the above informal classification of commands, put was a “command” — an operation which may modify objects. (The other two categories of operations were creators and queries).
putputputcommand
An ADT specification, however, is a mathematical model, and must rely on wellunderstood mathematical techniques. In mathematics the notion of command, or more generally of changing something, do computing the square root of the number 2 does not modify the value of that number. A mathematical expression simply defines certain mathematical objects in terms of certain other mathematical objects: unlike the execution of software on a computer, it never changes any mathematical object.
Yet we need a mathematical concept to model computer operations, and here the notion of function yields the closest approximation. A function is a mechanism for obtaining a certain result, belonging to a certain target set, from any possible input belonging to a certain source set. For example, if R denotes the set of real numbers, the function definition
square_plus_one: R (R) R
square_plus_one (x) = x2 + 1 (for any x in R)
introduces a function square_plus_one having R as both source and target sets, and yielding as result, for any input, the square of the input plus one.
square_plus_one: R (R) R
square_plus_one (x) = x2 + 1 (for any x in R)
square_plus_oneR
The specification of abstract data types uses exactly the same notion. Operation put, for example, is specified as put: STACK [G] ? G (R) STACK [G] which means that put will take two arguments, a STACK of instances of G and an instance of G, and yield as a result a new STACK [G]. (More formally, the source set of function put is the set STACK [G] ? G, known as the cartesian product of STACK [G] and G; this is the set of pairs &s, x& whose first element s is in STACK [G] and whose second element x is in G.) Here is an informal illustration:
put put: STACK [G] ? G (R) STACK [G] GSTACKGSTACK [G]putSTACK [G] ? GSTACK [G]G(cartesian product)&s, x&sSTACK [G]xG
With abstract data types, we only have functions in the mathematic they will produce neither side effects nor in fact changes of any kind. This is the condition that we must observe to enjoy the benefits of mathematical reasoning.
When we leave the ethereal realm of specification for the rough-and-tumble of software design and implementation, we will need to reintroduce
because of the performance overhead, few people would accept a software execution environment where every “push” operation on a stack begins by duplicating the stack. Later we will examine the details of the transition from the change-free world of ADTs to the change-full world of software development. For the moment, since we are studying how best to specify types, the mathematical view is the appropriate one.
The role of the operations modeled by each of the functions in the specification of STACK is clear from the previous discussion:
o Function put yields a new stack with one extra element pushed on top. The figure on the preceding page illustrates put (s, x) for a stack s and an element x.
putsxput (s, x)
o Function remove yields a new stack with the top element, if any, like put, this function should yield a command (an object-changing operation, typically implemented as a procedure) at design and implementation time. We will see below how to take into account the case of an empty stack, which has no top to be popped.
o Function item yields the top element, if any.
o Function empty indicates whet its result is a boolean value (true or false); the ADT BOOLEAN is assumed to have been defined separately.
emptytruefalseADT BOOLEAN
o Function new yields an empty stack.
The FUNCTIONS paragraph does not fully de it only introduces their signatures — the list of their argument and result types. The signature of put is
STACK [G] ? G (R) STACK [G]
indicating that put accepts as arguments pairs of the form &s, x& where s is an instance of STACK [G] and x is an instance of G, and yields as a result an instance of STACK [G]. In principle the target set of a function (the type that appears to the right of the arrow in signature, here STACK [G]) may itself be this can be used to describe operations that return two or more results. For simplicity, however, this book will only use single-result functions.
(signatures)
STACK [G] ? G (R) STACK [G]
put&s, x&sSTACK [G]xGSTACK [G]STACK [G]
The signature of functions remove and item includes a crossed arrow instead of the standard arrow used by put and empty. This notation expresses that the functions are not applicable to all membe it will be explained in detail below.
removeitemputempty
The declaration for function new appears as just
new: STACK
with no arrow in the signature. This is in fact an abbreviation for
new: (R) STACK
introducing a function with no arguments. There is no need for arguments since new must always return the same result, an empty stack. So we just remove the arrow for simplicity. The result of applying the function (that is to say, the empty stack) will also be written new, an abbreviation for new ( ), meaning the result of applying new to an empty argument list.
new: STACK
new: (R) STACK
newnew ( )new
Function categories
The operations on a type were classified informally at the beginning of this chapter into creators, queries and commands. With an ADT specification for a new type T, such as STACK [G] in the example, we can define the corresponding classification in a more rigorous way. The classification simply examines where T appears, relative to the arrow, in the signature of each function:
TADTSTACK [G]T
o A function such as new for which T appears only to the right of the arrow is a creator function. It models an operation which produces instances of T from instances of other types — or, as in the case of a constant creator function such as new, from no argument at all. (Remember that the signature of new is considered to contain an implicit arrow.)
newTcreator functionTnewnew
o A function such as item and empty for which T appears only on the left of the arrow is a query function. It models an operation which yields properties of instances of T, expressed in terms of instances of other types (BOOLEAN and the generic parameter G in the examples).
itememptyT(query function)TBOOLEANG
o A function such as put or remove for which T appears on both sides of the arrow is a command function. It models an operation which yields new instances of T from existing instances of T (and possibly instances of other types).
putremoveT(command function)TT
An alternative terminology calls the three categories “constructor”, “accessor” and “modifier”. The terms retained here are more directly related to the interpretation of ADT functions as models of operations on software objects, and will carry over to class features, the software counterparts of our mathematical functions.
(constructor)(accessor)(modifier)ADT
The AXIOMS paragraph
We have seen how to describe a data type such as STACK through the list of functions applicable to its instances. The functions are known only through their signatures.
To indicate that we have a stack, and not some other data structure, the ADT specification as given so far is not enough. Any “dispenser” structure, such as a first-in first-out queue, will also satisfy it. The choice of names for the operations makes this particularly clear: we do not even have stack-specific names such as push, pop or top to fool ourselves into believing that we have defined stacks and only stacks.
ADTpushpoptop
This is not surprising, of course, since the FUNCTIONS paragraph declared the functions (in the same way that a program unit may declare a variable) but did not fully define them. In a mathematical definition such as the earlier example
square_plus_one: R (R) R
square_plus_one (x) = x2 + 1 (for any x in R)
the first line plays the role of the signature declaration, but there is also a second line which defines the function’s value. How do we achieve the same for the functions of an ADT?
FUNCTION()
square_plus_one: R (R) R
square_plus_one (x) = x2 + 1 ( R x)
Here we should not use an explicit definition in the style of the second line of square_ plus_one’s definition, because it would force us to choose a representation — and this whole discussion is intended to protect us from representation choices.
square_ plus_one
Just to make sure we understand what an explicit definition would look like, let us write one for the stack representation ARRAY_UP as sketched above. In mathematical terms, choosing ARRAY_UP means that we consider any instance of STACK as a pair &count, representation&, where representation is the array and count is the number of pushed elements. Then an explicit definition of put is (for any instance x of G):
put (&count, representation&, x) = &count + 1, representation [count+1: x]&
where the notation a [n: v] denotes the array obtained from a by changing the value of the element at index n so that it is now v, and keeping all other elements, if any, as they are.
ARRAY_UPARRAY_UPSTACK&count, representation&representationcountput(Gx)
put (&count, representation&, x) = &count + 1, representation [count+1: x]&
a [n: v]anv
This definition of function put is just a mathematical version of the implementation of the put operation sketched in Pascal notation, next to representation ARRAY_UP, in the picture of possible stack representations at the beginning of this chapter.
putPascalputARRAY_UP
But this “Free us from the yoke of representations!”, the motto of the Object Liberation Front and its military branch (the ADT brigade), is also ours.
”!”(ADT)
Because any explicit definition would force us to select a representation, we must turn to implicit definitions. We will refrain from giving the values of the functions of an ADT instead we will state properties of these values — all the properties that matter, but those properties only.
(implicit definition)ADT
The AXIOMS paragraph states these properties. For STACK it will be:
AXIOMSSTACK
The first two axioms express the basic LIFO (last-in, first-out) property of stacks. To understand them, assume we have a stack s and an instance x, and define s' to be put (s, x), that is to say the result of pushing x onto s. Adapting an earlier figure:
LIFO(last-in, first-out)sxs'put (s, x)xs
Here axiom A1 tells us that the top of s' is x, the last el and axiom A2 tells us that if we remove the top element from s', we get back the stack s that we had before pushing x. These two axioms provide a concise description of the fundamental property of stacks in pure mathematical terms, without any recourse to imperative reasoning or representation properties.
A1s'xA2s'xs
Axioms A3 and A4 tell us when a stack is empty and when it is not: a stack resulting from the creator function new
any stack resulting from pushing an element on an existing stack (empty or not) is non-empty.
These axioms, like the others, are predicates (in the sense of logic), expressing that a certain property is always true for every possible value of s and x. Some people prefer to read A3 and A4 in the equivalent form
under which you may also view them, informally at least, as defining function empty by induction on the size of stacks.
Two or three things we know about stacks
ADT specifications are implicit. We have encountered two forms of implicitness:
ADT(implicit)
o The ADT method defines a set of objects implicitly, through the applicable functions. This was described above as defining objects by what they have, not what they are. More precisely, the definition never implies that the operations list when it comes to a representation, you will often add other operations.
o The functions themselves are also defined implicitly: instead of explicit definitions (such as was used for square_plus_one, and for the early attempt to define put by reference to a mathematical representation), we use axioms describing the functions’ properties. Here too there is no claim of exhaustiveness: when you eventually implement the functions, they will certainly acquire more properties.
square_plus_oneput
This implicitness is a key aspect of abstract data types and, by implication, of their future counterparts in object-oriented software construction — classes. When we define an abstract data type or a class, we always talk about the type or class: we simply list the properties we know, and take these as the definition. Never do we imply that these are the only applicable properties.
Implicitness implies openness: it should always be possible to add new properties to an ADT or a class. The basic mechanism for performing such extensions without damaging existing uses of the original form is inheritance.
The consequences of this implicit approach are far-reaching. The “supplementary topics” section at the end of this chapter will include more comments about implicitness.
Partial functions
The specification of any realistic example, even one as basic as stacks, is bound to encounter the problems of undefined operations: some operations are not applicable to every possible element of their source sets. Here this is the case with remove and item: you cannot pop an element and an empty stack has no top.
removeitem
The solution used in the preceding specification is to describe these functions as partial. A function from a source set X to a target set Y is partial if it is not defined for all members of X. A function which is not partial is total. A simple example of partial function in standard mathematics is inv, the inverse function on real numbers, whose value for any appropriate real number x is
XXY(Total Function)invx
Because inv is not defined for x = 0, we may specify it as a partial function on R, the set of all real numbers:
invx = 0RR
To indicate that a function may be partial, the notation uses the crossed arrow
; the normal arrow (R) will be reserved for functions which are guaranteed to be total.
The domain of a partial function in &is the subset of X containing those elements for which the function yields a value. Here the domain of inv is R – {0}, the set of real numbers other than zero.
(domain)XinvR – {0}
The specification of the
ADT applied these ideas to stacks by declaring put and item as partial functions in the FUNCTIONS paragraph, as indicated by the crossed arrow in their signatures. This raises a new problem, discussed in the next section: how to specify the domains of these functions.
FUNCTIONSputitemSTACK ADT:
In some cases it may be desirable to describe put as a
this is necessary to model implementations such as ARRAY_UP and ARRAY_DOWN, which only support a finite number of consecutive put operations on any given stack. It is indeed a good exercise to adapt the specification of STACK so that it will describe bounded stacks with a finite capacity, whereas the above form does not include any such capacity restriction. This is a new use for partial functions: to reflect implementation constraints. In contrast, the need to declare item and remove as partial functions reflected an abstract property of the underlying operations, applicable to all representations.
, putARRAY_UPARRAY_DOWNputSTACK itemremove
Preconditions
Partial functions are an inescapable fact of software development life, merely reflecting the observation that not every operation is applicable to every object. But they are also a potential source of errors: if f is a partial function from X to Y, we are not sure any more that the expression f (e) makes sense even if the value of e is in X: we must be able to guarantee that the value belongs to the domain of f.
fXYf (e)eXf
For this to be possible, any ADT specification which includes partial functions must specify the domain of each of them. This is the role of the PRECONDITIONS paragraph.
ADTPRECONDITIONS
For STACK, the paragraph will appear as:
对于STACK，这段显示如下：
where, for each function, the require clause indicates what conditions the function’s arguments must satisfy to belong to the function’s domain.
The boolean expression which defines the domain is called the precondition of the corresponding partial function. Here the precondition of both remove and item expresses that the stack argument must be non-empty. Before the require clause comes the name of the function with dummy names for arguments (s for the stack argument in the example), so that the precondition can refer to them.
preconditionremoveitemrequire(s)
Mathematically, the precondition of a function f is the characteristic function of the domain of f. The characteristic function of a subset A of a set X is the total function ch: X (R) BOOLEAN such that ch (x) is true if x belongs to A, false otherwise.
ff(characteristic function)XAch: X (R) BOOLEANxAch (x)
The complete specification
The PRECONDITIONS paragraph concludes this simple specification of the STACK abstract data type. For ease of reference it is useful to piece together the various components of the specification, seen separately above. Here is the full specification:
PRECONDITIONSSTACK
Nothing but the truth
The power of abstract data type specifications comes from their ability to capture the essential properties of data structures without overspecifying. The stack specification collected on the preceding page expresses all there is to know about the notion of stack in general, excluding anything that only applies to some particular representations of stacks. All th yet nothing but the truth.
This provides a general model of computation with data structures. We may describe complex sequences of operations by mathematical expressions enjoying the usual p and we may view the process of carrying out the computation (executing the program) as a case of algebraic simplification.
In elementary mathematics we have been taught to take an expression such as
cos2 (a – b) + sin2 (a + b – 2 ? b)
and apply the rules of algebra and trigonometry to simplify it. A rule of algebra tells us that we may simplify a + b – 2 ? b into a – b for any a and b; and a rule of trigonometry tells us that we can simplify cos2 (x) + sin2 (x) into 1 for any x. Such r for example the combination of the two preceding rules allow us to simplify the above expression into just 1.
cos2 (a – b) + sin2 (a + b – 2 ? b)
aba + b – 2 ? ba – bxcos2 (x) + sin2 (x)11
In a similar way, the functions defined in an abstract data type specification allow us to construct possibly and the axioms of the ADT allow us to simplify such expressions to yield a simpler result. A complex stack expression is the mathematical equ the simplification process is the mathematical equivalent of a computation, that is to say, of executing such a program.
Here is an example. With the specification of the STACK abstract data type as given above, we can write the expression
item (remove (put (remove (put (put (
remove (put (put (put (new, x1), x2), x3)),
item (remove (put (put (new, x4), x5)))), x6)), x7)))
Let us call this expression for future reference. It is perhaps easier to understand stackexp if we define it in terms of a sequence of auxiliary expressions:
stackexpstackexp
s2 = put (put (put (s1, x1), x2), x3)
s3 = remove (s2)
s5 = put (put (s4, x4), x5)
s6 = remove (s5)
y1 = item (s6)
s7 = put (s3, y1)
s8 = put (s7, x6)
s9 = remove (s8)
s10 = put (s9, x7)
s11 = remove (s10)
stackexp = item (s11)
Whichever variant of the definition you choose, it is not hard to follow the computation of which stackexp is a mathematical model: push elements x1, x2, x3, in this order, remove the last pushed element (x3), calling s3
create and so on. Or you can think of it graphically:
stackexp& x1, x2, x3(x3)s3
You can easily find the value of such an ADT expression by drawing figures such as the above. (Here you would find x4.) But the theory enables you to obtain this result formally, without any need for pictures: just apply the axioms repeatedly to simplify the expression until you cannot simplify any further. For example:
o Applying A2 to simplify s3, that is to say remove (put (put (put (s1, x1), x2), x3)), yields put (put (s1, x1), x2)). (With A2, any consecutive remove-put pair cancels out.)
A2s3remove (put (put (put (s1, x1), x2), x3))put (put (s1, x1), x2))A2remove-put
o The same axiom indicates that s6 is put (s4, x4); then we can use axiom A1 to deduce that y1, that is to say item (put (s4, x4)), is in fact x4, showing that (as illustrated by the arrow on the above figure) s7 is obtained by pushing x4 on top of s3.
s6put (s4, x4)A1y1item (put (s4, x4))x4x4s3s7
And so on. A sequence of such simplifications, carried out as simply and mechanically as the simplifications of elementary arithmetic, yields the value of the expression stackexp, which (as you are invited to check for yourself by performing the simplification process rigorously) is indeed x4.
stackexpx4
This example gives a glimpse of one of the main theoretical roles of abstract data types: providing a formal model for the notion of program and program execution. This model is purely mathematical: it has none of the imperative notions of program state, variables whose values may change in time, or execution sequencing. It relies on the standard expression evaluation techniques of ordinary mathematics.
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：48203次
排名：千里之外
原创：29篇
评论：62条
(1)(1)(1)(2)(1)(1)(2)(1)(3)(1)(3)(1)(3)(3)(1)(1)(2)(1)(5)(1)(1)(2)