This is the first day of my participation in the August Text Challenge.More challenges in August

Basic concepts and terminology

  • Data: A symbolic representation of an objective thing, a general term for all symbols that can be entered into a computer and processed by a computer program. For example: integer, real number, string, graph, image, sound and other data after special coding.
  • Data element: Basic unit of data, usually considered and processed as a unit in a computer. (Data elements are also called elements, records, etc.). Data elements are used to completely describe an object, such as a student record, a pattern of a chessboard in a tree, a vertex in a graph, etc.
  • Data item: The smallest, indivisible unit that makes up a data element and has its own meaning. For example: student id, name, gender, etc.
  • Data object: A collection of data elements of the same nature, a subset of data. (As long as the elements in the set have the same properties, they can be called a data object.)
  • Data structure: A collection of data elements that have one or more specific relationships with each other. In other words, a data structure is a collection of data elements with a “structure”, which is the relationship that exists between data elements.
    • Logical structure: A mathematical model abstracted from a specific problem that describes data logically, independent of its storage.
      • Nonlinear structure: a hierarchy with multiple branches
        • Collection structure: There is no relationship between data elements other than “belonging to the same collection”.
        • Tree structure: There is a one-to-many relationship between data elements.
          • The tree
          • Binary tree
        • Graph structure: A many-to-many relationship exists between data elements.
          • Directed graph (edges are ordered pairs of vertices)
          • Undirected graph (edges are unordered pairs of vertices)
      • Linear structure: There is a one-to-one relationship between data elements.
        • The linear table
          • General linear list
            • The linear table
          • Special linear list
            • The stack and queue
            • string
          • Generalization of linear tables
            • An array of
            • Generalized table
    • Storage structure (physical structure) : The storage representation of logical structures in a computer
      • Sequential storage structure: Contiguous storage space
      • Chain storage structure: no need to occupy a whole block of storage space
  • Abstract data type: A user – defined data model that represents an application problem and a general term for the operations defined on the model.
    • The data object
    • A collection of relationships on a data object
    • A collection of basic operations on data objects

The order sheet

Sequential storage definition

  • A storage structure that stores logically adjacent data elements in physically adjacent storage cells.
  • In short, logically adjacent, physically adjacent

Sequential storage method

  • The array V[n] is used to store the elements of a linear table in sequence with a set of contiguous storage cells.

Characteristics of sequential tables

  • The storage location of data elements is used to represent the relationship between adjacent data elements in a linear table, that is, the logical structure of a linear table is consistent with the storage structure
  • When accessing a linear table, you can quickly calculate the storage address of any data element. So you can roughly assume that each element takes the same amount of time to access

Advantages and disadvantages of sequential tables

  • advantages
    • High storage density (storage occupied by node itself/storage occupied by node structure)
    • You can randomly access any element in the table
  • disadvantages
    • When inserting or deleting an element, a large number of elements need to be moved
    • Waste storage space
    • It is static storage and the number of data elements cannot be expanded freely

C++ code implementation

#include<stdlib.h>
#include<iostream>
using namespace std;

#define MAXSIZE 100
#define OVERFLOW -2
#define ERROR -1
#define OK 1

typedef int Status;
typedef int ElemType;  / / non integer

// Node structure
typedef struct {
	ElemType* elem;
	int length;
	// int listsize;
}Sqlist;

// Initialize the sequence table
Status InitList_Sq(Sqlist& L)
{
	L.elem = new ElemType[MAXSIZE];
	if(! L.elem)exit(OVERFLOW);
	L.length = 0;
	return OK;
}

// Destroy the sequence table
void DestroyList(Sqlist& L)
{
	if(! L.elem)delete[] L.elem;
}

// Clear the order table
void ClearList(Sqlist& L)
{
	L.length = 0;
}

// Get the length of the order table
int GetLength(Sqlist L)
{
	return L.length;
}

// Check whether the sequence table is empty
int IsEmpty(Sqlist L)
{
	if(! L.elem)return 1;
	else
		return 0;
}

