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);
• 扩容需要申请新空间，容易造成浪费；