数据结构——顺序表、链表

目录

前言

一，数据结构

1，什么是数据结构？

2，有什么类型？

二，顺序表

1，线性表

2，顺序表基本结构

3，动态顺序表的功能实现

三，链表 

1，链表的分类

2，（单向）链表

3，双向链表

---

前言

当我们将要对大量相同类型的数据进行存储与操作时，使用通常的定义变量方式会太过机械重复，数据使用起来又太过耗时，此时用上数据结构就会更加便捷。

一，数据结构

1，什么是数据结构？

       数据结构的定义可以从“数据”和“结构”两部分来解释，数据指的是常见的数字、形形色色的信息等等。结构则是对数据的组织方式，数据结构将大量数据有规律的存储起来便于下次的数据操作（继续存储或使用等等）。

总结：数据结构是计算机对数据进行存储与组织的一种方式。

2，有什么类型？

数据结构具有许多类型，常见如下： 

1. 数组（Array）（又可称为顺序表）：一种基础的数据结构，可以在内存中连续存储多个元素，这些元素通常是相同类型的数据。数组的特点是可以通过索引快速访问元素，但大小固定，扩展性差。

2. 链表（Linked List）：由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表的优点在于可以动态地分配内存，易于插入和删除操作。

3. 栈（Stack）：遵循后进先出（LIFO）原则的数据结构。栈的操作主要是压栈（push）和出栈（pop）。

4. 队列（Queue）：遵循先进先出（FIFO）原则的数据结构。队列的操作主要是入队（enqueue）和出队（dequeue）。

5. 树（Tree）：一种分层数据结构，由节点组成，每个节点包含数据元素和若干指向其子节点的指针。特殊的树结构包括二叉树、平衡树（如AVL树）、二叉查找树等。

6. 图（Graph）：由顶点（节点）集合和边集合组成，边可以是有向的也可以是无向的。图用于表示物件之间多对多的关系。

7. 哈希表（Hash Table）：通过哈希函数将键映射到表中一个位置来访问记录，这种数据结构可以提供快速的插入和查找操作。

8. 堆（Heap）：一种特殊的完全二叉树，常用于实现优先队列，分为最大堆和最小堆。

 以上即为常用的数据结构，在使用时，要区别不同的使用场景，以便更好地提升程序的效率与性能。

以下我们主讲顺序表与链表：

二，顺序表

声明：在中文的计算机科学教材和文献中，“顺序表”是一个常用的术语，而在英文中，它通常被称为“Array”或者“Linear Array”。因此，当提到数组时，实际上就是在讨论顺序表。

1，线性表

       实际上，顺序表属于线性表的一种，线性表定义是：n个具有相同特性的数据元素的有限序列；线性表还包括链表、栈、队列、字符串等等，从上述举例我们可以得出线性表的一些特性：

1. 对于数据的获得可以依照某些顺序依次获得。
2. 对于数据的存放却不一定有规律

总结：线性表在逻辑上是线性结果（因为数据可以依次操作，像一条连续的线）；在物理结构上却不一定连续（实际上不是所有数据都连续存放），在物理上存储时，通常以数组（物理上连续）和链式结构（物理上不连续）的形式存储。

2，顺序表基本结构

       我们知道，顺序表的英文是 “Sequential List”。在计算机科学中，它通常指的是一种线性数据结构，其中元素按照一定的顺序排列，可以通过索引直接访问。在某些情况下，也被称为 “Array” 或 “ArrayList”。顺序表与数组英文一致，为什么如此呢？

实际上，顺序表的底层结构就是数组，即对数组进行封装，实现了增删查改的功能接口。

那么，顺序表是怎样的呢？

 顺序表依据其存储空间是否可以变化可以分为：静态顺序表和动态顺序表两种。

静态顺序表：

静态顺序表的缺点：数据可存储的空间在程序开始时就固定了，空间设置太小不够用，太大又会造成浪费。

 

动态顺序表：

注意：

       1，可能有人有疑问，上图中的 a 仅是一个指针，与数组无关，并且没有创建数组，但这里因为数组的指针的加减是一样的，就把指针当成数组来操作。

        2，尤其要了解的是，因为是数组操作，数组内的数据是连续存放的（顺序存放），依次进行数据的增删查改时尤其要注意位置的改变。

3，动态顺序表的功能实现

    扩容：凭借有效数据个数与容量做对比来考虑是否扩容，扩容一般扩容2/3倍（由数学推理而来）扩容后数据要重新移动到新数组里。；

    插入数据：一般是顺序插入（在尾部插入），要头插时，则需要移动全部数据位置，量大时，十分费时费力（一般考虑链表）；

    删除数据：分为两类，对于尾部的数据可以直接 size - 1（因为对数据查询是依靠size来寻找的），在除尾部之外的地方删除则要将其后的数据向前移一位。

