转载请注明出处：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;
}
测试结果如下：
分享到：
相关推荐
线性表是一个相当灵活的数据结构，线性表按照存储方式进行分类有两种，分为顺序存储和链式存储，代码实现了线性表的顺序存储方式，按照数组方式进行实现的，也可自行定义分配一段连续的空间来实现顺序线性表存储方式...
详情介绍：...基于链式存储结构的线性表实现：依据最小完备性和常用性相结合的原则，以函数形式定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等12种基本运算 。
根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表线性表的...
该代码实现了线性表的链式存储，包括创建线性表、删除线性表、清空线性表、插入元素、删除元素等API函数
本文实例为大家分享了C++实现线性表链式存储的具体代码，供大家参考，具体内容如下 实现的功能： 1、定义了三中传入不同参数的构造函数，用于初始化创建不同的链表； 2、能实现增、删、查等基本功能； 存在的问题：...
用C++描述，分为顺序存储的线性表类contlist和链式存储的线性表类linklist。均已放在头文件中
*5.6 C＋＋处理字符串的方法——字符串类与字符串变量 5.6.1 字符串变量的定义和引用 5.6.2 字符串变量的运算 5.6.3 字符串数组 5.6.4 字符串运算举例 习题 第6章 指针 6.1 指针的概念 6.2 变量与指针 6.2.1 定义...
一条记录有学号和成绩两个数据项，按成绩由大到小建立两个有序表（分别顺序表和链式表实现），并合并成一个有序表（有能力的同学才做这个合并）。第一个表输入的数据如下（学号，成绩）：(1,70),(2,85), (3,75), (4,...
*5.6 C＋＋处理字符串的方法——字符串类与字符串变量 5.6.1 字符串变量的定义和引用 5.6.2 字符串变量的运算 5.6.3 字符串数组 5.6.4 字符串运算举例 习题 第6章 指针 6.1 指针的概念 6.2 变量与指针 6.2.1 定义...
设计顺序表（单链表）类，在顺序表（单链表）类中增加成员函数，实现顺序表（单链表）的置逆，在顺序表（单链表）类中增加成员函数，实现两个顺序表（单链表）的合并，编写主函数，调用上述新增加函数。
本教程共分为5个部分，第一部分是C语言提高部分，第二部分为C++基础部分，第三部分为C++进阶部分，第四部分为C、C++及数据结构基础部分，第五部分为C_C++与设计模式基础，内容非常详细. 第一部分 C语言提高部分目录...
掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。 掌握线性表的链式存储结构的应用。 （1）描述你在进行实现时，主要的...
在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） 注意： 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的...
Data Structures， Algorithms， and Applications in C++， Second Edition 出版者的话 译者序 前言 第一部分 预备知识 第1章 C++回顾 1.1 引言 1.2 函数与参数 1.2.1 传值参数 1.2.2 模板函数 1.2.3 引用参数 ...
（1）使用指针和引用两种方式，完成两个学生的交换。 （2）定义一个结构体类型student，写一个...（3）完成线性表的基本操作：插入、删除、查找，遍历、以及线性表合并等运算在顺序存储结构和链式存储结构上的运算。
因此，要熟练掌握线性表的基本操作（建立、插入、删除、遍历等）在顺序存储和链式存储上的实现。通过实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。同时，...
<br>实验二 单链表结构及计算 实验目的: 通过实验掌握下列知识: 1、熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现； 2、继续熟悉VC编程、编译和调试环境； 内容及步骤:...
理解线性表的定义、顺序存储构造和链式存储构造。 2. 理解线性表的逻辑构造特征。 3. 掌握线性表的两种存储方法〔顺序表和链式表〕，并体会两者差异。 4. 掌握线性表的表示和实现。 5. 学会使用线性表解决一些相关...
线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D.上述三种说法都...