list.cpp

链表的各项删除

#include"List.h"
#include<iostream.h>
#include<process.h>

List Create (int m)
{
	if(m == 0)
	{
		cout<< "空指针，不用输入:"
			<<endl;
		return NULL;
	}

	// 定义变量
	List pHead = NULL; //用于保存链表头指针
	List pCur = NULL;  //用于保存当前指针
	List pTemp = NULL;	//临时指针，用于保存中间量

	for( int counter = 0; counter < m; counter++)
	{
		if(!counter)//创建的是第一个结点
		{
			pHead = new Node;
			cout<< "请输入第"<< (counter + 1) << " 个结点的数据（一个整数）：";
			cin>>pHead->data;
			pHead->pNext =pHead->pFormer=NULL;
			pTemp=pCur =pHead;
			continue;
		}

		pTemp = new Node;
		pCur->pNext = pTemp;
		pTemp->pNext = NULL;
		pTemp->pFormer = pCur;
		pCur = pTemp;
		cout<< "请输入第"<< (counter + 1) << " 个结点的数据（一个整数）：";
		cin>>pTemp->data;
	}
	return pHead;
}//完成创建链表


List Sort (List head)//对头结点指针为head 链表进行排序，返回排序后的头指针，原链表被破坏
{
	List pHead = head;
	
	if(pHead == NULL)
		return NULL;
	if(pHead->pNext == NULL)  //只有一个头指针，不用排序 故直接返回头指针
		return pHead;

	//创建变量
	//       List pHead = head;//头结点，用于返回


	List pCur = pHead;//用于保存指针当前值
	List pTemp = pHead->pNext;//临时指针，用于保存中间量

	pHead->pFormer = pHead->pNext = NULL;

	//List pTemp2 = pHead;//临时指针，用于保存中间量
	List pTempHead = pTemp;
	
	
	
	//===========================================================================================
	for( pTempHead = pTemp; pTempHead != NULL;  )
	{
		pTemp = pTempHead; //把胜下头结点取下，做为待插入点
		pTempHead = pTempHead->pNext;//把下一个结点为头结点
		if(pTempHead != NULL)
			pTempHead->pFormer = NULL;//剩下的头指针结点头指针为空
		pTemp->pNext = NULL;//取下的结点作为单结点，故后继为空
		pTemp->pFormer = NULL;//取下的结点作为单结点，故前驱为空
		
		for(pCur = pHead; pCur != NULL; pCur = pCur->pNext )
		{
			if(pCur->data > pTemp->data)
			{
				if(pCur->pFormer == NULL)
				{
					pCur->pFormer = pTemp;
					pTemp->pNext = pCur;
					pHead = pTemp;
					break;
				}
				
				else
				{
					pTemp->pNext = pCur;
					pTemp->pFormer = pCur->pFormer;
					pCur->pFormer->pNext = pTemp;
					pCur->pFormer = pTemp;
					break;					
				}
			}
			if(pCur->pNext == NULL)
			{
				pCur->pNext = pTemp;
				pTemp->pFormer = pCur;
				break;
			}
		}
		
	}

	//===========================================================================================
	return pHead;
}



List Merge(List la,List lb)  //把头指针为la,lb 的链表合并为一个链表
{
	//定义变量
	List lc = NULL;		//合并后的头指针
	List pCur = NULL;    //用来保存合并后的最后一个结点
	List pTempA = NULL;  //用来保存la的有关信息
	List pTempB = NULL; // 用来保存lb 的有关信息
	List pTemp = NULL;//用来保存合并时有一个接点为空时的指针

	//开始合并
	for(pTempA = la, pTempB = lb; (pTempA != NULL)&&(pTempB != NULL); )
	{
			if(!lc)
			{
				if(pTempA->data < pTempB->data)
				{
					lc = new Node;
					lc->data = pTempA->data;
					lc->pNext = NULL;
					lc->pFormer = NULL;
					pTempA = pTempA->pNext;
				}
				else
				{
					lc = new Node;
					lc->data = pTempB->data;
					lc->pNext = NULL;
					lc->pFormer = NULL;
					pTempB = pTempB->pNext;
				}
				pCur = lc;
			}
			else
			{
				if(pTempA->data < pTempB->data)
				{
					pCur->pNext = new Node;
					pCur->pNext->data = pTempA->data;
					pCur->pNext->pNext = NULL;
					pCur->pNext->pFormer = pCur;
					pTempA = pTempA->pNext;
				}
				else
				{
					pCur->pNext = new Node;
					pCur->pNext->data = pTempB->data;
					pCur->pNext->pNext = NULL;
					pCur->pNext->pFormer = pCur;
					pTempB = pTempB->pNext;
				}
				pCur = pCur->pNext;
			}
			
	}
	if(pTempB == NULL)
	{
		for( pTemp = pTempA; pTemp != NULL; pTemp = pTemp->pNext)
		{
			if(pCur == NULL)
			{
				pCur = new Node;
				pCur->pFormer = NULL;
				pCur->pNext = NULL;
				pCur->data = pTemp->data;
				lc = pCur;
				continue;
			}
			pCur->pNext = new Node;
			pCur->pNext->pFormer = pCur;
			pCur->pNext->data = pTemp->data;
			pCur->pNext->pNext = NULL;
			pCur = pCur->pNext;
		}
	}
	if(pTempB != NULL)
	{
		for( pTemp = pTempB; pTemp != NULL; pTemp = pTemp->pNext)
		{
			if(pCur == NULL)
			{
				pCur = new Node;
				pCur->pFormer = NULL;
				pCur->pNext = NULL;
				pCur->data = pTemp->data;
				lc = pCur;
				continue;
			}
			pCur->pNext = new Node;
			pCur->pNext->pFormer = pCur;
			pCur->pNext->data = pTemp->data;
			pCur->pNext->pNext = NULL;
			pCur = pCur->pNext;
		}
	}			
	return lc;
}


void Print(List head)//打印
{
	//定义变量
	List pCur;
	List pHead = head;
	for(pCur = pHead; pCur != NULL; pCur = pCur->pNext)
	{
		cout << pCur->data <<"\t";
	}
	cout<<endl;
}