@chawuciren
2018-12-03T13:47:39.000000Z
字数 4100
阅读 627
rCSI
抽象数据类型和子程序
开始从简单的变量（不可分）过渡到数组。先说混合结构，在计算圈子中，这些抽象包含的叫做抽象数据结构。我们知道这些结构是什么，如何操作，和他们的正确性，却不知道这些操作是如何实现的。
接下来用到top-down的算法，把一个问题分成很多子问题。这一章用子问题的语句，让代码镜像决定和算法与子算法的交流。
ADT is a container whose properties (data and operation) are specified independently of any praticular implementation.If we have a useful structure, we can use it to reduce complexity, also we can use it to any where we want.
We view data from three part, application(user) level, logical(abstract) level, implementation level. The application level view of data is about a particular problem.The logical level is about abstract and operations that manipulate them. The implementation level is ptaricular representation of the structure that holds the data items and the coding of the operations in a programming language.This view sees the properties represented as specific data fields and subprograms. It is concerned with data structures, the implementation of a composite data field in an abstract data type.
Characteristic:"last in, first out"(LIFO)
Every time we take an item, only can we take the top, if the stack is empty, we are not allow to take item,because there is nothing. We call put an item in the stack "push", take an item in the stack "pop",and we also have to inspect whether the stack empty.
A queue is an abstract structure in which items are entered at one end and removed from the other end.
Characteristrc:"first in, first out"(FIFO)
Like a waiting line.
Insertions are made at the rear of the queue, and removals are made from the front of the queue.The items in the queue have the longest time, but in stack they have shortest time. Insertion operation call "enqueue", deletion operation call dequeue.(or remove)
List occur as naturally in programming as they do in real life. It has three charaterstics: homogeneous, linear and varying lengths.
Lists usually provide operations to insert an item(insert), delet(delete), check whether an item is there, getlength, view each item in sequece (reset getnext moreitems(都是得到下一个)).
But List is not array, it can be implemented in array, it is an abstract structure.
Like a family relation tree, we need a hierarchical(分级的) structure.
Each node is capable of two successor nodes, call children.The beginning of the tree is a unique starting node called the root.
Each node in the tree may have zero, one or two children. The node to the left of a node called its left child.If a node in tje tree have no children, it is a leaf.A node is ancestor of another node if it is the patrent of the node or the parent of some other ancestor（是所有的祖先，包括祖先的祖先的祖先的祖先。。。） of that node. The descendants of the node cintaining its children and children's children(是所有的后代，还有孩子的孩子的孩子。。。).It is a recursive definition.
Like a binary tree, it root's data is larger than left subtree, less than right tree.It is also a recursive definition.
If we have a data, we first compare it with left child's data, if it is larger than left child's data, we find the left child's right tree. (反之就找右边，如果没有最后走到NULL，否则都能找到)
The shape of the tree effect the effiency of a seach.The shape of a tree is determined by the order in which items are entered into the tree.
We have a set of name, and we put the first in the root, then compera the second with the root, if it is larger than root, put it in right child, if it is less, put it in left child. Then recursive.
The tree can should a people and a people whether parent and children,but can't show whether they are sister or brother.So we have grapes.
A grape have vertices and edges.
We have undirected grapes and directed grapes(digrape).One's edge has direct,another hasn't.
A weighted graph is one in which has value attach to each edge.
Understand the inherent semantics(内在语义) in all data structrue.(all use to retrieval检索)
How can I get to somewhere as my favourite?
We go into a path(node by node,can't pass a node), and go to the path's deepest before other choses.Use a stack to do it, we push the first node in stack,then pop it and find this node's adjacent node, push them into stack, then we find one amount them and go to deepest.
How can I get to somewhere use fewest flight?
We put the first node in the queue, if not find, we put all the adjacent node into the queue. And if we not find, we put all the adjacent's nodes into the queue.Finally we what we want is in the queue.(in this way we find all the path)
12.3
每个城市到每个城市的距离是不同的，经过最少的城市，不代表经过最短的距离。
所以即要存上相邻节点，还要存上节点之间的距离。
书上没有告诉我怎么做（只好瞎想）。
如果总距离是最短的，dp一下，只要所有的最优子结构都是最短的，总距离就是最短的（贪心不起作用）。
就是函数，有声名、参数、实参、形参，可以传递地址也可以传递值，如果传递值实际值不会被函数改变，如果是地址就可以改变，比如指针和链表。
谈到交换函数，链表的插入和删除，某一个值是否在链表里面。