浅析数据结构之链表C/C++

程序员文章站 2022-05-26 11:29:50

...

什么是链表

链表，顾名思义，就是拿“链子”把数据串联在一起，但与顺序表不同，串联起来的数据不必是连续的物理地址，而是利用指针进行相连，是一种线性存储结构。
例如，使用链表存储 {1,2,3}，数据的物理存储状态如下图所示：数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。

浅析数据结构之链表C/C++

链表的特点

 增删方便，只需要考虑相邻节点的指针域，不需要移动数据，时间复杂度是O（1）。
 随机查找效率低，需要根据指针逐个结点进行遍历，时间复杂度是O（n）。
 空间消耗大，因为每一个结点除了要存储数据本身以外，还要存储指针域，用来保存前后节点的地址。

链表的类型

常见的链表类型主要分为单链表，双向链表及循环链表。下文记录了单/双链表的基本操作及实现方式。

一. 单链表

单链表，即每个结点只包含一个后继指针；

单链表的头结点和尾结点比较特殊，头结点用来记录链表的基地址，是链表遍历的起点，尾结点的后继指针不指向任何结点，而是指向一个空地址NULL。

单链表的插入、删除操作时间复杂度为O(1)，随机查找时间复杂度为O(n)。
浅析数据结构之链表C/C++

单链表的定义

浅析数据结构之链表C/C++

单链表初始化

浅析数据结构之链表C/C++

单链表的插入

浅析数据结构之链表C/C++

单链表的删除

浅析数据结构之链表C/C++

单链表的查找

浅析数据结构之链表C/C++

单链表的更新

浅析数据结构之链表C/C++

单链表的输出

浅析数据结构之链表C/C++

完整代码

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct Node
{
	int data;//数据域
	struct Node *next;//指针域
}LNode;


LNode* nodeInit(int n)//n表示除头结点以外的结点个数
{
	//创建头指针head,别忘了指向NULL，避免野指针
	LNode *head=NULL;
	//创建头结点，保持temp指针一直指向现结点
	LNode *temp=(LNode*)malloc(sizeof(LNode));
	head=temp;//头指针指向头结点，头结点没有数据域
	//如果需要给头结点赋值，可以采用head->data=xxx;

	for(int i=0;i<n;i++)//申请除头结点以外的结点
	{
		LNode *node=(LNode*)malloc(sizeof(LNode));
		cout<<"请输入数据： ";

		if(node)//
		{
			cin>>node->data;//输入数据域
			node->next=NULL;//保持创建的结点的指针域指向NULL
	
			/*****建立新结点与其前驱结点的关系******/
			temp->next=node;//1.将新结点的首地址给其前驱结点的指针域
			temp=temp->next;//2.将临时指针指向下一结点（后继结点）
		}
		else
		{
			cout<<"内存申请失败";
		}
	}

	return head;//返回头指针便于后续操作，头指针在链表中发挥索引作用
}

LNode* insertElem(LNode *head, int elem, int add) 
{
    LNode *temp = head;//将头指针先赋给临时指针temp
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < add; i++)//这里插入位置指第几个，不是索引值，因此i从1计数
    {
        temp = temp->next;
        if (temp == NULL) {
            cout<<"插入位置无效"<<endl;
            return head;
        }
    }
    //创建插入结点c
    LNode *insert = (LNode*)malloc(sizeof(LNode));
    insert->data = elem;
    //向链表中插入结点
    insert->next = temp->next;//顺序不能错，先将插入节点的指针域更新，即temp->next
    temp->next = insert;//再将前驱结点的指针域更新
    return head;
}

//head为原链表，add为要删除的结点索引
LNode *delElem(LNode *head, int add)
 {
    LNode *temp = head;
    //遍历到被删除结点的上一个结点
    for (int i = 1; i < add; i++)
	{
        temp = temp->next;
        if (temp->next == NULL) 
		{
            cout<<"没有该结点"<<endl;
            return head;
        }
    }
    LNode *del = temp->next;//单独设置一个指针指向被删除结点，以防丢失
    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点，防止内存泄漏
    return head;
}


