天天看點
傳回

【殷人昆資料結構】第二章2.2 單連結清單代碼的調試Single Linked List單連結清單

Single Linked List單連結清單

文章目錄

  • Single Linked List單連結清單
    • 單連結清單結點類定義
    • 單連結清單類定義
    • makeEmpty函數
    • 關于inputFront和inpurRear
    • 關于void input(T endTag, InsMod im = INR);
    • List類構造函數
    • inverse函數
    • insert函數
    • Locate函數
    • remove函數
    • search函數
    • 整一個頭檔案

檔案：

【殷人昆資料結構】第二章2.2 單連結清單代碼的調試Single Linked List單連結清單

主函數：

#include <fstream>   //調用檔案輸入輸出流類
#include "LinkedList.h" //調用單連結清單頭檔案
using namespace std;  //聲明命名空間

int main(){
	List<int> list;     //執行個體化類List
	ifstream fin("list.txt");  //這裡将輸入檔案設為ifstream類型
	assert(fin);        //判斷檔案讀取過程是否成功編譯
	fin >> list;        //調用輸入流operator>>，将檔案中的資料一一輸傳入連結表list
	//這句話的效果相當于operator>>(fin,list);
	//因為ifstream公有繼承了iostream
	cout << "The initial list in the file is:\n" << list << endl;
	list.Inverse();     //逆轉這個單連結清單
	cout << "Inverse the list, then the list is:\n" << list << endl;

	cout << "========================================\n";
	int i, elem;  //定義兩個整數變量
	cout << "Test the Insert, Remove and Search function:\n";
	cout << "Each test will terminate by an invaid input.";
	cout << "\n----------------------------------------\n";
	
	cout << "1. Test the Insert(int i, T &elem):\n";
	while (1){
		cout << "Input the index i and data elem to insert: ";
		cin >> i >> elem;
		if (!cin){  //結束條件1:輸入異常。
		//這是異常處理的一種，當碰到cin了錯誤的類型時
			cin.clear(); //clear将cin的資料元素failbit修改到原來的狀态
			cin.ignore(100,'\n'); //清空緩存區
			break;
		}
		if (i < 0)	break; //結束條件2：輸入負數
		if (list.Insert(i, elem))	cout << "Insert successful!\n";
		else	cout << "Insert failed!\n";
	}
	cout << "\nAfter inserted\n" << list << endl;

	cout << "----------------------------------------\n";
	cout << "2. Test the Remove(int i, T &elem):\n";
	while (1){
		cout << "Input the index i in which you want to remove: ";
		cin >> i;   
		if (!cin){
			cin.clear();
			cin.ignore(100,'\n');
			break;
		}
		if (i < 0)	break;
		if (list.Remove(i, elem))	cout << "The element " << elem << " has been removed!\n";
		else	cout << "Remove failed!\n";
	}
	cout << "\nAfter removed\n" << list << endl;

	cout << "----------------------------------------\n";
	cout << "3. Test the Search(T &elem):\n";
	while (1){
		cout << "Input the element you want to search: ";
		cin >> elem;
		if (!cin){
			cin.clear();
			cin.ignore(100,'\n');
			break;
		}
		if (elem < 0)	break;
		LinkNode<int> *p = list.Search(elem);
		if (p)	cout << "The element " << elem << " is in the list.\n";
		else	cout << "The element is not exist!\n";
	}
	cout << "\n----------------------------------------\n";
	cout << "End test!" << endl;
	return 0;
}

單連結清單結點類定義 

template <typename T>struct LinkNode{
	T data;         //資料域
	LinkNode<T> *link;  //指針域
	LinkNode(LinkNode<T> *ptr = NULL){    //構造函數，預設指針域為空
		link = ptr;  
	}
	LinkNode(const T &item, LinkNode<T> *ptr = NULL){
		data = item;   //傳入一個類型為T的資料，構造函數中定義為資料元素
		link = ptr;    //指針域，若未指派初始化為NULL
	}
};

單連結清單類定義 

