AI 摘要

这是数据结构基础的课堂笔记喵。本课程是信息安全大一下专业课。

FDS

1 Algorithm Complexity Analysis

1.1 The Max-subsequence Sum Problem

Attentionally: If the max-sum is negative. We define that the max sum is 0.

1.1.1 $   latex T(N)=O(N^3)$ Method:

/*
temp for now
need appendix
*/

1.1.2. $T(N)=O(N^2)$ Method:

for(i=0;i<n;i++){
thisSum=0;
for(j=i;j<n;j++){ thisSum+=seq[j]; if(thisSum>max){
max=thisSum;
}
}
}

1.1.3. $T(N)=O(NlogN)$ Method: Divide and Conquer

1.1.4. $T(N)=O(N)$ Method: Dynamic Planning

The transition state equation are as follows:

$$max[i]=max(seq[i]+max[i-1],seq[i])\newline ans=max(max[i])$$

1.2 Sample of $O(logN)$ Algorithm

1.2.1 The Binary Search

To find an exact number in a sorted squence, we could use the binary search.

1.3 Checking Your Analysis

  1. Double the dataset, and see if the runtime doubles.
  2. Use the limit analysis.

2 Data Structure: List/Queue/Stack

2.1 Abstract Data Structure

Definition: $$Data Type={Objects}+{Operations}$$

An ADT means specifications on the objects and oprations have nothing to do with the representation of the type and the implementation of the operations.

2.2 The List ADT

Objects: ${item_0,item_1…item_{N-1}}$ Operations:

  • Finding the length
  • Printing
  • Making an rm
  • finding the k-th item
  • insert a new item after the k-th item
  • delete an item
  • finding next of the current item
  • find previous of the current item

2. 3 Simple Implementation of List

2.3.1 Array: a sequential mapping

Negatives

  • Maxsize has to be estimated
  • Insetion and Deletion take $T(N)=O(N)$

Poaitives

  • Find k-th is $O(1)$

2.3.2 Linked Lists: a discrete mapping

It needs a head while each unit contains address, data, pointer. Initialization:

typedef struct list_node *listPtr;
typedef struct list_node{
char data[4];
listPtr next;
};
listPtr ptr;
2.3.2.1 Insertion
//to insert the data k to a node in a linked list
temp->data=k;
temp->next=node->next;
node->next=temp;
//an inelegant way to change the head node
temp->next=head;
head=temp;
//an elegant way
//set a pre node than use the first way
2.3.2.2 Deletion
//set a dummy-head node
pre->next=node->next;
free(node);
2.3.2.3 Doubly Linked Circular Link

Compared to the normal linked list, a unit in the doubly linked circular link extraly contains a pre-pointer.

typedef struct list_node *listPtr;
typedef struct list_node{
element item;
listPtr next;
listPtr pre;
};
listPtr ptr;
//ptr=ptr->pre->next=ptr->next->pre

Specially, the dummy-head node’s left pointer points to the last item, and the last node’s right pointer points to the dummy-head node. A single-item doubly linked circular list’s left and right pointers point to itself.

2.3.3 Sample1: Polynomial ADT

Objeccts: pairs of $<e_i,a_i>$ where $e_i$ refers to the exponent and the $a_i$ is the coefficient.

Representations:

  1. By use a struct contains $e_i$ and $a_i$.
typedef struct{
int CoeffArray[maxDegree+1];
int highPower;
} *Poly;

Positives: easy to access most operations like addition and multiplication. Negatives: the complexicty of multiplication is $O(N^2)$ , and most operations are meaningless for they are 0 in CoeffArray.

  1. By use a linked lists.
typedef struct{
int Coeff;
int highPower;
*Poly next;
} *Poly;

Positives: very fast in multiplication and save memories. Negatives: hard to operate addition.

2.3.4 Multilists

Suppose that we have 40,000 students and 2,500 courses. Print the students’ name list for each course, and print the registered classes’ list for each student. How to represent this structure?

Homework: Self-study the sparce-matrix linked list.

2.4 Cursor Implementation of Linked Lists(no pointer)

2.5 Implementation of A Stack

2.5.1 Linked Lists with a Dummy-header

Push:

tmpCell->Next = Dummy-Header -> Next
Dummy-Header -> Next = tmpCell

Top:

return Dummy-Header -> Element

Pop:

FirstCell = Dummy-Header -> Next
Dummy-Header -> Next = Dummy-Header -> Next ->Next
free(FirstCell)

Frequent malloc() and free() takes much time, so create a list as a recycling bin.

2.5.2 Array Implementation

Definition:

struct StackRecord{
int capacity;
int topOfStack
elementType *Array;
};

Push/Pop:

topOfStack ++/--;

Attention: As a regularity, when using the function, calling the function instead of operate on the topOfStack.

