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

This article mainly introduces the relevant knowledge of "what is the concept and structure of C language sequence table". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this article "what is the concept and structure of C language sequence table" can help you solve the problem.

1. The concept and structure of sequence table

A sequential table is a linear structure in which data is stored successively by a unit with a continuous physical address, usually stored in an array. Complete the addition, deletion, query and change on the array.

Sequence tables are divided into two categories:

Static sequence tables: storing elements using fixed-length arrays

Struct SeqList {the number of data stored in int data;// the number of data recorded by int size;// / the total capacity of the given current sequence table is 1000}

Dynamic sequence table: using dynamically opened array storage

Struct SeqList {the number of data stored in int data;//, the number of data recorded by int size;//, the total capacity of int capacity;// sequential table}; 2. The realization of addition, deletion, query and modification

When the amount of data we need to store is uncertain, it is better to use a dynamic sequence table, so let's use a dynamic sequence table to add, delete, query and change.

2.1 capacity expansion

First of all, we want to automatically expand the capacity of our dynamic sequence table. When the current data volume size is equal to the total capacity capacity, we need to automatically increase the capacity. Specifically, we use the malloc function to open up a certain amount of space. If we set two times for each expansion, the code is as follows:

/ / increase the capacity of void SLCheckcapacity (SL* pc) {assert (pc! = NULL); / / check the capacity. Expand if (pc- > sz = = pc- > capacity) {/ / double the capacity at one time. If the initial capacity is 0, expand it to 4 int newcapacity = pc- > capacity = = 0.4: pc- > capacity * 2 / / Note type conversion SLDatatype* tmp = (SLDatatype*) realloc (pc- > data, sizeof (SLDatatype) * newcapacity); if (tmp = = NULL) {perror ("SLCheckcapacity::realloc"); exit (- 1) } / / the open space tmp inserts data into the array pc- > data = tmp; pc- > capacity = newcapacity;} 2.2

We have three situations when inserting data, head-to-tail insertion and anywhere in the middle.

2.2.1 tail insertion

Start with the simplest tail insertion. When we insert the tail, we need to record the current size, so that we can find the tail directly. We need to note that before we insert it, we need to determine whether the current capacity is full. If it is full, we need to expand it, and if it is not full, we can insert it directly.

/ / tail insert void SLPushBack (SL* pc, SLDatatype x) {assert (pc! = NULL); / / need to determine whether additional SLCheckcapacity (pc) is needed; pc- > data [PC-> sz] = x; pc- > sz++;} 2.2.2

Head insertion is relatively more complicated. When there is no data on the head, we can see it as a tail plug directly. When there is data on the head, in order to avoid data coverage, we need to move all the data backward and put it in the head. When we move the data backward, we also need to determine whether it is full.

/ / insert void SLPushFront (SL* pc, SLDatatype x) {assert (pc! = NULL); SLCheckcapacity (pc); / move data int end = pc- > sz-1; while (end > = 0) {pc- > data [end + 1] = pc- > data [end];-- end } / / insert data pc- > data [0] = x; pc- > sz++;} 2.2.3 insert anywhere

When we insert at any position, there are three cases: when it is in the first position, the function of head insertion can be called, and in the last position, the function of tail insertion is called. When we are in the middle, we need to find the position we need to insert, and then move the data back from this position, and then insert it.

/ / insert void SLInsert (SL* pc, int pos, SLDatatype x) {assert (pc) at any location; / / determine whether pos is within the valid data range assert (pos > = 0 & & pos sz); SLCheckcapacity (pc); / / move data int end = pc- > sz-1; while (end > = pos) {pc- > data [end+1] = pc- > data [end] -- end;} pc- > data [pos] = x; pc- > sz++;} 2.3 Delete data

Deleting data is similar to the inserted data above, and we also need to put together three aspects to tear it apart: head deletion, tail deletion, and deletion anywhere in the middle. When we delete data, we just need to move the data after the data forward in turn and cover the data. Here we cannot use the free function to free up that address space for deletion, because the physical addresses of the sequential tables are contiguous. Linked lists are fine, which will be described in the next chapter.

2.3.1 tail deletion

There is no data behind the tail, so just make the last data 0.

/ / delete void SLPopBack (SL* pc) {assert (pc! = NULL); / / cannot delete more assert (pc- > sz > 0); pc- > sz--;} 2.3.2 headers

Move the data from the second location forward, it should be noted here that the deletion needs to be checked so as not to cross the line.

/ / deletion needs to be checked. If you delete too much, you will cross the boundary / / delete void SLPopFront (SL* pc) {assert (pc! = NULL); / / check assert (pc- > sz > 0); / / start from the second element and directly overwrite it int begin = 0; while (begin sz) {pc- > data [begin-1] = pc- > data [begin] + + begin;} pc- > sz--;} 2.3.3 Delete anywhere

Delete anywhere. We just need to move the number after the location we need to delete forward.

/ / delete void SLErase (SL* pc, int pos) {assert (pc! = NULL); assert (pos > = 0 & & pos) anywhere

Sz); int begin = pos; while (begin

Sz-1) {pc- > data [begin] = pc- > data [begin+ 1]; begin++;} pc- > sz--;} 2.4 search

We give a data x to represent the data we want to look for, go through the sequence table after going, and find it when the given X is equal to the X in the sequence table, and return the subscript of the current location.

/ / find int SLFind (SL* pc, SLDatatype x) {assert (pc! = NULL); for (int I = 0; I

Sz; + + I) {if (pc- > data [I] = = x) {return I;}} printf ("not found\ n"); return;} 2.5 modify data

When we want to modify the data in a certain place, we just enter the data in that location into the new data to overwrite it.

/ / change data void SlModify (SL* pc, int pos, SLDatatype x) {assert (pc! = NULL); if (pos > = 0 & & pos sz) {pc- > data [pos] = x;} else {printf ("out of range\ n");}} 2.6 destroy space

When we have finished using the sequence table, we need to note that our malloc space has not been released, which may cause memory leaks and other problems (please refer to the previous blog 'dynamic memory Development'). You need to use the free function to free memory.

/ / destroy space void SLDestory (SL* pc) {if (pc- > data) {free (pc- > data); pc- > data = NULL; pc- > capacity = pc- > sz = 0;}} this is the end of the content about "what is the concept and structure of the C language sequence table". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

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.