转载请注明出处：http://blog.csdn.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;
}
测试结果如下：
分享到：
相关推荐
在提供的C++代码中，实现了一个基于链式存储的线性表类`reacl`，使用了模板（template）以支持不同数据类型的元素。模板类使得这个线性表可以用于存储整型、浮点型等任意类型的数据。 类`reacl`包含以下成员函数： ...
在C++编程中，线性表的链式存储通常通过链表来实现，这里的链表可以是单链表或者双向链表。本实验主要关注的是单链表，特别是带头结点的单链表。 链表是一种动态数据结构，它不像数组那样需要预先分配连续的内存...
本问题涉及的是链式存储的实现，具体是用C++语言编写线性表的链式表示，包括插入、删除等基本操作。 首先，链式存储结构是一种动态存储结构，它通过节点间的指针链接来表示元素之间的逻辑关系。在这个例子中，...
通过实验，掌握了单链表的基本操作在链式存储结构上的实现，了解了线性表的逻辑结构特征，并掌握了链式表示的编程方法。 知识点： 1. 线性表的链式表示。 2. 单链表的基本操作。 3. 线性表的逻辑结构特征。 4. ...
下面我们将深入探讨如何用C++通过类来实现链式线性表。 ### 链表类设计 1. **节点定义**：首先，我们需要一个节点类（Node）来存储数据和指向下一个节点的指针。通常，节点类包含两个成员：数据部分（data）和指向...
在本实验中，线性表采用链式存储结构实现，即每个元素（节点）包含一个数据域和一个指向下一个元素的指针。 链式存储结构相比于顺序存储结构（如数组），在插入和删除操作上有更高的灵活性，因为它们不需要考虑元素...
线性表可以采用顺序存储或链式存储两种方式实现。本次实验主要关注的是顺序存储结构。 **顺序存储结构**的特点是使用一组地址连续的存储单元依次存放线性表的数据元素，同时可以通过数组下标直接访问元素，具有访问...
在本实验中，我们将深入理解并实践线性表的链式存储结构，这是一种非顺序存储方式，与数组不同，它通过指针链接元素，使得元素在内存中可以不连续存放。 链式存储结构的核心是链表，链表由一系列节点（或称为元素）...
本实验报告主要围绕线性表的顺序存储和链式存储两种实现方式，以及它们在实际操作中的应用展开。实验的目的是使学生能够深入理解线性表的特性，熟练掌握在顺序表和单链表上执行基本操作的方法。 线性表的基本操作...
线性表有两种常见的实现方式：顺序存储和链式存储。本话题主要关注线性表的链式实现。 链式存储结构是线性表的一种灵活实现方式，它不依赖于数组的连续内存空间。在链式存储中，每个元素称为节点，包含两部分：数据...
线性表是计算机科学中一种基础的数据结构，它是由n（n≥0）个相同类型...在实际编程中，我们可以结合具体需求选择单链表或双向链表，并根据所使用的编程语言特性，如C、C++、Java或Python等，实现相应的链表操作函数。
在C++中，顺序存储通常用数组实现，而链式存储则用链表实现。 链表是一种动态数据结构，它不依赖于内存的连续分配。每个节点包含两部分：数据域和指针域，指针域指向下一个节点的地址。链表的操作包括插入、删除、...
### 线性表的链式存储结构 #### 一、引言 在计算机科学中，数据结构的设计与实现对于程序的效率至关重要。线性表作为最基本的数据结构之一，在多种应用场合都有广泛的应用。线性表可以采用顺序存储或链式存储两种...
在C++中，链式线性表通常通过结构体或类来实现。这里我们将深入探讨如何用C++实现链表。 1. **定义链表节点结构**： 首先，我们需要定义一个结构体或类来表示链表的节点。节点通常包含两部分：数据成员（用于存储...
本实验主要探讨的是线性表的链式存储结构及其在C++中的实现。 链式存储结构是线性表的一种非顺序存储方式，它不依赖于元素在内存中的相对位置，而是通过链接指针来连接元素。在这种结构中，每个元素称为节点，包含...
下面将详细讨论线性表的顺序存储及其实现，以及涉及到的基本操作。 顺序存储的线性表通常使用数组来实现。数组是一种特殊的线性数据结构，它的元素在内存中是按顺序排列的，可以通过索引来快速访问任何位置的元素。...
《数据结构C++版》实验一的目的是让学生深入理解线性表的顺序存储结构，并熟练掌握C++程序设计的基本技巧。在这个实验中，学生需要通过类的定义来实现线性表，数据对象的类型可以自定义。以下是实验涉及的主要知识点...
在实现线性表时，我们首先定义一个模板类`List`，其中包含一个指向节点的指针，每个节点存储一个元素和指向下一个节点的指针。模板参数`T`代表我们要存储的数据类型，可以是整型、浮点型、自定义对象等。 ```cpp ...
线性表是一个相当灵活的数据结构，线性表按照存储方式进行分类有两种，分为顺序存储和链式存储，代码实现了线性表的顺序存储方式，按照数组方式进行实现的，也可自行定义分配一段连续的空间来实现顺序线性表存储方式...