Java教程

数据结构基本实现

本文主要是介绍数据结构基本实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1、顺序表

#define  MAX	20
#define OK		1
#define  ERRO	0
//typedef int linear_TYPE;

template <typename	linear_TYPE> //模板的定义
class linear	//类的创建
{
public:
	linear(); 	//构造函数(初始化)
	~linear();		//析构函数(释放内存变量)
	void append(linear_TYPE value);  	 //向列表末尾添加元素
	int insert(int key,linear_TYPE value);   	//向列表中插入元素
	void del();						//删除列表中的元素
	linear_TYPE judge_null();	//判断是否是空列表
private:
	linear_TYPE x_biao[MAX];
	int	x_length;

};

//构造函数
template <typename	linear_TYPE>
linear<linear_TYPE>::linear()
{
	x_length = 0;
	x_biao[MAX]=NULL;
}

//析构函数
template <typename	linear_TYPE>
linear<linear_TYPE>::~linear()
{
	printf("所有任务已执行完毕!");
	getchar();
}

//判断列表是否为空
template <typename	linear_TYPE>
linear_TYPE linear<linear_TYPE>::judge_null()
{
	if (this->x_length	==0)
		return OK;
	return	ERRO;
}

//插入
template <typename	linear_TYPE>
int	linear<linear_TYPE>::insert(int key,linear_TYPE value)
{
	for (int i=this->x_length;i>=key-1;i--)
	{
		this->x_biao[i] = this->x_biao[i-1];
	}
	this->x_biao[key-1] = value;
	this->x_length++;
	return ERRO;
}

//添加
template <typename	linear_TYPE>
void	linear<linear_TYPE>::append(linear_TYPE value)
{
	this->x_biao[this->x_length]= value;
	this->x_length++;
	//return	ERRO;
}

//删除
template <typename	Lstatic_TYPE>
void	linear<linear_TYPE>::del()
{
	if (judge_null())
	{
		printf("此表为空表!");
		//return ERRO;
	}
	this->x_biao[this->x_length-1]=NULL;
	this->x_length = this->x_length-1;
}

 

2、单列表

#include <iostream>

template <class TYPE>
class SList
{
public:
		SList();
		~SList();
		bool  IsEmpty(); //判断是否是空链表
		int GetElement(int dwIndex);	//根据索引获取元素
		int GetElementIndex(TYPE Element); //根据元素获取下标
		int Insert(TYPE Element);	//新增元素
		int Insert(int dwIndex,TYPE Element); //插入元素
		int Delete(int dwIndex);						//根据索引删除元素	
		int GetSize();						//获取链表中元素的数量
		int FindList(); 

private:
	typedef struct LNode{
		TYPE data;
		struct LNode  *next;
	};
	int ListLen;
	LNode *p_Head;
	LNode *P_next;

};

//构造函数
template <class TYPE> SList<TYPE>::SList():p_Head(NULL),ListLen(0)
{ 

}

//析构函数
template <class TYPE>
SList<TYPE>::~SList() 
{
	free(p_Head);
	free(P_next);
	printf("析构函数执行了!\n");
}



//判断列表是否为空
 template <class TYPE> bool SList<TYPE>::IsEmpty()
 {
	 if (p_Head==NULL && ListLen == 0)
	 {
		 return true;
	 }
	 return false;
 }

 //插入
 template <class TYPE>  int SList<TYPE>::Insert(TYPE Element)
 {
	  
	 if (IsEmpty())
	 {
		 p_Head = new LNode;
		 p_Head->data = Element;
		 ListLen++;
		 P_next=p_Head;
		  printf("插入成功!\n");
		// printf("%d\n",ListLen);
		 return 0;
		
	 }
     
	 P_next->next=new LNode;
	 P_next=P_next->next;
	 P_next->data=Element;
	 ListLen++;
	 //printf("%d\n",ListLen);
	 return 0;
 }

 //指定位置添加元素
 template <class TYPE>  int SList<TYPE>::Insert(int dwIndex,TYPE Element)
 {
	  LNode  *P_next=p_Head;
	 if (IsEmpty())
	 {
		 if (dwIndex > 1  || dwIndex <1)
		 {
			 printf("链表为空表,下标只能为1");
			 return 0;
		 }
	 }

	 for(int i=1;i<=ListLen+1;i++)
	 {
		
		if (i==(dwIndex-1))
		{
			LNode *xh;
			xh=P_next->next;
			P_next->next=new LNode;
			P_next=P_next->next;
			P_next->data=Element;
			P_next->next=xh;
			ListLen++;
            
			return 0;
		}
		P_next=P_next->next;
	 }

	 return 0;
 }

//遍历列表
 template <class TYPE>  int SList<TYPE>::FindList()
 {
	 printf("\n");
	  LNode  *P_next=p_Head;
	 int subscript=0;
	 while(subscript<ListLen)
	 {
		 
		 
		 printf("%d  ",P_next->data);
		 subscript++;
		 P_next=P_next->next;

	 }
	 return 0;
 }
 
//根据位置找元素
 template <class TYPE> int SList<TYPE>::GetElement(int dwIndex)
 {
	 LNode *P_next=p_Head;
	 int subscript=0;
	 while(subscript<=ListLen)
	 {

		 if (subscript == (dwIndex-1) )
		 {
			 printf("\n%d\n  ",P_next->data);
			 return 0;
		 }
		 
		 subscript++;
		 P_next=P_next->next;

	 }
	 return 0;
 }

//根据元素找位置
 template <class TYPE> int SList<TYPE>::GetElementIndex(TYPE Element)
 {
	 LNode *P_next=p_Head;
	 int subscript=0;
	 while(subscript<ListLen)
	 {

		 if (P_next->data == Element)
		 {
			 printf("\n%d\n  ",subscript+1);
			 return 0;
		 }

		 subscript++;
		 P_next=P_next->next;

	 }
	 return 0;
 }

