数据结构与算法（二）——线性表
今天我们来聊一聊逻辑结构中的线性结构，即线性表。线性表是一对一的逻辑结构。
对于非空的线性表和线性结构，其特点如下：
- 存在唯一的一个被称为“第一个”的数据元素
- 存在唯一的一个被称为“最后一个”的数据元素
- 除了第一个之外，结构中的每个数据元素均有一个前驱
- 除了最后一个之外，结构中的每个数据元素都有一个后继
接下来我将从顺序存储和链式存储这两个物理结构来讲解线性表。
一、线性表的顺序存储
所谓顺序存储，就是开辟一段连续的内存空间来存储。因此，线性表的顺序存储，其逻辑相邻，物理存储地址也相邻。
顺序存储的线性表的初始化、插入、查找、删除等操作的实现如下：
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define MAX_SIZE 100 // 顺序表的最大容量
// ElementType是线性表中的元素类型，根据具体情况而定，这里假定为int
typedef int ElementType;
// Status为函数的执行结果的类型
typedef enum : int {
OK,
Error,
} Status;
//顺序表的结构
typedef struct {
ElementType *data;
int length;
}SequenceTable;
// 1，顺序表的初始化
Status initTable(SequenceTable *table) {
// 为顺序表分配一个大小为MAX_SIZE的数组空间
table->data = malloc(sizeof(ElementType) * MAX_SIZE);
// 如果存储空间分配失败，那么就返回错误
if (!table->data) {
return Error;
}
// 空表的长度初始化为0
table->length = 0;
return OK;
}
// 2，顺序表的插入
// 能够插入成功的条件是：0<=index<=table.length
// 操作动作为：在table中第index个位置之前插入数据元素element，并且table的长度加1
Status insert(SequenceTable *table, int index, ElementType element) {
// 验证index的合法性
if (index < 0 || index > table->length) {
return Error;
}
// 判断是否存储空间已满
if (table->length == MAX_SIZE) {
return Error;
}
// 如果插入位置不在表尾，那么就需要将当前插入位置及其后面的所有元素都后移一个位置
if (index <= table->length - 1) {
for (int i = table->length - 1; i >= index; i--) {
table->data[i+1] = table->data[i];
}
}
// 将新元素放在第index个位置上
table->data[index] = element;
// 长度+1
table->length++;
return OK;
}
// 3，顺序表的取值
Status getElement(SequenceTable *table, int index, ElementType *element) {
// 判断index坐标是否合理
if (index < 0 || index > table->length -1) {
return Error;
}
// 取出对应坐标下的数据
*element = table->data[index];
return OK;
}
// 4，删除顺序表中指定元素
Status delete(SequenceTable *table, int index) {
// 判断index的合法性
if (index < 0 || index > table->length -1) {
return Error;
}
// 将后面的元素向前移一位
for (int i = index; i < table->length; i++) {
table->data[i] = table->data[i+1];
}
table->length--;
return OK;
}
// 5，清空顺序表
Status clearTable(SequenceTable *table) {
table->length = 0;
return OK;
}
// 6，顺序输出表内容
Status printTable(SequenceTable table) {
for (int i = 0; i < table.length; i++) {
printf("%d\n", table.data[i]);
}
return OK;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
SequenceTable table;
Status initStatus = initTable(&table);
printf("初始化线性顺序表，表长度：%d，初始化结果：%d\n", table.length, initStatus);
Status insertStatus = insert(&table, 0, 222);
printf("插入数据，插入的结果为%d，插入后的表长度为%d\n", insertStatus, table.length);
printTable(table);
ElementType element1;
Status checkStatus = getElement(&table, 0, &element1);
printf("查找数据，查找的结果为%d，查找到的元素为%d\n", checkStatus, element1);
Status deleteStatus = delete(&table, 0);
printf("删除数据，删除的结果为%d\n", deleteStatus);
Status clearStatus = clearTable(&table);
printf("清空线性表，清空的结果为%d\n", clearStatus);
return 0;
}二、线性表的链式存储
线性表的链式存储，其逻辑相邻，但是物理地址不相邻。
链式存储是有节点的概念的，如下：
可以看到，一个节点是由一个数据域和一个指针域组成的。线性表的链式存储，其最大的特点就是，在内存空间上它是不连续的，他们各个数据元素之间是通过指针域进行关联起来的。
本篇章我将以单链表的形式讲解线性表的链式存储。
单链表初始化
//
// main.c
// 线性表的链式存储
//
// Created by 拉维 on 2022/3/8.
//
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define MAX_SIZE 100 // 顺序表的最大容量
// ElementType是线性表中的元素类型，根据具体情况而定，这里假定为int
typedef int ElementType;
// Status为函数的执行结果的类型
typedef enum : int {
OK,
Error,
} Status;
// Node为链式结构中的节点
typedef struct Node {
ElementType data; // 数据域
struct Node *next; // 指针域
}Node;
// 定义链表
typedef struct Node * LinkedList;
// 1，初始化单链表
Status initLinkedList(LinkedList *list) {
// 初始化的时候要生成头结点
*list = malloc(sizeof(Node));
if (*list == NULL) {
return Error;
}
// 将头节点的指针域置为空
(*list)->next = NULL;
return OK;
}
可以看到，我在初始化单链表的时候，生成了一个头结点，并且头结点的指针域值为NULL。那么什么是头结点？头结点又有什么作用呢？
在设计单链表的时候，可以在链表的首位加一个头结点，双向链表和循环链表不需要。
在单链表中加入了头结点之后，便于对单链表中的首元结点进行操作（删除、插入），不然的话，我每一次操作单链表中元素的时候，都需要判断是否是首元结点（链表中第一个带有值的节点），因为当单链表的指针是指向首元结点的时候，如果是操作的首元结点，那么我还需要额外对链表的指针的指向做特殊处理。
单链表的遍历打印
// 2，打印单向链表
Status printList(LinkedList list) {
// 注意，一开始要指向首元结点，而不是指向头结点，不然的话就把头结点也给打印出来了。
LinkedList node = list->next;
while (node) {
printf("%d\n", node->data);
node = node->next;
}
return OK;
}由于单链表中最后一个节点的指针域是指向NULL，所以我们通过遍历逐个拿到各个节点的next，直到某一个next为空为止。
需要注意的是，第一个节点要给初始化为首元结点，也就是头结点的next。如果第一个节点设置为头结点，那么就会把头结点也给打印出来了。
单链表的插入
// 3，单向链表的插入
Status insert(LinkedList *list, int index, ElementType element) {
// 寻找第index-1个节点
int i = 1;
LinkedList lastNode = *list;
while (lastNode && i < index) {
lastNode = lastNode->next;
i++;
}
// 第index个节点没有前驱
if (!lastNode) {
return Error;
}
// 生成一个新的节点
LinkedList newNode = malloc(sizeof(Node));
// 给新节点数值域赋值
newNode->data = element;
// 给新节点指针域赋值（将上一个节点的后继节点赋值过来）
newNode->next = lastNode->next;
// 更新上一个节点的后继节点
lastNode->next = newNode;
return OK;
}单链表的一大优势就是很容易做插入，它的插入很简单，无非就是找到要插入位置的上一个节点，然后修改其后继节点即可。但是如何找到要插入位置的上一个节点是很麻烦的，其实单链表插入的时间复杂度主要是体现在遍历查找要插入位置的上一个节点上。
单链表的查找与删除
// 4，单向链表的取值
Status getElement(LinkedList list, int index, ElementType *element) {
// 遍历找到指定位置的节点
int i = 1;
LinkedList node = list;
while (node && i <= index) {
node = node->next;
i++;
}
// 如果该位置节点不存在，则报错
if (!node) {
return Error;
}
*element = node->data;
return OK;
}
// 5，单向链表删除元素
Status deleteElement(LinkedList *list, int index, ElementType *deletedElement) {
// 找到指定位置的前驱节点
LinkedList lastNode = (*list);
int i = 1;
while (i < index && lastNode) {
lastNode = lastNode->next;
i++;
}
// index的有效范围校验
if (index <= 0 || lastNode) {
return Error;
}
//由前驱结点找到待删除节点
LinkedList currentNode = lastNode->next;
// 将待删除节点的后继赋值给前驱结点的后继
lastNode->next = currentNode->next;
// 将删除的节点值传递出去
*deletedElement = currentNode->data;
// 释放内存
free(currentNode);
return OK;
}这里需要注意的是，一定要注意内存的释放，否则会造成内存泄漏。看到这里你可能会有个疑问，为啥顺序表删除元素的时候没有进行free，而这里却需要free呢？原因就在于，顺序表的内存空间是提前开辟好的，你删除顺序表中的某一个元素是不会影响到该顺序表所分配的内存空间的，只有当整个顺序表被销毁的时候其所占内存空间才会被销毁；而链表中每一个元素的内存空间都是单独开辟的，所以也需要单独销毁。
单链表的清空
// 6，清空单项链表
Status clearList(LinkedList *list) {
LinkedList node = (*list)->next; // 初始化为首元结点
LinkedList tempNode;
// 只要node不为空，就说明还没有遍历完，就要一直遍历
while (node) {
tempNode = node;
free(node);
node = tempNode->next;
}
// 最后需要将头结点的指针域置空
(*list)->next = NULL;
return OK;
}线性表-单链表的头插法/前插法
所谓头插法，指的就是新加的元素加入到单链表的首元结点的位置。
代码如下：
// 单链表前插法(一直将新元素插入到单链表的首元结点的位置)
void createLinkedListByHead(LinkedList *list, int count) {
//创建一个带有头结点的单向链表
*list = malloc(sizeof(Node));
(*list)->next = NULL;
//循环加入随机数据（前插）
LinkedList tempNode;
for (int i = 0; i < count; i++) {
// 创建新节点
tempNode = malloc(sizeof(Node));
tempNode->data = i;
tempNode->next = (*list)->next;
// 将新的节点插入到头结点
(*list)->next = tempNode;
}
}线性表-单链表的尾插法/后插法
所谓尾插法，指的就是新加入的元素加入到单链表的最后位置
代码如下：
// 单链表后插法（一直将新元素插入到单链表的最后面）
void createLinkedListByTail(LinkedList *list, int count) {
// 创建一个带有头结点的单向链表
*list = malloc(sizeof(Node));
(*list)->next = NULL;
// 记录单链表中最后一个元素
LinkedList lastNode = (*list);
// 循环加入随机数据（后插）
for (int i = 0; i < count; i++) {
// 新建节点
LinkedList newNode = malloc(sizeof(Node));
newNode->data = i;
newNode->next = NULL;
// 将新节点放到最后一个节点后面
lastNode->next = newNode;
// 将当前新节点定义为单链表的最后一个节点
lastNode = newNode;
}
}以上。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-03-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读