void display(LNode *p) //传入链表头指针即可
{
	LNode *temp =p;//将temp指针重新指向头结点
	//只要temp指针指向的结点的next不是Null，就执行输出语句。
	while (temp->next)
	{
		temp = temp->next;
		cout<<temp->data;
	}
	cout<<endl;
}

//p为原链表，elem表示被查找元素、
int selectElem(LNode * p,int elem){
//新建一个指针t，初始化为头指针 p
    LNode *temp=p;
    int i=1;
    
    while (temp->next) {
        temp=temp->next;
        if (temp->data==elem)
		{
            return i;//返回第i个结点
        }
        i++;
    }
    //程序执行至此处，表示查找失败
    return -1;
}

//更新函数，其中，add 表示更改结点在链表中第几的位置，newElem 为新的数据域的值
LNode *amendElem(LNode * p,int add,int newElem){
    LNode * temp=p;
    temp=temp->next;//在遍历之前，temp指向首元结点
    //遍历到待更新结点
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    temp->data=newElem;
    return p;
}

int main()
{
	LNode *p = NULL;
	p=nodeInit(5);
	cout<<"原链表为："<<endl;
	display(p);//输出原链表

	cout<<"在第4的位置插入元素5"<<endl;
    p = insertElem(p, 5, 4);
    display(p);

	cout<<"删除元素3"<<endl;
    p = delElem(p, 3);
    display(p);

	cout<<"查找元素2的位置为"<<endl;
    int address = selectElem(p, 2);
    if (address == -1) {
        printf("没有该元素");
    }
    else
	{
		cout<<"元素2的位置为："<<address<<endl;
    }

	cout<<"更改第3的位置上的数据为7"<<endl;
    p = amendElem(p, 3, 7);
    display(p);

	return 0;
}

-----------------

二. 双链表

双向链表中的每个结点具有两个方向指针，
• 后继指针：指向后面的结点，
• 前驱指针：指向前驱的结点。
双向链表也有两个特殊结点，首节点的前驱指针和尾结点的后继指针均指向空地址NULL。
浅析数据结构之链表C/C++

双向链表的定义

同单链表相比，双向链表的各节点多了一个用于指向直接前驱的指针域。因此，我们可以在单链表的基础上实现对双链表的创建。

需要注意的是，与单链表不同，双链表创建过程中，每创建一个新节点，都要与其前驱节点建立两次联系，分别是：

• 将新节点的 prior 指针指向直接前驱节点：node->prior=temp;
• 将直接前驱节点的 next 指针指向新节点：temp->next=node;
浅析数据结构之链表C/C++

双向链表初始化

浅析数据结构之链表C/C++

获取链表长度

浅析数据结构之链表C/C++

插入节点（非尾部）

浅析数据结构之链表C/C++

尾部新增（插入）节点

浅析数据结构之链表C/C++

双向链表的删除

浅析数据结构之链表C/C++

链表的修改

浅析数据结构之链表C/C++

获取结点数据/位置/前驱

浅析数据结构之链表C/C++

双向链表的输出

浅析数据结构之链表C/C++

完整代码

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct Node
{	
	struct Node *prior;//前驱指针
	int data;//数据域
	struct Node *next;//后继指针
}LNode;


