前言
这是C语言数据结构中最简单的顺序表,需要有指针和结构体的基础,这篇文章会尽可能以我的理解再配上一些较为官方的解释来使看这篇文章的人能够理解顺序表。
写这篇文章也是因为我在学校学习C语言数据结构的时候,因为较长时间没有敲过C语言了,所以前一两节课听着有点懵圈。
介绍
按照百度百科的解释,顺序表就是在计算机内存中以数组的形式保存的线性表,并且顺序表是采用顺序存储结构的线性表。
那么什么是线性表呢?我在之前的文章中讲过,不懂的可以去看一看。
或者这么说,线性表的顺序存储结构又称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。
举例说明
假设我们有一个班级,该班级中有n名学生,每个学生都有唯一的学号。如果我们按照学号的升序对学生进行排序,并将排序后的学生信息存储在一个顺序表中,那么可以想象这个顺序表是一个数组。在这个数组中,学号最小的学生将位于数组的第一个位置(即索引0),学号第二小的学生紧随其后,依此类推,直到最后一个学生。
物理位置与逻辑位置的关系
在这样的顺序表中,如果我们要找到某个特定学号的学生,我们可以直接计算出该学生在数组中的索引位置,而不需要从头开始逐个比较。比如,如果数组的第一个元素(索引0)对应学号为1的学生,那么学号为k的学生将会出现在数组的第(k-1)个位置(因为数组索引是从0开始的)。
附一个图片解释
假设线性表最大为Maxsize,起始位置为LOC(A),sizeof(ElemType)为单个元素所占用的内存大小,顺序表a1,a2便是学号为1的学生和学号为2的学生,学生对应的内存地址即为连续的LOC(A),LOC(A)+sizeof(ElemType)。
顺序表的存储结构
假定线性表的数据类型为ElemType,则线性表的存储类型描述如下:
#define Maxsize 50 //线性表最大长度
typedef struct{
ElemType elem[Maxsize]; //顺序表的元素
int length; //顺序表当前长度
}SqList; //顺序表的定义类型
其中ElemType数据类型是为了描述统一而自定的,在实际应用中,用户可以根据实际需要具体定义表中的数据类型,既可以是基本数据类型,如int、float、char等,也可以是构造数据类型,如struct结构体类型。
这里举一个结构体类型的例子
typedef struct {
char no[50];//书的标号
char title[50];//书的书名
float price;//书的价格
}Book;
这里我定义了一个图书的结构体,里面包含了书的标号,书的书名以及书的价格,接下来要描述顺序表则是:
#define Maxsize 50 //线性表最大长度
typedef struct {
Book elem[Maxsize];//顺序表的元素
int length;//当前图书数量
}SqList;
这相当于是把图书这个结构体整体的放入了“数组”之中,具体如图所示。
在这个图中可以看得出来顺序表就是数组,其中的a1,a2......都是数组里面的数据元素,因为我定义的数据类型是结构体类型Book,相当于把结构体存储到数组之中,所以数组中的每个数据元素相当于结构体Book,有我定义的“标号、书名、价格”这些信息。
数组可以是静态分配的,也可以是动态分配的。在静态分配时,由于数组的大小和空间事先已经固定.一旦空间占满,再加入新的数据就会产生溢出,进而导致程序崩溃。
#define Maxsize 50 //线性表最大长度
typedef struct{
ElemType elem[Maxsize]; //顺序表的元素
int length; //顺序表当前长度
}SqList; //顺序表的定义类型
在上面的描述中,我使用的是静态分配,因为数组 elem 的大小由预处理宏 Maxsize
定义,默认为 50,这意味着 elem 能够存储的最大元素数量是固定的,不会随着实际存储数据的变化而动态调整。
而在动态分配时,存储数组的空间是在程序执行过程中通过动态存储分配语句分配的,一旦数据空间占满,就另外开辟一块更大的存储空间,用以替换原来的存储空间,从而达到扩充存储数组空画的目的,而不需要为线性表一次性地划分所有空间。
#define InitSize 100 //线性表的初始长度
typedef struct{
ElemType *elem; //存储空间的基地址
int MaxSize,length; //顺序表当前最大容量和长度
}SqList; //顺序表的定义
这里补充一下,基地址指的是这些数据结构在内存中的起始位置。对于数组来说,第一个元素的地址就是数组的基地址。
C语言的动态分配内存
L.elem = (ElemType*)malloc(sizeof(ElemType)*InitSize);
malloc(sizeof(ElemType) * InitSize)
这部分会请求操作系统分配一段连续的内存空间,其大小为InitSize
个ElemType
类型的数据所占的字节数。(ElemType*)
是类型转换,确保返回的指针类型是ElemType
类型的指针。L.elem = ...
将分配得到的内存地址赋值给L
.elem
成员。
C++动态分配内存
L.elem = new ElemType[InitSize];
注意:动态分配并不是链式存储、它同样居于顺序存储结构,物理结构没有变化,依然是随机存取方式,只是分配的空间大小可以在运行时动态决定。
顺序表的特点
- 连续存储: 顺序表中的所有元素都存储在一个连续的内存区域中。这意味着可以通过计算偏移量快速访问任何元素,从而实现随机访问。
- 随机访问: 由于元素是连续存储的,可以使用索引快速访问任何一个元素。时间复杂度为 O(1),即常数时间复杂度。
- 固定大小: 一旦创建,顺序表的大小通常是固定的(除非使用动态数组)。如果需要存储的数据量超过预定的大小,就需要重新分配一块更大的内存区域,并复制原有数据过去。
- 插入和删除操作的成本: 插入和删除操作通常比较耗时,尤其是当插入或删除发生在中间位置时。为了保持元素的连续存储特性,可能需要移动大量的元素。最坏情况下,插入或删除操作的时间复杂度为 O(n),其中 n 是表中的元素数量。
- 易于实现: 顺序表基于数组实现,所以其实现相对简单。数组本身就是大多数编程语言提供的基本数据类型之一。
- 空间利用率: 由于顺序表的大小是固定的,所以在某些情况下可能会存在空间浪费。例如,如果预先分配的空间大于实际使用的空间,就会造成内存空间的浪费。
- 内存管理: 顺序表可以使用静态数组实现,也可以使用动态内存分配来实现。静态数组的大小在编译时确定,而动态数组允许在运行时根据需要调整大小。
- 辅助操作简单: 获取顺序表的长度、判断是否为空等操作都非常简单,通常只需要读取记录当前元素数量的变量即可。
顺序表的基本操作
初始化顺序表
算法步骤:
①为顺序表L动态分配一个预定大小的数组空间,使elem指向这段空间的基地址。
②将表的当前长度设为0。
int InitList(SqList& L) { //L本身要发生改变,所以用引用型
L.elem = new ElemType[100];
if (L.elem == NULL) {
return ERROR;
}
L.length = 0;
return OK;
}
动态分配线性表的存储区域可以更有效地利用系统的资源,当不需要该线性表时,可以使用销毁操作及时释放占用的存储空间。
顺序表的取值
算法步骤
①判断指定的位置序号 i 值是否合理(1≤i≤L.length),若不合理,则返回ERROR。
②若 i 值合理,则将第 i 个数据元素L.length[i-1]赋给参数 e ,通过e返回第 i 个数据元素的传值。
int GetElem(SqList L, int i, ElemType& e) {
if (i<1 || i>L.length) {
return ERROR;
}
e = L.elem[i - 1];
return OK;
}
顺序表的取值算法的时间复杂度为O(1)。
顺序表的查找
算法步骤
①从第一个元素起,依次将其值和e相比较,若找到值与e相等的元素L.elem[i],则查找成功,返回该元素的序号i+1。
②若查找整个顺序表都没有找到,则查找失败,返回0。
int LocateElem(SqList L, ElemType e){
for(int i=0;i<L.length;i++){
if(e==L.elem[i])
return i+1; //找到返回下标
}
return 0; //没找到返回0
}
当在顺序表中查找一个数据元素时, 其时间主要耗费在数据的比较上, 而比较的次数取于被查元素在线性表中的位置。
在查找时, 为确定元素在顺序表中的位置, 需和给定值进行比较的数据元素个数的期望称为查找算法在查找成功时的平均查找长度 ( Average Search Length, ASL)。
假设pi ,(pi=1/n)是查找的元素在第i (1<=i<=L.length)个位置上的概率,则在长度为n的线性表中查找值为e的元素所需比较的平均次数为(n+1)/2,因此,线性表按值查找算法的平均时间复杂度为O(n)。
最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为O(1)。
最坏情况:查找的元素在表尾(或不存在)时,需要比较n次,时间复杂度为O(n)。
顺序表的插入
算法步骤
①判断插入位置i是否合法(i值得合法范围使1≤i≤n+1),若不合法返回ERROR。
②判断顺序表得存储空间是否已满,若满则返回ERROR。
③将第n个至第i个位置的元素依次向后移动一个位置,空出第i个位置(i=n+1时无须移动)。
④将要插入的新元素e放入第i个位置。
⑤表长加1。
int InsertElem(SqList &L,int pos,ElemType &e){
if(pos<1||pos>L.length+1){
return ERROR;
}
if(L.length>MAXSIZE){
return ERROR;
}
for(i=L.length;i>=pos;i--){
L.elem[i]=L.elem[i-1];
}
L.elem[pos-1]=e;
L.length++;
return OK;
}
这里解释一下为什么要将元素依次向后移动一个位置之后再插入元素。
在顺序表中插入一个新元素时,需要移动元素的原因是为了给新元素腾出空间。这是因为顺序表是基于数组实现的,数组中的元素是连续存储的。如果要插入的新元素不是在数组的末尾,那么插入操作会破坏元素的连续性,因此需要将插入点之后的元素向后移动,以保持数组中元素的连续性。
简单的解释就是如果直接插入就会把原来位置的元素给覆盖了。并且移动元素的时候要从最后一个元素开始移动,否则元素也会被覆盖。
这里放一个图来直观的解释一下:
最好情况:在表尾插入(即 i= n+1),元素后移语句将不执行,时间复杂度为O(1) 。
最坏情况:在表头插入(即i= 1),元素后移语句将执行n次,时间复杂度为O(n)。
平均情况:假设pi(pi = 1/(n1+ 1))是在第个位置上插入一个结点的概率,则在长度为n的线性表中插入一个结点时,所需移动结点的平均次数为n/2。因此,线性表插入算法的平均时间复杂度为O(n)。
顺序表的删除
算法步骤
①判断删除位置 i 是否合法(合法值为 1≤i≤n),若不合法则返回ERROR。
②将第i+1个至第n个元素依次向前移动一个位置(i=n时无须移动)。
③表长减1。
bool ListDelete(SqList &L,int i){
if(i<1||i>L.length) //判断i是否在合法范围
return ERROR;
for(int j=i;j<=L.length-1;j++) //从第i个位置开始从后往前移动
L.elem[j-1]=L,elem[j];
L.length--; //线性表长度减1
rerurn OK;
}
要删除表中下标为p的元素,只需将其后边的元素逐个往前移动一个位置,将p位置上的元素覆盖 掉,就达到了删除的目的。
顺序表的清空
void ClearList(SqList &L) {
free(L.elem);
L.elem = NULL; // 或者使用nullptr
L.length = 0;
L.capacity = 0;
}
顺序表的遍历
遍历顺序表中的每一个元素,通常用于打印或其他操作。
void Traverse(SqList &L) {
for (int i = 0; i < L.length; ++i) {
printf("%d ", L.elem[i]);
}
printf("\n");
}
时间复杂度:o(n)
顺序表访问元素
访问顺序表中的指定位置的元素。
ElemType get(SqList &L, int index) {
if (index >= 0 && index < L.length) {
return L.elem[index];
}
// 返回错误标志或抛出异常
return ERROR;
}
顺序表赋值
为顺序表加入元素
void Assign(SqList& L) {
int i, N;
cout << "请输入顺序表中元素的个数" << endl;
cin >> N;
cout << "请输入元素" << endl;
for (i = 0; i < N; i++)
{
cin >> L.elem[i];
L.length++;
}
}
这里我使用了C++去写,其中的cout相当于printf,endl相当于\n,cin相当于scanf。
顺序表的扩容
当顺序表已满时,需要扩容以容纳更多元素。这通常涉及到重新分配更大的内存空间,并将原有数据复制过去。
bool resize(SqList &L, int newSize) {
ElemType *newData = (ElemType*)realloc(L.elem, sizeof(ElemType) * newSize);
if (newData != NULL) {
L.elem = newData;
L.capacity = newSize;
return OK;
}
return ERROR;
}
两个非递减有序顺序表的归并
算法步骤
①创建一个新的顺序表,其长度length为要合并的顺序表长度的总长。
②检查内存是否分配失败。
③初始化三个索引变量i、j、k,分别用来记录当前L1、L2以及L3中的当前位置。初始值都设为0.
④
- 使用一个循环同时遍历L1和L2,直到其中一个被完全遍历。
- 每次迭代中比较L1.elem[ i ]和L2.elem[ j ]的值。
- 如果L1.elem[ i ]小于等于L2.elem[ j ]的值,则将L1.elem[ i ]的值赋给L3.elem[ k ],然后增加i和k 。
- 否则将L2.elem[ j ]的值赋给L3.elem[ k ],然后增加j和k的值。
⑤
- 如果
L1
中有剩余元素未被复制(即i < L1.length
),继续将这些元素依次复制到L3
中。 - 如果
L2
中有剩余元素未被复制(即j < L2.length
),同样将这些元素依次复制到L3
中
⑥更新L3
的长度为k
,即已复制到L3
中的元素总数。
⑦通过一个循环打印出L3
中的所有元素,每个元素后换行。
int Merge(SqList &L1,SqList &L2){
SqList L3;
L3.elem=new ElemType[L1.length+L2.length];
if(L3.elem==NULL){
return ERROR;
}
int i=0,j=0,k=0;
while(i<L1.length&&j<L2.length){
if(L1.elem[i]<=L2.elem[j]) {
L3.elem[k++]=L1.elem[i++];
}
else{
L3.elem[k++]=L2.elem[j++];
}
}
//复制L1中剩余的元素
while(i<L1.length){
L3.elem[k++]=L1.elem[i++];
}
//复制L2中剩余的元素
while(j<L2.length){
L3.elem[k++] = L2.elem[j++];
}
L3.length = k;
for (i = 0; i < L3.length; i++) {
cout << L3.elem[i] << endl;
}
return 0;
}
具体实现
这里附上一个我之前写的顺序表的实现,使用的是结构体数据类型,里面涉及顺序表的遍历,批量添加等内容
#include <iostream>
#include <stdlib.h>
using namespace std;
#define OK 1
#define ERROR 0
#define MAX 100
//定义图书结构体
typedef struct {
char no[50];
char title[50];
float price;
}Book;
//定义顺序表结构体
typedef struct {
Book* elem;//动态数组
int length;//当前图书数量
}SqList;
//函数声明
int InitList(SqList& L);
int Insert(SqList& L,int position,Book e);
int BulkInsert(SqList& L, Book books[], int count);
int Traverse(SqList L);
int main() {
SqList L;
Book books[] = { {"1234","小红书",22.33},
{"2233","小黑书",44.66},
{"3344","小蓝书",55.77},
{"4455","小紫书",66.77},
{"6677","小绿书",111.222}
};
int bookcount = sizeof(books)/sizeof(Book);
//初始化顺序表
if (!InitList(L)) {
cout << "初始化失败" << endl;
return 1;
}
//批量插入图书
if (BulkInsert(L, books, bookcount)!=OK) {
cout << "插入失败" << endl;
return 1;
}
//遍历并显示图书信息
Traverse(L);
return 0;
}
int InitList(SqList& L) {
L.elem = new Book[100];
if (L.elem == NULL) {
return ERROR;
}
L.length = 0;
return OK;
}
int Insert(SqList& L, int pos, Book e) {
if (pos<1 || pos>L.length + 1) {
return ERROR;
}
if (L.length >= 100) {
return ERROR;
}
for (int i = L.length; i >= pos; i--) {
L.elem[i] = L.elem[i - 1];
}
L.elem[pos - 1] = e;
L.length++;
return OK;
}
//插入批量图书
int BulkInsert(SqList& L, Book books[], int count) {
for (int i = 0; i < count; i++) {
if (Insert(L, L.length + 1, books[i]) != OK) {
return ERROR;
}
}
return OK;
}
//遍历顺序表
int Traverse(SqList L) {
for (int i = 0; i < L.length; i++) {
cout << "序号:" << L.elem[i].no << endl;
cout << "书名:" << L.elem[i].title << endl;
cout << "价格:" << L.elem[i].price << endl;
}
return OK;
}
int GetElem(SqList L, int i, Book& e) {
if (i<1 || i>L.length) {
return ERROR;
}
e = L.elem[i - 1];
return OK;
}
这里我使用了C++去写,其中的cout相当于printf,endl相当于\n,cin相当于scanf。
这里面用到的函数除了批量插入以外,上文都讲到过,其中 int bookcount = sizeof(books)/sizeof(Book);的解释是:
在 C/C++ 中,sizeof 是一个运算符,用来获取数据类型或者对象的大小,在字节单位下。如果你有一个数组 books,并且 Book 是定义好的结构体类型,那么表达式 sizeof(books)/sizeof(Book) 或者sizeof(books)/sizeof(Book) 用来计算数组 books 中 Book 类型元素的数量。
再来一个例子,这个例子相对来说更加全面一点:
#include <iostream>
using namespace std;
typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100
typedef struct {
ElemType* elem;
int length;
} SqList;
// 初始化顺序表
Status InitList(SqList& L) {
L.elem = new ElemType[MAXSIZE];
if (!L.elem) {
return OVERFLOW;
}
L.length = 0;
return OK;
}
// 赋值操作
void Assign(SqList& L) {
int N;
cout << "请输入顺序表中元素的个数: ";
cin >> N;
cout << "请输入元素: " << endl;
for (int i = 0; i < N; i++) {
cin >> L.elem[i];
L.length++;
}
}
// 取值操作
Status GetElem(const SqList L, int index, ElemType& e) {
if (index < 1 || index > L.length) {
return ERROR;
}
e = L.elem[index - 1];
return OK;
}
// 查找操作
int LocateElem(const SqList L, ElemType e) {
for (int i = 0; i < L.length; i++) {
if (e == L.elem[i]) {
return i + 1; // 找到返回下标
}
}
return 0; // 没有找到返回0
}
// 插入操作
Status InsertElem(SqList& L, int pos, ElemType e) {
if (pos < 1 || pos > L.length + 1) {
return ERROR;
}
if (L.length >= MAXSIZE) {
return ERROR;
}
for (int i = L.length; i >= pos; i--) {
L.elem[i] = L.elem[i - 1];
}
L.elem[pos - 1] = e;
L.length++;
return OK;
}
// 删除操作
Status DeletElem(SqList& L, int index) {
if (index < 1 || index > L.length) {
return ERROR;
}
for (int j = index; j < L.length; j++) {
L.elem[j - 1] = L.elem[j];
}
L.length--;
return OK;
}
// 遍历操作
void Traverse(const SqList L) {
for (int i = 0; i < L.length; i++) {
cout << L.elem[i] << endl;
}
}
// 归并两个非递减有序顺序表
Status Merge(SqList& L1, SqList& L2) {
SqList L3;
L3.elem = new ElemType[L1.length + L2.length];
if (!L3.elem) {
return ERROR;
}
int i = 0, j = 0, k = 0;
while (i < L1.length && j < L2.length) {
if (L1.elem[i] <= L2.elem[j]) {
L3.elem[k++] = L1.elem[i++];
}
else {
L3.elem[k++] = L2.elem[j++];
}
}
// 复制L1中剩余的元素
while (i < L1.length) {
L3.elem[k++] = L1.elem[i++];
}
// 复制L2中剩余的元素
while (j < L2.length) {
L3.elem[k++] = L2.elem[j++];
}
L3.length = k;
for (i = 0; i < L3.length; i++) {
cout << L3.elem[i] << endl;
}
delete[] L3.elem; // 释放内存
return OK;
}
int main() {
SqList L1, L2, L3;
Status status;
int choice, pos, index, value;
ElemType e;
bool isInitList = false;
while (true) {
cout << "请选择操作:\n"
<< "1. 初始化顺序表\n"
<< "2. 赋值\n"
<< "3. 取值\n"
<< "4. 查找\n"
<< "5. 插入\n"
<< "6. 删除\n"
<< "7. 遍历\n"
<< "8. 归并\n"
<< "9. 退出\n";
cin >> choice;
if (!isInitList && choice != 1 && choice != 9) {
cout << "请先初始化顺序表!" << endl;
continue;
}
switch (choice) {
case 1:
status = InitList(L1);
if (status == OK) {
cout << "初始化顺序表成功!" << endl;
isInitList = true;
}
else {
cout << "初始化顺序表失败!" << endl;
}
break;
case 2:
Assign(L1);
break;
case 3:
cout << "请输入索引: ";
cin >> index;
status = GetElem(L1, index, e);
if (status == OK) {
cout << "元素为: " << e << endl;
}
else {
cout << "索引错误!" << endl;
}
break;
case 4:
cout << "请输入元素: ";
cin >> e;
index = LocateElem(L1, e);
if (index != 0) {
cout << "元素位置: " << index << endl;
}
else {
cout << "未找到该元素!" << endl;
}
break;
case 5:
cout << "请输入插入位置和元素: ";
cin >> pos >> value;
status = InsertElem(L1, pos, value);
if (status == OK) {
cout << "插入成功!" << endl;
}
else {
cout << "插入失败!" << endl;
}
break;
case 6:
cout << "请输入删除位置: ";
cin >> index;
status = DeletElem(L1, index);
if (status == OK) {
cout << "删除成功!" << endl;
}
else {
cout << "删除失败!" << endl;
}
break;
case 7:
cout << "遍历顺序表:" << endl;
Traverse(L1);
break;
case 8:
status = InitList(L2); // 先初始化第二个列表
if (status == OK) {
Assign(L2); // 然后赋值
status = Merge(L1, L2);
if (status == OK) {
cout << "合并完成!" << endl;
}
else {
cout << "合并失败!" << endl;
}
}
break;
case 9:
cout << "退出程序!" << endl;
return 0;
default:
cout << "无效的选择,请重新输入!" << endl;
break;
}
}
return 0;
}
这个例子感觉没什么可以解释的了,就是上面是介绍的顺序表操作的集合体,里面增加了一个用来判断顺序表是否初始化的isInitList,如果没有初始化就尝试进行赋值、取值、查找等操作,那么程序会访问到未定义的指针,这可能导致程序崩溃或产生不可预测的行为。只有当列表被初始化后,才允许用户选择其他操作。这样增加了程序的健壮性,但是这个程序目前还是没有非常严谨,只是具备了最基础的功能和一些简单的错误判断,用来当作参考,其健壮性还可以继续增加,这里为了不使文章过于冗长,就不再赘述,想知道更多的可以去百度或者询问AI。
写在最后
有的人可能会对什么时候使用&而感到疑问,这里简单说一下,只要涉及到地址都要加&。
这篇顺序表虽然是数据结构中最简单的部分,但是写这篇文章还是花了我好几个小时,中间不仅仅要以我的理解去编写文章,而且还要查找不少的资料来使这篇文章更加严谨,更加详细。
这篇文章先写与它的前篇线性表,算是继MC联机教程以外目前我写过,也是我花费时间最长的一篇文章了,在写这篇文章的过程中,我还会想这样写容不容易理解,在这个地方会不会产生疑问......尽管是这样,但还是感觉遗漏了不少东西,如果在阅读,学习过程中发现问题或者产生疑问,欢迎在评论区留下讨论,我会尽可能地去解决的。
这篇文章目前已经改过5次了,其中包括增加缺少的示例代码,增加顺序表的归并操作,以及增加了一个新的例子。
第六次修改增加了归并操作的算法步骤。
Comments NOTHING