11 operations on linear tables
1. Construct an empty linear table ----- InitList(*L)
2. Assign value to linear table ---------- ValueList(*L)
3. Destroy linear table - destrorylist (* l)
4. Reset linear table - ClearList(*L)
5. Judge whether the linear table is empty ----- ListEmpty(L)
6. Get length of linear table ---------- GetLength(L)
7. Get the element corresponding to a position in the linear table ----- GetElem(L,i,*e)
8. Insert element at a certain position in linear table ------------- ListInsert(*L,i,e)
9. Delete the element at a certain position in the linear table ------------- ListDelete(*L,i,*e)
10. Print linear table ----------------------- PrintList(L)
11. Exit ---------------------------------------- exit(0)
Explain the implementation of linear table with c + +
Before the code, let's review the theoretical knowledge related to linear table. Here I explain it in c + +. Finally, I use c language to realize all the operations related to sequential table. Note that the template in the following is a template function in c + + class library. It can turn a piece of code into a class of template for us to call, which is more convenient
I. definition of linear table
A linear list is a finite sequence of zero or more data elements. It includes a sequential list and a linked list. The addresses of elements in the sequential list (actually an array) are continuous, while the addresses of nodes in the linked list are discontinuous and connected by pointers.
II Sequential storage of linear tables (sequential tables)
The sequence table is generally implemented by an array. In fact, it is to find an initial address in memory, and then occupy a certain continuous memory space by occupying bits, Put the elements of the same data type into this space (memory) in turn. The size of the array can be specified in two ways: one is static allocation and the other is dynamic expansion. The operations related to the sequence table are related to the array, generally moving the array elements.
III Encapsulation of sequence table
The encapsulation of the sequence table requires three attributes:
1. Starting position of storage space. The storage location of array data is the storage location of linear table storage space. Here, it is added that the array name is the first address of the whole array.
2. Maximum storage capacity of linear table - MAXSIZE
3. The current length of the linear table - length (note that this is the current length. The current length is expressed by the number of elements in the array. It needs to be separated from the maximum length MAXSIZE set by us. MAXSIZE is the maximum capacity we set to store the linear table. It generally remains unchanged after initialization. Of course, you can use expansion if necessary)
Next, we use c + + language to realize various functions of linear table
1. To create a linear table with a length of n, you need to transfer the given array element into the linear table as the data element of the linear table, and the number of transferred elements as the length of the linear table.
template <class DataType>{ SeqList<DataType>::SeqList(DataType a[],int n)
if(n>MAXSIZE)throw"wrong parameter"; for(int i=0;i<n;i++) data[i]=a[i]; lengtn=n;
}
2. Search by bit
template<class DataType>
DataType SeqList<DataType>::Get(int i)
{
if(i<1 && i>length)throw"wrong location";
else return data[i-1];
}
3. To find by value, you need to compare it with the elements in the sequence table in turn
template <class DataType> int SeqList<DataType>::locate(DataType x) { for(int i=0;i<length;i++) if(data[i]==x) return i+1;
}
4. Insert, it should be noted here that we need to consider two issues. First, when the insertion position is unreasonable, for example, you only have five positions, and you insert into position 7, it is unreasonable; Second, when the table is full, it will cause overflow. We need to consider these two situations.
template <class DataType> void SeqList<DataType>::Insert(int i,DataType x){ if(length>=MAXSIZE)throw"overflow"; if(i<1 || i>length+1)throw "Location"; for(int j=length;j>=i;j--) data[j]=data[j-1]; data[i-1]=x; length++;
}
5. Delete here, we should also consider two cases. First, the table is empty, and second, the deletion position is unreasonable.
template <class DataType> DataType SeqList<DataType>::Delete(int i)
{
int x; if(length==0)throw"Underflow"; if(i<1 || i>length)throw"Location"; x=data[i-1]; for(int j=i;j<length;j++) data[j-1]=data[j]; length--; return x;
}
6. Traversal
template<class DataType> void SeqList<DataType>::PrintList()
{
for(int i=0;i<length;i++) cout<<data[i]<<endl;
}
After finishing all the code, let's talk about the advantages and disadvantages of sequential storage. In the next issue, we will compare it with the linked list.
Advantages: random access, high storage density; Logically adjacent elements are also physically adjacent; There is no need to add additional storage space for the logical relationship between elements in the table;
Disadvantages: inserting and moving require a large number of elements; "Fragmentation" of storage space;
To sum up, when there are a lot of elements to deal with, it is obvious that we can't use a linear table. In the next issue, I will update the linked list, compare the linear list with the linked list, and reflect it with actual code.
The following is the sequence table implemented in c language:
Use c language code to realize all functions
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
//1. Dynamic allocation storage structure of linear table
#define LIST_INIT_SIZE 100 / / initial capacity of linear table storage space
#define LISTINCREMENT 10 / / space increment of linear table
typedef struct{
ElemType *elem; //Base address of storage space
int length; //Current linear table length
int listsize; //Current linear table capacity
}SqList;
//2. Construct an empty linear table
Status InitList_Sq(SqList &L){
L.elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
if(!L.elem){
printf("Storage space allocation failed");
exit(OVERFLOW);
}
L.length=0;
L.listsize=LIST_INIT_SIZE;
printf("An empty linear table has been built successfully");
return OK;
}
//Assign a value to an empty linear table
Status ValueList_Sq(SqList &L){
int i,j;
printf("Please enter the number of linear tables:");
scanf("%d",&i);
if(i>L.listsize)
{
while(1)
{
if(i>L.listsize) //If the element to be input is larger than the initial capacity, it must be allocated space until it is greater than i
{
L.elem=(ElemType *)realloc(L.elem,sizeof(ElemType)*LISTINCREMENT);
L.listsize+=LISTINCREMENT;
}
else
break;
}
for(j=0;j<i;j++)
{
printf("Please enter page%d Elements:",j+1);
scanf("%d",&L.elem[j]);
}
L.length=i; //After the assignment is completed, modify and save the length of the linear table
printf("Assignment succeeded");
return OK;
}
}
//Destroy linear table
Status DestoryList_Sq(SqList &L){
if(!L.elem)
{
printf("You haven't created a linear table yet. Please create a linear table first\n");
return ERROR;
}
free(L.elem);
L.elem=0;
L.length=0;
L.listsize=0;
printf("Linear table destroyed\n");
return OK;
}
//Reset linear table
Status ClearList_Sq(SqList &L){
if(L.elem)
{
L.length=0;
printf("Linear table reset\n");
return OK;
}
else
{
printf("Linear table does not exist and cannot be reset\n");
return OK;
}
}
//Judge whether the linear table is empty
Status ListEmpty_Sq(SqList &L){
if(L.elem){
if(L.length!=0)
{
printf("Linear table is not empty\n");
return FALSE;
}
else
{
printf("The linear table is empty\n");
return TRUE;
}
}else
{
printf("The linear table does not exist and cannot be judged\n");
return OK;
}
}
//Get the number of linear tables
Status ListLength_Sq(SqList L)
{
if(L.elem)
{
int k;
k=L.length;
printf("Linear table length is%d\n",k);
return OK;
}else{
printf("The linear table does not exist and cannot be judged\n");
return OK;
}
}
//Gets an element at a location in a linear table
Status GetElem_Sq(SqList L,int index){
int Num;
if(index<=0 || index>L.length)
{
printf("Please enter a valid number\n");
return ERROR;
}else{
Num=L.elem[index-1];
printf("The first%d The element of the location is:%d\n",index,Num);
return OK;
}
}
//Inserts an element at a location in the linear table
Status ListInsert_Sq(SqList &L,int i,ElemType e){
ElemType *newbase;
int *q,*p;
if(i<1 || i>L.length+1) //Determine whether the insertion position is legal
return ERROR;
if(L.length>=L.listsize){
newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
L.elem=newbase; //New spatial base address
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
printf("Element inserted successfully\n");
return OK;
}
//Delete an element at a location in the table
Status DeleteList_Sq(SqList &L,int i)
{
int *q,*p;
if(i<1 || i>L.length)
{
printf("Please enter a valid number:\n");
return ERROR;
}
p=&(L.elem[i-1]); //p is the position of the deleted element
q=L.elem+L.length-1;
for(++p;p<=q;p++)
*(p-1)=*p;
--L.length;
printf("The first%d Elements deleted successfully\n");
return OK;
}
//Print linear table
Status PrintList_Sq(SqList L)
{
printf("The elements of the current linear table are:");
for(int k=0;k<L.length;k++)
{
printf(" %d",L.elem[k]);
printf("\n");
}
return OK;
}
int main()
{
SetConsoleTitle("Dream_Soar");
SqList L;
int choose,index,e;
while(1)
{
printf("*********************************************\n");
printf("* Representation and implementation of sequence table *\n");
printf("* 1.Construct an empty linear table *\n");
printf("* 2.Assign values to linear tables *\n");
printf("* 3.Destroy linear table *\n");
printf("* 4.Reset linear table *\n");
printf("* 5.Judge whether the linear table is empty *\n");
printf("* 6.Gets the length of the linear table *\n");
printf("* 7.Gets the element corresponding to a position in the linear table *\n");
printf("* 8.Inserts an element at a location in the linear table *\n");
printf("* 9.Delete an element at a certain position in a linear table *\n");
printf("* 10.Print linear table *\n");
printf("* 11.sign out *\n");
printf("*********************************************\n");
printf("Please make your choice:");
scanf("%d",&choose);
switch(choose){
case 1:InitList_Sq(L);break;
case 2:ValueList_Sq(L);break;
case 3:DestoryList_Sq(L);break;
case 4:ClearList_Sq(L);break;
case 5:ListEmpty_Sq(L);break;
case 6:ListLength_Sq(L);break;
case 7:{
printf("Please enter the location to get the element:");
scanf("%d",&index);
GetElem_Sq(L,index);
}
break;
case 8:{
printf("Please enter the location of the element to insert:");
scanf("%d",&index);
printf("Please enter the value of the element to insert:");
scanf("%d",&e);
ListInsert_Sq(L,index,e);
}
break;
case 9:{
printf("Please enter the location of the element to delete:");
scanf("%d",&index);
DeleteList_Sq(L,index);
}
break;
case 10:PrintList_Sq(L);break;
case 11:exit(0);
}
}
return 0;
}