Some concepts and definitions
1. Linear table, what is a linear table?
We went to buy milk tea and there was a long line. This is the linear table.
We call the roll in class and the names in the list from top to bottom. This is also a linear table.
2. What is the concept of linear table?
A finite sequence of zero or more data elements.
3. It should be noted that:
1> . is a sequence
2> The first element has no predecessor, the last element has no successor, and the rest have predecessor and successor
3> 3. Limitation
4> Note that zero elements are also linear tables
4. Abstract data type
Concept: a set of mathematical models and a set of operations defined on them
Pseudo code format of the specified abstract data type:
ADT Abstract data type name Data Definition of logical relationship between data elements Operation operation endADT
Sequential storage structure of linear table
# include<stdio.h> # define OK 1 # define ERROR 0 # define TRUE 1 # define FALESE 0 // Status is the type of function, and its value is the status code of the function result, such as OK typedef int status;
Code implementation:
// Sequential storage structure code of linear table
const int Maxsize = 20;
typedef int Elemtype;
typedef struct
{
Elemtype data[Maxsize];
int length; // Current length of linear table
}Sqlist;
getelem
// getelem function
/*
list The value of the ith element in is returned as e
*/
status Getelem(Sqlist list,int i,Elemtype *e)
{
if(list.length == 0 || list.length < i)
{
return ERROR;
}
*e = list.data[i - 1];
return *e;
}
listinsert
Algorithm idea:
1. Whether the insertion position is reasonable, continue if it is reasonable, and return an error if it is unreasonable
2. The table moves backward one bit from back to front to the position to be inserted (including the insertion position)
3. Add one to the length of the table
// listinsert function
/*
list Insert the new element e at the ith position in the
*/
status Listinsert(Sqlist *list,int i,Elemtype e)
{
int k ;
if (list->length == Maxsize)
{
return ERROR;
}
if ( i < 0 || i > list->length + 1)
{
return ERROR;
}
if ( i <= list->length)
{
for ( int k = list->length - 1; k >= i - 1; k --)
{
list->data[ k + 1 ] = list->data[k];
}
}
list->data[i - 1] = e; // Insert the new element. Note that the data subscript here is i - 1!
list->length ++ ; // Don't forget this step!
return OK;
}
listdelete
Only one is deleted by location
Idea:
1. Enter the deletion location. If the location is unreasonable, an error will be returned
2. Return the elements of the deleted position to the output, and move all the elements of the subsequent position forward by one bit
3. Subtract one from the length of the watch
//Listdelete
status Listdelete (Sqlist *list,int i,Elemtype e)
{
if(list->length == 0) // When writing for the first time, the table is empty is not considered
{
return ERROR;
}
else if (i <= 0 || i > list->length) // Note that these two conditions can be combined
{
return ERROR;
}
e = list->data[i - 1];
printf("Deleted e!\n");
for(int k = i - 1; k <= list->length - 1; k ++)
{
list->data[k] = list->data[k + 1];
}
list->length --;
return OK;
}
After reading the insert and delete operations, we can find that the time complexity of the two operations is O(n), but the actual complexity is O(1) when reading or saving.
It can be seen that the sequential storage structure of linear table has the following advantages:
Quickly read the stored element.
Disadvantages:
The space size cannot be determined. The space size cannot meet the demand, or is wasted or insufficient (the demand may always increase, so the length of the array may always be insufficient)
Inserting and deleting takes time
# include<stdio.h>
# include<stdlib.h>
# define OK 1
# define ERROR 0
# define TRUE 1
# define FALESE 0
// Status is the type of function, and its value is the status code of the function result, such as OK
typedef int status;
// Sequential storage structure code of linear table
const int Maxsize = 20;
typedef int Elemtype;
typedef struct
{
Elemtype data[Maxsize];
int length; // Current length of linear table
}Sqlist;
// getelem function
/*
list The value of the ith element in is returned as e
*/
status Getelem(Sqlist list,int i,Elemtype *e)
{
if(list.length == 0 || list.length < i)
{
return ERROR;
}
*e = list.data[i - 1];
return *e;
}
// listinsert function
/*
list Insert the new element e at the ith position in the
*/
status Listinsert(Sqlist *list,int i,Elemtype e)
{
int k ;
if (list->length == Maxsize)
{
return ERROR;
}
if ( i < 0 || i > list->length + 1)
{
return ERROR;
}
if ( i <= list->length)
{
for ( int k = list->length - 1; k >= i - 1; k --)
{
list->data[ k + 1 ] = list->data[k];
}
}
list->data[i - 1] = e; // Insert the new element. Note that the data subscript here is i - 1!
list->length ++ ; // Don't forget this step!
return OK;
}
//Listdelete
status Listdelete (Sqlist *list,int i,Elemtype e)
{
if(list->length == 0) // When writing for the first time, the table is empty is not considered
{
return ERROR;
}
else if (i <= 0 || i > list->length) // Note that these two conditions can be combined
{
return ERROR;
}
e = list->data[i - 1];
printf("Deleted e!\n");
for(int k = i - 1; k <= list->length - 1; k ++)
{
list->data[k] = list->data[k + 1];
}
list->length --;
return OK;
}
// listprint function
status Listprint(Sqlist *list)
{
printf("list: ");
for(int i = 0; i < list->length; i ++)
{
printf("%d ",list->data[i]);
}
printf("\n");
return OK;
}
int main()
{
printf("hello world!\n");
printf("------------------------------------------------------\n");
printf("|Select menu:\n");
printf("|1.Insert number\n");
printf("|2.Delete by location\n");
printf("------------------------------------------------------\n");
printf("Please enter a number:\n");
//Initialize a list
Sqlist list ;
list.length = 0;
//Input operation
while(1)
{
int option;
scanf("%d",&option);
system("cls");
if(option == 1)
{
//Enter 1 listinsert
//Insert element
int cnt;
printf("Please enter how many elements will be inserted:\n");
scanf("%d",&cnt);
for(int i = 1; i <= cnt ; i ++)
{
int e;
printf("Please enter the number to insert:\n");
scanf("%d",&e);
// printf("i = %d ,e = %d\n",i,e);
Listinsert(&list,i,e);
Listprint(&list);
}
}
else if (option == 2)
{
// Enter 2 listdelete
system("cls");
printf("Please enter to delete list The number in the\n");
int deln;
scanf("%d",&deln);
int e = 0;
Listdelete(&list,deln,e);
Listprint(&list);
}
}
system("pause");
return 0;
}