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

In this article, the editor introduces in detail "how to realize the sequence table of C language". The content is detailed, the steps are clear, and the details are handled properly. I hope this article "how to realize the sequence table of C language" can help you solve your doubts. Let's follow the editor's ideas to learn new knowledge.

1. Linear table

A linear table (linear list) is a finite sequence of n data elements with the same characteristics. Linear table is a widely used data structure in practice. Common linear tables are sequential lists, linked lists, stacks, queues, strings.

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.

two。 Sequence Table 2.1 Concepts and structures

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:

1. Static sequence table: use fixed-length array storage.

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

/ / static storage of sequential table # define N 100struct SeqList {int a [N]; / number of int size;// valid data of fixed length storage}; / / dynamic storage of sequential table typedef struct SeqList {SeqDataType* int size;// / pointing to dynamically opened array number of valid data int capacity; / / capacity} SeqList

A sequential table is essentially an array, adding two requirements to the array:

1. In the process of inserting data, it can grow dynamically.

two。 And the data stored in it must be continuous from left to right.

Defects in the sequence table

1. Dynamic compatibilization has performance consumption

two。 When the head is inserted into the data, the data needs to be moved.

2.2 provide an interface

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.

First, provide the interface in the header file:

Typedef int SeqDataType; / / what type of data needs to be inserted, change it to the corresponding type typedef struct SeqList {SeqDataType* a role / point to dynamically opened array int size; / / number of valid data int capacity; / / capacity} SeqList;// memory management data structure provides an interface for adding, deleting, querying and modifying / / sequence table initialization void SeqListInit (SeqList* pq) / / sequence table destroy void SeqListDestory (SeqList* pq); / / sequence table print void SeqListPrint (SeqList* pq); / print array / / check space, if full, add void SeqCheckCapacity (SeqList* pq) / / sequence footer insert void SeqListPushBack (SeqList* pq, SeqDataType x); / / sequence header insert void SeqListPushFront (SeqList* pq, SeqDataType x); / / sequence footer delete void SeqListPopBack (SeqList* pq); / / sequence header delete void SeqListPopFront (SeqList* pq) / / look up xint SeqListFind (SeqList* pq, SeqDataType x) in the sequence table; / / find the subscript returned, but not return-1 int pos / insert data void SeqListInsert (SeqList* pq, int pos, SeqDataType x) at the specified location in the sequence table; / / insert data at the subscript pos location / / delete the data void SeqListErase (SeqList* pq, int pos) at the specified location in the sequence table / / delete the data at the subscript pos location / / the sequence table replaces the data void SeqListModify (SeqList* pq, int pos, SeqDataType x) at the specified location; / / change the value of the subscript pos location to x2.3 interface implementation

Implement the interface function in the source file SeqList.c

(1) sequence table initialization

Void SeqListInit (SeqList* pq) {assert (pq! = NULL); / / or assert (pq); assertion prevents passing null pointer pq- > a = NULL; pq- > size = 0; pq- > capacity = 0;}

(2) sequence table destruction

Void SeqListDestory (SeqList* pq) {assert (pq); free (pq- > a); pq- > a = NULL; pq- > size = 0; pq- > capacity = 0;}

(3) print the sequential table

Void SeqListPrint (SeqList* pq) {assert (pq); for (int I = 0; I

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

(4) check the space and increase the capacity if it is full.

/ / check whether you need to expand void SeqCheckCapacity (SeqList* pq) {/ / full and increase if (pq- > size = = pq- > capacity) {int newcapacity = (pq- > capacity = = 0.4: pq- > capacity * 2) / / if the address received by realloc is empty, it will, like malloc, open up a new space SeqDataType* newA = realloc (pq- > a, sizeof (SeqDataType) * newcapacity); / / realloc returns the address if (newA = = NULL) {printf ("realloc fail\ n") of the opened new space Exit (- 1); / / exit if you fail} pq- > a = newA; pq- > capacity = newcapacity;}}

(5) insert at the end of the sequence table.

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

(6) Sequential header insertion

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++;}

(7) Delete at the end of the sequence table

Void SeqListPopBack (SeqList* pq) {assert (pq); assert (pq- > size > 0); pq- > size--;}

(8) sequence header deletion

Void SeqListPopFront (SeqList* pq) {assert (pq); assert (pq- > size > 0); int begin = 0; while (begin)

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

(9) sequence table lookup x

Int SeqListFind (SeqList* pq, SeqDataType x) {assert (pq); for (int I = 0; I

Size; + + I) {if (pq- > a [I] = = x) {return x;}} return-1 scramble / not found}

(10) the sequence table inserts data at the specified location

Void SeqListInsert (SeqList* pq, int pos, SeqDataType x) {assert (pq); assert (pos > = 0 & & pos

Size); SeqCheckCapacity (pq); / / check whether you need to expand int end = pq- > size-1 position while (end > = pos) {pq- > a [end + 1] = pq- > a [end]; end--;} pq- > a [pos] = x Ting PQ-> size++;} void SeqListInsert (SeqList* pq, int pos, SeqDataType x) {assert (pq); assert (pos > = 0 & pos)

Size); SeqCheckCapacity (pq); / / check whether capacity expansion is required: int end = pq- > size-1; while (end > = pos) {pq- > a [end + 1] = pq- > a [end]; end--;} pq- > a [pos] = x; pq- > size++;}

(11) the sequence table deletes data at the specified location

Void SeqListErase (SeqList* pq, int pos) {assert (pq); assert (pos > = 0 & & pos

Size); int begin = pos; while (begin size- 1) {pq- > a [begin] = pq- > a [begin+ 1]; begin++;} pq- > size--;}

(12) the sequence table replaces the data at the specified location

Void SeqListModify (SeqList* pq, int pos, SeqDataType x) {assert (pq); assert (pos > = 0 & & pos

Size); pq- > a [pos] = x;} at this point, the article "how to implement the sequence Table of C language" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it before you can understand it. If you want to know more about related articles, 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.