第1章 顺序表和单链表

本文主要是介绍第1章 顺序表和单链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 基本概念

数据结构是一门研究如何有效组织数据，并提高数据处理效率的学科。通过研究各种数据内 部的逻辑关系，使用某种特定的存储形式，并在此基础上对数据实施各种操作，这些工作被 称为称为广义上的算法。

逻辑结构

指数据之间的内在关系。通常有集合、线性表、树、图等常见的逻辑结构。

逻辑结构是数据之间本身的属性，跟我们怎么处理它们无关。

线性关系：各个元素之间是一种一对一的关系，比如图书馆中的书架的书，除了首尾两本书 之外，其余的任意一本书的编号假设是N，都有且仅有一个直接前驱节点N-1，有且仅有一个 直接后继节点N+1。这种关系就是典型的线性逻辑。

非线性关系：与上述线性关系的表述不同，如果各个元素之间不是严格一对一的关系，则被 称为非线性关系，比如家族中的各个成员、不同城市间的交通道路等，对于它们中间的某个 元素，都可能有不止一个元素与之关联。这种关系是典型的非线性逻辑。

存储形式

数据的存储方式。比如顺序存储、链式存储等。

不同的存储形式对最终数据的处理效率通常有很大的影响。

逻辑结构与存储形式并无必然联系。

2. 算法分析【了解】

算法分析是指算法在正确的情况下，对其优劣的分析。

一个好的算法通常是指：

1. 算法对应的程序所耗时间少

2. 算法对应的程序所耗存储空间少

3. 算法结构性好、易读、易移植和调试

数据结构与算法的本质任务，是提高程序的时间空间效率，简单讲就是让程序的执行速度越 快越好，所需内存空间越少越好。虽然在很多情况下，程序的时空特性是相互制约的，就像 鱼和熊掌不可兼得，但我们可以根据程序实际解决问题的侧重点，去平衡时间和空间的对性 能的消耗。

2.1 时间复杂度

一般而言，时间复杂度并不考察一段代码运行所需要的绝对时间，因为不同的计算机的硬件 参数不同，考察绝对时间没有意义。时间复杂度一般指的是代码的语句执行总次数，称为语 句频度。比如：

void counting(int n)
{
for(int i=0; i<n; i++)
{
printf("本行语句将会出现n次\n");
for(int j=0; j<n; j++)
{
printf("本行语句将会出现n*n次\n");
}
}
}

在上述代码中，程序执行的语句频度理论是：

但一般情况下，我们只关心多项式的最高次幂，于是上述代码的时间复杂度我们表示为：

这意味着，该程序算法所需要的时间，与传进来的参数n的平方成正比。

不同算法的时间复杂度相差很大，如下图所示，随着所处理的问题规模的增大，不同时间复 杂度的程序所需要的时间有天壤之别。

2.2 空间复杂度

空间复杂度的概念更简单一点，就是一段程序运行时所需的内存字节量。

2.3 时空复杂度互换

一段程序的性能指标，既要运行快速，又要节省内存，而通常这两者又是相互制约的，很难 兼得。因此在实际解决问题时，会根据需要侧重一方，牺牲另一方。

3. 线性表

3.1 概念

对于一组拥有n个数据元素的线性表，其严格数学定义是：其中任何一个数据元素 ，有且仅 有一个直接前驱 ，有且仅有一个直接后继 。首元素 无直接前驱，尾元素 无直接 后继。

满足这种数学关系的一组数据，当中的数据是一个挨着一个的，常被称为一对一关系。反 之，如果数据之间的关系不是一对一的，就是非线性的。

注意： 线性表是一种数据内部的逻辑关系，与存储形式无关 线性表既可以采用连续的顺序存储，也可以采用离散的链式存储

4. 顺序表

4.1 基本概念

顺序表：顺序存储的线性表。

链式表：链式存储的线性表，简称链表。

顺序存储就是将数据存储到一片连续的内存中，在C语言环境下，可以是具名的栈数组，或者 是匿名的堆数组。

