数据结构：线性表

1、线性表概述

1.1线性表的定义

线性表（list）：零个或多个数据元素的有限序列。

简单地来说，我们可以用下面这张图来描述一个线性表：

1.2 线性表的存储结构

1.2.1顺序存储结构——顺序表

顺序表是将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。

1.2.2链式存储结构——链表

链表不强制要求数据在内存中集中存放，各个元素可以分散存放在内存中。 

2、顺序表

2.1顺序表的定义

它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使逻辑上相邻的两个

元素在物理位置上也相邻。

接下来我们用代码进行描述：

#define LIST_MAX_NUM 100
typedef struct
{int list[LIST_MAX_NUM];int len;
}Linear_List_Type;Linear_List_Type mylist;

这段代码定义了一个结构体类型 Linear_List_Type，并创建了一个该类型的变量 mylist。

代码解析：

1. typedef struct { ... } Linear_List_Type;：这行代码定义了一个结构体，并使用 typedef 为该结构体起了一个别名 Linear_List_Type。这意味着在以后使用 Linear_List_Type 这个名字就代表了这个结构体类型。

2. int list[LIST_MAX_NUM];：这是一个整数数组，数组的长度是 LIST_MAX_NUM，这个宏应该在其他地方定义过，用来表示数组的最大长度。

3. int len;：这是一个整数变量，用来存储数组中当前有效元素的数量，也就是线性表的长度。

4. Linear_List_Type mylist;：这行代码定义了一个名为 mylist 的变量，类型是 Linear_List_Type，也就是前面定义的结构体类型。mylist 代表一个具体的线性表实例。

2.2顺序表的基本操作

2.2.1初始化

初始化操作的意义：

• 该函数将传入的线性表的长度 len 设置为 0，从而将线性表重置为空状态。
• 在数据结构中，初始化操作是确保线性表在使用之前处于一个已知的、正确的状态。这通常是使用线性表的第一步操作。

void InitList(Linear_List_Type* p)
{p->len = 0;
}

代码解析：

1. 函数声明 void InitList(Linear_List_Type* p)：

   • void：表示该函数没有返回值。
   • InitList：函数名称，用于初始化线性表。
   • Linear_List_Type* p：函数的参数是一个指向 Linear_List_Type 类型的指针 p。这个指针用于指向需要初始化的线性表。

2. p->len = 0;：

   • p->len：通过指针 p 访问线性表结构体中的 len 成员。
   • =：赋值运算符。
   • 0：将 len 设置为 0。
   • 这一步将线性表的长度初始化为 0，表示线性表为空，没有有效元素。

 2.2.2插入

假设线性表的存储空间为V[1:m]，表长为n，插入位置i，插入元素b，则代码如下：

void InsertList(Linear_List_Type* p, int m, int i, int b)
{int k;if (p->len == m){printf("overflow");return;}if (i > p->len){i = p->len + 1;}else if (i < 1){i = 1;}for (k = p->len; k >= i; k--){p->list[k] = p->list[k - 1];}p->list[i - 1] = b;p->len += 1;
}

• 参数说明：

  • 线性表的指针用于操作目标线性表。
  • 参数包括线性表的最大容量、插入位置、以及要插入的元素。

• 判断线性表是否已满：

  • 首先检查线性表当前长度是否已达最大容量，如果已满，打印“overflow”提示并退出函数，防止溢出错误。

• 调整插入位置：

  • 检查插入位置是否超出当前长度，如果插入位置大于当前长度，将位置调整为表的末尾。
  • 如果插入位置小于 1，则将插入位置调整为第一个位置。

• 移动元素腾出插入空间：

  • 从线性表的最后一个元素开始，逐个向后移动元素，为插入新元素腾出空间。

• 插入新元素：

  • 将新元素插入到调整好的位置。

• 更新线性表长度：

  • 插入后，更新线性表的长度以反映新的元素数量。

2.2.3删除

void DeleteList(Linear_List_Type* p, int i)
{int k;if (p->len == 0){printf("underflow");return;}if (i<1 || i>p->len){printf("this element is not in the list");return;}for (k = i; k < p->len; k++){p->list[k - 1] = p->list[k];}p->len -= 1;return;
}

步骤解析：

1. 函数定义与参数说明：

   • Linear_List_Type* p：指向线性表的指针，操作的目标是这个线性表。
   • int i：表示要删除的元素的位置，从 1 开始计数。

2. 检查线性表是否为空：

   • if (p->len == 0)：判断线性表是否为空，即当前长度是否为 0。
   • 如果线性表为空，则打印 "underflow" 提示，表示删除操作无法进行，并立即返回。

3. 检查删除位置是否有效：

   • if (i < 1 || i > p->len)：判断插入位置是否超出有效范围。
     • 如果 i 小于 1 或大于当前线性表的长度，说明删除位置无效。
     • 打印 "this element is not in the list" 提示，并退出函数。

4. 移动元素填补空位：

   • for (k = i; k < p->len; k++)：从删除位置 i 开始，将其后的元素依次向前移动。
   • p->list[k - 1] = p->list[k];：将第 k 位置的元素移动到 k-1 位置，逐步覆盖被删除的元素位置。

5. 更新线性表的长度：

   • p->len -= 1;：删除元素后，线性表的长度减少 1。

6. 函数返回：

   • return;：结束函数，返回到调用者。

总结：