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 
        return null;//not found
}

//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(){
    ptr head=(ptr)malloc(sizeof(struct chain_list));
    head->data=-1;
    head->next=null;
    return head;
}

//Find element x
ptr find(ptr head,elementtype x){
    ptr p=head;
    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
    if (t==null&&p!=head)
        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:
    if (p==head){
        ptr new_ptr=(ptr)malloc(sizeof(struct chain_list));
        new_ptr->data=x;
        new_ptr->next=head;
        head=new_ptr;
        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
    if (t==null&&p!=head)
        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:
    if (p==head){
        head=head->next;
        free(p);
        return true;
    }
}

Posted on Fri, 11 Oct 2019 07:29:51 -0700 by kyleldi