[data structure] (initial stage): linear table

 

✨ preface ✨

🎓 Author: [leader]

☕ The level of bloggers is limited. If there is any error, please correct it.

📌 Opportunities are always reserved for those who are prepared. The harder you work, the luckier you are!

💦 Navigation assistant 💦

​​​​​​​

catalogue

Linear table

Sequence table

Concept and structure of sequence table

Implementation of sequence table interface

initialization

Check capacity

Data insertion

Data deletion

Data search

Data modification

Data printing

Destruction sequence table

Linked list

Linked list classification:

Implementation of single linked list interface

Create a new node

Head inserting node

Tail insertion node

Linked list printing

insert data

Find data

Header deletion point

Tail deletion node

Destroy linked list

Linear table

A linear table is a finite sequence of n data elements with the same characteristics. Linear table is a data structure widely used in practice. Common linear tables: sequential table, linked list, stack, queue, string

In logic, a linear table is a linear structure, that is, a continuous line, but it is not necessarily continuous in physical structure. When a linear table is stored physically, it is usually stored in the form of array and chain structure.

Sequence table

Concept and structure of sequence table

Sequence table is a linear structure in which data elements are stored in sequence with a storage unit with continuous physical addresses. Generally, array storage is used to complete addition, deletion, modification and query on the array.

The sequence table is generally divided into two types:

  • Static sequence table
  • Dynamic sequence table

A static sequential table uses a fixed length array to store elements.

Dynamic order table is stored in dynamic array.

Implementation of sequence table interface

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType *p;//Point to dynamic array
	int size;//Number of valid data
	int capacity;//Capacity space size
}SL;

initialization

void SL_Init(SL* ps)
{
	assert(ps);
	ps->size = 0;
	ps->capacity = 0;
	ps->p = NULL;
}

Check capacity

void SL_CheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		int newCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);
		SLDataType* temp = (SLDataType*)realloc(ps->p, sizeof(SLDataType) * newCapacity);
		if (NULL == temp)
		{
			printf("realloc failed\n");
			return;
		}
		ps->p = temp;
		ps->capacity = newCapacity;
	}
}

Data insertion

void SL_Insert(SL* ps, int loc, SLDataType x)
{
	assert(ps);
	assert(loc >= 0 && loc <= ps->size);

	SL_CheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= loc)
	{
		ps->p[end + 1] = ps->p[end];
		end--;
	}
	ps->p[loc] = x;
	ps->size++;
}

Data deletion

void SL_Erase(SL* ps,int loc)
{
	assert(ps);
	assert(loc >= 0 && loc < ps->size);

	int begin = loc;
	while (begin < ps->size - 1)
	{
		ps->p[begin] = ps->p[begin + 1];
		begin++;
	}
	ps->size--;
}

Data search

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

Data modification

void SL_Modify(SL* ps, int loc, SLDataType x)
{
	assert(ps);
	assert(loc >= 0 && loc < ps->size);

	ps->p[loc] = x;
}

Data printing

void SL_Print(const SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->p[i]);
	}
	printf("\n");
}

Destruction sequence table

void SL_Destroy(SL* ps)
{
	assert(ps);
	if (ps->p != NULL)
	{
		free(ps->p);
		ps->p = NULL;
	}
}

Linked list

Linked list is a non continuous and non sequential storage structure in physical storage. The logical order of data elements is realized through the pointer link order in the linked list.

Linked list classification:

  • One way or two-way
  • Take the lead or not
  • Cyclic or acyclic

Although there are many classifications, there are two most commonly used structures:

  • One way acyclic linked list
  • Lead two-way circular linked list

Implementation of single linked list interface

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

typedef int SListDataType;
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;
}SListNode;

Create a new node

SListNode* BuySListNode(SListDataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	assert(newNode);
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

Node plug

void SL_PushFront(SListNode** phead,const SListDataType x)
{
	SListNode* newNode = BuySListNode(x);
	if (*phead == NULL)
	{
		*phead = newNode;
		return;
	}
	newNode->next = *phead;
	*phead = newNode;
}

Tail insertion node

void SL_PushBack(SListNode** phead,const SListDataType x)
{
	SListNode* newNode = BuySListNode(x);
	if (*phead == NULL)
	{
		*phead = newNode;
		return;
	}
	SListNode* cur = *phead;
	while (cur->next != NULL)
	{
		cur = cur->next;
	}
	cur->next = newNode;
}

Linked list printing

void SL_Show(const SListNode** phead)
{
	assert(phead);
	SListNode* cur = *phead;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

insert data

void SL_Insert(SListNode** pphead, SListNode* loc, SListDataType x)
{
	assert(pphead && loc);
	SListNode* newNode = BuySListNode(x);
	SListNode* cur = *pphead;
	while (cur != loc)
	{
		assert(cur);
		cur = cur->next;
	}
	newNode->next = cur->next;
	cur->next = newNode;
}

Find data

SListNode* SL_Find(const SListNode** phead, SListDataType x)
{
	SListNode* cur = *phead;
	while (cur->data != x)
	{
		cur = cur->next;
	}
	return cur;
}

Header deletion point

void SL_PopFront(SListNode** phead)
{
	assert(phead);
	SListNode* temp = *phead;
	*phead = (*phead)->next;
	free(temp);
}

Tail deletion node

void SL_PopBack(SListNode** phead)
{
	SListNode* cur = *phead;
	while ((cur->next)->next != NULL)
	{
		cur = cur->next;
	}
	free(cur->next);
	cur->next = NULL;
}

Destroy linked list

void SL_Destroy(SListNode** pphead)
{
	SListNode* cur = *pphead;
	assert(pphead);
	while ((*pphead)->next != NULL)
	{
		cur = *pphead;
		*pphead = (*pphead)->next;
		free(cur);
	}
	free(*pphead);
}

Welcome to pay attention. The code is not easy. I hope you can praise and collect more! Fist.

Tags: C data structure

Posted by new2phpcode on Sun, 01 May 2022 20:10:01 +0300