存储方式不仅仅只是提供数据的存储空间，而是必须要能体现数据之间的逻辑关系。当采用 顺序存储的方式来存放数据时，唯一能用来表达数据间本身的逻辑关系的就是存储位置。比 如队列中的两个人，小明和小花，如果小明在逻辑上排在相邻的小花的前面，那么在存储位 置上也必须把小明存放在相邻的小花的前面。

4.2 基本操作

顺序表设计

一般而言，为了方便操作顺序表，需要一个专门管理顺序表的”管理结构体“，管理结构体 中一般会包含：

1. 顺序表总容量

2. 顺序表当前最末元素下标位置

3. 顺序表指针

下面是管理结构体示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
typedef struct
{
int capacity; // 顺序表容量
int last; // 最末元素下标
int * data; // 顺序表，以整型数据为例
}sequenceList;

初始化

所谓初始化就是建立一个不包含任何元素的顺序表，设置好管理结构体中的表的总容量、 末元素下标，申请好顺序表内存空间等系列准备工作。

下面是初始化顺序表的示例代码：

sequenceList *init_list(int cap)
{
sequenceList *list = malloc(sizeof(sequenceList));
if(list != NULL)
{
list -> data = malloc(sizeof(int) *cap);
if(list -> data == NULL)
{
free(list);
return NULL;
}
list -> capacity = cap;
list -> last = -1;
}
return list;
}

测试

int main()
{
sequenceList *list = init_list(10);
if(list == NULL)
{
perror("初始化顺序表失败!");
exit(0);
}
else
{
printf("初始化顺序表成功！\n");
}
}

增删节点

在顺序表中增加一个数据，可以有多种方式，比如在原数组的末尾增加，或者在原数组的 头部增加，或者在数组中间任意一个位置增加。根据实际需要来定。

下面以在顺序表头部增删数据为例，示例代码如下：

// 判定顺序表是否为空
bool isEmpty(sequenceList *s)
{
return s->last == -1;
}
// 判定顺序表是否已满
bool isFull(sequenceList *s)
{
return s->last == s->capacity-1;
}
// 在顺序表表头插入一个新数据
bool insert(sequenceList *s, int data)
{
if(isFull(s))
return false;
// 将原有数据全部往后挪一位
for(int i=s->last; i>=0; i--)
s->data[i+1] = s->data[i];
// 将新数据置入表头
s->data[0] = data;
s->last++;
return true;
}
// 将顺序表表头的数据删除掉
bool removeNode(sequenceList *s)
{
if(isEmpty(s))
return false;
// 将所有数据全部往前挪一位
for(int i=0; i<s->last; i++)
s->data[i] = s->data[i+1];
s->last--;
return true;
}

销毁顺序表

一个顺序表最后不再需要，应当要释放其所占用的内存空间，这被称为顺序表的销毁。

下面是销毁操作的示例代码：

void destroy(sequenceList *s)
{
if(s == NULL)
return;
free(s->data);
free(s);
}

4.3 完整代码

seqlist.h

#ifndef __SEQLIST_H
#define __SEQLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdbool.h>
typedef struct
{
int capacity; // 顺序表容量
int last; // 最末元素下标
int *data; // 顺序表，以整型数据为例
} sequenceList;
// 初始化顺序表
sequenceList *init_list(int cap);
// 判断顺序表是否写满
bool isFull(sequenceList *list);
// 向顺序表插入数据
bool insert(sequenceList *s, int data);
// 非空校验
bool isEmpty(sequenceList *list);
// 遍历顺序表
void show(sequenceList *list);
// 删除顺序表数据
bool removeNode(sequenceList *list, int data);
// 释放内存
void destroy(sequenceList *s);
#endif

seqlist.c

