当前位置 : 主页 > 编程语言 > 其它开发 >

【原创】浅谈指针(十)链表的写法

来源:互联网 收集:自由互联 发布时间:2022-05-17
前言 最近我又来更新这个系列了,其实感觉指针对于我们还是非常重要的存在。指针之所以是初学者们的“噩梦”,它的难度源于它的灵活性。 这篇文章,我想要来写一下指针的实际
前言

最近我又来更新这个系列了,其实感觉指针对于我们还是非常重要的存在。指针之所以是初学者们的“噩梦”,它的难度源于它的灵活性。
这篇文章,我想要来写一下指针的实际运用,如果指针只是一些考试的考题,那就没有意义了。最重要的,指针在C语言,乃至C++,都是不可或缺的一部分。

链表的简单回顾

链表是一种数据结构。

对于一个链表来说,每个结点有两个域,即数据域和指针域,数据域是用来存放这个链表的数字,指针域用来存放下一个结点的地址。特别的,最后一个结点的指针域设为NULL。
这样,就不需要让整个链表顺序存储了。

对于数据的插入和删除操作,链表只需要新建结点即可:

插入和删除的时间复杂度是O(1),不需要移动元素。而对于普通的线性表,需要移动数据,因此时间复杂度为O(n)。

结构体声明

对于链表的结构体,我们可以这样写:

typedef struct List{
	int data;
	List *next;
	List(int x){
		this->data=x;
		next=NULL;
	}
};
List *lst;

data是数据域,next是指针域。

其中,List(x)是一个构造函数,这样在使用new进行结点分配的时候可以简便书写。分配的时候就需要这样写:

l=new List(x);

这个构造函数做了两件事:一个是把data进行赋值,一个是把next设为NULL。

补充1:this指针
其中,写this->data,this是指这个结构体本身,例如调用:

l=new List(x);

此时this就指向l。this是一个特殊的指针。有一种形象的比喻方式:

当你进入一个房子后,你可以看见桌子、椅子、地板等,但是房子你是看不到全貌了。
对于一个类的实例来说,你可以看到它的成员函数、成员变量,但是实例本身呢?
this是一个指针,它时时刻刻指向你这个实例本身。

当然,这里不写this也是可以的。这只是写法问题。

补充2:->运算符
这个运算符,我们一般称为“箭头运算符”。
假设我们有现在下面的一个结构体:

struct info{
  string name;
  int age;
}

如果现在有一个普通变量x,那么引用其中的age,写作:x.age
如果现在有一个指针变量p,那么引用其中的age,要写作p->age
也就是说,对于一个指针结构体,引用其中的成员需要使用->运算符。
本质上,p->age等同于(*p).age,注意这里括号虽然麻烦但是不可省略。箭头运算符只是一种简便写法。

在链表的最后添加元素

我们知道,如果一个链表的当前结点为NULL,那么它必定是最后的结点。因此,我们可以采用递归的写法,如果链表当前节点不为NULL,那么就下一个结点。

void add(List *&l,int x){
	if(l==NULL){
		l=new List(x);
		return;
	}
	else add(l->next,x);
}

l=new List(x);,之前说过的构造函数写法。
add(l->next,x)表示找下一个结点。

补充3:*&是什么鬼!

我们知道,&是引用传递参数。我之前的浅谈指针(三)写过,网页链接
如果懒得在原文找的话,我这里直接把原文贴出来了:

在这里,*表示指针,&表示引用传递,那么加在一起就是指针的引用传递,虽然声明看上去很烦,但是理解了也就是这么回事。

输出链表的所有元素

毫无难度的函数,我直接贴出来了,逻辑和add函数类似。

void write(List *l){
	if(l==NULL)return;
	else{
		printf("%d ",l->data);
		write(l->next);
	}
}
插入元素

链表的灵活之处就是它的插入和删除函数。
如下图所示,我们要在2之后插入一个10:

首先,我们需要把10和3连接起来,否则一旦断掉2和3之间的连接,那么整个链表就直接分离了,无法再找到3的位置。

下一步,就是把2和10连接起来,同时断开2和3的连接。

这样就把插入的操作完成了,其实本质是很简单了。

void insert(int pos,List *&l,int x){
	if(pos==1){
		List *p=new List(x);
		p->next=l->next;
		l->next=p;
	}
	else insert(pos-1,l->next,x);
}

为了找到待插入的位置pos,我们可以采用递归的方法,每往后一个结点pos-1,最终当pos=1时就到了想要的位置。

删除元素

同样的链表,假设删除其中的3:

首先,先新建一个指针,指向3,否则后续操作过后就无法释放这块内存:

第二步,把2连接到4上面去。

最后,释放这个新建的指针,本质就是释放3。

代码还是一样,注意最终到pos=2就要停止了,这个算法无法删除首个结点的位置。

void remove(int pos,List *&l){
	if(pos==2){
		List *p=l->next;
		l->next=l->next->next;
		delete p;
	}
	else remove(pos-1,l->next);
}
完整思路

一套完整的链表写下来也是有四五十行代码的,完整代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef struct List{
	int data;
	List *next;
	List(int x){
		this->data=x;
		next=NULL;
	}
};
List *lst;
void add(List *&l,int x){
	if(l==NULL){
		l=new List(x);
		return;
	}
	else add(l->next,x);
}
void write(List *l){
	if(l==NULL)return;
	else{
		printf("%d ",l->data);
		write(l->next);
	}
}
void insert(int pos,List *&l,int x){
	if(pos==1){
		List *p=new List(x);
		p->next=l->next;
		l->next=p;
	}
	else insert(pos-1,l->next,x);
}
void remove(int pos,List *&l){
	if(pos==2){
		List *p=l->next;
		l->next=l->next->next;
		delete p;
	}
	else remove(pos-1,l->next);
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		add(lst,x);
	}
	while(m--){
		int k;
		scanf("%d",&k);
		if(k==1){//插入操作
			int pos,val;
			scanf("%d%d",&pos,&val);
			insert(pos,lst,val);
			write(lst);putchar('\n');
		}
		else if(k==2){//删除操作
			int pos;
			scanf("%d",&pos);
			remove(pos,lst);
			write(lst);putchar('\n');
		}
	}
	return 0;
}
上一篇:设计模式之【建造者模式】
下一篇:没有了
网友评论