[brother Yang takes you to play with the linear table (I) - sequence table]

Tips ： When the article is finished , Directories can be generated automatically , How to generate it, please refer to the help document on the right

List of articles

• Preface
• One 、 The concept and structure of sequence table ：
• 1. Static sequence table
• 2. The concept and structure of dynamic sequential table algorithm
• 3. Code implementation of sequence table
• Two 、 Code implementation of sequence table ：
  • 1. Print data
  • 2. Define a linear table
  • 3. Destroy the linear table
  • 4. Expand capacity
  • 5. Insert elements by head interpolation
  • 6. To insert elements by tailgating
  • 7. Delete elements by header deletion
  • 8. Delete elements by tail deletion
  • 9. Insert elements anywhere
  • 10. Delete elements anywhere
  • 11. Find the element location and import it into the warehouse
• summary

---

Preface

The linear table ：

The linear table is n A finite sequence of data elements with the same characteristics . It is a data structure widely used in practice , Common linear tables in data structures are ： The order sheet 、 Linked list 、 Stack 、 queue 、 Strings and so on .

A linear table is logically linear , That is, a continuous straight line , But his physical structure is not necessarily continuous , When it is physically stored , It is usually stored in the form of array and chain structure .

1. Definition of sequence table and code implementation .

2. Single linked list definition and code implementation .

3. Definition and code implementation of bidirectional linked list

---

One 、 The order sheet

1 Concept and structure

        A sequence table is a linear structure in which data structure elements are sequentially stored in a storage unit with a continuous physical address , In general, array storage is used . Add, delete, check and modify the data on the array .

        The structure of the sequence table

1

2

3

4

5

6

7

        The sequence table is often divided into Static sequence table and Dynamic sequence table

        1） Static sequence table ： Use a fixed length array to store elements .

         expand ： When using static sequence table, you need to define a fixed length array , Then use macro definitions , Define a fixed capacity for the array , The definitions are as follows ：

​#define MAX_SIZE 50

typedef int DataType;
typedef struct SeqList{
    DataType arr[MAX_SIZE];
    int size;
}SList;

        2） Deficiency of static sequence table ：

         When defining the capacity of an array, if the defined array is too large, it will cause a waste of memory space , If it is too small, the remaining data cannot be stored , Inconvenience to operation . So we often use dynamic types when using , Instead of using static types .

        3） Dynamic sequence table ： Adopt dynamic array storage

typedef int DataType;

typedef struct SeqList{
    DataType* arr;    // Define an array whose pointer points to dynamic development 
    int size;        // Number of valid data 
    int capacity;    // Size of space capacity 
}SList;

1

2

3

4

NULL

NULL

NULL

If the space is insufficient, you can expand

        4） expand ：

        a：typedef Use ：

         there typedef The use of is equivalent to renaming, equivalent to the original structure “struct SeqList” Rename it to “SList”, In this way, you can use it directly when you continue to write code “SList” To define the structure .

        b： Definition DataType The meaning of ：

         As mentioned above “typedef” Equivalent to redefining 、 Rename means , Put the “int” Type defined as ”DataType“, If you need to change the data type in the sequence table to ”double“ or ”char“ Other types can be modified directly ”DataType“ by ”double“ or ”char“ Wait for other types , Otherwise, you need to put the ”int“ Change the type .

        c: Use of the pointer ：

         Arrays are not directly used in dynamic memory development , Instead, use array pointers （ Address of array ）.

When the sequential table space is insufficient, you can directly use the dynamic memory development function to directly develop memory .

2 Code implementation

1） The header file ：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;

typedef struct SeqList {
	DataType* arr;
	int capacity;
	int size;
}SList;

void SListPrint(SList* L);
void SListInit(SList* L);
void SListDestroy(SList* L);
void SListCheckCapacity(SList* L);
void SListPushBack(SList* L, DataType x);
void SListPushFront(SList* L, DataType x);
void SListPopFront(SList* L);
void SListPopBack(SList* L);
void SListInsert(SList* L,int pos,DataType x);
void SListErase(SList* L);
int SListFind(SList* L);
void SListModify(SList* L, int pos, DataType x);

2） Source code display ：
1） Element printing ：

expand ：

a）”assert“ Assertion , It can be understood as certain satisfaction or certain correctness .

for example ：”assert（L）“ It means the address of the sequence table L There must be , If it doesn't exist , The code will not be executed further , That is to say, when the code is running , Parameters must be passed correctly , If an empty address is passed into the function , The code will not execute .

b） Because the parameters of the function interface are formal parameters , A formal parameter is just a temporary copy of an argument , Changes in formal parameters cannot affect arguments , Therefore, the address must be passed in the function interface .

​
#define  _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void SListPrint(SList* L)
{
	assert(L);
	for (int i = 0; i < L->size; i++)
	{
		printf("%d", L->arr[i]);
	}
	printf("\n");
}

​

2） Initialization of linear table ：

