本文最后更新于208 天前，其中的信息可能已经过时，如有错误请发送邮件到zhangweihao22@outlook.com

简介

此模块为学校数据结构必修课学习内容的记录与分享

全文大体分为一下几个部分

模块解释
可视化GIF合集
整体复现
最终结果

模块解释

* 顺序表储存结构

创建顺序表数据结构

typedef struct SqList {  // typedef 是为已有的类型创造别名的，而模板是用于创建泛型类型的，因此这里不能使用 typedef
    int Length;
    int data[MAX_LLIST_LEN];
} *SqListPtr;  // 为什么这里申明的是一个指针？

这里有一个小想法，使用模板变量替换 int 变量，提高其可迁移性。

发现一个问题，使用模板变量的结构体无法用 typedef 创造别名

typedef 是为已有的类型创造别名的，而模板是用于创建泛型类型的，因此这里不能使用 typedef

至于为什么别名为一个指针，是因为这样方便内存分配管理以及在函数中的参数传递（避免复制传递带来的不必要开销）

注意，struct 后面需要跟着结构体标签名或者直接定义结构体成员，也就是不能直接创建 struct *SqList只能创造指针别名

输出顺序表

void OutPutList (SqListPtr L) {
    for (int i = 0; i < L->Length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\r\n");  // \r 是回车符的转义符 建议只使用\n
}

\r 是回车符的转义符表示把光标移至改行最前位

window 中 \r\n表示换行，而 Linux 中 \n 表示换行

推荐直接只使用 \n

输出顺序表中元素的地址

void OutPutListPos (SqListPtr L) {
    printf("the position of structure is : %ld\n",L);
    for (int i = 0; i < L->Length; i++) {
        printf("the position of data [%d] is %ld\n",i,&L->data[i]);
    }
    printf("\n");  
}

打印出顺序表中元素的地址，方便对其顺序储存模式的理解

顺序表在物理空间上也是顺序储存数据的

初始化顺序表

传入数组并初始化顺序表为数组内数据

SqListPtr InitList (int *ParaData, int ParaLen ) {
    SqListPtr ResultPtr = (SqListPtr)malloc(sizeof(struct SqList));
    for (int i = 0; i < ParaLen; i++) {
        ResultPtr->data[i] = ParaData[i];
    }
    ResultPtr->Length = ParaLen;
    return ResultPtr;
}

为什么分配内存后转化为 SqListPtr 而不是 SqList ？二者不都是结构体吗？

SqListPtr 是一个指向结构体的指针类型

SqList 是一个结构体类型

malloc返回的是一个void* 类型的指针，需要在使用时显式转化为其它类型的指针，转化后编译器才能知道其指向的数据结构布局，才能进行对应的偏移计算和访问操作。

顺序表的数据插入

在顺序表指定位置插入指定数据

void SqListInsert (SqListPtr L, int Pos, int Data) {
    // 三段边界检查
    if(L -> Length >= MAX_LLIST_LEN) {
        printf("Cannot insert element: list full.\n");
        return;
    }

    if (Pos < 0) {
        printf("Cannot insert element: negative position unsupported.");
        return;
    }
 
    if (Pos > L->Length) {
        printf("Cannot insert element: the position %d is bigger than the list length %d.\r\n", Pos, L->Length);
        return;
    }

    // 腾位置
    for(int i = L->Length; i > Pos; i--) {
        L->data[i] = L->data[i - 1];
    }

    L->data[Pos] = Data;
    L->Length++;
}

检查顺序表整个插入流程

void SqListInsertTest () {
    int i;
	int tempArray[5] = {3, 5, 2, 7, 4};

    printf("---- sequentialInsertTest begins. ----\r\n");

	// 初始化数据
    SqListPtr tempList = InitList(tempArray, 5);
    printf("After initialization, the list is: ");
	OutPutList(tempList);

	// 8，3, 5, 2, 7, 4
    printf("Now insert to the first, the list is: ");
	SqListInsert(tempList, 0, 8);
	OutPutList(tempList);

	// 8，3, 5, 2, 7, 4，9
    printf("Now insert to the last, the list is: ");
	SqListInsert(tempList, 6, 9);
	OutPutList(tempList);

	// 8，3, 5, 2, 7, 4，9
    printf("Now insert beyond the tail. \r\n");
	SqListInsert(tempList, 8, 9);
    printf("The list is:");
	OutPutList(tempList);

	// 10 11 12 13 14 8 3 5 2 7
	for (i = 0; i < 5; i ++) {
		printf("Inserting %d.\r\n", (i + 10));
		SqListInsert(tempList, 0, (i + 10));
		OutPutList(tempList);
	}

    printf("---- sequentialInsertTest ends. ----\r\n");
}

顺序表的数据删除

删除指定位置的数据，并返回该位置上的数据

注意，判断条件分为两部分：

操作索引的实际意义（与0和最大表长关系)

