博客

在链表中，尤其是自己写链表的时候，插入或者删除常常会遇到各种问题。

例如：插入的时候第一个插到了第二个，插入最后一个的时候会出错。

又或者在删除的时候也有了类似的问题。

我也同样如此，归根到底，不过是算法方面的问题，在我读《数据结构》（C语言版）（严蔚敏）的时候，发现其中算法非常妙，无论如何都不会出错。

PS：该链表是带头结点的链表（C++）

链表的插入

代码：

int LinkList::Insert_pos(int pos, int val)			//按位置插入
{
	Node* p = head;
	int j = 0;
	while (p && j < pos - 1)//寻找第pos-1个结点
	{
		p = p->next;
		++j;
	}
	if (!p || j > pos - 1)//pos小于1或者大于表长+1
	{
		return 0;
	}
	Node* temp = new Node;//生成新结点
	temp->data = val;		//插入L中
	temp->next = p->next;
	p->next = temp;
	return 1;
}

链表的删除

代码：

int LinkList::Delete_pos(int pos)//按位置删除
{
	Node* p = head;
	int j = 0;
	while (p->next && j < pos - 1)
	{//寻找到第pos个结点，并另p指向他的前趋
		p = p->next;
		++j;
	}
	if (!p->next || j > pos - 1)//删除位置不合理
	{
		return 0;
	}
	Node* pDel = p->next;//删除并释放
	p->next = pDel->next;
	delete pDel;
	return 1;
}