线性表的链式存储及其接口函数C++类实现

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

首先通过结构体建立每个节点< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;"> struct node //链表节点 { node* ptrnext; int data; };在线性表的类中，定义了一些对线性表的常用操作

class linklist //链表类
{
private:
	static int length; //链表长度
	static int capacity;//链表容量

public:
	node* ptr_node;//节点指针
	node* rootnode;//链表根节点，没有元素，指向position为0的节点
	linklist()//构造函数
	{
		length = 0;
		capacity = 0;
		ptr_node = NULL;
		rootnode->ptrnext = NULL;
	}
	linklist(int capacity_num)//带参数的构造函数
	{
		capacity = capacity_num;
		length = 0;
		ptr_node = NULL;
		rootnode = new node;
		rootnode->ptrnext = NULL;
	}
	
	int linklist_insert(linklist* ptr,int pos,int member);//插入元素
	int linklist_erase(linklist* ptr,int  pos);//删除元素
	int linklist_getlength(linklist* ptr);//获取链表长度
	int linklist_getcapacity(linklist* ptr);//获取链表容量
	void linklist_display(linklist* ptr);//顺序输出链表中的每个元素
	void linklist_increaselength(linklist* ptr);//增加元素的个数
	void linklist_decreaselength(linklist* ptr);//减少元素的个数
	int linklist_getmember(linklist* ptr,int pos);//获取某位置上的元素

	~linklist()//析构函数
	{
	
	}	
};

int linklist::linklist_insert(linklist* ptr,int pos,int member)
{	
	if(ptr->linklist_getlength(ptr) == ptr->linklist_getcapacity(ptr))//链表已满
	{
		cout<<"超出链表的容量"<
  
    linklist::linklist_getcapacity(ptr) - 1)//位置在链表之外
	{
		cout<<"位置超出链表的尾巴"<
   
    ptrnext == NULL) //空链表的 { ptr_node = new node; ptr_node->data = member; ptr_node->ptrnext = NULL; rootnode->ptrnext = ptr_node; ptr->linklist_increaselength(ptr); } else //在中间插入 if(ptr->linklist_getlength(ptr) - 1 < pos) { node* current; node* next; current = rootnode; next = current->ptrnext; ptr_node = new node; ptr_node->data = member; ptr_node->ptrnext = NULL; for(int i = 0; i < ptr->linklist_getlength(ptr) ; i++) { current = next; next = current->ptrnext; } current->ptrnext = ptr_node; ptr->linklist_increaselength(ptr); return 0; } else if(pos == 0) //空链表，貌似跟上面的重复了，额，不影响运行 { ptr_node = new node; ptr_node->data = member; ptr_node->ptrnext = rootnode->ptrnext; rootnode->ptrnext = ptr_node; ptr->linklist_increaselength(ptr); return 0; } else { node* current; node* next; current = rootnode; ptr_node = new node; ptr_node->data = member; next = current->ptrnext; for(int i = 0; i < pos; i++) { current = next; next = next->ptrnext; } ptr_node->ptrnext = current->ptrnext; current->ptrnext = ptr_node; ptr->linklist_increaselength(ptr); return 0; } } }
   
  

int linklist::linklist_erase(linklist* ptr,int pos)
{
	node* current = rootnode;
	node* next = current->ptrnext;
	if(pos > ptr->linklist_getlength(ptr))//位置在链表之外
	{
		cout<<"oop!!该位置没有元素"<
  
   ptrnext;
		}

		current->ptrnext = next->ptrnext;
		ptr->linklist_decreaselength(ptr);
	}
}
  

线性表的链式存储具体实现和完整测试代码如下：

#include
  
   
using namespace std;
 struct node	//链表节点
{
	node* ptrnext;
	int data;

};
class linklist //链表类
{
private:
	static int length; //链表长度
	static int capacity;//链表容量

public:
	node* ptr_node;//节点指针
	node* rootnode;//链表根节点，没有元素，指向position为0的节点
	linklist()//构造函数
	{
		length = 0;
		capacity = 0;
		ptr_node = NULL;
		rootnode->ptrnext = NULL;
	}
	linklist(int capacity_num)//带参数的构造函数
	{
		capacity = capacity_num;
		length = 0;
		ptr_node = NULL;
		rootnode = new node;
		rootnode->ptrnext = NULL;
	}
	
