C++数据结构：单链表、双链表与循环链表

曾经终败给现在 2022-03-08 15:24 366阅读 0赞

注意：以下所有链表均包含空的头结点。

# 1 单链表（SingleLinkedList） #

## 1.1 代码 ##

#include "stdafx.h"
    #include <iostream>
    
    using namespace std;
    
    //节点类
    class Node { 
    public:
    	int data;
    	Node * next;
    
    	//两个参数的构造函数
    	Node(const int info, Node * nextValue) { 
    		data = info;
    		next = nextValue;
    	}
    
    	//一个参数的构造函数
    	Node(Node * nextValue) { 
    		next = nextValue;
    	}
    };
    
    //单链表类
    class SingleLinkedList { 
    private:
    	Node *head, *tail;
    
    	//返回线性表指向第p个元素的[指针值]
    	Node *setPos(const int i) { 
    		int count = 0;
    		if (i == -1) { 
    			return head;
    		}
    		Node *p = new Node(head->next);
    		while (p != NULL && count < i) { 
    			p = p->next;
    			count++;
    		}
    		return p;
    	}
    
    public:
    	SingleLinkedList() { 
    		head = tail = new Node(NULL);
    	}
    
    	~SingleLinkedList() { 
    		Node *tmp;
    		while (head != NULL) { 
    			tmp = head;
    			head = head->next;
    			delete tmp;
    		}
    	}
    
    	//判断链表是否为空
    	bool isEmpty() { 
    		if (head->next == NULL)
    			return true;
    		else
    			return false;
    	}
    
    	//将链表内容清除
    	void clear() { 
    		Node *tmp;
    		while (head != NULL) { 
    			tmp = head;
    			head = head->next;
    			delete tmp;
    		}
    		head = tail = new Node(NULL);
    	}
    
    	//返回当前链表长度
    	int length() { 
    		int count = 0;
    		Node *p = new Node(head->next);
    		while (p != NULL) { 
    			p = p->next;
    			count++;
    		}
    		return count;
    	}
    
    	//在表尾添加一元素
    	bool append(const int value) { 
    		Node *p = new Node(value, tail->next);
    		tail->next = p;
    		tail = p;	//tail重置
    		return true;
    	}
    
    	//在位置i上插入一个元素value
    	bool insert(const int i, const int value) { 
    		Node *p, *q;
    		if ((p = setPos(i - 1)) == NULL) { 
    			cout << "Illegle location of insertion!" << endl;
    			return false;
    		}
    		q = new Node(value, p->next);	//q是待插入元素
    		p->next = q;
    		if (p == tail)	//插入点在链尾
    			tail = q;
    		return true;
    	}
    
    	//在位置i上删除该元素
    	bool drop(const int i) { 
    		Node *p, *q;
    		if ((p = setPos(i - 1)) == NULL || p == tail) { 
    			cout << "Illegle location of delete operation!" << endl;
    			return false;
    		}
    		q = p->next;	//q是待删除元素
    		if (q == tail) { 
    			tail = p;
    			p->next = NULL;
    			delete q;
    		}
    		else if (q != NULL) { 
    			p->next = q->next;
    			delete q;
    		}
    	}
    
    	//通过value返回位置p的元素值
    	bool getValue(const int p, int & value) { 
    		if (p == -1) { 
    			value = NULL;
    			return false;
    		}
    		Node *q = head;
    		for (int i = 0; i < p; i++) { 
    			q = q->next;
    		}
    		value = q->data;
    		return true;
    	}
    
    	//查找值为value的元素并通过p返回其第一次出现时的位置
    	bool getPos(int &p, const int value) { 
    		Node *q;
    		p = 0;
    		for (q = head; q != NULL; q = q->next, ++p) { 
    			if (q->data == value) { 
    				return true;
    				break;
    			}
    		}
    		return false;
    	}
    };

## 1.2 测试 ##

int main()
    { 
    	SingleLinkedList test;
    	int tmp;
    
    	if (test.isEmpty())
    		cout << "Empty linked list." << endl;
    	else
    		cout << "Linked list is Not Empty." << endl;
    	cout << "Length: " << test.length() << endl;	//空表头，长度一开始就是1
    	test.append(1);
    	test.append(2);
    	test.append(3);
    	test.getValue(0, tmp);
    	cout << "Value: " << tmp << endl;
    	test.getValue(1, tmp);
    	cout << "Value: " << tmp << endl;
    	test.getValue(2, tmp);
    	cout << "Value: " << tmp << endl;
    	test.getValue(3, tmp);
    	cout << "Value: " << tmp << endl;
    	if (test.isEmpty())
    		cout << "Empty linked list." << endl;
    	else
    		cout << "Linked list is Not Empty." << endl;
    	cout << "Length: " << test.length() << endl;
    	test.insert(2, 4);
    	test.getPos(tmp, 4);
    	cout << "Positon: " << tmp << endl;
    	test.getValue(2, tmp);
    	cout << "Value: " << tmp << endl;
    	test.drop(2);
    	return 0;
    }

