The logical definition of the linear table is a limited sequence composed of N (n ≥ 0) data element (node) A1, A2, ..., AN. 1 Number N of the data element is defined as the length of the table (N = 0 is called empty table). 2 Remember non-empty linear forms (N> 0): (A1, A2, ..., AN) 3 data element AI (1 ≤ i ≤ N) is just an abstract symbol, and the specific meaning may be different in different situations. Linear table logical structure features for non-empty linear tables: 1, and only one start node A1, there is no direct, there is only one direct successive A2; 2 have only one end node AN, no Direct successive, there is only one direct forward AN-1; 3 The remaining internal nodes AI (2 ≤ i ≤ N-1) is there and have only one direct Zeng Ai-1 and an AI 1. Basic operations of common linear tables 1. Initlist (L)
Construct an empty linear table L, the initialization of the table. 2. DESTROYLIST (L) eliminates a linear table L. 3. ClearList (L) Clear a linear table L. 4. Listempty (L) Rogue Linear Table L is empty. 5. Listlength (L)
Ask the number of nodes in linear table L, that is, the mean. 6. GetElem (L, I)
Take the i-th junction in linear table L, which requires 1 ≤ i ≤ Listlength (L) 7. LocateElem (L, X)
The node of the value is X is found in the L and returns the position of the node in L. If there are multiple nodes in the L, returns the node position for the first found; if there is no node in the L, it returns a special value to the lookup failed. 8. PRIORELEM (L, CUR_E, * PRE_E) Returns the previous node of the current node in the L. 9. NEXTELEM (L, CUR_E, * PRE_E) Returns the next node of the current node in the L. 10. Listinsert (L, X, I)
Insert a new node of X, which is inserted in the i, i 1, ..., N, N, N, N 1 node. Here 1 ≤ i ≤ N 1, and N is the length of the original table L. After insertion, the length of the table L is 1.11. Listdelete (L, I)
Delete the i, i 1, ..., N-1 of the original number I 1, i 2, ..., n to be numbered to be numbered I, i 1, ..., N-1. Here 1 ≤ i ≤ N, and N is the length of the original table L. Remove the length of the table L 1.12. ListTraverse (L, Visit ()) traversed linear table L.
/ ****************************************************** .h> #include
Struct List {ELEMTYPE * ELEM; int LENGTH; INT LISTSIZE;}; typefedef struct list list;
STATUS INTLIST (List * L) {L-> ELEM = (ELEMTYPE *) Malloc (List_init_size * sizeof (elemType)); if (! L-> elem) exit (overflow); l-> length = 0; l-> Listsize = list_init_size; return ok;}
Status DestroyList (List * L) {Free (L); L = NULL; RETURN OK;}
Status ClearList (List * L) {List R Initlist (& R); STRCPY (L, R); Return OK;}
Status Listempty (List L) {IF (L.Elem [0] == Null) Return True; Else Return False;}
Status ListLength (List L) {Return L.Length;}
Status getElem (List L, INT I, ELEMTYPE * E) {IF (1 <= I && I <= L.LENGTH) * E = L.Elem [I];}
Status Locateelem (List L, ElemType E, ELEMTYPE Compare ()) {INT i; for (i = 1; i <= L.LENGTH; I ) {IF (L.Elem [i], e)) Return I Else Return False;}}
Status priorelem (List L, ELEMTYPE CUR_E, INT * PRE_E) {INT i; for (i = 2; i <= L.Length; I ) IF (L.Elem [i] == CUR_E) * pre_e = i-1 }
Status NEXTELEM (List L, ELEMTYPE CUR_E, INT * NEXT_E) {INT i; for (i = 1; I <= L.Length; I ) IF (L.Elem [i] == CUR_E) * Next_e = i 1 }
Status ListInsert (List * L, INT I, ELEMTYPE E) {
ELEMTYPE * P, * Q, * newbase; if (i <1 || i> l-> length 1) return error; if (l-> length> = l-> listsize) {newbase = (elemType *) Realloc (L-> ELEM, (L-> ListSize ListINcrement) * SizeOf (ELEMTYPE)); if (! Newbase) EXIT (OVERFLOW); l-> elem = newbase; l-> listsize = listincrement;} Q = & L-> ELEM [I-1]); for (p = & (l-> elem [l-> length-1]); p> = q; - p) * (p 1) = * P; * Q = E; L-> Length; return ok;} status listdelete (list * L, int I, elemType * e) {ELEMTYPE * P, * Q; if (((i <1) || (i> L-> Length)) Return Error; P = & (L-> ELEM [I-1]); * e = * p; q = l-> ELEM L-> length-1; for ( P; P <= q; p) * (p-1) = * p; --L-> Length; Return OK;}
Status ListTraverse (List L, ElemType Visit ()) {INT i; for (i = 1; i <= L.Length; i ) Visit (L.Elem [i]);} / ******** ************************************************************ / # Define True 1 # define false 0 # define ok 1 #define error 0 # define infeasivle -1 # define overflow -2 # define list_init_size 100 # Define ListINcrement 10 # define Equal 1 # define stack_init_size 100 # define stackincrement 10 # define max 100 # define maxsize 100
