001.cpp

数据结构之：链表的添加和删除

#include<iostream>
using namespace std ;
struct List
{
	int money ;//链表中存放的数据
	List *pNext ;//指向下一节点的指针
	List()//构造函数
	{
		//初始化指针
		pNext = NULL ;
	}
};
//链表的头(全局)
List *ListHead = NULL ;
//添加函数
void AddList( int a )
{
	//新的节点,分配空间
    List * pNew = new List();
	//赋值
	pNew->money = a;
	//如果头为空,新节点赋给头
	if( ListHead == NULL )
	{
		ListHead = pNew;
	}
	else//否则
	{
		//循环往下找,找到空的位置
		for( List *pTemp = ListHead; pTemp->pNext != NULL; pTemp = pTemp->pNext );
		//将新的节点赋给空的位置
		pTemp->pNext = pNew;
	}
}
//打印函数
void Print()
{
	//头为空
	if(ListHead == NULL)
	{
		cout<<"链表为空"<<endl;
	}
	else//否则
	{
		//一个(代替头的)临时的节点循环的遍历整个链表,直到为空
		for(List * pTemp = ListHead; pTemp != NULL; pTemp = pTemp ->pNext)
		{
			//每次遍历打印一个节点的值
			cout << pTemp->money << endl ;
		}
	}
}
//删除表（节点的值）
bool deleteList ( const int &x )
{
	//如果头为空
	if( ListHead == NULL )
	{
		cout << "链表为空，无法删除!" << endl ;
		return false;
	}
	else//头不为空
	{
		//如果删除的是头
		if( ListHead->money == x )
		{
			//临时节点代替头
			List *pTemp = ListHead ;
			//头的下一个作为头
			ListHead = ListHead->pNext ;
			//删除掉原来代替头的指针
			delete(pTemp);
			//指针赋空
			pTemp = NULL ;
			cout<< "删除的是第一个元素!" << endl ;
			return true;
		}
		else//删除的不是头
		{
			//临时节点代替头
			List *pTemp = ListHead ;
			//循环遍历链表
			while( pTemp->pNext != NULL )
		    {
				//如果找到要删除的节点,跳出循环
				if( pTemp->pNext->money == x )
				     break ;
				pTemp = pTemp->pNext ;
		     }
			//如果删除的节点不是空的
			if(pTemp->pNext != NULL)
			{
				//临时节点代替要删除的节点
				List *pTemp2 = pTemp->pNext ;
				//将要删除的节点的下一个节点赋给原来的节点
				//要删除的节点的下一个代替原来的位置
				pTemp->pNext = pTemp2->pNext ;
				//删除掉临时节点
				delete(pTemp2);
				pTemp2 = NULL ;
				cout<< "删除的是链表中除第一位的某个元素!" << endl ;
				return true;
			}
			else
			{
				cout<< "链表中没有这样的元素！" << endl ;
		        return false;
			}
		    
		}
	}
    return false;
}
//删除表
void DeleteList( const int &a )
{
	if ( !ListHead )
	{
		cout << "空表" << endl ;
		return ;
	}
	else
	{
		//如果删的是头
		if ( ListHead->money == a )
		{
			//
			List *pTemp = ListHead ;
			ListHead = ListHead->pNext ;
			delete pTemp ;
			pTemp = NULL ;
		}
		else
		{
			List *pTemp = ListHead ;
			while ( pTemp->pNext->money != a )
			{
				pTemp = pTemp->pNext ;
				if ( !pTemp->pNext )
				{
					cout << "表里没这个东西！" << endl ;
					return ;
				}
			}
			List *pTemp1 = pTemp->pNext ;
			pTemp->pNext = pTemp->pNext->pNext ;
			delete pTemp1 ;
			pTemp1 = NULL ;
		}
	}
}
//插入表         值				位置
void InsertList( const int &a, const int n )
{
	//新节点
	List *pNew = new List() ;
	pNew->money = a ;
	//头为空,就给头
	if ( !ListHead )
	{
		ListHead = pNew ;
	}
	else//否则
	{
		//如果位置编号小于1
		if ( n < 1 )
		{
			//将新节点给头
			//现有的头作为新节点的下一个
			pNew->pNext = ListHead ;
			//新节点作为头
			ListHead = pNew ;
		}
		else//如果n不小于1
		{
			//临时节点代替头
			List *pTemp = ListHead ;
			//循环遍历链表,找到n的位置
			for ( int i = 1; i < n; i++ )
			{
				pTemp = pTemp->pNext ;
				//如果链表中节点的数量每有n那么多
				if ( !pTemp->pNext )
				{
					//新节点给表的尾
					pTemp->pNext = pNew ;
					return ;
				}
			}
			//要插入位置的节点先赋给新节点的下一个节点
			pNew->pNext = pTemp->pNext ;
			//让新节点代替原来的位置
			pTemp->pNext = pNew ;
		}
	}
}
void main ()
{
	AddList( 9 );
	AddList( 10 );
	AddList( 5000 );
	AddList( 1000000 );
	AddList( 1500 );
	AddList( 100 );
    //Print();
   // deleteList(100);
	DeleteList( 9 ) ;
	DeleteList( 10 ) ;
	DeleteList( 1500 ) ;
	InsertList( 10050, 10 ) ;
	Print();
}