当前位置：首页 -> 基础 -> c++编程基础

用C++的类和结构体DIY静态链表及其接口函数(一)

2014-11-24 11:12:10 · 作者: · 浏览: 0
标签: 类和 结构 DIY 静态 及其 接口 函数

关于静态链表的C实现，网上已经烂大街了，这里就不在废话了。对于本文，纯粹是本 闲的蛋疼，如有异议，请轻喷。

对于每个节点，这里也不能免俗，使用结构体实现

struct staticlinklistnode
{
	int data;//数据
	int next;//下个数据的存储位置
	bool used;//是否放在链表中了
};
静态链表的类主要仿照STL中实现了一些接口函数 

class staticlinklist
{
private:
	static int length;//长度
	static int capacity;//容量
public:
	staticlinklistnode* ptrnode;//用来存放元素
	staticlinklistnode* root;//链表的头
	staticlinklist()
	{
		length = 0;
		capacity = 0;
		root->next = -1;
	//	ptrnode = NULL;
	}
	staticlinklist(int n)
	{
		length = 0;
		capacity = n;
		root = new staticlinklistnode;
	//	staticlinklistnode* node = new staticlinklistnode[n];
	//	ptrnode = node;
		ptrnode = new staticlinklistnode[n];
		root->next = -1;
		for(int i = 0; i < n; i++) 
		{
			ptrnode[i].next = -1;
			ptrnode[i].used = false;
		}
	//	ptrnode = node;
	}
	int insert(staticlinklist* ptr,int pos,int n);//插入
	void display(staticlinklist* ptr);//输出链表的数据
	int getlength(staticlinklist* ptr);//长度
	int getcapacity(staticlinklist* ptr);//返回容量
	void decreaselength(staticlinklist* ptr);//减小长度
	void increaselength(staticlinklist* ptr);//增加长度
	void setcapacity(staticlinklist* ptr,int capa);//设置容量
	int erase(staticlinklist* ptr, int pos);//删除
	int getmember(staticlinklist* ptr, int pos);//取得元素
	void pushback(staticlinklist* ptr,int n);//末尾插入
	void pushfront(staticlinklist* ptr, int n);//前端插入
	int popback(staticlinklist* ptr);//弹出最后一个元素
	int popfront(staticlinklist* ptr);//弹出第一个元素
	~staticlinklist()
	{
		
	}
};

其中display可以用getmember实现呢，封装一下就好，popback/popfront是erase函数的封装，pushfront/pushback是insert函数的封装，下面看每个函数的具体定义： 

int staticlinklist::popfront(staticlinklist* ptr)
{
		ptr->erase(ptr,0);
	//	ptr->length--;
		return 0;
}
int staticlinklist::popback(staticlinklist* ptr)
{
	ptr->erase(ptr,ptr->getlength(ptr) - 1);
//	ptr->length--;
	return 0;
}
void staticlinklist::pushfront(staticlinklist* ptr, int n)
{
	ptr->insert(ptr,0,n);
//	ptr->length++;
}
void staticlinklist::pushback(staticlinklist* ptr,int n)
{
	ptr->insert(ptr,ptr->getlength(ptr),n);
//	ptr->length++;
}
上面四个函数很简单吧，不多说了~

重点看下插入和删除函数

int staticlinklist::insert(staticlinklist* ptr,int pos,int n)
{
	if(pos > ptr->length)
	{
		cout<<不合法的位置<
  
   getlength(ptr);
		ptrnode[index].data = n;*/
		int i =0;
	//	while((ptrnode[i++].next == -1) && (ptrnode[i].used == true));
		while(ptrnode[i++].used == true);
		int index = i -1 ;
		ptrnode[index].data = n;
		int current = root->next ;
		int back;
		if(root->next == -1) //链表为空
		{
			if(pos == 0)
			{
				root->next = index;
				ptrnode[index].used = true;
				ptr->increaselength(ptr);
		        return 0;
			}
			else
			{
				cout<
   
    next; root->next = index; ptrnode[index].used = true; ptr->increaselength(ptr); return 0; } for(int i = 0; i < pos; i++)//链表不为空，插入位置亦不为0 { back = current; current = ptrnode[current].next; } ptrnode[back].next = index; ptrnode[index].used = true; ptrnode[index].next = current; ptr->increaselength(ptr); return 0; } }

插入函数花了好久，主要是对插入的元素判断是否插入判断出现问题，因为如果插入的链表的末尾的话，那么其next仍然没有指向一个节点，而没有放入静态链表的next也没有指向某个节点，这样在判断这个节点是否已经使用并放入了静态链表时会出现问题，因此，在节点结构体引入了use，如果已经使用，则为真，否则为假。

删除节点的源码

int staticlinklist::erase(staticlinklist* ptr,int pos)
{
	if(pos > ptr->getlength(ptr))
	{
		cout<<此位置不合法<
  
   next;
		int back ;
		if(pos == 0)
		{
			ptrnode[current].used = false;
			root->next = ptrnode[current].next;
			ptrnode[current].next = -1;
			ptr->length--;
			return 0;
		}
		else
		{
			for(int i = 0; i < pos; i++)
			{
				back = current;
				current = ptrnode[current].next;
			}
			ptrnode[back].next = ptrnode[current].next;
			ptrnode[current].next = -1;
			ptrnode[current].used = false;	
			ptr->length--;
			return 0;
		}
	}
}
很明显，删除比插入简单了一些，程序的整体代码是： 

#include 
  
   
using namespace std;
struct staticlinklistnode
{
	int data;//数据
	int next;//下个数据的存储位置
	bool used;//是否放在链表中了
};
class staticlinklist
{
private:
	static int length;//长度
	static int capacity;//容量
public:
	staticlinklistnode* ptrnode;//用来存放元素
	staticlinklistnode* root;//链表的头
	staticlinklist()
	{
		length = 0;
		capacity = 0;
		root->next = -1;
	//	ptrnode = NULL;
	}
	staticlinklist(int n)
	{
		length = 0;
		capacity = n;
		root = new staticlinklistnode;
	//	staticlinklistnode* node = new staticlinklistnode[n];
	//	ptrnode = node;
		ptrnode = new staticlinklistnode[n];
		root->next = -1;
		for(int i = 0; i < n; i++) 
		{
			ptrnode[i].next = -1;
			ptrnode[i].used = false;
		}
	//	ptrnode = node;
	}
	int insert(staticlinklist* ptr,int pos,int n);//插入
	void display(staticlinklist* ptr);//输出链表的数据
	int getlength(staticlinklist* ptr);//长度
	int getcapacity(staticlinklist* ptr);//返回容量
	void decreaselength(staticlinklist* ptr);//减小长度
	void increaselength(staticlinklist* ptr);//增加长度
	void setcapacity(staticlinklist* ptr,int capa);//设置容量
	int erase(staticlinklist* ptr, int pos);//删除
	int getmember(staticlinklist* ptr, int pos);//取得元素
	void pushback(staticlinklist* ptr,int n);//末尾插入
	void pushfront(staticlinklist* ptr, int n);//前端插入
	int popback(staticlinklist* ptr);//弹出最后一个元素
	int popfront(staticlinklist* ptr);//弹出第一个元素
	~staticlinklist()
	{
		
	}
};
int staticlinklist::capacity = 0;
int staticlinklist::length = 0;
int staticlinklist::popfront(staticlinklist* ptr)
{
		ptr->erase(ptr,0);
	//	ptr->length--;
		return 0;
}
int staticlinklist: