本人在写该文章过程中发现一个内容及其清晰地文章自己也很受益:

http://data.biancheng.net/view/157.html

因此本文章主要注重代码的实现并解析,以代码为基础进行顺序表的讲解.

顺序表详解及其实现

一 什么是顺序表

线性表 (linear list): 线性表是最基本,最简单,也是最常用的一种数据结构。

线性表中数据元素之间的关系是一对一的关系, 即除了第一个和最后一个数据元素之外, 其它数据元素都是首尾相

接的 (绝大部分线性表满足,有特例)

线性表，基于数据在实际物理空间中的存储状态，又可细分为顺序表（顺序存储结构）和链表（链式存
储结构）

顺序表: 在计算机内存中以数组的形式保存的线性表

二 顺序表的代码实现(注释详细)

1. 顺序表的初始化

多文件编写- Table.h (用于函数定义) , Table.c (写入函数内容与Table.h联合使用) , main.c (主程序)

文件名Table.h

//结构体 Table:表类型
typedef struct {int* head;  // 1 指针 存储申请的内存首地址int length; // 2 长度 记录当前顺序表元素个数int size;   // 3 大小 记录当前的顺序表最大长度
}Table;// 创建一个顺序表
// 参数: 初始长度
Table CreatTable(int SIZE);// 给所有元素初始值
// 参数: 表指针 (表以创建完成,只需向表中存储内容)
Table* SetTable(Table* ptable);

文件名:Table.c (尝试多文件编写)

// 创建一个(int型数据)顺序表
// 参数:初始长度
Table CreatTable(int SIZE) {Table table;//创建一个空的顺序表,动态申请内存(存储空间)table.head = (int*)malloc(sizeof(int) * SIZE); // malloc用于申请动态内存,详情见往期文章:指针(三)动态内存//判断:  malloc()函数如果申请失败返回NULL(0)if (!table.head) // table.head==NULL 与 !table.head 判断等价{printf("动态内存申请失败!!\n");exit(0); //结束程序代码}//当动态内存申请成功时:table.length = 0;   // 长度初始化为 0(开始顺序表内未存储元素_因此初始化长度为0)table.size = SIZE;  // 大小初始化为 SIZE (size为内存大小)return table;
}// 给所有元素初始值
// 参数: 表指针 (表以创建完成,只需向表中存储内容)
Table* SetTable(Table* ptable) {printf("向表内输入%d个整数:", ptable->size);// size_t类型产生:typedef unsigned int size_t;(非负整型变量)// "->" :指针取结构体子数据for (size_t i = 0; i < ptable->size; i++) // 遍历整个表{scanf("%d",&ptable->head[i]);   // 赋值并通过i增加不断偏移头指针ptable->length++;               // 每添加一个元素,顺序表长度增加一}return ptable;
}// 输出所有元素值
// 参数: 表/表指针(此处用表作为参数_防止改变实参的值)
void displayTable(Table table) {printf("顺序表中存储的元素是:\n");for (size_t i = 0; i < table.length; i++){printf("%d ", table.head[i]);}printf("\ntable.size = %d , table.length = %d ;\n\n", table.size, table.length);
}

文件名:main.c

#include<stdio.h>
#include"Table.h"int main() {// 创建顺序表Table t;t = CreatTable(5);// 给初始值SetTable(&t);// 输出顺序表displayTable(t);return 0;
} 

2.顺序表的基本操作

这里只给出Table.c的代码实现,具体内容见完整代码

增(插入元素)

