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

This article mainly introduces the example analysis of sequence list and linked list in C language, which has a certain reference value. Interested friends can refer to it. I hope you will gain a lot after reading this article.

Definition and characteristics of linear table

The basic characteristics of the linear structure: except that the first element has no direct precursor, the last element has no direct successor, and all other elements have a precursor and a successor.

In human terms, the first element cannot be accessed forward, the last element cannot be accessed backward, and the middle element can access other elements back and forth.

For example: 26 alphabets {Ameng Bpeng C Magi D M é rine F … } is a linear table.

Although the data elements in the linear table are different, each element has the same characteristics and belongs to the same data object.

Linear table: a finite sequence of finite data elements with the same data characteristics

If there are no data elements, the linear table is also called an empty table.

The characteristics of linear structure

1, there is only one "first" and "last" data element

2, give the first and last data elements, and all the other elements have a front driver and a rear driver

Explain: the predecessor and successor are the previous element and the next element in the logical relationship

I thought it was a pointer or something.

Linear table

The length of the linear table can be increased or decreased as needed. It also has inserts and deletions anywhere.

Linear tables are divided into sequential lists and linked lists.

Sequential storage

The sequential storage of a linear table is a sequential table, which refers to the data elements stored in sequence by a set of storage units with consecutive addresses. * * the reality is that each element is stored in a contiguous address space (array for short). For sequential storage, it is logically continuous and its physical order is also continuous.

Take a look at a picture to enhance understanding (this is my habit of writing sequential storage, there may be differences)

For the sequential storage of linear tables, each data element can be quickly accessed and read by subscript. Formally, it's random access.

Element type definition of sequential table

This is my definition of the structure type of sequential storage.

# define N 8typedef struct elem {data items in each data element} sel;typedef struct seq {the first address of the linear tablespace dynamically opened by sel* arr;//, through which you can access the linear tablespace int size;// the number of spaces currently used int capacity;// the current maximum data element capacity} sl

For a brief description here, I directly use data items that are equivalent to only int types for each data element.

In fact, just like the address book, each data element is a collection of all the information of a person (so to speak), and the data item is a part of each element.

Add, delete, check and modify the sequence table

For sequential tables, most of them can be operated as arrays, of course, that is, we have to consider the capacity of the order, whether we need to expand the capacity of several dynamic changes.

