《数据结构与算法》——线性表之链表（LinkList）总结

今天药忘吃喽~ 2021-11-23 04:24 358阅读 1赞

# 《数据结构与算法》——线性表之链表（LinkList）总结 #

在数据结构的基本顺序结构中线性表有两类存储逻辑，一种是[顺序表][Link 1]，一种是链表。链表中又包括单链表、双链表、单循环链表、双循环链表、静态链表。本文对最基本的单链表结构进行总结，剩下的几种除静态链表外均可以在此基础上进行理解以及实现。

结构

LinkNode（结点类）

LinkList（链表类）

类方法实现

错误

总结

参考文献

--------------------

## 结构 ##

首先定义结构，一个链表是由若干个链节点连接而成，头结点可有可无。而每个节点需要包含两个属性，一个是当前节点的值，一个是指向下一节点的指针，二者缺一不可，若有头结点，则可在其数据项位保存长度。

**链表就想象成攀岩，你总得踩住一个点才有机会去踩下一个点，这样一直踩下去总会把所有的点踩个遍，即根据上一个点获取下一个点。**

**[线性表][Link 1]就想象成教学楼一层教室，只要你有房间号你就能很快的到达该教室，无论你知不知道前后教室是哪个。**

## LinkNode（结点类） ##

class LinkNode{
    	private :
    		Elemtype data;
    		LinkNode<Elemtype> *nextNode;
    	public:
    		LinkNode(Elemtype data);//构造函数
    		LinkNode<Elemtype>* next();//获取next指针 
    		Elemtype getData();//获取data值 
    		void setNext(LinkNode<Elemtype> *ln); //设置next指针 
    		~ LinkNode();//析构函数 	
    };

## LinkList（链表类） ##

class LinkList{
    	private :
    		int len;
    		bool flag;//顺序标志 
    		LinkNode<Elemtype> *next;
    	public:
    		LinkList();//构造函数 
    		void InitList();//初始化 
    		void setNext(LinkNode<Elemtype> *ln);//设置下一指针 
    		int length();//获得长度 
    		int LocateElem(Elemtype elem);//按值查找
    		Elemtype GetElem(int i); //按位查找
    		LinkNode<Elemtype>* GetNext();//获//获取下一指针  
    		void ListInsert(int i ,Elemtype elem);
    		void ListDelete(Elemtype elem);//删除元素
    		void PrintList(); 
    		bool Empty();
    		void DestroyList();
    		void MergeList(LinkList lb);//合并两个表，有序 
    		~ LinkList();//析构函数 		
    };

## 类方法实现 ##