// 插入一个元素
// 参数:表指针,插入值,插入位置下标 
Table* addNum(Table* ptable, int num, int pos) {// 判断参数是否可以执行(插入位置超出范围)// 插入范围: pos(0 --- ptable->length)if (pos < 0 || pos >ptable->length) {printf("参数错误! 表中无法找到插入位置\n");return ptable;}// 能够插入// 判断是否有存储空间_如果存储空间不足则扩容if (ptable->length >= ptable->size) {printf("表指针内存不足! 开始扩容....\n");// 扩容:(动态内存扩容具体内容见往期文章_指针(三)动态内存)// 1. 记录原来的内存int* pTemp = ptable->head; // 只有head涉及内存,无需Table*只需使用int*即可// 2. 申请新的内存ptable->head = (int*)calloc(sizeof(int), ptable->size *= 2); // 以2倍方式扩容并更改size值// 判断扩容是否成功(内容与Table.c_16行代码类似)if (!ptable->head) {printf("动态内存申请失败! 未成功扩容_未添加元素");// 未成功扩容则把原来的内存恢复(不能丢弃)ptable->head = pTemp;return ptable;}// 3. 拷贝新的内存for (size_t i = 0; i < ptable->length; i++){ptable->head[i] = pTemp[i];}// 4. 释放原来的内存free(pTemp);// 5. 置空pTemp = NULL;   //防止变成野指针}// 插入:// 1.后移(先移动后面的元素)for (int i = ptable->length; i >= pos; i--){ptable->head[i + 1] = ptable->head[i];}// 2.插入ptable->head[pos] = num;// 3.更改长度ptable->length++;return ptable;
}

删(删除元素)

// 删除元素 (按照下标删除 返回指针)
// 参数: 表指针,下标
Table* delNum(Table* ptable, int pos) {// 判断参数是否可以执行(删除位置超出范围)if (pos >= ptable->length || pos < 0) {printf("参数错误! 表中无法找到删除位置\n");return ptable;}// 删除for (int i = pos; i < ptable->length; i++){ptable->head[i] = ptable->head[i + 1];}// 改变长度ptable->length--;// 判断是否缩减大小if (ptable->length <= ptable->size / 2 && ptable->size % 2 == 0) {// 满足缩减条件printf("以满足内存缩减条件,正在重新分配内存...\n");// 缩减内存:// 1. 记录原来内存int* ptemp = ptable->head;// 2. 申请新的内存ptable->head = calloc(sizeof(int), ptable->size /= 2);// 判断缩减是否成功if (!ptable->head) {printf("动态内存申请失败! 未成功缩减");// 未成功缩减则把原来的内存恢复(不能丢弃)ptable->head = ptemp;return ptable;}// 3. 拷贝新的内存for (size_t i = 0; i < ptable->length; i++){ptable->head[i] = ptemp[i];}// 4. 释放原来的内存free(ptemp);// 5. 置空ptemp = NULL;}return ptable;
}

改(更改元素)

// 更改元素 按照下标更改元素 返回指针
// 参数: 表指针 下标 值
Table* changeNum(Table* ptable, int pos, int num) {// 判断参数是否可以执行(更改位置超出范围)if (pos > ptable->length - 1 || pos < 0) {printf("参数错误! 表中无法找到修改位置_修改失败\n");return ptable;}ptable->head[pos] = num;return ptable;
}

查(查找元素)

// 查找元素 按数值查找(只返回找到的第一个) 返回下标
// 参数: 表,数值
int findWithNum(Table table, int num) {for (int i = 0; i < table.length; i++){if (num == table.head[i]) {return i;}}return -1; // 找不到返回-1 程序员查找代码规范!!(找不到返回-1)
}

完整代码-输出效果

效果:(对照主程序main.c查看)

main.c

#include<stdio.h>
#include"Table.h"int main() {// 创建顺序表Table t;t = CreatTable(5);// 给初始值SetTable(&t);// 输出顺序表displayTable(t);// 插入值;addNum(&t, 13, 3); //在顺序表t中的下标为3的位置插入数值13;// 输出顺序表displayTable(t);// 按位置删除值并输出(链式操作_两个函数写在一起_作用:装逼)   在顺序表t中的下标为3的位置删除数值;displayTable(*delNum(&t, 3));// 查找 (测试方法,如果找到数值4_找到则删除并输出)displayTable(*delNum(&t, findWithNum(t, 4)));   //又是一个装逼的代码// 修改displayTable(*changeNum(&t, 3, 1314)); //把顺序表t中下标为3的数值更改为1314后输出;return 0;
} 

