线性表与链表
用C++编程语言实现 线性与链表 的代码撰写
===对于自定义类(复杂数据类型)===
结点类(class Node)
#pragma once
#include <iostream>
using namespace std;
#include "LinearList.h"
#define NODE
#include <cstring>
函数声明(声明与实现都放入 Node.h 头文件中)
// 复杂数据元素要抽象为一个 结点类Node 。
// 并定义取数据GetNode()函数和输出数据函数OutPutNode(ostream &out)
class Node
{
public:
Node(char* NumberOfStudent, char* NameOfStudent, int grade[]);
Node() {};
Node& GetNode(); //得到结点数据
void OutPutNode(ostream& out)const; //输出结点数据
private:
string StdNumber;
string StdName;
int Score[3];
};
创建结点(构造函数)
Node::Node(char* NumberOfStudent, char* NameOfStudent, int grade[])
{
StdNumber = NumberOfStudent;
StdName = NameOfStudent;
for (int i = 0; i < 3; i++)
{
Score[i] = grade[i];
}
}
得到结点数据
// 实现得到结点数据函数
Node& Node::GetNode()
{
return *this;
}
输出结点数据及重载运算符<<
//输出结点数据
void Node::OutPutNode(ostream& out)const
{
out << StdNumber << " " << StdName << endl;
out << "语文：" << Score[0];
out << "数学：" << Score[1];
out << "英语：" << Score[2];
}
//重载运算符
ostream& operator<<(ostream& out, const Node& x)
{
x.OutPutNode(out);
return out;
}
一、线性表
===对于内置数据(简单数据类型)===
线性表类(class LinearList)
#pragma once
#include <iostream>
using namespace std;
函数声明 (声明与实现都放入 LinearList.h 头文件中)
template<class T>
class LinearList
{
private:
int length; //当前数组元素个数(数组长度)
int MaxSize; //线性表中最大元素个数 (数组最大长度)
T *element; // 一维动态数组（指向顺序表的开始位置）
public:
LinearList(int LLmaxSize); //创建空表 (构造函数)
~LinearList(); //删除表 (析构函数)
LinearList<T>& Insert(int k, const T& x); //在第k个位置插入元素x，返回插入后的列表
bool IsEmpty() const; //判断表是否为空，表空返回true，表非空返回none
int GetLength() const; //返回表中数据元素个数
bool GetData(int k, T& x); //将表中第k个元素保存到x中，不存在则返回false
bool ModifyData(int k, T& x); //将表中第k个元素修改为x，不存在则返回false
int Find(const T& x); //返回x在表中的位置，如果x不在表中返回0
LinearList<T>& DeleteByIndex(int k,T& x); //删除表中第k个元素，并把它保存到x中，返回删除后的线性表
LinearList<T>& DeleteByKey(const T& x,T& y); //删除表中关键字为x的元素，返回删除后的线性表
void OutPut(ostream& out) const; // 将线性表放到输出流out中输出
};
创建空表 (构造函数)
//创建空表 (构造函数)
template<class T>
LinearList<T>::LinearList(int LLmaxSize)
{
MaxSize = LLmaxSize;
element = new T[LLmaxSize];
length = 0;
}
删除表(析构函数)
//删除表 (析构函数)
template<class T>
LinearList<T>::~LinearList()
{
delete[] element;
}
在第k个位置插入元素x，返回插入后的列表
//在第k个位置插入元素x，返回插入后的列表
template<class T>
LinearList<T>& LinearList<T>::Insert(int k, const T& x)
{
if ((k<1)||(k>(length+1)))
cout << "元素下标越界，添加元素失败" ;
else
{
if (length == MaxSize)
cout << "此表已满，添加元素失败" ;
else
{
for (int i = length ; i >= k - 1; i--) //第k个位置元素下标是k-1
{
element[i] = element[i - 1]; //移动元素
}
element[k - 1] = x; //插入元素
length++; //表长+1
}
}
return *this; // 返回自身
}
判断表是否为空
//判断表是否为空，表空返回true，表非空返回none
template<class T>
bool LinearList<T>::IsEmpty()const
{
return length == 0;
}
返回表中数据元素个数
//返回表中数据元素个数
template<class T>
int LinearList<T>::GetLength()const
{
return length;
}
将表中第k个元素保存到x中
//将表中第k个元素保存到x中，不存在则返回false
template<class T>
bool LinearList<T>::GetData(int k, T& x)
{
if (k<1 || k>length) // 1-n 上都合法
return false;
x = element[k - 1]; //第k个元素的下标为k-1
return true;
}
将表中第k个元素修改为x
//将表中第k个元素修改为x，不存在则返回false
template<class T>
bool LinearList<T>::ModifyData(int k, T& x)
{
{
if (k<1 || k>length) // 1-n 上都合法
return false;
element[k - 1] = x ;
return true;
}
}
实现关键字查找 返回所在位置
// 实现关键字查找 返回所在位置
template<class T>
int LinearList<T>::Find(const T& x)
{
for (int i = 0; i < length; i++)
{
if (element[i] == x)
return (i+1);
}
return 0;
}
按位置删除元素
// 按位置删除元素
template<class T>
LinearList<T>& LinearList<T>::DeleteByIndex(int k, T& x)
{
if (GetData(k, x))
{
for (int i = 0; i < length - 1; i++)
{
element[i] = element[i + 1];
}
length--;
}
else
cout << "元素下标越界，删除失败";
return *this;
}
按关键字删除
// 按关键字删除
template<class T>
LinearList<T>& LinearList<T>::DeleteByKey(const T& x, T& y)
{
int index = Find(x);
if (index != 0)
return DeleteByIndex(index, y);
else
{
cout << "没有此元素，删除失败";
return *this;
}
}
输出线性表及重载运算符<<
//输出线性表
template<class T>
void LinearList<T>::OutPut(ostream& out)const
{
for (int i = 0; i < length; i++)
{
out << element[i] << endl;
}
}
//重载运算符
template<class T>
ostream& operator<<(ostream& out, const LinearList<T>& x)
{
x.OutPut(out);
return out;
}
主程序(main)
LinearList<int> l;
l.Insert(1,6);
l.Insert(2,7);
l.Insert(3,8);
cout << l;
二、链表
#include <iostream>
using namespace std;
单结点类(class LinkNode)
// 结点类模板
template<class T>
class LinkNode
{
template<class T>
friend class LinkList;
public:
LinkNode()
{
next = NULL;
}
private:
T data; //结点元素
LinkNode<T>* next; //指向下一个结点指针
};
单向链表类（class LinkList)
函数声明
// 单向链表
template<class T>
class LinkList
{
private:
LinkNode<T> *head; // 指向链表的第一个头结点的指针
public:
LinkList(); //创建链表 (构造函数)
~LinkList(); //删除链表 (析构函数)
LinkList<T>& Insert(int k, const T& x); //在第k个位置插入元素x，返回插入后的链表
bool IsEmpty() const; //判断链表是否为空，表空返回true，表非空返回none
int GetLength() const; //返回链表中数据元素个数
bool GetData(int k); //将链表中第k个元素保存到x中，不存在则返回false
bool ModifyData(int k, const T& x); //将链表中第k个元素修改为x，不存在则返回false
int Find(const T& x); //返回x在链表中的位置，如果x不在链表中返回0
LinkList<T>& DeleteByIndex(int k); //删除链表中第k个元素，并把它保存到x中，返回删除后的线性表
LinkList<T>& DeleteByKey(const T& x); //删除链表中关键字为x的元素，返回删除后的线性表
void OutPut(ostream& out) const; // 将链表放到输出流out中输出
int AnWeiZhi(int k);
};
创建链表(析构函数)
//创建链表 (构造函数)
template<class T>
LinkList<T>::LinkList()
{
head = new LinkNode<T>; // 创建头结点
}
删除链表(析构函数)
//删除链表 (析构函数)
template<class T>
LinkList<T>::~LinkList()
{
T x;
int len = GetLength();
for (int i = len; i >= 1; i--)
{
DeleteByIndex(i); //释放所有结点
}
delete head; //释放头结点
}
在第k个位置插入元素x，返回插入后的链表
//在第k个位置插入元素x，返回插入后的链表
template<class T>
LinkList<T>& LinkList<T>::Insert(int k, const T& x)
{
LinkNode<T>* p = head; //p指向头结点 创建个临时指针，用来遍历链表
LinkNode<T>* newNode = new LinkNode<T>; //创建待插入的新结点
newNode->data = x;
int len = GetLength();
if (k<1 || k>(len + 1))
cout << "元素下标越界，添加元素失败";
else
{
for (int i =1; i < k; i++) //i=0 就错误
{
p = p->next; //将p移动到第k-1个结点
}
newNode->next = p->next; //在k处插入新结点
p->next = newNode; //这两步顺序不可颠倒
}
return *this;
}
判断链表是否为空
//判断链表是否为空，表空返回true，表非空返回none
template<class T>
bool LinkList<T>::IsEmpty() const
{
return head->next == NULL;
}
返回链表中数据元素个数
//返回链表中数据元素个数
template<class T>
int LinkList<T>::GetLength() const
{
int length = 0;
LinkNode<T>* p = head->next; //创建临时指针 用来遍历链表
while (p)
{
length++;
p = p->next;
}
return length;
}
按位置取元素 将链表中第k个元素的值为
//按位置取元素 将链表中第k个元素的值为
template<class T>
bool LinkList<T>::GetData(int k)
{
LinkNode<T>* p = head->next;
int index = 1;
if (k<1 || k>GetLength())
return false;
while (p!=NULL && index<k)
{
index++;
p = p->next;
}
if (p == NULL)
return false;
return true;
}
将链表中第k个元素修改为x
//将链表中第k个元素修改为x
template<class T>
bool LinkList<T>::ModifyData(int k, const T& x)
{
LinkNode<T>* p = head->next;
int index = 1;
if (k<1 || k>GetLength())
return false;
while (p != NULL && index < k)
{
index++;
p = p->next;
}
if (p == NULL)
return false;
else
{
p->data = x;
return true;
}
}
返回x在链表中的位置
//返回x在链表中的位置
template<class T>
int LinkList<T>::Find(const T& x)
{
LinkNode<T>* p = head->next;
int index = 1;
while (p != NULL && p->data != x)
{
p = p->next;
index++;
}
if (p != NULL)
return index;
else
return 0;
}
按位置删除
// 按位置删除
template<class T>
LinkList<T>& LinkList<T>::DeleteByIndex(int k)
{
if (GetData(k))
{
LinkNode<T>* p = head; // 创建一个临时指针指向头结点
LinkNode<T>* q = NULL; // 创建另一个临时指针用来当桥梁
for (int i = 1; i < k; i++)
{
p = p->next;
}
q = p->next;
p->next = q->next;
delete q;
else
cout << "元素下标越界，删除失败";
return *this;
}
按关键字删除
//删除链表中关键字为x的元素，返回删除后的线性表
//按值删除
template<class T>
LinkList<T>& LinkList<T>::DeleteByKey(const T& x)
{
int index = Find(x); //得到删除元素的位置
if (index != 0)
return DeleteByIndex(index);
else
{
cout << "没有此元素，删除失败";
return *this;
}
}
输出线性表及重载运算符<<
//将链表放到输出流out中输出
template<class T>
void LinkList<T>::OutPut(ostream& out) const
{
LinkNode<T>* p = head->next;
while(p != NULL)
{
out << p->data << endl;
p = p->next;
}
}
template<class T>
ostream& operator<<(ostream& out, LinkList<T>& x)
{
x.OutPut(out);
return out;
}
主程序(main)
LinkList<int> l;
l.Insert(1,6);
l.Insert(2,7);
l.Insert(3,8);
cout << l;
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