//删除指定位置的元素
 template <class TYPE>  int SList<TYPE>::Delete(int dwIndex)
 {
	 LNode  *P_next=p_Head;
	 if (IsEmpty())
	 {
		printf("链表为空表,下标只能为1");
	 }

	 for(int i=1;i<=ListLen+1;i++)
	 {

		 if (i==(dwIndex-1))
		 {
			 LNode *xh;
			 xh=P_next->next;
			 xh=xh->next;
			free(P_next->next);
			 P_next->next=xh;
			 ListLen--;
             
			 return 0;
		 }
		 P_next=P_next->next;
	 }

	 return 0;
 }

//获取列表的长度
 template <class TYPE>  int SList<TYPE>::GetSize()
 {	
	 printf("\n链表长度:%d",ListLen);
	 return 0;
 }

2、双列表

#define  MAX	20
#define OK		1
#define  ERRO	0
using namespace std;

template <typename	linear_TYPE>  //定义模板
class Two_dxl  //创建类
{
public:
	Two_dxl();
	~Two_dxl();
	void append(linear_TYPE value);	//添加元素
	int  Blank_nodes();	//判断链表是否为空
	void del(linear_TYPE value);  //删除
private:
	typedef struct Lclass 	//创建结构体
	{
		Lclass   *lchild;
		Lclass	*rchild;
		linear_TYPE data;

	};
	Lclass *head;
	Lclass *next_add;

};

//构造函数
template<typename linear_TYPE>
Two_dxl<linear_TYPE>::Two_dxl()
{
	head = NULL;
	printf("构造函数执行了");

}

//析构函数
template<typename linear_TYPE>
Two_dxl<linear_TYPE>::~Two_dxl()
{
	printf("析构函数执行了");

}

//判断列表是否为空
template<typename linear_TYPE>
int Two_dxl<typename linear_TYPE>::Blank_nodes()
{
	if (this->head==NULL)
	{
		return ERRO;
	}
	return OK;
}

//I在列表末尾添加元素
template<typename  linear_TYPE>
void Two_dxl<linear_TYPE>::append(linear_TYPE value)
{
	if (Blank_nodes())
	{
		Lclass *p =NULL;
		p = next_add;
		next_add = new  Lclass;
		p->rchild =  next_add;
		next_add->lchild = p;
		next_add->data = value;
		next_add->rchild = NULL;
		return ;

	}
	this->head = new Lclass;
	head->data = value;
	head->lchild = NULL;
	next_add = head;
	return ;
}

//删除列表中的元素
template<typename linear_TYPE>
void Two_dxl<linear_TYPE>::del(linear_TYPE value)
{
	Lclass *p =NULL;
	Lclass *x=NULL;
	if (Blank_nodes()== ERRO)
	{
		printf("此链表为空!");
		return ;
	}
	if (head->data  == value)
	{
		p=head->rchild;
		free(head);
		head = p;
		return ;
	}
	else
		p=head->rchild;
	while(OK)
		{
		
			if (p->data==value)
			{
				x=p->lchild;
				p->data=0;
				x->rchild = p->rchild;
				free(p);
				return ;
			}
			p=head->rchild;

		}

}

3、循环列表

#define  MAX	20
#define OK		1
#define  ERRO	0
//using namespace std;


template <typename	linear_TYPE>	//定义模板
class Two_dxl    //创建类
{
public:
	Two_dxl();
	~Two_dxl();
	void append(linear_TYPE value);	//添加元素
	int  Blank_nodes();	//判断链表是否为空
	void del(linear_TYPE value);
private:
	typedef struct Lclass //创建结构体
	{
		Lclass   *lchild;
		Lclass	*rchild;
		linear_TYPE data;

	};
	Lclass *head;
	Lclass *next_add;

};

//构造函数
template<typename linear_TYPE>
Two_dxl<linear_TYPE>::Two_dxl()
{
	head = NULL;
	printf("构造函数执行了");

}

//析构函数
template<typename linear_TYPE>
Two_dxl<linear_TYPE>::~Two_dxl()
{
	printf("析构函数执行了");

}

//判断列表是否为空
template<typename linear_TYPE>
int Two_dxl<typename linear_TYPE>::Blank_nodes()
{
	if (this->head==NULL)
	{
		return ERRO;
	}
	return OK;
}

//添加元素
template<typename  linear_TYPE>
void Two_dxl<linear_TYPE>::append(linear_TYPE value)
{
	if (Blank_nodes())
	{
		Lclass *p =NULL;
		p = next_add;
		next_add = new  Lclass;
		p->rchild =  next_add;
		next_add->lchild = p;
		next_add->data = value;
		next_add->rchild = head;
		return ;

	}
	this->head = new Lclass;
	head->data = value;
	head->lchild = NULL;
	next_add = head;
	return ;
}

//删除元素
template<typename linear_TYPE>
void Two_dxl<linear_TYPE>::del(linear_TYPE value)
{
	Lclass *p =NULL;
	Lclass *x=NULL;
	if (Blank_nodes()== ERRO)
	{
		printf("此链表为空!");
		return ;
	}
	if (head->data  == value)
	{
		p=head->rchild;
		free(head);
		head = p;
		return ;
	}
	else
		p=head->rchild;
	while(OK)
	{

		if (p->data==value)
		{
			x=p->lchild;
			p->data=0;
			x->rchild = p->rchild;
			free(p);
			return ;
		}
		p=head->rchild;

	}

}

 

 

 

这篇关于数据结构基本实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!