shunxu.cpp

包括顺序链表的查找

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include "shunxu.h"
typedef int ElementType;

void InitList(lNode *head)//创建一个空链表
{
	head=new lNode;
	head->next=NULL;
}

void DestroyList(lNode *head)
{
	lNode *temp;
	temp = new lNode;
	while (head!=NULL)
	{
		temp=head;
		head=head->next;
		delete temp;
	}
}

bool GetElem(lNode *head,int pos,ElementType &e)
{
	lNode *p;
	p=new lNode;
	p=head->next;
	int i=1;
	if (pos>ListLenghth(head))
		return false;
	else
	{
		while (i<pos)
		{
			p=p->next;
			i++;
		}
		e=p->data;
		return true;
	}
}

bool ListInsert(lNode *head,int pos,ElementType e)//pos为插入后元素所处的位置
{
	if (pos>ListLenghth(head)+1||pos<1)
		return false;
	else 
	{
		lNode *temp;
		temp = new lNode;
		temp = head;
		int i=0;
		while (i<pos-1)
		{
			temp=temp->next;
			i++;
		}
		lNode *InsertEle;
		InsertEle = new lNode;
		InsertEle->data = e;
		InsertEle->next = temp->next;
		temp->next = InsertEle;
		return true;
	}
}
bool ListDelete(lNode *head,int pos,ElementType &e)
{
	if (pos>ListLenghth(head)+1||pos<1)
		return false;
	else 
	{
		int i = 1;
		lNode *temp,*temp1;
		temp = temp1 = new lNode;
		temp = head->next;
		while (i<pos)
		{
			temp1 = temp;
			temp = temp->next;
			i++;
		}
		e = temp->data;
		temp1->next = temp->next;
		delete temp;
		return true;
	}
}
bool ListEmpty(lNode *head)
{
	if (head == NULL)
		return true;
	else 
		return false;
}
int ListLenghth(lNode *head)//包括头结点
{
	lNode *temp;
	temp = new lNode;
	temp = head;
	int lenghth=0;
	while (temp!=NULL)
	{
		temp=temp->next;
		lenghth++;
	}
	return lenghth;
}
void print(lNode *head)
{
	if(ListEmpty(head))
	{
		cout<<"The list is empty"<<endl;
	}
	else
	{
		lNode *temp;
		temp = new lNode;
		temp = head->next;
		while (temp!=NULL)
		{
			cout<<temp->data<<"\t"<<temp<<endl;
			temp=temp->next;
		}
	}
}
void addEnd(lNode *head,ElementType e)
{
	lNode *temp;
	temp=new lNode;
	temp->data = e;	
	lNode *p;
	p=new lNode;
	p=head->next;
	while (p->next!=NULL)
	{
		p=p->next;
	}
	p->next = temp;
	temp->next=NULL;
}
void CreFro(lNode *head,int n,ElementType a[])
{
	for (int i=0;i<n;i++)
	{	
		addEnd(head,a[i]);
	}
}
void purge(lNode *head)
{
	lNode *p;
	p=new lNode;
	p = head->next;//原来的链表
	head->next=NULL;//设新链表为空链表
	lNode *succ;
	succ=new lNode;
	lNode *newl;
	newl=new lNode;
//	newl = head->next;//新的链表的头结点
	while (p)
	{
		succ = p->next;
		newl = head->next;
		while (newl&&p->data!=newl->data)
			newl = newl->next;
		if (newl == NULL)
		{
			p->next=head->next;
			head->next=p;
		}
		else
			delete p;
		p=succ;
	}
}
void invert(lNode *head)
{
	lNode *temp1;
	temp1 =new lNode;
	temp1 = head;

	lNode *Start;
	Start=new lNode;
	Start = temp1->next;
	
	head->next = NULL;
	while (Start!=NULL)
	{
		ListInsert(head,1,Start->data);
		Start=Start->next;
	}
}

void del_between_min_max(lNode *head,ElementType min,ElementType max)
{
	if (min>max)
		cout<<"min should be smaller"<<endl;
	else
	{
	lNode *Start,*StartPre;
	Start=StartPre=new lNode;
	Start = head->next;
	StartPre = head;
	while (Start!=NULL)
	{
		if (Start->data<max&&Start->data>min)
		{
			lNode *temp;
			temp = new lNode;
			temp = Start;
			StartPre->next = Start->next;
			Start = Start->next;
			delete temp;
		}
		else
		{
			StartPre = StartPre->next;
			Start = Start->next;
		}
	}
	}
}