操作索引与表的实际长度关系

int SqListDelete (SqListPtr L, int Pos) {
    if (Pos < 0) {
        printf("Invalid position: %d.\r\n", Pos);
        return -1;
    }

    int ResultValue = L->data[Pos];

    if (Pos >= L->Length) {
        printf("Cannot delete element: the position %d is beyond the list length %d.\r\n", Pos, L->Length);
        return -1;
    }

    L -> Length--;
    return ResultValue;  // 返回被删除的元素
}

检查顺序表整个删除流程

void SqListDeleteTest () {
    int tempArray[5] = {3, 5, 2, 7, 4};

    printf("---- sequentialDeleteTest begins. ----\r\n");

	// Initialize.
    SqListPtr tempList = InitList(tempArray, 5);
    printf("After initialization, the list is: ");
	OutPutList(tempList);

	// Delete the first.
    printf("Now delete the first, the list is: ");
	SqListDelete(tempList, 0);
	OutPutList(tempList);

	// Delete to the last.
    printf("Now delete the last, the list is: ");
	SqListDelete(tempList, 3);
	OutPutList(tempList);

	// Delete the second.
    printf("Now delete the second, the list is: ");
	SqListDelete(tempList, 1);
	OutPutList(tempList);

	// Delete the second.
    printf("Now delete the 5th, the list is: ");
	SqListDelete(tempList, 5);
	OutPutList(tempList);

	// Delete the second.
    printf("Now delete the (-6)th, the list is: ");
	SqListDelete(tempList, -6);
	OutPutList(tempList);

    printf("---- sequentialDeleteTest ends. ----\r\n");

	OutPutListPos(tempList);
}

定位给定的数据在顺序表中的位置

int LocateElement(SqListPtr L, int Data) {
    for (int i = 0; i < L->Length; i++) {
        if (L->data[i] == Data) {
            return i;
        }
    }
    return -1;
}

获取顺序表指定位置的数据

int GetElement(SqListPtr L, int Pos) {
    if (Pos < 0 || Pos >= L->Length) {
        printf("Invalid position: %d.\r\n", Pos);
        return -1;
    }
    return L->data[Pos];
}

重置顺序表

void ClearList (SqListPtr L) {
    L->Length = 0;
}

可视化GIF合集

整体代码复现

// 第一遍顺序表未正确有初始化
    // 查明原因是顺序表长度忘记初始化

#include<stdio.h>
#include<malloc.h>

#define MAX_LLIST_LEN 10
// Idea 0 : 用 C++ 中的模板变量替换 int 变量，提高顺序表可迁移性 
// 先复现代码，后面再实现想法

// 定义顺序表
typedef struct SqList {  // typedef 是为已有的类型创造别名的，而模板是用于创建泛型类型的，因此这里不能使用 typedef
    int Length;
    int data[MAX_LLIST_LEN];
} *SqListPtr;  // 为什么这里申明的是一个指针？