Table.h

#define _CRT_SECURE_NO_WARNINGS 1   // 解决VS2019 scanf不安全报错问题#ifndef _TABLE_
#define _TABLE_/* 一.定义顺序表 */
//结构体 Table:表类型
typedef struct {int* head;  // 1 指针 存储申请的内存首地址int length; // 2 长度 记录当前顺序表元素个数int size;   // 3 大小 记录当前的顺序表最大长度
}Table;/* 函数声明 */// 创建一个顺序表
// 参数: 初始长度
Table CreatTable(int SIZE);// 给所有元素初始值
// 参数: 表指针 (表以创建完成,只需向表中存储内容)
Table* SetTable(Table* ptable);// 插入一个元素
// 参数: 表指针,插入值,插入位置坐标 
Table* addNum(Table* ptable, int num, int pos);// 输出所有元素值
// 参数: 表/表指针(此处用表作为参数_防止改变实参的值)
void displayTable(Table table);// 删除元素 (按照下标删除 返回指针)
// 参数: 表指针,下标
Table* delNum(Table* ptable, int pos);// 查找元素 按数值查找(只返回找到的第一个) 返回下标
// 参数: 表,数值
int findWithNum(Table table, int num);// 更改元素 按照下标更改元素 返回指针
// 参数: 表指针 下标 值
Table* changeNum(Table* ptable, int pos, int num);#endif

Table.c