template <typename T>class List{
public:
	List(){ //無參構造函數，其中也調用了LinkNode的無參構造函數
		first = new LinkNode<T>;  //first指向新的記憶體空間LinkNode<T>
	}
	List(const T &x){  //有參構造函數，其中也調用了LinkNode的有參構造函數
		first = new LinkNode<T>(x);  
		//first指向新的記憶體空間LinkNode<T>，資料成員為x
	}
	List(List<T> &L); //拷貝構造函數
	~List(){          //析構函數
		makeEmpty();  //釋放首節點之後的所有結點
		delete first; //釋放首節點
	}
	void makeEmpty(); //聲明清空函數
	int Length()const;//聲明計算長度函數
	LinkNode<T> *getHead()const{ //傳回指向結點指針的函數（通路私有成員first）
		return first;
	}
	LinkNode<T> *Search(const T &x);//聲明查找函數，傳回指向結點的指針
	LinkNode<T> *Locate(int i);  //聲明定位函數，傳回指向結點的指針
	bool getData(int i,T&x)const;//擷取資料函數，傳入結點号i，T類型資料x
	void setData(int i, T &x);   //設定資料函數，傳入i和x
	bool Insert(int i, T &x);    //插入函數，傳入i和x
	bool Remove(int i, T &x);    //删除函數，傳入i和x
	bool IsEmpty()const{         //判斷單連結清單是否為空
		return (first->link == NULL)?true:false;   
		//首節點往後第一個結點不為空則傳回true，否則傳回false
	}
	bool IsFull()const{     //判斷連結清單是否滿函數
		return false;
	}
	void Sort();   //排序函數
	void Inverse();//反轉函數
	void input(T endTag, InsMod im = INR); //輸入函數
	void output(); //輸出函數
	List<T> &operator = (List<T> &L);   //傳回List的引用，這是指派運算符的常用套路
	friend ostream& operator << (ostream &out, List<T> &L){  
	//函數傳回的是ostream對象的引用out
		LinkNode<T> *current = L.first->link;  //current指向頭結點後面第一個結點
		while (current){   //周遊連結清單元素
			out << current->data <<'\t';   //将目前指針的資料元素傳給ostream對象out
			current = current->link;   //current指向下一個結點
		}
		out<<endl;    //最後傳入換行符
		return out;   //運算符傳回out
	}
	//調用時前面加cout<<list，相當于operator<<(cout,list);主函數中這樣表達結果是正确的。

    /******************輸入運算符和輸出運算符目的不同，**************************
     ******************輸出運算符隻需要周遊清單，*******************************
     ******************但輸入運算符需要确定輸出位置、容量改變等問題。*************/
    
	friend istream& operator >> (istream &in, List<T> &L){  //現在可以這麼說了：
	//類定義内定義友元函數operator>>，傳回類型為istream的引用，
	//傳入istream對象in的引用（可以修改in），以及清單類型資料L的引用（可以修改L）。
		LinkNode<T> *newNode,*last;   //定義兩個LinkNode型的指針newNode和last
		T val;  //定義一個val型的資料成員T
		L.makeEmpty();   //将L設定為一個隻剩首節點的空連結清單
		last = L.first;  //指針last此時設定為指向首節點
		while (!in.eof()){  
		//eof是istream流類庫中的函數，判斷緩存區是否仍有資料要讀入
			in >> val;   //輸入val
			newNode = new LinkNode<T>(val); //将val放入newNode指向的新結點
			assert(newNode);  //在這裡檢查編譯過程，若錯誤則友善定位
			last->link = newNode;  //将newNode放入單連結清單的尾部
			last = newNode;   //last指向newNode
		}
		last->link = NULL;//最後将尾節點的指針域設為NULL
		return in;    //傳回輸入流類型in的引用，友善連續輸入
	}

protected:
	LinkNode<T> *first;     //指針first指向連結清單List的首節點（是以類型為指向結點的指針）
	//然後
	void inputFront(T endTag);  
	void inputRear(T endTag);
};

makeEmpty函數 

//定義makeEmpty函數
template <typename T>void List<T>::makeEmpty(){  
	LinkNode<T> *q;   //定義一個LinkNode類型的指針p
	while (first->link)	{    //隻要首節點之後不是NULL
		q = first->link;     //q指向首節點之後的第一個結點
		first->link = q->link; //first指向第一個結點後面的結點（如果後面沒有則指向NULL
		delete q;            //釋放p的空間
	}
}
/*注意這裡沒有first = first -> link，也就是first指針并沒有後移*/
/*調用時，如List<int> list;  list.makeEmpty();*/

這樣删下來此連結清單就變成了一個隻有首節點的空連結清單。

關于inputFront和inpurRear

1、inputFront——在連結清單頭指針後插入新結點

