1. Definition of linear table
Linear List (List): A finite sequence of zero or more data elements.
The data set of the linear table is {a1,a2,...,an}, assuming that the type of each element is DataType. Among them, except the first element a1, each element has one and only one direct predecessor element, and except the last element an, each element has one and only one direct successor element. The relationship between data elements is a one-to-one relationship.
In a more complex linear table, a data element can consist of several data items. In this case, the data elements are often called records, and the linear table containing a large number of records is also called a file.
2. Sequence table
Sequential storage structure of linear table
1. Concept
A group of storage units with continuous addresses are used to store the data elements of the linear table sequentially. The linear table of this storage structure is called a sequential table.
2. Features
Logically adjacent data elements are also adjacent in physical order.
As long as the starting position for storing the linear table is determined, any data element in the linear table can be accessed randomly, so the sequential storage structure of the linear table is a random access storage structure, because the array type in the high-level language is also It has the characteristics of random access, so we usually use arrays to describe the sequential storage structure in the data structure, and use dynamically allocated one-dimensional arrays to represent linear tables.
3. Code
1: .h
#pragma once
//Prevent header files from being re-referenced
//Definition and Declaration
//fixed length list
typedef struct SQList
{
int elem[10];//Store data, fixed length is 10
int length;//The number of valid data
}SQList,*PSQList;
//initialization
void InitSqlist(PSQList ps);
//Insert data, insert val at the pos position of the ps sequence table
bool Insert(PSQList ps, int pos, int val);
//Empty
bool IsEmpty(PSQList ps);
//Find the first val in ps. Return subscript if found, return -1 if not found
int Search(PSQList ps, int key);
//Delete the value of pos position
bool DelPos(PSQList ps, int pos);
//delete the value of the first val
bool DelVal(PSQList ps, int val);
//Returns the predecessor subscript of the key, or -1 if it does not exist
int GetPrio(PSQList ps, int key);
//Returns the subsequent subscript of the key, or -1 if it does not exist
int GetNext(PSQList ps, int key);
//output
void Show(PSQList ps);
//clear data
void Clear(PSQList ps);
//destroy the entire memory
void Destroy(PSQList ps);
2: .cpp
1. Header file
#include<stdio.h> #include<assert.h> #include"sqlist.h"
2. Initialization, in order for the program to run correctly
void InitSQList(PSQList ps)
{
assert(ps != NULL);
if (ps == NULL)
{
return;
}
ps->length = 0;
}
static bool IsFull(PSQList ps)
{
return ps->length == 10;
}3. Insert data, insert val at the pos position of the ps sequence table
bool Insert(PSQList ps, int pos, int val)
{
//Empty
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
//Judging whether the table is full
if(pos<0||IsFull(ps)||pos> ps->length)
{
return false;
}
//After moving the data to
for(int i=ps->length-1;i>=pos;i--)
{
ps->elem[i+1] = ps->elem[i];
}
//insert data
ps->elem[pos] = val;
//valid data++
ps->length++;
}4. Short judgment
bool IsEmpty(PSQList ps)
{
return ps->length == 0;
}5. Search, return subscript if found, return -1 if not found
int Search(PSQList ps, int key)
{
//Empty
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
for (int i = 0; i < ps->length; i++)
{
if (ps->elem[i] == key)
{
return i;
}
}
return -1;
}6. Delete the value of pos position
bool Delpos(PSQList ps, int pos)
{
//Empty
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
if (pos < 0 || pos >= ps->length)
{
return false;
}
for (int i = pos; i < ps->length-1; i++)
{
ps->elem[i] = ps->elem[i + 1];
}
ps->length--;
}7. Delete the value of the first val
bool Delval(PSQList ps, int val)
{
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
int i = Search(ps, val);
if (i < 0)
{
return false;
}
return Delpos(ps, i);
}8. Return the predecessor subscript of the key, if it does not exist, return -1
int GetPrio(PSQList ps, int key)
{
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
int i = Search(ps, key);
if (i <= 0)//headless
return false;
else
return i-1;
}9. Return the subsequent subscript of the key, or -1 if it does not exist
int GetNext(PSQList ps, int key)
{
assert(ps != NULL);
if (ps == NULL)
{
return false;
}
int i = Search(ps, key);
if (i < 0||i==ps->length-1)//no successor
return false;
else
return i+1;
}
10. Output
void Show(PSQList ps)
{
//Empty
assert(ps != NULL);
if (ps == NULL)
{
return ;
}
for (int i = 0; i < ps->length; i++)
{
printf("%d ", ps->elem[i]);
}
printf("\n");
}11. Clear data
void Clear(PSQList ps)
{
ps->length = 0;
}12. Destroy
void Destroy(PSQList ps)
{
Clear(ps);
}3. .test
#include <stdio.h>
#include "sqlist.h"
int main()
{
SQList sq;
printf("%d\n", sizeof(sq));
InitSQList(&sq);
for (int i = -1; i < 20; i++)
{
Insert(&sq, i, i);
}
Show(&sq);
int i = Search(&sq, 2);
if (i >= 0)
{
printf("The value is located in%d subscript\n", i);
}
else
{
printf("could not find it\n");
}
int index;
for (int i = -1; i < 11; i++)
{
index = Search(&sq, i);
if (index >= 0)
{
printf("%d lie in%d subscript\n", i, index);
}
else
{
printf("could not find it%d\n",i);
}
}
Delpos(&sq, 5);
Show(&sq);
Delval(&sq, 0);
Show(&sq);
return 0;
}v
4. Test results
44
0 1 2 3 4 5 6 7 8 9 Insert data, only save 10 (table size is 10)
The value is located at subscript No. 2 Find the subscript with val=2
Not found -1 Cannot find -1
0 is located at subscript 0
1 is in subscript number 1
2 is located at subscript number 2
3 is in subscript number 3
4 is in the subscript number 4
5 is located in the subscript number 5
6 is in the subscript number 6
7 is located at subscript number 7
8 is located in the subscript number 8
9 is in the subscript number 9
Not found 10 Query less than 10
0 1 2 3 4 6 7 8 9 delete 5
1 2 3 4 6 7 8 9 delete 0
