Summary ADS Definitions
数据结构代考 Stack: last in, first out Push: to first free position in stack (at the top) Pop: retrieving the integer from the highest nonempty position
Stack:
last in, first out
Push: to first free position in stack (at the top)
Pop: retrieving the integer from the highest nonempty position
Struct: *array; top; size 
Functions:
– newStack
– doubleStackSize
– Push
– Pop
– isEmptyStack
– freeStack: free(st.array)
Queue: 数据结构代考
First in, First out
Enqueue: store item at the back end
Dequeue: return the item at the front end of the queue
Struct: *array; back; front; size
Functions:
– newQueue
– isEmptyQueue
– enqueue
– dequeue
– doubleQueueSize
– freeQueue: free(q.array)
Priority Queues:
removeMax: element with the highest priority value is chosen uses an ordered List or a heap
Queue from two stacks:
– enqueue: push item on stack0
– dequeue: push(pop(&(qp->stack0)), &(qp->stack1)); pop(&(qp->stack1))
Lists: 数据结构代考
Struct: item; next (List)
End of list: NULL-pointer
Functions:
– newEmptyList
– addItem
– listEmptyError
– firstItem
– removeFirstNode
– freeList
– listTooShort
– itemAtPos
– addItemAtPos
– removeItem
Stacks implemented with Lists:
Push: like addItem
Pop: firstItem + removeFirstNodeQueue implemented with Lists:
Enqueue: add new node at the end of the list
Dequeue: give lastNode pointer NULL
Traversing a list: visit each Node after each other
Ordered Lists:
– you can use it for implementing priority queues
– decreasing: removeMax = removeFirstNode
– enqueue: insertInOrder
Grammar:
[] = optional
{} = multiple times
| = alternatives
Scanning:
Functions:
– matchNumber
– matchCharacter
– *matchIdentifier
Get symbol etc.: (li->t).symbol
Trees: 数据结构代考
– They structure data hierarchically
– Binary tree: each node has at most 2 children
– Unary tree: at most one children à list!
– The number of edges = number of nodes – 1 (the root)
– Height (h) in general: 2^x nodes on level x ≤ h
– For every number h there is a binary tree with height h and 2^(h+1) – 1 nodes (“perfect binary
tree” à without gaps)
– Complete tree: all layers maximally filled and the last one maximally to the left
– Numbering node positions:
o Root: 1
o If node has position n: leftChild = 2n; rightChild = 2n + 1
o In an array: position 0 is not used!!!
– Traversing a tree:
o preOrder: t -> leftChild -> rightChild
o postOrder: leftChild -> rightChild -> t
o inOrder: leftChild -> t -> rightChild
– Search trees:
o The items have a linear order (or
lexicographical, if they are letters)
o LeftChild < node; RightChild > node
Heaps:
– Complete binary tree
– “For each node v, its descendants have a value ≤ the value in v.”
– Can be used for a priority queue (be careful with duplicates)
– Placing a value in a heap: adding the node + upheap
– Getting the biggest value: get the root, fill the gap + downheap
Tries:
– “Let a text T with length n be given. Then there is an auxiliary structure with size in O(n) so that
we can check in O(k) time (!) whether T contains an arbitrary pattern p with length k.”- Search speed doesn’t depend on n!
– Standard tries:
o No-initial-segment-property: “it does not contain words v and w such that v is an initial
segment of w.” à Example: v: house; w: houselord
o Root of T is empty
o Children of T contain different letters and are in
alphabetical order
o The branches in T from the root correspond exactly with
the word in W
o Memory for T: O(n)
– Compressed tries:
o Compressing the non-branching part of a branch into
one node
o Children of a node contain strings with different initial
letters
o There are no nodes with branching degree 1 (!!!)
o The branches from the root correspond exactly with the words in W
o The compressed trie contains at most 2m nodes (m = number of words)
o #Non-Leaves ≤ #Leaves
o Memory: O(m)
– Compact tries:
o Every node except the root contains two numbers referring to a string
o It is obtained from the compressed trie by replacing the strings in the nodes by their
coordinates
o An array (A) represents the collection of words
o Use: you can easily check if a pattern occurs as a prefix of one of the words in W
– Suffix tries: 数据结构代考
o “every substring of a string is the prefix of a suffix”
o it contains all substrings of a text
Expression trees:
– operator is placed before the two operants
– Example: +3*t7 à 3 + (t * 7)
Graphs:
– Consists of nodes and edges
– Cycle: same start- as endpoint
– Directed: edges have a direction
– G = (V,E) à V = #Nodes; E = #Edges
– Edges are parallel: they are incident with the same nodes
– Simple: no loops, nor parallel edges
– Loop: connects a node with itself
– Path: sequence of edges
– Length of a path: Number of nodes – 1
– Connected: every pair of nodes is connected by a path
– Euler:
o Path which crosses each edge exactly once
o At most two nodes have an odd degree
o Euler cycle: path with identical begin and end node
- “A connected graph has an Euler cycle if and only if all nodes have an even
degree.”
- “A connected graph has an Euler path if and only if at most two nodes have an
odd degree.”
– Directed graphs:
o have an initial and a terminal node- A connected graph without simple cycles is a tree!
– Trees with a root are called rooted trees
– Spanning tree: it is the minimal spanning subgraph of a connected graph which is a tree.
– Weighted: edges contain a number (weight)
Depth-first-search: (Applications)
– Finds a path between two nodes
– Checks whether a path is connected
– Checks whether a graph contains a cycle
– Finds a spanning tree for the graph
Breath-first-search:
– “BFS finds minimal paths from the starting node to the other nodes.”
Pseudocode:
– English text
– No type declarations
– No semicolons
– ß assign values to variables
– ‘=’ is used to compare values
– Block structure is indicated by indentation
(no {})
– The output of an algorithm is indicated by
return 数据结构代考
– Use /* */ for comments
