数据结构与算法教程,数据结构C语言版教程!(第二部分、线性表详解:数据结构线性表10分钟入门)三

2024-01-01 08:34:19

第二部分、线性表详解:数据结构线性表10分钟入门

线性表,数据结构中最简单的一种存储结构,专门用于存储逻辑关系为"一对一"的数据。

线性表,基于数据在实际物理空间中的存储状态,又可细分为顺序表(顺序存储结构)和链表(链式存储结构)。

本章还会讲解顺序表和链表的结合体——静态链表,不仅如此,还会涉及循环链表、双向链表、双向循环链表等链式存储结构。

五、单链表的基本操作(C语言版)

《四、什么是单链表,链式存储结构详解》一节我们学习了如何使用链表存储数据元素,以及如何使用 C 语言创建链表。本节将详细介绍对链表的一些基本操作,包括对链表中数据的添加、删除、查找(遍历)和更改。

注意,以下对链表的操作实现均建立在已创建好链表的基础上,创建链表的代码如下所示:

//声明节点结构

typedef struct Link{

????????int elem;//存储整形元素

????????struct Link *next;//指向直接后继元素的指针

}link;

//创建链表的函数

link * initLink(){

????????link * p=(link*)malloc(sizeof(link));//创建一个头结点

????????link * temp=p;//声明一个指针指向头结点,用于遍历链表

????????//生成链表

????????for (int i=1; i<5; i++) {

????????//创建节点并初始化

????????????????link *a=(link*)malloc(sizeof(link));

????????????????a->elem=i;

????????????????a->next=NULL;

????????????????//建立新节点与直接前驱节点的逻辑关系

????????????????temp->next=a;

????????????????temp=temp->next;

????????}

????????return p;

}

从实现代码中可以看到,该链表是一个具有头节点的链表。由于头节点本身不用于存储数据,因此在实现对链表中数据的"增删查改"时要引起注意。

1、链表插入元素

同顺序表一样,向链表中增添元素,根据添加位置不同,可分为以下 3 种情况:

  • 插入到链表的头部(头节点之后),作为首元节点
  • 插入到链表中间的某个位置
  • 插入到链表的最末端,作为链表中最后一个数据元素

虽然新元素的插入位置不固定,但是链表插入元素的思想是固定的,只需做以下两步操作,即可将新元素插入到指定的位置:

  1. 将新结点的 next 指针指向插入位置后的结点;
  2. 将插入位置前结点的 next 指针指向插入结点

例如,我们在链表?{1,2,3,4}?的基础上分别实现在头部、中间部位、尾部插入新元素 5,其实现过程如图 1 所示:

链表中插入元素的 3 种情况示意图

图 1 链表中插入元素的 3 种情况示意图

从图中可以看出,虽然新元素的插入位置不同,但实现插入操作的方法是一致的,都是先执行步骤 1 ,再执行步骤 2。

注意:链表插入元素的操作必须是先步骤 1,再步骤 2;反之,若先执行步骤 2,除非再添加一个指针,作为插入位置后续链表的头指针,否则会导致插入位置后的这部分链表丢失,无法再实现步骤 1。

通过以上的讲解,我们可以尝试编写 C 语言代码来实现链表插入元素的操作:

//p为原链表,elem表示新数据元素,add表示新元素要插入的位置

link * insertElem(link * p, int elem, int add) {

????????link * temp = p;//创建临时结点temp

????????//首先找到要插入位置的上一个结点

????????for (int i = 1; i < add; i++) {

????????????????temp = temp->next;

????????????????if (temp == NULL) {

????????????????????????printf("插入位置无效\n");

????????????????????????return p;

????????????????}

????????}

????????//创建插入结点c

????????link * c = (link*)malloc(sizeof(link));

????????c->elem = elem;

????????//向链表中插入结点

????????c->next = temp->next;

????????temp->next = c;

????????return p;

}

2、链表删除元素

从链表中删除指定数据元素时,实则就是将存有该数据元素的节点从链表中摘除,但作为一名合格的程序员,要对存储空间负责,对不再利用的存储空间要及时释放。因此,从链表中删除数据元素需要进行以下 2 步操作:

  1. 将结点从链表中摘下来;
  2. 手动释放掉结点,回收被结点占用的存储空间;

其中,从链表上摘除某节点的实现非常简单,只需找到该节点的直接前驱节点 temp,执行一行程序:

temp->next=temp->next->next;

例如,从存有?{1,2,3,4}?的链表中删除元素 3,则此代码的执行效果如图 2 所示:

链表删除元素示意图

图 2 链表删除元素示意图

因此,链表删除元素的 C 语言实现如下所示:

//p为原链表,add为要删除元素的值

