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;
}