北郵22信通一枚~???

跟隨課程進度每周更新數(shù)據(jù)結(jié)構(gòu)與算法的代碼和文章?

持續(xù)關(guān)注作者? 解鎖更多郵苑信通專屬代碼~

獲取更多文章? 請訪問專欄：

北郵22信通_青山如墨雨如畫的博客-CSDN博客

**說明**

最近復習看到書后有雙向鏈表的題目，編出來供大家復習~

*********

目錄

一.講解

1.insert 增添函數(shù)

2.構(gòu)造函數(shù)：

3.del刪除函數(shù)：

4.change修改函數(shù)

5.search查找函數(shù)

二.代碼部分及運行結(jié)果

完整代碼

代碼效果圖：

運行結(jié)果：

?文章來源地址http://www.zghlxwxcb.cn/news/detail-465589.html

一.講解

小編實現(xiàn)的這個雙向鏈表只涉及增刪改查四個功能。下面先大體說一下思路。

結(jié)點結(jié)構(gòu)包括數(shù)據(jù)域、左指針和右指針?，左指針鏈接左邊的相鄰結(jié)點，右指針鏈接右邊的相鄰結(jié)點；

雙向鏈表類的實現(xiàn)部分，成員屬性包括整條鏈表的頭指針和尾指針以及鏈表的長度；

為什么增添了尾指針，請讀者帶著問題先往下看；

成員函數(shù)包括類的構(gòu)造函數(shù)和析構(gòu)函數(shù)，增刪改查4種功能的實現(xiàn)函數(shù)以及鏈表打印函數(shù)，下面逐個講解這幾個函數(shù)。

1.insert 增添函數(shù)

實現(xiàn)增添功能的過程如下圖所示；

簡單講解一下插入過程的步驟：

首先申請一個temp大小的堆空間，用來存放新增結(jié)點；

初始化這個結(jié)點，數(shù)據(jù)域賦值為傳入的參數(shù)，兩個指針域均賦值為空指針；

找到插入的地方，比如傳入的參數(shù)是3那就是找到第3個結(jié)點；

新增結(jié)點的右指針和第3個結(jié)點相連，?

新增結(jié)點的左指針和第三個結(jié)點的前驅(qū)結(jié)點也就是第二個結(jié)點相連

（先將新增結(jié)點的兩個指針連在鏈表上，

然后再斷開原先鏈表的指針連接，并重新與新增鏈表相連）；

斷開前驅(qū)結(jié)點的右指針，將右指針和新增結(jié)點相連，

斷開查找結(jié)點的左指針，將左指針與新增結(jié)點相連；執(zhí)行完畢。

insert函數(shù)的代碼：

template<class temp>
void linklist<temp>::insert(int i, temp x)
{
	node<temp>* p = this->front->right;
	while (--i)
		p = p->right;
	node<temp>* before_p = p->left;
	node<temp>* s = new node<temp>;
	s->data = x;
	s->right = p;
	s->left = before_p;
	p->left = s;
	before_p->right = s;
	this->length++;
}

2.構(gòu)造函數(shù)：

????????這里將講解為什么要多引入一個尾指針成員屬性。

????????其實構(gòu)造函數(shù)無非就是數(shù)據(jù)的接連插入操作，所以我們完全可以調(diào)用insert函數(shù)來實現(xiàn)構(gòu)造函數(shù)的頭插法。但是面臨的問題是，如上insert函數(shù)的實現(xiàn)過程，我們必須保證至少有兩個結(jié)點，才能執(zhí)行在這兩個結(jié)點之間的插入操作。綜上，新增尾指針。其實，不添加尾指針也可以實現(xiàn)構(gòu)造函數(shù)，即如果鏈表中只存在頭結(jié)點，則將新增結(jié)點直接接在頭結(jié)點后面，以后再新增數(shù)據(jù)，就直接調(diào)用insert函數(shù)實現(xiàn)。但是增加了尾指針還有其他好處比如倒序遍歷，使得某些方法變得更加簡便。所以小編選擇增加了一個鏈表尾指針的成員屬性。

構(gòu)造函數(shù)實現(xiàn)如下：

template<class temp>
linklist<temp>::linklist(temp a[], int n)
{
	this->front = new node<temp>;
	this->rear = new node<temp>;
	this->front->left = NULL;
	this->front->right = this->rear;
	this->rear->left = this->front;
	this->rear->right = NULL;
	this->length = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		insert(1, a[i]);
		this->length++;
	}
}

3.del刪除函數(shù)：

刪除操作的大致思路如下：

????????找到要刪除的結(jié)點，其前驅(qū)結(jié)點的右指針指向刪除結(jié)點的后繼結(jié)點，后繼結(jié)點的左指針指向刪除結(jié)點的前驅(qū)結(jié)點，最后刪除要刪除的結(jié)點，執(zhí)行完畢。

實現(xiàn)過程如下：

template<class temp>
temp linklist<temp>::del(int i)
{
	if (i > this->length)
		throw"上溢!";
	node<temp>* p = this->front->right;
	while (--i)
		p = p->right;
	cout << "被刪除的數(shù)據(jù)為:";
	p->data.print();
	p->left->right = p->right;
	p->right->left = p->left;
	temp tempdata = p->data;
	return tempdata;
}

