数据结构】顺序表的使用"/>
【C语言 数据结构】顺序表的使用
本文借鉴点击跳转
上一篇：线性表的简绍
文章目录
- 顺序表
- 什么是顺序表
- 顺序表的初始化
- 顺序表插入元素
- 顺序表删除元素
顺序表
什么是顺序表
顺序表又称顺序存储结构，是线性表的一种，专门存储逻辑关系为“一对一”的数据。
顺序表存储数据的具体实现方案是：将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。
举个简单的例子，将 {1,2,3,4,5} 这些数据使用顺序表存储，数据最终的存储状态如下图所示：
顺序表的初始化
使用顺序表存储数据，除了存储数据本身的值以外，通常还会记录以下两样数据：
- 顺序表的最大存储容量：顺序表最多可以存储的数据个数；
- 顺序表的长度：当前顺序表中存储的数据个数。
C 语言中，可以定义一个结构体来表示顺序表：
// TODO 定义结构体
typedef struct {ElemType *elem;int length;int listSize;
} SeqList;
尝试建立一个顺序表，例如：
//TODO 构造空的线性表L
void initList(SeqList *L) {L->elem = (ElemType *) malloc(LISTSIZE * sizeof(char));L->length = 0;L->listSize = LISTSIZE;
}
如上所示，整个建立顺序表的过程都封装在一个函数中，建好的顺序表可以存储 5 个逻辑关系为“一对一”的整数。
通常情况下，malloc() 函数都可以成功申请内存空间，当申请失败时，示例程序中进行了“输出失败信息和强制程序退出”的操作，您可以根据实际需要修改代码。
顺序表插入元素
向已有顺序表中插入数据元素，根据插入位置的不同，可分为以下 3 种情况：
-
插入到顺序表的表头；
-
在表的中间位置插入元素；
-
尾随顺序表中已有元素，作为顺序表中的最后一个元素；
虽然数据元素插入顺序表中的位置有所不同，但是都使用的是同一种方式去解决，即：通过遍历，找到数据元素要插入的位置，然后做如下两步工作：
- 将要插入位置元素以及后续的元素整体向后移动一个位置；
- 将元素放到腾出来的位置上；
例如，在 {1,2,3,4,5} 的第 3 个位置上插入元素 6，实现过程如下：
- 遍历至顺序表存储第 3 个数据元素的位置，如图1 所示：
- 将元素 3、4 和 5 整体向后移动一个位置，如图 2 所示：
- 将新元素 6 放入腾出的位置，如图 3 所示：
因此，顺序表插入数据元素的 C 语言实现代码如下：
// TODO 插入
void insertList(SeqList *L, int loc, char c) {//存储空间已满if (L->length >= L->listSize) {L->elem = (ElemType *) realloc(L->elem, (L->listSize + LISTINCREMENT) * sizeof(char));L->listSize += LISTINCREMENT;}for (int k = L->length; k > loc; k--) {L->elem[k] = L->elem[k - 1];}L->length++;L->elem[loc] = c;
}
顺序表删除元素
从顺序表中删除指定元素，实现起来非常简单，只需找到目标元素，并将其后续所有元素整体前移 1 个位置即可。
后续元素整体前移一个位置，会直接将目标元素删除，可间接实现删除元素的目的。
例如，从 {1,2,3,4,5} 中删除元素 3 的过程如图 4 所示：
因此，顺序表删除元素的 C 语言实现代码为：
// TODO 删除
void delList(SeqList *L, int loc) {for (int j = loc; j < L->length; j++) {L->elem[j - 1] = L->elem[j];}L->length--;
}
完整的代码如下所示
#include "stdio.h"
#include "windows.h"
#include "stdlib.h"// TODO 定义常量
#define LISTSIZE 10
#define LISTINCREMENT 2typedef char ElemType;// TODO 定义结构体
typedef struct {ElemType *elem;int length;int listSize;
} SeqList;//TODO 构造空的线性表L
void initList(SeqList *L) {L->elem = (ElemType *) malloc(LISTSIZE * sizeof(char));L->length = 0;L->listSize = LISTSIZE;
}// TODO 增加
void appendList(SeqList *L, char c) {L->elem[L->length++] = c;
}// TODO 插入
void insertList(SeqList *L, int loc, char c) {//存储空间已满if (L->length >= L->listSize) {L->elem = (ElemType *) realloc(L->elem, (L->listSize + LISTINCREMENT) * sizeof(char));L->listSize += LISTINCREMENT;}for (int k = L->length; k > loc; k--) {L->elem[k] = L->elem[k - 1];}L->length++;L->elem[loc] = c;
}// TODO 删除
void delList(SeqList *L, int loc) {for (int j = loc; j < L->length; j++) {L->elem[j - 1] = L->elem[j];}L->length--;
}
// TODO 打印
void printList(SeqList *L){for (int i = 0; i < L->length; ++i) {printf("%c",L->elem[i]);}printf("\n");
}
void combine(SeqList *a, SeqList *b, SeqList *c)
{int i=0, j=0, k=0;//同时扫描两个表while(i<a->length && j<b->length){if(a->elem[i]<=b->elem[j]){c->elem[k] = a->elem[i];i++;k++;}else{c->elem[k] = b->elem[j];j++;k++;}}//A表扫完，B组未扫完if(i==a->length){for(; j<b->length; j++){c->elem[k] = b->elem[j];k++;}}if(j==b->length){for(; i<a->length; i++){c->elem[k] = a->elem[i];k++;}}c->length=k;
}int main() {char a[] = "ajcniydu";SeqList list;// TODO 初始化顺序表initList(&list);printf("%d\n", list.length);for (int i = 0; i < strlen("ajcniydu"); i++) {appendList(&list, a[i]);}printList(&list);printf("%d\n", list.length);insertList(&list, 3, 'p');printList(&list);printf("%d\n", list.length);delList(&list, 3);printList(&list);printf("%d\n", list.length);SeqList aList;SeqList bList;SeqList cList;initList(&aList);initList(&bList);initList(&cList);char a1[] = {'1','3','5','7'};char a2[] = {'2','4','6'};for (int i = 0; i < 4; i++) {appendList(&aList, a1[i]);}for (int i = 0; i < 3; i++) {appendList(&bList, a2[i]);}combine(&aList,&bList,&cList);printList(&cList);return 0;
}
运行结果
0
ajcniydu
8
ajcpniydu
9
ajpniydu
8
1234567
更多推荐
【C语言 数据结构】顺序表的使用
发布评论