// 输出顺序表
void OutPutList (SqListPtr L) {
    for (int i = 0; i < L->Length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\r\n");  // \r 是回车符的转义符 建议只使用\n
}

// 输出顺序表中元素的 position
void OutPutListPos (SqListPtr L) {
    printf("the position of structure is : %ld\n",L);
    for (int i = 0; i < L->Length; i++) {
        printf("the position of data [%d] is %ld\n",i,&L->data[i]);
    }
    printf("\n");  
}

// 初始化顺序表
SqListPtr InitList (int *ParaData, int ParaLen ) {
    SqListPtr ResultPtr = (SqListPtr)malloc(sizeof(struct SqList));
    for (int i = 0; i < ParaLen; i++) {
        ResultPtr->data[i] = ParaData[i];
    }
    ResultPtr->Length = ParaLen;
    return ResultPtr;
}
// 为什么分配内存后转化为 SqListPtr 而不是 SqList ？ 二者不都是结构体吗？
// SqListPtr 是一个指向结构体的指针类型
// SqList 是一个结构体类型
// malloc返回的是一个void* 类型的指针，需要在使用时显式转化为其它类型的指针
    // （转化后编译器才能知道其指向的数据结构布局，就能进行对应的偏移计算和访问操作

void SqListInsert (SqListPtr L, int Pos, int Data) {
    // 三段边界检查
    if(L -> Length >= MAX_LLIST_LEN) {
        printf("Cannot insert element: list full.\n");
        return;
    }

    if (Pos < 0) {
        printf("Cannot insert element: negative position unsupported.");
        return;
    }
 
    if (Pos > L->Length) {
        printf("Cannot insert element: the position %d is bigger than the list length %d.\r\n", Pos, L->Length);
        return;
    }

    // 腾位置
    for(int i = L->Length; i > Pos; i--) {
        L->data[i] = L->data[i - 1];
    }

    L->data[Pos] = Data;
    L->Length++;
}

void SqListInsertTest () {
    int i;
	int tempArray[5] = {3, 5, 2, 7, 4};

    printf("---- sequentialInsertTest begins. ----\r\n");

	// 初始化数据
    SqListPtr tempList = InitList(tempArray, 5);
    printf("After initialization, the list is: ");
	OutPutList(tempList);

	// 8，3, 5, 2, 7, 4
    printf("Now insert to the first, the list is: ");
	SqListInsert(tempList, 0, 8);
	OutPutList(tempList);

	// 8，3, 5, 2, 7, 4，9
    printf("Now insert to the last, the list is: ");
	SqListInsert(tempList, 6, 9);
	OutPutList(tempList);

	// 8，3, 5, 2, 7, 4，9
    printf("Now insert beyond the tail. \r\n");
	SqListInsert(tempList, 8, 9);
    printf("The list is:");
	OutPutList(tempList);

	// 10 11 12 13 14 8 3 5 2 7
	for (i = 0; i < 5; i ++) {
		printf("Inserting %d.\r\n", (i + 10));
		SqListInsert(tempList, 0, (i + 10));
		OutPutList(tempList);
	}

    printf("---- sequentialInsertTest ends. ----\r\n");
}

int SqListDelete (SqListPtr L, int Pos) {
    if (Pos < 0) {
        printf("Invalid position: %d.\r\n", Pos);
        return -1;
    }

    int ResultValue = L->data[Pos];

    if (Pos >= L->Length) {
        printf("Cannot delete element: the position %d is beyond the list length %d.\r\n", Pos, L->Length);
        return -1;
    }

    L -> Length--;
    return ResultValue;  // 返回被删除的元素
}

void SqListDeleteTest () {
    int tempArray[5] = {3, 5, 2, 7, 4};

    printf("---- sequentialDeleteTest begins. ----\r\n");

	// Initialize.
    SqListPtr tempList = InitList(tempArray, 5);
    printf("After initialization, the list is: ");
	OutPutList(tempList);

	// Delete the first.
    printf("Now delete the first, the list is: ");
	SqListDelete(tempList, 0);
	OutPutList(tempList);

	// Delete to the last.
    printf("Now delete the last, the list is: ");
	SqListDelete(tempList, 3);
	OutPutList(tempList);

	// Delete the second.
    printf("Now delete the second, the list is: ");
	SqListDelete(tempList, 1);
	OutPutList(tempList);

	// Delete the second.
    printf("Now delete the 5th, the list is: ");
	SqListDelete(tempList, 5);
	OutPutList(tempList);

	// Delete the second.
    printf("Now delete the (-6)th, the list is: ");
	SqListDelete(tempList, -6);
	OutPutList(tempList);

    printf("---- sequentialDeleteTest ends. ----\r\n");

	OutPutListPos(tempList);
}

// 定位给定的数据在顺序表中的位置
int LocateElement(SqListPtr L, int Data) {
    for (int i = 0; i < L->Length; i++) {
        if (L->data[i] == Data) {
            return i;
        }
    }
    return -1;
}

// 获取顺序表指定位置的数据
int GetElement(SqListPtr L, int Pos) {
    if (Pos < 0 || Pos >= L->Length) {
        printf("Invalid position: %d.\r\n", Pos);
        return -1;
    }
    return L->data[Pos];
}

void ClearList (SqListPtr L) {
    L->Length = 0;
}

int main() {
	SqListInsertTest();
	SqListDeleteTest();
}

输出结果

PS D:\a_study\code_vs\DataStructure\SequenceList> gcc -o kernel code.cpp
PS D:\a_study\code_vs\DataStructure\SequenceList> ./kernel
---- sequentialInsertTest begins. ----
After initialization, the list is: 3 5 2 7 4 
Now insert to the first, the list is: 8 3 5 2 7 4
Now insert to the last, the list is: 8 3 5 2 7 4 9
Now insert beyond the tail.
Cannot insert element: the position 8 is bigger than the list length 7.
The list is:8 3 5 2 7 4 9
Inserting 10.
10 8 3 5 2 7 4 9
Inserting 11.
11 10 8 3 5 2 7 4 9
Inserting 12.
12 11 10 8 3 5 2 7 4 9
Inserting 13.
Cannot insert element: list full.
12 11 10 8 3 5 2 7 4 9
Inserting 14.
Cannot insert element: list full.
12 11 10 8 3 5 2 7 4 9
---- sequentialInsertTest ends. ----
---- sequentialDeleteTest begins. ----
After initialization, the list is: 3 5 2 7 4
Now delete the first, the list is: 3 5 2 7
Now delete the last, the list is: 3 5 2
Now delete the second, the list is: 3 5
Now delete the 5th, the list is: Cannot delete element: the position 5 is beyond the list length 2.
3 5
Now delete the (-6)th, the list is: Invalid position: -6.
3 5
---- sequentialDeleteTest ends. ----
the position of structure is : 2064336
the position of data [0] is 2064340
the position of data [1] is 2064344

过程记录

按照自己的变量命名方式对代码进行复现
理解函数运行方式，对不理解的地方进行注解
博客文章搬运
尝试实现复现过程中产生的想法

拟进行功能添加

用模板变量代替固定类型变量【使用 using 关键字解决 typedef 与模板类型的冲突】

OptimizedVersion

用 C++ 中的模板变量替换 int 变量，提高顺序表可迁移性

由于原代码内容较多，进行全部修改工程量太大，因此只给出部分示例

#include <iostream>
#include<malloc.h>

// 定义最大长度
#define MAX_LLIST_LEN = 100;

// 定义顺序表结构体模板
template <typename T>
struct SqList {
    int Length;
    T data[MAX_LLIST_LEN];
};

// 定义指向 SqList 的指针类型别名
template <typename T>
using SqListPtr = SqList<T>*;

// 初始化顺序表的函数模板
template <typename T>
SqListPtr<T> InitList(int paraLen, const T* paraData) {  // const T* 表示函数内部不能修改该指针的数据
    SqListPtr<T> resultPtr = new SqList<T>;
    resultPtr->Length = paraLen;
    for (int i = 0; i < paraLen; ++i) {
        resultPtr->data[i] = paraData[i];
    }
    return resultPtr;
}

// 打印顺序表的函数模板
template <typename T>
void PrintList(SqListPtr<T> list) {
    for (int i = 0; i < list->Length; ++i) {
        std::cout << list->data[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    int intData[] = {1, 2, 3, 4, 5};
    SqListPtr<int> intList = InitList(5, intData);
    PrintList(intList);
    delete intList;

    double doubleData[] = {1.1, 2.2, 3.3, 4.4, 5.5};
    SqListPtr<double> doubleList = InitList(5, doubleData);
    PrintList(doubleList);
    delete doubleList;

    return 0;
}

Points

顺序表是顺序储存结构

顺序表是顺序储存结构不是链表

使用 using 关键字

typedef 是 C 语言引入的特性，设计初衷并非用于处理模板类型，只能定义具体类型的别名

而 C++ 中引入的 using 关键字，则可以解决 typedef 与模板变量的冲突

新知

const T* 的使用

const T* paraData 将数据的地址传入函数，避免变量的复制开销，并且限制函数内部不能修改指针所指向的数据。

程序优化时候可以注意一下这一点【已并入优化知识】

Thinking

what – 什么是顺序表, 在现实世界中有哪些顺序表的例子？

将线性表的数据元素按其逻辑顺序依次存储在一段连续的存储空间中的数据结构

现实生活中的例子：

花名册
路线表
值班表
考试排名表

why – 为什么学习顺序表？

顺序表是理解线性数据结构的基础

学习顺序表能够构建数据结构学习的起点

how – 在现实世界中, 如何管理、操纵这些顺序表?

按照需求进行单链表的结构体设置以及基本操作

单链表的基本操作有：定义、初始化、插入、删除、查找

END

Post Views: 426

简介