当前位置：网站首页>Sequence list and linked list

The sequence table uses a paragraph A storage unit with continuous physical addresses A linear structure that stores data elements in turn , Generally speaking Store... In an array , Add, delete, check and modify in the array . Pictured 1, It has the following characteristics :

Storage Space is continuous , It allows sequential access to elements , Again Random access .
To visit Specify elements , have access to Indexes ( Subscript ) To visit , The time complexity is O(1);
To add or delete an element , It involves the forward or backward movement of all subsequent elements , The time complexity is O(n);
It can conveniently store any node in the table , Fast storage ;
Fixed length , You must know the length of the array before allocating memory ;
There is no need to add additional storage space to represent the logical relationship between nodes , Improved storage utilization ;

Storage structure :

The order table can be divided into :
1. Static sequence table : Use Fixed length array Storage ;
2. Dynamic sequence table : Use Dynamic array Storage ;
What is the difference between static allocation and dynamic allocation ？ In fact, it is the difference between arrays . In static allocation , When we were writing , The size of the array has been determined . Dynamic allocation , Its size is not determined , The size of a dynamic allocation statement is allocated only at run time . One advantage of this is , In static allocation , When I want to store the data elements of the sequence table more than 100 Error overflow will occur when , Dynamic allocation , If the allocated space is exceeded , You can reallocate another piece of memory space , Transfer the old space and the added data elements to the newly applied space , In this way, there will be no overflow problem . This is an advantage of dynamic allocation .

The code is as follows :

// Static storage of sequence table 
#define N 8
typedef int SLDataType;
typedef struct SeqList
{
  SLDataType array[N];// Fixed length array 
  size_t size;// Number of valid arrays 
}SeqList;


// Dynamic storage of sequence table 
typedef int SLDataType;
typedef struct SeqList
{ 
   SLDataType* array;// Point to the dynamic array 
   size_t size;// Number of valid data 
   size_t capacity;// Size of space capacity 
}SeqList;
/* annotation : We found that the pointer is used here , A pointer is used to store the address of a storage unit . The order table is based on the address of the first data element and the size of the data element , You can calculate the position of any data element . That is, just define the pointer of the first element , Describe the entire sequence table . But it's just an address , There is no definite space , So we use it to open up space ;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
 The detailed code is explained below ;*/

A fixed length array of a static order table results in N Dingda , There is not enough space to open , Drive too much, waste , So in reality, dynamic sequence table is used , Use Multiply - Copy To support dynamic capacity expansion , Change the sequence table to “ Variable length ” Of . Next I will implement the dynamic sequence table ;

1.2 Insertion of sequence table ( Head insertion , Tail insertion , Insert the specified location ）

1) The first interpolation : Insert at the front of the sequence table every time , Move other data back

void SeqListPushFront(SL* ps, SLDataType x)
{
	// If there is no space , Or lack of space , We can increase capacity 
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;// Double the capacity of the array , The ternary operator is used to prevent 0 This situation 
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		// Judge whether the capacity increase is successful 
		if(tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
    // Traverse forward from the last element to the first element , Move them back one position respectively 
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;// Insert the data to be inserted into the header 
	ps->size++;// Watch length plus 1
}

2) The tail interpolation : Add data at the end of the sequence table , Other elements need not be changed

void SeqListPushBack(SL* ps, SLDataType x)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->size] = x;
	ps->size++;
}

3) Insert... At specified location : Traverse forward from the last element to the specified position , Move them back one position respectively

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	// Because the sequence table is stored continuously , So first of all, it is necessary to judge whether the insertion position is legal ;
	assert(pos >= 0 && pos <= ps->size);
	// increase capacity 
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	// Traverse forward from the last element to the specified position , Move them back one position respectively 
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
    // take x Insert in the specified location 
	ps->a[pos] = x;
    // Watch length plus 1
	ps->size++;
}

1.3 Deletion of sequence table ( Head deletion , Deletion at the end , Delete the specified location )

1) Head deletion : Traverse from the deletion position to the position of the last element , Move them forward one position in turn ;

void SeqListPopFront(SL* ps)
{
	// Judge whether the current length of the sequence table is 0
	assert(ps->size > 0);  

    // Traverse from the deletion position to the last element position , Move them forward one position respectively .
	for (int i = 1; i < ps->size; i++)
	{
		ps->a[i - 1] = ps->a[i];
	}
     // Watch length minus one 
	ps->size--;
}

