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

2021-09-18 05:08:49

转载请注明出处：http://blog.csdn.net/hongkangwl/article/details/21882459

关于静态链表的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<<"不合法的位置"<<endl;
		return -1;
	}
	else
	{
		/*int index = ptr->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<<"oops！！存放位置不合法"<<endl;
				return -1;
			}
		}
		if(pos == 0)//链表不为空，插入第0位置
		{
			ptrnode[index].next = root->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<<"此位置不合法"<<endl;
		return -1;
	}
	else
	{
		int current= root->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 <iostream>
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::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::getmember(staticlinklist* ptr, int pos)
{
	if(pos > ptr->getlength(ptr))
	{
		cout<<"位置非法"<<endl;
		return -1;
	}
	int current = root->next;
	for(int i = 0; i < pos; i++)
	{
		current = ptrnode[current].next;
	}
	return ptrnode[current].data;
}
int staticlinklist::erase(staticlinklist* ptr,int pos)
{
	if(pos > ptr->getlength(ptr))
	{
		cout<<"此位置不合法"<<endl;
		return -1;
	}
	else
	{
		int current= root->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;
		}
	}
}
void staticlinklist::setcapacity(staticlinklist* ptr,int capa)
{
	ptr->capacity = capa;
}
void staticlinklist::display(staticlinklist* ptr)
{	
	int index = root->next;
	for(int i = 0; i < ptr->getlength(ptr); i++)
	{
		cout<<ptrnode[index].data<<" ";
		index = ptrnode[index].next;
	}
	cout<<endl;
}
void staticlinklist::decreaselength(staticlinklist* ptr)
{
	ptr->length--;
}
void staticlinklist::increaselength(staticlinklist* ptr)
{
	ptr->length++;
}
int staticlinklist::getlength(staticlinklist* ptr)
{
	return ptr->length;
}
int staticlinklist::getcapacity(staticlinklist* ptr)
{
	return ptr->capacity;
}
int staticlinklist::insert(staticlinklist* ptr,int pos,int n)
{
	if(pos > ptr->length)
	{
		cout<<"不合法的位置"<<endl;
		return -1;
	}
	else
	{
		/*int index = ptr->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<<"oops！！存放位置不合法"<<endl;
				return -1;
			}
		}
		if(pos == 0)//链表不为空，插入第0位置
		{
			ptrnode[index].next = root->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;
	}
}

int main()
{
	
	int n;
	cout<<"静态链表的容量是多大？请输入："<<endl;
	cin>>n;
//	slinklist->setcapacity(slinklist,n);
	staticlinklist* slinklist = new staticlinklist(n);
	int m;
	cout<<"你要存储多少个元素？请输入："<<endl;
	cin>>m;
	for(int i = 0; i < m; i++)
	{
		slinklist->insert(slinklist,i,i);
	}
	slinklist->display(slinklist);
	slinklist->insert(slinklist,2,100);
	cout<<"在位置2上插入100后静态链表为："<<endl;
	slinklist->display(slinklist);
	slinklist->erase(slinklist,3);
	cout<<"把位置3上面的元素删除后静态链表为："<<endl;
    slinklist->display(slinklist);
	slinklist->erase(slinklist,3);
	cout<<"把位置3上面的元素删除后静态链表为："<<endl;
    slinklist->display(slinklist);
	cout<<"使用成员函数输出链表数据"<<endl;
	for(int i  = 0; i < slinklist->getlength(slinklist); i++)
	{
		cout<<slinklist->getmember(slinklist,i)<<" ";
	}
	cout<<endl;
	slinklist->popback(slinklist);
	cout<<"使用popback后静态链表为"<<endl;
	slinklist->display(slinklist);
	slinklist->popfront(slinklist);
	cout<<"使用popfront后静态链表为"<<endl;
	slinklist->display(slinklist);
	slinklist->pushfront(slinklist,88);
	cout<<"使用pushfront 88 后静态链表为"<<endl;
	slinklist->display(slinklist);
	slinklist->pushback(slinklist,99);
	cout<<"使用pushback 99 后静态链表为"<<endl;
	slinklist->display(slinklist);
	return 0;
}

测试结果为：

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

经测试初步实现功能，嘎嘎~

用C++的类和结构体DIY静态链表及其接口函数,布布扣,bubuko.com

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

码农公寓

相关文章