# [algorithm design zxd] Chapter 1 algorithm basics 5 Basic data structure

Fatal primary school 2022-06-23 18:42:50 阅读数:112

algorithmdesignzxdchapteralgorithm

Catalog

Thinking questions ： Learned data structure and its characteristics

（1） Linear data structure

(2) Trees

(2) Trees — Binary tree

(3) chart

(3) chart — Representation . adjacency matrix

(3) chart — Representation . Adjacency list

## Thinking questions ： Learned data structure and its characteristics

Linearity is a structure .

There are also categories in the linear table .

Realization ： Array , Linked list （ Single chain list ,）

Nonlinear structure ： Trees ：（ characteristic ： Only one parent ）

# （1） Linear data structure

The linear table 、 Stack （LIFO）、 queue （FIFO）

# (2) Trees

Trees (Tree) yes n(n≥0) A finite set of nodes . In any non-empty tree ：

There is and only one specific node called root ;

② When n>1 when , The rest of the nodes can be divided into m(m>0) A finite set that doesn't intersect each other T1,T2,…Tm, Each of these sets is itself a tree , And called the root of the subtree ;

③T1,T2,…Tm There may also be several disjoint subtrees T1,1,T1,2……Tm,k, By analogy . ## (2) Trees — Binary tree

nature 1】 In the binary tree The first i layer At most 2^(i-1) Nodes (i≥1).

【 nature 2】 Depth is k Two fork tree at most Yes 2^(k) - 1 Nodes (k≥1)

【 nature 3】 have n Of nodes Perfect binary tree The depth of this is ⌊log_2 n⌋+1.

It is known from this property that , Have arbitrarily n A binary tree of nodes , Its high h Satisfy the following inequality .

⌊log_2 n⌋ ≤ h ≤n−1

The representation of binary tree ： ``````typedef struct BiTNode{
TElemtype data; // Node information
Struct BiTNode *lchild, *rchild; // Left the child , The right child
}BiTNode, *BiTree;
``````

# (3) chart

G=(V, E)

If (v, u)∈VR, be (v, u) From v To u An arc of ,v For the arc tail ,u For the arc head , At this time said chart G It's a digraph .

If (v, u)∈VR There must be (u, v)∈VR, namely VR It's symmetrical , Disordered pair (v, u) Instead of two ordered pairs (v, u) and (u, v), be (u, v) To represent an edge , call chart G For undirected graph .

edge 、 arc 、 Adjacency 、 relation 、 degree (Degree)、 The degree of (InDegree)、 The degree of (OutDegree)

## (3) chart — Representation . adjacency matrix ``````V: VNode v[n]; // The vertices
VR: weight vr[n][n]; // Adjacency matrix
``````
``````typedef struct VNode{
elementtype vertex; // Vertex data
}VNode, v;
weight vr= { 0, 1, 1, 1,
1, 0, 1, 1,
1, 1, 0, 1,
1, 1, 1, 0 };
``````

## (3) chart — Representation . Adjacency list The vertices

``````V:
typedef struct VNode{ // Vertex structure
vertextype data;
``````VR: