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 .

 v Arctail ->u Arc head

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[4];
weight vr[4][4]= { 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;
struct adjvex * firstedge; // Side linked list
}VNode, v[n];

  Adjacency list

VR:
struct adjvex{
int seqNo;
struct adjvex *next;
};