2) Deletion at the end : Subtract... From the table length 1 that will do ;

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}

3) Delete the specified location : First, judge whether the specified location is legal, and then move forward one step from the next element of the specified location .

void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos + 1; i < ps->size; i++)
	{
		ps->a[i - 1] = ps->a[i];
	}
	ps->size--;
}

1.4 Look up the sequence table

lookup : Start at one end of the sequence table , Match the keyword of each element with the given value in turn K Compare , Not found until the equality or comparison is completed .

int SeqListFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

1.5 Interface implementation of sequence table ( For everyone to check whether they master ）

You can refer to the interface provided by it to practice and check whether you have mastered .

//  Dynamic storage of sequence table 
typedef struct SeqList
{
 SLDataType* array; //  Point to the dynamic array 
 size_t size ; //  The number of valid data 
 size_t capicity ; //  The size of the capacity space 
}SeqList;
//  Basic addition, deletion, query and modification interface 
//  Sequence table initialization 
void SeqListInit(SeqList* psl, size_t capacity);
//  Destroy the sequence table 
void SeqListDestory(SeqList* psl);
//  Sequence table printing 
void SeqListPrint(SeqList* psl);
//  Check the space , If the full , Increase capacity 
void CheckCapacity(SeqList* psl);
//  End of sequence table 
void SeqListPushBack(SeqList* psl, SLDataType x);
//  Delete the end of the sequence table 
void SeqListPopBack(SeqList* psl);
//  Sequential header interpolation 
void SeqListPushFront(SeqList* psl, SLDataType x);
//  Sequential header delete 
void SeqListPopFront(SeqList* psl);
//  Sequence table lookup 
int SeqListFind(SeqList* psl, SLDataType x); 
//  The sequence table is in pos Position insert x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//  Sequential table deletion pos The value of the location 
void SeqListErase(SeqList* psl, size_t pos);

2. Linked list

2.1 The concept and structure of linked list

Basic concepts :

A list is a kind of The physical storage structure is discontinuous 、 Nonsequential storage structure , Data elements Logical order It is through... In the linked list Pointer link Sequential implementation of . Take the single linked list as an example , Explain its characteristics , Pictured 1

Storage space Discontinuous , Data elements are connected by pointers , Each data element can only access one surrounding element ;
Length is not fixed , It can be added or deleted at will ;
To visit Specify elements , want Traverse the elements from scratch , Until we find the position of that element , The time complexity is O(N);
At the designated Insert or delete data elements , No need to move other elements , The time complexity is O(1);

Chain table structure :

The structure of the linked list is very diverse , Combined with the following situations, there are 8 Middle linked list structure :
1. A one-way 、 two-way 2. Take the lead 、 Don't take the lead 3. loop 、 Acyclic
（ notes :
A one-way : Only contain the pointer to the next node , Only one way traversal ;
two-way : Contains a pointer to the next node and a pointer to the previous node , Therefore, it can traverse in both directions ;
Take the lead :1. The head node is set up for the unity and convenience of operation , Put it before the first element of the linked list , Most of its data fields are meaningless , But it can also be used to save the length of the linked list .2. With the head node , The insertion and deletion of the linked list header are unified .3. The head node is not a necessary element of the linked list .
loop : Link the tail node with the first node , Formed a ring structure , It can be very useful in some cases )
Although there are so many linked list structures , But the two most common structures we see in practice :
Because of the space , Just explain the first Headless unidirectional acyclic list .

2.2 Insertion of single chain table ( Head insertion , Tail insertion , Insert... At specified location ）

1） Tail insertion ( Headless node ):1. Create a new node 2. Judge whether the list is empty 3. If it is empty, let the header pointer point to the new node 4. Otherwise, find the last pointer , Point to the new node ;

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuyListNode(x);// Create a new node 
	if (*pphead == NULL)
	{// Judge whether the list is empty 
		*pphead = newnode;
	}
	else {
		// Find the last node 
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		// Point the last node to the new node 
		tail->next = newnode;
	}
}

2) Head insertion ( Headless node ):1. Create a new node 2. The new node points to the original linked list 3. The header pointer points to the new node ;( notes :2,3 The order cannot be reversed , Otherwise, the new node will not find the address of the original linked list )

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuyListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}

