线性表和顺序表
线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列，是一种很常见的数据结构
线性表在逻辑上是线性结构，但是在物理结构上并不一定是连续的
常见的线性表有：顺序表、链表、栈、队列、字符串等
顺序表
顺序表(seqlist)是物理地址连续的存储元素的线性结构，一般情况下采用数组存储,在数组上完成数据的增删查改
可以认为，顺序表的本质就是数组
顺序表一般可以分为：1. 静态顺序表：使用定长数组存储元素。2. 动态顺序表：使用动态开辟的数组存储。
复制代码
静态顺序表
使用定长数组存储元素。
例子：静态通讯录
#define BOOK_MAX 100typedef int DataType //这样可以随时改变内容的类型
typedef struct address_book //通讯录内容{ struct perinfmt p[BOOK_MAX];//每个人信息,数组一共100个人 DataType ID;//统计每个人编号}SeqlistContact;//顺序表
复制代码
动态顺序表
动态顺序表：使用动态开辟的数组存储。
例子：动态通讯录
typedef struct PeopleInfo{ struct People* a;//指向动态开辟的结构体成员数组 int size;//标记成员个数(有效成员个数) int capacity;//容量，如果不够可以增容}PeopleInfo;
复制代码
2.1.基本架构
使用 typedef，类型可以不固定，后序想要更改存储的数据类型更方便
typedef int SLDateType;typedef struct SeqList{ SLDateType* a; size_t size; size_t capacity; // unsigned int}SeqList;
复制代码
size 是有效数字个数，同时也是最后一个数据的下一个位置的下标
2.2 初始化
指针置空，一开始可以不给容量，也可以给一定的容量
void SeqListInit(SeqList* ps){ assert(ps); ps->a = NULL; ps->capacity = 0; ps->size = 0;}
复制代码
2.3 扩容
realloc ：如果传空指针，相当于 malloc
realloc原理 1.原地扩容：如果后面空间足够则在后面扩 2.异地扩容：如果后面空间不够，则重新找一块空间开辟，把原来的数组拷贝过去，然后释放原来空间
复制代码
最初就是空指针，所以最开始使用 realloc 时相当于是 malloc
扩容每次扩两倍，要判断 realloc 是否成功
最后还要把新容量赋给 ps->capacity，把新开辟空间的地址赋给 ps->a
void CheckCapacity(SeqList* ps){ if (ps->size == ps->capacity) { //扩容 //如果最初容量为0，就把容量设置为4 //如果最初容量不为0，那就两倍扩容 int newcapacity = ps->capacity == 0 ? 4 : ps -> capacity * 2; SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (newcapacity)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1);//直接结束进程 } ps->a = tmp; ps->capacity = newcapacity; }}
复制代码
2.4 打印
遍历数组打印即可,ps->size 标志的就是有效数字的个数
void SeqListPrint(SeqList* ps){ assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n");}
复制代码
2.5 尾插
尾插：即插入到 size 位置
size：标志元素个数，size 下标是数组最后一个元素的下一个位置
注意：插入要判断容量是否满了 插入元素后：size++
void SeqListPushBack(SeqList* ps, SLDateType x){ CheckCapacity(ps); ps->a[ps->size] = x; ps->size++;}
复制代码
2.6 头插
把元素往后移动，然后在 0 位置插入元素
注意：防止元素覆盖，要从数组最后一个元素往后移动，0 位置的元素也要后移
注意：插入要判断容量是否满了 插入元素后：size++
void SeqListPushFront(SeqList* ps, SLDateType x){ int i = 0; for (i = ps->size; i > 0; i--) { ps->a[i] = ps->a[i - 1]; } //写法2 /* int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } */
ps->a[0] = x; ps->size++;}
复制代码
2.7 尾删
注意:要考虑数组中是否还有元素可以被删除
只需让 ps->size--即可，因为 size 标志的就是元素个数。最后一个元素虽然空间还在，但是我们已经没有权限访问了
void SeqListPopBack(SeqList* ps){ //温柔处理 if (ps->size == 0) { printf("已经没有元素\n"); return ; } //暴力处理：assert(ps->size >0) ps->size--;}
复制代码
2.8 头删
注意:要考虑数组中是否还有元素可以被删除
头删：即把第二个元素往前覆盖
注意：要从前面开始往前覆盖！ 删除元素：size--
void SeqListPopFront(SeqList* ps){ if (ps->size == 0) { printf("已经没有元素\n"); return ; } int i = 0; for (i = 0; i < ps->size - 1; i++) { ps->a[i] = ps->a[i+1]; } //写法2： //int begin = 1; //while (begin < ps->size) //{ // ps->a[begin - 1] = ps->a[begin]; // ++begin; //}
//写法3： //int begin = 0; //while (begin < ps->size-1) //{ // ps->a[begin] = ps->a[begin+1]; // ++begin; //}
ps->size--; }
复制代码
2.9 查找
遍历数组进行查找即可，如果数组是有序的，可以使用二分查找。如果找到了，返回对应下标，找不到返回-1
int SeqListFind(SeqList* ps, SLDateType x){ //遍历查找 int i = 0; for (i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } //找不到 return -1;}
复制代码
2.10 pos 位置插入
注意：插入要考虑容量是否足够的问题，还要考虑 pos 位置是否合法。pos 位置可以在 0 位置插入，也可以在 size 位置插入(因为 size 标志的是成员个数，同时也是最后一个元素的下一个位置的下标) 插入后：size++
在 pos 位置插入：即把 pos 位置的数据往后移动
注意：要从后往前移动
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x){ //断言：如果括号内为真就无视，如果为假就报错 //所以写成：assert(pos < 0 || pos >ps->size)是错误的
//插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置 assert(pos >= 0 && pos<=ps->size); CheckCapacity(ps);
//写法1 //int i = 0; ////往后移动 //for (i = ps->size-1 ; i > pos; i--) //{ // ps->a[i+1] = ps->a[i]; //} //ps->a[pos] = x; //ps->size++; //写法2： int i =ps->size ; while (i > pos) { ps->a[i] = ps->a[i-1]; i--; } ps->size++; ps->a[pos] = x;}
复制代码
头插尾插的写法：
头插：即在 0 位置插入
尾插：即在 size-1 位置插入
头插：SeqListInsert(ps, 0, x);尾插：SeqListInsert(ps,ps->size - 1,x)
复制代码
2.11pos 位置删除
注意：删除也要保证位置的合法性 删除后，size--
在 pos 位置删除，即把 pos 后面的数据向前覆盖。
从前往后移动(先移动 pos+1 位置的数据往前覆盖)
void SeqListErase(SeqList* ps, size_t pos){ //此时pos不可以为size， //因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置，这个位置没有存元素，不可以删除 assert(pos >= 0 && pos < ps->size); int i = 0; for (i = pos; i < ps->size -1; i++) { ps->a[i] = ps->a[i+1]; } /* //写法2： int begin = pos + 1; while (begin < ps->size) { ps->a[begin-1] = ps->a[begin]; begin++; } */ ps->size--;}
复制代码
头删尾删的写法
头删：SeqListErase(ps,0)尾删：SeqListErase(ps, ps->size - 1);
复制代码
2.12 销毁
因为数组指向的空间是动态开辟的，所以结束时要把空间销毁，防止内存泄漏。
销毁之后要把指针置空！！防止造成野指针
void SeqListDestory(SeqList* ps){ free(ps->a); ps->a = NULL; ps->size = 0; ps->capacity = 0;}
复制代码
注意事项
插入元素考虑因素：
整个顺序表空间是否满了，满了则扩容，插入之后 size 要++
头插：从后往前移动(先移动最后的数据)
尾插：直接插入到 size 位置
删除元素考虑因素
是否还有元素可以被删除，删除元素之后 size--
头删：从前往后移动(先移动前面的数据进行覆盖)
尾删：直接 size--即可
test.c
#include"Seqlist.h"void Test1(){ SeqList s; SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 3); SeqListPushFront(&s, 5); SeqListPushFront(&s, 6); SeqListPushFront(&s, 7); // 7 6 5 1 3 SeqListInsert(&s, 0,1); SeqListPrint(&s);}int main(){ Test1(); return 0;}
复制代码
Seqlist.c
#define _CRT_SECURE_NO_WARNINGS 1#pragma once#include"Seqlist.h"
void SeqListInit(SeqList* ps){ assert(ps); ps->a = NULL; ps->capacity = 0; ps->size = 0;}void SeqListDestory(SeqList* ps){ free(ps->a); ps->a = NULL; ps->size = 0; ps->capacity = 0;}
void SeqListPrint(SeqList* ps){ assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n");}void CheckCapacity(SeqList* ps){ if (ps->size == ps->capacity) { //扩容 //如果最初容量为0，就把容量设置为4 //如果最初容量不为0，那就两倍扩容 int newcapacity = ps->capacity == 0 ? 4 : ps -> capacity * 2; SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (newcapacity)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1);//直接结束进程 } ps->a = tmp; ps->capacity = newcapacity; }}//尾插void SeqListPushBack(SeqList* ps, SLDateType x){ CheckCapacity(ps); ps->a[ps->size] = x; ps->size++;}//头插void SeqListPushFront(SeqList* ps, SLDateType x){ int i = 0; for (i = ps->size; i > 0; i--) { ps->a[i] = ps->a[i - 1]; } int end = ps->size - 1;
//写法2 /* while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } */
ps->a[0] = x; ps->size++;}//头删void SeqListPopFront(SeqList* ps){ if (ps->size == 0) { printf("已经没有元素\n"); return ; } int i = 0; for (i = 0; i < ps->size - 1; i++) { ps->a[i] = ps->a[i+1]; } //写法2： //int begin = 1; //while (begin < ps->size) //{ // ps->a[begin - 1] = ps->a[begin]; // ++begin; //}
//写法3： //int begin = 0; //while (begin < ps->size-1) //{ // ps->a[begin] = ps->a[begin+1]; // ++begin; //}
ps->size--; }//尾删void SeqListPopBack(SeqList* ps){ //温柔处理 if (ps->size == 0) { printf("已经没有元素\n"); return ; } //暴力处理：assert(ps->size >0) ps->size--;}
// 顺序表查找int SeqListFind(SeqList* ps, SLDateType x){ //遍历查找 int i = 0; for (i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } //找不到 return -1;}// 顺序表在pos位置插入xvoid SeqListInsert(SeqList* ps, size_t pos, SLDateType x){ //断言：如果括号内为真就无视，如果为假就报错 //所以写成：assert(pos < 0 || pos >ps->size)是错误的
//插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置 assert(pos >= 0 && pos<=ps->size); CheckCapacity(ps);
//写法1 //int i = 0; ////往后移动 //for (i = ps->size-1 ; i > pos; i--) //{ // ps->a[i+1] = ps->a[i]; //} //ps->a[pos] = x; //ps->size++; //写法2： int i =ps->size ; while (i > pos) { ps->a[i] = ps->a[i-1]; i--; } ps->size++; ps->a[pos] = x;}
// 顺序表删除pos位置的值void SeqListErase(SeqList* ps, size_t pos){ //此时pos不可以为size， //因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置，这个位置没有存元素，不可以删除 assert(pos >= 0 && pos < ps->size); int i = 0; for (i = pos; i < ps->size -1; i++) { ps->a[i] = ps->a[i+1]; } //写法2： int begin = pos + 1; while (begin < ps->size) { ps->a[begin-1] = ps->a[begin]; begin++; } ps->size--;}
//头删：SeqListErase(ps,0)//尾删：SeqListErase(ps, ps->size - 1);////头插：SeqListInsert(ps, 0, x);//尾插：SeqListInsert(ps,ps->size - 1,x)
复制代码
Seqlist.h
#define _CRT_SECURE_NO_WARNINGS 1#pragma once// SeqList.h#pragma once#include <stdio.h>#include <assert.h>#include <stdlib.h>
typedef int SLDateType;typedef struct SeqList{ SLDateType* a; size_t size; size_t capacity; // unsigned int}SeqList;
// 对数据的管理:增删查改 void SeqListInit(SeqList* ps);void SeqListDestory(SeqList* ps);void CheckCapacity(SeqList* ps);
void SeqListPrint(SeqList* ps);void SeqListPushBack(SeqList* ps, SLDateType x);void SeqListPushFront(SeqList* ps, SLDateType x);void SeqListPopFront(SeqList* ps);void SeqListPopBack(SeqList* ps);
// 顺序表查找int SeqListFind(SeqList* ps, SLDateType x);// 顺序表在pos位置插入xvoid SeqListInsert(SeqList* ps, size_t pos, SLDateType x);// 顺序表删除pos位置的值void SeqListErase(SeqList* ps, size_t pos);
复制代码
写的时候遇到的坑点：
//在pos位置插入//错误写法：void SeqListInsert(SeqList* ps, size_t pos, SLDateType x){ assert(pos >= 0 && pos<=ps->size); CheckCapacity(ps); //写法1 //int i = 0; ////往后移动 //for (i = ps->size-1 ; i >= pos; i--) //{ // ps->a[i+1] = ps->a[i]; //} //ps->a[pos] = x; //ps->size++; //写法2： int i =ps->size -1 ; while (i >= pos) { ps->a[i+1] = ps->a[i]; i--; } ps->size++; ps->a[pos] = x;}
复制代码
错误原因：pos 是 size_t 类型，无符号整形。i 为整形
pos 和 i 进行比较时，i 会提升为无符号整形，即 i 的范围为：[0,2147483 648]，i 恒大于 0.所以若在 pos = 0 位置插入，则 i>=pos 恒成立，会造成死循环。
pos 为其他正数值的时候不会发生，因为 i 的返回时[0,2^31]，i 终究会变到小于 pos 的值跳出循环！！，但是若 pos 为 0，则 i>=pos 恒满足，死循环。所以这是个很隐藏的错误，
即使 i 也定义为无符号整形也是如此
i 和 pos 进行比较不能取相等！！！防止出现 pos 位置取 0 的情况！
//正确写法：void SeqListInsert(SeqList* ps, size_t pos, SLDateType x){ //断言：如果括号内为真就无视，如果为假就报错 //所以写成：assert(pos < 0 || pos >ps->size)是错误的
//插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置 assert(pos >= 0 && pos<=ps->size); CheckCapacity(ps);
//写法1 //int i = 0; ////往后移动 //for (i = ps->size-1 ; i > pos; i--) //{ // ps->a[i+1] = ps->a[i]; //} //ps->a[pos] = x; //ps->size++; //写法2： int i =ps->size ; while (i > pos) { ps->a[i] = ps->a[i-1]; i--; } ps->size++; ps->a[pos] = x;}
复制代码
同理在 pos 位置删除时，i 和 pos 比较也不能取等号
评论