数据结构复习 ---- 顺序表（数组）--定长版本+不定长版本

标签：return 版本 -- ElemType int length 定长 sqlist data

//我的思考************//
//1.顺序表是一种线性结构（一对一关系），每个数据都是有一个前驱（除了第一个元素）和一个后继(除了最后一个元素)
//2.顺序表分为定长顺序表（指针存储固定数量的元素）和不定长顺序表(顾名思义。。。使用较多) ----类似于动态数组，就像 Go语言中的切片， Python中的列表，其实基本都差不多只是名称罢了
//3.逻辑表和数组有相似之处也有不同
// 3.1相似之处：在逻辑上数据元素是连续的，在物理存储上也是连续的
// 3.2不同之处：数组只能够存储数据，顺序表不仅存储数据而且还能进行操作。其实我觉得这就体现出面向对象的一个特点
// 那就是我们在抽象一个事物的同时不仅要把事物的属性抽象出来，也要把事物的行为抽象出来。
//注：顺序表在存储数据时必须要从左边开始连续存储（确保lenth是有意义的）

我在文末实现的不定长顺序表其实是想要仿照vector，但是只是实现了空间配置器，后边我会重写vector。

数组（Array）——顺序表

数组是最基础的、使用最广泛的数据结构之一，也被称为顺序表。它是一种线性数据结构，用于存储一组大小相同的数据元素，所有元素在内存中连续存储。数组的特性使得它在程序设计中应用广泛，特别是在需要对元素进行随机访问的场景。

1. 数组的定义和基本操作

1.1. 数组的定义

在 C++ 中，我们可以通过以下方式定义一个数组：
```
int arr[5] = {1, 2, 3, 4, 5};
```
这里定义了一个长度为 5 的整型数组 arr，并初始化为 {1, 2, 3, 4, 5}。
数组在内存中是连续分配的，这意味着数组中的每个元素都有唯一的索引，可以通过索引快速访问元素。
```
int element = arr[2];  // 访问第三个元素，索引从0开始
```

1.2. 数组的基本操作

访问（Access）：数组的每个元素都有唯一的索引，因此可以通过索引直接访问元素。时间复杂度是 O(1)。
```
std::cout << arr[3];  // 输出第4个元素
```
插入（Insert）：对于静态数组，数组的大小是固定的，不能改变。插入元素时，需要将元素移动以腾出空间，因此插入的时间复杂度为 O(n)（最坏情况是在开头插入）。
- 例如，如果要在数组的开头插入一个新元素，需要把所有元素向后移动一个位置。
```
// 将元素插入到数组的开头
int n = 5;
for (int i = n; i > 0; --i) {
    arr[i] = arr[i - 1];
}
arr[0] = 10;
```
删除（Delete）：删除元素时同样需要移动其他元素来保持数组的连续性，因此删除的时间复杂度也为 O(n)（最坏情况是在开头删除）。
```
// 删除数组的第一个元素
for (int i = 0; i < n - 1; ++i) {
    arr[i] = arr[i + 1];
}
n--;  // 数组的有效大小减少
```

2. 数组的优缺点

2.1. 优点

快速随机访问：数组最大的优点是可以通过索引直接访问任意位置的元素，时间复杂度为 O(1)，这在需要频繁访问特定位置的数据时非常高效。
存储连续：数组在内存中是连续存储的，这样可以有效地利用 CPU 缓存，提升程序运行效率。

2.2. 缺点

固定大小：数组的大小在创建时需要确定，一旦定义就无法改变，无法适应需要动态调整大小的场景。
插入和删除效率低：在数组中插入或删除元素需要移动其他元素来保持连续性，因此效率较低，尤其是在需要频繁插入和删除的场景中，数组显得不够灵活。

3. 顺序表的应用场景

频繁访问元素：当你需要频繁地访问数组中的元素时，数组是最理想的选择，因为它的随机访问效率很高。
元素数量固定且不变：如果你在程序中需要存储固定数量的数据，例如一周七天的数据或月度的销售数据，数组是非常合适的。
性能关键的程序：因为数组在内存中是连续的，CPU 缓存命中率高，因此在一些性能关键的程序中，数组往往是首选的数据结构。

4. 动态数组与 STL 中的 `vector`

由于静态数组的大小是固定的，因此在需要动态调整大小时，C++ 中可以使用 动态数组 或 STL 中的 vector。

动态数组：可以通过 new 和 delete 关键字动态分配和释放内存。

int* dynamicArr = new int[5];  // 动态分配大小为 5 的数组
delete[] dynamicArr;  // 释放动态数组