#include"Table.h"
#include<stdlib.h>
#include<stdio.h>#define _CRT_SECURE_NO_WARNINGS 1   // 解决VS2019 scanf不安全报错问题// /* 函数定义 */// 创建一个(int型数据)顺序表
// 参数:初始长度
Table CreatTable(int SIZE) {Table table;//创建一个空的顺序表,动态申请内存(存储空间)table.head = (int*)malloc(sizeof(int) * SIZE); // malloc用于申请动态内存,详情见往期文章:指针(三)动态内存//判断:  malloc()函数如果申请失败返回NULL(0)if (!table.head) // table.head==NULL 与 !table.head 判断等价{printf("动态内存申请失败!!\n");exit(0); //结束程序代码}//当动态内存申请成功时:table.length = 0;   // 长度初始化为 0(开始顺序表内未存储元素_因此初始化长度为0)table.size = SIZE;  // 大小初始化为 SIZE (size为内存大小)return table;
}// 给所有元素初始值
// 参数: 表指针 (表以创建完成,只需向表中存储内容)
Table* SetTable(Table* ptable) {printf("向表内输入%d个整数:", ptable->size);// size_t类型产生:typedef unsigned int size_t;(非负整型变量)// "->" :指针取结构体子数据for (size_t i = 0; i < ptable->size; i++) // 遍历整个表{scanf("%d",&ptable->head[i]);   // 赋值并通过i增加不断偏移头指针ptable->length++;               // 每添加一个元素,顺序表长度增加一}return ptable;
}// 插入一个元素
// 参数:表指针,插入值,插入位置下标 
Table* addNum(Table* ptable, int num, int pos) {// 判断参数是否可以执行(插入位置超出范围)// 插入范围: pos(0 --- ptable->length)if (pos < 0 || pos >ptable->length) {printf("参数错误! 表中无法找到插入位置\n");return ptable;}// 能够插入// 判断是否有存储空间_如果存储空间不足则扩容if (ptable->length >= ptable->size) {printf("表指针内存不足! 开始扩容....\n");// 扩容:(动态内存扩容具体内容见往期文章_指针(三)动态内存)// 1. 记录原来的内存int* pTemp = ptable->head; // 只有head涉及内存,无需Table*只需使用int*即可// 2. 申请新的内存ptable->head = (int*)calloc(sizeof(int), ptable->size *= 2); // 以2倍方式扩容并更改size值// 判断扩容是否成功(内容与Table.c_16行代码类似)if (!ptable->head) {printf("动态内存申请失败! 未成功扩容_未添加元素");// 未成功扩容则把原来的内存恢复(不能丢弃)ptable->head = pTemp;return ptable;}// 3. 拷贝新的内存for (size_t i = 0; i < ptable->length; i++){ptable->head[i] = pTemp[i];}// 4. 释放原来的内存free(pTemp);// 5. 置空pTemp = NULL;   //防止变成野指针}// 插入:// 1.后移(先移动后面的元素)for (int i = ptable->length; i >= pos; i--){ptable->head[i + 1] = ptable->head[i];}// 2.插入ptable->head[pos] = num;// 3.更改长度ptable->length++;return ptable;
}// 输出所有元素值
// 参数: 表/表指针(此处用表作为参数_防止改变实参的值)
void displayTable(Table table) {printf("顺序表中存储的元素是:\n");for (size_t i = 0; i < table.length; i++){printf("%d ", table.head[i]);}printf("\ntable.size = %d , table.length = %d ;\n\n", table.size, table.length);
}// 删除元素 (按照下标删除 返回指针)
// 参数: 表指针,下标
Table* delNum(Table* ptable, int pos) {// 判断参数是否可以执行(删除位置超出范围)if (pos >= ptable->length || pos < 0) {printf("参数错误! 表中无法找到删除位置\n");return ptable;}// 删除for (int i = pos; i < ptable->length; i++){ptable->head[i] = ptable->head[i + 1];}// 改变长度ptable->length--;// 判断是否缩减大小if (ptable->length <= ptable->size / 2 && ptable->size % 2 == 0) {// 满足缩减条件printf("以满足内存缩减条件,正在重新分配内存...\n");// 缩减内存:// 1. 记录原来内存int* ptemp = ptable->head;// 2. 申请新的内存ptable->head = calloc(sizeof(int), ptable->size /= 2);// 判断缩减是否成功if (!ptable->head) {printf("动态内存申请失败! 未成功缩减");// 未成功缩减则把原来的内存恢复(不能丢弃)ptable->head = ptemp;return ptable;}// 3. 拷贝新的内存for (size_t i = 0; i < ptable->length; i++){ptable->head[i] = ptemp[i];}// 4. 释放原来的内存free(ptemp);// 5. 置空ptemp = NULL;}return ptable;
}// 查找元素 按数值查找(只返回找到的第一个) 返回下标
// 参数: 表,数值
int findWithNum(Table table, int num) {for (int i = 0; i < table.length; i++){if (num == table.head[i]) {return i;}}return -1; // 找不到返回-1 程序员查找代码规范!!
}// 更改元素 按照下标更改元素 返回指针
// 参数: 表指针 下标 值
Table* changeNum(Table* ptable, int pos, int num) {// 判断参数是否可以执行(更改位置超出范围)if (pos > ptable->length - 1 || pos < 0) {printf("参数错误! 表中无法找到修改位置_修改失败\n");return ptable;}ptable->head[pos] = num;return ptable;
}return ptable;
}// 查找元素 按数值查找(只返回找到的第一个) 返回下标
// 参数: 表,数值
int findWithNum(Table table, int num) {for (int i = 0; i < table.length; i++){if (num == table.head[i]) {return i;}}return -1; // 找不到返回-1 程序员查找代码规范!!
}// 更改元素 按照下标更改元素 返回指针
// 参数: 表指针 下标 值
Table* changeNum(Table* ptable, int pos, int num) {// 判断参数是否可以执行(更改位置超出范围)if (pos > ptable->length - 1 || pos < 0) {printf("参数错误! 表中无法找到修改位置_修改失败\n");return ptable;}ptable->head[pos] = num;return ptable;
}