一些常用的数据结构（二）：链表

继续。

二.链表

先考虑带头节点的单向链表。

两个类，节点类和链表类。如下：

class ChainNode
{
	friend Chain;
	private:
		int data;
		ChainNode* next;
}

 

class Chain
{
	public:
		Chain(){first=0;}
		~Chain();
		//其他一些，blablabla
	private:
		ChainNode* first;
}

 析构函数：

Chain::~Chain()
{
	while(first)
	{
		ChainNode* temp = first->next;
		delete first;
		first=temp;
	}
}

 查找指定元素：

int Chain:: Search(int x)
{
   ChainNode* temp = first;
   int i=1;
   while(temp)
   {
		if(temp->data==x)
			return i;
		i++;
		temp=temp->next;
   }
   return -1;
}

 删除指定元素：

bool Chain::Delete(int x)
{ 
       int index = Search(x);
	   if(index>0)
	   {
	     if(index==1)
		  first=first->next;
	     else
	     {
		  ChainNode* temp = first;
		  for(int i=1;i<index-1;i++)
		      temp=temp->next;
		  ChainNode* q = temp->next;
		  temp->next=q->next;
		  delete q;
	     }
		 return true;
	   }
	   else
		 return false;
}

 在指定位置后插入元素：

bool Chain::Insert(int index,ChainNode cn)
{
	//非法不判断啦，烦死啦,越界什么的
	temp=first;
	for(int i=1;i<index;i++)
		temp=temp->next;
	cn->next=temp->next;
	temp->next=cn;
	return true;
}

 在链表尾部插入节点：

//链表元素少于两个的情况不判断了。。
ChainNode* temp = first;
ChainNode* temp2 = first->next;
while(temp2)
{
	temp=temp->next;
	temp2=temp2->next;
}
temp->next=cn;

 就地逆置：

 http://lee3do.iteye.com/blog/777239

双向链表不写了，太繁琐了。