std::vector：vector 是 C++ 标准模板库（STL）中的一个动态数组容器，具有自动调整大小的特性，并提供了许多便捷的方法来管理和操作数组元素。
```
#include <vector>
std::vector<int> vec = {1, 2, 3, 4, 5};
vec.push_back(6);  // 向 vector 末尾添加元素
vec.erase(vec.begin());  // 删除第一个元素
```
vector 提供了类似数组的随机访问能力，但在添加和删除元素时，它可以自动调整大小，非常灵活。

5. 小结

数组是顺序存储的数据结构，适合在数据量固定且需要频繁随机访问时使用。
数组有固定大小的限制，插入和删除操作效率低，在需要动态调整大小时，可以考虑使用 std::vector。
理解数组的优缺点以及合适的应用场景，可以帮助你在程序设计中做出更合理的数据结构选择。

6. 定长顺序表代码分析

6.1. 数据结构定义

在 .h 文件中定义了顺序表的结构：
```
#define MAXSIZE 100
typedef int ElemType;

struct FixedSqList {
    ElemType data[MAXSIZE];  // 固定大小的数组
    int length;              // 当前顺序表的元素个数
};
```
- MAXSIZE：定义了顺序表的最大容量。
- data 数组：用于存储顺序表中的元素，类型为 ElemType。
- length：记录顺序表中实际存储的元素个数。

6.2. 初始化、清空、销毁

InitFixedSqList：将 length 设为 0，初始化顺序表。
```
void InitFixedSqList(FixedSqList &L) {
    L.length = 0;  // 初始化顺序表，将长度设为 0，表示表为空。
}
```
通过设置 length 为 0，确保顺序表初始时没有存储任何元素，适合开始插入操作。
ClearFixedSqList：将 length 设为 0，清空顺序表，但保留分配的内存。
```
void ClearFixedSqList(FixedSqList &L) {
    L.length = 0;  // 清空顺序表内容，将长度重置为 0，但内存依然保留。
}
```
ClearFixedSqList 函数并不释放数组内存，而是简单地重置长度，这样可以保留顺序表的原有容量并便于重复使用。
DestroyFixedSqList：将 length 设为 0，销毁顺序表。
```
void DestroyFixedSqList(FixedSqList &L) {
    L.length = 0;  // 销毁顺序表，将长度重置为 0。
}
```
DestroyFixedSqList 函数的功能与清空类似，但语义上用于表示顺序表生命周期的结束，适合在程序结束时调用。

这些函数使得顺序表在使用过程中能够方便地被清空和重新初始化。

6.3. 插入和删除操作

头插法 (InsertOfHead)：通过调用 InsertOfPos 在顺序表的开头插入元素，时间复杂度为 O(n)。
```
bool InsertOfHead(FixedSqList &L, ElemType e) {
    return InsertOfPos(L, 1, e);  // 在位置 1 插入新元素，实现头插。
}
```
头插法需要将所有已有元素向后移动一个位置，从而在开头插入新元素。因此最坏情况下的时间复杂度为 O(n)。

尾插法 (InsertOfTail)：直接在尾部添加新元素，时间复杂度为 O(1)。

bool InsertOfTail(FixedSqList &L, ElemType e) {
    if (L.length >= MAXSIZE) return false;  // 检查顺序表是否已满。
    L.data[L.length] = e;  // 在尾部插入元素。
    L.length++;  // 更新顺序表长度。
    return true;
}

尾插法非常高效，只需在当前长度位置添加元素，并更新长度，无需移动其他元素，因此时间复杂度为 O(1)。

按位置插入 (InsertOfPos)：在指定位置插入元素，需要将指定位置及其后的元素向后移动，最坏情况下时间复杂度为 O(n)。

bool InsertOfPos(FixedSqList &L, int pos, ElemType e) {
    if (L.length >= MAXSIZE) return false;  // 检查顺序表是否已满。
    if (pos < 1 || pos > L.length + 1) return false;  // 检查插入位置是否合法。
    for (int i = L.length; i >= pos; --i) {
        L.data[i] = L.data[i - 1];  // 将从插入位置开始的元素向后移动。
    }
    L.data[pos - 1] = e;  // 在指定位置插入新元素。
    L.length++;  // 增加顺序表的长度。
    return true;
}

该函数首先检查表是否已满以及插入位置是否合法，然后将插入位置及其后的元素向后移动一位，最后在指定位置插入新元素。由于需要移动元素，因此最坏情况下时间复杂度为 O(n)。

头删法 (DeleteOfHead)：删除第一个元素，需要将所有元素向前移动，时间复杂度为 O(n)。
```
bool DeleteOfHead(FixedSqList &L) {
    return DeleteOfPos(L, 1);  // 删除第一个元素。
}
```
头删法通过调用 DeleteOfPos 删除第一个位置的元素，需要将所有元素向前移动以保持数组的连续性，最坏情况下时间复杂度为 O(n)。
尾删法 (DeleteOfTail)：直接减少 length，时间复杂度为 O(1)。
```
bool DeleteOfTail(FixedSqList &L) {
    if (L.length == 0) return false;  // 检查顺序表是否为空。
    L.length--;  // 减少顺序表的长度。
    return true;
}
```
尾删法直接减少顺序表的长度即可，不需要移动其他元素，因此时间复杂度为 O(1)。