#include "seqlist.h"
sequenceList *init_list(int cap)
{
sequenceList *list = malloc(sizeof(sequenceList));
if (list != NULL)
{
list->data = malloc(sizeof(int) * cap);
if (list->data == NULL)
{
free(list);
return NULL;
}
list->capacity = cap;
list->last = -1;
}
return list;
}
bool isFull(sequenceList *list)
{
return list->last == list->capacity - 1;
}
// 在顺序表表头插入一个新数据
bool insert(sequenceList *s, int data)
{
if (isFull(s))
return false;
// 将原有数据全部往后挪一位
for (int i = s->last; i >= 0; i--)
s->data[i + 1] = s->data[i];
// 将新数据置入表头
s->data[0] = data;
s->last++;
return true;
}
// 判断是否为空
bool isEmpty(sequenceList *list)
{
return list->last == -1;
}
// 查看当前顺序表的元素
void show(sequenceList *list)
{
if (isEmpty(list))
{
return;
}
for (int i = 0; i <= list->last; i++)
printf("%d\t", list->data[i]);
printf("\n");
}
// 将顺序表中指定的某个元素删除掉
bool removeNode(sequenceList *list, int data)
{
if (isEmpty(list))
return false;
// 找到要删除的节点的位置
int i, pos = -1;
for (i = 0; i <= list->last; i++)
{
if (list->data[i == data])
{
pos = i;
break;
}
}
// 找不到要删除的元素
if (i > list->last)
{
return false;
}
// 将所有数据全部往前挪一位
for (int i = 0; i < list->last; i++)
list->data[i] = list->data[i + 1];
list->last--;
return true;
}
// 释放内存
void destroy(sequenceList *s)
{
if(s == NULL)
return;
free(s->data);
free(s);
}
int main()
{
// 创建顺序表
sequenceList *list = init_list(10);
if (list == NULL)
{
perror("初始化顺序表失败!");
exit(0);
}
else
{
printf("初始化顺序表成功！\n");
}
// 测试向顺序表插入/删除信息
int n;
while (true)
{
scanf("%d", &n);
if (n > 0)
{
// 插入
if (!insert(list, n))
{
printf("容量已满，插入失败！\n");
continue;
}
}
else if(n < 0)
{
// 删除
if(!removeNode(list,-n))
{
printf("查无此数，删除失败！\n");
continue;
}
}
// 遍历
show(list);
}
// 释放
destroy(list);
}

「课堂练习1」

创建一个顺序表，并从键盘接收数字输入，将输入的正整数按从小到大的顺序插入顺序表，并在输入 负整数的时候将其绝对值数据删除。每次输入后，将顺序表的内容打印到屏幕上。

解析：

此题考查顺序表的基本思路，先要设计好顺序表的逻辑表达，再通过对顺序表的插入和删除操作，体 会顺序存储中对于插入和删除的不便性。

