Data structure--order table of linear table

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

 

Tags: C++ data structure

Posted by TLawrence on Mon, 21 Nov 2022 02:28:59 +1030