	int linklist_insert(linklist* ptr,int pos,int member);//插入元素
	int linklist_erase(linklist* ptr,int  pos);//删除元素
	int linklist_getlength(linklist* ptr);//获取链表长度
	int linklist_getcapacity(linklist* ptr);//获取链表容量
	void linklist_display(linklist* ptr);//顺序输出链表中的每个元素
	void linklist_increaselength(linklist* ptr);//增加元素的个数
	void linklist_decreaselength(linklist* ptr);//减少元素的个数
	int linklist_getmember(linklist* ptr,int pos);//获取某位置上的元素

	~linklist()//析构函数
	{
	
	}	
};
int linklist::length = 0;
int linklist::capacity = 0;
int linklist::linklist_getmember(linklist* ptr,int pos)
{
	node* current = rootnode;
	node* next = current->ptrnext;
	for(int i = 0; i < pos; i++)
	{
		current = next;//循环迭代
		next = current->ptrnext;
	}
	return next->data;
}
void linklist::linklist_decreaselength(linklist *ptr)
{
	ptr->length--;
}
int linklist::linklist_erase(linklist* ptr,int pos)
{
	node* current = rootnode;
	node* next = current->ptrnext;
	if(pos > ptr->linklist_getlength(ptr))//位置在链表之外
	{
		cout<<"oop!!该位置没有元素"<
   
    ptrnext; } current->ptrnext = next->ptrnext; ptr->linklist_decreaselength(ptr); } } int linklist::linklist_getcapacity(linklist *ptr) { return ptr->capacity; } void linklist::linklist_increaselength(linklist* ptr) { ptr->length++; } int linklist::linklist_getlength(linklist* ptr) { return ptr->length; } void linklist::linklist_display(linklist* ptr)//输出每个元素 { node *current; current = rootnode; node* next; next = current->ptrnext; for(int i = 0; i< ptr->linklist_getlength(ptr); i++) { cout<
    
     ptrnext->data<<" "; current = next; next = current->ptrnext; } cout<
     
      linklist_getlength(ptr) == ptr->linklist_getcapacity(ptr))//链表已满 { cout<<"超出链表的容量"<
      
        linklist::linklist_getcapacity(ptr) - 1)//位置在链表之外 { cout<<"位置超出链表的尾巴"<
       
        ptrnext == NULL) //空链表的 { ptr_node = new node; ptr_node->data = member; ptr_node->ptrnext = NULL; rootnode->ptrnext = ptr_node; ptr->linklist_increaselength(ptr); } else //在中间插入 if(ptr->linklist_getlength(ptr) - 1 < pos) { node* current; node* next; current = rootnode; next = current->ptrnext; ptr_node = new node; ptr_node->data = member; ptr_node->ptrnext = NULL; for(int i = 0; i < ptr->linklist_getlength(ptr) ; i++) { current = next; next = current->ptrnext; } current->ptrnext = ptr_node; ptr->linklist_increaselength(ptr); return 0; } else if(pos == 0) //空链表，貌似跟上面的重复了，额，不影响运行 { ptr_node = new node; ptr_node->data = member; ptr_node->ptrnext = rootnode->ptrnext; rootnode->ptrnext = ptr_node; ptr->linklist_increaselength(ptr); return 0; } else { node* current; node* next; current = rootnode; ptr_node = new node; ptr_node->data = member; next = current->ptrnext; for(int i = 0; i < pos; i++) { current = next; next = next->ptrnext; } ptr_node->ptrnext = current->ptrnext; current->ptrnext = ptr_node; ptr->linklist_increaselength(ptr); return 0; } } } int main() { int num; cout<<"链表的容量是多少"<
        
         >num; linklist* LinkList = new linklist(num); int n; cout<<"你想要在链表中放入多少元素"<
         
          >n; int* ptrint = new int[n]; for(int i = 0; i < n; i++) { cin>>ptrint[i]; } for(int i = 0; i < n; i++) { LinkList->linklist_insert(LinkList,i,ptrint[i]); } cout<<"链表中元素是："<
          
           linklist_display(LinkList); LinkList->linklist_erase(LinkList,3); cout<<"删除位置是3（即第4个）的元素后，链表中元素是："<
           
            linklist_display(LinkList); cout<<"位置为2（即第3个）的元素是："<
            
             linklist_getmember(LinkList,2); return 0; }