C++ 数据结构应用——链表
头文件：Linklist.h
#include <iostream>
/******************************************************
Copyright: University of Science & Technology Beijing
Author: Turing Aaron
Date: 2017-05
Description:
ProgrammingLanguage: C++
FunctionName -------- Description
Createlist() 创建链表，申请链表头节点的空间，并将头节点的next指针指向NULL。
ListInsert() 按给定链表位置序号找到位置并将元素插入到该序号后面。
ListClear() 遍历链表，依次释放节点的内存。
ListDel() 按照给定序列的值从链表中删除该结点。
GetElem() 按序号查找链表中的元素，并返回该节点的指针。
LocateElem() 按值查找（定位）链表中的元素，并返回该节点的指针。
print() 遍历链表并打印元素的data.
isEmpty() 判断链表是否为空。
Adjmax() 计算相邻k个节点data值之和最大的第一节点。
*******************************************************/
class LinkList
{
public:
//链表的构造函数，调用私有方法中的Creatlist()，下同，都是通过公共函数调用私有函数
LinkList() { Createlist(); }
int Adjmax(const int & k) {
return Adjmax(head, k);
}
const int & GetElem(int i) {
return GetElem(head, i)->data;
}
const int & LocateElem(const int & data) {
LocateElem(head, data);
}
bool ListInsert(const int &i, const int & data) {
return ListInsert(head, i, data);
}
bool ListDel(const int &i) {
ListDel(head, i);
}
void ListClear() {
ListClear(head);
}
void print() {
print(head);
}
bool isEmpty() {
return isEmpty(head);
}
private:
struct LinkNode
{
int data;
LinkNode *next;
//LinkNode的初始化函数（调用new时会调用这个函数）
LinkNode(const int & data, LinkNode *next = NULL)
: data(data), next(next) { }
};
LinkNode *head;
void Createlist();
int Adjmax(LinkNode * & L, const int & k);
void ListClear(LinkNode * & H);
LinkNode * GetElem(LinkNode * H, int i) const;
LinkNode * LocateElem(LinkNode *H, const int & data) const;
bool ListInsert(LinkNode * & H, const int & i, const int & data) const;
bool ListDel(LinkNode * & H, const int & i);
void print(LinkNode * H);
bool isEmpty(LinkNode * & head);
};
/*******************************************************
Function: Adjmax().
Description: 计算相邻k个节点data值之和最大的第一节点.
Arguments: 链表头节点 LinkNode * & L, 链表长度 const int & k .
Variables:
VariableName -------- Description
LinkNode* p 记录当前区间头指针
LinkNode* q 记录当前区间尾指针
int sum 记录当前区间内所有data之和；
int maxSum 记录和最大的值；
int maxNode 记录和最大的那个区间的第一个节点位置；
int curNode 记录当前区间第一个节点位置。
Return: 和最大的第一节点在链表中的序号
*******************************************************/
int LinkList::Adjmax(LinkNode * & L, const int & k) {
//检测空链表
if (L->next == NULL) return 0;
//curNode为当前计数区间的头一个结点
int sum = 0, maxSum = 0, maxNode = 1, curNode = 1;
LinkNode *p = NULL, *q = NULL;
p = q = L->next;
//根据k的范围移动q指针,sum记录为q到p区间内的和
//初始化sum，记录和为[1, k]的数据。
for (int i = 1; i <= k ; i++) {
sum += q->data;
q = q->next;
if(q==NULL){
std::cout << "[-] ---------- 您输入的k值小于链表长度 ----------" << std::endl;
return maxNode;
}
}
maxSum = sum;
//开始移动长度为k的区间，减去前一个元素，加上后一个元素，同时移动curNode，如果sum更大，则更新maxNode
while (q) {
sum -= p->data;
p = p->next;
curNode++;
sum += q->data;
q = q->next;
if (sum > maxSum) {
maxSum = sum;
maxNode = curNode;
}
}
return maxNode;
}
//创建链表，申请链表头结点的空间，并将头节点的next指针指向NULL。
void LinkList::Createlist() {
head = new LinkNode(0);
}
//遍历链表，依次释放结点的内存。
void LinkList::ListClear(LinkNode * & H) {
LinkNode * p;
p = H;
//从头结点开始循环删除
while (p)
{
LinkNode *q;
q = p->next;
delete p;
p = q;
}
}
//按序号查找链表中的元素，并返回该节点的指针。
LinkList::LinkNode * LinkList::GetElem(LinkNode * H, int i) const {
//输入的i小于0或链表为空时返回NULL
if (i < 0)
return NULL;
//新建指针指向表头
LinkNode * P = H;
//由于是从表头开始遍历，所以开始时位置为-1
int j = -1;
//从表头开始遍历i个节点
while (P->next && j < i)
{
P = P->next;
++j;
}
//成功遍历到第i个节点，返回该元素的指针
if (i == j) return P;
//否则返回空指针
else return NULL;
}
//按值查找（定位）链表中的元素，并返回该节点的指针。
LinkList::LinkNode * LinkList::LocateElem(LinkNode *H, const int & data) const {
//新建指针指向第一个元素
LinkNode * P = H->next;
//遍历链表，如果没找到data，P指针为NULL
while (P && P->data != data)
P = P->next;
return P;
}
//按给定链表位置序号找到位置并将元素插入到该序号后面。
bool LinkList::ListInsert(LinkNode * & H, const int & i, const int & data) const {
LinkNode * p, *q;
if (i == 0) p = H;
else p = GetElem(H, i - 1);
if (p == NULL)
return false;
else
{
//在q中存入数据，并把p指针的下一位给新节点q
q = new LinkNode(data, p->next);
p->next = q;
return true;
}
}
//按照给定序列的值从链表中删除该结点。
bool LinkList::ListDel(LinkNode * & H, const int & i) {
LinkNode *p, *q;
//如果输入位置为0，则从头开始删除
if (i == 0)
p = H;
//如果不是，则查找该元素
else
p = GetElem(H, i - 1);
if (p&&p->next)
{
q = p->next;
p->next = q->next;
delete q;
return true;
}
else
return false;
}
//遍历链表并打印元素的data.
void LinkList::print(LinkNode * H) {
if (H == NULL)
return;
for (LinkNode *p = head->next; p; p = p->next) {
std::cout << p->data << "\t";
}
std::cout << std::endl;
}
//判断链表是否为空。
inline bool LinkList::isEmpty(LinkNode * & head) {
return head == NULL ? true : false;
}
主文件：list_app.cpp
#include "LinkList.h"
#include <string>
#include <ctype.h>
#include <fstream>
#include <sstream>
#include <limits>
using namespace std;
int main()
{
cout << "实验1：链表的应用 -- 作者：Turing Aaron" << endl;
while (true)
{
menu:
cout << "\n[+] 是否创建链表？\n"
<< "1) 创建链表\t2) 退出系统\t3) 从文件读入数据" << endl;
//读入操作数并将第一个字符做为操作数
string op_input;
cin.clear();
getline(cin, op_input);
int op = op_input[0] - '0';
//1） 创建链表
if (op == 1)
{
//---初始化链表---
cout << "[+] ---------- 正在初始化链表... ----------" << endl;
LinkList *myList = new LinkList;
cout << "[+] ---------- 初始化完毕，接下来请输入k值 ----------" << endl;
int k = 0;
while (true)
{
cin >> k;
if (cin.good())
break;
else if (cin.fail())
{
cout << "[-] ---------- k值输入错误，请重新输入！----------" << endl;
//清空输入流
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
}
//---数据读取---
cout << "[+] ---------- 请输入数据，#结束输入 ----------" << endl;
cin.clear();
int data = 0, listLen = 0;
while (true)
{
cin >> data;
//如果读入的是数字，则插入链表
if (cin.good())
myList->ListInsert(listLen++, data);
//如果输入的不是数字，输入流cin的fail会被置位，此时读入一个字符，判断是#还是非法字符。
else if (cin.fail())
{
char c = getchar();
if (c == '#')
break;
cin.ignore();
cout << "[-] ---------- 输入的【 " << c << " 】非法，该输入跳过! ----------" << endl;
//清空错误输入流
cin.clear();
}
}
//---判断链表内是否有数据---
if (myList->isEmpty())
{
myList->ListClear();
goto menu;
}
//---输出链表---
cout << "[+] ---------- 您输入的链表为： ----------" << endl;
myList->print();
//---调用Adjmax()求值---
cout << "[+] ---------- 开始计算相邻 [ " << k << " ] 个节点和最大的第一个节点 ----------" << endl;
int maxNode = myList->Adjmax(k);
if (maxNode == 0)
cout << "[-] ---------- 链表为空！请检查！----------" << endl;
else
{
cout << "[+] 相邻 " << k << " 个结点data值之和为最大的第一结点为： " << endl;
cout << "[+] 序号" << maxNode << ", data值" << myList->GetElem(maxNode - 1) << endl;
}
cout << "[+] ---------- 计算结束 ----------" << endl;
//---析构链表---
myList->ListClear();
//---清除输入流---
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
//2） 退出系统
else if (op == 2)
{
cout << "[+] ---------- 感谢使用，再见 ----------" << endl;
exit(0);
}
//3） 从文件读入数据
else if (op == 3)
{
//------从文件读入数据------
string file_name;
cout << "[+] ----------- 请输入要读取的文件名字 ---------" << endl;
getline(cin, file_name);
ifstream fin(file_name);
//------打开文件失败------
if (!fin)
{
cout << "[-] ---------- 找不到数据文件，请检查！ ----------" << endl;
goto menu;
}
//在读到文件结束以前
while (fin.peek() != EOF)
{
int k = 0;
string k_input, data_input;
getline(fin, k_input);
//如果k的输入非空且第一个字符为数字，则判断为k的输入有效，否则退出循环
if (!k_input.empty())
k = k_input[0] - '0';
else
break;
//建立链表
LinkList *myList = new LinkList;
getline(fin, data_input);
//将data字符串输入变为数据流，方便链表读取
istringstream sin(data_input);
int data = 0, listLen = 0;
while (sin >> data)
{
myList->ListInsert(listLen++, data);
}
//---输出链表---
cout << "[+] ---------- 您输入的链表为： ----------" << endl;
myList->print();
//---调用Adjmax()求值---
cout << "[+] ---------- 开始计算相邻 [ " << k << " ] 个节点和最大的第一个节点 ----------" << endl;
int maxNode = myList->Adjmax(k);
if (maxNode == 0)
cout << "[-] ---------- 链表为空！请检查！ ----------" << endl;
else
{
cout << "[+] 相邻 " << k << " 个结点data值之和为最大的第一结点为： " << endl;
cout << "[+] 序号" << maxNode << ", data值" << myList->GetElem(maxNode - 1) << endl;
}
cout << "---------------------------------------------------------------------------------------" << endl;
//---析构链表---
myList->ListClear();
}
fin.close();
}
//非法参数
else
cout << "[-] ---------- 非法参数，请重试！ ----------" << endl;
}
return 0;
}
其他的以后有空再补充哈