## 1.3 输出 ##

Empty linked list.
    Length: 1
    Value: 0
    Value: 1
    Value: 2
    Value: 3
    Linked list is Not Empty.
    Length: 4
    Positon: 2
    Value: 4

# 2 双链表（DoubleLinkedList） #

这部分代码相较于1.1节的内容修改不大，主要变化体现在`insert()`和`drop()`方法内部以及类`DoubleLinkedList`中函数的形参变化上。  
测试用例和输出结果同1.2和1.3节，故省略。

#include "stdafx.h"
    #include <iostream>
    
    using namespace std;
    
    //节点类
    class Node { 
    public:
    	int data;
    	Node * next;
    	Node * prev;
    
    	//包含值和前后指针三个参数的构造函数
    	Node(const int info, Node * preValue, Node * nextValue) { 
    		data = info;
    		prev = preValue;
    		next = nextValue;
    	}
    
    	//包含前后指针两个参数的构造函数
    	Node(Node * preValue, Node * nextValue) { 
    		prev = preValue;
    		next = nextValue;
    	}
    };
    
    //双链表类
    class DoubleLinkedList { 
    private:
    	Node *head, *tail;
    
    	//返回线性表指向第p个元素的[指针值]
    	Node *setPos(const int i) { 
    		int count = 0;
    		if (i == -1) { 
    			return head;
    		}
    		Node *p = new Node(head, head->next);
    		while (p != NULL && count < i) { 
    			p = p->next;
    			count++;
    		}
    		return p;
    	}
    
    public:
    	DoubleLinkedList() { 
    		head = tail = new Node(NULL, NULL);
    	}
    
    	~DoubleLinkedList() { 
    		Node *tmp;
    		while (head != NULL) { 
    			tmp = head;
    			head = head->next;
    			delete tmp;
    		}
    	}
    
    	//判断链表是否为空
    	bool isEmpty() { 
    		if (head->next == NULL)
    			return true;
    		else
    			return false;
    	}
    
    	//将链表内容清除
    	void clear() { 
    		Node *tmp;
    		while (head != NULL) { 
    			tmp = head;
    			head = head->next;
    			delete tmp;
    		}
    		head = tail = new Node(NULL, NULL);
    	}
    
    	//返回当前链表长度
    	int length() { 
    		int count = 0;
    		Node *p = new Node(head, head->next);
    		while (p != NULL) { 
    			p = p->next;
    			count++;
    		}
    		return count;
    	}
    
    	//在表尾添加一元素
    	bool append(const int value) { 
    		Node *p = new Node(value, tail, tail->next);
    		tail->next = p;
    		tail = p;	//tail重置
    		return true;
    	}
    
    	//在位置i上插入一个元素value
    	bool insert(const int i, const int value) { 
    		Node *p, *q;
    		if ((p = setPos(i - 1)) == NULL) { 
    			cout << "Illegle location of insertion!" << endl;
    			return false;
    		}
    		q = new Node(value, p, p->next);	//q是待插入元素
    		q->prev = p;
    		q->next = p->next;
    		p->next = q;
    		q->prev->next = q;
    		if (p == tail)	//插入点在链尾
    			q = tail;
    		return true;
    	}
    
    	//在位置i上删除该元素
    	bool drop(const int i) { 
    		Node *p;		//p本身就是待删除元素
    		if ((p = setPos(i - 1)) == NULL || p == tail) { 
    			cout << "Illegle location of delete operation!" << endl;
    			return false;
    		}
    		if (p == tail) { 
    			tail = p->prev;
    			p->prev->next = NULL;
    			delete p;
    		}
    		else if (p != NULL) { 
    			p->prev->next = p->next;
    			p->next->prev = p->prev;
    			p->prev = NULL;
    			p->next = NULL;
    			delete p;
    		}
    	}
    
    	//通过value返回位置p的元素值
    	bool getValue(const int p, int & value) { 
    		if (p == -1) { 
    			value = NULL;
    			return false;
    		}
    		Node *q = head;
    		for (int i = 0; i < p; i++) { 
    			q = q->next;
    		}
    		value = q->data;
    		return true;
    	}
    
    	//查找值为value的元素并通过p返回其第一次出现时的位置
    	bool getPos(int &p, const int value) { 
    		Node *q;
    		p = 0;
    		for (q = head; q != NULL; q = q->next, ++p) { 
    			if (q->data == value) { 
    				return true;
    				break;
    			}
    		}
    		return false;
    	}
    };