4.change修改函數(shù)

很簡單，向單鏈表一樣循環(huán)，找到要修改數(shù)據(jù)域的結(jié)點，修改數(shù)據(jù)域即可。

5.search查找函數(shù)

思路同上。

二.代碼部分及運行結(jié)果

完整代碼

#include<iostream>
using namespace std;
class student
{
private:
	int ID;
	string name;
public:
	student()
	{
		this->ID = 0;
		this->name = "nuknown_name";
	}
	student(int ID, string name)
	{
		this->ID = ID;
		this->name = name;
	}
	void print()
	{
		cout << this->ID << " " << this->name << endl;
	}
	friend ostream& operator <<(ostream& output, student& s)
	{
		output << s.ID << " " << s.name << endl;
		return output;
	}
	bool operator !=(student&s)
	{
		return (this->ID != s.ID) || (this->name != s.name) ? true : false;
	}
};

template<class temp>
struct node                                                                                                                                         
{
	temp data;
	node* left;
	node* right;
};

template<class temp>
class linklist
{
private:
	node<temp>* front;
	node<temp>* rear;
	int length;
public:
	linklist()
	{
		this->front = new node<temp>;
		this->rear = new node<temp>;
		this->front->left = NULL;
		this->front->right = this->rear;
		this->rear->left = this->front;
		this->rear->right = NULL;
		this->length = 0;
	}
	linklist(temp a[], int n);
	~linklist();
	void insert(int i, temp x);
	temp del(int i);
	void change(int i, temp x);
	void search(temp x);
	void printlist();
};

template<class temp>
linklist<temp>::linklist(temp a[], int n)
{
	this->front = new node<temp>;
	this->rear = new node<temp>;
	this->front->left = NULL;
	this->front->right = this->rear;
	this->rear->left = this->front;
	this->rear->right = NULL;
	this->length = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		insert(1, a[i]);
		this->length++;
	}
}

template<class temp>
linklist<temp>::~linklist()
{
	node<temp>* p = this->front;
	while (p != NULL)
	{
		this->front = p;
		p = p->right;
		delete front;
	}
}

template<class temp>
void linklist<temp>::insert(int i, temp x)
{
	node<temp>* p = this->front->right;
	while (--i)
		p = p->right;
	node<temp>* before_p = p->left;
	node<temp>* s = new node<temp>;
	s->data = x;
	s->right = p;
	s->left = before_p;
	p->left = s;
	before_p->right = s;
	this->length++;
}

template<class temp>
temp linklist<temp>::del(int i)
{
	if (i > this->length)
		throw"上溢!";
	node<temp>* p = this->front->right;
	while (--i)
		p = p->right;
	cout << "被刪除的數(shù)據(jù)為:";
	p->data.print();
	p->left->right = p->right;
	p->right->left = p->left;
	temp tempdata = p->data;
	return tempdata;
}

template<class temp>
void linklist<temp>::change(int i, temp x)
{
	if (i > this->length)
		throw "上溢!";
	node<temp>* p = this->front->right;
	while (--i)
		p = p->right;
	if (p->right == NULL)
	{
		cout << "未查詢到數(shù)據(jù)!" << endl;
		return;
	}
	p->data = x;

}

template<class temp>
void linklist<temp>::search(temp x)
{
	node<temp>* p = this->front->right;
	while ((p->right != NULL) && (p->data != x))
		p = p->right;
	if ((p->left == NULL)||(p->right==NULL))
	{
		cout << "未查詢到數(shù)據(jù)!" << endl << endl;
		return;
	}
	cout << "找到數(shù)據(jù)!" << endl;
	p->data.print();
}

template<class temp>
void linklist<temp>::printlist()
{
	node<temp>* p = this->front->right;
	while (p->right != NULL)
	{
		p->data.print();
		p = p->right;
	}
	cout << endl;
}

int main()
{
	system("color 0A");
	cout << "雙鏈表數(shù)據(jù)如下:" << endl;
	student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"liu"},{5,"zhao"} };
	linklist<student>list(stu, 5);
	list.printlist();

	cout << "下面檢驗插入操作:" << endl;
	cout << "插入學生的信息為:";
	student stu1(6, "fu");
	stu1.print();
	list.insert(3, stu1);
	cout << "雙鏈表當前數(shù)據(jù)為:" << endl;
	list.printlist();

	cout << "下面檢驗刪除操作:" << endl;
	cout << "以刪除成員3為例:" << endl;
	cout << "執(zhí)行函數(shù)……";
	list.del(3);
	cout << "雙鏈表當前數(shù)據(jù)為:" << endl;
	list.printlist();

	cout << "下面檢驗查找操作:" << endl;
	cout << "查找同學的信息為:";
	stu1.print();
	list.search(stu1);

	cout << "下面檢驗替換操作:" << endl;
	cout << "替換進來的同學信息為:";
	student stu2(8, "zheng");
	stu2.print();
	list.change(2, stu2);
	cout << "雙鏈表當前數(shù)據(jù)為:" << endl;
	list.printlist();
	return 0;
}

代碼效果圖：

運行結(jié)果：

?

?

到了這里，關(guān)于北郵22信通：復習補充：雙向鏈表的實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！