expand ：”size“ Represents the number of opportunities of elements in the sequence table ,”capacity“ Represents the size of the capacity , Both are zero at initialization .

void SListInit(SList* L)
{
	assert(L);
	L->arr = NULL;
	L->size = L->capacity = 0;
}

3） Destruction of linear tables ：

expand ： Only dynamically opened memory can be used ”free“ To release , After release, it needs to be empty , Of course, you can also leave it blank （ Set as NULL）, Because the system will automatically recycle , But we suggest recycling , Otherwise, it is easy to cause wild pointer , If the pointer is not set to NULL, It means that he also has access to the address , But the address has been ”free“ Released , This time will lead to illegal access .

void SListDestroy(SList* L)
{
	assert(L);
	if (L->arr)
	{
		free(L->arr);
		L->arr = NULL;
		L->capacity = L->size = NULL;
	}
}

4） Expand capacity ：

expand ：

a）”DataType* tmp“ Is to define a ”DataType“ An array of types ,”tmp“ Is the address of this array .

b）”realloc“ It is also a dynamic memory allocation function , It is used for capacity expansion , First, pass in the first address of the object to be expanded , Enter the size to be expanded .

void SListCheckCapacity(SList* L)
{
	assert(L);
	if (L->capacity == L->size)
	{
		int newcapacity = L->capacity == 0 ? 4 : L->capacity * 2;
		DataType* tmp = (DataType*)realloc(L->arr, newcapacity * sizeof(DataType));
		if (tmp == NULL)
		{
			printf("realloc is fail\n");
			return;
		}
		L->arr = tmp;
		L->capacity = newcapacity;
	}
}

5） The tail interpolation ：

expand ： there ”size“ Represents the next position of the last element in the array .

void SListPushBack(SList* L, DataType x)
{
	assert(L);
	SListCheckCapacity(L);
	L->arr[L->size] = x;
	L->size++;
}

6） The first interpolation ：

expand ： The head insertion method must move all the elements at the position to be inserted and the subsequent elements backward by one position before it can be inserted , And the movement must start from the last element , Otherwise, Hu will cause mutual coverage of elements .

        And it should be noted that the expansion check must be carried out at each insertion , More than that, there is the existence of expansion function .

void SListPushFront(SList* L, DataType x)
{
	assert(L);
	SListCheckCapacity(L);
	int end = L->size - 1;
	while (end >= 0)
	{
		L->arr[end + 1] = L->arr[end];
		--end;
	}
	L->arr[0] = x;
	L->size++;
}

7） Head deletion ：

expand ： Starting from the second element, move each element forward to cover the previous element , To delete the first element , The second element overrides the first element , The third element covers the second element , And so on .

void SListPopFront(SList* L)
{
	assert(L);
	assert(L->size > 0);
	int begin = 1;
	while (begin < L->size)
	{
		L->arr[begin - 1] = L->arr[begin];
		++begin;
	}
	L->size--;
}

8） Tail deletion ：

expand ： Direct will ”size“ Adjust it

void SListPopBack(SList* L)
{
	assert(L);
	assert(L->size > 0);
	L->size--;
}

9） Insert at any position ：

void SListInsert(SList* L, int pos, DataType x)
{
	assert(L);
	assert(pos >= 0 && pos <= L->size);
	SListCheckCapacity(L);
	int end = L->size - 1;
	while (end >= pos)
	{
		L->arr[end + 1] = L->arr[end];
		--end;
	}
	L->arr[pos] = x;
	L->size++;
}

10） Delete anywhere ：

void SListErase(SList* L,int pos)
{
	assert(L);
	assert(pos >= 0 && pos <= L->size);
	int begin = pos + 1;
	while (begin < L->size)
	{
		L->arr[begin - 1] = L->arr[begin];
		++begin;
	}
	L->size--;
}

11） Element search ：

int SListFind(SList* L,DataType x)
{
	assert(L);
	for (int i = 0; i < L->size; i++)
	{
		if (L->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

12） Data modification ：

void SListModify(SList* L, int pos, DataType x)
{
	assert(L);
	assert(pos >= 0 && pos <= L->size);
	L->arr[pos] = x;
}​

To be continued , Let's see you next time ! ! !

Two 、 Single chain list

3、 ... and 、 Double linked list

---

Summary and experience ：

1） The structure of the sequence table

2） Type of sequence table （ Dynamic and static ）

3） The advantages of a sequence table ： Compared with the linked list, it can achieve random access to any location of nodes

4） Want to learn data structure well C The foundation of language must be solid , Especially the pointer 、 Structure 、 Dynamic memory opens up these three trunks , Otherwise, the data structure will be very difficult to learn

5） Want to learn programming well , Hands on ability must be strong , Quantitative changes pile up dead qualitative changes , Work hard to create miracles , When you find that you have insufficient knowledge of a certain point , That is largely a lack of quantity , So you have to type more code , But tapping code must also be based on understanding , Otherwise, it is useless to knock more , Programming requires understanding the code , Instead of memorizing the code .