线性表的链式储存及其接口函数C++类实现
线性表的链式存储及其接口函数C++类实现
每次最难的就是插入，插入的是第一个和最后一个时比较麻烦
删除比插入简单多了。。。
测试结果如下：
转载请注明出处：http://blog.****.net/hongkangwl/article/details/21883231
首先通过结构体建立每个节点
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<<"超出链表的容量"<<endl;
return -1;
}
if(pos > linklist::linklist_getcapacity(ptr) - 1)//位置在链表之外
{
cout<<"位置超出链表的尾巴"<<endl;
return -1;
}
else
{
if(rootnode->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!!该位置没有元素"<<endl;
return -1;
}
else
{
for(int i = 0; i < pos; i++)
{
current = next;
next = current->ptrnext;
}
current->ptrnext = next->ptrnext;
ptr->linklist_decreaselength(ptr);
}
}
删除比插入简单多了。。。
线性表的链式存储具体实现和完整测试代码如下：
#include<iostream>
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!!该位置没有元素"<<endl;
return -1;
}
else
{
for(int i = 0; i < pos; i++)
{
current = next;
next = current->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<<current->ptrnext->data<<" ";
current = next;
next = current->ptrnext;
}
cout<<endl;
}
int linklist::linklist_insert(linklist* ptr,int pos,int member)
{
if(ptr->linklist_getlength(ptr) == ptr->linklist_getcapacity(ptr))//链表已满
{
cout<<"超出链表的容量"<<endl;
return -1;
}
if(pos > linklist::linklist_getcapacity(ptr) - 1)//位置在链表之外
{
cout<<"位置超出链表的尾巴"<<endl;
return -1;
}
else
{
if(rootnode->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<<"链表的容量是多少"<<endl;
cin>>num;
linklist* LinkList = new linklist(num);
int n;
cout<<"你想要在链表中放入多少元素"<<endl;
cin>>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<<"链表中元素是："<<endl;
LinkList->linklist_display(LinkList);
LinkList->linklist_erase(LinkList,3);
cout<<"删除位置是3（即第4个）的元素后，链表中元素是："<<endl;
LinkList->linklist_display(LinkList);
cout<<"位置为2（即第3个）的元素是："<<endl;
cout<<LinkList->linklist_getmember(LinkList,2);
return 0;
}
测试结果如下：