LNode* nodeInit(int n)//n表示除头结点以外的结点个数
{
	//创建头指针head,别忘了指向NULL，避免野指针
	LNode *head=NULL;
	//创建头结点，保持temp指针一直指向现结点
	LNode *temp=(LNode*)malloc(sizeof(LNode));
	head=temp;//头指针指向头结点，头结点没有数据域

	head->prior=NULL;
	head->next=NULL;
	//如果需要给头结点赋值，可以采用head->data=xxx;

	for(int i=0;i<n;i++)//申请除头结点以外的结点
	{
		LNode *node=(LNode*)malloc(sizeof(LNode));
		cout<<"请输入数据： ";

		if(node)
		{
			cin>>node->data;//输入数据域
			node->next=NULL;//保持创建的结点的指针域指向NULL

			/*****建立新结点与其前驱结点的关系******/
			node->prior=temp;//新结点的prior为上一节点temp的首地址
			temp->next=node;//1.将新结点的首地址给其前驱结点的指针域
			temp=temp->next;//2.将临时指针指向下一结点（后继结点）
		}
		else
		{
			cout<<"内存申请失败";
		}
	}

	return head;//返回头指针便于后续操作，头指针在链表中发挥索引作用
}



//获取该链表的长度（不包括头结点）
int getlength(LNode *head)
{
	LNode *temp = head;
	int len = 0;
	while(temp->next)
	{
		temp = temp->next;
		len++;	
	}
	return len;
}


LNode* insertElem(LNode *head, int elem, int add) //非尾部插入结点
{
    LNode *temp = head;//将头指针先赋给临时指针temp
    //首先找到要插入位置的上一个结点
	//若要找到此结点，需要将temp的指针指向除头结点的第一个结点temp=temp->next；
    for (int i = 1; i < add; i++)//这里插入位置指第几个，不是索引值，因此i从1计数，temp指向待插入位置的上一结点
    {
        temp = temp->next;
        if (temp == NULL) {
            cout<<"插入位置无效"<<endl;
            return head;
        }
    }
    //创建插入结点c
    LNode *insert = (LNode*)malloc(sizeof(LNode));
    insert->data = elem;
    //向链表中插入结点
    insert->next = temp->next;//顺序不能错，先将插入节点的指针域更新，即temp->next
	insert->prior=temp;//前驱指针指向上一节点
    temp->next = insert;//再将前驱结点的指针域更新
    return head;
}

//尾部新增（插入）结点
LNode* insertEnd(LNode *head, int elem)
{
	LNode *temp=head;
	LNode *node=(LNode*)malloc(sizeof(LNode));//创建尾结点

	while(temp->next)//遍历到尾结点
	{
		temp=temp->next;
	}

	node->next=NULL;
	node->prior=temp;
	node->data=elem;
	temp->next=node;

	return head;

}

//删除结点
LNode *delElem(LNode *head, int add)
 {
    LNode *temp = head;
    //遍历到被删除结点的上一个结点
    for (int i = 1; i < add; i++)//利用遍历查找结点的上一节点(不包括头结点)
	{
        temp = temp->next;
        if (temp->next == NULL) 
		{
            cout<<"没有该结点"<<endl;
            return head;
        }
    }

	if(add==getlength(head))//若删除的结点是尾结点
	{
		cout<<"删除尾结点后的链表为：";
		LNode *del = temp->next;//单独设置一个指针指向被删除结点，以防丢失
		temp->next=NULL;

		free(del);//手动释放该结点，防止内存泄漏
	}
	else//若删除的结点是一般结点
	{
		LNode *del = temp->next;//单独设置一个指针指向被删除结点，以防丢失
		temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
		temp->next->prior=temp;
		free(del);//手动释放该结点，防止内存泄漏
	}

    return head;
}


//修改结点数据
LNode *editElem(LNode *head, int n, int newdata)
 {
    LNode *temp = head;
	temp=temp->next;//temp首先就指向除头结点的第一个结点，若删除此语句即temp一开始指向头结点

    for (int i = 1; i < n; i++)//利用遍历查找该结点，此时temp指向该结点
	{
        temp = temp->next;
        if (temp->next == NULL) 
		{
            cout<<"没有该结点"<<endl;
            return head;
        }
    }
	temp->data=newdata;

	return head;
}

