基础数据结构与算法2：顺序表

顺序表是用一组地址连续的存储单元依次存储线性表中的各个元素，使线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。

顺序表实现

1.定义

• 存储单元的数据类型DataType
• 顺序表
  1.存储空间基地址datas
  2.长度size

typedef int DataType;
typedef struct Sqlist{
        DataType* datas;
        size_t size;
} sqlist;

2. 函数：创建新的顺序表并初始化

// 函数:创建顺序表指针
sqlist* sqlist_create(){
        sqlist* sq = malloc(sizeof(sqlist));
        sq->datas = NULL;
        sq->size = 0;
        return sq;
}

3.函数：向顺序表中添加元素

• 1.首添加

// 函数：首添加
void sqlist_append(sqlist* sq,DataType data){
        sq->size++;
        sq->datas = realloc(sq->datas,sq->size*sizeof(DataType));
        sq->datas[sq->size-1] = data;
}

• 2.尾添加

// 函数：尾添加
void sqlist_prepend(sqlist* sq,DataType data){
        sq->size++;
        sq->datas = realloc(sq->datas,sq->size*sizeof(DataType));
        memcpy(sq->datas+1,sq->datas,(sq->size-1)*sizeof(DataType));
        sq->datas[0] = data;
}

4.函数：获取顺序表元素

// 根据下标获取顺序表元素地址
DataType* sqlist_get(sqlist* sq,size_t index){
        return sq->datas+index;
}

5.函数：获取顺序表元素个数

// 函数：获取顺序表元素个数
size_t get_sqlist_size(sqlist* sq){
        return sq->size;
}

6.函数：向顺序表中插入元素

// 函数：插入元素
void sqlist_insert(sqlist* sq,size_t index,DataType insert_data){
        sq->datas = realloc(sq->datas,(sq->size+1)*sizeof(DataType));
        memcpy(sq->datas+index+1,sq->datas+index,(sq->size-index)*sizeof(DataType));
        sq->datas[index] = insert_data;
        sq->size++;
}

7.函数：查找顺序表中某个元素

// 函数：查找顺序表元素
// 找到：返回找到元素的地址
// 未找到：返回空指针
DataType* search_sqlist(sqlist* sq,DataType search_data){
        for(int i=0;i<sq->size;i++){
                if(sq->datas[i] == search_data) return sq->datas+i;
        }
        return NULL;
}

8.函数：删除寻书表中某个元素

// 函数：删除顺序表元素
void delete_sqlist(sqlist* sq,DataType delete_num){
        DataType* delete_flag = search_sqlist(sq,delete_num);
        if(NULL == delete_flag) return;
        // 进行依次替换
        // 指针操作
        /*
        while(delete_flag < sq->datas+sq->size){
                *delete_flag = *(delete_flag+1);
                delete_flag++;
        }
        */
        // memcpy操作
        int i = delete_flag - sq->datas; // 剩余元素个数
        memcpy(delete_flag,delete_flag+1,(sq->size-i-1)*sizeof(DataType));
        sq->size--;
}

9.函数：销毁顺序表

// 函数:销毁顺序表
// 参数:二维指针
void sqlist_destory(sqlist** sq){
        free((*sq)->datas);
        (*sq)->datas = NULL;
        (*sq)->size = 0;
        free(*sq);
        *sq = NULL;
}

优化

1.容量

• 每次增加一个元素，都要重复释放申请内存。可以预先申请一部分备用。

typedef struct Sqlist{
        DataType* datas;
        size_t size;
        size_t capacity;
} sqlist;

2.遍历

• 提供一个对顺序表的整体操作的接口。

// 遍历
// 参数：顺序表 函数指针
void sqlist_traverse(sqlist* sq,void(*func)(DataType*)){
        for(int i=0;i<get_sqlist_size(sq);i++){
                func(sq->datas+i);
        }
        printf("\n");
}

// 打印数字
void Print_arr(DataType* data){
        printf("%d ",*data);
}

// 函数：打印顺序表
void sqlist_print(sqlist* sq){
        /*
        for(int i=0;i<sq->size;i++){
                printf("%d ",sq->datas[i]);
        }
         printf("\n");
        */
        sqlist_traverse(sq,Print_arr);
}

顺序表优缺点

• 优点
  1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
  2.可以快速地存取表中的任一位置元素。

• 缺点
  1.插入和删除操作需要移动大量元素；
  2.当线性表长度变化较大时，难以确定存储空间的容量；
  3.造成存储空间的“碎片”。

  
  
  存储空间碎片化