Shulou(Shulou.com)06/01 Report--

This article mainly explains "what are the advantages of database cross-linked list". Interested friends may wish to take a look at it. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "what are the advantages of database cross-linked lists"?

1. Introduction:

For a directed graph, the adjacency table is flawed:

Adjacency table: concerned about the degree problem, if you want to understand the degree, you have to traverse the whole graph to know.

Inverse adjacency table: solve the degree of entry, but do not understand the degree of output.

Can you combine the adjacency table with the inverse adjacency table? The answer is: use cross-linked lists.

two。 Cross-linked list storage structure:

Vertex table node structure:

Firstin: indicates the entry table header pointer to the first node in the entry table of the vertex. / / newly added

Firstout: indicates the edge table header pointer, pointing to the first node in the outgoing table of the vertex. / / same as the vertices in the adjacency table

Edge table node structure:

Tailvex: refers to the subscript of the starting point of the arc at the vertex table.

Headvex: refers to the subscript at the end of the arc in the vertex table. / / same as the adjvex in the adjacency table

Headlink: points into the edge table pointer domain.

Taillink: the pointer domain of the pointer table. / / same as the next in the adjacency table

If it is a network, you can add another weight domain to store weights.

The blue line indicates the degree of output, and the red line indicates the degree of entry.

3. Advantages of cross-linked lists:

1.) Cross list integrates adjacency list and inverse adjacency list, so that it is easy to find arcs ending with Vi and arcs with Vi as head.

Therefore, it is easy to find the degree of exit and entry of the vertex.

2.) the time complexity of the graph creation algorithm of the cross list is the same as that of the adjacency table.

Cross linked list typedef char Vtype / / Vertex type typedef int Etype / / weight type # definde MAXV 100; typedef struct edgeNode / / Edge list node {int tailvex; / / newly added int headvex; / / adjacency points store the subscript Etype weight;// edge weights corresponding to the vertex struct edgeNode * headllink; / / newly added struct edgeNode * taillink;} EdgeNode Typedef struct Vnode / / vertex table node {Vtype data; EdgeNode* firstInEdge; / / entry EdgeNode* firstOutEdge;// exit degree} VNODE; / / typedef struct {VNODE adjlist [MAXV]; current number of int numV;// vertices current number of int numE;// current edges} GraphAdjList; void CreateALGraph (GraphAdjList* G) {int iJournal j EdgeNode* k; EdgeNode* e = NULL; cout > G-> numE For / establish vertex information {cin > > G-> adjlist [I] .data; / / enter vertex information G-> adjlist [I] .firstOutEdge = NULL; / / Edge node is empty G-> adjlist [I] .firstInEdge = NULL; / / Edge node is empty} for / / the starting point of the newly added arc is e-> headlink = G-> adjlist [j] .firstInEdge; / / the new G-> adjlist [j] .firstInEdge = e _ Tender / new e-> headvex = j; / / the original e-> adjvex e-> taillink = G-> adjlist [I] .firstOutEdge; / / the original G-> adjlist [I] .firstOutEdge = e }} at this point, I believe you have a deeper understanding of "what are the advantages of database cross-linked lists". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.