//获取指定位置的节点，若获取指定元素的位置，遍历过程中加上if判断返回n即可
int getElem(LNode *head, int n)
 {
    LNode *temp = head;
    for (int i = 1; i <= n; i++)//遍历的另一种方法，自己可根据喜好灵活处理
	{
        temp = temp->next;
		//if(temp->data==xxx,return n)加上这条语句可修改为返回指定元素的位置
        if (temp->next == NULL) 
		{
            cout<<"没有该结点"<<endl;
            return 0;
        }
    }

	return temp->data;
	//return temp->prior->data;可获取该结点的前驱结点的数据，双向链表的优势
}

//双向链表反转
LNode *Reverse(LNode *head)
{
	LNode *temp=head;//temp指针没什么必要，只是习惯
	LNode *current=temp->next;
	LNode *pre=NULL;
	LNode *pnext=NULL;
	while(current)
	{
        //单独设置指针保留后继节点,
		//不能使用current=current->next，因为下面需要将其指向pre前驱
        pnext = current -> next;
        //新的后继指向前驱实现反转
        current -> next = pre;
		current->prior=pnext;
 
        //将当前节点向后移动
        pre = current;
        current = pnext;
	}
	current=head;//将头指针指向current，最后返回current作为新的头指针
	current->next=pre;
	current->prior=NULL;//头结点前驱指针初始化NULL
	return current;
}

//输出链表
void display(LNode *head) //传入链表头指针即可
{
	LNode *temp =head;//将temp指针重新指向头结点
	//只要temp指针指向的结点的next不是Null，就执行输出语句
	while (temp->next)
	{
		temp = temp->next;
		cout<<temp->data;
	}
	cout<<endl;
}

int main()
{
	LNode *p = NULL;
	p=nodeInit(5);
	cout<<"原链表为：";
	display(p);//输出原链表
	cout<<"链表长度为： "<<getlength(p)<<endl;

	//非尾部插入结点
	cout<<"在第一个位置插入8：";
	p=insertElem(p,8,1);
	display(p);

	//双链表反转
	p=Reverse(p);
	cout<<"链表反转后为: ";
	display(p);

	//尾部插入结点
	cout<<"在第尾部位置插入0：";
	p=insertEnd(p,0);
	display(p);

    //删除结点（包括尾部）
	p=delElem(p,7);
	display(p);
	
	//修改结点的数据
	cout<<"修改结点1的数据为5：";
	p=editElem(p,1,5);
	display(p);

	//获取节点的数据
	cout<<"获取第3结点的数据为："<<getElem(p,3)<<endl;


	return 0;
}

-----------------

链表反转

单链表的反转

浅析数据结构之链表C/C++

双链表的反转

浅析数据结构之链表C/C++

小结

笔者不才，非科班出身，汽车电子从业者，简单的了解了单/双链表的基本操作及实现方式，趁着记忆犹新记录下来，同时也记录在了小白的公众号（随时查阅复习）：智能驾驶软件宝典，仅供参考，如有疑问，欢迎与作者进行探讨。

浅析数据结构之链表C/C++

文章目录

什么是链表

链表的特点

链表的类型

一. 单链表

单链表的定义

单链表初始化

单链表的插入

单链表的删除

单链表的查找

单链表的更新

单链表的输出

完整代码

-----------------

二. 双链表

双向链表的定义

双向链表初始化

获取链表长度

插入节点（非尾部）

尾部新增（插入）节点

双向链表的删除

链表的修改

获取结点数据/位置/前驱

双向链表的输出

完整代码

-----------------

链表反转

单链表的反转

双链表的反转

小结

面试题之基础C/C++问题整理

数据结构之C++实现图（Graph）（无主函数）

sqlite学习笔记7：C/C++中使用sqlite之打开数据库

数据库知识学习之C C++ 操作系统、计算机网络等

数据结构之---C语言实现关键路径AOE图

数据结构【完整代码】之（C语言实现【图的存储创建遍历】邻接矩阵与邻接表）

C数据结构之Floyd和Dijstra实现最短路径教程

【基于C++和Python的Opencv3学习笔记之基本图形的绘制】

数据结构(C++)——图：基于邻接矩阵实现的图结构

c++复习要点总结之九——继承二