线性表之顺序存储结构实现

一，线性表的概念以及数学定义1.线性表的概念 零个或多个数据元素的有限序列。首先说明这是一个序列，也就是说数据元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且仅有一个前驱和后继。2.数学定义 若将线性表记为（a₁...a_i-1,a_i,a_i+1....a_n），则线性表中，a_i-1领先于a_i，a_i领先于a_i+1，则称a_i-1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素，当i=1,2....n-1的时候，a_i有且仅有一个直接后继元素，当i=2,3...n的时候，a_i有且仅有一个直接前驱元素。二，线性表的顺序存储结构1.顺序存储结构的概念 线性表的顺序存储结构，指的是利用一段地址连续的存储单元依次存储线性表的数据元素。 2.顺序存储方式的实现 我们利用数组这个数据类型，来表示一段地址连续的存储单元。三，线性表之顺序存储结构的的实现1.线性表基本功能： 1.创建线性表 ==> List * createList（int capacity）; 2.销毁线性表 ==> void destoryList（List * list）; 3.清空线性表 ==> void clearList（List * list）; 4.获取线性表长度 ==> int length（List * list）; 5.获取线性表容量 ==> int capacity（List * list）; 6.线性表的插入 ==> void insert（List * list,int pos,Node * node）; 7.线性表的删除 ==> Node * delete（List * list,int pos）; 8.线性表的修改 ==> Node * update（List * list,int pos,Node * node）; 9.线性表的获取 ==> Node * get（List * list,int pos）;2.线性表基本功能的代码实现：# include<stdio.h># include<stdlib.h># include<string.h>typedef void Node;typedef struct SeqList{int capacity;int length;int * array;}List;/* 创建指定容量大小的线性表 */List * createList（int capacity）{// 在堆上分配线性表对象List * list = （List *）malloc（sizeof（List））;// 初始化线性表对象的容量list->capacity = capacity;// 初始化线性表当前长度list->length = 0;// 初始化线性表的数组list->array = malloc（capacity*sizeof（void *））;// 返回线性表return list;}/* 销毁线性表 */void destoryList（List * list）{if （list ！= NULL）{if （list->array ！= NULL）{// 释放线性表中的数组free（list->array）;list->array = NULL;}// 释放线性表对象free（list）;list = NULL;}}/* 清空线性表 */void clearList（List * list）{if （list ！= NULL）{// 线性表的数组清空memset（list->array, 0, sizeof（list->array）/list->capacity）;// 线性表的长度清空list->length = 0;}}/* 线性表的长度 */int length（List * list）{return list->length;}/* 线性表的容量 */int capacity（List * list）{return list->capacity;}/* 线性表的插入 */void insert（List * list, int pos, Node * node）{if （list == NULL）{printf（"线性表为NULL "）;return;}if （pos > list->capacity）{printf（"插入位置超过线性表的容量 "）;return;}if （list->length > list->capacity）{printf（"线性表容量已满,无法插入 "）;return;}// 容错机制 6个长度，容量20，插入10，则自动插入到7这个位置if （pos>list->length）{list->array[list->length] = node;// 线性表长度加一list->length++;return;}// 移动pos之后的数据for （int i = list->length; i > pos-1; i--）{list->array[i] = list->array[i-1];}// 插入数据list->array[pos - 1] = node;// 线性表长度加一list->length++;}/* 线性表的删除 */Node * delete（List * list, int pos）{if （list == NULL）{printf（"线性表为NULL "）;return NULL;}if （pos > list->length）{printf（"删除位置不存在 "）;return NULL;}// 返回的元素Node * node = list->array[pos - 1];;// 删除元素后线性表长度减一list->length--;// 删除最后一个if （pos == list->length）{list->array[pos - 1] = NULL;return node;}// 删除for （int i = pos - 1; i < list->length; i++）{list->array[i] = list->array[i + 1];}return node;}/* 线性表的修改 */Node * update（List * list, int pos, Node * node）{if （list == NULL）{printf（"线性表为NULL "）;return NULL;}// 返回修改前的对象Node * result = list->array[pos - 1];// 修改list->array[pos - 1] = node;return result;}/* 线性表的获取 */Node * get（List * list, int pos）{if （list == NULL）{printf（"线性表为NULL "）;return NULL;}return list->array[pos - 1];} 3.测试程序实现/* 测试程序 */typedef struct Student{char name[64];int age;}Student;int main（）{// 创建线性表List * list = createList（20）;// 创建学生对象并初始化Student s1 = { "刘备",42 };Student s2 = { "关羽",38 };Student s3 = { "张飞",32 };Student s4 = { "赵云",36 };Student s5 = { "马超",26 };Student s6 = { "黄忠",59 };// 头插法插入insert（list, 1, &s1）;insert（list, 2, &s2）;insert（list, 3, &s3）;insert（list, 4, &s4）;insert（list, 5, &s5）;insert（list, 19, &s6）;// 获取长度printf（"############线性表长度############ "）;printf（"length = %d ", length（list））;// 获取容量printf（"############线性表容量############ "）;printf（"capacity = %d ", capacity（list））;// 遍历printf（"############线性表遍历############ "）;for （int i = 1; i <= length（list）; i++）{Student * s = get（list, i）;printf（"name = %s,age = %d ", s->name, s->age）;}// 删除第一个元素delete（list, 3）;printf（"############删除第三个元素############ "）;// 遍历for （int i = 1; i <= length（list）; i++）{Student * s = get（list, i）;printf（"name = %s,age = %d ", s->name, s->age）;}// 修改第一个元素printf（"############修改第一个元素############ "）;Student sss = { "刘备-汉中王",50 };update（list, 1, &sss）;// 遍历for （int i = 1; i <= length（list）; i++）{Student * s = get（list, i）;printf（"name = %s,age = %d ", s->name, s->age）;}// 清空线性表printf（"############清空线性表############ "）;clearList（list）;// 遍历for （int i = 1; i <= length（list）; i++）{Student * s = get（list, i）;printf（"name = %s,age = %d ", s->name, s->age）;}// 销毁线性表printf（"############销毁线性表############ "）;destoryList（list）;return 0;} 四，线性表顺序存储结构的总结1.顺序存储结构的优点 1.无需为线性表中的逻辑关系增加额外的空间。 2.可以快速获取线性表中合法位置的数据元素。2.顺序存储结构的缺点 1.插入和删除操作需要移动大量元素。 2.当线性表长度变化较大时难以确定存储空间的容量。3.总结 线性表顺序存储结构适用于查询多，增删少，数据长度变化小的场景。更多详情见请继续阅读下一页的精彩内容： http://www.linuxidc.com/Linux/2017-01/139260p2.htm