リニアテーブルの線形記憶構造

順序格納構造とは、各要素のデータタイプが同じであるため、プログラム言語(ここではC言語)を用いて配列を用いて順序記憶構造を実現することができる、一セグメントのアドレスで必要な記憶ユニットによって一度に線形テーブルのデータ要素を記憶することである.
文章の最後の使用例は、順序記憶構造の理解を強化する.
構造定義コードを順次記憶します.

typedef int ElemType;
typedef struct
{
  ElemType data[MAXSIZE];
  int length;
}Sqlist;

  ここで注意したいのは、線形表長と配列長の違いです.     配列長:リニアテーブルを格納する記憶空間の長さを指し、記憶割り当て後のこの量は通常不変です. 線形表長:線形表のデータ要素の個数を指し、線形表の挿入または削除によって変化します.
要素の取得操作:

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
//    
int GetElem(Sqlist L,int i,ElemType *e)
{
  if(L.length==0||i<1||i>L.length)
    { return ERROR;}
   *e=L.data[i-1];
   return OK;
}

要素を挿入する操作:
 

//    
int ListInsert(Sqlist *L,int i,ElemType e)
{
  int k;
  if(L->length==MAXSIZE)
     {return ERROR;}
  if(i<1||i>L->length+1)
     {return ERROR;}
  if(i<=L->length)
     {
	   for(k=L->length;k>=i-1;k--)
	   {
	     L->data[k+1]=L->data[k];
	   }
	 }
	 
	 L->data[i-1]=e;
	 L->length++;
	 return OK;
}

要素の削除操作:

int ListDelete(Sqlist *L,int i,ElemType *e)
{
  
  int k;
  if(L->length==MAXSIZE)
     {return ERROR;}
  if(i<1||i>L->length)
     {return ERROR;}
	 
  *e=L->data[i-1];
  if(ilength)
  {
     for(k=i;klength;k++)
	 {
	   L->data[k-1]=L->data[k];
	 }
  }
  L->length--;
  return OK;
}

最後にデバッグの例を示します.

#include
#define MAXSIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef struct
{
  ElemType data[MAXSIZE];
  int length;
}Sqlist;
//    
int GetElem(Sqlist L,int i,ElemType *e)
{

  if(L.length==0||i<1||i>L.length)
    { return ERROR;}
	
   *e=L.data[i-1];
   return OK;
}

//    
int ListInsert(Sqlist *L,int i,ElemType e)
{
  int k;
  if(L->length==MAXSIZE)
     {return ERROR;}
  if(i<1||i>L->length+1)
     {return ERROR;}
  if(i<=L->length)
     {
	   for(k=L->length;k>=i-1;k--)
	   {
	     L->data[k+1]=L->data[k];
	   }
	 }
	 
	 L->data[i-1]=e;
	 L->length++;
	 return OK;
}
//    
int ListDelete(Sqlist *L,int i,ElemType *e)
{
  
  int k;
  if(L->length==MAXSIZE)
     {return ERROR;}
  if(i<1||i>L->length)
     {return ERROR;}
	 
  *e=L->data[i-1];
  if(ilength)
  {
     for(k=i;klength;k++)
	 {
	   L->data[k-1]=L->data[k];
	 }
  }
  L->length--;
  return OK;
}


int main()
{
	Sqlist list={{3,5,1,7,9,2,1},7};
	printf("%d
",list.length);
	ElemType *e,test=1;
	e=&test;
	
	printf("---------------------------      -----------------------------------
");
	//      
	  int k;
	 for(k=1;k<=list.length;k++)
	 {
	 	GetElem(list,k,e);
	 	printf("%d ",*e);
	 }
	 
	
	printf("
-----------------------------      ---------------------------------
");
	
	//      

	if(GetElem(list,3,e)==OK)
	{
	  printf("The Element=%d
",*e);
	}

	printf("-----------------------------      ---------------------------------
");
	//      
	if(ListInsert(&list,4,6)==OK)
	{
		printf("insert successdully!
");
	}
	if(GetElem(list,4,e)==OK)
	{
	  printf("insert,The Element=%d
",*e);
	}
	
	printf("---------------------------      -----------------------------------
");
	//      
	  if(ListDelete(&list,4,e)==OK)
	{
		printf("delete successdully!
");
		printf("delete,The Element=%d
",*e);
	}
	 else
	  {
		printf("delete fail...");
      }
    
    printf("---------------------------      -----------------------------------
");
	//      
	  int i;
	 for(i=1;i<=list.length;i++)
	 {
	 	GetElem(list,i,e);
	 	printf("%d ",*e);
	 }
	 
	 return 0;
	 
}

まとめ:
線形テーブルの順序格納構造の挿入、削除、クエリーの時間の複雑さは次の通りです. 挿入:O(n) 削除:O(n)クエリー:O(1)
利点:線形テーブルのいずれかの未知の要素を迅速に取得することができます.
            要素間の未知は順番に格納されるので、要素間の論理関係を表すために追加的に記憶空間を増加させる.短所:挿入と削除を実行する場合は、大量の要素を移動する必要があります.
            線形表の長さがランダムに変動する場合には適しない.
            記憶空間の「破片」を引き起こしやすく、空間を浪費する.