按位置删除 (DeleteOfPos)：删除指定位置的元素，后面的元素需要向前移动，时间复杂度为 O(n)。

bool DeleteOfPos(FixedSqList &L, int pos) {
    if (L.length == 0) return false;  // 检查顺序表是否为空。
    if (pos < 1 || pos > L.length) return false;  // 检查删除位置是否合法。
    for (int i = pos; i < L.length; ++i) {
        L.data[i - 1] = L.data[i];  // 将删除位置之后的元素向前移动。
    }
    L.length--;  // 减少顺序表的长度。
    return true;
}

该函数检查顺序表是否为空以及删除位置是否合法，然后将删除位置后的所有元素向前移动，覆盖被删除的位置，最后更新顺序表长度。最坏情况下时间复杂度为 O(n)。

按值删除 (DeleteOfVal)：删除值匹配的所有元素，通常需要遍历整个顺序表并移动元素。

bool DeleteOfVal(FixedSqList &L, ElemType e) {
    if (L.length == 0) return false;  // 检查顺序表是否为空。
    int k = 0;  // 记录要保留的元素个数。
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] != e) {
            L.data[k++] = L.data[i];  // 保留不等于 e 的元素。
        }
    }
    L.length = k;  // 更新顺序表的长度。
    return true;
}

该函数通过遍历顺序表，将不等于目标值的元素保留，并依次覆盖原位置，从而删除所有匹配的值。由于需要遍历所有元素，因此时间复杂度为 O(n)。

快速按值删除 (DeleteOfValFast)：使用“填补空缺”的策略，提升删除效率。

bool DeleteOfValFast(FixedSqList &L, ElemType e) {
    if (L.length == 0) return false;  // 检查顺序表是否为空。
    int i = 0;
    int n = L.length;
    while (i < n) {
        if (L.data[i] == e) {
            L.data[i] = L.data[--n];  // 用最后一个元素填补当前的位置。
        } else {
            i++;
        }
    }
    L.length = n;  // 更新顺序表的长度。
    return true;
}

该函数采用一种快速删除策略：当找到要删除的元素时，用顺序表最后一个元素填补当前位置，并减少长度。这样可以减少移动操作的次数，提高删除效率。时间复杂度平均为 O(n)，但在减少移动次数上具有优势。

不定长顺序表代码分析

1. 数据结构定义和函数声明

#pragma once
#define INITSIZE 10
typedef int ElemType;  // 将类型重命名，方便以后代码的迁移和复用

typedef struct Sqlist {
    ElemType *data;  // 指向动态分配的顺序表数据存储空间
    int length;      // 当前存储的数据元素个数
    int size;        // 当前空间的大小
} SqList;

// 初始化
void InitSqList(SqList& sqlist);
// 销毁
void DestorySqList(SqList& sqlist);
// 清空
void ClearSqList(SqList& sqlist);
// 打印
void PrintfSqList(SqList& sqlist);

// 插入操作
// 头插法
bool InsertOfhead(SqList& sqlist, ElemType val);
// 尾插法
bool InsertOfTail(SqList& sqlist, ElemType val);
// 按位置插入
bool InserOfPos(SqList& sqlist, ElemType val, int pos);

// 删除操作
// 头删法
bool DeleteOfHead(SqList& sqlist);
// 尾删法
bool DeleteOfTail(SqList& sqlist);
// 按位置删除
bool DeleteOfPos(SqList& sqlist, int pos);
// 按值删除
bool DeleteOfVal(SqList& sqlist, ElemType val);
bool DeleteOfValFast(SqList& sqlist, ElemType val);

// 查找元素位置
int FindVal(SqList& sqlist, ElemType val);

分析与解释

#pragma once：防止头文件被多次包含，避免重复定义。
INITSIZE：定义初始顺序表容量为 10，使得顺序表一开始有一定的存储空间。
ElemType：通过 typedef 使代码对数据类型更加灵活，如果将来需要修改元素的类型，只需要修改这一行即可。
SqList 结构体：动态顺序表的核心数据结构，包含：
- ElemType *data：指向动态分配的存储空间。
- int length：当前顺序表的实际元素个数。
- int size：当前存储空间的容量，允许扩展。

接下来是函数声明，包括初始化、清空、销毁、打印操作，以及插入、删除、查找等各种方法。

2. 辅助函数 - AppendSpace

