C语言中的顺序表-创新互联

顺序表就是逻辑上相邻的数据元素物理上也相邻，连续存储
时间复杂度：最好O(1)，最差O(n)

特点：

• 支持随机访问
• 存储密度高
• 拓展容量不方便
• 插入、删除元素不方便

定义顺序表

typedef int SLDataType;
typedef struct SeqList
{SLDataType *a;//动态开辟的数组
    size_t size;//有效数据个数
    size_t capacity;//容量大小
} SeqList;

初始化顺序表

void SeqListInit(SeqList *psl)
{assert(psl !=NULL);//断言，防止传进来的指针为空
    psl->a = NULL;//初始顺序表为空
    psl->size = 0;//初始数据个数为0
    psl->capacity = 0;//初始空间容量0
}

销毁顺序表

void SeqListDestroy(SeqList *psl)
{assert(psl != NULL);
    free(psl->a);//释放malloc给数组a开辟的空间
    psl->a = NULL;
    psl->size =  0;
    psl->capacity = 0;
}

检查顺序表是否满，方便增容

void CheckCapacity(SeqList *psl)
{assert(psl !=NULL);
    
    if(psl->size == psl->capacity)
    {size_t newcapacity;
        if(psl->capacity == 0)
        {newcapacity = psl->capacity = 4;
        }
        else
        {newcapacity = 2*psl->capacity;
        }
        SLDataType *p = (SLDataType *)relloc(psl->,newcapacity);
        if (NULL == p)
        {perror("relloc");
            exit(-1);
        }
        psl->a = p;
        psl->capacity = newcapacity;
    }
}

顺序表头插

voidSeqlistPushFront(SeqList *psl,SLDataType x)
{assert(psl);
    CheckCapacity(psl);
    
    int i = 0;
    for(i = psl->size-1;i>=0;i++)
    {psl->a[i + 1] = psl->a[i];
    }
    psl->a[0] = x;
    psl->size++;
}

顺序表尾插

void SeqListPushBack(SeqList *psl,SLDataType num)
{assert(psl != NULL);
    CheckCapacity(psl);
    
    psl->a[psl->size] = x;
    psl->size++;
}

顺序表头删

void SeqListPopFront(SeqList *psl)
{assert(psl);
    
    int i = 0;
    for(i = 0;isize;i++)
    {psl->a[i] = psl->a[i+1];
    }
    psl->size--;
}

顺序表尾删

void SeqListPopBack(SeqList *psl)
{assert(psl);
    assert(psl->size >0);//顺序表不能为空
    
    //根据SLDataType类型，给0值
    psl->a[psl->size] = 0;
    psl->size--;
}

顺序表查找指定值

int SeqListFind(const SeqList *psl,SLDataType x)
{assert(psl);
    int i = 0;
    for(i=0;isize;i++)
    {if(psl->a[i] == x)
        {return i;
        }
        return -1;
    }
}

在顺序表指定下标位置插入数据

void SeqListInsert(SeqList *psl,size_t pos,SLDataType x)
{assert(psl);
    assert(pos >= 0 && pos<= psl->size);
    CheckCapacity(psl);
    
    size_t i = 0;
    for(i=psl->size;i>pos;i--)
    {psl->a[i] = psl->a[i-1];
    }
    psl->a[pos] = x;
    psl->size++;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