线性表（3）——链表的实现

南航自己的教材伪代码看的我有点头晕，不过好歹完成了。后面的双向链表等笔者便不写了，有兴趣的读者可以自行尝试。

需要说明的地方有：首先，我的pos，或者说索引是从0开始的，而length是有几个算几个（1个，2个……）也就是说最后一个索引是length-1——这是为了和C++自带的vector等一致。书上写的有点乱，掌握知识就行，不要管这些。

插入操作的pos我这里指代的是插入后这个插入元素的索引就是pos，也就是插入到pos-1后面。而删除是删除以pos为索引的元素。

另外为了和书上一致，head为空表头，不存储数据。

0.节点的声明

				
					template <typename Data>
struct Node{
	Data item;
	struct Node<Data>* next;
};

1.链表初始化

				
					List()//替代initiallist
	{
		head=(Node<Data> *)malloc(sizeof(Node<Data>));
		head->next=nullptr;
		tail=nullptr;
		current=nullptr;
		length=0;
	}

2.删除链表

				
						bool DestroyList()
	{
		Node<Data> *tmp;
		while(head->next!=nullptr)
		{
			tmp=head->next;
			head->next=tmp->next;
			free(tmp);
		}
		free(head);
		head=nullptr;
		tail=nullptr;
		current=nullptr;
		length=0;
		
		return true;
	}

3.插入项

				
						bool InsertItem(Data d,int pos)
	{
		//0.找到当前节点，书上没有，我也不知道想干嘛，这段代码供参考
		if(pos==0)
			current=head;
		else if(pos==length)
			if(length==0)//这里是一个特判，想想看为什么要这么做？
				current=head;
			else
				current=tail;
		else{
			current=head;
			for(int i=0;i<pos;i++)
				current=current->next;//前进到相应项
		}
		//1.申请空间
		Node<Data> *tmp=(Node<Data> *)malloc(sizeof(Node<Data>));
		if(tmp==nullptr)
		{
			cout<<"overflow error.";
			return false;
		}
		tmp->item=d;
		//2.插入当前项后面
		tmp->next=current->next;
		current->next=tmp;
		//3.善后
		if(current==tail)
			tail=tmp;
		if(length==0)//除此之外，在刚刚插入第一项后，要把尾巴设置好
			tail=head->next;
		//4.链表长度自增
		++length;
		
		return true;
	}

4.删除项

				
						Data DelItem(int pos)
	{
		//0
		if(pos>length-1)//我们让pos从0开始，而length是1个，2个……与vector等保持一致
		{
			cout<<"the end of List is nullptr"<<endl;
			return 0;
		}
		//1保存待删除节点数据
		Node<Data>* current =head;
		for(int i=0;i<pos;i++)
		{
			current=current->next;
		}
		int tmp=current->next->item;
		//2删除当前节点
		Node<Data> *p=current->next;
		current->next=p->next;
		free(p);
		if(current->next==nullptr) tail=current;
		//3长度自减
		--length;
		
		return tmp;
		
	}

5.获得项

				
						Data GetItem(int pos)
	{
		if(pos<0||pos>length)
		{
			cout<<"fail in GetItem";
			exit(1);
		}
		Node<Data>* scan=head->next;
		for(int i=0;i<pos;i++)
			scan=scan->next;
		current=scan;
		return current->item;
	}

6.打印链表

				
					bool TraverseList()
	{
		Node<Data> *scan=head->next;
		while(scan!=nullptr)
		{
			cout<<scan->item<<' ';
			scan=scan->next;
		}
		cout<<endl;
		return true;
	}

7.得到长度

				
						int GetLength()
	{
		return length;
	}

8.所有代码

				
					#include <iostream>
using namespace std;

template <typename Data>
struct Node{
	Data item;
	struct Node<Data>* next;
};

template <typename Data>
class List
{
private:
	
	typedef Node<Data>* LinkList;
	
	LinkList head;
	LinkList tail;
	Node<Data>* current;
	int length;

public:
	List()//替代initiallist
	{
		head=(Node<Data> *)malloc(sizeof(Node<Data>));
		head->next=nullptr;
		tail=nullptr;
		current=nullptr;
		length=0;
	}
	
	bool DestroyList()
	{
		Node<Data> *tmp;
		while(head->next!=nullptr)
		{
			tmp=head->next;
			head->next=tmp->next;
			free(tmp);
		}
		free(head);
		head=nullptr;
		tail=nullptr;
		current=nullptr;
		length=0;
		
		return true;
	}
	
	bool TraverseList()
	{
		Node<Data> *scan=head->next;
		while(scan!=nullptr)
		{
			cout<<scan->item<<' ';
			scan=scan->next;
		}
		cout<<endl;
		return true;
	}
	
	bool InsertItem(Data d,int pos)
	{
		//0.找到当前节点，书上没有，我也不知道想干嘛，这段代码供参考
		if(pos==0)
			current=head;
		else if(pos==length)
			if(length==0)//这里是一个特判，想想看为什么要这么做？
				current=head;
			else
				current=tail;
		else{
			current=head;
			for(int i=0;i<pos;i++)
				current=current->next;//前进到相应项
		}
		//1.申请空间
		Node<Data> *tmp=(Node<Data> *)malloc(sizeof(Node<Data>));
		if(tmp==nullptr)
		{
			cout<<"overflow error.";
			return false;
		}
		tmp->item=d;
		//2.插入当前项后面
		tmp->next=current->next;
		current->next=tmp;
		//3.善后
		if(current==tail)
			tail=tmp;
		if(length==0)//除此之外，在刚刚插入第一项后，要把尾巴设置好
			tail=head->next;
		//4.链表长度自增
		++length;
		
		return true;
	}
	Data GetItem(int pos)
	{
		if(pos<0||pos>length)
		{
			cout<<"fail in GetItem";
			exit(1);
		}
		Node<Data>* scan=head->next;
		for(int i=0;i<pos;i++)
			scan=scan->next;
		current=scan;
		return current->item;
	}
	int GetLength()
	{
		return length;
	}
	
	Data DelItem(int pos)
	{
		//0
		if(pos>=length-1)//我们让pos从0开始，而length是1个，2个……与vector等保持一致
		{
			cout<<"the end of List is nullptr"<<endl;
			exit(1);
		}
		//1保存待删除节点数据
		GetItem(pos-1);
		Data tmp=current->next->item;
		//2删除当前节点
		Node<Data> *p=current->next;
		current=p->next;
		free(p);
		if(current->next==nullptr) tail=current;
		//3长度自减
		--length;
		
		return tmp;
		
	}
};
int main()
{
	List<int> list;
	for(int i=0;i<15;i++)
	{
		list.InsertItem(i,i);
	} 
	list.InsertItem(15,3);
	list.TraverseList();
	cout<<list.GetLength()<<endl;
	cout<<list.GetItem(14)<<endl;
	cout<<list.DelItem(14)<<endl;
	
	return 0;
}

9.额外的话

使用类模板出现了一些问题，不过好在已经解决了。线性表的相关知识就写到这里，读者可以尝试自己写循环链表、双向链表等……本次代码部分参考了《C++ Primer Plus》中的内容，如果你是大一学生我强烈推荐阅读这本书。

之后的栈与队列，可以很简单的使用链表制作出来，笔者不打算写了。不过这也要看后来心情，例如链表笔者本打算使用大一上的，今天也用类的思想重新写了。不说了，笔者打会游戏去了。

订阅评论

1 评论

最旧

柒氿