数据结构笔记二_线性表的链式存储结构

2024-02-01 20:19:40

线性表

线性表的基本定义和顺序存储的实现见上一篇博客：https://blog.csdn.net/weixin_51352359/article/details/120497500

线性表的链式存储结构

线性表的抽象类

首先依据线性表要实现的功能，定义线性表的类模板即父类（当然这一步也可以不做）：

template<class elemType>
class list {
public:
	//对于属性类的函数，因其并不改变原数组or链表的值，在后面加const
	//可以达到保护隐含this指针以及供常对象使用的目的
	virtual int length() const = 0;
	virtual int search(const elemType& x) const = 0;
	//const &结构：在数据类型未知or比较复杂时，可以提高运行效率，同时节省空间
	virtual elemType visit(int i) const = 0;

	//数据操纵类函数
	virtual void insert(int i, const elemType& x) = 0;
	virtual void remove(int i) = 0;
	virtual void clear() = 0;

	//遍历操作
	virtual void traverse()const = 0;

	//析构函数,防止内存泄露
	virtual ~list() {};
};

单链表类的定义

关于单链表的一些基本概念，可以参考以前的博客：
https://blog.csdn.net/weixin_51352359/article/details/120471969

单链表的存储映像图如下：

描述单链表只需要一个指向头结点的指针型变量——头指针，这里用head指针。

利用内嵌类

//单链表类的定义
template<class elemType>
class linkList :public list<elemType> {
private:
	struct node {//内嵌类
		elemType data;
		node* next;
	//构造函数
	node(const elemType& x, node* p = NULL) { data = x; next = p; }
	node():next(NULL){}
	//析构函数
	~node(){}
	}
	node* head;
public:
	linkList();
	~linkList() { clear(); delete head; }
	int length() const;
	int search(const elemType& x)const;
	elemType visit(int i)const;
	void insert(int i, const elemType& x);
	void remove(int i);
	void clear();
	void traverse()const;
};

基本操作实现

构造类

构造函数

template<class elemType>
linkList<elemType>::linkList() {
	head = new node();
}

属性类

求链表的长度
从首节点开始，沿着后继指针链一个一个往后数，数到一个节点长度加1

template<class elemType>
int linkList<elemType>::length() {
	int count = 0;
	node* p = head->next;//指向首节点
	while (p != NULL) {
		count++; p = p->next;
	}
	return count;
}

搜索某个元素在线性表中是否存在,并返回元素下标

template<class elemType>
int linkList<elemType>::search(const elemType& x)const {
	//首节点位置为0
	int pos = -1;
	node* p = head->next;
	while (p) {
		pos++;
		if (p->data == x)break;
		p = p->next;
	}
	if (!p) return-1;//并未找到
	return pos;
}

访问某个元素

template<class elemType>
elemType linkList<elemType>::visit(int i)const {
	//判断i是否出界，若出界则直接跳出
	if (i<0 || i>length()) throw OutOfBound();
	int count = 0;
	node* p = head->next;
	while (p) {
		if (count == i)break;
		else {
			count++;
			p = p->next;
		}
	}
	return p->data;
}

操纵类

在位置i插入某个元素x
首先考虑最简单的情况，即在首节点后插入一个节点（首席插入法）

tmp = new node(x);//新建节点
tmp->next = head->next;//使自己指向下一个节点
head->next = tmp;//使上一个节点指向自己，链入完毕

之后考虑一般情况，即在第i个位置插入元素。由上述可知，在定位到第i-1个元素后，元素的插入就变得很简单了，故主要分为一下几步：

new一个新节点tmp存储元素
使指针p指向第i-1个元素
链入链表

//在第i-1个后面插入
template<class elemType>
void linkList<elemType>::insert(int i, const elemType& x) {
	if (i<0 || i>length()) throw OutOfBound();
	node* tmp;
	tmp = new node(x);//node的构造函数
	//使p指向第i-1个节点
	int count = 0;
	p = head;
	while (count < i) {
		p = p->next;
		count++;
	}
	//链入tmp
	tmp->next = p->next;
	p->next = tmp;
}

删除第i个位置的元素
同上，删除首节点最为简单：

node* tmp = head->next;
if (!tmp)return;//注意： tmp可能为空！！
head->next = tmp->next;
delete tmp;

之后进入到一般情况：

template<class elemType>
void linkList<elemType>::remove(int i) {
	if (i<0 || i>=length()) throw OutOfBound();
	//让p指向第i-1个位置
	node* q,*p = head;
	int count = 0;
	while (count < i) {
		p = p->next;
		if (!p)return;//如果p为空，则直接返回 和上面的边界判定其实有重合
		count++;
	}
	q = p->next;
	if (!q) return;
	p->next = q->next;
	delete q;
}

清除一个线性表clear（）

template<class elemType>
void linkList<elemType>::clear() {
	//第一种方法：永远删首节点
	node* p = head->next;
	while (p) {
		head->next = p->next;
		delete p;
		p = head->next;
	}
	head->next = NULL;
	/*
	//第二种方法：兄弟协同法
	node* p = head->next, * q;
	head->next = NULL;
	while (p) {
		q = p->next;
		delete p;
		p = q;
	}
	*/
	}

遍历类：即将线性表中的所有元素输出

