C語言--動態順序表

C語言--動態順序表

  順序表是在計算機內存中以數組的形式保存的線性表，是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。線性表采用順序存儲的方式存儲就稱之為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連續的存儲單元中。分為靜態順序表和動態順序表。 .h文件  

#pragma once

#include<string.h>
#include<assert.h>
#include<malloc.h>


typedef int DataType;
typedef struct SeqList//定義一個結構體
{
    DataType* arry;
    size_t size;
    size_t capacity;
}SeqList;

void InitSeqList(SeqList*Seq);//初始化結構體
void PrintSeqList(SeqList*Seq);//輸出函數
void PushBack(SeqList*Seq,DataType x);//後面插入數據
void PopBack(SeqList*Seq);//後面刪除數據
void PushFrant(SeqList*Seq,DataType x);//前面插入數據
void PopFrant(SeqList*Seq);//前面刪除數據
int Find(SeqList*Seq, DataType x);//查找數據
void Erase(SeqList*Seq,size_t pos);//清除第幾個數據
void Remove(SeqList*Seq,DataType x);//刪除第一個數據x
void Removeall(SeqList*Seq,DataType x);//刪除所有的x
void firstRemoveall(SeqList*Seq, DataType x);//刪除所有x的第二種方法
void Modify(SeqList*Seq, size_t pos, DataType x);//把第pos個數據修改成x
void Insert(SeqList*Seq, size_t pos, DataType x);//把第pos個數據插入x
void check(SeqList*Seq);//判斷指針是否有效，並動態開辟內存
void check(SeqList*Seq)
{
    assert(Seq);
    if (Seq->size >= Seq->capacity)
    {
        DataType* tmp;
        Seq->capacity *= 2;
        tmp = (DataType*)malloc(sizeof(DataType)*(Seq->capacity));
        memcpy(tmp, Seq->arry, sizeof(DataType)*(Seq->size));
        free(Seq->arry);
        Seq->arry=tmp;
    }
}

void InitSeqList(SeqList*Seq)
{
    assert(Seq);
    Seq->capacity = 2;
    Seq->arry = (DataType*)malloc(sizeof(DataType)*Seq->capacity);
    Seq->size = 0;
     
}
void PrintSeqList(SeqList*Seq)
{
    int i = 0;
    for (i = 0; i < (int)Seq->size; i++)
    {
        printf("%d", Seq->arry[i]);
    }
}
void PushBack(SeqList*Seq, DataType x)
{
     check(Seq);
     Seq->arry[Seq->size++] = x;
}
void PopBack(SeqList*Seq)
{
    assert(Seq);
    --Seq->size;
}
void PushFrant(SeqList*Seq, DataType x)
{
    check(Seq);
    int i = Seq->size-1;
    for (; i >= 0; i--)
    {
        Seq->arry[i + 1] = Seq->arry[i];
    }
    Seq->arry[0] = x;
    ++Seq->size;
}
void PopFrant(SeqList*Seq)
{
    assert(Seq);
    int i =0;
    for (; i<=(int)Seq->size;i++)
    {
        Seq->arry[i] = Seq->arry[i+1];
    }
    --Seq->size;
}
void Remove(SeqList*Seq, DataType x)
{
    assert(Seq);
    int i = 0;
    for (; i<(int)Seq->size; i++)
    {
        if (Seq->arry[i] == x)
        {
            Seq->arry[i] = Seq->arry[i+1];
             
        }
    }
    --Seq->size;
}
void Removeall(SeqList*Seq, DataType x)
{
    assert(Seq);
    int firstIndex = 0, secondIndex = 0;
    int count = 0;
    while (secondIndex<=(int)Seq->size)
    {
        if (Seq->arry[secondIndex] == x)
        {      
            count++;
        }
        else
        {
            Seq->arry[firstIndex] = Seq->arry[secondIndex];
            firstIndex++;
        }
        secondIndex++;
    }
    Seq->size-=count;   
}
void firstRemoveall(SeqList*Seq, DataType x)
{
    assert(Seq);
    int i = 0;
    for (; i <(int)Seq->size; i++)
    {
        if (Seq->arry[i] == x)
        {
            int begin = i;
            for (; begin < (int)Seq->size - 1; begin++)
            {
                Seq->arry[begin] = Seq->arry[begin + 1];
            }
            --Seq->size;
            i--;
        }      
    }  
}
int Find(SeqList*Seq, DataType x)
{
    assert(Seq);
    int i = 0;
    for (; i < (int)Seq->size; i++)
    {
        if (Seq->arry[i] == x)
        {
            return Seq->arry[i];
        }
        else
        {
            return -1;
        }          
    }
    return 0;
}
void Erase(SeqList*Seq, size_t pos)
{
    assert(Seq);
    int i = pos-1;
    for (; i<(int)Seq->size-1; i++)
    {
        Seq->arry[i] = Seq->arry[i+1];             
    }
    --Seq->size;
}
void Modify(SeqList*Seq, size_t pos, DataType x)
{
    check(Seq);
    int i = 0;
    for (; i <(int) Seq->size - 1; i++)
    {
        if (i== pos-1)
        {
            Seq->arry[i] = pos;
        }
    }
}
void Insert(SeqList*Seq, size_t pos, DataType x)
{
    check(Seq);
    int i = Seq->size - 1;
    for (; i >= (int)pos; i--)
    {
        Seq->arry[i + 1] = Seq->arry[i];
    }
    Seq->arry[pos] = x;
    Seq->size++;
}

 

  .c 文件  

#include<stdio.h>
#include"test.h"
SeqList Seq;
void test()
{
    PushBack(&Seq,1);
    PushBack(&Seq,2);
    PushBack(&Seq,3);
    PushBack(&Seq,4);
    PopBack(&Seq);
    PrintSeqList(&Seq);
}
void test1()
{
    PushFrant(&Seq, 1);
    PushFrant(&Seq, 2);
//  PopFrant(&Seq);
    PushFrant(&Seq, 4);
    PushFrant(&Seq, 3);
//  Remove(&Seq, 2);
//  Removeall(&Seq, 2);y
//  firstRemoveall(&Seq, 2);
//  Erase(&Seq, 1);
//  Modify(&Seq, 3, 2);
    Insert(&Seq, 4, 6);
    PrintSeqList(&Seq);
}
int main(void)
{
    InitSeqList(&Seq);
    test1();
}