本文共 8105 字，大约阅读时间需要 27 分钟。
上一篇文章，实现了静态顺序表的基本操作，不难发现静态顺序表有诸多缺陷，首先，进程中，需要开辟一大块空间供动态顺序表存储数据用，如果存储的数据不多（结点不多），会浪费很多内存；如果开辟空间比较少，而存储数据较多，又会存在数据存不下的情况，这都不是我们想要的，建立在这样的基础上，动态顺序表的就出现了，先来看一下动态顺序表的结构体：
typedef int DataType;#define INIT_SIZE 10typedef struct SeqList{ DataType* _array; //数据块指针 size_t _size; //顺序表有效元素个数 size_t _capicity; //顺序表容量}SeqListD;typedef SeqListD* PSeqListD; 这里的数据块指针是数据在内存中存储的首地址，就像数组的地址一样。
实现基于动态数组的顺序表的以下基本操作：
具体代码实现如下：
#pragma once #include#include #include #include #include //动态顺序表的定义typedef int DataType;#define INIT_SIZE 10typedef struct SeqList{ DataType* _array; size_t _size; //顺序表有效元素个数 size_t _capicity; //顺序表容量}SeqListD;typedef SeqListD* PSeqListD;/****************************************///动态顺序表初始化void SeqListDInit(PSeqListD pSeq);//动态顺序表的尾插void SqListDPushBack(PSeqListD pSeq, DataType data);//动态顺序表尾删void SeqListDPopBack(PSeqListD pSeq);//动态顺序表的头插void SeqListDPushFront(PSeqListD pSeq,DataType data);//动态顺序表的头删void SeqListDPopFront(PSeqListD pSeq);//顺序表判空int SeqListDEmpty(PSeqListD pSeq);//获取顺序表中有效元素的个数 int SeqListDSize(PSeqListD pSeq);//获取顺序表的容量 int SeqListDCapacity(PSeqListD pSeq);// 清空顺序表中的所有元素 注意：不改变顺序表空间的大小 void SeqListDClear(PSeqListD pSeq);// 动态增容 void CheckCapacity(PSeqListD pSeq);// 销毁顺序表 void SeqListDDestroy(PSeqListD pSeq);// 顺序表任意位置插入元素 void SeqListDInsert(PSeqListD pSeq, DataType pos, DataType data);// 顺序表任意位置删除元素 void SeqListDErase(PSeqListD pSeq, DataType pos);//打印动态顺序表void SeqListDPrint(PSeqListD pSeq);//在动态顺序表中查找元素data，找到返回下标，找不到返回-1int Find(PSeqListD ps, DataType data);//顺序表遍历void PrintSeqListD(PSeqListD ps);//冒泡排序，升序和降序两种版本，用了函数指针void BubbleSort(PSeqListD ps, int(*cmp)(const void *elem1, const void *elem2));//选择排序，升序和降序两种版本，用了函数指针void SelectSort(PSeqListD ps, int(*cmp)(const void *elem1, const void *elem2));//升序比较int CmpInAscendingOrder(const void *elem1, const void *elem2);//降序比较int CmpInDescendingOrder(const void *elem1, const void *elem2);//二分查找 int BinarySearch(PSeqListD ps, DataType data);/****************************************///动态顺序表初始化void SeqListDInit(PSeqListD pSeq){ assert(pSeq); pSeq->_array = (DataType*)malloc(sizeof(DataType)*INIT_SIZE); if (pSeq->_array == 0) { printf("申请失败！\n"); return ; } pSeq->_size = 0; pSeq->_capicity = INIT_SIZE;}//检查当前动态顺序表容量，不够，则申请空间void CheckCapacity(PSeqListD pSeq){ assert(pSeq); if (pSeq->_size >= pSeq->_capicity) { DataType *p = (DataType*)realloc(pSeq->_array, 2 * (pSeq->_capicity)*sizeof(DataType)); if (p == NULL) { printf("内存申请失败1\n"); return; } else { pSeq->_array = p; pSeq->_capicity = 2 * pSeq->_capicity; } }}//打印动态顺序表void SeqListDPrint(PSeqListD pSeq){ assert(pSeq); for (size_t i = 0; i < pSeq->_size; i++) { printf("%d", pSeq->_array[i]); } printf("\n");}//动态顺序表的尾插void SeqListDPushBack(PSeqListD pSeq, DataType data){ assert(pSeq); CheckCapacity(pSeq); pSeq->_array[pSeq->_size] = data; pSeq->_size++; printf("插入成功！\n");}//动态顺序表尾删void SeqListDPopBack(PSeqListD pSeq){ assert(pSeq); if (pSeq->_size == 0) { printf("顺序表为空，无法删除！\n"); return; } pSeq->_size--;}//动态顺序表的头插void SeqListDPushFront(PSeqListD pSeq, DataType data){ assert(pSeq); CheckCapacity(pSeq); for (int i = pSeq->_size; i > 0;i--) { pSeq->_array[i] = pSeq->_array[i - 1]; } pSeq->_array[0] = data; pSeq->_size++;}//动态顺序表的头删void SeqListDPopFront(PSeqListD pSeq){ assert(pSeq); if (pSeq->_size == 0) { printf("顺序表为空，无法删除！\n"); return; } for (int i = 0; i < pSeq->_size; i++) { pSeq->_array[i] = pSeq->_array[i + 1]; } pSeq->_size--;}//顺序表判空，为空返回true，否则返回false int SeqListDEmpty(PSeqListD pSeq){ assert(pSeq); if (pSeq->_size == 0) { printf("顺序表为空！\n"); } printf("顺序表不为空，顺序表共有%d个元素\n", pSeq->_size); return pSeq->_size;}// 顺序表任意位置插入元素 void SeqListDInsert(PSeqListD pSeq, DataType pos, DataType data){ assert(pSeq); CheckCapacity(pSeq); for (int i = pSeq->_size; i > pos; i--) { pSeq->_array[i] = pSeq->_array[i - 1]; } pSeq->_array[pos] = data; pSeq->_size++;}// 顺序表任意位置删除元素 void SeqListDErase(PSeqListD pSeq, DataType pos){ assert(pSeq); if (pos <= 0 || pos >= pSeq->_size) { printf("输入为止不合法！越界！\n"); return; } for (int i = pos; i < pSeq->_size-1; i++) { pSeq->_array[i] = pSeq->_array[i + 1]; } pSeq->_size--;}//获取顺序表中有效元素的个数 int SeqListDSize(PSeqListD pSeq){ assert(pSeq); return pSeq->_size;}//获取顺序表的容量 int SeqListDCapacity(PSeqListD pSeq){ assert(pSeq); return pSeq->_capicity;}// 清空顺序表中的所有元素 注意：不改变顺序表空间的大小 void SeqListDClear(PSeqListD pSeq){ assert(pSeq); pSeq->_size =0;}// 销毁顺序表 void SeqListDDestroy(PSeqListD pSeq){ assert(pSeq); free(pSeq->_array); pSeq->_array = NULL; pSeq->_capicity = 0; pSeq->_size = 0;}//在动态顺序表中查找元素data，找到返回下标，找不到返回-1int Find(PSeqListD pSeq, DataType data){ assert(pSeq); if (pSeq->_size == 0) { printf("顺序表为空！\n"); } for (int i = 0; i < pSeq->_size; i++) { if (pSeq->_array[i] == data) return i; } return -1;}//顺序表遍历void PrintSeqListD(PSeqListD pSeq){ assert(pSeq); for (int i = 0; i < pSeq->_size; i++) { printf("顺序表中的全部元素：%d\n", pSeq->_array[i]); }}//升序比较int CmpInAscendingOrder(const void *elem1, const void *elem2){ return *(int*)elem1 - *(int*)elem2;}//降序比较int CmpInDescendingOrder(const void *elem1, const void *elem2){ return *(int*)elem2 - *(int*)elem1;}//冒泡排序，升序和降序两种版本，用了函数指针void BubbleSort(PSeqListD pSeq, int(*cmp)(const void *elem1, const void *elem2)){ int i = 0; int j = 0; // 设置一个标签，如果一次循环中flag值始终没改变 //证明数组内元素已经有序 int flag = 0; //参数检验 assert(pSeq); for (i; i < pSeq->_size - 1; i++) { flag = 0;// 把flag重置为0，方便下一次循环里有没有交换元素 for (j; j < pSeq->_size - 1 - i; j++) { if (cmp(&pSeq->_array[j], &pSeq->_array[j + 1]) > 0) { int tmp = pSeq->_array[j]; pSeq->_array[j] = pSeq->_array[j + 1]; pSeq->_array[j + 1] = tmp; flag = 1; } } if (flag == 0) break; }}//选择排序，升序和降序两种版本，用了函数指针void SelectSort(PSeqListD pSeq, int(*cmp)(const void *elem1, const void *elem2)){ int i = 0; int j = 0; int pos = 0; assert(pSeq); for (i; i < pSeq->_size -1; i++) { pos = i; for (j = i + 1; j _size; j++) { if (cmp(&pSeq->_array[j], &pSeq->_array[pos]) < 0) { pos = j; } } if (i != pos) { int tmp = pSeq->_array[i]; pSeq->_array[i] = pSeq->_array[pos]; pSeq->_array[pos] = tmp; } }}//二分查找 int BinarySearch(PSeqListD pSeq, DataType data){ int left = 0; int right = 0; int mid = 0; assert(pSeq); right = pSeq->_size - 1; while (left <= right) { if (pSeq->_array[mid] > data) right = mid - 1; else if (pSeq->_array[mid] < data) left = mid + 1; else return mid; } return -1;}/****************************************///测试部分void SeqListDTest(){ SeqListD p; SeqListDInit(&p); SeqListDPushBack(&p, 1); SeqListDPushBack(&p, 2); SeqListDPushBack(&p, 3); SeqListDPushBack(&p, 4); SeqListDPrint(&p); SeqListDPopBack(&p); SeqListDPrint(&p); SeqListDPushFront(&p, 4); SeqListDPushFront(&p, 5); SeqListDPrint(&p); SeqListDPopFront(&p); SeqListDPrint(&p); SeqListDEmpty(&p); SeqListDInsert(&p, 2, 6); SeqListDPrint(&p); SeqListDErase(&p, 2); SeqListDPrint(&p); BinarySearch(&p, 3);}
在上两篇文章中，我们完成的静态顺序表以及动态顺序表的基本操作实现，现在我们来总结一下顺序表的整体内容。
原理：
顺序表存储是将数据元素放到一块连续的内存存储空间，存取效率高，速度快。但是不可以动态增加长度优点：
1.尾插效率高，便于随机访问 2.cpu缓存利用率高 3.存取速度高效，通过下标来直接存储缺点：
1.不利于插入和删除操作 2.不可以增长长度比如：插入或者删除一个元素时，整个表需要遍历移动元素来重新排一次顺序
适用场景：
1.频繁的查找却很少的插入和删除操作 2.在进行尾插的时候用顺序表，因为相对于链表来说，顺序表进行尾插不需要进行遍历来找到最后一个位置，而链表则需要遍历。这样会影响程序运行的效率。转载地址：http://stuoi.baihongyu.com/