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

This article mainly explains "how to use C language array to achieve order table". The content of the article is simple and clear, and it is easy to learn and understand. let's study and learn how to use C language array to realize sequence table.

Linear table and order table linear table

Linear table (linear list) is a finite sequence of n data elements with the same characteristics, which is a widely used data structure.

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

Common linear tables: sequential lists, linked lists, stacks, queues, strings.

Sequence table

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.

Generally, it can be divided into:

Static sequence tables: using fixed-length arrays to store elements

Dynamic sequence tables: use dynamically opened arrays to store elements

The static sequence table / / defines the size of the static array, which facilitates the subsequent modification of the data type of the # define MAX_SIZE 50 beat / renamed array, and the subsequent modification of the typedef int SLDataType;// definition structure / / member variable as an array and the variable / / renamed structure data type that records the current number of data. It is convenient to write typedef struct SeqList {SLDataType arr [Max _ SIZE]; int size;} SL / / the following are the declarations of some common interfaces / / sequence table initialization / / after creating a static sequence table variable using the structure type It can be initialized with void SLInit (SL* psl) / / print the sequence table / / print out the values of the sequence table in order void SLPrint (SL* psl); / / check whether the sequence table is full / / every time you add data, you need to check whether it is full. If it is full, you cannot insert void SLCheck (SL* psl). / / insert an element at the end of the sequence table / / insert an element at the end of the sequence table / / because it is convenient to add data to the array, you can access void SLPushBack (SL* psl, SLDataType data) directly by using the array subscript; / / delete the tail of the sequence table / delete the data void SLPopBack (SL* psl) at the end of the sequence table; / / insert the header of the sequence table / / add a data void SLPushFront (SL* psl, SLDataType data) to the beginning of the sequence table / / delete the head of the sequence table / / delete the first bit data of the sequence table void SLPopFront (SL* psl); / / the sequence table looks for some data / / find whether there is some data in the sequence table, and return the corresponding subscript / / if it cannot be found, return-1int SLFind (SL* psl, SLDataType x) / / order table inserts x _ void SLModify at pos position / insert data x at specified subscript position, the data at the original x position and subsequent data move back void SLInsert (SL* psl, size_t pos, SLDataType x); / / sequence table deletes data at pos location void SLErase (SL* psl, size_t pos); / / order table modifies data at a certain location (SL* psl, size_t pos, SLDataType x)

The following is the specific implementation of these interfaces

/ / sequence table initialization void SLInit (SL* psl) {psl- > arr [0] = 0 SL* psl / only one element can be initialized here psl- > size = 0;} / / print sequence table void SLPrint (SL* psl) {int I = 0; if (psl- > size) {for (I = 0; I)

Size; iTunes +) {/ / output format, remember to modify printf ("% d", psl- > arr [I]) according to the type of SLDataTyped;} printf ("\ n");} else {printf ("Null\ n") }} / * / / check whether the sequence table is full void SLCheck (SL* psl) {if (psl- > size = = MAX_SIZE) {printf ("sequence table is full and cannot perform subsequent operations") } * / / void SLPushBack (SL* psl, SLDataType data) of sequence table {/ / insert data first check whether the space is full / / implementation method 1 is not good enough / * if (psl- > size = = MAX_SIZE) {printf ("space is full\ n"); return } else {psl- > arr [psl-> size] = data; psl- > size++;} * / / implementation method 2, simple and clear assert (psl- > size! = MAX_SIZE); psl- > arr [psl-> size] = data; psl- > size++ } / / sequence table tail deletion void SLPopBack (SL* psl) {/ / determine whether there are elements that can be deleted assert (psl- > size); psl- > size--;} / / sequence table header insert void SLPushFront (SL* psl, SLDataType data) {assert (psl- > size! = MAX_SIZE); / / src is used to move data int src = psl- > size While (src > = 1) {psl- > arr [src] = psl- > arr [src- 1]; src--;} psl- > arr [src] = data; psl- > size++;} / / header deletion of the sequence table void SLPopFront (SL* psl) {/ / determine whether there is still data to delete assert (psl- > size); int src = 0 While (src

Size- 1) {psl- > arr [src] = psl- > arr [src+ 1]; src++;} psl- > size--;} / / look up some data int SLFind (SL* psl, SLDataType x) {int I = 0; for (I = 0; I)

Size; return +) {if (psl- > arr [I] = = x) {/ / return the position of the data in the sequence table if found;}} / / return-1 return-1 if not found } / / insert xvoid SLInsert (SL* psl, size_t pos, SLDataType x) {assert (psl- > size) in the sequence table at the pos location

= 0 & & pos size); / / pos=0 or pos=size is equivalent to head insertion, followed by int end = psl- > size; while (end > pos) {psl- > arr [end] = psl- > arr [end- 1]; end--;} psl- > arr [pos] = x; psl- > size++ } / / sequence table deletes data at pos location void SLErase (SL* psl, size_t pos) {assert (psl- > size); assert (pos > = 0 & & pos)

Size); int start = pos + 1; while (start

Size) {psl- > arr [start-1] = psl- > arr [start]; start++;} psl- > size--;} / / void SLModify (SL* psl, size_t pos, SLDataType x) {assert (psl- > size); assert (pos > = 0 & & pos)

Size); psl- > arr [pos] = x;}