template <typename T>void List<T>::inputFront(T endTag){ //傳入資料設為結束标記
	LinkNode<T> *newNode;    //定義一個指向結點的指針newNode
	T val;                   //一個類型為T的資料元素
	cin >> val;
	while ( val != endTag){
		newNode = new LinkNode<T>(val);  //調用關鍵字new配置設定記憶體，調用LinkNode的構造函數
		if (!newNode){       //如果newNode配置設定的空間不為0，配置設定成功
			cerr << "Memory allocating error!" << endl;
			exit(1);
		}
		newNode->link = first->link; //兩步插入下一個結點
		first->link = newNode;
		cin >> val;
	}
}

2、inputRear——在連結清單尾部插入新結點

template <typename T>void List<T>::inputRear(T endTag){
	LinkNode<T> *newNode, *last=first;  //定義兩個LinkNode型指針，last指向first
	T val;      
	while(last->link!=NULL) last=last->link; //使last指向最後一個結點
	cin >> val;   //輸入val
	while (val != endTag){   
		newNode = new LinkNode<T>(val);
		if (!newNode){
			cerr << "Memory allocating error!" << endl;
			exit(1);
		}
		last->link = newNode;
		last = newNode;
		cin >> val;
	}
	last->link = NULL;
}

關于void input(T endTag, InsMod im = INR);

在開頭定義了枚舉變量InsMod（難怪我搜不到這個變量）

template <typename T>void List<T>::input(T endTag, InsMod im){
//InsMod是一個狀态變量，此函數傳入需要放傳入連結表的資料endTag和狀态變量
	if (im == INF)	inputFront(endTag);  //如果狀态為INF，則在鍊首放入endTag
	else  inputRear(endTag);    //否則在連結清單尾部放入endTag
}

List類構造函數

LinkNode的構造函數（類内定義）

LinkNode(LinkNode<T> *ptr = NULL){
		link = ptr;
	}
	LinkNode(const T &item, LinkNode<T> *ptr = NULL){
		data = item;
		link = ptr;
	}

List的構造函數（類内定義）

List(){
		first = new LinkNode<T>;
	}
	List(const T &x){           //頭結點中可放特殊資訊
		first = new LinkNode<T>(x);
	}
	List(List<T> &L);           //拷貝構造函數
	~List(){                    //析構函數
		makeEmpty();
		delete first;
	}

List拷貝構造函數（類外定義）

template <typename T>List<T>::List(List<T> &L){   //拷貝構造函數
	T value;
	LinkNode<T> *srcptr = L.first();    //srcptr指向L的第一個結點 
	LinkNode<T> *destptr = first = new LinkNode<T>; //destptr指向本單連結清單的第一個結點并配置設定空間
	while (srcptr->link){               //周遊連結清單L
		value = srcptr->link->data;     //第一個結點是空的，如果不是空的，可以省掉->link
		destptr->link = new LinkNode<T>(value);  //同樣，本連結清單第一個結點也是空的，第二個結點指派為value
		destptr = destptr->link;        //destptr指針後移
		srcptr = srcptr->link;          //srcptr指針後移
	}
	destptr->link = NULL;               //設定最後一個結點指針指向NULL
}

提問1：為什麼連結清單的第一個結點是空的？

這是一種程式設計習慣。頭結點其實也可以放資料，隻是在連結清單節點的插入，删除操作中極為不便，尤其是雙向連結清單，邏輯通用性不強，處理不好很容易出錯。

提問2：為什麼連結清單類的元素first是指針而構造函數中卻有

first()

？

不加括号也可以正常編譯正常調用，也許是C++中允許的一種寫法。

inverse函數 

template <typename T>void List<T>::Inverse(){ //沒有傳回值
	LinkNode<T> *h, *p, *pr;  //定義指針h、p、pr
	h = NULL;  //先讓h指向NULL
	p = first->link;  //p指向首結點後面的結點
	while (p){   //通過p來周遊連結清單
		pr = h;  
		h = p;   
		p = h->link; 
		h->link = pr; 
	}
	//循環過後h指向原結點最後一個結點
	first->link = h; //使首節點指向h，完成連結清單的逆轉
}

insert函數 

template <typename T> bool List<T>::Insert(int i, T &x){
	LinkNode<T> *current = Locate(i);  //定義一個current指針。Locate函數傳回第i個結點的指針LinkNode<T> *Locate(int i);
	if (!current)	return false; //當第i個為NULL時，傳回false
	LinkNode<T> *newNode = new LinkNode<T>(x); //為指針newNode配置設定一個新結點
	if (!newNode){ //如果沒有配置設定成功，調用cerr
		cerr << "Memory allocating error!" << endl; 
		//在輸出錯誤資訊時一般用cerr，因為它不占用緩存區
		exit(1);
	}
	newNode->link = current->link; 
	current->link = newNode;
	return true;
}