Initialization order table void initsequence (sl* a) / / initialization dynamic order table {a-> size = 0 malloc / the array elements are calculated with 0, size is the subscript of the last element, not the total number of elements a-> capacity = Nash pact N has been define a-> arr = (sel*) malloc (sizeof (int) * N) } expansion sequence table void checkcapacity (sl* a) / / check whether you need to expand {if (a-> size + 1 steps = a-> capacity) {a-> capacity * = 2; a-> arr = (sel*) realloc (a-> arr,sizeof (int) * (a-> capacity)) If (a-> arr = = NULL) {printf ("realloc defect"); exit (- 1);}

Expansion is when the number of elements in the sequence table has reached the maximum capacity when it is ready to operate on the elements of the sequence table, because our size is a subscript, we need to add one. Because we are going to expand the capacity, we will not allow size > = capacity.

At the same time, capacity expansion can not be expanded too much at one time, otherwise it may lead to a waste of space.

Can not expand too little, less will be many times to expand capacity, will increase consumption.

So, see for yourself. Hee hee ~

The tail insertion method adds the element void sequpushfront (sl* aforce sell * ele) / / tail interpolation {checkcapacity (& a); / / check whether expansion is needed * (a-> arr + a-> size) = ele- > element;// because I only set one int type if there are multiple data items in the data element looking down + + (a-> size);} void sequpushfront (sl* ather sell * ele) / tail interpolation {checkcapacity (& a) / / check whether you need to expand the capacity (a-> arr + a-> size)-> n = ele- > element;// assuming that multiple data items are matched in turn (a-> arr + a-> size) and then-> n accesses the space of the corresponding element for storage. + (a-> size);}

Tail insertion is not that complicated, check the expansion and put the element directly in the back.

I'm not going to give any more examples. It's easy to cite examples.

Void sequpushback (sl* a, int n) / / plug {checkcapacity (& a); / / check whether expansion is needed int head = 0; int end = a-> size; while (end > = head) {* (a-> arr + end + 1) = * (a-> arr + end);-- end } + + (a-> size); * (a-> arr + head) = n;}

The head insertion method requires that all the elements placed in the position be moved backward one position.

However, how to move is also a question to be considered.

Whether to move from front to back, or from the last element.

If it's moving forward and backward,

Will cause this to look like this, and the latter element will always be 1, then this method is wrong.

Let's take a look at moving from behind to forward.

This method is feasible.

Expand the capacity first

Move the element back, then insert it in the head.

Void sequpushback (sl* a, sel* ele) / / plug method {checkcapacity (& a); / / check whether capacity expansion is needed int head = 0; int end = a-> size; while (end > = head) {* (a-> arr + end + 1) = * (a-> arr + end);-- end } + + (a-> size); * (a-> arr + head) = ele- > element;} delete anywhere

Delete will not be deleted at the beginning and tail, but will be deleted directly anywhere.

Find the subscript of that element and start to overwrite it forward

Moving elements is another hassle for deletion.

This time for deletion, the element has to start moving back and forth.

Void sequpopmid (sl* a, int n) / / intermediate deletion, n is the location to be deleted {assert (n > = 0&&nsize); for (int I = n; I

Size-1; iTunes +) {* (a-> arr + I) = * (a-> arr + I + 1);}-- (a-> size);}

After deletion, the boundary, that is, size, should be self-subtracted to prevent it from crossing the boundary.

Add anywhere

Pass the location you want to add, and then start moving backwards.

Void sequpushmid (sl* a, int njisel * ele) / / add {assert (n > = 0&&n=size+1) in the middle; / / add checkcapacity (& a) in a valid location; / / check whether you need to expand the capacity int head = n; int end = a-> size; while (end > = head) {* (a-> arr + end + 1) = * (a-> arr + end) -- end;} + (a-> size); * (a-> arr + head) = ele- > element;}

In fact, it is a kind of deformation of head insertion.

Small summary

For array deletion elements, start moving forward and backward.

For adding elements to the array, move from back to front.

At the same time, delete and add the location must meet the conditions, can not cross the boundary.

Chain storage of linear table

The storage structure is characterized by using a set of arbitrary storage units to store the data elements of the linear table. (this set of memory cells can be continuous or discontiguous, referred to as randomly distributed memory cells)

Data domain and pointer domain

Each allocated storage unit is divided into two parts: the data domain and the pointer domain.

These two fields or information make up the storage image of the data element. It is the projection of elements at the logical level at the physical level. Also known as nodes.

Data field: stores each data element, including individual data items

Pointer field: stores a pointer, that is, the address of the next node

Note that chained storage is a linked list, in which the address of each node is random, not a sequential list in which each space is arranged in turn.

Linked list has a variety of structures, such as: single linked list, one-way / two-way circular linked list, two-way linked list, binary linked list, cross linked list, adjacent linked list, adjacent multiple list and so on.

This paper mainly analyzes single linked list, cyclic linked list and two-way linked list. The rest will not be analyzed for the time being (in fact, I will not, it is relatively lame at the moment). I will supplement the analysis in the future.

It is best to draw a picture of the data structure first, which can enhance understanding and analysis.

Get a general idea of the structure of the linked list.

Because the physical relationship of each node in the linked list is uncertain and random, it needs to be represented by the pointer domain to form a logical relationship. It is very important for the pointer to point.

You don't want the head node of this sentinel.

# include "linkedlist.h" void test () {list* head; list* last; initLinkedlist (& head,&last); pushlast (& last, 1); / / tail insertion pushlast (& last, 2); pushlast (& last, 3); pushlast (& last, 4); pushfront (& head, 5); / / head insertion pushfront (& head, 8) / / pushfront (& head, 7); / & pushfront (& head, 6); / popchoice (& head, 0); / / delete / / poshposition (& head, 3) anywhere; / / insert printlist (& head) at any location; / / print} int main (void) {test (); return 0;}

First analyze the linked list of sentinels to make it easier to understand

Initialize linked list void initLinkedlist (list** head,list** last) / / initialize linked list {* head = (list*) malloc (sizeof (list)); (* head)-> next = NULL; * last=*head;}

Head is the sentinel bit, and this last is to locate the last node. When last points to head, it represents an empty table.

Since I created the sentinel node and tail node pointer in the test function, I have to pass a secondary pointer to the pointer before the address call can affect the linked list.

When the tail node points to the Sentinel node, it indicates an empty table.

Tail insertion adds linked list nodes void pushlast (list** last, int num) / / tail insertion {list* new = (list*) malloc (sizeof (list)); new- > n = num; new- > next = (* last)-> next; (* last)-> next = new; (* last) = new;}

At the end node, that is, the last node.

Insert the diagram of the node at the end, that's it.

At the same time, when the last- > next points to the newnode, the last also moves to the newnode, because the newnode becomes the tail node, and the next insert will be inserted after this newnode.

Add linked list node void pushfront (list** head, int num) / / head insertion {list* new = (list*) malloc (sizeof (list)); new- > n = num; new- > next = (* head)-> next; (* head)-> next = new;}

To insert after the Sentinel, each insertion should be satisfied after the Sentinel node.

The sentinel node is always the same, we can continue to insert the head through this operation.

Print linked list void printlist (list** head) / / print {list* p = (* head)-> next; while (p) {printf ("% d", p-> n); p = p-> next;}}

Traverse from the sentinel node and print it in turn.

Delete void popchoice (list** head, int pos) / / delete {assert (pos=0) at any location; int I = 0; list* pre = * head; list* cur = (* head)-> next; while (I)

Next; iTunes;} pre- > next = cur- > next; free (cur);}

Since it is a linked list with sentinels, it is OK to delete it at any location, but there is some trouble without a linked list with sentinels.

Although similar changes. Because the bit wants to save the previous node address of the node, it needs to be judged by if when there is no sentinel bit. It's not really much trouble.

Inserting and deleting anywhere is the same.

Bidirectional linked list

This is another chain structure.

Each node has two pointers, one to the previous logical relation node and one to the next logical relation node.

This generally uses a sentinel node, which makes it easier to create a two-way linked list.

For two-way linked list and single linked list, two-way linked list has more advantages in inserting, deleting and multiple operations.

Such as: tail insertion.

For a single linked list, the pointer traverses to find the tail node, and then insert it. The time complexity is O (N).

In the two-way linked list, the prev pointer of its header node points to the last node and does not need to be traversed at all.

Like some insert operations.

Such as: forward insertion

Prepare two pointers for a single linked list.

The two-way linked list directly accesses the prev pointer to find the last node.

Although more pointers may be more troublesome than single-linked lists, the overall operation is simpler.

Moreover, in many future structures, single-linked lists will not be used alone, but as part of a data structure. The two-way linked list will be used as a body.

Test the two-way linked list (main function) # include "doubly_Linkedlist.h" void doublelinkedlist1 () {doulink head; initlinkedlist (& head); / initialize the two-way linked list LinkedlistFrontPush (& head, 1); / / insert LinkedlistFrontPush (& head, 2); / / insert LinkedlistFrontPush (& head, 3); / / insert LinkedlistFrontPush (& head, 4); / / insert LinkedlistFrontPush (& head, 5) / / head insertion LinkedlistBackpush (& head, 6); / tail insertion LinkedlistBackpush (& head, 7); / tail insertion LinkedlistBackpush (& head, 8); / tail insertion LinkedlistBackpush (& head, 9); / / tail insertion LinkedlistBackpush (& head, 10); / / tail insertion LinkedlistFrontPop (& head); / head deletion LinkedlistFrontPop (& head); / head deletion LinkedlistFrontPop (& head) / / head delete LinkedlistBackPop (& head); / / tail delete LinkedlistPrint (& head); / / print linked list} int main (void) {doublelinkedlist1 ();}

Because I created a structure variable, to operate on it, you need to pass the address call, if the value call will, in fact, the Sentinel has not changed, just changed the parameter in the function.

Initialize bidirectional linked list void initlinkedlist (doulink* head) / / initialize bidirectional linked list {(* head). Next = head; (* head). Prev = head;}

Because the two-way linked list is to form a closed loop, it is also necessary to form a closed loop during initialization.

Insert elements void LinkedlistFrontPush (doulink* head, lint n) / / insert {doulink* newnode = (doulink*) malloc (sizeof (doulink)); newnode- > num = n; doulink*phead= (* head). Next;// original head node newnode- > next = phead;// new rear drive pointer is connected to the next (* head). Next = newnode;// links the new node newnode- > prev = head / / the leading pointer of the new node points to the Sentinel phead- > prev = the leading pointer of the original newnode;// node points to the new head node}

Insert element void LinkedlistBackpush (doulink* head, lint n) / / tail insertion {doulink* newnode = (doulink*) malloc (sizeof (doulink)); newnode- > num = n; doulink* plast = (* head). Prev;// finds the tail node newnode- > prev = plast;// new tail node newnode- > next = plast- > next;// new access sentinel plast- > next = newnode / / the original tail node next points to the new tail (* head). The prev of the prev = newnode;// header node points to the new tail node, forming a closed loop}

The case of having multiple nodes in a linked list

Delete node void LinkedlistBackPop (doulink* head) / / tail delete {doulink* last = (* head). Prev;// find the tail node to be deleted doulink* llast = last- > prev;// find the new tail node if (last = = head) {printf ("Empty List\ n"); return } (* head) .prev = llast;// change Sentinel node prev to point to llast- > next = last- > next;// to connect the next of the new tail node to Sentinel free (last); / / Delete memory}

Delete node void LinkedlistFrontPop (doulink* head) / / delete node {doulink* phead = (* head) .next; doulink* second = phead- > next; if (phead = = head) {printf ("Empty List\ n"); return;} second- > prev = phead- > prev; (* head). Next = second; free (first);}

For head-to-tail insertion and tail deletion, be sure to pay attention to the order, otherwise the pointer may point to the wrong place.

For the deletion and insertion of two-way linked lists, there is no need for multiple pointers, which is much more convenient.

Here is the whole body of the code

Doubly-Linked list.c file # include "doubly_Linkedlist.h" void initlinkedlist (doulink* head) / / initialize bi-directional linked list {(* head). Next = head; (* head). Prev = head;} void LinkedlistFrontPush (doulink* head, lint n) / / insert {doulink* newnode = (doulink*) malloc (sizeof (doulink)); newnode- > num = n; doulink*phead= (* head). Next / / original head node newnode- > next = phead;// the new rear drive pointer is connected to the next (* head). Next = newnode;// points the leading pointer of the Sentinel link new node newnode- > prev = head;// new node to Sentinel phead- > prev = newnode / / the leading pointer of the original head node points to the new head node} void LinkedlistBackpush (doulink* head, lint n) / / tail interpolation {doulink* newnode = (doulink*) malloc (sizeof (doulink)); newnode- > num = n; doulink* plast = (* head) .prev; / / find the tail node newnode- > prev = plast;// the new tail node newnode- > next = plast- > next / / New access Sentinel plast- > next = newnode;// the original tail node next points to the new tail (* head). Prev = newnode;// head node prev points to the new tail node, forming a closed loop} void LinkedlistFrontPop (doulink* head) / / head deletion {doulink* phead = (* head) .next; doulink* second = phead- > next If (phead = = head) {printf ("Empty List\ n"); return;} second- > prev = phead- > prev; (* head). Next = second;} void LinkedlistBackPop (doulink* head) / / tail deletion {doulink* last = (* head) .prev; / / find the tail node doulink* llast = last- > prev / / find the deleted new tail node if (last = = head) {printf ("Empty List\ n"); return;} (* head). Prev = llast;// change the sentinel node prev to llast- > next = last- > next;// to allow the next of the new tail node to access Sentinel free (last) } void LinkedlistPrint (doulink* head) / / print linked list {doulink* cur = (* head) .next; while (cur! = head) {printf ("% d", cur- > num); cur = cur- > next;}} doubly-Linkedlist.h#pragma once#include # include # include typedef int lint;typedef struct doulinked {lint num; lint* prev; lint* next } doulink;void initlinkedlist (doulink* head); / / initialize bidirectional linked list void LinkedlistFrontPush (doulink* head, lint n); / / head insertion void LinkedlistBackpush (doulink* head, lint n); / / tail insertion void LinkedlistFrontPop (doulink* head); / / head deletion void LinkedlistBackPop (doulink* head); / / tail deletion void LinkedlistPrint (doulink* head) / / print linked list Thank you for reading this article carefully. I hope the article "sample Analysis of sequence list and linked list in C language" shared by the editor will be helpful to you. At the same time, I also hope that you will support and pay attention to the industry information channel. More related knowledge is waiting for you 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.