参考代码：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct
{
int total_size; // 顺序表总容量
int last; // 顺序表最末元素的下标
int *data; // 顺序表的存储空间
}sqlist;
// 初始化一个空的顺序表
sqlist * init_list(int total_size)
{
sqlist *sq = (sqlist *)malloc(sizeof(sqlist));
if(sq != NULL)
{
sq->total_size = total_size;
sq->last = -1; // 用-1表征当前没有元素
sq->data = (int *)malloc(sizeof(int) * total_size);
if(sq->data == NULL)
{
free(sq);
}
}
return sq;
}
// 在递增的顺序表中找到x应插入的合适位置
int get_pos(sqlist *sq, int x)
{
int pos = 0;
while((pos<=sq->last) && (sq->data[pos]<x))
pos++;
// 当链表为空（即sq->last为-1时），返回0
return pos;
}
// 判断顺序表是否已满
bool is_full(sqlist *sq)
{
return sq->last >= sq->total_size-1;
}
// 将元素x插入顺序表sq中
bool insert(sqlist *sq, int x)
{
if(is_full(sq))
return false;
// 在顺序表中得到即将要插入的元素x的合适的位置
int pos = get_pos(sq, x);
// 将顺序表中pos往后的所有元素往后挪一位
for(int i=sq->last; i>=pos; i--)
sq->data[i+1] = sq->data[i];
sq->data[pos] = x;
sq->last++;
return true;
}
// 在顺序表sq中，定位元素x
int locate(sqlist *sq, int x)
{
int pos;
for(pos=0; pos<=sq->last; pos++)
{
if(sq->data[pos] == x)
{
printf("data[%d]=%d\n", pos, x);
return pos;
}
}
return -1;
}
// 从顺序表中将元素x剔除
bool delete(sqlist *sq, int x)
{
int pos;
pos = locate(sq, x);
// 元素x不存在
if(pos == -1)
return false;
// 将pos后续的元素全部往前挪一位
for(; pos<=sq->last; pos++)
sq->data[pos] = sq->data[pos+1];
sq->last--;
return true;
}
// 展示顺序表元素
void show_data(sqlist *sq)
{
for(int i=0; i<=sq->last; i++)
printf("\tsq->data[%d]=%d\n", i, sq->data[i]);
printf("=======================\n");
}
int main(int argc, char *argv[])
{
// 初始化一条空的顺序表
sqlist *sq = init_list(10);
// 插入元素
int num;
while(1)
{
scanf("%d", &num);
if(num > 0)
{
if(insert(sq, num))
show_data(sq);
else
fprintf(stderr, "顺序表已满\n");
}
else if(num < 0)
{
if(delete(sq, -num))
show_data(sq);
else
fprintf(stderr, "元素不存在\n");
}
else
{
fprintf(stderr, "BYE\n");
break;
}
}
return 0;

4.4 顺序表优缺点总结

顺序存储中，由于逻辑关系是用物理位置来表达的，因此从上述示例代码可以很清楚看到，增删数据 都非常困难，需要成片地移动数据。顺序表对数据节点的增删操作是很不友好的。

总结其特点如下：

优点

1. 不需要多余的信息来记录数据间的关系，存储密度高

2. 所有数据顺序存储在一片连续的内存中，支持立即访问任意一个随机数据，比如上述顺序表中第 个节点是 s->data[i]

缺点

1. 插入、删除时需要保持数据的物理位置反映其逻辑关系，一般需要成片移动数据

2. 当数据节点数量较多时，需要一整片较大的连续内存空间

3. 当数据节点数量变化剧烈时，内存的释放和分配不灵活

5. 单链表

5.1 基本概念

顺序表：顺序存储的线性表。

链式表：链式存储的线性表，简称链表。

既然顺序存储中的数据因为挤在一起而导致需要成片移动，那很容易想到的解决方案是将数据离散地 存储在不同内存块中，然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表，就是所 谓的链表。

顺序表和链表在内存在的基本样态如下图所示：

5.2 链表的分类

根据链表中各个节点之间使用指针的个数，以及首尾节点是否相连，可以将链表细分为如下种类：

1. 单向链表

2. 单向循环链表

3. 双向循环链表 这些不同链表的操作都是差不多的，只是指针数目的异同。以最简单的单向链表为例，其基本示意图

如下所示：

上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。另外注 意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节点。 head 通常被称为头指针。

链表的基本操作，一般包括：

1. 节点设计

2. 初始化空链表

3. 增删节点

4. 链表遍历

5. 销毁链表

下面着重针对这几项常见操作，讲解单向链表的处理。

5.3 单链表节点设计

单向链表的节点非常简单，节点中除了要保存用户数据之外（这里以整型数据为例），只需要增加一 个指向本类节点的指针即可，如下所示：

typedef int DATA;
typedef struct Node
{
DATA data; // 存储数据---数据域
struct Node *next; // 存储下一个节点的地址---指针域
} NODE;

5.4 单链表初始化

首先，空链表有两种常见的形式。一种是带所谓的头结点的，一种是不带头结点的。所谓的头结点是 不存放有效数据的节点，仅仅用来方便操作，如下：

而不带头结点的空链表如下所示：

注意：

头指针 head 是必须的，是链表的入口

头节点是可选的，为了方便某些操作

由于头结点是不存放有效数据的，因此如果空链表中带有头结点，那么头指针 head 将永远不变，这会 给以后的链表操作带来些许便捷。

示例代码：

/*
@function: int slist_create(NODE** head,DATA data);
@berif: 创建单项链表
@argument: head: 指向头指针变量的地址，用来接收首节点地址
data: 存储在节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_create(NODE** head,DATA data)
{
NODE* p = (NODE*)malloc(sizeof(NODE));
if(!p)
{
return -1;
}
p -> data = data;
p -> next = NULL;
*head = p;
return 0;
}

5.5 单链表增删节点

相对于顺序表需要整片移动数据，链表增删节点只需要修改几个相关指针的指向，动作非常快速。 与顺序表类似，可以对一条链表中的任意节点进行增删操作，示例代码是：

/*
@function: int slist_addHead(NODE** head,DATA data);
@berif: 向链表头部插入一个节点数据
@argument: head: 指向头指针变量的地址，用来接收首节点地址
data: 存储在新节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_addHead(NODE** head,DATA data)
{
NODE* p = (NODE*)malloc(sizeof(NODE));
if(!p)
{
return -1;
}
p -> data = data;
p -> next = *head;
*head = p;
return 0;
}
/*
@function: int slist_addTail(NODE** head,DATA data);
@berif: 向链表尾部插入一个节点数据
@argument: head: 指向头指针变量的地址，用来接收首节点地址
data: 存储在新节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_addTail(NODE** head,DATA data)
{
NODE * pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
{
return -1;
}
pNew -> data = data;
pNew -> next = NULL;
NODE* p = *head, *q = NULL;
if(!p)
{
*head = pNew;
return 0;
}
while(p)
{
q = p;
p = p -> next;
}
q -> next = pNew;
return 0;
}
/*
@function: int slist_insert(NODE** head,DATA pos ,DATA data);
@berif: 向链表节点值为pos的位置插入一个节点数据data
@argument: head: 指向头指针变量的地址
pos: 插入节点位置的节点数据
data: 存储在新节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_insert(NODE** head,DATA pos,DATA data)
{
// 创建一个新节点
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
// 给新节点赋值
pNew -> data = data;
pNew -> next = NULL;
NODE *p = *head, *q = NULL;
if(!p)
{
*head = pNew;
return 0;
}
// 等值判断
if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0)
{
pNew -> next = *head;
*head = pNew;
return 0;
}
while(p)
{
// 从头开始，找到pos指定位置的节点
if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0)
{
// 新节点指向pos位置对应的节点（pos对应节点位置在新节点之后）
pNew -> next = p;
// q节点指向新节点（新节点前一个节点）
q -> next = pNew;
return 0;
}
// pos对应位置的节点指向新节点，新节点在pos对应节点的后面
q = p;
p = p -> next;
}
//
q -> next = pNew;
return 0;
}
/*
@function: int slist_update(const NODE* head,DATA old,DATA newdata);
@berif: 更新链表数据old 为 newdata
@argument: head: 指向头指针变量
old: 待更新的节点数据
newdata: 更新后的节点数据
@return : 成功返回 0
失败返回 -1
*/
int slist_update(const NODE* head,DATA old,DATA newdata)
{
NODE* p = NULL;
if(!(p = slist_find(head,old)))
return -1;
p -> data = newdata;
return 0;
}
/*
@function: int slist_delete(NODE** head,DATA data);
@berif: 删除链表中节点值为data的节点
@argument: head: 指向头指针变量的地址
data: 删除节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_delete(NODE** head,DATA data)
{
NODE *p = *head, *q = NULL;
if(!p)
return -1;
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
*head = p -> next;
free(p);
return 0;
}
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
q -> next = p -> next;
free(p);
return 0;
}
q = p;
p = p -> next;
}
return -1;
}

注意: 删除链表的节点并不意味着释放其内存，而是将其剔除出链表

这篇关于第1章 顺序表和单链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---