/*Status insert(Sqlist& L, int i, ElemType e) { int j; if (i < 1 || i > L.length + 1) return ERROR; if (L.length == MAXSIZE) return OVERFLOW; for (j = L.length - 1; j >= i - 1; j--) L.elem[j + 1] = L.elem[j]; L.elem[i - 1] = e; L.length++; return OK; } * /

// Insert elements at I
Status ListInsert_Sq(Sqlist& L, int i, ElemType e)
{
	// Insert a new element e before the ith element of sequence table L
	if (i < 1 || i > L.length + 1)
		return ERROR;
	if (L.length == MAXSIZE)
		return OVERFLOW;
	ElemType* p, * q;
	q = &(L.elem[i - 1]);
	for (p = &(L.elem[L.length - 1]); p >= q; p--)
		* (p + 1) = *p;
	*q = e;
	L.length++;
	return OK;
}


/*Status insert(Sqlist& L, int i, ElemType e) { if (i < 1 || i > L.length + 1) return ERROR; if (L.length == MAXSIZE) return OVERFLOW; int* p, * q; q = L.elem + i - 1; for (p = L.elem + L.length - 1; p >= q; p--) * (p + 1) = *p; *q = e; L.length++; return OK; } * /

// Get the value of the element at I and store it in e
Status GetElem(Sqlist L, int i, ElemType& e)
{
	if (i < 1 || i > L.length) return ERROR;
	e = L.elem[i - 1];
	return OK;
}

// Find the element with value e in the order table and return its position
int Search(Sqlist L, ElemType e) // Multiple search methods
{
	int i;
	for (i = 0; L.elem[i] ! = e && i < L.length; i++);if (i < L.length) return i + 1;
	else return 0;
}

/*int LocateElem(Sqlist L, ElemType e) {for(I = 0; /*int LocateElem(Sqlist L, ElemType e) { i < L.length; i ++) if(L.elem[i] == e) return i + 1; return 0; } * /

// Remove the element at position I in the order table and store its value in e
Status ListDelete(Sqlist &L, int i, ElemType& e) 
{
	if (i < 1 || i > L.length) return ERROR;
	e = L.elem[i - 1];
	int j;
	for (j = i; j < L.length; j++)
		L.elem[j - 1] = L.elem[j];
	L.length--;
	return OK;
}

// Create the order table
Status Create(Sqlist& L, int n)
{
	int i;
	if (n < 0) return ERROR;
	for (i = 0; i < n; i++)
		cin >> L.elem[i];
	L.length = n;
	return OK;
}

// Outputs the sequence table
void OutPut(Sqlist L)
{
	int i;
	for (i = 0; i < L.length; i++)
		cout << L.elem[i] << "";
	cout << endl;
}

int main(a)
{
	// The following is the test code
	Sqlist L;
	int n, i, e;
	cout << "Please enter the length of the order table:";
	cin >> n;
	InitList_Sq(L);
	cout << "Please enter data:";
	Create(L, n);
	cout << "Output data:";
	OutPut(L);
	cout << "The length of the order table is:" << GetLength(L) << endl;  // Get the order table length
	cout << IsEmpty(L) << endl;  // Check whether the sequence table is empty
	cout << "Please enter the value you are looking for:";
	cin >> e;
	cout << e << "The location is:" << Search(L, e) << endl;  / / to find
	cout << "Please enter the location of the deleted value:";
	cin >> i;
	ListDelete(L, i, e);
	cout << "Deleted successfully! " << "The value you deleted is:" << e << endl;
	cout << "The order is:";
	OutPut(L);
	cout << "Please enter the location you inserted:";
	cin >> i;
	cout << "Please enter the value you want to insert:";
	cin >> e;
	cout << ListInsert_Sq(L, i, e) << endl;
	cout << "The order is:";
	OutPut(L);
	cout << "The length of the order table is:" << GetLength(L) << endl;
	ClearList(L);
	cout << "The length of the order table is:" << GetLength(L) << endl;
	DestroyList(L);
	return 0;
}
Copy the code
Please input the length of the sequence table: 5 Please input data: 1 2 3 4 5 Output data: 1 2 3 4 5 The length of the sequence table is: 5 0 Please enter the value to be searched: 2 2 Please enter the location of the deleted value: 3 Delete successfully! The values you deleted are as follows: 3 The sequence table is as follows: 1 2 4 5 The value you want to insert: 6 1 The sequence table is as follows: 1 2 6 4 5 The length of the sequence table is as follows: 5 The length of the sequence table is as follows: 0 Press any key to continue..Copy the code