【C++】单链表的操作

2021 年 03 月 19 日

1265 次浏览

1224字数

## 1.查找“数据域满足一定条件的节点”

```C
	p = head->next;
	while ((p->data != x) && (p->next != NULL)) p = p->next;
								//找到第一个就结束
	if (p->data == x)
		找到了处理;
	else
		输出不存在;
```

如果想找到所有满足条件的节点，则修改如下：

```C
	while (p != NULL)
	{
		if (p->data == x)	//找到一个修改一个

p = p->next;
	}
```

## 2.取出单链表的第i个节点的数据域

```C
void get(Node* head, int i)
{
	Node* p;
	int j;
	p = head;
	j = 1;
	while ((p != NULL) && j < i)
	{
		p = p->next;
		j=j++;
	}
	if ((p != NULL) && (j == i))
	{
		cout << p->data;
	}
	else {
		cout << "i not exsit!";
	}
}
```

## 3.插入一个节点到单链表中去

![插入节点前和后的链表变化](https://blog.fivk.cn/usr/uploads/2021/03/1599488835.png)

```C
void insert(Node* head, int i, int x)	//插入x到第i个元素之前
{
	Node* p, * s;
	int j;
	p = head;
	j = 0;
	while ((p != NULL) && (j < i - 1))
	{
		p = p->next;
		j = j + 1;
	}
	if (p == NULL)

cout << "no this position";
	else 
	{					//插入
		s = new Node;
		s->data = x;
		s->next = p->next;
		p->next = s;
	}
}
```

## 4.删除单链表的第i个节点

![删除一个节点前和后链表的变化](https://blog.fivk.cn/usr/uploads/2021/03/2822496551.png)

```C
void delete(Node* head, int i)	//删除第 i 个元素
{
	Node* p, * s;
	int j;
	j = 0;
	while ((p->next != NULL) && (j < i - 1))
	{
		p = p->next;
		j = j + 1;
	}
	if (p->next == NULL)		//p指向第i-1个节点
		cout << "no this position";
	else
	{
		s = p->next;			//删除p的后继节点，假设为s
		p->next = p->next->next;//或者p->next = s->next;
		free(s);
	}
}
```

## 5.求链表的实际长度

```C
int len(Node* head)
{
	Node* p;
	int n = 0;
	p = head;

while (p != = NULL)
	{
		n = n + 1;
		p = p->next;
	}
	return n;
}
```

最后修改：2021 年 03 月 19 日