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

This article mainly explains "how to realize the C language sequence table". The content of the explanation in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought. Let's study and learn how to realize the C language sequence table.

Concept and structure

A sequential table is a linear structure in which data elements are stored successively in a storage unit with a continuous physical address, usually using an array. Complete the addition, deletion, query and modification of the data on the array.

Sequence tables can generally be divided into:

Static sequence table: uses a fixed-length array to store elements, and the number of elements cannot be modified.

/ / static storage of sequence table # define N 7typedef int SLDataType;typedef struct SeqList {SLDataType array [N]; / / number of size_t size;// valid data of fixed length array} SeqList

Dynamic sequence table

/ / the dynamic storage of the sequence table typedef struct SeqList {SLDataType* array;// points to the dynamically opened array, and there is not enough space to increase the number of valid data in size_t size;//, the size of size_t capacity;// capacity space}; interface implementation

Static sequence tables are only suitable for scenarios where you know how much data you need to store. The fixed length array of the static sequence table causes the N to be larger, the space to be more expensive, and the less to be used. So in reality, we basically use dynamic sequence tables to dynamically allocate space as needed, so let's implement dynamic sequence tables.

1 dynamic storage of sequential table data stored in typedef int SLDataType;// sequential table. Here, it is assumed that int type typedef struct SeqList {int* int capacity;// / points to dynamically opened array space, which can increase the number of int size;// storage data at any time. Int capacity;// storage space size} SL,SeqList;2 sequential table initialization void SeqListInit (SeqList* psl) / / declare void SeqListInit (SeqList* psl) {assert (psl); / / make the assertion because when psl is NULL, the following operation cannot be done because null pointers cannot be dereferenced. Psl- > a = NULL; psl- > size = 0; psl- > capacity = 0;} / / function implementation

Note: the assertion is made because when psl is NULL, the following cannot be done because null pointers cannot be dereferenced, as is the case later.

3 destruction of sequential tables void SeqListDestroy (SeqList* psl); void SeqListDestroy (SeqList* psl) {assert (psl); free (psl- > a); psl- > a = NULL; psl- > capacity = psl- > size = 0;}

Note: the pointer in parentheses after free must be the space opened up by malloc, and there must be no deviation (that is, the pointer cannot be moved).

Here is an example:

There is no problem with using it like this, but there is a problem with using it like this:

After performing the self-increment operation, tmp points to the location shown in the following figure:

The location of the free is after the tmp++, which does not comply with the provisions of the C language, and even if it is normally released, the front piece of int space will also cause memory leakage, that is, the dynamically opened memory will forget to release.

4 insert void SeqListPushBack (SeqList* psl,SLDataType x) in the sequence table; / / declare void SeqListPushBack (SeqList* psl,SLDataType x) {assert (psl); / / expand SeqListCheckCapacity (psl) if it is full; psl- > a [psl-> size] = x; psl- > size++;}

5 sequence table tail deletion void SeqListPopBack (SeqList* psl); void SeqListPopBack (SeqList* psl) {assert (psl); if (psl- > size > 0) {psl- > size-= 1;}} 6 sequence table header insert void SeqListPushFront (SeqList* psl, SLDataType x); void SeqListPushFront (SeqList* psl, SLDataType x) {assert (psl); SeqListCheckCapacity (psl); int end = psl- > size-1 While (end > = 0) {psl- > a [end+1] = psl- > a [end];-- end;} psl- > a [0] = x; psl- > size++;}

The header insertion of the sequential table involves the movement of subsequent elements, and the elements in the sequential table should be moved from the back, because there will be overwriting if you start moving from the front. The following is an illustration:

7 head deletion of sequence table

By the same token, if you want the element not to be overwritten, you can only move forward and backward.

Void SeqListPopFront (SeqList* psl); void SeqListPopFront (SeqList* psl) {/ / remove data to make room for the head / / method 1: move / * assert (psl) from 1; if (psl- > size > 0) {int begin = 1; while (begin)

Size) {psl- > a [begin-1] = psl- > a [begin]; begin++;} psl- > size--;} * / / method 2: move assert (psl) from 0 If (psl- > size > 0) {int begin = 0; while (begin

Size- 1) {psl- > a [begin] = psl- > a [begin+ 1]; begin++;} psl- > size--;}}