/*
    *win10专业版
    *DEV C++ 5.11
    *TDM-GCC 4.9.2 64bit
    */
    #include<iostream>
    #include<malloc.h>
    #include <typeinfo>
    #define WRONG 0
    
    using namespace std;
    template <typename Elemtype>
    class LinkNode{
    	private :
    		Elemtype data;
    		LinkNode<Elemtype> *nextNode;
    	public:
    		LinkNode(Elemtype data);//构造函数
    		LinkNode<Elemtype>* next();//获取next指针 
    		Elemtype getData();//获取data值 
    		void setNext(LinkNode<Elemtype> *ln); //设置next指针 
    		~ LinkNode();//析构函数 
    		
    }; 
    
    
    template <typename Elemtype>
    LinkNode<Elemtype>::LinkNode(Elemtype data){//构造函数 
    	this->data = data;
    	this->nextNode = NULL;
    }
    
    template <typename Elemtype>
    LinkNode<Elemtype>::~ LinkNode(){//析构函数 
    	free(this);
    }
    
    template <typename Elemtype>
    LinkNode<Elemtype>* LinkNode<Elemtype>::next(){//获取next指针 
    	return this->nextNode;
    }
    
    template <typename Elemtype>
    Elemtype LinkNode<Elemtype>::getData(){//获取next指针 
    	return this->data;
    }
    
    template <typename Elemtype >
    void LinkNode<Elemtype>::setNext(LinkNode<Elemtype> *ln){ //设置next指针 
    	this->nextNode = ln;
    }
    
    
    
    
    template <typename Elemtype>
    class LinkList{
    	private :
    		int len;
    		bool flag;//顺序标志 
    		LinkNode<Elemtype> *next;
    	public:
    		LinkList();//构造函数 
    		void InitList();//初始化 
    		void setNext(LinkNode<Elemtype> *ln);//设置下一指针 
    		int length();//获得长度 
    		int LocateElem(Elemtype elem);//按值查找
    		Elemtype GetElem(int i); //按位查找
    		LinkNode<Elemtype>* GetNext();//获//获取下一指针  
    		void ListInsert(int i ,Elemtype elem);
    		void ListDelete(Elemtype elem);//删除元素
    		void PrintList(); 
    		bool Empty();
    		void DestroyList();
    		void MergeList(LinkList lb);//合并两个表，有序 
    		~ LinkList();//析构函数 		
    }; 
    
    template <typename Elemtype>
    LinkList<Elemtype>::LinkList(){//构造函数 
    	this->len = 0;
    	this->next = NULL;
    	this->flag = 1; 
    }
     
    template <typename Elemtype>
    void LinkList<Elemtype>:: InitList(){//初始化 
    	this->LinkList();
    }
    
    template <typename Elemtype >
    void LinkList<Elemtype>::setNext(LinkNode<Elemtype> *ln){ //设置next指针 
    	this->next = ln;
    }
    
    
    
    template <typename Elemtype>
    int LinkList<Elemtype>::length(){//获得长度 
    	return this->len;
    }
     
    template <typename Elemtype>
    int LinkList<Elemtype>::LocateElem(Elemtype elem){//按值查找
    	LinkNode<Elemtype> *temp = this->next;
    	int i = 1;
    	while(temp!=NULL && temp->getData() != elem){//顺序查找值 
    		i++;
    		temp = temp->next();
    	}
    	if(temp->getData() == elem)
    		return i;
    	return 0;//查找失败 
    }
    
    template <typename Elemtype>
    Elemtype LinkList<Elemtype>::GetElem(int i){ //按位查找
    	LinkNode<Elemtype> *temp = this->next;
    	int j = 1; 
    	while((++j!=i) && temp)
    		temp = temp->next();
    	if(i==j)
    		return temp->next()->getData();
    	else
    		return NULL;
    }
     
    template <typename Elemtype>
    LinkNode<Elemtype>* LinkList<Elemtype>::GetNext(){//获取下一指针 
    	return this->next; 
    } 
    
    template <typename Elemtype>
    void LinkList<Elemtype>::ListInsert(int i ,Elemtype elem){//按位插入元素，包括头插尾插 
    	if(i==0)
    		i=1;//头插法 
    	if(i==-1)
    		i = this->len+1;//尾插法 
    	if(i<=0||i>len+1)
    		exit(WRONG);
    	
    	int j = 0;
    	LinkNode<Elemtype> *temp = new LinkNode<Elemtype>(0);
    	if(this->next==NULL){//直接插入点 
    		LinkNode<Elemtype> *inNode = new LinkNode<Elemtype>(elem);
    		this->next = inNode;
    		inNode->setNext(NULL);
    		this->len++; 
    		return;
    	}
    	else//后移 
    		if(i==1){//首插 
    			LinkNode<Elemtype> *inNode = new LinkNode<Elemtype>(elem);
    			inNode->setNext(this->next);
    			this->next = inNode;
    			this->len++; 
    			return;	
    		}
    		else
    			temp = this->next;
    	j+=2;
    	while(j<=i-1){
    		j++;
    		temp = temp->next();
    	}
    		
    	if((this->len==0)||(temp->getData()<=elem&&((temp->next()!=0)||(temp->next()->getData()>=elem))))
    		flag = 1;
    	else
    		flag = 0;
    
    	LinkNode<Elemtype> *inNode = new LinkNode<Elemtype>(elem);
    	inNode->setNext((temp->next()));
    	temp->setNext(inNode);
    	this->len++;
    }
    
     
    template <typename Elemtype>
    void LinkList<Elemtype>::ListDelete(Elemtype elem){//删除元素
    	if(this->len == 0 )
    		exit(WRONG);
    	LinkNode<Elemtype> *pre = this->next;
    	LinkNode<Elemtype> *temp = this->next;
    	if(pre->getData()==elem){//判断首元素
    		this->next=this->next->next();
    		free(temp);
    		this->len--;
    		return ;
    	}
    	while(temp->getData()!=elem && temp){
    		pre = temp;
    		temp = temp->next();
    	}
    	if (temp->getData() == elem){
    		pre->setNext(temp->next()) ;
    		free(temp);
    		this->len--;
    	}
    	else
    		exit(WRONG);	
    }
     
    template <typename Elemtype>
    void LinkList<Elemtype>::PrintList(){ 
    	LinkNode<Elemtype> *temp = this->next;
    	cout<<"[ ";
    	if(this->len==0){
    		cout<<" ";
    	}else{
    		cout<<temp->getData()<<" ";
    		while(temp->next()){
    			cout<<temp->next()->getData()<<" ";
    			temp = temp->next();
    		}
    	}
    	cout<<"]"<<endl;
    }
     
    template <typename Elemtype>
    bool LinkList<Elemtype>::Empty(){
    	return this->len == 0 ? 1 : 0; 
    }
     
    template <typename Elemtype>
    void LinkList<Elemtype>::DestroyList(){
    	this->~LinkList();
    }
    
    template <typename Elemtype>
    void LinkList<Elemtype>::MergeList(LinkList<Elemtype> lb){//合并两个表，有序 
    	if(this->flag&&lb.flag){//有序排列，按大小合并
    		
    		LinkList<Elemtype> *lc = new LinkList<Elemtype>();
    		LinkNode<Elemtype> *c  = new LinkNode<Elemtype>(0);
    		lc->setNext(c);
    		lc->len = 0;
    		while(lb.len!=0 && this->len!=0){
    			if(this->next->getData() < lb.next->getData()){
    				c->setNext(this->next);
    				this->next = this->next->next();
    				c = c->next();
    				this->len--;lc->len++;
    			}// 
    			else{//插入位置合适 
    				c->setNext(lb.GetNext());
    				lb.setNext(lb.GetNext()->next());
    				c = c->next();//lb删除首节点，后移一位 
    				lb.len--;lc->len++;
    			}	
    		}
    		while(lb.len){
    			c->setNext(lb.GetNext());
    			lb.setNext(lb.GetNext()->next());
    			c = c->next();
    			lb.len--;lc->len++;
    		}
    		while(this->len){
    			c->setNext(this->next);
    			this->next = this->next->next();
    			c = c->next();
    			this->len--;lc->len++;
    			//cout<<"判空：\t"<<this->next->next()<<endl;	
    		}
    		this->next = lc->next->next();
    		this->len  = lc->len;		
    	}else{//无序排列，直接合并 
    		LinkNode<Elemtype> *temp = new LinkNode<Elemtype>(0);
    		temp = this->next;
    		if(this->len==0)//当前链表为空 
    			this->next = lb.GetNext();
    		else{
    			while(temp->next())
    				temp = temp->next();
    			temp->setNext(lb.next);
    		}
    		this->len += lb.length();//修改长度
    	}
    }
    
    template <typename Elemtype>
    LinkList<Elemtype>::~LinkList(){//析构函数
    /*	LinkNode<Elemtype> *del = this->next;
    	while(del->next()!=NULL){//this->len > 1
    		cout<<this->next<<endl;
    		this->next = this->next->next(); 
    		free(del);
    		del = this->next;//获取下一个节点	
    		this->len--;
    	
    	}
    	free(this);
    */	this->next = NULL;
    	this->len  = 0;
    }
    
    
    int main(){
    	LinkList<int> *la = new LinkList<int>();
    	cout<<"新建la：\t";la->PrintList();
    	la->ListInsert(1,10);cout<<"第1位插入10：\t";la->PrintList();cout<<"现在长度为：\t"<<la->length()<<endl; 
    	la->ListInsert(1,6); cout<<"第1位插入6：\t";la->PrintList(); cout<<"现在长度为：\t"<<la->length()<<endl; 
    	la->ListInsert(2,8); cout<<"第2位插入8：\t";la->PrintList(); cout<<"现在长度为：\t"<<la->length()<<endl; 
    	la->ListInsert(4,7); cout<<"第4位插入7：\t";la->PrintList(); cout<<"现在长度为：\t"<<la->length()<<endl; 
    	la->ListDelete(8);   cout<<"删除元素8：\t";la->PrintList();    cout<<"现在长度为：\t"<<la->length()<<endl;
    	cout<<"第2个元素是：\t"<<la->GetElem(2)<<endl;
    	cout<<"元素6是：\t第"<<la->LocateElem(6)<<"位"<<endl;
    	
    	LinkList<int> *lb = new LinkList<int>();
    	lb->ListInsert(1,10);lb->ListInsert(1,9);
    	lb->ListInsert(1,8); lb->ListInsert(1,7);
    	lb->ListInsert(1,6); lb->ListInsert(1,4);
    	cout<<"新建lb：\t";  lb->PrintList();
    	
    	LinkList<int> *lc = new LinkList<int>();
    	lc->ListInsert(1,5);lc->ListInsert(1,3);
    	lc->ListInsert(1,2); lc->ListInsert(1,1);
    	lc->ListInsert(1,0); 
    	cout<<"新建lc：\t";  lc->PrintList();
    	
    	lb->MergeList(*lc);   cout<<"lb与lc有序合并：\t";lb->PrintList();
    	lb->MergeList(*la);   cout<<"lb与la无序合并：\t";lb->PrintList();
    	
    	la->DestroyList();
    	cout<<"la进行销毁：\t";la->PrintList();cout<<"现在长度为：\t"<<la->length()<<endl; 
    	
    	return 0;
    }

## 错误 ##

在代码实现的过程中，因为方法返回值是指针还是值得问题一直没搞明白，以及插入方法和合并方法中的点之间逻辑关系在循环处没做好其边界值的判断，导致bug频出。问题出现的原因应归结为：编码过程中格式以及变量设计不规范，对c++语言中的一些基本定义没搞明白，以及编程经验少。

## 总结 ##

对于单链表结点：元素elem+下一结点指针\*next，尾结点next指向NULL；

双链表结点：元素elem+下一结点指针\*next+上一结点指针\*pre，前后相指；

循环单链表：将最后一个结点的next指针指向首结点；

循环双链表：首结点的pre指向指向尾结点，尾结点的next指向首结点。

静态链表： 建立顺序表，元素elem + 下一结点下标next，看起来就像是一个二维数组。

## 参考文献 ##

严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.

**如有错误，还请朋友不吝指正。**

[Link 1]: https://blog.csdn.net/Kwzc4/article/details/96594791