doublelist.cpp

用VC2005实现的双向链表里面包括添加元素删除元素查询等基本功能

#include <iostream>
#include "doubleList.h"

using std::cout;
using std::cin;
using std::endl;

void Add(NODE *&pHead, NODE *&pTail)
{

    NODE *newNODE = new NODE;
	cout << "insert the data of this newNODE:\n";
	cin >> newNODE->data;
	newNODE ->nextNODE = NULL;
	newNODE ->preNODE = NULL;
    
	if(pHead == 0)
	{
		cout << "因为链表为空，所以创建头节点\n";
	    pHead = pTail = newNODE;
		return;
	}
    
	int is = 2; 
    cout << "你想从前添加还是从后添加元素（前0后1）？\n";
    cin >> is;
	if(is == 1)
	{
	NODE *last2 = pTail;//假设添加完毕后从后往头数第二个
	pTail = newNODE;
	last2 ->nextNODE =pTail;
	pTail ->preNODE = last2;
	return;
	}
    if(is == 0)
	{
	NODE *front2 = pHead; //假设添加完毕后从头往后数第二个
	pHead = newNODE;
	pHead->nextNODE = front2;
	front2->preNODE = pHead;
	return;
	}

	cout<< "输入错误，返回\n";
	delete newNODE;
	return;
	

}


void deleteX(NODE *&pHead, NODE *&pTail)
{

    int index;
	cout << "你要删除第几个元素？\n";
	cin >> index;
	if(pHead == 0)
	{
		cout<< "the link was empty!\n";
		return;
	}

    if(index == 1)
	{
		NODE *first = pHead;
		pHead = pHead->nextNODE;
		delete first;
	    return;
	}

	int i=2;
	NODE *current = pHead;
	while((current ->nextNODE != NULL) && (i != index))
	{
		current = current ->nextNODE;
		i++;
	}
	if(current ->nextNODE == NULL)
	{
	   cout<< "要删除的目标不存在。\n";
	   return;
	}
	if(current ->nextNODE == pTail)
	{
		NODE* last =pTail;
		pTail=pTail->preNODE;
		delete last;
		return;

	}
	NODE *deleteNODE = current ->nextNODE;
	deleteNODE->nextNODE->preNODE = current;
	current ->nextNODE = deleteNODE ->nextNODE;
	delete deleteNODE;
	return;
	
		
}



void insertX(NODE *&pHead, NODE *&pTail)
{
	 int index;
	cout << "你要插入的第几个元素？\n";
	cin >> index;
	
	NODE * newNODE = new NODE;
	cout << "请输入插入的元素的数据:\n";
	cin >> newNODE ->data;
	newNODE -> nextNODE = NULL;
	newNODE -> preNODE = NULL;

	if(pHead == 0)
	{
		if(index==1){
		pHead = pTail =newNODE;
		return;
		}else{
		cout << "此链表为空!\n";
		return;
		}
	}
	if(index == 1)
	{
		pHead->preNODE = newNODE;
		newNODE->nextNODE = pHead;
		pHead = newNODE;
		return;
	}

	int i=2;
	NODE* current=pHead;
	while((current != 0) && (i != index))
	{
		current = current->nextNODE;
		i++;
	
	}
	if(current == 0)
	{
	    cout << "目标插入的位置不正确!\n";
		return;
	}

	if(current == pTail)
	{

		pTail->nextNODE = newNODE;
		newNODE->preNODE = pTail;
		pTail=newNODE;
		return;
	}

	NODE * next= current->nextNODE;
	newNODE->preNODE = current;
	newNODE->nextNODE = next;
	current->nextNODE=newNODE;
	next->preNODE=newNODE;
    return;


}

void find(NODE *&pHead, NODE *&pTail)
{
	int is=3;
	cout << "从前找还是从后找？(前0后1)\n";
    cin >> is;
	int index = 0;
	if(is == 0)
	{
		cout << "从前往后查询第几个元素的数据？\n";
		cin >> index;

		int i=1;
		NODE* current=pHead;
		while((current != 0) && (i != index))
		{
			current = current->nextNODE;
			i++;
	
		}
	
		if(current == 0)
		{
		    cout << "找不到该目标元素!\n";
			return;
		}
		cout << "该元素数据为："
			 << current->data 
			 << endl;
		return;
	}
	if(is == 1)
	{
		cout << "从后往前查询第几个元素的数据？\n";
		cin >> index;

		int i=1;
		NODE* current=pTail;
		while((current != 0) && (i != index))
		{
			current = current->preNODE;
			i++;
	
		}
	
		if(current == 0)
		{
		    cout << "找不到该目标元素!\n";
			return;
		}
		cout << "该元素数据为："
			 << current->data 
			 << endl;
		return;
	}
	cout << "你输入有误!\n";
	return;

	


}