I put the test of the above code on Gitee. If you need it, you can refer to it.

Dynamic sequence table

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 leads to a large N, a waste of space, and a shortage of space. So in reality, we basically use dynamic sequence tables to dynamically allocate space as needed, so let's implement dynamic sequence tables.

/ / rename the data type of SL to facilitate subsequent modification of typedef int SLDataType;// to define the structure / / member variables as pointers to dynamic sequence tables, the number of data, and the capacity / / capacity of the sequence tables are used to manage the total size of the array. If size is equal to capacity, it means that the array is full and needs to be expanded / / redefined structure type names. It is convenient to operate typedef struct SeqList {SLDataType* p; int size. Int capacity;} SL;//----// are some commonly used interfaces, similar to static sequence tables / / SL initializes void SLInit (SL* ps) / / SL space check / / if the size equals capacity indicates that the array is full, you need to expand the capacity of void SLCheckCapacity (SL* ps); / / SL print void SLPrint (SL* ps); / / SL destroy / / because the array is opened dynamically, free the space void SLDestory (SL* ps) when the array is not used last; / / SL insert void SLPushBack (SL* ps,SLDataType x); / / SL delete void SLPopBack (SL* ps) / / SL headers insert void SLPushFront (SL* ps, SLDataType x); / / SL headers delete void SLPopFront (SL* ps); / / SL looks for certain data / / if it can be found, return the data in the order table subscript int SLFind (SL* ps, SLDataType x); / / SL inserts xvoid SLInsert (SL* ps, size_t pos, SLDataType x) at pos location; / / SL deletes the value void SLErase (SL* ps, size_t pos) of pos location / / SL modifies the data void SLModity (SL* ps, size_t pos, SLDataType x) of a location

The following is the specific implementation

/ / implementation of dynamic sequence table # include "DynamicSeqList.h" / / SL initializes void SLInit (SL* ps) {ps- > p = NULL; ps- > capacity = 0; ps- > size = 0;} / / SL space check void SLCheckCapacity (SL* ps) {if (ps- > size = = ps- > capacity) {ps- > capacity = (ps- > capacity = = 0)? 5: 2 * ps- > capacity SLDataType* tmp = (SLDataType*) realloc (ps- > p, (ps- > capacity) * sizeof (SLDataType)); if (tmp = = NULL) {printf ("realloc fail\ n"); exit (- 1);} ps- > p = tmp }} / / SL print void SLPrint (SL* ps) {if (ps- > size = = 0) {printf ("sequence table is empty\ n");} else {int I = 0; for (I = 0; I

Size; iTunes +) {/ / print format remember to modify printf ("% d", ps- > p [I]) according to the type of SLDataType;} printf ("\ n") } / / SL destroy / / the structure s is not completely destroyed here, but the member variables are assigned to 0void SLDestory (SL* ps) {free (ps- > p); ps- > p = NULL; ps- > size = ps- > capacity = 0;} / / SL insert void SLPushBack (SL* ps, SLDataType x) {SLCheckCapacity (ps); ps- > p [PS-> size] = x; ps- > size++ } / / SL delete void SLPopBack (SL* ps) {/ / Delete data need to determine whether the sequence table is empty assert (ps- > size > 0); ps- > size--;} / / SL header void SLPushFront (SL* ps, SLDataType x) {SLCheckCapacity (ps); int end = ps- > size While (end > 0) {ps- > p [end] = ps- > p [end- 1]; end--;} ps- > p [end] = x; ps- > size++;} / / SL header delete void SLPopFront (SL* ps) {/ / delete data need to determine whether the sequence table is empty assert (ps- > size > 0) Int start = 0; while (start

Size- 1) {ps- > p [start] = ps- > p [start+ 1]; start++;} ps- > size--;} / / SL to find a data int SLFind (SL* ps, SLDataType x) {/ / you need to determine whether the sequence table is empty, you can use assert or if to determine assert (ps- > size); int I = 0 For (I = 0; I)

Size; iTunes +) {if (x = = ps- > p [I]) {return I;} return-1;} / SL inserts xbank in the pos position / when pos is 0 or pos is size, it is equivalent to void SLInsert (SL* ps, size_t pos, SLDataType x) {SLCheckCapacity (ps) Assert (pos > = 0 & & pos size); int end = ps- > size; while (end > pos) {ps- > p [end] = ps- > p [end- 1]; end--;} ps- > p [end] = x; ps- > size++ } / / SL delete the value of pos location void SLErase (SL* ps, size_t pos) {/ / determine whether the location to be deleted is within the size assert (pos > = 0 & & pos

Size); int start = pos + 1; while (start

Size) {ps- > p [start-1] = ps- > p [start]; start++;} ps- > size--;} / / SL modify the data void SLModity (SL* ps, size_t pos, SLDataType x) of a location {/ / determine whether the location to be modified is within size assert (pos > = 0 & & pos)

Size); ps- > p [pos] = x;} Thank you for reading, the above is the content of "how to use C language array to achieve order table". After the study of this article, I believe you have a deeper understanding of how to use C language array to achieve order 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.