2.6 Applications of Stacks

2.6.1 Balancing Symbols

Check if parenthesis (), blankets [], and braces {} are balanced.

make an empty stack s
while(reading character c)
if c is an opening: push(c,s)
else if c is a closing:
if(s is empty) error
else{
if(top(s) doesn't match) error
else pop(s)
}
if(s is not empty) error

2.6.2 Postfix Evaluation

Postfix evaluation:

$$opreand1\ operand2\ oprator = operand1\ operator\ operand2$$

Implementation:

make an empty stack s
while(read the character a)
a is a operand: push(s,a)
a is an operator:
op1=pop();op2=pop();
op3=op2 a op1;
push(op3,s)

2.6.3 Function Calls

2.7 The Queue ADT

2.7.1 ADT

A queue is a First-in-First-out list. Important Operations:

  • Enqueue
  • dequeue
  • Front

2.7.2 Array Implementation

Definition:

struct QUueueRecord{
int Capacity; //max size of the queue
int Front; //the front pointer
int rear; //the rear pointer
int Size;//optional the current size of the queue
ElementType *Array;
};

2.7.3 Application - Job Scheduling

make an empty queue q
while( job )
enqueue( job, q )
rear + 1
if( q[front] is over )
dequeue
front+1

When the rear reaches the end, there is still space in front of the front, so to save the space, we use circular queue.

2.7.4 Circular Queue

make a 3-item circular queue;
rear=0;front=1;//empty queue
enqueue job1;rear=(rear+1)%3;
enqueue job2;rear=(rear+1)%3;
enqueue job3;rear=(rear+1)%3;
// to compare the rare and front to judge if the stack is full
// add variable Size to judge easily

3 Tree

3.1 Definition

A tree is a collection of nodes. The collection canbe empty; otherwise, a tree consists of:

  • a distinguishied node r, called the root
  • and zero or more nonempty trees $T_1…T_n$, each os whose roots are connected by a directed edge from r

Note that:

  • Subtress must not connect each other. Therefore every node is the root
  • There are $N-1$ edge in a N-node tree
  • Normally the root is drawn at the top

Definitions of a tree:

  • Degree of a node: number of subtrees of the node
  • Degree of a tree: max degree of all the nodes
  • Parent: a node that has subtree(s)
  • Children: the roots of the subtrees of a parent
  • Siblings: children of the same oarent
  • Leaf: nonroot nodes that have no children
  • Path from $n_i$ to $n_k$: a unique sequence of nodes
  • Length of the path: number of edges on the path
  • Depth of $n_i$: length of the path from root to $n_i$
  • Height of $n_i$: length of the longest path from $n_i$ to a leaf
  • Height(Depth) of a tree: height(root) = depth(deepest leave)
  • Ancestors of a node: all the nodes along the path from the node up to the root
  • Descendants of a node: all the nodes in the subtree(s)

3.2 Implementations

3.2.1 FC-NS Represenation

To implement the FirstChild-NextSibling representation, each node contains a its first child. and a pointer to its next sibling, however this representation is not unique.

3.2.2 Binary tree

To store a binary tree, each node contains a left and right pointer to its children.

3.2.2.1 Applications
Expression trees

Example: Given a infix expression $(a+b)\times(c\times(d+e))$ for example.

  • transform it into a postfix expression: $a\ b\ +\ c\ d\ e\ +\ \times\ \times\ $
  • Use a stack, push it in and create a leaf node when entering an operand, pop out two operands out when entering an operator, and connect its left and right pointer with the openrands, connect the parent pointer of the two operands to the operator.
  • After the operation, all the parent nodes are operators, and all the leaves are operands.

3.2.3 Tree Traversals

Visit each node exactly once.

Preorder Traversal
void preOrder( tree_ptr, tree){
if(tree){
visit(tree);
for(each child C of tree)
preOrder(C);
}
}
Leveloreder Traversal
void leveltOrder( tree_ptr, tree){
enqueue(tree);
while(queue is not empty){
visit(T=dequeue());
for(each child of T)
enqueue(C);
}
}
Postorder Traversal
void postOrder( tree_ptr, tree){
if(tree){
for(each child C of tree)
postOrder(C);
visit(tree);
}
}
Inorder Traversal
void inOrder(tree_ptr, tree){
if(tree){
inOrder(tree->left);
visit(tree-element);
inOrder(tree->right);
}
}

3.3 Threaded Binary Tree

To use the blank pointers, we create the threaded binary tree, here are some rules.

  1. If Tree-Left is NULL, replace it with a pointer to the indorder predecessor of Tree.
  2. If Tree-Right is NULL, replace it with a pointer to the indorder successor of Tree.
  3. There must not be any loose threads. Therefore a thresded inary tree must have a head node of which the left child points to the first node.
typedef struct ThreadedTreeNode{
int LeftThread;
ThreadType Left;
ElementType Left;
int RightThread;
ThreadType Right;
}//If Left or Right is true, the Left/Right.

3.4 Kinds of Trees

  • Skewed Binary Tree
  • Complete Binary Tree

3.5 Propertities of Binary Trees

  1. The maximum number of nodes on level $i$ is $2^{i-1},i\ge1$.
  2. The maimum numbers of nodes in a binary tree of depth $k$ is $2^k-1,k\ge 1$.
  3. For any nonempty binary tree, $n_0=n_2+1$ where $n_0$ is the number of leaf nodes and $n_2$ the number of nodes of degree 2.

4 Binary Search Tree

4.1 Definition

A binary search tree is a empty or nonempty tree that qualifies the following properties:

  • every node is a dinstince integer
  • left subtree is smaller than the root
  • right subtree is bigger than the root
  • left and right subtree are binary search trees

4.2 Impementation

4.2.1 Find

tail recursion

Position Find(ElementType X,SearchTree T){
if(T==NULL) return NULL;
else if(XElment) return Find(X,T->Left);
else if(X>T->Element) return Find(X,T->Right);
else return T;
}

$T(N)=S(N)=O(d)$ d refers to the tree iterarion

while(T){
if(T->Element==x) pos=T;
else if(xElement) T=T->Left;
else T=T->Right;
}

4.2.2 FindMin/Max

Just like the find operation, when finding min, search along down the left subtree, and for the max, down right.

4.2.3 Insert

Insert an element:

  1. Check if the element is in the tree.
  2. Judge whether it’s bigger or smaller than the current node.
  3. If bigger/smaller, go right/left subtree. And if it’s NULL, insert it as a right/left child.

4.2.4 Delete

  • Delete a leaf node: reset its parent link to NULL
  • Delete a degree-1-node: Replace the node by its single child
  • Delete a degree-2-node
  1. Replace the node by the largest one in its left subtree or the smallest one in the right subtree.
  2. Delete the replacing node from the subtree

5 Disjointed Set

6 Graph

6.1 Definition

A graph is represented by G(V,E) where V=V(G) is a finite nonempty set of verticles, and E=E(V) is a finite set of edges of verticles.

  • Undirected graph: (v_i,v_j)=(v_j,v_i)
  • Directed graph: (v_i,v_j)\neq(v_j,v_i)
  • Restriction: no self loop and multigraph
  • Complete graph: a graph that has the maximum number of edges,|V|=C_N^2
  • For a Directed graph: (v_j,v_i)is incident on v_i and v_j, v_i and v_j are adjacent
  • For a undirected graph: <v_j,v_i>is incident on v_i and v_j, v_i is adjacent to v_j, and v_j is adjacent from v_i
  • Subgraph
  • Length of a path
  • Simple Path: the vertices in the path is distinct
  • Cycle: there is a path from the node to itself
  • Connected graph: there exists a path between any pair of nodes
  • Component of and undirected G: the maximal connected subgraph
  • A tree is a connected graph and acyclic
  • DAG: a directed acyclic graph
  • Strongly connected directed graph: for every pair of nodes, there existed a path from v_i to v_j and a path from v_j to v_i
  • Strongly connected component: the maximal subgraph that is strongly connected
  • Degree of a node: numbers of edges incident to v_i, and for a directed graph, there are in-degree and out-degree.
  • \sum\limits_{i=0}^{n-1}d_i/2=|E|

6.2 Representations

6.2.1 Adjacency Matrix

A two-dimension array adjMat[n][n]: adjMat[i][j]=\begin{cases}1 & <v_i,v_j>\newline 0 & no <v_i,v_j>\end{cases}

To calculate the degree:
D(i)=\sum\limits_{j=0}^{n-1}adjMat[i][j]+\sum\limits_{j=0}^{n-1}adjMat[j][i]

6.2.2 Adjency link

Replace each row with a link with a space complexity of O(n+2e),\ n+2e\ ptrs,\ 2e\ ints

To calculate the degree
  • Undirected graph: the number of nodes in graph[i], time complexity is O(n+e)
  • Directed graph: invere linked lists or adjacency multilists

6.2.3 Adjacency multilists

Each katex[/katex] have two nodes graph[i]/graph[j]

6.3 Topological Sort

  • AOV Network
  • Partial order: a precedence relation which is both transitive and irreflexive

6.3.1 O(V^2) Method

for i=0->numOfVertex:
    V=findZeroInDegree();
    if(V==NULL) unfeasible;
    topNum[v]=i;
    for W adjacent from V: indegree[W]--;

6.3.2

Use a stack/queue to store all the unassigned vertices of degree 0: