首页 > 其他分享 >1.线性结构（上）——数组与链表

1.线性结构（上）——数组与链表

时间：2024-07-27 20:56:13浏览次数：13  
标签：current 结点 int 链表 link 数组 线性 first

线性结构（上）：数组和链表

1.数据结构基本分类

线性结构：表、栈、队列

非线性结构：树、图、集合

本节，我们主要围绕线性表展开讨论

线性表主要有两类存储方式：即顺序存储方式——顺序表（数组）；链表存储方式——链表

在探讨线性表时，我们主要把目光聚焦在“增、删、查”这三种操作之上，同时我们会简要概述其时间维度的性能（时间复杂度）

2.顺序表（数组）

定义：将线性表中的元素相继存放在一个连续的空间中，顺序表一般形式为数组

特点：各表项（元素）逻辑顺序与物理顺序一致；各表项（元素）可以顺序查找，也可以随机访问

具体实现：我们将自己动手实现一个Array类，来模拟数组，主要分为以下几个步骤：

（一）基本类成员及函数

#include<iostream>
const int defaultSize = 100;
template<class E>
class Array
{
protected:
    E* data;//存放数组
    int maxSize;//最大容量
    int last;//最后元素的下标
public:
    Array(int sz = defaultSize);    
    ~Array();
    int Search(const E& x);
    bool Insert(int i,const E& x);
    bool Remove(const E& x);
    int Length(){return last+1;}
    //......
}

（二）构造及析构函数

构造函数需要给成员赋予恰当初始值，并且用new动态开辟内存

template<class E>
Array<E>::Array(int sz)
{
    if(sz<=0)return;
    maxSize = sz;
    last = -1;
    data = new E[maxSize];//动态分配内存空间以便存储数组元素
    if(!data){
       std::cerr << "storage allocation failed!" << std::endl;
       exit(1);
    }//考虑失败的情况
}

析构就很简单了，手动释放掉内存即可

template<class E>
Array<E>::~Array()
{
    delete[] data;
}

（三）访问查找

1.根据下标访问：

往往可以通过重载[ ]操作符来实现，

template<class E>
class Array
{
    //......
    E operator[](int i)
    {
        if(i>=maxSize||i<0){
            std::cerr<<"访问越界！"<<std::endl;
            exit(1);
        }
        return data[i];
    }
}

这种搜索直接通过给定下标从某一位置拿到元素值，时间复杂度为O(1)

2.根据值查找：

给定某个值，通过顺序比较元素是否等于该值逐一查找，找到值相等的元素即成功，并且返回该元素的下标

template<class E>
int Array<E>::Search(const E& x)
{
    for(int i = 0;i<maxSize;i++){
        if(data[i]==x)return i;
        return -1;
    }
}

最坏情况下需要遍历整个数组，故时间复杂度为O(n)

（四）插入操作

我们指定一个下标位置和元素值，往已有数组中插入元素

需要注意的是，该位置之后的元素需要依次向后移动一个单位，腾出空位便于该元素插入

简单起见我们暂且不考虑数组的动态扩容（感兴趣可以去了解C++ vector）

template<class E>
bool Array<E>::Insert(int i,const E& x)
{
    if(i<0||i>=maxSize)return false;//考虑i不合法情况
    if(last>=maxSize-1)return false;//考虑数组容量已满
    for(int j = last;j>=i;j--)
    {
        data[j+1] = data[j];
    }
    data[i] = x;
    last++;
    return true;
}

最坏情况下依旧需要遍历整个数组，所以时间复杂度为O(n)

（五）删除操作

我们想要删除某个元素，势必要先找到它，故需要先进行一个查找操作

我们以值查找为例

与插入相反，该元素之后的元素需要依次向前移动一个单位

template<class E>
bool Array<E>::Remove(const E& x)
{
    int index = Search(x);
    if(index==-1)return false;
    for(int j = index;j<last;j++)
    {
        data[j] = data[j+1];
    }
    last--;
    return true;
}

无论怎样查找待删除的元素，由于顺序表结构改变的弊端，时间复杂度依旧是O(n)

适用情形：

优点：存储利用率高，存取速度快

缺点：插入、删除等操作时需要移动大量数据

故适合需要频繁访问值，但改变结构操作不频繁的情形

例如学号成绩单。

由于人数基本固定所以成绩单结构几乎不需要改变，而只需要输入学号序号就能直接查找到分数，故适合用数组存储

3.链表

与数组不同，链表采用链式存储方式，

其优点是：适应表的动态增长和删除；

当然也有不足：需要额外的指针存储空间，且访问起来较为麻烦

特点：每个元素由一个节点类组成，结点可以不连续存储（物理地址不连续），扩充长度更加方便

