# [data structure] (initial stage): linear table

✨ preface ✨

☕ 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!

​​​​​​​

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

Implementation of single linked list interface

Create a new node

Tail insertion node

insert data

Find data

Tail deletion node

# 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 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.

• 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

## 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)
{
{
return;
}
}```

### Tail insertion node

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

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

### insert data

```void SL_Insert(SListNode** pphead, SListNode* loc, SListDataType x)
{
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)
{
while (cur->data != x)
{
cur = cur->next;
}
return cur;
}```

```void SL_PopFront(SListNode** phead)
{
free(temp);
}```

### Tail deletion node

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

```void SL_Destroy(SListNode** pphead)
{