Data Structure Learning (C ++) - Figure [1] (Basic Storage Method)

First tell everyone a good news, the data structure is here to end! Then there is another bad news, here is the "most meaningless" part and the most difficult part in the data structure. The application of the figure is probably the broadest in all structures, but this is also destined to say that there is nothing to say when talking about the "data structure" - the most important thing about the map is the algorithm, and the considerable part is very Professional, the general people will hardly come into contact; relatively, the structure is very light. You can see that there are very few operations in the figure, far without a lot of "interfaces" listed there. - A structure is complicated, then the operation that can be defined is limited.

No matter what to say, it is still necessary to put the picture. Don't read a lot of methods on the book, there is only one - adjacent matrix. If the matrix is ​​sparse, you can store the matrix with a cross-chain table (see the "sparse matrix (crosslink table)"). If we only have the relationship between the line, it is the adjacent table (out of the edge); the opposite, only the relationship between the column is the counterpostation table (enter the point).

The implementation of two storage methods are given below.

#ifndef graphmem_h

#define graphmem_h

#include

#include

Using namespace std;

Template Class NetWork;

Const int maxv = 20; // maximum number of nodes

Template

Class Adjmatrix

{

Friend Class Network >;

PUBLIC:

Adjmatrix (): vnum (0), ENUM (0)

{

Vertex = new name [MAXV]; Edge = new dist * [MAXV];

For (int i = 0; i

}

~ Adjmatrix ()

{

For (int i = 0; i

DELETE [] Edge; delete [] Vertex;

}

Bool Insertv (Name V)

{

IF (Find (V)) Return False;

Vertex [vnum] = v;

For (int i = 0; i

VNUM ; return true;

}

Bool Inserte (Name V1, Name V2, DIST COST)

{

INT I, J;

IF (V1 == V2 ||! Find (v1, i) ||! Find (v2, j)) Return False;

IF (Edge [I] [J]! = NOEDGE) RETURN FALSE

EDGE [I] [J] = COST; ENUM ; Return True;

}

Name & GetV (int N) {return vertex [n];} // no off -ral inspection

INT NEXTV (int M, int N) // Returns the first neighboring top point number after the N-top of the M number vertices, no return -1

{

For (int i = n 1; i

}

Private:

Int vnum, enum;

Dist noedge, ** Edge; Name * Vertex;

Bool Find (Const Name & V)

{

For (int i = 0; i

Return False;

}

Bool Find (Const Name & V, INT & I)

{

For (i = 0; i

Return False;

}

}

Template

Class LinkedList

{

Friend Class Network >;

PUBLIC:

LinkedList (): vnum (0), ENUM (0) {}

~ Linkedlist ()

{

For (int i = 0; i

}

Bool Insertv (Name V)

{

IF (Find (V)) Return False;

Vertices.push_back (VERTEX (V, New List

VNUM ; return true;

}

BOOL INSERTE (Const Name & V1, Const Name & V2, Const Dist & Cost) {INT I, J; IF (V1 == V2 ||! Find (V1, I) ||! Find (V2, J)) Return False; for (List :: item = vertices [i] .E-> begin (); it! = vertices [i] .E-> end () &&im-> vid end ()) {vertices [i] .E-> push_back (EDGE (J, COST)); ENUM ; Return True;} if (iter-> vid == j) Return False; Vertices [i] .E-> ITERT (Iter, Edge (j, cost)); ENUM ; return true;} name & getv (int N) {return vertices [n] .v;} // No critical check INT NextV (int M, int N) // Returns the first neighboring top point number after the first neighbor of the N-number of the M number vertices, no -1 {for (List :: Iterator ITER = Vertices [M] .e > begin (); it! = vertices [m] .e-> end (); it ) if (iter-> vid> n) Return ITER-> VID; RETURN -1;}

Private: Bool Find (const name & v) {for (int i = 0; i * E): V (v), E (E) {} Name V; List * E;}; int vnum, enum; vector Vertices;}; # Endif This implementation is very simple, but it should be able to meet the following explanation. Now this can not do anything, don't worry, in the next article, the DFS and BFS of the chart will be described.