3) stay pos Insert node before position :1. Create a new node ;2. Determine whether the first one is its designated location 3. If it's another head insertion , otherwise , find pos The previous position of posPrev;4 Insert its new node into pos Before the position ,posPrev after ;

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//  stay pos Insert a node before the location 
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	assert(pos);
	SLTNode* newnode = BuyListNode(x);// Create a new node 
    // Judge whether the first one is equal to pos
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else {
        // find pos The previous position of 
		SLTNode* posprev = *pphead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		posprev->next = newnode;
		newnode->next = pos;
	}
}

4) stay pos Insert node after position :1. Create a new node ; 2. New node next Point to pos Of next;3.pos Of next Point to newnode;( notes :2,3 You can't swap places , Otherwise you will lose pos Address after ）

SLTNode* BuyListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos);
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2.3 Deletion of single chain table ( Head deletion , Deletion at the end , Delete... In the specified location )

1) Deletion at the end :1. Judge whether the list is empty , If it is empty, the deletion will stop ;2. If there is only one node , Release its node , Make the linked list empty ;3. If there are two or more nodes , Find the last one and its precursor ;4. Its precursor next It's empty , Release the last node ;

void SListPopBack(SLTNode** pphead)
{
	assert(*pphead != NULL);
	//1. A case of 
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//2. Two or more 
	else {
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

2) Head deletion : 1. Judge whether the list is empty ;2. The header pointer points to the first node next;3. Release the first node ;

void SListPopFront(SLTNode** pphead)
{
	assert(*pphead != NULL);// Judge whether the linked table is empty ·
	SLTNode* cur = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
	*pphead = cur;
}

3) Delete... In the specified location :1. Judge whether the list is empty ;2. If pos Equal to the first node , Use header deletion ;3. find pos Former one prev 4. take prev Of next Point to pos Of next;5. Release pos;

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPopFront(pphead);// Head deletion , See the code above 
    }
	else {
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		} 
		prev->next = pos->next;
		free(pos);
	}
}

2.4 Single chain table search

SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else {
			cur = cur->next;
		}
	}
	return NULL;
}

2.5 Interface implementation of single linked list ( For everyone to check whether they master )

// 1、 Headless + A one-way + Implementation of addition, deletion, query and modification of acyclic linked list 
typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next;
}SListNode;
//  Dynamically apply for a node 
SListNode* BuySListNode(SLTDateType x);
//  Single linked list printing 
void SListPrint(SListNode* plist);
//  Single list tail insert 
void SListPushBack(SListNode** pplist, SLTDateType x);
//  The header of a single linked list 
void SListPushFront(SListNode** pplist, SLTDateType x);
//  Tail deletion of single linked list 
void SListPopBack(SListNode** pplist);
//  Delete the single chain header 
void SListPopFront(SListNode** pplist);
//  Single linked list lookup 
SListNode* SListFind(SListNode* plist, SLTDateType x);
//  Single linked list pos Insert after position x
//  Analyze and think about why not pos Insert before position ？
void SListInsertAfter(SListNode* pos, SLTDateType x);
//  Single linked list deletion pos Value after position 
void SListEraseAfter(SListNode* pos);

3. Advantages and disadvantages of sequential list and linked list

3.1 Access method

The order sheet : It can be accessed sequentially , It can also be accessed randomly ;
Single chain list : Elements can only be accessed from the header sequence ;

3.2 Logical structure and physical structure

The order sheet : Logically adjacent elements , The corresponding physical storage locations are also adjacent ;
Single chain list : Logically adjacent elements , Physical storage locations are not necessarily adjacent , Its logical relationship is represented by pointer Links ;

3.3 Time performance

Sequential tables support random access , The time complexity is O(1);
The insertion and deletion of the sequence table need to move the elements in turn , The time complexity is O(N);
The single linked list needs to access the specified elements , It needs to be traversed from the beginning , The time complexity is O(N);
The insertion and deletion of single linked list do not need to move elements , The time complexity is O(1);

3.4 Space performance

The order sheet : Need to pre allocate storage space , Excessive allocation will cause a waste of storage space , But too little allocation will cause overflow . Dynamic storage allocation, although the storage space can be expanded , But you need to move a lot of elements , Resulting in reduced operating efficiency , And if there is no more continuous storage space in memory , This will lead to allocation failure .

Single chain list : Distribute on demand , And the number of elements is unlimited

The above are the relevant knowledge points of sequence list and linked list , There are deficiencies or better insights into the code , Welcome to comment in the discussion area , Common progress ！！

原网站

版权声明
本文为[skeet follower]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202142009081273.html