去哪学做网站,深圳住房和建设局网站,哪里有市场营销培训班,网站搭建同一页不同按钮不同页面原文托管在Github: https://github.com/shellhub/blog/issues/52数据结构与算法之线性表-顺序表实现(C语言版本)前言数据结构与算法是一个程序员必备的技能之一,而顺序表更是每个程序员在面试过程中要经常被问到的#xff0c;如Java语言中的ArrayList类的底层实现就是使用顺序…原文托管在Github: https://github.com/shellhub/blog/issues/52数据结构与算法之线性表-顺序表实现(C语言版本)前言数据结构与算法是一个程序员必备的技能之一,而顺序表更是每个程序员在面试过程中要经常被问到的如Java语言中的ArrayList类的底层实现就是使用顺序表实现的,别把顺序表想的有多么高大上其实就是使用数组实现的一种线性表什么是线性表线性表英语Linear List是由nn≥0个数据元素结点a[0]a[1]a[2]…a[n-1]组成的有限序列。 其中 数据元素的个数n定义为表的长度 list.length() list.length() 0表里没有一个元素时称为空表 将非空的线性表n1记作a[0]a[1]a[2]…a[n-1] * 数据元素a[i]0≤i≤n-1只是个抽象符号其具体含义在不同情况下可以不同一个数据元素可以由若干个数据项组成。数据元素称为记录含有大量记录的线性表又称为文件。这种结构具有下列特点存在一个唯一的没有前驱的头数据元素存在一个唯一的没有后继的尾数据元素此外每一个数据元素均有一个直接前驱和一个直接后继数据元素。什么是顺序表顺序表是在计算机内存中以数组的形式保存的线性表是指用一组地址连续的存储单元依次存储数据元素的线性结构。顺序表的实现为了能实现顺序表的基本操作如(增删改查),我们使用结构体封装一个指向一维数组的指针base同时提供一个名字叫做length的整型变量表示顺序表中实际有用的元素个数,当插入一个元素时length, 当删除一个元素时length--,所以length可以记录当前顺序表的长度顺序表综合案列-学生信息管理系统#include stdio.h
#include stdbool.h
#include stdlib.h
#include assert.h#define INIT_SIZE 1
#define INCREMENT_SIZE 5
typedef struct {int id; //学号int age; //年龄char name[10]; //姓名
} Student;typedef Student ElemType;typedef struct {ElemType *base;int size; /* 顺序表的最大容量 */int length; /* 记录顺序表的元素个数 */
} SqList;/*** 初始化顺序表* param p 指向顺序表的指针* return 如果初始化成功返回true否则返回false*/
bool init(SqList *p) {p-base malloc(sizeof(SqList) * INIT_SIZE);if (p-base NULL) {return false;}p-size INIT_SIZE;p-length 0;return true;
}/*** 指定位置插入数据元素* param p 指向顺序表的指针* param index 插入的下标* param elem 插入的元素值* return 如果插入成功返回true否则返回false*/
bool insert(SqList *p, int index, ElemType elem) {if (index 0 || index p-length) {perror(插入下标不合法);return false;}//如果顺序表满了则重新分配更大的容量if (p-length p-size) {int newSize p-size INCREMENT_SIZE;ElemType *newBase realloc(p-base, newSize);if (newBase NULL) {perror(顺序表已满重新分配内存失败);return false;}p-base newBase;p-size newSize;}//从最后一个元素开始依次把元素复制到后面的位置for (int i p-length - 1; i index; --i) {p-base[i 1] p-base[i];}p-base[index] elem;p-length;return true;
}/*** 删除指定下标的数据元素* param p 指向顺序表的指针* param index 删除的元素的下标* param elem 返回删除的元素* return 如果删除成功返回true否则返回false*/
bool del(SqList *p, int index, ElemType *elem) {if (p-length 0) {perror(顺序是空的无法执行删除操作);return false;}if (index 0 || index p-length - 1) {perror(删除位置不合法);return false;}//把删除的元素保存起来*elem p-base[index];//从删除位置开始依次把后面的元素赋值到前面for (int i index; i p-length - 1; i) {p-base[i] p-base[i 1];}p-length--;return true;
}/*** 更新顺序表中特定的元素值* param p 指向顺序表的指针* param index 更新下标* param elem 更改后的新元素值* return 如果更改成功则返回true否则返回false*/
bool update(SqList *p, int index, ElemType elem) {if (p-length 0) {perror(顺序表是空的无法指向更新);return false;}if (index 0 || index p-length - 1) {perror(更新下标不合法);return false;}p-base[index] elem;return true;
}/*** 搜索顺序表中特定下标的元素* param list 指定的顺序表* param index 搜索的下标* param elem 保存搜索到的元素* return 如果搜索成功则返回true否则返回false*/
bool search(SqList list, int index, ElemType *elem) {if (list.length 0) {perror(顺序表没有任何元素无法查找);return 0;}if (index 0 || index list.length - 1) {perror(查找下标不合法);return false;}*elem list.base[index - 1];return true;
}/*** 打印顺序表* param list 指定顺序表*/
void output(SqList list) {printf(学号t年龄t姓名n);for (int i 0; i list.length; i) {printf(%dt%dt%sn, list.base[i].id, list.base[i].age, list.base[i].name);}printf(n);
}int main() {SqList list;while (1) {printf(tt顺序表的基本操作n);printf(tt1.初始化顺序表n);printf(tt2.顺序表的插入n);printf(tt3.顺序表的删除n);printf(tt4.顺序表的查找(下标)n);printf(tt5.顺序表的修改n);printf(tt6.打印n);printf(tt0.退出n);int choice;printf(请输入功能编号:);scanf(%d, choice);switch (choice) {case 1:if (init(list)) {printf(初始化成功n);}assert(list.length 0);break;case 2:;ElemType elem;printf(请输入插入的学生学号:);scanf(%d, elem.id);printf(请输入插入的学生年龄:);scanf(%d, elem.age);printf(请输入插入的学生姓名:);scanf(%s, elem.name);printf(请输入插入位置:);int index;scanf(%d, index);if (insert(list, index, elem)) {printf(插入成功n);}break;case 3:printf(请输入删除位置:);scanf(%d, index);if (del(list, index, elem)) {printf(删除的学生 学号:%dt年龄:%dt姓名:%sn, elem.id, elem.age, elem.name);}break;case 4:printf(请输入要查找的位置:);scanf(%d, index);if (search(list, index, elem)) {printf(查找的学生 学号:%dt年龄:%dt姓名:%sn, elem.id, elem.age, elem.name);}break;case 5:printf(请输入更新位置:);scanf(%d, index);printf(请输入更新后的学生学号:);scanf(%d, elem.id);printf(请输入更新后的学生年龄:);scanf(%d, elem.age);printf(请输入更新后的学生姓名:);scanf(%s, elem.name);if (update(list, index, elem)) {printf(更新成功n);}break;case 6:output(list);break;case 0:exit(0);default:printf(输入编号有误请重新输入n);break;}}return 0;
}顺序表优缺点优点因为顺序表使用数组实现可以通过下标存取所以存取速度极快T(n)O(1)无需为表中元素之间的逻辑关系而增加额外的存储空间空间利用效率高缺点插入删除均需要循环移动元素,比较浪费时间 T(n)O(n)需要提前预估顺序表的长度(INIT_SIZE),分配太大浪费造成内存的碎片化