link * delElem(link * p, int add) { ???

????????link * temp = p; ???

????????//遍历到被删除结点的上一个结点 ???

????????for (int i = 1; i < add; i++) { ???????

????????????????temp = temp->next; ???????

????????????????if (temp->next == NULL) { ???????????

????????????????????????printf("没有该结点\n"); ???????????

????????????????????????return p; ???????

????????????????}

????????} ???

????????link * del = temp->next;//单独设置一个指针指向被删除结点,以防丢失 ???

????????temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域 ???

????????free(del);//手动释放该结点,防止内存泄漏 ???

????????return p;

}

我们可以看到,从链表上摘下的节点 del 最终通过 free 函数进行了手动释放。

3、链表查找元素

在链表中查找指定数据元素,最常用的方法是:从表头依次遍历表中节点,用被查找元素与各节点数据域中存储的数据元素进行比对,直至比对成功或遍历至链表最末端的?NULL(比对失败的标志)。

因此,链表中查找特定数据元素的 C 语言实现代码为:

//p为原链表,elem表示被查找元素、

int selectElem(link * p,int elem){

//新建一个指针t,初始化为头指针 p

????????link * t=p;

????????int i=1;

????????//由于头节点的存在,因此while中的判断为t->next

????????while (t->next) {

????????????????t=t->next;

????????????????if (t->elem==elem) {

????????????????????????return i;

????????????????}

????????????????i++;

????????}

????????//程序执行至此处,表示查找失败

????????return -1;

}

注意,遍历有头节点的链表时,需避免头节点对测试数据的影响,因此在遍历链表时,建立使用上面代码中的遍历方法,直接越过头节点对链表进行有效遍历。

4、链表更新元素

更新链表中的元素,只需通过遍历找到存储此元素的节点,对节点中的数据域做更改操作即可。

直接给出链表中更新数据元素的 C 语言实现代码:

//更新函数,其中,add 表示更改结点在链表中的位置,newElem 为新的数据域的值

link *amendElem(link * p,int add,int newElem){

????????link * temp=p;

????????temp=temp->next;//在遍历之前,temp指向首元结点

????????//遍历到待更新结点

????????for (int i=1; i<add; i++) {

????????????????temp=temp->next;

????????}

????????temp->elem=newElem;

????????return p;

}

5、总结

以上内容详细介绍了对链表中数据元素做"增删查改"的实现过程及 C 语言代码,在此给出本节的完整可运行代码:

#include <stdio.h>

#include <stdlib.h>

typedef struct Link {

????????int elem;

????????struct Link *next;

}link;

link * initLink();

//链表插入的函数,p是链表,elem是插入的结点的数据域,add是插入的位置

link * insertElem(link * p, int elem, int add);

//删除结点的函数,p代表操作链表,add代表删除节点的位置

link * delElem(link * p, int add);

//查找结点的函数,elem为目标结点的数据域的值

int selectElem(link * p, int elem);

//更新结点的函数,newElem为新的数据域的值

link *amendElem(link * p, int add, int newElem);

void display(link *p);

int main() {

????????//初始化链表(1,2,3,4)

????????printf("初始化链表为:\n");

????????link *p = initLink();

????????display(p);

????????printf("在第4的位置插入元素5:\n");

????????p = insertElem(p, 5, 4);

????????display(p);

????????printf("删除元素3:\n");

????????p = delElem(p, 3);

????????display(p);

????????printf("查找元素2的位置为:\n");

????????int address = selectElem(p, 2);

????????if (address == -1) {

????????????????printf("没有该元素");

????????}

?????????else {

????????????????printf("元素2的位置为:%d\n", address);

????????}

????????printf("更改第3的位置上的数据为7:\n");

????????p = amendElem(p, 3, 7);

????????display(p);

????????return 0;

}

link * initLink() {

????????link * p = (link*)malloc(sizeof(link));//创建一个头结点

????????link * temp = p;//声明一个指针指向头结点,用于遍历链表

????????//生成链表

????????for (int i = 1; i < 5; i++) {

????????????????link *a = (link*)malloc(sizeof(link));

????????????????a->elem = i;

????????????????a->next = NULL;

????????????????temp->next = a;

????????????????temp = temp->next;

????????}

????????return p;

}

link * insertElem(link * p, int elem, int add) {

????????link * temp = p;//创建临时结点temp

????????//首先找到要插入位置的上一个结点

????????for (int i = 1; i < add; i++) {

????????????????temp = temp->next;

????????????????if (temp == NULL) {

????????????????????????printf("插入位置无效\n");

????????????????????????return p;

????????????????}

????????}

????????//创建插入结点c

????????link * c = (link*)malloc(sizeof(link));

????????c->elem = elem;

????????//向链表中插入结点

????????c->next = temp->next;

????????temp->next = c;

???????? return p;

}

