Linear list
Linear table sequential storage and operation implementation
The sequential storage is to sequentially store the elements of the linear table sequentially inverted a set of addresses in the computer memory. The sequential storage linear table is called sequence table.
The sequence table is a random access storage structure.
The operation of the sequence table:
#define maxlen 100tpyedef struct {datatype data [maxlen]; int lay;} listtp; listtp L;
1, initialize voidin {l.Length = 0;}
2, the length of linear table int Listlen (Listttp & l) {Return L.Length;}
3, find element int Localelem (Listtp & l, DataType X, INT I) {for (i = 0; i 4, insert element void insertelem (Listttp & l, datatype x, int 1) {INT J; if (i <1 || i> L.Length 1) Printf ("infeasible / n"); Else IF (L.LENGTH > = Maxlen) Printf ("overflow / n"); else {for (j = L.Length-1; J> = I-1; j -) L.Data [J 1] = L.Data [J ]; L.Data [i-1] = x; L.Length ;}} 5, delete element void delelem (Listttp & l, INT i) {INT J; if (i <1 || I> L.LENGTH 1) Printf ("Infeasible / N"); Else IF (L.Length == 0 ) PRINTF ("EMPTY LIST / N"); Else {for (j = i; j <= L.LENGTH-1; J ) L.Data [J-1] = L.Data [J]; L.LENGTH- -;}} Sequential storage is suitable for rare or simply not insert, delete operation, or only insertion, delete, etc. at the endpoint of the table. Chain storage and operation of linear table The so-called chain storage is the logically adjacent nodes are not adjacent to the storage location. Linear tables with chain storage structures are called linked lists. According to the link, the linked list is divided into: single-link table, two-way linked list, and loop chain list. According to the implementation, the linked list is divided into: static linked lists and dynamic chains. Typedef struct lnot {datatype data; struct lnot; Linklist * head; Basic operation of single-strand table: 1, create a list LinkList * InitList_L (LinkList * p; Int i; l = malloc (sizeof (limited)); Head-> next = null; for (i = N-1; I> 0; I -) {p = malloc (sizeof (linklist)); scanf (& p-> data); p-> next = head-> next; head-> next = p;} return L; 2. Find element LinkList * Locallist (Linklist * head, datattype x) {link1 * p; p = {p = p-> next;} return p; } 3, insert (1) insert insertafter_l (LinkList * S, DATATYPE X) {linklist * p; p = malloc (limited)); p-> data = x; p-> next = S-> next; S-> Next = P;} (2) Pretty insertFore_L (LinkList * Head, LinkList * S, Datatype X) {linkListx * p, * q; p = malloc (sizeof (limited)); P-> Data = X ; Q = head; while (q-> next! = S) {q = q-> next;} Q-> next = p; p-> next = s;} 4, delete delelem_l (Linklist * head, linklist * s) {linkList * p; p = head; while (p-> next! = s) {p = p-> next;} P-> next = S-> next; free (s);} The pointer domain of the last node is directed to the header node. At this time, the entire linked table is called a loop table. The operation is basically the same as the single-chain table. In addition to the data domain in the bidirectional chain table node, there is a pointer domain PRIOR that points to the direct, but also a direct successive pointer domain NEXT. typedef struct dlnode {datatype data; struct dlnode * prior; struct dlnode * next;} dlinklist; 1, forward runs doubly linked list INSERTFORE_DL (dlinklist * s, datatype x) {dlinklist * p; p = malloc (sizeof (dlinklist)); P-> data = x; s-> prior-> next = p; p-> pRIOR = S-> PRIOR; P-> next = S; S-> prior = p;} 2, two-way linked table delete delelem_dl (DLinkList * s) {s-> next-> prior = s-> prior; s-> prior-> next = S-> next; free (s);} Comparison of sequence tables and linked lists 1. The storage space from the storage space utilization angle is static allocation, which may be too large, waste space, may be too small, resulting in overflow. The storage space of the linked list is dynamically allocated as needed, as long as there is a disabled space in the memory, it will not produce overflow. Therefore, when the length of the linear table changes, and the storage capacity can be estimated in advance, the order storage structure is preferably employed in order to save the storage space (the finger needle in the chain). 2. From the time efficiency perspective, the sequence table is the random storage structure, the time complexity is O (1), and each node access in the linked list must be achieved from the head pointer and the chain-chain scan. Therefore, when the main operation on the linear table is to look, and when the insertion deletion is inserted, the sequential table storage structure is adopted. When inserting and deleting operations in linear forms, the linked list should be used as the storage structure.