分类：单向链表、双向链表，循环链表

3.1 单向链表：

（一）基本结构

每个元素存储到一个节点中，并且该节点中需要保存下一个节点的地址信息，该地址指向下一个节点，

节点依次相连，呈线性结构

故节点需要存储至少两个信息，一个是元素值，另一个是下一个节点的地址，我们用一个结构体来实现节点类

struct LinkNode //链表结点结构 
{	        	
      int data;		     //结点数据
      LinkNode *link;        //结点指针		
};
 
class List //链表类 
{	    
public:
      bool Insert(int i, int x); //插入元素
      bool Remove(int i);//删除元素
      //...... 
private:
      LinkNode *first;        //表头指针
};

单链表的存储映像：

Alt Text

（二）插入方法

我们分情况讨论：

头插： 在链表最前端插入

newNode->link = first;

first = newNode;

Alt Text

（插入前后）

尾插：在链表末尾插入

newNode->link = current->link(NULL);

current->link = newNode;

Alt Text

中间插：在链表中间插入

newNode->link = current->link;

current->link = newNode;

Alt Text

完整插入算法实现如下：

bool List::Insert(int i, int x) {
//将新元素 x 插入到第 i 个结点之后。i 从 1 开始，
//i <= 0 表示插入到首元结点之前。
    if (first == NULL || i <= 0) {	  //空表或首元结点前
	    LinkNode *newNode = new LinkNode(x);		  //建立一个新结点
	    newNode->link = first;  first = newNode;       //新结点成为首元结点
    }			 		
  	else {                     //否则，寻找插入位置
        LinkNode *current = first;	 //用current记录当前遍历到的节点地址
        int k = 1; 
        while (k < i && current != NULL)    //遍历找到第i结点
 	    { 
            current = current->link;  k++; 
        }
	    if (current == NULL)    //插入位置不恰当（超出链表长度）
	    { 
            cerr << “无效的插入位置!\n”;  return false;
        }
        else   //插入在链表的中间
        {		 
		   LinkNode *newNode = new LinkNode(x);
	 	   newNode->link = current->link;
            current->link = newNode;
        }
	}
	return true; 
};

（三）删除方法

情况一：删除表中第一个元素

del = first; first = first->link; delete del;

情况二：删除表中或表尾元素

delNode = current->link; current->link = delNode->link; delete del;

Alt Text

我们以通过下标删除元素为例：

bool List::Remove (int i) {
//将链表中的第 i 个元素删去, i从1开始。
    if(first == NULL)
    {
        cerr << “链表为空!\n”;  return false;
    }
    LinkNode *delNode;		//暂存删除结点指针
	if (i <= 1)  
    { 
        delNode = first;  first = first->link; //删头节点
    }
	else 
    { 
        LinkNode *current = first;  k = 1;   //找i-1号结点
	    while (k < i-1 && current != NULL)	
  	    { 
            current = current->link;   k++; 
        }
	    if (current == NULL || current->link == NULL) 
        { 
            cerr << “无效的删除位置!\n”;  return false;
        }		
          delNode = current->link;  current->link = delNode->link;	 //删中间或尾结点	
	}
	delete delNode; 	
	return true;			
};

注意，无论插入还是删除算法，都需确保指针赋值的顺序正确！

综上我们可以看出，链表的插入和删除，不需要移动元素，只需修改结点指针，比顺序表方便

然而也有弊端——寻找插入或删除位置只能沿着链顺序检测，且要专门讨论空表和在表头插入的特殊情形

其访问、插入、删除操作均需沿着链顺序遍历，故时间复杂度均为O(n)

（四）附加头节点的单链表

为了简化链表操作，统一空表与非空表、最前端与非最前端的操作，我们引入一种新的概念——附加头节点的单链表

其与普通链表的区别是：额外添加一个表头结点位于表的最前端，但其本身不带数据，仅起标志表头的作用，不作为链表元素

Alt Text

  • 在带表头结点的单链表最前端插入新结点：

Alt Text

newNode->link = current->link;

current->link = newNode;

不难发现，表空与否均可用同样代码逻辑表示，且和其他位置插入的代码逻辑同样一致

  • 从带表头结点的单链表中删除最前端的结点：

Alt Text

delNode = current->link;

current->link = delNode->link;

delete delNode;

我们同样统一了代码逻辑

例题1：实现一个算法，能够翻转已有链表序列。

3.2 双向链表与循环链表：

（一）双向链表：

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点，只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。

为了克服单链表的上述缺点，我们引入双向链表的结构。

双向链表每个节点记录了两个方向的节点地址：

Alt Text

向左为前驱方向，向右为后继反向

节点类定义如下:

template <class E> 
struct DblNode {		//双向链表结点类定义
    E data;			//链表结点数据
    DblNode<E> *lLink, *rLink;//前驱、后继指针
    /*构造函数*/   
    DblNode (const E& value, DblNode<E> *l = NULL, DblNode<E> *r = NULL):data(value),lLink(l),rLink(r){}
};

（二）循环链表：

与非循环链表相比，循环链表最后一个结点的 link 指针不为NULL，而是指向了表的前端

这样只要知道表中任一结点的地址，就可搜寻到所有其他结点的地址

Alt Text

以下为附加头节点的结构：

Alt Text

类定义大致如下：

template <class E>      
class CircList  //循环链表类 
{ 
private: 
	LinkNode<E> *head, *tail;  //头指针, 尾指针
public: 
	 CircularLinkedList() : head(nullptr), tail(nullptr) {}
	～CircList();			       
 
	bool IsEmpty() { return first->link == first; }//判表空否
	LinkNode<E> * Search(const E& x);//查找某元素
    //......
}

我们额外添加一个tail指针用来记录链表尾部

通过 tail 成员，可以直接访问链表的尾部节点，而不需要从头节点开始遍历整个链表。

这使得在尾部插入（其实相当于在头部之前插入）或删除节点的操作更加高效，时间复杂度为 O(1)。

（在其他地方插入的逻辑较非循环链表并无区别）

以搜寻算法为例（假如附加头节点）：

template <class E> 
LinkNode<E> * CircList<E>::Search(const E& x) 
{
//在链表中从头搜索其数据值为 x 的结点
     current = first->link;
     while (current != first && current->data != x )  {
         current = current->link;
     }
     if(current == first){ cerr << “查找失败!\n”; return NULL;}
     return current;
}

循环链表的经典应用：约瑟夫问题

例题2：一个圈共有N个人，每个人的编号顺时针依次为1，2，...，N。从编号为1的人顺时针开始依次从1报数，报到M这个数字的人出局，紧接着从出局的这个人的下一个人重新开始从1报数，和上面过程类似，报到M的人出局，直到N个人全部出局。

请输出出局编号序列。

3.3 * 双向循环链表：

现实应用中往往双向链表和循环链表结合使用

下图为附加头节点的双向循环链表结构图：

Alt Text

template <class E>
class DClList {		//双向循环链表类定义
public:
    DClList(const E& uniqueVal) {	        //构造函数
        first = new DblNode<E>(uniqueVal);
        first->rLink = first->lLink = first;
    };

    bool IsEmpty() { return first->rlink == first; }//判断链表空否

    DClNode<E>* Search(const E& x, int d);
    //在链表中按d指示方向寻找等于给定值x的结点,d=0按前驱方向,d≠0按后继方向

    bool Insert(int i,const E& x, int d);
    //在第i个结点后插入一个包含有值x的新结点

    bool Remove(int i,int d);   //删除第i个结点
private:
    DClNode<E>* first;                 //表头指针
};

（一）搜索方法

template <class E>
DblNode<E> * DClList<E>::Search (const E& x, int d) {
//在双向循环链表中寻找其值等于x的结点。
    DblNode<E> *current = (d == 0)?first->lLink : first->rLink;   //按d确定搜索方向
	while ( current != first && current->data != x ){	
        current = (d == 0) ? current->lLink : current->rLink;
    }
     if(current == first){ cerr << “查找失败!\n”; return NULL;}
     return current;
};

（二）插入方法

插入到current后：

newNode->rLink = current->rLink;

current->rLink = newNode;

newNode->rLink->lLink = newNode;

newNode->lLink = current;

template <class E>
bool DClList<E>::Insert(int i,const E& x, int d) {
	//建立一个包含有值x的新结点, 并将其按 d 指定的方向插入到第i个结点之后。
	DblNode<E>* current = Search(i, d);
	
	if (!current) return false;    //插入失败
	DblNode<E>* newNode = new DblNode<E>(x);
	if (d == 0) {	  //前驱方向:插在第i个结点左侧
		newNd->lLink = current->lLink; //链入lLink链
		current->lLink = newNode;
		newNd->lLink->rLink = newNode;  //链入rLink链
		newNd->rLink = current;
	}
	else {		     //后继方向:插在第i个结点后面
		newNd->rLink = current->rLink;  //链入rLink链
		current->rLink = newNode;
		newNd->rLink->lLink = newNode;   //链入lLink链
		newNd->lLink = current;
	}
	return true; 	    //插入成功
};

（三）删除方法

删除current：

current->rLink->lLink = current->lLink;

current->lLink->rLink = current->rLink;