link * delElem(link * p, int add) { ???

????????link * temp = p; ???

????????//遍历到被删除结点的上一个结点 ???

????????for (int i = 1; i < add; i++) { ???????

????????????????temp = temp->next; ???????

????????????????if (temp->next == NULL) { ???????????

????????????????????????printf("没有该结点\n"); ???????????

????????????????????????return p; ???????

????????????????}

????????}

????????link * del = temp->next;//单独设置一个指针指向被删除结点,以防丢失 ???

????????temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域 ???

????????free(del);//手动释放该结点,防止内存泄漏 ???

????????return p;

}

int selectElem(link * p, int elem) {

????????link * t = p;

????????int i = 1;

????????while (t->next) {

????????????????t = t->next;

????????????????if (t->elem == elem) {

????????????????????????return i;

????????????????}

????????????????i++;

????????}

????????return -1;

}

link *amendElem(link * p, int add, int newElem) {

????????link * temp = p;

????????temp = temp->next;//tamp指向首元结点

????????//temp指向被删除结点

????????for (int i = 1; i < add; i++) {

????????????????temp = temp->next;

????????}

????????temp->elem = newElem;

????????return p;

}

void display(link *p) {

????????link* temp = p;//将temp指针重新指向头结点

????????//只要temp指针指向的结点的next不是Null,就执行输出语句。

????????while (temp->next) {

????????????????temp = temp->next;

????????????????printf("%d ", temp->elem);

????????}

????????printf("\n");

}

代码运行结果:

初始化链表为:
1 2 3 4
在第4的位置插入元素5:
1 2 3 5 4
删除元素3:
1 2 5 4
查找元素2的位置为:
元素2的位置为:2
更改第3的位置上的数据为7:
1 2 7 4


?六、顺序表和链表的优缺点(区别、特点)详解

顺序表和链表由于存储结构上的差异,导致它们具有不同的特点,适用于不同的场景。本节就来分析它们的特点,让读者明白 "在什么样的场景中使用哪种存储结构" 更能有效解决问题。

通过系统地学习顺序表和链表我们知道,虽然它们同属于线性表,但数据的存储结构有本质的不同:

  • 顺序表存储数据,需预先申请一整块足够大的存储空间,然后将数据按照次序逐一存储,数据之间紧密贴合,不留一丝空隙,如图 1a) 所示;
  • 链表的存储方式与顺序表截然相反,什么时候存储数据,什么时候才申请存储空间,数据之间的逻辑关系依靠每个数据元素携带的指针维持,如图 1b) 所示;

顺序表和链表的存储结构对比

图 1 顺序表和链表的存储结构对比

基于不同的存储结构,顺序表和链表有以下几种不同。

1、开辟空间的方式

顺序表存储数据实行的是 "一次开辟,永久使用",即存储数据之前先开辟好足够的存储空间,空间一旦开辟后期无法改变大小(使用动态数组的情况除外)。

而链表则不同,链表存储数据时一次只开辟存储一个节点的物理空间,如果后期需要还可以再申请。

因此,若只从开辟空间方式的角度去考虑,当存储数据的个数无法提前确定,又或是物理空间使用紧张以致无法一次性申请到足够大小的空间时,使用链表更有助于问题的解决。

2、空间利用率

从空间利用率的角度上看,顺序表的空间利用率显然要比链表高。

这是因为,链表在存储数据时,每次只申请一个节点的空间,且空间的位置是随机的,如图 2 所示:

链表结构易产生碎片

图 2 链表结构易产生碎片

这种申请存储空间的方式会产生很多空间碎片,一定程序上造成了空间浪费。不仅如此,由于链表中每个数据元素都必须携带至少一个指针,因此,链表对所申请空间的利用率也没有顺序表高。

空间碎片,指的是某些容量很小(1KB 甚至更小)以致无法得到有效利用的物理空间。

3、时间复杂度

解决不同类型的问题,顺序表和链表对应的时间复杂度也不同。

根据顺序表和链表在存储结构上的差异,问题类型主要分为以下 2 类:

  1. 问题中主要涉及访问元素的操作,元素的插入、删除和移动操作极少;
  2. 问题中主要涉及元素的插入、删除和移动,访问元素的需求很少;

第 1 类问题适合使用顺序表。这是因为,顺序表中存储的元素可以使用数组下标直接访问,无需遍历整个表,因此使用顺序表访问元素的时间复杂度为?O(1);而在链表中访问数据元素,需要从表头依次遍历,直到找到指定节点,花费的时间复杂度为?O(n);

第 2 类问题则适合使用链表。链表中数据元素之间的逻辑关系靠的是节点之间的指针,当需要在链表中某处插入或删除节点时,只需改变相应节点的指针指向即可,无需大量移动元素,因此链表中插入、删除或移动数据所耗费的时间复杂度为??O(1);而顺序表中,插入、删除和移动数据可能会牵涉到大量元素的整体移动,因此时间复杂度至少为?O(n);

综上所述,不同类型的场景,选择合适的存储结构会使解决问题效率成倍数地提高。

文章来源:https://blog.csdn.net/sinat_41942180/article/details/135150240
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。