【数据结构】如何通过ADT实现链表

朴灿烈づ我的快乐病毒、 2022-11-13 15:24 188阅读 0赞

## 1. ADT的定义 ##

使用C/C++的结构体可以定义我们的抽象数据类型（ADT），从而自定义我们的单链表数据结构，对ADT的设计如下：

typedef struct linklist{
        
    	ElementType data;
    	linklist *next;
    }node;

解释如下：

`struct`用于定义结构体类型；其前面的`typedef`关键字的作用在于：将花括号之后的`node`定义为数据类型，方便之后的使用；linklist是对当前链表节点元素的修饰，可以看成是地址类型，用于其指向下一节点；data则是你要定义的数据值，前面的ElementType是这个值的数据类型

## 2. 初始化链表 ##

初始化链表的任务就是创建一个不包含元素的空节点，我们称这个空节点为头节点，头节点有以下特点：

1.  头节点的元素值为空，当然也可以是你规定的为无效值的元素值；
2.  头节点所指的下一个节点为空

我们采用`init()`方法来对头节点进行创建

void init(node *&l){
        
    	l = new node;
    	l->next = NULL;
    }

在C++中经常使用new来为变量分配内存空间，在C语言中则经常通过以下方式开辟内存空间：

l = (node *)malloc(sizeof(node))

道理是一样的

`l->next`这里则是采用了结构体指针的方式访问到了结构体类型变量的属性（通常情况使用`.`操作符访问），因为这里函数的形式参数为**引用指针类型**，使用结构体指针的方式进行访问更为严谨

## 3. 创建链表 ##

创建链表一般采用数组输入，然后通过遍历数组的方式创建节点元素并插入链表中，代码如下：

void create(node *&l, ElementType a[], int n){
        
    	node *p=l;
    	for(int i=0; i<n; i++){
        
    		node *tmp = new node;
    		tmp->data = a[i];
    		tmp->next = NULL;
    		
    		p->next = tmp;
    		p = p->next;
    	}
    }

这里采用了指针p指向头节点，之后用p指针的移动来模拟节点元素的插入

tmp同样为结构体指针类型，为其分配了内存空间，作为待插入的节点，它的元素值为数组当前元素，它的指针指向空（为了规范）

之前有提到的用p模拟插入，原理是将p的指针指向tmp后将p移动到tmp处，每插入一个就往后移动一个，这也就是课上讲到的“尾插法”建立单链表

**由于p同样为结构体指针，p=l表示p和l同时指向同一内存地址，所以对p的改变就是对l的改变**

## 4. 遍历单链表 ##

遍历的操作其实和创建差不多，甚至比创建还要简单，因为不需要做太多的操作，我们只需要将其输出即可：

void display(node *&l){
        
    	node *p = l->next;
    	while(p){
        
    		cout<<p->data<<" ";
    		p = p->next;
    	}
    }

这里需要注意的是，无需将头节点输出，所以在定义指针时，直接指向头节点的下一节点即可。

发表评论取消回复

表情：

评论列表（有 0 条评论，188人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java数据结构：如何有效实现链表操作？

在Java中，链表是一种动态的数据结构，每个节点包含两个部分：数据和下一个节点的引用。以下是如何有效实现链表操作的一些步骤： 1. **创建节点类**：首先定义一个Node类

小灰灰/ 2024年12月04日 12:30/ 0 赞/ 15 阅读

相关数据结构：Java如何实现链表和堆栈？

在Java中，可以通过定义类来实现各种数据结构，如链表和堆栈。 1. 链表（Linked List）： ```java // 定义节点类 class Node {

一时失言乱红尘/ 2024年10月14日 05:42/ 0 赞/ 36 阅读

相关链表-Java实现链表数据结构

> 链表通常由一连串节点组成，每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接(“links”) 链表(Linked

骑猪看日落/ 2023年02月16日 06:03/ 0 赞/ 19 阅读

相关（数据结构）链表讲解和链表实现

什么是链表？链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的优缺点：优点： 1.任意位置插入

矫情吗；*/ 2023年02月14日 15:41/ 0 赞/ 134 阅读

相关【数据结构】STL实现链表

前言在本教程中，我所介绍的用法或接口可能并不完整，但是在日常的做题学习中已经足够用了。所以，如有额外需求可私信，我会及时发布新的文章补充相关知识点！ 1. 什么

Dear 丶/ 2022年11月15日 11:52/ 0 赞/ 332 阅读

相关【数据结构】如何通过ADT实现链表

1. ADT的定义使用C/C++的结构体可以定义我们的抽象数据类型（ADT），从而自定义我们的单链表数据结构，对ADT的设计如下： typedef struc

朴灿烈づ我的快乐病毒、/ 2022年11月13日 15:24/ 0 赞/ 189 阅读

相关 adt android 搜索工具条实现,抽象数据类型（ADT）--链表的实现

/\ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ \ Fil

墨蓝/ 2022年10月16日 04:46/ 0 赞/ 167 阅读

相关数据结构:JavaScript实现链表

链表是由一组节点组成的集合，每个节点都使用一个对象的引用指向它的后继。数组元素靠他们的位置进行引用，链表元素则是靠互相之间的关系进行引用。一.一个基本的链表

冷不防/ 2022年08月20日 04:23/ 0 赞/ 209 阅读

相关数据结构-链表实现（单链表，双链表，类实现）

1.单链表 1）单的意思就是说只有一个方向，所以只能往一个方向增加节点。 2）也因为单（身）所以处理起来很寂寞，注意几点吧： A）创建和遍历需要一个头节点（不含数据）

桃扇骨/ 2022年05月28日 12:54/ 0 赞/ 280 阅读

相关【数据结构】双向链表实现

双向链表(Double Linked List) 由两个指针域构成，分别指向前驱、后驱。如下图。 ![在这里插入图片描述][2020031420072497.png_

叁歲伎倆/ 2021年09月21日 04:34/ 0 赞/ 400 阅读