提問：為什麼第一個錯誤是return false，第二個錯誤是exit(1)？

exit是在調用處強行退出程式，運作一次程式就結束。這個狀态辨別了應用程式的一些運作資訊，這個資訊和機器和作業系統有關。return是函數的退出(傳回)；exit是程序的退出。exit(0)是正常退出,就是代碼一切正常的時候的退出。

Locate函數 

template <typename T>LinkNode<T> *List<T>::Locate(int i){
//函數傳回LinkNode型指針，輸入參數為整數i
	if (i < 0)	return NULL;  //如果輸入号碼小于0，傳回NULL
	LinkNode<T> *current = first; 
	//設定一個LinkeNode型指針current，初始狀态指向首結點
	int k = 0; //設定k為計數器，走到第i個結點時停止
	while (current && k < i){ //部分周遊連結清單
		current = current->link; //current後移
		k++; 
	}
	return current;
}

remove函數 

template <typename T>bool List<T>::Remove(int i, T &x){
	LinkNode<T> *current = Locate(i-1);  //将current指針定位到第i-1個結點
	if (!current || !current->link)	return false; 
	//如果第i-1個或者第i個指針為NULL，則傳回false
	LinkNode<T> *del = current->link; //指針del指向第i個結點
	current->link = del->link;  //使第i-1個結點指針域指向第i+1個結點
	x = del->data; //x等于第i個結點的資料元素
	delete del;   //釋放第i個結點的記憶體
	return true;  
}

search函數 

template <typename T>LinkNode<T> *List<T>::Search(const T &x){
//Search函數傳回指向結點的指針
	LinkNode<T> *current = first->link;  //定義current指針指向第一個結點
	while (current && current->data != x){ //周遊連結清單
		current = current->link; 
	}
	return current; //找到時傳回current指針
}

整一個頭檔案 

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include <cassert>
using namespace std;
#ifndef INSMOD_INF_INR
#define INSMOD_INF_INR
enum InsMod {INF, INR};//¶¨ÒåÏòÇ°»¹ÊÇÏòºóÉú³É
#endif
template <typename T>struct LinkNode{
	T data;
	LinkNode<T> *link;
	LinkNode(LinkNode<T> *ptr = NULL){
		link = ptr;
	}
	LinkNode(const T &item, LinkNode<T> *ptr = NULL){
		data = item;
		link = ptr;
	}
};

template <typename T>class List{
public:
	List(){
		first = new LinkNode<T>;
	}
	List(const T &x){//Í·½áµãÖпɷÅÌØÊâÐÅÏ¢
		first = new LinkNode<T>(x);
	}
	List(List<T> &L);
	~List(){//¸Ä
		makeEmpty();
		delete first;
	}
	void makeEmpty();
	int Length()const;
	LinkNode<T> *getHead()const{
		return first;
	}
	LinkNode<T> *Search(const T &x);
	LinkNode<T> *Locate(int i);
	bool getData(int i,T&x)const;
	void setData(int i, T &x);
	bool Insert(int i, T &x);
	bool Remove(int i, T &x);
	bool IsEmpty()const{
		return (first->link == NULL)?true:false;
	}
	bool IsFull()const{
		return false;
	}
	void Sort();
	void Inverse();
	void input(T endTag, InsMod im = INR);
	void output();
	List<T> &operator = (List<T> &L);
	friend ostream& operator << (ostream &out, List<T> &L){
		LinkNode<T> *current = L.first->link;
		while (current){
			out << current->data <<'\t';
			current = current->link;
		}
		out<<endl;
		return out;
	}
	friend istream& operator >> (istream &in, List<T> &L){//ÒѸÄ
		LinkNode<T> *newNode,*last;
		T val;
		L.makeEmpty();
		last = L.first;
		while (!in.eof()){
			in >> val;
			newNode = new LinkNode<T>(val);
			assert(newNode);
			last->link = newNode;
			last = newNode;
		}
		last->link = NULL;
		return in;
	}
protected:
	LinkNode<T> *first;
	void inputFront(T endTag);
	void inputRear(T endTag);
};

