データ構造基礎二---のモジュール一「線形記憶【配列】」

モジュール1:リニアストレージ【すべてのノードを1本の直線で貫通する】
一:連続記憶[配列]//連続記憶とはアドレス連続を指す
    1.配列とは
要素タイプが同じで、サイズが等しい
    2.配列の長所と短所(チェーンテーブルに対して)
利点:アクセス速度が速い
欠点:実装は配列の長さを知らなければならない
大きな連続メモリブロックが必要
要素の挿入と削除が遅い
空間には通常制限があります
JAVAのArrayListオブジェクトのサンプルコードを模倣する:

#include
#include
#include//   stdlib 

//                     struct Arr             。
struct Arr
{
   int * pBase;//              
   int len;//              
   int cnt;//           
   //int increment;//      
   //                                 
};

//                   。
void init_arr(struct Arr * pArr,int length);//     

bool append_arr(struct Arr * pArr,int val);//        
bool insert_arr(struct Arr * pArr,int pos,int val);//pos   1     pso            
bool  delete_arr(struct Arr * pArr,int pos,int *pVal);//           。
bool get();

bool is_empty(struct Arr * pArr);
bool is_full(struct Arr * pArr);

void sort_arr(struct Arr * pArr);
void show_arr(struct Arr * pArr);

void inversion_arr(struct Arr * pArr);//    

int main(void)
{
   struct Arr  arr;
   int val;
   init_arr(&arr,6);

   show_arr(&arr);

/* append_arr(&arr,1);
   append_arr(&arr,2);
   append_arr(&arr,3);
   append_arr(&arr,4);
   append_arr(&arr,5);
	
*/
   append_arr(&arr,1);
   append_arr(&arr,2);
   append_arr(&arr,3);
   append_arr(&arr,4);
   //insert_arr(&arr,5,99);
   show_arr(&arr);
/* if(delete_arr(&arr, 3, &val))
   {
     printf("    
");
     printf("       ：%d
",val);

   }
	
   else{
	printf("    ");
   }
*/
   inversion_arr(&arr);
   show_arr(&arr);
   sort_arr( &arr);
   show_arr(&arr);
		return 0;
}

void init_arr(struct Arr * pArr,int length)
{
   //(*pArr ).len = 99;
   pArr -> pBase = (int *) malloc(sizeof(int)*length);
   //                NULL
   if(NULL == pArr ->pBase)
   {
     printf("        ！
");
     exit(-1);//      
   }
   else
   {	
     pArr ->len = length;
     pArr->cnt = 0;
   }
   return;	
}

bool is_empty(struct Arr * pArr)
{
  if(0 == pArr->cnt)
     return true;
  else
     return false;
}

bool is_full(struct Arr * pArr)
{
   if(pArr->cnt == pArr ->len)
     return true;
   else
     return false;
}

void show_arr(struct Arr * pArr)
{
//   if(    ）
//	        
//   else
//	        
   if(is_empty(pArr))
   {
     printf("      
");	
   }
   else
   {	
      for(int i = 0;icnt;++i)
      {
	printf("%d
",pArr->pBase[i]);
      }
      printf("
");
   }
}

bool append_arr(struct Arr * pArr,int val)//        
{
   //      false
   if(is_full(pArr))
      return false;	
   //       
   pArr->pBase[pArr->cnt] = val;
   (pArr->cnt)++;

   return true;
} 

//                   
bool insert_arr(struct Arr * pArr,int pos,int val)
{
  int  i;
  if(is_full(pArr))
     return false;
  if(pos<1 || pos>pArr->cnt+1)
  {
     return false;
  }
  for(i = pArr->cnt;i>= pos -1;--i)
  {
    pArr ->pBase[i+1] = pArr->pBase[i];	
  }
  pArr->pBase[pos-1] = val;
  (pArr->cnt)++;
  
  return true;
}

bool  delete_arr(struct Arr * pArr,int pos,int *pVal)
{
  int i ;
  if(is_empty(pArr))
    return false;

  if(pos<1 || pos>pArr ->cnt)
    return false;
  *pVal = pArr->pBase[pos-1];
  for(i = pos;icnt;i++)
  {
    pArr->pBase[i-1] = pArr->pBase[i];
  }
  pArr->cnt --;
  return true;
}

void inversion_arr(struct Arr * pArr)
{
  int i = 0;
  int j = pArr ->cnt-1;
  int t;
  while(ipBase[i];
     pArr->pBase[i] = pArr ->pBase[j];
     pArr->pBase[j] = t;
     i++;
     j--;
   }
}

//                             
//         
void sort_arr(struct Arr * pArr)
{
  int i ,j;
  int t;

  for(i = 0;icnt;++i)
  {
    for(j = 1;j<=pArr->cnt;++j)
    {
      if(pArr->pBase[j] pBase[i])
      {
        t =pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
      }
    }
  }
}