template<class elemType>
void linkList<elemType>::traverse() {
	node* p = head->next;
	while(p)
	{
		cout << p->data << " ";
		p = p->next;
	}
}

代码集合清单：

头文件
并未使用父类，主要利用友元实现，其中要注意node类的使用。如若不用友元，代码中也提供了另一种实现方式。

//文件名：linklist.h
#include<iostream>
using namespace std;

class outOfBound {};

/*
//类模板的定义
//在使用这种情况时，node可以直接使用，而不用使用node<elemType>
template<class elemType>
class linkList {
private:
	struct node {
		elemType data;
		node* next;
		node(const elemType& x, node* p = NULL) { data = x; p = next; }
		node() :next(NULL) {}
		~node() {}
	};
	node* head;
public:
	linkList();
	~linkList() { clear(); delete head; }
	int length()const;
	int search(const elemType& x)const;
	elemType visit(int i)const;
	void insert(int i, const elemType& x);
	void remove(int i);
	void clear();
	void traverse()const;
};
*/

//如果用下面这种方式定义，node需用node<elemType>
template<class elemType>
class linkList;//前声明
template<class elemType>
class node {
	friend class linkList<elemType>;
private:
	elemType data;
	node* next;
public:
	node(const elemType& x, node* p = NULL) {
		data = x; next = p;
	}
	node() :next(NULL) {}
};

template<class elemType>
class linkList {
private:
	node<elemType>* head;
public:
	linkList();
	~linkList() { clear(); delete head; }
	int length()const;
	int search(const elemType& x)const;
	elemType visit(int i)const;
	void insert(int i, const elemType& x);
	void remove(int i);
	void clear();
	void traverse()const;
};


//基本操作实现
template<class elemType>
linkList<elemType>::linkList() {
	head = new node<elemType>();
}

template<class elemType>
int linkList<elemType>::length() const{
	//首节点长度为1
	int count = 0;
	node<elemType>* p = head->next;
	while (p) {
		count++;
		p = p->next;
	}
	return count;
}

template<class elemType>
int linkList<elemType>::search(const elemType& x)const {
	//首节点下标为0
	int count = 0;
	node<elemType>* p = head->next;
	while (p) {
		if (p->data == x)break;
		else count++;
		p = p->next;
	}
	if (!p)return -1;
	else return count;
}

template<class elemType>
elemType linkList<elemType>::visit(int i)const {
	//首节点下标为0
	if (i<0 || i>length() - 1) throw outOfBound();
	int count = 0;
	node<elemType>* p = head->next;
	while (p) {
		if (count == i) break;
		count++;
		p = p->next;
	}
	return p->data;
}

template<class elemType>
void linkList<elemType>::insert(int i, const elemType& x) {
	if (i<0 || i>length()) throw outOfBound();
	node<elemType>* tmp = new node<elemType>(x);
	node<elemType>* p = head;
	int count = 0;
	while (p) {
		if (count == i) break;
		count++;
		p = p->next;
	}
	tmp->next = p->next;
	p->next = tmp;
}

template<class elemType>
void linkList<elemType>::remove(int i){
	if (i<0 || i>length()-1) throw outOfBound();
	int count = 0;
	node<elemType>* p = head;
	while (p) {
		if (count == i) break;
		count++;
		p = p->next;
	}
	node<elemType>* tmp = p->next;
	p->next = tmp->next;
	delete tmp;
}

template<class elemType>
void linkList<elemType>::clear() {
	node<elemType>* p = head->next;
	head->next = NULL;
	if (!p) return;
	node<elemType>* q = p->next;
	while (q) {
		delete p;
		p = q;
		q = p->next;
	}
	delete p;
}

/*
template<class elemType>
void linkList<elemType>::clear() {
	node* p = head->next;
	while (p) {
		head->next = p->next;
		delete p;
		p = head->next;
	}
}
*/

template<class elemType>
void linkList<elemType>::traverse() const {
	node<elemType>* p = head->next;
	while (p) {
		cout << p->data << " ";
		p = p->next;
	}
}

主函数
功能测试，将一个字符串的首字符删除并插入到中间位置

#include<iostream>
#include"linklist.h"
using namespace std;

int main() {
	linkList<char> chlist;

	char ctemp;
	int i, n, result;

	cout << "number of the elements:" << endl;
	cin >> n;
	cin.get(ctemp);//将enter抛弃

	cout << "input the elements:\n" << endl;
	//将字符逐个输入到表中，并依次插入表尾
	for (i = 0; i < n; i++) {
		cin.get(ctemp);
		chlist.insert(i, ctemp);
	}
	ctemp = chlist.visit(0);//获得首节点
	chlist.remove(0);//将首节点删除
	chlist.insert((chlist.length() + 1) / 2, ctemp);//将删除的首节点放在中间位置

	cout << "output the elements:\n" << endl;
	for (i = 0; i < chlist.length(); i++) {
		cout.put(chlist.visit(i));//读取第i个节点的值并输出
	}
	cout << endl;
	cout << endl;
	chlist.traverse();//遍历输出
	cout << endl;
	cout << endl;
	cout << chlist.search('a');
	return 0;
}

代码运行结果：

码农公寓

线性表

线性表的链式存储结构

线性表的抽象类

单链表类的定义

基本操作实现

代码集合清单：

相关文章