Shulou(Shulou.com)05/31 Report--

Today, I would like to share with you the relevant knowledge of what is the basic operation of C++ linear table. The content is detailed and the logic is clear. I believe most people still know too much about this, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Section 1: linear Table 1.1 concept

Linear table is a simple linear structure, which is characterized by that in a non-empty finite set, the first element has no direct predecessor element, the last element has no direct successor element, and all other elements have unique precursor and successor elements.

Linear tables have sequential storage structure and chain storage structure.

1.2 Sequential storage structure

It means that each element of a linear table is stored in a set of consecutive address storage units in turn, and the linear table stored in this method is usually called a sequential table.

Suppose that each element of the linear table occupies m storage units, and the storage address of the first unit is taken as the storage location of the data element. Then the relationship between the storage location location (ai+1) of the I + 1 element in the linear table and the storage location location (ai) of the I element satisfies the relationship location (ai+1) = location (ai) + m. The storage location of the first element in the linear table satisfies the following relationship between the storage location of the first element and the A1 of the first element, location (ai) = location (A1) + (Imur1) * m. Where the position location (A1) of the first element is called the starting address or base address.

The elements that are logically adjacent to the sequence table are also physically adjacent. The storage location of each data element differs from the starting position of the linear table by a constant proportional to the order of the order in the data element's online table. As long as the starting position of the first element is determined, any element in the linear table can be randomly accessed. Therefore, the sequential storage structure of the linear table is a random access storage structure. Because the array of C language has special random storage, the array is used to describe the sequence table. As follows:

Typedef struct {DataType list [ListSize]; int length;} SeqList

Where DateType represents the data element type, list is used to store data elements in the linear table, length is used to represent the number of data elements in the linear table, and SeqList is the structure type name. Define a sequence table code: SeqList L; pointer to the sequence table: SeqList * L

The basic operations of the sequential table are as follows:

(1) initialize the linear table:

Void InitList (SeqList * L) {L-> length = 0; / / set the length of the linear table to 0}

(2) non-empty judgment of linear table:

Int ListEmpty (SeqList L) {if (L.length = = 0) return 1; else return 0;}

(3) search by serial number:

Int GetElem (SeqList L, int I, DataType * e) {/ / looks for the first element in the linear table, successfully returns the value to e, and returns 1 indicates success, but failed to return the-1 table anyway. If (iL.length) return-1; * e = L.Listl [I-1]; return 1;}

(4) search by content:

Int LocateElem (SeqList LMagna dataType e) {/ / find the element with e in the linear table int i; for (I = 0; L.length; iDiffect +) if (L.ListList [I] = = e) return iDiffl1; return 0ramramp / cannot find 0}

(5) insert operation:

/ insert the element e in the I position of the sequence table, return 1 for success and-1 for failure. If the sequence table is full, return 0int InsertList (SeqList * Lint int I, DataType e) {int j; if (I L-> length+1) {return-1;} else if (L-> length > = ListSize) {return 0;} else {for (jacks L-> length; j > = I) JMQ -) {L-> list [j] = L-> list [j-1];} L-> list [I-1] = e; / / insert elements to I positions L-> length = L-> length+1; return 1;}}

(6) delete operation:

Int DeleteList (SeqList * L length-1; return int I, DataType * e) {int j; if (L-> length-1; return [I-1]; for (j-list [j-1] = L-> length-1; return [j]) {L-> list [j-1] = L-> list [j];}}

Summary: advantages and disadvantages of sequential tables.

(1) advantages: there is no need to care about the relationship between the elements in the table, so there is no need to add additional storage space; you can quickly fetch the elements anywhere in the table.

(2) disadvantages: insert and delete operations require a large number of elements to be moved. The memory space needs to be allocated before use, and when the length of the linear table changes greatly, it is difficult to determine the capacity of the storage space. Excessive allocation of space will result in a huge waste of storage space, and the allocated space is too small to meet the needs of the problem.

1.3 chain storage of linear tables

When solving practical problems, sometimes it is not suitable to use the sequential storage structure of linear tables, such as the addition and multiplication of two unary polynomials, which requires another storage structure-chain storage. It uses a set of arbitrary contiguous or discontiguous storage cells to store linear table elements. To represent the logical relationship between each element ai and its immediate successor ai+1, chained storage needs to store not only the element itself, but also an address that points to its immediate successor. This storage structure is called node. The storage element is called the data domain, and the storage address is called the pointer domain. The logical order of node elements is called linear linked list or single linked list.

Because the first node does not have a direct precursor node, you need a header pointer to it. In order to facilitate the operation, a node before the first element node is called the head node, and the head pointer points to the head node, and its data field can store information such as the length of the line table, while the pointer field stores the address information of the first element node. If the linked list is empty, the pointer field of the head node is empty.

Because the last element has no immediate successor, its pointer field is set to "Null" empty.

The storage structure of single linked list is described in C language:

Typedef struct Node {DataType data; struct Node * next;} ListNode,*LinkList

Where ListNode is the node type of the linked list and LinkList is the pointer type that points to the linked list node. It is defined as: LinkList L = ListNode * L.

The basic operations of a single linked list are as follows:

(1) initialize single linked list:

Void InitList (LinkList * head) {if ((* head= (LinkList) malloc (sizeof (ListNode) = NULL) {/ / allocate storage space exit (- 1) for the header node;} (* head)-> next = NULL; / / set the header node pointer field of the single linked list to null}

(2) non-empty judgment of single linked list:

Int ListEmpty (LinkList head) {if (head- > next = = NULL) {/ / single linked list is empty return 1;} else {return 0;}}

(3) query operation by serial number:

/ / find node I in the single linked list ListNode * Get (LinkList head,int I) {ListNode * p; int j; if (ListEmpty (head)) {/ / if the linked list is empty return NULL;} if (inext! = NULL & & jnext; jungle;} if (jungi) / / find the first node return p; else return NULL;}

(4) search by content:

/ find the element ListNode * LocateElem (LinkList head,DataType e) {ListNode * p; p = head- > next;// pointer p points to the first node while (p) {if (p-> data! = e) {pendant-> next;// to continue to the next} else {break;}} return p;}

(5) location operation:

Int LocatePos (LinkList head,DataType e) {ListNode * pashing / defines a pointer p int i; if (ListEmpty (head)) / / non-null judgment return 0 to a node of a single linked list; p = head- > next;// pointer p points to a node I = 1; wihle (p) {if (p-> data==e) return i; else {pendant-> next / / point to the next node inode;}} if (! p) / / if no element equal to e is found, return 0;}

(6) insert new data element e:

Int InsertList (LinkList head,int iCommerce dataType e) {ListNode * pre,*p;// defines the leading node pointer pre of the first element, and the new node pointer p int j; pre = head; / / pointer pre points to the header node j = 0; while (pre- > nextparagraph null & & jnext; jungle);} if (jackpot 1) / / if it is not found, the insertion position is incorrect return 0 / / A new node if ((p = (ListNode*) malloc (sizeof (ListNode) = = NULL) {exit (- 1);} p-> data = e; / / assign e to the node's data field p-> next = pre- > next; pre- > next = p; return 1;}

(7) delete node I:

Int DeleteList (LinkList head,int iMagazine dataType * e) {ListNode * pre,*p; int j; pre = head; j = 0; while (pre- > nextparagraph null & & pre- > next- > nextjewelry null & & jnext; jobless;} if (jackpot 1) {return 0 } / / pointer p points to the I node in the single linked list and assigns the node data field value to e p = pre- > next; * e = p-> data; / / points the pointer field of the precursor node to the next node pre- > next = p-> next; free (p) to delete the node; / / releases the node return 1 that p points to } 1.4 comparison between single linked list and sequential list

(1) Storage mode: the sequential table uses a set of continuous storage units to store the data elements of the linear table in turn, while the single-linked table uses a set of arbitrary storage units to store the data elements of the linear table.

(2) time performance: when using sequential storage structure, the time complexity of searching is O (1). Inserting and deleting data elements need to move an average of half of the data elements, and the time complexity is O (n). The search time complexity of single linked list storage structure is O (n), insertion and deletion do not need to move elements, and the time complexity is only O (1).

(3) Space performance: when using sequential storage structure, storage space needs to be allocated in advance, too much space will lead to waste, and too small will cause problems. When using the single linked list storage structure, it can be allocated temporarily according to the need, there is no need to estimate the size of the problem, as long as there is enough memory, it can also be used in some special cases, such as the representation of unary items.

1.5 cyclic single linked list

Cyclic single linked list (circular linkedlist) is a kind of single linked list connected from end to end, that is, the null pointer of the last node is changed to point to the head node or the first node to form a ring, and the last node is called tail pointer: rear. The condition for judging the emptiness of a single linked list is head- > next==NULL, while the condition for judging an empty cyclic single linked list is head- > next==head. Visit the first node, rear- > next- > next.

If you combine two cyclic single linked lists (LA,LB) into a linked list, you only need to join the footer of one table to the header of the other table. The specific steps are:

1, change LA- > next = LB- > next- > next; to the first node.

2. Release the header node of LB, free (LB- > next)

3. Connect the footer of LB to the header of LA, LB- > next = LA- > next.

LinkList Link (LinkList head1,LinkList head2) {ListNode * pcogimq; p = head1;//p points to 1 node while (p-> next! = head1) {/ / cycle so that the pointer p points to the last node of the linked list p = p-> next;} Q = head2; while (Q-> next! = head2) {/ / ditto Q = Q-> next;} p-> next = head2- > next / / connect the end of the first linked list to the first node of the second linked list Q-> next = head1; / / connect the end of the second linked list to the first node of the first connection return head1;}

Description: the head node in the circular single linked list can also be turned into a sentinel node.

1.6 two-way linked list

A two-way linked list (double linked list) is that each node in the linked list has two pointer fields, one pointing to the direct precursor node and the other to the direct successor node. Each node of the two-way linked list has three fields: the data field, the priority field, and the next field. Among them, the data domain is the data domain and stores the data elements; the prior domain is the precursor node pointer domain; and the next domain is the subsequent node pointer domain. A two-way linked list can also add a header node to facilitate operation, and it also has a circular structure like a single linked list, which is called a two-way cyclic linked list.

The condition for determining that the bi-directional circular linked list of the leading node is empty is: head- > prior = = head | | head- > next = = head. Description in C language: pairp-> prior- > next = p-> next- > prior.

The node storage structure of the two-way linked list is described as follows:

Typedef struct Node {DataType data; struct Node * prior; struct Node * next;} DListNode,*DLinkList

(1) insert a node with an element value of e at position I:

Analysis: first find the I node; then apply for a new node, point to the node by s, and put e into the data domain. Then modify the pointer domain of the node pointed to by p and s, modify the priority domain of s to point to the direct precursor node of p, modify the Nextfield of the direct precursor node of p to point to the node pointed to by s, modify the nextfield of s to point to the node pointed to by p, and modify the priority domain of p to point to the node pointed to by s.

Int InsertDList (DListLink head,int igrad dataType e) {DListNode* pjime; int j; p = head- > next; j = 0; while (paired headlines) {return 0;} s = (DListNode*) malloc (sizeof (DListNode)); / / create a new node if (! s) {return-1;} s-> data=e for s / / e assign a value to s s-> prior = p-> prior; / / assign the precursor pointer of p to the precursor of s p-> prior- > next = s return / e, the successor pointer of p to p is p-> prior = p-/ the precursor of p is s return 1;}

(2) Delete Node I

Int DeleteDList (DListLink head,int I, DataType e) {DListNode * p; int j; p = head- > next; j = 0; while (paired headlines headlined static jnextjnextjnextjinxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

The allocation and release of the above linked list nodes are dynamically realized by the functions malloc and free, so they are called dynamic linked lists. However, some advanced programs do not have pointer types, so they can not use the above methods to dynamically create linked lists, but need to use static linked lists to achieve the function of dynamic linked lists.

A static linked list is implemented using an one-dimensional array. The type is described as follows:

Typedef struct {DataType data; int cur;} SListNode; typedef struct {SListNode list [ListSize]; / / Node type int av; / / alternate linked list pointer} SLinkList; / / static linked list type

Static cyclic linked list: a component of an array represents a node, while a cursor (indicator cur) is used instead of a pointer to indicate the relative position of the node in the array. The header node is the zero component of the array, and its pointer field indicates the first node of the linked list. The pointer field of the last node in the table is 0, pointing to the header node. Example: the linear table is as follows:

Let s be a variable of type SlinkList, then s [0] .cur indicates the header node, and if you make iObs [0] .cur, then s [I] .data indicates that the first element "Yang" in the table is s [I] .cur indicates the position of the second element in the array.

Basic elements of a static linked list:

(1) initialize static linked list:

Void InitSList (SLink * L) {int i; for

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.