C language linear table of the sequential representation and implementation of examples

1. An overview of the

In general, a sequential table is a linear table stored as an array in the memory of a computer. A linear table is called a sequential table if it is stored sequentially. A sequence table stores the nodes in sequence in a contiguous set of locations in the computer's memory.

The storage structure that stores the elements of a table, one by one, into a continuous set of storage units is the sequential structure.

A linear table with a sequential storage structure is called a "sequential table" for short. The storage characteristics of the sequence table are as follows: as long as the starting position is determined, the address of any element in the table can be obtained by the following formula: LOC (ai) =LOC (a1) + (I -1) *L 1 Or less I Or less n where L is the length of the storage unit occupied by the element. For example, each node in the sequence table occupies len memory cells, and location (ki) is used to represent the address of the first cell in the memory space occupied by the ith node ki in the sequence table. Then there is the following relationship :location (ki+1) = location (ki) +len

Location (ki) = location(k1) + (I -1)len

The storage structure should reflect the logical structure of the data. In the storage structure of the sequential table, the nodes adjacent to the physical address in memory must have the logical relationship in the sequential table.

2. Basic operation

 
 #define LIST_INIT_SIZE 10 
 #define LISTINCREMENT 2 
 typedef struct
 {
  ElemType *elem; 
  int length; 
  int listsize; 
 }SqList;

 Status InitList(SqList *L) 
 { 
  (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  if(!(*L).elem)
   exit(OVERFLOW); 
  (*L).length=0; 
  (*L).listsize=LIST_INIT_SIZE; 
  return OK;
 }
 Status DestroyList(SqList *L)
 { 
  free((*L).elem);
  (*L).elem=NULL;
  (*L).length=0;
  (*L).listsize=0;
  return OK;
 }
 Status ClearList(SqList *L)
 { 
  (*L).length=0;
  return OK;
 }
 Status ListEmpty(SqList L)
 { 
  if(L.length==0)
   return TRUE;
  else
   return FALSE;
 }
 int ListLength(SqList L)
 { 
  return L.length;
 }
 Status GetElem(SqList L,int i,ElemType *e)
 { 
  
  if(i<1||i>L.length)
   exit(ERROR);
  *e=*(L.elem+i-1);
  return OK;
 }
 int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
 { 
  
  
  ElemType *p;
  int i=1; 
  p=L.elem; 
  while(i<=L.length && !compare(*p++,e))
   ++i;
  if(i<=L.length)
   return i;
  else
   return 0;
 }
 Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)
 { 
  
  
  int i=2;
  ElemType *p=L.elem+1;
  while(i<=L.length && *p!=cur_e)
  {
   p++;
   i++;
  }
  if(i>L.length)
   return INFEASIBLE;
  else
  {
   *pre_e=*--p;
   return OK;
  }
 }
 Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
 { 
  
  
  int i=1;
  ElemType *p=L.elem;
  while(i<L.length && *p!=cur_e)
  {
   i++;
   p++;
  }
  if(i==L.length)
   return INFEASIBLE;
  else
  {
   *next_e=*++p;
   return OK;
  }
 }
 Status ListInsert(SqList *L,int i,ElemType e) 
 { 
  
  ElemType *newbase,*q,*p;
  if(i<1||i>(*L).length+1) 
   return ERROR;
  if((*L).length>=(*L).listsize) 
  {
   newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
   if(!newbase)
    exit(OVERFLOW); 
   (*L).elem=newbase; 
   (*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; 
  return OK;
 }
 Status ListDelete(SqList *L,int i,ElemType *e) 
 { 
  
  ElemType *p,*q;
  if(i<1||i>(*L).length) 
   return ERROR;
  p=(*L).elem+i-1; 
  *e=*p; 
  q=(*L).elem+(*L).length-1; 
  for(++p;p<=q;++p) 
   *(p-1)=*p;
  (*L).length--; 
  return OK;
 }
 Status ListTraverse(SqList L,void(*vi)(ElemType*))
 { 
  
  
  ElemType *p;
  int i;
  p=L.elem;
  for(i=1;i<=L.length;i++)
   vi(p++);
  printf("n");
  return OK;
 }

 #include"c1.h"
 typedef int ElemType;
 #include"c2-1.h" 
 #include"bo2-1.c" 
 Status equal(ElemType c1,ElemType c2)
 { 
  if(c1==c2)
   return TRUE;
  else
   return FALSE;
 }
 void Union(SqList *La,SqList Lb) 
 { 
  ElemType e;
  int La_len,Lb_len;
  int i;
  La_len=ListLength(*La); 
  Lb_len=ListLength(Lb);
  for(i=1;i<=Lb_len;i++)
  {
   GetElem(Lb,i,&e); 
   if(!LocateElem(*La,e,equal)) 
    ListInsert(La,++La_len,e);
  }
 }
 void print(ElemType *c)
 {
  printf("%d ",*c);
 }
 int main()
 {
  SqList La,Lb;
  Status i;
  int j;
  i=InitList(&La);
  if(i==1) 
   for(j=1;j<=5;j++) 
    i=ListInsert(&La,j,j);
  printf("La= "); 
  ListTraverse(La,print);
  InitList(&Lb); 
  for(j=1;j<=5;j++) 
   i=ListInsert(&Lb,j,2*j);
  printf("Lb= "); 
  ListTraverse(Lb,print);
  Union(&La,Lb);
  printf("new La= "); 
  ListTraverse(La,print);
　 return 0;
 }