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; // 存储个数初始化为0 p->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，先定义一个指针，先给这个指针赋予realloc if( 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; // 存储个数初始化为0
p->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 10
vector *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 ； 删除 为 0
printf("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;
}