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


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 


– 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


– 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


– 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


[] = optional

{} = multiple times

| = alternatives



– 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


– 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


– “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


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


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)


– 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


  • 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


– “BFS finds minimal paths from the starting node to the other nodes.”



– 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