| 数据结构 | 您所在的位置：网站首页 › 链表线性结构和非线性结构的区别和联系 › 数据结构 |
数据结构
|
1 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表指的是在逻辑上是线性结构，也就是指连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。 数组的存储结构： 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。 顺序表一般可以分为： 1、静态顺序表：使用定长数组存储 2、动态顺序表：使用动态开辟的数组存储//顺序表的静态存储 #define N 100 typedef int SLDataType; typedef struct SeqList { SLDataType array[N]; size_t size; }SeqList; //顺序表的动态存储 #define N 100 typedef int SLDataType; typedef struct SeqList { SLDataType* array; //指向动态开辟的空间 size_t size; //有效元素的个数 size_t capacity; //动态申请的空间的大小，即容量空间的大小 }; 静态顺序表的存储示意图： 静态顺序表只适用于确定知道需要存多少个数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，所以现实开发中基本使用动态顺序表，根据需要动态的分配空间大小，所以，下面我们以实现动态顺序表为例。 2.2.1 头文件及顺序表的定义 #include #include typedef int SLDataType; typedef struct seqList { SLDataType* data; //指向动态开辟的空间 size_t size; //有效元素的个数 size_t capacity; //动态申请的空间的大小，即容量空间的大小 }seqList; 2.2.2 顺序表的初始化 void initSeqList(seqList* s1) { //初始化顺序表就是使开辟的数组长度和容量均为0 //使data指向的数组为空 s1->data = NULL; //是data指向为空 s1->size = 0; s1->capacity = 0; //有效数据和容量均为空 } 2.2.3 打印顺序表 void printSeqList(seqList* s1) { //打印顺序表就是依次将顺序表中元素打印出来 for (int i = 0; i size; i++) { printf("%d ", s1->data[i]); } printf("\n"); } 2.2.4 检查是否需要扩容 //检查容量是否足够不够则进行扩容 void checkCapacity(seqList* s1) { //1.检查参数是否合理 if (s1 == NULL) return; //2.如果有效元素个数和容量相同，则说明空间满了，需要扩容 //扩容时每次将容量增加为原来的两倍 if (s1->size == s1->capacity) { size_t newCapacity = s1->capacity == 0 ? 1 : 2 * s1->capacity; s1->data = (SLDataType*)realloc(s1->data, sizeof(SLDataType) * newCapacity); //3.更新数据 s1->capacity = newCapacity; } } 2.2.5 尾插一个数据 void pushBack(seqList* s1, SLDataType val) { //1.检查参数是否合理 if (s1 == NULL) return; //2.检查是否需要扩容 checkCapacity(s1); //3.进行尾插 s1->data[s1->size] = val; s1->size++; } 2.2.6 尾删一个数据 //尾删一个数据 void popBack(seqList* s1) { //1.检查参数是否合理 if (s1 == NULL || s1->size == 0) return; //2.删除最后一个数据，只需是有效元素个数减一 s1->size--; } 2.2.7 头插一个数据 //头插一个数据 void pushFront(seqList* s1, SLDataType val) { //1.检查参数是否合理 if (s1 == NULL) return; //2.检查是否需要扩容 checkCapacity(s1); //3.从后先前逐个移动元素，空出第0个位置 for (int idx = s1->size - 1; idx >= 0; idx--) { s1->data[idx + 1] = s1->data[idx]; } //4.插入数据 s1->data[0] = val; s1->size++; } 2.2.8 头删一个数据 //头删一个数据 void popFront(seqList* s1) { //1.检查参数是否合理 if (s1 == NULL || s1->size == 0) return; //2.从前往后逐次向前移动，空出有效元素的最后一位 for (int idx = 1; idx size; idx++) { s1->data[idx - 1] = s1->data[idx]; } //3.删除元素 s1->size--; } 2.2.9 任意一个位置插入一个数据 //任意一个位置插入一个数据 void insert(seqList* s1, int pos , SLDataType val) { //1.检查参数是否合理 if (s1 == NULL) return; //2.插入位置合理后进行数据的插入 //有效插入位置[0,size] if (pos >= 0 && pos size) { //3.检查容量 checkCapacity(s1); //4.移动元素[pos,size),从后向前依次向后移动 for (int idx = s1->size-1; idx >= pos; idx--) { s1->data[idx + 1] = s1->data[idx]; } //5.插入元素 s1->data[pos] = val; s1->size++; } } 2.2.10 任意一个位置删除一个数据 //任意一个位置删除一个数据 void erase(seqList* s1, int pos) { //1.检查参数是否合理 if (s1 == NULL || s1->size == 0) return; //2.删除位置合理后进行删除 //合理位置[0,size) if (pos >= 0 && pos size) { //3.移动元素[pos+1,size), //从前向后移动，每个元素向前移动 for (int idx = pos + 1; idx size; idx++) { s1->data[idx - 1] = s1->data[idx]; } //4.删除元素 s1->size--; } } 2.2.11 判断顺序表是否为空表 int empty(seqList* s1) { if (s1 == NULL || s1->size == 0) return 1; else return 0; } 2.2.12 计算顺序表的长度 //计算顺序表的长度 int size(seqList* s1) { if (s1 == NULL || s1->size == 0) return 0; else return s1->size; } 2.2.13 根据数据查找在数组中的索引 int findIdx(seqList* s1, SLDataType val) { if (s1 == NULL || s1->size == 0) return -1; //遍历整个数组[0,size)查找每一个元素 for (int idx = 0; idx size; idx++) { if (s1->data[idx] == val) return idx; } return -1; } 2.2.14 根据索引查找数据 int getIdx(seqList* s1, int pos) { //这里要求数均为合理参数 return s1->data[pos]; } 2.2.15 销毁顺序表 void destroySeqList(seqList* s1) { if (s1) { if (s1->data) { free(s1->data); s1->data = NULL; s1->size = 0; s1->capacity = 0; } } } 2.3 验证顺序表的接口 int main() { seqList s; initSeqList(&s);//初始化顺序表 pushBack(&s, 1);//在尾部插入数字1 //顺序表为[1] printSeqList(&s);//打印顺序表 pushBack(&s, 2);//尾插数字2 //顺序表为[1 2] printSeqList(&s);//打印顺序表 pushFront(&s, 0);//头插数字0 //顺序表为[0 1 2] printSeqList(&s);//打印顺序表 insert(&s, 1, 11);//在位置1插入数字11 //顺序表为[0 11 1 2] printSeqList(&s);//打印顺序表 insert(&s, 0, 12);//在位置0插入数字12，相当于头插 //顺序表为[12 0 11 1 2] printSeqList(&s);//打印顺序表 insert(&s, s.size,13);//在最后位置插入数字13，相当于尾插 //顺序表为[12 0 11 1 2 13] printSeqList(&s);//打印顺序表 printf("顺序表是否为空：%d\n", empty(&s)); //结果为0 printf("顺序表的长度为：%d\n", size(&s));//结果为6 printf("数字13在顺序表中的索引：%d\n", findIdx(&s, 13));//结果为5 printf("索引为3的数据为:%d\n", getIdx(&s, 3));//结果为1 popBack(&s);//尾删一个数据 //顺序表为[12 0 11 1 2] printSeqList(&s);//打印顺序表 popFront(&s);//头删一个数据 //顺序表为[0 11 1 2] printSeqList(&s);//打印顺序表 erase(&s, 1);//删除位置1上的元素 //顺序表为[0 1 2] printSeqList(&s);//打印顺序表 erase(&s, 0);//删除0号位置的元素，相当于头删 //顺序表为[1 2] printSeqList(&s);//打印顺序表 destroySeqList(&s); printSeqList(&s);//打印顺序表 }运行结果如下图： .c文件中所要声明的头文件如下： #include #include #include"seq.h" |
链表的存储结构： 
动态表的存储示意图： 
【本文地址】
公司简介
联系我们