Realization of Linear Tables

1. Sequence table:

It consists of only one structure, and is defined and implemented as follows:

struct order_list {
elementtype data[maxsize];//Define an array, long enough
int last;//Location of the last element
}
typedef struct order_list* list;//Pointer to the structure

//Initialization
list initial(){
list L=(list)malloc(sizeof(struct order_list));
L->last=-1;//Express empty
return L;
}

//Find the subscript of element x
int find(list L,elementtype x){
list p=L;
int position=0;
while(p->last>=position && p->data[position]!=x)
position++;
if (p->data[position]==x)
return position;//Find, return coordinates
else
}

//Insert element x before position p
bool insert(list L,elementtype x,int p){
if (L->last+1==maxsize)
return false;//No place to insert

if (p<0 || p>L->last+1)
return false；//Illegal coordinates

for (int i=L->last;i>=p;i--)
L->data[i+1]=L->data[i];//Start with coordinates p to the last element and move one bit back.
L->data[p]=x;//Insert x
L->last++;
return true;//Insert success
}

//Delete the element x at coordinate p
bool delete(list L,int p){
if (p<0 || p>L->last)
return false；//Illegal coordinates

for (int i=p;i<L->last;i++)
L->data[i]=L->data[i+1];//Move forward one bit from coordinate p+1 to last
L->last--;
return true;
}

To sum up, we can see:

1. Sequence table is fixed length, once defined, the length can not be changed;
2. When deleting or inserting, it needs a lot of shifting work, which is inefficient.

2. Chain list:

1. The time complexity of finding element x is the same as that of sequential table - O(N)O(N)O(N).

2. When deleting and inserting, the efficiency is high, the time complexity is O(1)O(1)O(1) O (1), and the sequence table is O (N) O (N).

However, in the following operations, it is necessary to determine where to delete and insert, so it is O(N)O(N)O(N);

Chain list is composed of an unlimited number of structures and a head pointer, so its length is variable and unrestricted. Its definition and implementation are as follows:

typedef struct chain_list* ptr;
struct chain_list{
elementtype data;
ptr next;
}

//Initialization
ptr initial(){
}

//Find element x
ptr find(ptr head,elementtype x){
while(p!=null && p->data!=x)
p=p->next;
return p;//When not found, p==null, returns null; if found, returns position ptr p.
}

//Insert element x before position p
bool insert(ptr head,ptr p,elementtype x){
for (ptr t=head; t!=null&&t->next!=p; t=t->next) ;//Judging whether p exists
return false;//p is not in this table
else{//Eureka
ptr new_ptr=(ptr)malloc(sizeof(struct chain_list));
new_ptr->data=x;
new_ptr->next=p;
t->next=new_ptr;
return true;
}
//The above can not be added before the first node, so add the following judgment:
ptr new_ptr=(ptr)malloc(sizeof(struct chain_list));
new_ptr->data=x;
return true;
}
}

//Delete the node at p
bool delete(ptr head,ptr p){
for (ptr t=head; t!=null&&t->next!=p; t=t->next) ;//Judging whether p exists
return false;//p is not in this table
else{//Eureka
t->next=p->next;
free(p);
return true;
}
//The first node cannot be deleted above, so the following judgment is added: