C++实现线性表链式存储（单链）

2024-10-01 04:41:02

本文实例为大家分享了C++实现线性表链式存储的具体代码，供大家参考，具体内容如下

实现的功能：

1、定义了三中传入不同参数的构造函数，用于初始化创建不同的链表；
2、能实现增、删、查等基本功能；

存在的问题：

当创建一个已知大小的空链表后，链表中的数据并不为空,见下图：

下面是代码及测试结果：

singlelinklist.h

#pragma once

#include "iostream"
#include "exception"
#include "stdlib.h"
#include "malloc.h"

using namespace std;

//结点类
template<class T>
class Node
{
public:
 T data;
 Node<T> *next;
 Node()
 {
 this->next = NULL;
 }
 Node(T data, Node<T>* next = NULL)
 {
 this->data = data;
 }
 ~Node() {};
};

//定义链表类
template<class T>
class SLinkList
{
public:
 Node<T> node; //结点
 Node<T>* head; //头指针

 SLinkList();   //创建链表
 SLinkList(int num, T elem[]);
 SLinkList(int num);
 ~SLinkList();

 int LengthSLinkList();  //表长
 void InsertNode(int i, T elem);  //插入结点
  void InsertNode(T elem);
 void DeleteNode(int i); //删除结点
 void DeleteAllNode(); //删除表
 T GetElem(int i);  //按序号查找
 int* GetNum(T elem);  //按元素查找
 void OutputList();    //输出
};

template<class T>
SLinkList<T>::SLinkList()
{
 Node<T>* p = new Node<T>();
 this->head = p;
 cout << "finish<SLinkList()>!" << endl;
}

template<class T>
SLinkList<T>::SLinkList(int num, T elem[])
{
 try
 {
 if(num < 1)
  throw length_error("输入初始化num参数必须大于1！");
 else
 {
  Node<T>* p = new Node<T>();
  this->head = p;
  Node<T>* temp = this->head;
  for (int i = 0; i < num; i++)
  {
  temp->next = new Node<T>(*(elem + i)); //这里犯了一个错，就是把elem[i]直接丢进去，（）里面放的是T类型初始值，实参传进来的是T* elem[]，无法用下标进行访问
  temp = temp->next;
  }
  temp->next = NULL;
  cout << "finish<SL]inkList(int num, T elem[])>!" << endl;
 }
 }
 catch(length_error e)
 {
 cout << "info:" << e.what() << endl;
 exit(1);
 }
}

template<class T>
SLinkList<T>::SLinkList(int num)
{
 try
 {
 if (num < 1)
  throw length_error("输入初始化参数num必须大于1！");
 else
 {
  Node<T>* p = new Node<T>();
  this->head = p;
  Node<T>* temp = this->head;
  for(int i = 1; i <= num; i++)
  {
  temp->next = new Node<T>();
  temp = temp->next;
  }
  temp->next = NULL;
  cout << "finish<SLinkList(int num)>!" << endl;
 }
 }
 catch(length_error e)
 {
 cout << "info:" << e.what() << endl;
 exit(0);
 }
}

//调用函数析构
/*
template<class T>
SLinkList<T>::~SLinkList()
{
 this->DeleteAllNode();
}
*/

template<class T>
SLinkList<T>::~SLinkList()
{
 Node<T>* p = this->head;
 Node<T>* temp = p->next;
 Node<T>* q = NULL;
 while(temp)
 {
 q = temp;
 temp = temp->next;
 delete q;
 }
 delete p;
 delete temp;
 cout << "finish ~SLinkList()" << endl;
}

template<class T>
int SLinkList<T>::LengthSLinkList()
{
 int count = 0;
 Node<T>* p = this->head;
 Node<T>* temp = p->next;
 while (temp)
 {
 count++;
 temp = temp->next;
 }
 return count;
}

template<class T>
void SLinkList<T>::InsertNode(int i, T elem)
{
 try
 {
 if(i<1 || i>LengthSLinkList() + 1)
  throw out_of_range("输入的参数i值超出了链表的范围！");
 else
 {
  if (i != LengthSLinkList()+1) //1-len之间插入
  {
  Node<T>* Elem = new Node<T>(elem);
  Node<T>* temp = this->head;
  for (int j = 1; j < i; j++)
   temp = temp->next;
  Node<T>* p = temp->next;
  temp->next = Elem;
  Elem->next = p;
  }
  else
  InsertNode(elem); //在末尾插入
  cout << "finish<Insert(int i, T elem)>!" << endl;
 }
  }
 catch(out_of_range e)
 {
 cout << "info:" << e.what() << endl;
 exit(0);
 }
}

template<class T>
void SLinkList<T>::InsertNode(T elem)  //末尾插入
{
 Node<T>* Elem = new Node<T>(elem);
 Node<T>* temp = this->head;
 Node<T>* p = NULL;
 while (temp)
 {
 p = temp;
 temp = temp->next;
 }
 p->next = Elem;
 Elem->next = NULL;
 cout << "finnish<InsertNode(T elem)>!" << endl;
}

template<class T>
void SLinkList<T>::DeleteNode(int i)  //返回的是被删除的值
{
 try
 {
 if (i<1 || i > LengthSLinkList())
  throw out_of_range("输入的参数i值超出了链表的范围！");
 else
 {
  Node<T>* temp = this->head;
  for (int j = 1; j < i; j++)
  temp = temp->next;
  Node<T> *p = temp->next;
  temp->next = p->next;
  cout << "finish<DeleteNode(int i)>!" << endl;
 }
 }
 catch(out_of_range e)
 {
 cout << "info:" << e.what() << endl;
 exit(1);
 }
}

template<class T>
void SLinkList<T>::DeleteAllNode()
{
 Node<T>* temp = this->head;
 int count = this->LengthSLinkList();
 while(count)
 {
 DeleteNode(count);
 count--;
 }
 delete temp;
 cout << "finish<DeleteAllNode()>!" << endl;
}

template<class T>
T SLinkList<T>::GetElem(int i)
{
 try
 {
 if(i<1 || i > LengthSLinkList())
  throw out_of_range("输入参数i值超出了链表的范围！");
 else
 {
  Node<T>* temp = this->head;
  for(int j = 1; j <=i; j++)
  temp = temp->next;
  cout << "finish!" << endl;
  cout << "finish<GetElem(int i)>! " << endl;
  return temp->data;
 }
 }
 catch(out_of_range e)
 {
 cout << "info:" << e.what() << endl;
 exit(1);
 }
}

template<class T>
int* SLinkList<T>::GetNum(T elem)
{
 Node<T>* p = this->head;
 Node<T>* temp = p->next;
 int* count = new int[LengthSLinkList()];
 int j = 0;
 for(int i = 1; i <= LengthSLinkList(); i++)
 {
 if(temp->data == elem)
 {
  count[j] = i;
  j++;
 }
 else
  temp = temp->next;
 }
 cout << "finish<GetNum(T elem)>!" << endl;
 return count;
}

template<class T>
void SLinkList<T>::OutputList()
{
 Node<T>* p = this->head;
 Node<T>* temp = p->next;
 cout << "output list：" ;

 for(int i = 1; i <= LengthSLinkList(); i++)
 {
 cout << temp->data << "   " ;
 temp = temp->next;
 }
 cout << endl;
}

main.cpp

#include "iostream"
#include "singlelinklist.h"

using namespace std;

int main()
{
 //Init:测试初始化构造函数
 //operator:测试增、删、查
 //标注行代码为异常测试，主要包括length_error和out_of_range
 //最后输出的是析构函数，下面代码行中未给出，见.h文件中的析构函数定义
 cout << "**************************************************" << endl;
 cout << "test Innit<SLinkList()>" << endl;
 SLinkList<int> sqlinklist1;
 cout << "**************************************************" << endl;
 cout << "test Init<SLinkList(int num, T elem[])>" << endl;
 int num = 5;
 int a[] = {1, 2, 3, 4, 5};
 cout << "input list:" ;
 for(int i = 0; i < num; i++)
 cout << a[i] << "   ";
 cout << endl;
 SLinkList<int> sqlinklist2(num, a);
 cout << "length:" << sqlinklist2.LengthSLinkList() << endl;
 sqlinklist2.OutputList();
 cout << endl;
 //cout << "test error" << endl;
 //SLinkList<int> error1(0, a);
 cout << "**************************************************" << endl;
 cout << "test Init<SLinkList(int num)>" << endl;
 int num1 = 5;
 SLinkList<int> slistlink3(num1);
 cout << "length:" << slistlink3.LengthSLinkList() << endl;
 slistlink3.OutputList();
 cout << endl;
 //cout << "test error" << endl;
 //SLinkList<int> errror(0);
 cout << "**************************************************" << endl;
 cout << "test operation<InsertNode(int i, T elem)>" << endl;
 sqlinklist2.InsertNode(2, 1996);
 sqlinklist2.OutputList();
 cout << endl;
 //cout << "test error" << endl;
 //error.InsertNode(0, 0);
 //error.InsertNode(7, 0);
 cout << "test operation<InsertNode(T elem)>" << endl;
 sqlinklist2.InsertNode(256);
 sqlinklist2.OutputList();
 cout << endl;
 //cout << "test error" << endl;
 //error.InsertNode(0);
 //error.InsertNode(7);
 cout << "**************************************************" << endl;
 cout << "test operation<DeleteNode(int i)>" << endl;
 sqlinklist2.DeleteNode(1);
 sqlinklist2.OutputList();
 cout << endl;
 //cout << "test error" << endl;
 //error.DeleteNode(18);
 //cout << "test operation<DeleteAllNode()>" << endl;
 //sqlinklist2.DeleteAllNode();
 cout << "**************************************************" << endl;
 cout << "test operation<GetElem(int i)>" << endl;
 cout << "num '2' is:" << sqlinklist2.GetElem(2) << endl;
 //cout << "test error" << endl;
 //error.DeleteNode(18);
 cout << "test operation<GetNum(T elem)>" << endl;
 cout << "elem '2' is :" << *(sqlinklist2.GetNum(2)) << endl;
 cout << endl;
 return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

解析C++的线性表链式存储设计与相关的API实现

基本概念链式存储定义: 为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息. 表头结点: 链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息. 数据结点: 链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息. 尾结点: 链表中的最后一个数据结点,其下一元素指针为空,表示无后继. 链表技术领域推演链表链式存储_api实现分析: 在C语言中可以用结构体来定义链表中的指针域,链表中的表头结点也可以
C++实现线性表链式存储（单链）

本文实例为大家分享了C++实现线性表链式存储的具体代码,供大家参考,具体内容如下实现的功能: 1.定义了三中传入不同参数的构造函数,用于初始化创建不同的链表: 2.能实现增.删.查等基本功能: 存在的问题: 当创建一个已知大小的空链表后,链表中的数据并不为空,见下图: 下面是代码及测试结果: singlelinklist.h #pragma once #include "iostream" #include "exception" #include "s
java线性表的存储结构及其代码实现

Java数据结构学习笔记第一篇: 用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系线性结构:数据元素之间存在一个对一个的关系树形结构:数据元素之间存在一个对多个关系图形结构或网状结构:数据元素之间存在多个对多个的关系对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构顺序存储结构链式存储结构本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图. 线性表的基本特征: 总存在唯一的第一个数据元素
Java实现线性表的链式存储

本文实例为大家分享了Java实现线性表的链式存储,供大家参考,具体内容如下链表:一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的. package algorithm.datastructure.linklist; import java.util.NoSuchElementException; /* * 链表 * 物理存储上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现 * * */ public class LinkedLi
C语言数据结构之线性表的链式存储结构

1.什么是线性表的链式存储结构 -链表存储结点:包括元素本身的信息,还有元素之间的关系逻辑的信息这个结点有:数据域和指针域一个指针域:指向后继结点, 单链表二个指针域: 指向前继结点,还有一个指向后继结点双链表 2.原理是: s=(LinkNode *)malloc(sizeof(LinkNode));// s->data=e; //这里赋值了 s->next=p->next; // p->next=s; //这里把指针s给到了p 结点a-> 结点b -> 结
JAVA 实现二叉树（链式存储结构）

二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树)) 链式存储一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针) 二叉搜索树或者叫二叉查找树(BST) 所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false
C语言二叉树的链式存储实例

二叉树的链式存储实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl
C++中实现队列类链式存储与栈类链式存储的代码示例

队列类链式存储代码: linkqueue.hpp // 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int le
Hbase列式存储入门教程

目录 1.逻辑结构 2.物理结构 3.增删改查 4.应用场景 5.参考资料 HBase是一种分布式.可扩展.支持海量数据存储的NoSQL数据库.分布式是因为HBase底层使用HDFS存储数据,可扩展也是基于HDFS的横向扩展能力,作为大数据的存储当然支持海量数据的存储,NoSQL非关系型数据库表结构和关系型数据库(如Mysql)的逻辑结构.物理结构很不一样,性质特点.应用场景也不一样. 1.逻辑结构 1)Name Space 命名空间,类似于关系型数据库的 DatabBase 概念,每个命名空间
队列的动态链式存储实现代码分享

复制代码代码如下: #include <stdlib.h>#include <malloc.h>#include <memory.h>#include <assert.h>#include "DynaLnkQueue.h" /*------------------------------------------------------------操作目的: 初始化队列初始条件: 无操作结果: 构造一个空的队列函数参数: LinkQue

C++实现线性表链式存储（单链）

相关推荐

随机推荐