The following figure shows the difference between the two modes of movement:

Q: why can't you just add one to the pointer?

The pointer when free frees up space must be the same as that used by malloc to open up space.

The space created by mallo is wasted, that is, the space of 0 is wasted and cannot be used because it is legally applied for.

8 check and expand the capacity of sequential tables void SeqListCheckCapacity (SeqList* psl); void SeqListCheckCapacity (SeqList* psl) {assert (psl); if (psl- > capacity = = psl- > size) {size_t newCapacity = psl- > capacity = = 0.4: psl- > capacity * 2; SLDataType* tmp = (SLDataType*) realloc (psl- > a, sizeof (SLDataType) * newCapacity) If (tmp = = NULL) {printf ("realloc fail\ n"); exit (- 1);} else {psl- > a = tmp; psl- > capacity * = 2 }}}

Note 1: what is considered here is that if the capacity is not enough, the capacity will be expanded to twice the original capacity, but the initial capacity is 0, so the initial capacity of 0 should be taken into account.

Note 2: check whether the expansion is successful, that is, to determine whether the space you just applied for is empty.

9 insert void SeqListInsert (SeqList* psl,size_t pos,SLDataType x) anywhere in the sequence table; void SeqListInsert (SeqList* psl,size_t pos,SLDataType x) {assert (psl); / / milder check method / * if (pos > psl- > size) {exit (- 1);} * / assert (pos size) / / the more violent inspection method SeqListCheckCapacity (psl); size_t end = psl- > size; while (end > pos) {psl- > a [end] = psl- > a [end-1];-- end;} psl- > a [pos] = x; psl- > size++;}

Note:

Q: why does end start with psl- > size?

A: what needs to be noted here is the type of pos and end. Why? Because both are unsigned types, it is especially important to note that when end reaches-1, it will become a large number. If you use this as the subscript for access, you will certainly cross the boundary to access memory. Consider an extreme case: when pos is 0, the minimum end is 0, so there is no crossing the line at this time, but if end starts with psl- > size-1 Then the statement inside the while loop looks like this:

While (end > pos) {psl- > a [end+1] = psl- > a [end];-- end;}

In the end, the minimum value of end will become-1, but because end is of type size_t, it will become a large number, and the condition will always be satisfied when the whle () loop condition is determined, and after entering the loop body, there will be cross-boundary access to memory.

10 delete void SeqListErase (SeqList* psl, size_t pos) anywhere in the sequence table; void SeqListErase (SeqList* psl, size_t pos) {assert (psl); assert (pos size); size_t begin = pos+1; while (begin)

Size) {psl- > a [begin-1] = psl- > a [begin]; + + begin;} psl- > size--;} 11 print void SeqListPrint (SeqList* psl); void SeqListPrint (SeqList* psl) {assert (psl); for (int I = 0; I)

Size; iTunes +) {printf ("% d", psl- > a [I]);} printf ("\ n");} 12 lookup int SeqListFind (SeqList* psl,SLDataType x) for sequential table elements; int SeqListFind (SeqList* psl,SLDataType x) {assert (psl); for (int I = 0; I)

Size; iSense +) {if (psl- > a [I] = = x) return iPlachap / found the corresponding element and return the corresponding subscript} return-1 Sexabash / indicating that the corresponding element was not found} 13 modified void SeqListModify of sequence table elements (SeqList* psl, size_t pos, SLDataType x) Void SeqListModify (SeqList* psl, size_t pos, SLDataType x) {assert (psl); assert (pos

Size); psl- > a [pos] = x;} Thank you for your reading. The above is the content of "how to realize the C language sequence table". After the study of this article, I believe you have a deeper understanding of how to realize the C language sequence table, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.