首页 > 其他分享 >数据结构:线性表的链式表示

数据结构:线性表的链式表示

时间:2024-07-15 20:18:49浏览次数:19  
标签:结点 NULL return LNode int next 链式 数据结构 线性表

继上文《数据结构:线性表的顺序表示》,我们知道线性表的主要操作如下:

  • InitList(&L): 初始化表
  • length(L): 求表长
  • LocateElem(L, e): 按值查找操作
  • GetElem(L, i): 按位查找操作
  • ListInsert(&L,i,e): 插入操作
  • ListDelete(&L,i,&e): 删除操作
  • PrintList(L):输出操作
  • Empty(L):判空操作
  • DestroyList(&L): 销毁操作

本文将讨论如何用链式表示的方法定义线性表

一般来说,默认链表是带头结点的

代码部分

线性表的定义

typedef int ElemType;

typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode, * LinkList;

第二个typedef语句本质上是,先定义一个结构体LNode, 再为LNode*类型取一个别名LinkList;可以说,链式表示用头节点来代表一个线性表。

单链表的初始化

带头结点的单链表初始化时,需先创建一个头结点,并让头指针指向头结点,头结点的next域初始化为NULL

bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));	// 创建头节点
	L->next = NULL;						// 头节点指向空
	return true;
}

关键语句解释:

L = (LNode*)malloc(sizeof(LNode));
sizeof(LNode) 表示 LNode 结构体的大小,即需要多少字节的内存空间来存储这个结构体的数据。
malloc(...) 调用malloc函数,在堆内存中分配指定大小的空间
L = (LNode*)... 是将 malloc 返回的指向分配的内存空间的指针转换为 LNode* 类型,并将其赋值给 L 这个指针变量。

求表长操作

求表长操作是计算单链表中数据结点的个数。

int length(LinkList L) {
	int len = 0;	// 计数变量
	LNode* p = L;
	while (p->next != NULL) {
		p = p->next;
		len++;
	}
	return len;
}

按序号查找结点

从单链表的第一个结点开始,沿着next域从前向后依次搜索,直到找到第i个结点为止,则返回该结点的指针;若i大于单链表的表长,则返回NULL

LNode* GetElem(LinkList L, int i) {
	LNode* p = L;	// 指向当前扫描到的节点
	int j = 0;
	while (p != NULL && j<i) {
		p = p->next;
		j++;
	}
	return p;	// 返回节点i得指针或NULL
}

按值查找结点

LNode* LocateElem(LinkList L, ElemType e) {
	LNode* p = L->next;
	while (p != NULL && p->data != e)
		p = p->next;
	return p;
}

插入结点操作

插入结点操作将值为x的新结点插入到单链表的第i个位置。先检查位置的合法性,然后找到待插入位置的前驱a,插入时遵循下列操作:

  1. 先将新结点指向a的后驱b(b=a->next
  2. 再将前驱a指向新结点
    具体代码如下:
bool ListInsert(LinkList& L, int i, ElemType e) {
	LNode* p = L;
	int j = 0;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;	// 位序不合法
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

删除结点操作

先检查位置的合法性,然后找到待插入位置的前驱a,删除时遵循如下步骤:

  1. 定义指针q,将待删除的结点指针赋值给q
  2. 将前驱a指向q的下一个结点
  3. 释放指针q指向的内存
bool ListDelete(LinkList& L, int i, ElemType& e) {
	LNode* p = L;
	int j = 0;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL || p->next == NULL)
		return false;
	LNode* q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

标签:结点,NULL,return,LNode,int,next,链式,数据结构,线性表
From: https://www.cnblogs.com/SXWisON/p/18303864

相关文章

  • 数据结构的基础(集合框架算法,复杂度和泛型)
    一.什么是集合框架        Java集合框架JavaCollectionFramework,又被称为容器container,是定义在java.util包下的一组接口interfaces和其实现类classes。        其主要表现为将多个元素element置于一个单元中,用于对这些元素进行......
  • 数据结构学习笔记——线性表
    链表1.单链表链表的插入:    (1)需要知道插入位置的前驱结点(从表头顺序遍历)    (2)先修改要插入的结点(新结点)的指针    (3)再修改前驱结点的指针链表的删除:    (1)要知道删除结点的前驱结点(从表头顺序遍历)    (2)只需要修改前驱结点的指......
  • 【数据结构】线性结构——数组、链表、栈和队列
    目录前言一、数组(Array)1.1优点1.2缺点1.3适用场景二、链表(LinkedList)2.1优点2.2缺点2.3适用场景三、栈(Stack)3.1优点3.2缺点3.3适用场景四、队列(Queue)4.1优点4.2缺点4.3适用场景......
  • 数据结构第28节 字典树
    字典树(Trie,也称前缀树)是一种用于存储字符串的树形数据结构。它将字符串中的字符作为树的边,每个节点代表一个可能的前缀。字典树非常适合处理大量字符串的搜索、插入和删除操作,尤其是在查找具有相同前缀的字符串时非常高效。基本概念:根节点:通常不包含任何数据,它的子节点包......
  • 数据结构绪论
    本篇主要介绍数据结构的基本概念和术语数据:数据是信息的载体。数据元素:数据的基本单元,通常作为一个整体进行考虑和处理。数据项:构成数据元素的不可分割的最小单位。数据对象:具有相同性质的数据元素的集合。数据类型原子类型:值不可再分的数据类型结构类型:值可以分解为......
  • 【NOI】C++数据结构入门之一维数组(一)数组基础
    文章目录前言一、概念1.导入2.数组2.1数组的创建2.2数组的使用二、例题讲解问题:1423-考试成绩的简单统计问题:1153-查找“支撑数”问题:1156-排除异形基因问题:1155-找找谁的身高超过全家的平均身高问题:1231-考试成绩的分布情况三、总结四、感谢前言在......
  • 数据结构专题
    [NOIP2012]借教室可以看到答案是有单调性的,若第i个可以那么第i-1个也可以,就可以二分答案,用差分维护区间加,也可以用树状数组#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#definedoublelongdouble#definePIIpair<int,int>constintN=1e6......
  • 【数据结构】图
     目录一、数据结构图的基本概念二、数据结构图的操作2.1图的创建(CreateGraph)2.2输入元素(InputElements)2.3遍历算法(TraversalAlgorithms)2.4搜索算法2.5查找操作(LocateOperation)2.6其他操作三、几种常见的数据结构图3.1UML类图(UnifiedModelingLanguage......
  • 数据结构-栈
    介绍栈是一种线性的数据结构,它具有先进后出的特性。栈是一种“操作受限”的数据结构——栈的插入和弹出都只能在一端进行。正是因为栈的这一个特性,计算机许多底层逻辑都是由栈实现的。栈的操作将元素压入栈查询栈的顶端元素弹出栈的顶端元素C++中栈的实现C++STL中包含栈......
  • 数据结构-黄洛天
    数据结构-黄洛天A-冰火战士题面支持$Q$次两种操作,添加一个三元组$(w,a,b),w\in{0,1}$撤回第$k$此操作,此操作保证为报名信息每次操作后,求$$\max_{x}\min(\sum_{w_i=0,a_i\lex}b_i,\sum_{w_i=1,a_i\gex}b_i)$$以及取到最值的最大的$x$。$1\leQ\le1\times10^......