手机版
你好,游客 登录 注册
背景:
阅读新闻

线性表之单链表C++实现

[日期:2017-04-03] 来源:Linux社区  作者:lcy362 [字体: ]

线性表之单链表

一、头文件:LinkedList.h

//单链表是用一组任意的存储单元存放线性表的元素,这组单元可以是连续的也可以是不连续的,甚至可以是零散分布在内存中的任意位置。
//单链表头文件
#include<iostream>
using namespace std;
//定义单链表结点-结构体类型
template<class DataType>
struct Node
{
  //数据域,存放该结点的数据
  DataType data;
  //指针域,指向下一个结点
  Node<DataType> *next;
};

template<class DataType>
class LinkedList{
public:
  //单链表无参构造器
  LinkedList();
  //单链表有参构造器
  LinkedList(DataType array[], int n);
  LinkedList(int n, DataType array[]);
  //单链表析构函数
  ~LinkedList();
  //获取单链表的长度
  int GetLength();
  //查找单链表指定元素的序号
  int GetLocal(DataType x);
  //获取单链表指序号的元素
  DataType GetElement(int index);
  //单链表中在指定位置插入指定的元素
  void Insert(int index, DataType x);
  //在单链表中删除指定位置的元素
  DataType Delete(int index);
  //按序号输出单链表中的元素
  void PrintLinkedList();

private :
  //声明单链表的头指针
  Node<DataType> *first;
};

//实现单链表的无参构造函数
template<class DataType>
LinkedList<DataType>::LinkedList()
{
  first = new Node<DataType>;
  first->next = NULL;
}

//头插法建立单链表
template<class DataType>
LinkedList<DataType>::LinkedList(int n,DataType array[])
{
  //初始化一个空链表
  first = new Node<DataType>;
  first->next = NULL;
  for (int i = 0; i < n; i++)
  {
    //为每一个数组元素都申请新结点
    Node<DataType> *s = new Node<DataType>;
    //数组元素赋值给结点数据域
    s->data = array[i];
    //将结点插入到头结点之前
    s->next = first->next;
    first->next = s;

  }
}

//尾插法建立单链表
template<class DataType>
LinkedList<DataType>::LinkedList(DataType array[], int n)
{
  //生成头结点
  first = new Node<DataType>;
  //定义尾结点
  Node<DataType> *r = first;
  for (int i = 0; i < n; i++)
  {
    //为每一个数组元素申请一个结点
    Node<DataType> *s = new Node<DataType>;
    //把数组元素赋值给结点的数据域
    s->data = array[i];
    //将每一个结点追加到终端结点之后
    r->next = s;
    r = s;
  }
  //尾结点尾NULL
  r->next = NULL;
}

//实现单链表的析构函数
template<class DataType>
LinkedList<DataType>::~LinkedList()
{
  //声明工作指针
  Node<DataType> *q;
  while (first != NULL)
  {
    //暂存被释放的结点
    q = first;
    //让头指针指向要释放结点的下一个结点
    first = first->next;
    delete q;
  }
}

//实现单链表插入:在指定的位置插入指定的元素
template<class DataType>
void LinkedList<DataType>::Insert(int index, DataType x)
{
  //定义工作指针
  Node<DataType> *p = first->next;
  //定义计数器,初始值为0
  int count = 0;
  while (p != NULL &&count < index - 1)
  {
    //工作指针后移
    p = p->next;
    count ++;
  }
  //找到 index-1 的位置
  if (p == NULL)
  {
    throw "插入的位置有误";
  }
  else
  {
    //申请一个新结点
    Node<DataType> *s;
    s= new Node<DataType>;
    //其数据域为 x
    s->data = x;
    //在新结点的指针域存放工作指针p的指针域
    s->next = p->next;
    //将结点s插入到p结点之后
    p->next = s;
  }
}

//实现单链表的按值查找,返回指定元素在单链表中的序号(如不存在,则返回0)
template<class DataType>
int LinkedList<DataType>::GetLocal(DataType x)
{
  //定义工作指针
  Node<DataType> *p = first->next;
  //定义计数器,初始值是1
  int count = 1;
  //查找序号所对应的位置
  while (p != NULL)
  {
    if (p->data == x)
    {
      return count;
    }
    //工作指针后移
    p = p->next;
    //计数器加1
    count++;
  }
  //如果找不到该元素,则返回0
  return 0;
}

//实现单链表按位查找,返回指定位置的元素
template<class DataType>
DataType LinkedList<DataType>::GetElement(int index)
{
  //定义工作指针
  Node<DataType> *p = first->next;
  //定义计数器,初始值是1
  int count = 1;
  //查找序号所对应的位置
  while (p != NULL&&count < index)
  {
    //工作指针后移
    p = p->next;
    //计数器加1
    count++;
  }
  //如果找到单链表的末尾,还找不到指定的位置,则抛出异常
  if (p == NULL)
  {
    throw "查找的位置有误";
  }
  else
  {
    //当找到合适的位置时,返回该位置上的元素
    return p->data;
  }

}

//实现获取单链表的长度
template<class DataType>
int LinkedList<DataType>::GetLength()
{
  //定义计数器,用来计算单链表的长度
  int count = 0;
  //定义工作指针
  Node<DataType> *p = first->next;
  while (p != NULL)
  {
    p = p->next;
    count++;
  }
  return count;

}

//实现单链表的按序号输出元素
template<class DataType>
void LinkedList<DataType>::PrintLinkedList()
{
  //声明工作指针
  Node<DataType> *p;
  //初始化工作指针
  p = first->next;
  while(p != NULL)
  {
    cout << p->data << " ";
    //工作指针向后移动
    p = p->next;
  }
  cout << endl;
}

//实现单链表的删除
template<class DataType>
DataType LinkedList<DataType>::Delete(int index)
{
  Node<DataType> *p = first->next;
  int count = 0;
  //查找第 index-1 位置结点
  while (p != NULL&&count < index - 1)
  {
    p = p->next;
    count++;
  }
  //如果能找到
  if (p == NULL || p->next == NULL)
  {
    throw "删除的位置有误";
  }
  else
  {
    Node<DataType> *q = p->next;
    DataType x = q->data;
    p->next = q->next;
    delete q;
    return x;
  }
}

 二、测试线性表之单链表的源文件:TestLinkedList.cpp

 

#include<iostream>
#include "LinkedList.h"
using namespace std;
void show()
{
  cout << "---------------------------------------" << endl;
}
int main()
{
  int array[] = { 1, 3, 5, 2, 7, 6, 9, 8, 10, 4};
  //声明单链表
  LinkedList<int> linkedList = LinkedList<int>(10,array);
  cout << "输出单链表:" << endl;
  linkedList.PrintLinkedList();
  show();
  cout << "单链表的长度:" << linkedList.GetLength() << endl;
  cout << "单链表中第5个元素是:" << linkedList.GetElement(5) << endl;
  cout << "单链表中元素5的位置是:" << linkedList.GetLocal(5) << endl;
  show();
  cout << "在单链表的第5个位置上插入元素22" << endl;
  linkedList.Insert(5, 22);
  cout << "输出单链表:" << endl;
  linkedList.PrintLinkedList();
  cout << "单链表的长度:" << linkedList.GetLength() << endl;
  show();
  cout << "删除第5位置的元素" << endl;
  linkedList.Delete(5);
  cout << "输出单链表:" << endl;
  linkedList.PrintLinkedList();
  cout << "单链表的长度:" << linkedList.GetLength() << endl;
  show();
  return 0;
}

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-04/142465.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款