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

This article mainly introduces the relevant knowledge of how the C language realizes the operation of the sequence table, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe you will gain something after reading this article on how to realize the operation of the sequence table in C language. let's take a look.

Linear table

A linear table (linear list) is a finite sequence of n data elements with the same characteristics. Linear table is a kind of data structure which is widely used in practice. the common linear tables are: sequential list, linked list, stack, queue, string and so on.

A linear table is logically a linear structure, that is, a continuous straight line. However, it is not necessarily continuous in physical structure. When linear tables are physically stored, they are usually stored in the form of arrays and chains.

Sequence table

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

In general, sequence tables can be divided into the following two categories:

1. Static sequence tables: use fixed-length arrays to store elements.

two。 Dynamic sequence table: use dynamically opened array storage.

Implementation of sequence table interface

Static sequence tables are only suitable for scenarios where you know how much data you need to store. Static sequence tables are not flexible enough. So we basically use dynamic sequence tables to allocate size according to the amount of space needed, all of which we implement dynamic sequence tables.

Define a structure first:

Typedef int SLDataType;typedef struct SeqList {SLDataType* a; int size; / / number of data stored int capacity; / / capacity space size} SeqList;1. Initialize void SeqListInit (SeqList* ps); void SeqListInit (SeqList* ps) {assert (ps); / / check the validity of pointers ps- > a = NULL; / / if you don't know how much space to open, assign NULL ps- > capacity = ps- > size = 0;}

When we open up space for ps- > a, we can also open it in the following way, which is even easier (we need to check the validity of the space after opening up the space), but both are fine.

STDataType*tmp= (STDataType*) malloc (sizeof (SeqList) * 2); 2. Sequential tablespaces are added / / checked for void SeqListCheckCapacity (SeqList* ps); void SeqListCheckCapacity (SeqList* ps) {assert (ps); if (ps- > capacity = = ps- > size) {size_t newcapacity = ps- > capacity = 0? 4: ps- > capacity * 2; SLDataType* tmp = realloc (ps- > a, sizeof (SLDataType) * newcapacity) If (tmp = = NULL) {printf ("CheckCapacity::%s\ n", strerror (errno)); / / if the space opening fails, the reason for the print opening failure exit (- 1) / / if space development fails, terminate the program} else {ps- > a = tmp; ps- > capacity = newcapacity;}

1. Here realloc space, if there is not enough capacity, we will double the capacity, but our initial initialization space is likely to be zero, so we should take this situation into account.

The 2.realloc space may fail for some reason, so check the opened space, that is, to determine whether the applied space is empty (NULL).

3. Sequential table printing / / sequential table printing void SeqListPrint (SeqList* ps); void SeqListPrint (SeqList* ps) {assert (ps); for (int I = 0polii)

Size;++i) / / traverse in turn, printing out each message {printf ("% d", ps- > a [I]);} printf ("\ n");} 4. Tail-inserted data

/ insert void SeqListPushBack (SeqList* ps, SLDataType x); void SeqListPushBack (SeqList* ps, SLDataType x) {assert (ps); SeqListCheckCapacity (ps); ps- > a [PS-> size] = x; ps- > size++;} 5. Delete the data at the end / / delete the data at the end of the sequence table void SeqListPopBack (SeqList* ps); void SeqListPopBack (SeqList* ps) {assert (ps); if (ps- > size > 0) / / prevent the data from being deleted, and the size has a negative number {ps- > size--;}}

Note: conditions must be added when size is subtracted to prevent negative subscript numbers.

6. Headline data

/ insert void SeqListPushFront (SeqList* ps, SLDataType x); void SeqListPushFront (SeqList* ps, SLDataType x) {assert (ps); SeqListCheckCapacity (ps); / / check the space capacity int end = ps- > size-1; while (end > = 0) {ps- > a [end + 1] = ps- > a [end];-- end } ps- > a [0] = x; ps- > size++;} 7. Head delete data / / sequence header delete void SeqListPopFront (SeqList* ps); void SeqListPopFront (SeqList* ps) {assert (ps); / / move data overlay delete if (ps- > size > 0) / / ensure that data can be deleted to prevent negative subscript {int begin = 1; while (begin)

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

Note: head deletion must make sure that the subscript is greater than 0, otherwise delete a subscript, the current subtraction to a negative number, the program will make an error. When the head is deleted, the data is overwritten one bit in turn from front to back.

8. Insert data at the pos subscript

/ the sequence table inserts data void SeqListInsert (SeqList* ps, size_t pos, SLDataType x) at the pos location; void SeqListInsert (SeqList* ps, size_t pos, SLDataType x) {assert (ps); if (pos > ps- > size) {printf ("pos out of bounds\ n"); return;} SeqListCheckCapacity (ps); size_t end = ps- > size While (end > pos) {ps- > a [end] = ps- > a [end-1];-- end;} ps- > a [pos] = x; ps- > size++;}

Special attention needs to be paid to the subject matter here, as shown in the following figure:

There are two ways to write the loop here, one as above, and the other is the one below.

Int end = ps- > size-1;while (end > = int) pos) {ps- > a [end+1] = ps- > a [end];-- end;}

Note: comparing the above two ways of writing, we notice the types of pos and end. Because the coordinates cannot be negative, pos is of type size_t. For the second case: int end=ps- > size- 1, the value of the loop to the end of the end will become-1, but the type of pos will be size_t, so when end is compared with pos, shaping will occur, so that the unsigned end shaping will be promoted to a signed number and pos comparison, so the while condition holds, it will continue to loop, resulting in out-of-line access to memory. Our solution to this is to cast the pos to an int type, such as the appeal code.

For the first case: int end=ps- > size, the value of end at the end of the loop is 0, which is an unsigned number, so the mobile coverage happens to be perfect, and there will be no out-of-bounds access. So we recommend the first method.

9. Delete data / / sequence table at pos subscript Delete data at pos location void SeqListErase (SeqList* ps, size_t pos); void SeqListErase (SeqList* ps, size_t pos) {assert (ps); if (pos > = ps- > size) {printf ("pos out of bounds\ n"); return;} size_t begin = pos + 1; while (begin

Size) {ps- > a [begin-1] = ps- > a [begin]; + + begin;} ps- > size--;} 10. Data search

Traverse the data search in turn, and if the corresponding data is found, its subscript is returned. If it cannot be found,-1 is returned.

/ / sequence table lookup int SeqListFind (SeqList* ps, SLDataType x); int SeqListFind (SeqList* ps, SLDataType x) {assert (ps); for (int I = 0 int I)

Size;++i) {if (ps- > a [I] = = x) {return I;}} return-1;} 11. Sequence list destroy

When we use dynamic application space, be sure to release the dynamically opened memory after using it. Otherwise, it may cause a memory leak.

/ / sequence table destruction void SeqListDestroy (SeqList* ps); void SeqListDestroy (SeqList* ps) {assert (ps); free (ps- > a); ps- > a = NULL; ps- > size = ps- > capacity = 0;} this is the end of the article on "how C language implements the operation of sequence tables". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to operate the sequence table in C language". If you want to learn more knowledge, you are welcome to follow the industry information channel.

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.