template < class E>
bool DClList< E>::Remove(int i, int d) {
//在双向循环链表中按d所指方向删除第i个结点。
    DblNode<E> *current = Search(i, d);
    if (!current) return false; 	      //删除失败
	current->rLink->lLink = current->lLink;
	current->lLink->rLink = current->rLink;	//从lLink链和rLink链中摘下
    delete current; 	  
    return true; 			             //删除成功
};

练习：

1.给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

示例 1：

img

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

2.将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

示例 1：

img

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = [0]
输出：[0]

3.给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

  • 链表中节点的数目范围是 [0, 10^4]
  • -10^5 <= Node.val <= 10^5

示例 1：

img

head = [3,2,0,-4], pos = 1 （pos 来表示链表尾连接到链表中的位置（索引从 0 开始）,-1表示无环）
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

标签：current,结点,int,链表,link,数组,线性,first
From： https://www.cnblogs.com/artystudio/p/18327464

相关文章

  • golang 数组转为链表 - 正序和逆序
    有时候，有这样的场景，我们需要就给定数组将其转为一个链表，通常的思路有两种：正序逆序以下是具体的代码实现和测试函数：packagemainimport("fmt""testing")typelistNodestruct{next*listNodevalint}//正序遍历构建链表//通过一个虚拟头结点，不......
  • C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
    写在最前，一篇文章学会C语言指针顶级重要，学习C语言最重要的一部分-------指针第八章指针超详细讲解_指针变量_二维数组指针_指向字符串指针文章目录写在最前，一篇文章学会C语言指针第八章指针超详细讲解_指针变量_二维数组指针_指向字符串指针1.指针变量1.1指针变......
  • C141 线段树分治+线性基 P3733 [HAOI2017] 八纵八横
    视频链接：C141线段树分治+线性基P3733[HAOI2017]八纵八横_哔哩哔哩_bilibili   P3733[HAOI2017]八纵八横-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树分治+线性基O(q*logq*logL*logL)#include<iostream>#include<cstring>#include<algorithm>......
  • 数组基础、多维数组、静态Array
    数组：一组数据。本身是一种类型（引用类型），但它中存储的元素（项）也有数据类型，数组只能用来存储类型相同的强类型的数据，比如班级只能用来存放学生，不能放别的。数组在内存中是按定长连续来存储的，具有相同数据类型的数据元素的有序集合。inta=10;//一个数据boolb=true;//一......
  • 为什么用 numpy 数组除以 float32 常量比将 numpy 数组转换为 float32 然后除法更快？
    我正在处理一些图像数据，因此图像表示为形状为(1404,1404,3)的numpy数组。图像的类型为np.uint8（它的RGB值从0到255）我想知道这两行代码之间的速度差异：normalized_image=image.astype("float32")/255.0normalized_image=image/np.float32(255)在1......
  • 标题：在 OpenSees Python 中定义具有特定卸载行为的双线性弹塑性材料
    我正在使用Python中的OpenSees，我想定义一种在负载下表现出双线性弹塑性行为的材料。但是，我需要在卸载过程中将材质返回到其原始位置，遵循准确的加载路径。在此处输入图像描述我不确定如何在OpenSees中正确实现卸载行为，我正在寻找实现这一具体材料反应的指导。......
  • 线性模型的 SHAP 值与手动计算的值不同
    我训练一个线性模型来预测房价，然后我将手动计算的Shapley值与SHAP库返回的值进行比较，它们略有不同。我的理解是，对于线性模型，Shapley值是给定的通过：coeff*featuresforobs-coeffs*mean(featuresintrainingset)或者如SHAP文档中所述：coef[i]*......
  • 线性规划的求解方法
    文章目录基于求解器求解基于问题求解利用Lindo求解0-1整数非线性规划转化为线性规划基于求解器求解问题：min⁡z=∣x1∣+2∣x2∣+∣x3∣+∣x4∣\mathop{\min}z=\left|x_1\right|+2\left|x_2\right|+\left|x_3\right|+\left|x_4\right|......
  • 数据结构-线性表
    目录王道章节内容知识框架考纲内容引入方法1：顺序存储结构的直接表示方法2：顺序存储结构表示非0项方法3：链表结构存储非零项线性表定义线性表的主要操作（ADT）顺序存储结构定义结构代码实现操作及实现初始化获得查找插入删除链式存储结构单链表定义结构代码......
  • js 一个对象有多层，都是分组对象，最后一层才是数组，怎么拍平这个对象，拍平后的格式是{a.b.
    要将一个嵌套对象拍平为{a.b.c:[]}这种格式，可以使用递归方法遍历对象的每一层，并在最终层级构建平坦的键值对。以下是实现这一功能的示例代码：functionflattenObject(obj,parentKey='',result={}){for(letkeyinobj){constfullKey=parentKey?`${......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99