代码如下：（有几个要点，扩容时要检验是否成功，扩容后要释放原有内存，删除时要检验是否有数据，）

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDatatype;
typedef struct Seqlist//̬˳
{SLDatatype* arr;int size;int capacity;
}SL;void SLInit(SL *ps);
void SLDestory(SL* ps);
//void memorycheck(ps);
void SLPushBack(SL* ps, SLDatatype x);
void SLPushFront(SL* ps, SLDatatype x);
void popback(SL* ps);
void popfront(SL* ps);
void SLTnsert(SL* ps, int pos, SLDatatype x);
void SLErase(SL* ps, int pos);
int find(SL* ps, int pos);
void SLPrint(SL s);

 功能实现文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"
//初始化实现
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}
//销毁实现
void SLDestory(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
//尾插实现
void SLPushBack(SL* ps, SLDatatype x)
{//插入数据之前先看空间够不够assert(ps);if (ps->capacity == ps->size){//申请空间int Newcapacity=ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* pf= realloc(ps->arr, ps->capacity * sizeof(SLDatatype));//多大空间呢？if (pf == NULL){perror("realloc");exit(1);}ps->arr = pf;ps->capacity = Newcapacity;}//插入ps->arr[ps->size] = x;ps->size++;
}
//头插
void SLPushFront(SL* ps, SLDatatype x)
{//插入数据之前先看空间够不够assert(ps);if (ps->capacity == ps->size){//申请空间int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* pf = realloc(ps->arr, ps->capacity * 2 * sizeof(SLDatatype));//多大空间呢？if (pf == NULL){perror("realloc");exit(1);}ps->arr = pf;ps->capacity = Newcapacity;}//插入//整体移动x位for (int i = ps->size; i>=1; i--){ps->arr[1] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;}
//尾删
void popback(SL*ps)
{assert(ps);assert(ps->size);--ps->size;
}
//头删
void popfront(SL* ps)
{assert(ps);assert(ps->size);for (int i = 0; i<ps->size; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
//在指定位置之前插入
void SLTnsert(SL* ps, int pos, SLDatatype x)
{assert(ps);assert(pos >= 0&&pos<=ps->size);if (ps->capacity == ps->size){//申请空间int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* pf = realloc(ps->arr, ps->capacity * 2 * sizeof(SLDatatype));//多大空间呢？if (pf == NULL){perror("realloc");exit(1);}ps->arr = pf;ps->capacity = Newcapacity;}//插入for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;}
//删除指定位置的数
void SLErase(SL* ps, int pos)
{/*判断相关数据*/{assert(ps);assert(pos >= 0 && pos < ps->size);if (ps->capacity == ps->size){//申请空间int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* pf = realloc(ps->arr, ps->capacity * 2 * sizeof(SLDatatype));//多大空间呢？if (pf == NULL){perror("realloc");exit(1);}ps->arr = pf;ps->capacity = Newcapacity;}}for (int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];ps->size--;}
}
//查找数据
int find(SL* ps, int pos)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] = pos){return i;}}return -1;
}
//测试
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");
}

 功能运行文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"
void SLTest01()
{SL sl;//sl˳SLInit(&sl);//ʼSLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);//SLPushBack(&sl, 6);//SLPushBack(&sl, 7);SLPrint(sl);//SLErase(&sl, 0);}
int main()
{SLTest01();return 0;
}

三，链表 

 通过顺序表的学习我们可以发现顺序表有许多缺点：

• 在顺序表中插入与删除数据要移动大量数据（数据量大时），复杂度为O(n)；
• 增容需要申请新空间，拷贝数据，释放旧空间会有不小的消耗。
• 增容⼀般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

此时便要使用链表来避免这些问题。 

1，链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2x2x2）链表结构：

单向与双向、带不带头结点、是否循环。

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表

1. 无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

下面我们介绍带头单向不循环链表（称为链表）和带头双向循环链表 。

2，（单向）链表

 链表属于线性表的一种，在逻辑上是连续的但物理结构上不一定连续。

基本结构：

示意图：

 

 基本原理是，设置一个头结点 （plist），它是一个指针指向下一个节点，而下一个节点有存储着一个数据和一个指针，该指针又指向下一个节点，依次往复，直到最后一个节点，它的指针没有指向的对象，便指向空指针（NULL），使用指针访问其中的数据（值得注意的是它是单向的）。

 注意：

1. 节点（与结点一种意思），节点包括要保存的数据和下一节点的地址（指针）
2. 节点⼀般是从堆上申请的，而从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。因此链表的物理结构不一定连续。

实现链表：

增删查改的要点，对于函数的使用要注意分辨要不要用上二级指针；使用完之后要销毁链表。

简要说明链表销毁的原因：

1. 避免内存泄漏：动态分配的内存如果不手动释放，可能导致内存浪费。
2. 防止野指针：已释放的内存如果不更新指针，可能导致程序访问非法内存。
3. 提高内存利用率：及时释放内存可以让操作系统重新分配给其他需要的地方。

删除，分为头删，尾删，中间删，获得其前节点改变其指针指向下一节点或空指针（不要忘记释放相应空间）。

插入，分为头插，尾插，中间插，只需要创建一个新节点，再修改其前后结点指针的指向即可。

查找与修改，一般是利用循环和 if 函数与查找对象比较，然后进行相关操作。 

代码如下： 

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}// 在链表头部插入节点
void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);newNode->next = *head;*head = newNode;
}// 在链表尾部插入节点
void insertAtTail(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}Node* current = *head;while (current->next != NULL) {current = current->next;}current->next = newNode;
}// 在链表中间插入节点（在值为prevData的节点之后插入）
void insertInMiddle(Node** head, int prevData, int data) {Node* current = *head;while (current != NULL && current->data != prevData) {current = current->next;}if (current == NULL) {printf("找不到值为 %d 的节点\n", prevData);return;}Node* newNode = createNode(data);newNode->next = current->next;current->next = newNode;
}// 删除链表头节点
void deleteAtHead(Node** head) {if (*head == NULL) {printf("链表为空，无法删除头节点\n");return;}Node* temp = *head;*head = (*head)->next;free(temp);
}// 删除链表尾节点
void deleteAtTail(Node** head) {if (*head == NULL) {printf("链表为空，无法删除尾节点\n");return;}Node* current = *head;Node* prev = NULL;while (current->next != NULL) {prev = current;current = current->next;}if (prev != NULL) {prev->next = NULL;}else {*head = NULL;}free(current);
}// 删除链表中间的节点（删除值为data的节点）
void deleteInMiddle(Node** head, int data) {if (*head == NULL) {printf("链表为空，无法删除节点\n");return;}Node* current = *head;Node* prev = NULL;while (current != NULL && current->data != data) {prev = current;current = current->next;}if (current == NULL) {printf("找不到值为 %d 的节点\n", data);return;}if (prev != NULL) {prev->next = current->next;}else {*head = current->next;}free(current);
}// 打印链表
void printList(Node* head) {Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}// 释放链表内存
void freeList(Node** head) {Node* current = *head;Node* next;while (current != NULL) {next = current->next;free(current);current = next;}*head = NULL;
}// 主函数
int main() 
{Node* head = NULL;// 插入节点insertAtHead(&head, 30);insertAtTail(&head, 40);insertInMiddle(&head, 30, 35);printList(head); // 应该打印 30 -> 35 -> 40 -> NULL// 删除节点deleteAtHead(&head);printList(head); // 应该打印 35 -> 40 -> NULLdeleteAtTail(&head);printList(head); // 应该打印 35 -> NULLinsertAtTail(&head, 40);insertAtTail(&head, 50);printList(head); // 应该打印 35 -> 40 -> 50 -> NULLdeleteInMiddle(&head, 40);return 0;
}

