DS:順序表執行個體

文章目錄

• • • • 順序表
      • • • 靜态順序表(編譯期間決定的)
          • 動态順序表(運作期間決定的)
          • 初始化與銷毀
          • 增加(插入)資料
          • 擴容
          • 删除資料
          • 查找資料
          • 修改資料
          • 缺點

順序表

• 邏輯上線性的，實體存儲上位址連續的存儲單元；

靜态順序表(編譯期間決定的)

typedef struct SeqList
{
    int arry[100];//能存100個數的靜态順序表
    int size;//表示目前順序表裡有多少個元素，也表示了下一個元素插入時的下标；
} SeqList;
           

動态順序表(運作期間決定的)

typedef struct SeqList
{
    int *arry;//指向堆上的空間；
    int size;//表示目前順序表裡有多少個元素，也表示了下一個元素插入時的下标；
    int capacity;//容量；
} SeqList;
           

初始化與銷毀

void SeqListInit(SeqList* seqList)
{
  assert(seqList != NULL);//seqList 必定是要存在的才可以處理，是以要先判斷；
  seqList->arry = (int*)malloc(sizeof(int)*seqList->capacity);
  seqList->size =0;
}

void SeqListDel(SeqList* seqList)
{
  assert(seqList !=NULL);
  assert(seqList->arry !=NULL);
  free(seqList->arry);
  seqList->size = 0;
}
           

增加(插入)資料

void SeqListPushBack(SeqList*seqList,int vale)
{
   assert(seqList!=NULL);
   assert(seqList->arry!=NULL);
   seqList->arry[seqList->size]=vale;
   seqList->size++;
}//尾插入；

void SeqListPushFront(SeqList*seqList,int vale)
{
   assert(seqList!=NULL);
   assert(seqList->arry!=NULL);
   for(int i =seqList->size;i>0;i--)
   {
       seqList->arry[i]=seqList->arry[i-1];
   }
   seqList->arry[i] = 0;
   seqList->size++;
}//頭插入:寫循環，确定循環邊界；

void SeqListPushInsert(SeqList*seqList,int vale，int pos)
{
   assert(seqList!=NULL);
   assert(seqList->arry!=NULL);
   assert(pos>=0 && pos<=seqList->size);
   for(int i =seqList->size;i>pos;i--)
   {
       seqList->arry[i]=seqList->arry[i-1];
   }
   seqList->arry[pos] = value;
   seqList->size++;
}//中間插入:寫循環，确定循環邊界；
           

擴容

void CheckCapacity(SeqList*seqList,int vale)
{
   assert(seqList!=NULL);
   assert(seqList->arry!=NULL);
   if(seqList->size<seqList->capacity)
   {
      return;
   }
   seqList->capacity +=  seqList->capacity;//節省時間，較為浪費空間；
   int* tmp = realloc(seqList->arry,sizeof(int)*seqList->capacity)
   if(tmp!=NULL)
   {
      seqList->arry = tmp;
   }
   else
   {
      printf("擴容失敗!\n");
   }
}//中間插入:寫循環，确定循環邊界；
           

删除資料

void SeqListPoplBack(SeqList*seqList,int vale)
{
   assert(seqList!=NULL);
   assert(seqList->arry!=NULL);
  // seqList->arry[seqList->size]=vale;
   assert(seqList->size>0);
   seqList->size--;
}//尾删除；

void SeqListPopFront(SeqList*seqList,int vale)
{
   assert(seqList!=NULL);
   assert(seqList->arry!=NULL);
   for(int i =1;i<seqList->size;i--)
   {
       seqList->arry[i-1]=seqList->arry[i];
   }
   seqList->size--;
}//頭删；

void SeqListPopInsert(SeqList*seqList,int vale，int pos)
{
   assert(seqList!=NULL);
   assert(seqList->arry!=NULL);
   assert(pos>=0 && pos<=seqList->size);
   for(int i =pos;i<seqList->size-1;i--)
   {
       seqList->arry[i]=seqList->arry[i+1];
   }
   seqList->size--;
}//中間删除；
           

查找資料

int SeqListFind(const SeqList*seqList,int target)
{
  for(int i =0;i<seqList->size;i++)
  {
     if(seqList->arry[i]==target)
     {
        return i+1;
     }
  }
  return  -1;
}
           

修改資料

void SeqListModify(SeqList*seqList,int pos,int value)
{
 assert(pos>=0&&pos<seqList->size);
 seqList->arry[pos] = value;
}
           

缺點

• 中間/頭部插入時間複雜度為O(N);
• 擴容需要申請新空間，容易造成浪費；