template <typename T>List<T>::List(List<T> &L){
	T value;
	LinkNode<T> *srcptr = L.first;
	LinkNode<T> *destptr = first = new LinkNode<T>;
	while (srcptr->link){
		value = srcptr->link->data;
		destptr->link = new LinkNode<T>(value);
		destptr = destptr->link;
		srcptr = srcptr->link;
	}
	destptr->link = NULL;
}

template <typename T>void List<T>::makeEmpty(){
	LinkNode<T> *q;
	while (first->link)	{
		q = first->link;
		first->link = q->link;
		delete q;
	}
}

template <typename T>int List<T>::Length()const{
	LinkNode<T> *p = first->link;
	int count = 0;
	while (p){
		p = p->link;
		count++;
	}
	return count;
}

template <typename T>LinkNode<T> *List<T>::Search(const T &x){
	LinkNode<T> *current = first->link;
	while (current && current->data != x){
		current = current->link;
	}
	return current;
}

template <typename T>LinkNode<T> *List<T>::Locate(int i){//¸Ä
	if (i < 0)	return NULL;
	LinkNode<T> *current = first;
	int k = 0;
	while (current && k < i){
		current = current->link;
		k++;
	}//δÕÒµ½·µ»ØNULL
	return current;
}

template <typename T>bool List<T>::getData(int i,T&x)const{
	if (i <= 0)	return NULL;
	LinkNode<T> *current = Locate(i);
	if (!current)	return false;
	else{
		x=current->data;
		return true;
	}
}

template <typename T>void List<T>::setData(int i, T &x){
	if (i <= 0)	return;
	LinkNode<T> *current = Locate(i);
	if (!current)	return;
	else	current->data = x;
}

template <typename T> bool List<T>::Insert(int i, T &x){
	LinkNode<T> *current = Locate(i);
	if (!current)	return false;
	LinkNode<T> *newNode = new LinkNode<T>(x);
	if (!newNode){
		cerr << "Memory allocating error!" << endl;
		exit(1);
	}
	newNode->link = current->link;
	current->link = newNode;
	return true;
}

template <typename T>bool List<T>::Remove(int i, T &x){
	LinkNode<T> *current = Locate(i-1);
	if (!current || !current->link)	return false;
	LinkNode<T> *del = current->link;
	current->link = del->link;
	x = del->data;
	delete del;
	return true;
}

template <typename T> void List<T>::output(){
	LinkNode<T> *current = first->link;
	while (current){
		cout << current->data << endl;
		current = current->link;
	}
}

template <typename T> List<T> &List<T>::operator = (List<T> &L){//¸Ä
	T value;
	LinkNode<T> *destptr=first,*srcptr = L.first;
	makeEmpty();//ÏÈÇå¿Õ£¬ºó¸´ÖÆ
	while (srcptr->link)
	{
		value = srcptr->link->data;
		destptr->link = new LinkNode<T>(value);
		destptr = destptr->link;
		srcptr = srcptr->link;
	}
	destptr->link = NULL;
	return *this;
}

template <typename T>void List<T>::input(T endTag, InsMod im){
	if (im == INF)	inputFront(endTag);
	else	inputRear(endTag);
}

template <typename T>void List<T>::inputFront(T endTag){//¸Ä£¬Ìí¼Ó
	LinkNode<T> *newNode;
	T val;
	cin >> val;
	while ( val != endTag){
		newNode = new LinkNode<T>(val);
		if (!newNode){
			cerr << "Memory allocating error!" << endl;
			exit(1);
		}
		newNode->link = first->link;
		first->link = newNode;
		cin >> val;
	}
}

template <typename T>void List<T>::inputRear(T endTag){//¸Ä
	LinkNode<T> *newNode, *last=first;
	T val;
	while(last->link!=NULL) last=last->link;
	cin >> val;
	while (val != endTag){
		newNode = new LinkNode<T>(val);
		if (!newNode){
			cerr << "Memory allocating error!" << endl;
			exit(1);
		}
		last->link = newNode;
		last = newNode;
		cin >> val;
	}
	last->link = NULL;
}

template <typename T>void List<T>::Sort(){
}

template <typename T>void List<T>::Inverse(){
	LinkNode<T> *h, *p, *pr;
	h = NULL;
	p = first->link;
	while (p){
		pr = h;
		h = p;
		p = h->link;
		h->link = pr;
	}
	first->link = h;
}
#endif
資料結構筆記 資料結構 連結清單
上一篇: 09python之函數三
下一篇: 計算機定義 馮諾依曼,馮・諾伊曼計算機——一個程式員的基本修養（1）

繼續閱讀