3，双向链表 

typedef struct DoublyLinkedListNode {int data;                         //存储的数据struct DoublyLinkedListNode* prev;//前一节点地址struct DoublyLinkedListNode* next;//后一节点地址
} Node;

 head 即头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”

“哨兵位”存在的意义： 遍历循环链表避免死循环。

优点：避免遍历链表

实现代码如下：

#include <stdio.h>
#include <stdlib.h>// 定义双向链表的节点结构体
typedef struct DoublyLinkedListNode {int data;struct DoublyLinkedListNode* prev;struct DoublyLinkedListNode* next;
} Node;// 创建一个新的节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (!newNode) {return NULL;}newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;
}// 在链表尾部添加节点
void appendNode(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;newNode->prev = temp;
}// 在链表头部添加节点
void prependNode(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}newNode->next = *head;(*head)->prev = newNode;*head = newNode;
}// 删除节点
void deleteNode(Node** head, Node* delNode) {if (*head == NULL || delNode == NULL) {return;}if (*head == delNode) {*head = delNode->next;}if (delNode->next != NULL) {delNode->next->prev = delNode->prev;}if (delNode->prev != NULL) {delNode->prev->next = delNode->next;}free(delNode);
}// 打印链表
void printList(Node* node) {while (node != NULL) {printf("%d ", node->data);node = node->next;}printf("\n");
}// 释放链表内存
void freeList(Node* head) {Node* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}// 主函数
int main() {Node* head = NULL;appendNode(&head, 10);appendNode(&head, 20);appendNode(&head, 30);prependNode(&head, 5);printList(head); // 应该打印 5 10 20 30// 删除节点Node* delNode = head->next; // 删除第二个节点deleteNode(&head, delNode);printList(head); // 应该打印 5 20 30// 释放链表内存freeList(head);return 0;
}