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

This article introduces the relevant knowledge of "how to construct the sequence table of data structure in C language". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Preface

Master the sequence list before learning the linked list

What is a sequence table?

The sequence table uses a storage unit with a continuous physical address to store the linear structure of the data elements in sequence. in general, the array storage is used to complete the addition, deletion, query and modification of the data on the array.

Sequence tables can generally be divided into:

1. Static sequence table: use fixed-length array storage. two。 Dynamic sequence table: use dynamically opened array storage.

Tip: due to the limited static function, the dynamic sequence table is mainly discussed here.

First, the construction of sequence table VS function 1. The construction of sequential table

Example:

Dynamic storage of typedef int SeqDataType// sequence table typedef struct SeqList {SeqDataType* a; / points to dynamically opened array size_t size; / / number of valid data size_t capicity; / / size of capacity space} SeqList

The SeqDataType definition is used here because we don't know what type of array an is, so if we want to use the function flexibly, we should define the type of SeqDataType in advance (in this case, int), so that it is easy to operate when the structure type is changed later.

two。 API implementation (function) / basic add, delete, query and modify interface / / sequence table initialization void SeqListInit (SeqList* psl, size_t capacity); / sequence table destruction void SeqListDestory (SeqList* psl); / sequence table print void SeqListPrint (SeqList* psl); / / check the space, if full, add void CheckCapacity (SeqList* psl); / / insert void SeqListPushBack at the end of the sequence table (SeqList* psl, SLDataType x) / / sequence footer deletion void SeqListPopBack (SeqList* psl); / / sequence header insert void SeqListPushFront (SeqList* psl, SLDataType x); / / sequence header deletion void SeqListPopFront (SeqList* psl); / / sequence table lookup int SeqListFind (SeqList* psl, SLDataType x); second, function specific analysis 1. Initialization

Before realizing the specific project function, you should be prepared in advance, that is, initialize and empty it. The assert function is explained below.

The code is as follows (example):

Void SeqListInit (SeqList* pq) / / initialize {assert (pq); / / assert to determine whether it is possible to execute pq- 0 > a = NULL; pq- > size = 0; pq- > capacity = 0;} 2. Destroy

Destruction is what needs to be done after the end, because it is dynamic and space release needs to be considered to avoid space leakage. (destruction is mentioned first because it comes first with initialization.)

The code is as follows (example):

Void SeqListDestory (SeqList* pq) {assert (pq); free (pq- > a); pq- > a = NULL; pq- > capacity = pq- > size = 0;} 3. Check whether size and capacity are overflowing

Dynamic process is to change the size of our array according to the input data, so we need to correctly avoid the overflow, as to why the overflow occurs, because we set its space to 0 at initialization. No matter how much data is entered for the first time, it will overflow.

Void SeqCheckCapacity (SeqList* pq) {if (pq- > size = = pq- > capacity) / / is full and needs to be added {int newcapacity = pq- > capacity = 0.4: pq- > capacity * 2; / / SeqDataType* newA = malloc (sizeof (SeqDataType) * newcapacity); SeqDataType* newA = realloc (pq- > aQuinsizeof (SeqDataType) * newcapacity) / / or directly expand if (newA = = NULL) {printf ("realloc fail\ n"); exit (- 1);} pq- > a = newA; pq- > capacity = newcapacity;}}

It is customary to double the size of the realloc when expanding its capacity. Since there are two cases in which the expansion of the API is divided into two cases (not discussed here), we need to cut off and print an error if the expansion fails.

4. Tail increment function (implementation)

Code first:

Void SeqListPushBack (SeqList* pq, SeqDataType x) {assert (pq); SeqCheckCapacity (pq); pq- > a [PQ-> size] = x; pq- > size++;}

As the name implies, it adds content to the tail. Size corresponds to the next digit of the valid array subscript and assigns this position. Finally, the valid array size should be + 1, because we do not know whether its capacity is equal to size before the tail increment.

Therefore, we need to check the seqCheckCapacity, if equal, we need to expand the capacity.

5. Print void SeqListPrint (SeqList* pq) {assert (pq); for (int I = 0; I

Size; + + I) {printf ("% d", pq- > a [I]);} printf ("\ n");}

There is nothing specific here, just to ensure that the program function can be realized concretely and completely.

For other functions, see the following code

3. Implement the specific function code page (SeqList.c) # define _ CRT_SECURE_NO_WARNINGS 1#include "SeqList.h" # includevoid SeqListInit (SeqList* pq) / initialize {assert (pq); / / assert to determine whether it is possible to execute 1 pq- > a = NULL; pq- > size = 0; pq- > capacity = 0;} void SeqListDestory (SeqList* pq) {assert (pq); free (pq- > a) Pq- > a = NULL; pq- > capacity = pq- > size = 0;} void SeqCheckCapacity (SeqList* pq) {if (pq- > size = = pq- > capacity) / / full, need to increase the capacity {int newcapacity = pq- > capacity = 0.4: pq- > capacity * 2; / / SeqDataType* newA = malloc (sizeof (SeqDataType) * newcapacity); SeqDataType* newA = realloc (pq- > acothesizeof (SeqDataType) * newcapacity) / / or directly expand if (newA = = NULL) {printf ("realloc fail\ n"); exit (- 1);} pq- > a = newA; pq- > capacity = newcapacity }} void SeqListPushBack (SeqList* pq, SeqDataType x) {assert (pq); SeqCheckCapacity (pq); pq- > a [PQ-> size] = x; pq- > size++;} void SeqListPrint (SeqList* pq) {assert (pq); for (int I = 0; I

Size; + + I) {printf ("% d", pq- > a [I]);} printf ("\ n");} void SeqListPushFront (SeqList* pq, SeqDataType x) {assert (pq); SeqCheckCapacity (pq); int end = pq- > size-1; while (end > = 0) {pq- > a [end + 1] = pq- > a [end] End--;} pq- > a [0] = x; pq- > size++;} void SeqListPopBack (SeqList* pq) {assert (pq); assert (pq- > size > 0);-- pq- > size;} void SeqListPopFront (SeqList* pq); / / tail deletion is not implemented temporarily

Test.c main function code page

# define _ CRT_SECURE_NO_WARNINGS 1#include#include#include "SeqList.h" void TestSeqList1 () {SeqList s; SeqListInit (& s); / / SeqListPushBack (& s, 1); SeqListPushBack (& s, 2); SeqListPushBack (& s, 3); SeqListPushBack (& s, 4); SeqListPushBack (& s, 5); SeqListPushFront (& s, 0); SeqListPushFront (& s, 0) SeqListPushFront (& s, 0); SeqListPushFront (& s, 0); SeqListPrint (& s); SeqListPopBack (& s); SeqListPrint (& s); SeqListPopBack (& s); SeqListPrint (& s); SeqListDestory (& s); / /} int main () {TestSeqList1 (); return 0;}

This is the end of the content of "how to construct the sequence table of data structure in C language". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.