static bool AppendSpace(SqList& sqlist) {
    int newsize = 0;
    if (sqlist.size < 1000) {
        newsize = sqlist.size * 2;  // 当前空间小于 1000 时，每次扩展一倍
    } else {
        newsize = sqlist.size + INITSIZE;  // 当前空间达到 1000 以上时，每次扩展固定的 INITSIZE
    }

    ElemType *s = (ElemType*)malloc(sizeof(ElemType) * newsize);
    if (s == NULL) return false;

    // 数据复制，将旧的数据复制到新分配的空间中
    for (int i = 0; i < sqlist.length; i++) {
        s[i] = sqlist.data[i];
    }
    free(sqlist.data);  // 释放旧空间，防止内存泄漏

    sqlist.data = s;
    sqlist.size = newsize;
    return true;
}

AppendSpace：用于顺序表扩容的辅助函数。
- 采用倍增策略进行扩容，当容量小于 1000 时，每次扩容一倍；否则，每次增加固定容量 INITSIZE。
- 新分配内存后，将原有数据复制到新空间，然后释放旧内存。
- 该策略可以平衡扩容频率与内存使用效率。

3. 初始化、清空和销毁

初始化 (InitSqList)：

void InitSqList(SqList& sqlist) {
    sqlist.data = (ElemType*)malloc(sizeof(ElemType) * INITSIZE);
    assert(sqlist.data != NULL);
    sqlist.length = 0;
    sqlist.size = INITSIZE;
}

使用 malloc 为顺序表分配初始内存，并设置 length 为 0，表示初始为空。
assert 确保内存分配成功。

销毁 (DestorySqList)：

void DestorySqList(SqList& sqlist) {
    free(sqlist.data);  // 释放动态分配的内存
    sqlist.data = NULL;
    sqlist.length = 0;
    sqlist.size = 0;
}

释放动态分配的内存并将指针设为 NULL，防止悬空指针。

清空 (ClearSqList)：

void ClearSqList(SqList& sqlist) {
    sqlist.length = 0;  // 只重置长度，不释放内存
}

将长度重置为 0，但保留已经分配的内存，方便后续使用。

4. 插入操作

头插法 (InsertOfhead)：

bool InsertOfhead(SqList& sqlist, ElemType val) {
    return InserOfPos(sqlist, val, 1);  // 在位置 1 插入新元素，头插
}

通过调用按位置插入函数，将元素插入到第一个位置，时间复杂度为 O(n)。

尾插法 (InsertOfTail)：

bool InsertOfTail(SqList& sqlist, ElemType val) {
    if (sqlist.length >= sqlist.size) {
        if (!AppendSpace(sqlist)) return false;  // 空间不足时扩容
    }
    sqlist.data[sqlist.length++] = val;  // 在末尾添加元素
    return true;
}

直接将新元素插入到当前长度的位置，若空间不足则扩容，时间复杂度为 O(1)。

按位置插入 (InserOfPos)：

bool InserOfPos(SqList& sqlist, ElemType val, int pos) {
    if (pos < 1 || pos > sqlist.length + 1) return false;  // 检查插入位置是否合法
    if (sqlist.length >= sqlist.size) {
        if (!AppendSpace(sqlist)) return false;  // 空间不足时扩容
    }
    for (int i = sqlist.length; i >= pos; --i) {
        sqlist.data[i] = sqlist.data[i - 1];  // 将插入位置及之后的元素向后移动
    }
    sqlist.data[pos - 1] = val;  // 插入新元素
    sqlist.length++;
    return true;
}

先检查插入位置是否合法，若合法则插入元素。
需要将插入位置及之后的元素向后移动一位，时间复杂度为 O(n)。

5. 删除操作

头删法 (DeleteOfHead)：

bool DeleteOfHead(SqList& sqlist) {
    return DeleteOfPos(sqlist, 1);  // 删除第一个元素
}

调用按位置删除函数，删除第一个元素。

尾删法 (DeleteOfTail)：

bool DeleteOfTail(SqList& sqlist) {
    if (sqlist.length == 0) return false;  // 检查顺序表是否为空
    sqlist.length--;  // 直接减少长度
    return true;
}

直接将 length 减 1，无需移动元素，时间复杂度为 O(1)。

按位置删除 (DeleteOfPos)：

bool DeleteOfPos(SqList& sqlist, int pos) {
    if (sqlist.length == 0) return false;  // 检查是否为空
    if (pos < 1 || pos > sqlist.length) return false;  // 检查位置是否合法
    for (int i = pos - 1; i < sqlist.length - 1; i++) {
        sqlist.data[i] = sqlist.data[i + 1];  // 将删除位置后的元素向前移动
    }
    sqlist.length--;
    return true;
}

删除指定位置的元素，将该位置后的元素向前移动以保持连续性，时间复杂度为 O(n)。

6. 打印顺序表

