线性结构总结(1)-基于链表的实现

1.开篇之言本人非计算机专业，自学数据结构和算法为图像处理和模式识别打基础，如有错误，感谢指正。数据结构是人们为了方便计算机处理数据而将数据进行合理组织的一门学问。数据结构也反映了人们对事物间关系的认知，由于计算机内存只有一种结构即线性结构，所以人们想要使用计算机来表示世界中一些非线性结构，如树、图等，就必须对它们进行转换为线性结构，从而使得计算机可以表示和处理。数据结构中的线性结构主

yaodix

589人浏览 · 2016-05-14 14:52:58

yaodix · 2016-05-14 14:52:58 发布

1.开篇之言

本人非计算机专业，自学数据结构和算法为图像处理和模式识别打基础，如有错误，感谢指正。

数据结构是人们为了方便计算机处理数据而将数据进行合理组织的一门学问。数据结构也反映了人们对事物间关系的认知，由于计算机内存只有一种结构即线性结构，所以人们想要使用计算机来表示世界中一些非线性结构，如树、图等，就必须对它们进行转换为线性结构，从而使得计算机可以表示和处理。

数据结构中的线性结构主要包括线性表、栈和队列等，这些线性结构在语言层面的实现基础是数组或链表，本文代码实现语言为C++。

2.链表实现线性表

数组大概是程序语言学习过程中最先接触到的一种数据结构，它的定义很简单，但是功能非常强大，再配合以指针足以成为解决问题的利器。数组可以用来实现线性表，这种实现有它的优点也有缺点。本文主要使用链表来实现线性表。

链表是由一个个节点依次链接而成（图就不上了，有基础的人都应该能够脑补一下^_^）。实现链表首先需要表示出链表节点类。链表节点需要说明的是，

首节点：存放第一个有效数据的节点

尾节点：存放最后一个有效数据的节点

头节点：头节点首节点前面的那个节点；它的数据类型和首节点数据类型一致；头结点不存放有效数据；设置头结点的目的是目的是为了方便对链表的操作。

以下为链表节点类：

template
  
  
   
   
class ListNode
{
public:
ListNode(){next = NULL;	}
ListNode(T _element,ListNode
   
   
    
    * _next= NULL)
{
	element = _element;
	next = _next;
}
~ListNode(){next =NULL;}
T getDate(){return date;}

private:
    //声明为链表的友元类，这样链表类中成员函数可以访问链表节点的成员
	template 
    
    
     
      friend class LinkList;
	T element;
	ListNode
     
     
      
      * next;
};

以下为链表类：

template<typename T>
class LinkList
{
public:
	LinkList(){head = NULL;listSize=0;}
~LinkList();
//ADT
void insert(int theIndex,T theElement);
void push_back(T theElement);
void erase( T theElement);
void find(T theElement);
void pop_head();
void push_head(T theElement);
void show();
private:
	ListNode<T>* head;
	int listSize;
};

方法实现

template<typename T>
class LinkList
{
public:
	LinkList(){head = NULL;listSize=0;}
~LinkList();

void insert(int theIndex,T theElement);
void push_back(T theElement);
void erase( T theElement);
void find(T theElement);
void pop_head();
void push_head(T theElement);
void show();
private:
	ListNode<T>* head;
	int listSize;
};

template<typename T>
LinkList<T>::~LinkList()
{
	ListNode<T> *p = head;
	ListNode<T> *temp = NULL;
	for (;p!=NULL;p = temp)
	{
		temp = p->next;
		delete p;
	}
	head = NULL;
}

template<typename T>
void LinkList<T>::insert(int theIndex,T theElement)
{
	
	if (theIndex<0 || theIndex>listSize )
	{
		cout<<"插入数据错误"<<endl;
		return;
	}
	else
	{
		ListNode<T> *p = head;
		ListNode<T> *p1 = new ListNode<T>(theElement);
		if (theIndex ==0)
		{
			p1->next = p;
			head =p1;
			listSize++;
		}
		else
		{
			for (int i=0;i<theIndex-1;i++)
			{
				p = p->next;
			}
			p1->next = p->next;
			p->next = p1;
			listSize++;
		}
	}
}
template<typename T>
void LinkList<T>::push_back(T theElement)
{
	if (head == NULL)
	{
		head = new ListNode<T>(theElement);
		listSize++;
	}
	else
	{
		ListNode<T> *p = head;
		while(p->next !=NULL)
		{
			p = p->next;
		}
		p->next = new ListNode<T>(theElement);
		listSize++;
	}
}
template<typename T>
void LinkList<T>::erase(T theElement)
{
	if(head ==NULL)
	{
		cout<<"linklist is empty!"<<endl;
		return;
	}
	ListNode<T> *cur =head;
	ListNode<T> *pre =head;
	ListNode<T>*del =NULL;
	while (cur->element != theElement && cur->next !=NULL)
	{
		pre =cur;
		cur = cur->next;
	} 
	if (cur == head)
	{
		del=head;
		head = head->next;
		delete del;
		listSize--;
	} 
	else if(cur->element !=theElement )
	{
		cout<<"no find "<<theElement<<endl;
	}
	else
	{
		del =cur;
		pre->next = cur->next;
		listSize--;
		if(del !=NULL)
			delete del;
	}
}
template<typename T>
void LinkList<T>::find(T theElement)
{

}
template<typename T>
void LinkList<T>::push_head(T theElement)
{
	insert(0,theElement);
}
template<typename T>
void LinkList<T>::pop_head()
{
	ListNode<T> *del = NULL;

	del =head;
	head =head->next;
	delete del;
	listSize--;
}
template<typename T>
void LinkList<T>::show()
{
	ListNode<T>*p =head;
	while(p !=NULL)
	{
		cout<<p->element<<" ";
		p=p->next;
	}
	cout<<"长度为:"<<listSize;
	cout<<endl;
}

节点操作过程中的两点总结：

1.在节点插入操作中，节点p用p = ××->next操作取出后，可以进行元素element、next读取，但不能对其直接赋插入节点的指针p1，因为此时的p只是一个临时变量对其赋值操作无法改变链表(类似传值交换两个变量时无法完成交换操作)。

2.在节点删除操作中，可能会出现多个指针同时指向同一个动态分配的内存，此时释放这块内存只需要delete其中一个指针即可，然后对所有指向这块内存的指针赋NULL。

如果链表只使用push_head()和pop_head()方法在链表一端(头部)进行删除和插入操作即为栈。只使用pop_head()和push_back()方法在链表尾部插入，头部删除即为队列。