0 链表整理

常规
1

链表

1 单向链表
每个节点有两个部分：数据域和指针域
数据域：存储本身数据
指针域（nxt）：存储下一个节点地址

单链表的建立

struct node
{
	int data;
	node* nxt;
};

node *head, *tail, *t;

head = new node;
head -> nxt = NULL;
tail = head;

while (n--)
{
	t = new node;
	cin >> t -> data;
	t -> nxt = NULL;
	tail -> nxt = t;
	tail = t;
}

打印

for(t = head -> nxt; t != NULL; t = t -> nxt)
{
	cout << t -> data << " ";
}
cout << endl;

查找值为 a 的节点

for(t = head; t -> nxt != NULL; t = t -> nxt)
{
	if (t -> nxt -> data == a)
	{
		t -> nxt = t -> nxt -> nxt;
		break;
	}
}

删除值为 a 的节点

for(t = head; t -> nxt != NULL; t = t -> nxt)
{
	if (t -> nxt -> data == a)
	{
		t -> nxt = t -> nxt -> nxt;
		break;
	}
}

增加一个节点，值为 a

for(t = head; t -> nxt != NULL; t = t -> nxt)
{
	if (t -> nxt -> data == a)
	{
		t -> nxt = t -> nxt -> nxt;
		break;
	}
}

2 双链表
每个节点有三个部分：数据域和两个指针域
数据域：存储本身数据
指针域A（nxt）：存储下一个节点地址
指针域B（pre）：存储下一个节点地址
但通常用数组模拟

7 个赞