void PrintfSqList(SqList& sqlist) {
    for (int i = 0; i < sqlist.length; i++) {
        printf("%d ", sqlist.data[i]);
    }
    printf("\n");
}

通过 for 循环遍历顺序表，输出每个元素，适用于调试和观察结果。

7. 按值删除

按值删除 (DeleteOfVal)：

bool DeleteOfVal(SqList& sqlist, ElemType val) {
    if (sqlist.length == 0) return false;  // 检查是否为空
    for (int i = 0; i < sqlist.length;) {
        if (sqlist.data[i] == val) {
            DeleteOfPos(sqlist, i + 1);  // 如果匹配则调用按位置删除
        } else {
            i++;
        }
    }
    return true;
}

遍历顺序表，找到匹配的元素后调用按位置删除，时间复杂度为 O(n^2)（因为嵌套了删除操作）。

快速按值删除 (DeleteOfValFast)：

bool DeleteOfValFast(SqList& sqlist, ElemType val) {
    if (sqlist.length == 0) return false;
    int count = 0;  // 记录匹配的元素个数
    for (int i = 0; i < sqlist.length - count;) {
        if (sqlist.data[i + count] == val) {
            count++;
        } else {
            sqlist.data[i] = sqlist.data[i + count];

该函数采用一种快速删除策略：当找到要删除的元素时，用顺序表最后一个元素填补当前位置，并减少长度。这样可以减少移动操作的次数，提高删除效率。时间复杂度平均为 O(n)，但在减少移动次数上具有优势。

最后附上完整代码

定长顺序表

fixedsqlist.h

#pragma once//防止头文件重复包含


typedef int ElemType; //将类型重命名，方便以后的代码迁移和复用

#define MAXSIZE 100 //设置最大存储元素个数

typedef struct Sqlist  // 结构体类型重命名
{
	ElemType data[MAXSIZE];//
	int length;//当前已经存储数据元素的个数
}FixedSqList;

//顺序表的操作

//初始化
void InitFixedSqList(FixedSqList& sqlist);
// 销毁
void DestoryFixedSqList(FixedSqList&sqlist);
//清空
void ClearFixedSqList(FixedSqList& sqlist);
//打印
void PrintfFixedSqList(FixedSqList& sqlist);
//插入
// 头插法
bool InsertOfhead(FixedSqList& sqlist, ElemType val);
//尾插法
bool InsertOfTail(FixedSqList& sqlist, ElemType val);
//按位置插入
bool InserOfPos(FixedSqList& sqlist, ElemType val,int pos);


//删除
//头删法
bool DeleteOfHead(FixedSqList& sqlist);
//尾删法
bool DeleteOfTail(FixedSqList& sqlist);
//位置删除
bool DeleteOfPos(FixedSqList& sqlist,int pos);
//元素删除
bool DeleteOfVal(FixedSqList& sqlist, ElemType val);//时间复杂度为O(n^2)
bool DeleteOfValFast(FixedSqList& sqlist, ElemType val);//时间复杂度为 O(n)
//查找元素位置
int FindVal(FixedSqList& sqlist, ElemType val);

fixedsqlist.cpp

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include"fixedsqlist.h"
//初始化
//C代码中变量的分类 ：全局变量  局部变量  堆区变量  静态变量（全局，局部） 字符常量
//C程序（Windows的.exe文件，Linux中的ELF格式a.out ）中则分为： .rodata(字符常量区) .data（初始化不为零的变量：全局变量，静态变量） 
                                                             // .bss（未初始化或者初始化为零的变量）  .heap（堆区 ：malloc new delete free）     .stack(栈区 ： 局部变量)

//使用引用不用判空可以提高代码的健壮性
void InitFixedSqList(FixedSqList& sqlist)
{   
	sqlist.length = 0;
}
// 销毁
void DestoryFixedSqList(FixedSqList& sqlist)
{  
	sqlist.length = 0;
}
//清空
void ClearFixedSqList(FixedSqList& sqlist)
{
	sqlist.length = 0;
}

//打印顺序表的元素
void PrintfFixedSqList(FixedSqList& sqlist)
{
	
	for (int i = 0; i < sqlist.length; i++)
	{
		printf("%d\t", sqlist.data[i]);
	}
	printf("\n");
}

// 第一次思考，写完之后我发现一个问题，我原本就是最简单的插入思想，就是然后三个函数都是分开写
// 但是我在写完按位置插入的时候忽然想到 其实头插法就是 位置为0的按位置插入插法，尾插就是位置为末尾的按位置插入法
//  
//在写代码之前一定要思考好 ，我的意思是 把函数都思考好  ，而不是想一个函数就写一个 ，其实函数的精妙就在于函数之间的相互利用

//插入
// 头插法
bool InsertOfhead(FixedSqList& sqlist, ElemType val)
{   
	return  InserOfPos(sqlist, val, 1);
}

/*void InsertOfhead(FixedSqList&sqlist, ElemType val)
{
	if (sqlist.length < MAXSIZE)
	{
		if (sqlist.length == 0)
		{
			sqlist.data[0] = val;
		}
		else
		{
			for (int i = sqlist.length ; i > 0; i--)
			{
				sqlist.data[i] = sqlist.data[i - 1];
			}
			sqlist.data[0] = val;
		}
		sqlist.length += 1;
	}
	else
	{
		printf("储存元素个数达到峰值，插入失败");
	}
}
*/

//尾插法
bool InsertOfTail(FixedSqList& sqlist, ElemType val)
{    //代码效率更高
	if (sqlist.length == MAXSIZE) return false;
	sqlist.data[sqlist.length++] = val;
	return true;
	//return InserOfPos(sqlist, val, sqlist.length+1);//  --<< sqlist.length-1+1 数组最后一个元素的下标的后一位
}
/*
void InsertOfTail(FixedSqList&sqlist, ElemType val)
{
	if (sqlist.length < MAXSIZE)
	{
		sqlist.data[sqlist.length - 1] = val;
		sqlist.length += 1;
	}
	else
	{
		printf("储存元素个数达到峰值，插入失败");
	}
}
*/

//按位置插入
bool InserOfPos(FixedSqList& sqlist, ElemType val, int pos)
{
	int tag = true;
	if (sqlist.length < MAXSIZE )
	{
		if (pos <= 0 || pos > sqlist.length+1) exit(0);
		
			for (int i = sqlist.length; i > pos-1; i--)
			{
				sqlist.data[i] = sqlist.data[i - 1];
			}

			sqlist.data[pos-1] = val;
			sqlist.length += 1;
		
	}
	else
	{
		tag = false;
	}
	return tag;
}


//删除
//头删法
bool DeleteOfHead(FixedSqList& sqlist)
{
	return DeleteOfPos(sqlist, 1);
}
//尾删法
bool DeleteOfTail(FixedSqList& sqlist)
{   //代码效率更高
	if (sqlist.length == 0) return false;
	sqlist.length--;
	return true;
	//return DeleteOfPos(sqlist, sqlist.length);
}
//位置删除
bool DeleteOfPos(FixedSqList& sqlist, int pos)
{
	if (sqlist.length == 0) return false;
	if (pos<=0 || pos>sqlist.length) return false;
	for (int i = pos-1; i < sqlist.length-1; i++)
	{
		sqlist.data[i] = sqlist.data[i + 1];
	}
	sqlist.length -= 1;
	return true;
}


//元素删除
bool DeleteOfVal(FixedSqList& sqlist, ElemType val)
{  /*这种代码只能删除第一个val元素而不能删除所有
	int pos = FindVal(sqlist, val);
	if (DeleteOfPos(sqlist, pos + 1)) return true;
	else return false;
	*/
	if (sqlist.length == 0)return false;
	/*for (int i = 0; i < sqlist.length; i++)//如果这样的话，要是连续的数据就会有bug
	{   if(sqlist.data[i]==val)
		{
			DeleteOfPos(sqlist, i+1);
		}
	}*/
	//时间复杂度O(n^2) 太高
	for (int i = 0; i < sqlist.length;)
	{
		if (sqlist.data[i] == val)
		{
			DeleteOfPos(sqlist, i + 1);
		}
		else
		{
			i++;
		}
	}
	return true;
}
bool DeleteOfValFast(FixedSqList& sqlist, ElemType val)
{
	if (sqlist.length == 0)return false;
	int count = 0;//记录val值出现的次数

	for (int i = 0; i < sqlist.length - count;)
	{ /*
		sqlist.data[i] = sqlist.data[i + count];
		if (sqlist.data[i] == val)
		{
			count++;
		}
		else
		{
			i++;
		}*/
		if (sqlist.data[i + count] == val)
		{
			count++;
		}
		else
		{
			sqlist.data[i] = sqlist.data[i + count];
			i++;
		}
	}
	

	sqlist.length -= count;
	return true;

}
//定位函数
int FindVal(FixedSqList& sqlist, ElemType val)
{
	int i = 0;
	for (; i < sqlist.length; i++)
	{
		if (sqlist.data[i] == val)
		{
			break;
		}
	}
	if (i == sqlist.length) 
	{ 
		i = -1; 
	}

	return i;
}

main.cpp

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include"fixedsqlist.h"

int main(void)
{
	FixedSqList sqlist;
	InitFixedSqList(sqlist);
	InsertOfhead(sqlist, 1);
	InsertOfhead(sqlist, 2);
	InsertOfhead(sqlist, 3);
	InsertOfhead(sqlist, 4);
	PrintfFixedSqList(sqlist);

	InsertOfTail(sqlist, 5);
	InsertOfTail(sqlist, 7);
	InsertOfTail(sqlist, 7);
	InsertOfTail(sqlist, 7);
	PrintfFixedSqList(sqlist);

	InserOfPos(sqlist, 9, 3);
	PrintfFixedSqList(sqlist);

	DeleteOfHead(sqlist);
	PrintfFixedSqList(sqlist);

	DeleteOfTail(sqlist);
	PrintfFixedSqList(sqlist);

	DeleteOfPos(sqlist, 4);
	PrintfFixedSqList(sqlist);

	//DeleteOfVal(sqlist, 7);
	DeleteOfValFast(sqlist, 7);
	PrintfFixedSqList(sqlist);

	ClearFixedSqList(sqlist);
	DestoryFixedSqList(sqlist);
	return 0;

}

不定长顺序表

sqlist.h

#pragma once
#define INITSIZE 10
typedef int ElemType; //将类型重命名，方便以后的代码迁移和复用

typedef struct Sqlist  // 结构体类型重命名
{
	ElemType *data;//指向申请的堆区空间首地址
	int length;//当前已经存储数据元素的个数
	int size;//存储当前空间大小
}SqList;


//初始化
void InitSqList(SqList& sqlist);
// 销毁
void DestorySqList(SqList& sqlist);
//清空
void ClearSqList(SqList& sqlist);
//打印
void PrintfSqList(SqList& sqlist);
//插入
// 头插法
bool InsertOfhead(SqList& sqlist, ElemType val);
//尾插法
bool InsertOfTail(SqList& sqlist, ElemType val);
//按位置插入
bool InserOfPos(SqList& sqlist, ElemType val, int pos);


//删除
//头删法
bool DeleteOfHead(SqList& sqlist);
//尾删法
bool DeleteOfTail(SqList& sqlist);
//位置删除
bool DeleteOfPos(SqList& sqlist, int pos);
//元素删除
bool DeleteOfVal(SqList& sqlist, ElemType val);//
bool DeleteOfValFast(SqList& sqlist, ElemType val);//
//查找元素位置
int FindVal(SqList& sqlist, ElemType val);


sqlist.cpp

#include"sqlist.h"
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<malloc.h>


//类似于仿造STL里的空间配置器的想法，也是相当于一级空间配置器和二级空间配置器
static bool AppendSpace(SqList& sqlist)//扩容函数，static修饰函数，此函数只能在本文件中使用
{   // 当size<1000时，扩容每次以两倍增长，一旦size>=1000,则每次追加10个空间，防止空间浪费
	int newsize = 0;
	if (sqlist.size < 1000)
	{
		newsize = sqlist.size * 2;
	}
	else
	{
		newsize = sqlist.size + INITSIZE;
	}
  
	ElemType *s= (ElemType*)malloc(sizeof(ElemType) * newsize);
	if (s == NULL) return false;
	//数据复制：将原来的数据复制到扩容后新的空间中
	for (int i = 0; i < sqlist.length; i++)
	{
		  s[i] = sqlist.data[i];
	}
	free(sqlist.data);//释放原来空间，防止内存泄露
	sqlist.data = s;
	sqlist.size =newsize;
	return true;
}



// 初始化
void InitSqList(SqList& sqlist)
{
	sqlist.data =(ElemType*)malloc(sizeof(ElemType)*INITSIZE) ;
	assert(sqlist.data != NULL);
	sqlist.length = 0;
	sqlist.size = INITSIZE;
}
// 销毁
void DestorySqList(SqList& sqlist)
{
	free(sqlist.data);
	sqlist.data = NULL;
	sqlist.size =sqlist.length= 0;
}
//清空
void ClearSqList(SqList& sqlist)
{
	sqlist.length = 0;
	sqlist.size = INITSIZE;
}
//打印
void PrintfSqList(SqList& sqlist)
{
	for (int i = 0; i < sqlist.length; i++)
	{
		printf("%d\t", sqlist.data[i]);
	}
	printf("\n");
}


//插入
// 头插法
bool InsertOfhead(SqList& sqlist, ElemType val)
{
	return InserOfPos(sqlist, val, 1);
}
//尾插法
bool InsertOfTail(SqList& sqlist, ElemType val)
{
	return InserOfPos(sqlist, val, sqlist.length+1);
}
//按位置插入
bool InserOfPos(SqList& sqlist, ElemType val, int pos)
{
	if (pos < 1 || pos > sqlist.length+1) return false;
	if (sqlist.length == sqlist.size)
	{
		if (!AppendSpace(sqlist)) return false;//进行扩容并检查扩容是否成功
	}
	for (int i = sqlist.length; i > pos-1; --i)
	{
		sqlist.data[i] = sqlist.data[i-1];
	}
	sqlist.data[pos - 1] = val;
	sqlist.length++;
	return true;
}


//删除
//头删法
bool DeleteOfHead(SqList& sqlist)
{
	return DeleteOfPos(sqlist, 1);
}
//尾删法
bool DeleteOfTail(SqList& sqlist)
{
	if (sqlist.length == 0) return false;
	sqlist.length -= 1;
	return true;
}
//位置删除
bool DeleteOfPos(SqList& sqlist, int pos)
{
	if (sqlist.length == 0) return false;
	if (pos <0 || pos>sqlist.length) return false;
	for (int i = pos - 1; i < sqlist.length - 1; i++)
	{
		sqlist.data[i] = sqlist.data[i + 1];
	}
	sqlist.length -= 1;
	return true;
}


//元素删除
bool DeleteOfVal(SqList& sqlist, ElemType val)
{
	if (sqlist.length == 0)return false;
	for (int i = 0; i < sqlist.length;)
	{
		if (sqlist.data[i] == val)
		{
			DeleteOfPos(sqlist, i + 1);
		}
		else
		{
			i++;
		}
	}
	return true;
}
bool DeleteOfValFast(SqList& sqlist, ElemType val)
{
	if (sqlist.length == 0) return false;
	int count = 0;//记录val值出现的次数

	for (int i = 0; i < sqlist.length - count;)
	{
		if (sqlist.data[i + count] == val)
		{
			count++;
		}
		else
		{
			sqlist.data[i] = sqlist.data[i + count];
			i++;
		}
	}
	sqlist.length -= count;
	return true;
}
//查找元素位置
int FindVal(SqList& sqlist, ElemType val)
{
	int i = 0;
	for (; i < sqlist.length; i++)
	{
		if (sqlist.data[i] == val)
		{
			break;
		}
	}
	if (i == sqlist.length)
	{
		i = -1;
	}

	return i;
}

main.cpp
#include"sqlist.h"
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<malloc.h>



int main()
{
	SqList sqlist;
	InitSqList(sqlist);
	InsertOfhead(sqlist, 1);
	InsertOfhead(sqlist, 1);
	InsertOfhead(sqlist, 1);
	PrintfSqList(sqlist);

	InsertOfTail(sqlist, 5);
	InsertOfTail(sqlist, 6);
	InsertOfTail(sqlist, 7);
	PrintfSqList(sqlist);

	InserOfPos(sqlist, 2, 2);
	PrintfSqList(sqlist);
	InserOfPos(sqlist, 3, 4);
	PrintfSqList(sqlist);
	PrintfSqList(sqlist);

	DeleteOfHead(sqlist);
	DeleteOfTail(sqlist);
	PrintfSqList(sqlist);
	DeleteOfPos(sqlist, 2);
	PrintfSqList(sqlist);

	//DeleteOfVal(sqlist, 1);
	DeleteOfValFast(sqlist, 1);
	PrintfSqList(sqlist);

	ClearSqList(sqlist);
	DestorySqList(sqlist);
	return 0;

}

标签：return,版本,--,ElemType,int,length,定长,sqlist,data
From： https://blog.csdn.net/timeflyfast/article/details/143846841

数据结构复习 ---- 顺序表（数组）--定长版本+不定长版本

1. 数组的定义和基本操作

1.1. 数组的定义

1.2. 数组的基本操作

2. 数组的优缺点

2.1. 优点

2.2. 缺点

3. 顺序表的应用场景

4. 动态数组与 STL 中的 `vector`

5. 小结

6. 定长顺序表代码分析

6.1. 数据结构定义

6.2. 初始化、清空、销毁

6.3. 插入和删除操作

不定长顺序表代码分析

1. 数据结构定义和函数声明

分析与解释

2. 辅助函数 - AppendSpace

3. 初始化、清空和销毁

4. 插入操作

5. 删除操作

6. 打印顺序表

7. 按值删除

相关文章

赞助商

阅读排行

数据结构复习 ---- 顺序表（数组）--定长版本+不定长版本

1. 数组的定义和基本操作

1.1. 数组的定义

1.2. 数组的基本操作

2. 数组的优缺点

2.1. 优点

2.2. 缺点

3. 顺序表的应用场景

4. 动态数组与 STL 中的 vector

5. 小结

6. 定长顺序表代码分析

6.1. 数据结构定义

6.2. 初始化、清空、销毁

6.3. 插入和删除操作

不定长顺序表代码分析

1. 数据结构定义和函数声明

分析与解释

2. 辅助函数 - AppendSpace

3. 初始化、清空和销毁

4. 插入操作

5. 删除操作

6. 打印顺序表

7. 按值删除

相关文章

赞助商

阅读排行

4. 动态数组与 STL 中的 `vector`