c实现顺序表
目录
c语言实现顺序表
完整代码实现
c语言实现顺序表
顺序表的结构定义：
typedef struct vector {int size; // 顺序表的容量int count; // 顺序表现在存储了多少个数据int *data; // 指针指向连续的整型存储空间 } vector;顺序表的结构操作：
1、初始化顺序表
vector *getNewVector(int n) // 获取一个存储上限为n的顺序表 {vector *p = (vector *)malloc(sizeof(vector)); // 为顺序表结构体动态开辟空间p->size = n; // 上限p->count = 0; // 存储个数初始化为0p->data = (int *)malloc(sizeof(int *) * n); // 指针指向连续的存出区return p; }2、销毁顺序表
void clear(vector *v) {if (v == NULL)return; // 如果没有顺序表则返回free(v->data); // 先销毁连续的存储区free(v); // 再销毁顺序表本身的存储空间return; }3、插入数据
int insert(vector *v, int pos, int value) // 在pos位置插入 {if (pos < 0 || pos > v->count)return 0; // 插入位置合不合法// if (v->size == v->count)// return 0; if(v->size == v->count && !expand(v)) return 0; // 判断表是否满了for (int i = v->count - 1; i >= pos; i--) // 逆序遍历，后移{v->data[i + 1] = v->data[i];}v->data[pos] = value; // 插入v->count += 1; // 维护数据return 1; }4、删除数据
int erase(vector *v, int pos) // 在pos位置删除数据 {if (pos < 0 || pos >= v->count)return 0; // 删除位置合法不if (v->count == 0)return 0; // 无数据for (int i = pos + 1; i < v->size; i++) // 前序遍历，前移{v->data[i - 1] = v->data[i];}v->count -= 1; // 维护数据return 1; }5、输出数据
// 5、输出数据 void output_vector(vector *v) {int len = 0;for (int i = 0; i < v->size; i++){len += printf("%3d", i);}printf("\n");for (int i = 0; i < len; i++)printf("-");printf("\n");for (int i = 0; i < v->count; i++){printf("%3d", v->data[i]);}printf("\n");printf("\n");return; }6、扩容数据
注意：
realloc的三种工作方式
1、试着在原内存的基础上向后延展内存空间
2、当后面的内存不够用了，会重新找一块内存将原来的复制过来然后向后延展
3、若重新找的内存没有足够大的，就返回NULL。
int expand(vector* v) {if(v == NULL) return 0;int * p = (int *)realloc(v->data,sizeof(int) * 2 * v->size); //为了避免realloc工作原理产生的bug，先定义一个指针，先给这个指针赋予reallocif( p == NULL) return 0; //若p返回NULL，则扩容空间失败 返回就可以了v->data = p;v->size *= 2;return 1; }
完整代码实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>// 顺序表 结构定义
typedef struct vector
{int size; // 顺序表的容量int count; // 顺序表现在存储了多少个数据int *data; // 指针指向连续的整型存储空间
} vector;// 顺序表 结构操作
// 1、初始化顺序表
vector *getNewVector(int n) // 获取一个存储上限为n的顺序表
{vector *p = (vector *)malloc(sizeof(vector)); // 为顺序表结构体动态开辟空间p->size = n; // 上限p->count = 0; // 存储个数初始化为0p->data = (int *)malloc(sizeof(int *) * n); // 指针指向连续的存出区return p;
}
// 2、销毁顺序表
void clear(vector *v)
{if (v == NULL)return; // 如果没有顺序表则返回free(v->data); // 先销毁连续的存储区free(v); // 再销毁顺序表本身的存储空间return;
}
//6、扩容
int expand(vector* v)
{if(v == NULL) return 0;int * p = (int *)realloc(v->data,sizeof(int) * 2 * v->size); if( p == NULL) return 0;v->data = p;v->size *= 2;return 1;
}
// 3、插入
int insert(vector *v, int pos, int value) // 在pos位置插入
{if (pos < 0 || pos > v->count)return 0; // 插入位置合不合法// if (v->size == v->count)// return 0; if(v->size == v->count && !expand(v)) return 0; // 判断表是否满了for (int i = v->count - 1; i >= pos; i--) // 逆序遍历，后移{v->data[i + 1] = v->data[i];}v->data[pos] = value; // 插入v->count += 1; // 维护数据return 1;
}
// 4、删除
int erase(vector *v, int pos) // 在pos位置删除数据
{if (pos < 0 || pos >= v->count)return 0; // 删除位置合法不if (v->count == 0)return 0; // 无数据for (int i = pos + 1; i < v->size; i++) // 前序遍历，前移{v->data[i - 1] = v->data[i];}v->count -= 1; // 维护数据return 1;
}
// 5、输出数据
void output_vector(vector *v)
{int len = 0;for (int i = 0; i < v->size; i++){len += printf("%3d", i);}printf("\n");for (int i = 0; i < len; i++)printf("-");printf("\n");for (int i = 0; i < v->count; i++){printf("%3d", v->data[i]);}printf("\n");printf("\n");return;
}int main(void)
{srand(time(0)); //实现随机数
#define MAX_OP 10vector *v = getNewVector(2);for (int i = 0; i < MAX_OP; i++){int op = rand() % 4, pos, val, ret;switch (op){//75% 插入case 0:case 1:case 2:pos = rand() % (v->count + 2); //随机位置val = rand() % 100; //随机值ret = insert(v, pos, val); //插入 为 1 ； 删除 为 0printf("insert %d at %d to vector = %d\n",val, pos, ret);break;//25% 删除case 3:pos = rand() % (v->count + 2);ret = erase(v, pos);printf("erase item at %d in vector = %d\n",pos, ret);break;}output_vector(v);}clear(v); //销毁表return 0;
}