数据结构–模板类实现单链表（参考殷人昆版本c++第二版）------学习体会理解
#pragma once
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include
#include
using namespace std;
#ifndef INSMOD_INF_INR
#define INSMOD_INF_INR
enum InsMod { INF, INR };//定义向前还是向后生成
#endif
/*我明白了，定义的结点保存的数据，是一个个分散的数据，是没有任何线性关系的数据
根据我的理解，这种定义方式一次只能构造一个结点，所以在拉链的时候需要有指针不断开辟下一个空间
*/
template struct LinkNode {
T data;
LinkNode* link;
LinkNode(LinkNode* ptr = NULL) {
link = ptr;
}//一个具有默认值的初始化函数，可是这样做有什么好处呢？！
LinkNode(const T& item, LinkNode* ptr = NULL) {
data = item;
link = ptr;
}
//这里对函数进行了一次函数重载，对data进行初始化的函数，和安排指向data
};
//自己的理解：const有可能会对链表改变的函数
template class List {
public:
List() {
first = new LinkNode;
}
List(const T& x) {//头结点中可放特殊信息
first = new LinkNode(x);
}
List(List& L);
~List() {//改
makeEmpty();
delete first;
}
void makeEmpty();
int Length()const;
LinkNode* getHead()const {
return first;
}
LinkNode* Search(const T& x);
LinkNode* Locate(int i);
bool getData(int i, T& x)const;
void setData(int i, T& x);
bool Insert(int i, T& x);
bool Remove(int i, T& x);
bool IsEmpty()const {
return (first->link == NULL) ? true : false;
}
bool IsFull()const {
return false;
}
void Sort();
void Inverse();
void input(T endTag, InsMod im = INR);
void output();
List& operator = (List& L);
friend ostream& operator << (ostream& out, List& L) {
LinkNode* current = L.first->link;
while (current) {
out << current->data << ‘\t’;
current = current->link;
}
out << endl;
return out;
}
friend istream& operator >> (istream& in, List& L) {//已改
LinkNode* newNode, * last;
T val;
L.makeEmpty();
last = L.first;
while (!in.eof()) {
in >> val;
newNode = new LinkNode(val);
assert(newNode);
last->link = newNode;
last = newNode;
}
last->link = NULL;
return in;
}
protected:
LinkNode* first;
void inputFront(T endTag);
void inputRear(T endTag);
};
template List::List(List& L) {//定义一个L的链表
T value;//声明一个value
LinkNode* srcptr = L.first;//定义一个指针来保存first头指针，主要是用来保存数据的
LinkNode* destptr = first = new LinkNode;//定义一个指针来为该节点开辟空间
while (srcptr->link) {//拉链的过程，不是遍历，因为目前只有一个头结点不存在链表
value = srcptr->link->data;//这里的data应该头结点内保存的值，将已经初始化的data值复制给value
destptr->link = new LinkNode(value);//将value值放在第一个结点空间内
destptr = destptr->link;//指针向后移到下一个空间，虽然还没有创建，经过LinkNode* destptr = first = new LinkNode创建下个空间;
srcptr = srcptr->link;//指针后移，递归
}
destptr->link = NULL;//结束标志，停止拉链
}
template void List::makeEmpty() {
LinkNode* q;//定义一个结点指针
while (first->link) {
q = first->link;
first->link = q->link;
delete q;
}
}
template int List::Length()const {
LinkNode* p = first->link;
int count = 0;
while § {
p = p->link;
count++;
}
return count;
}
/为什么要特意设置一个指针变量current来保存第一个结点/ //const 修饰，X函数体之内不可改变
template LinkNode* List::Search(const T& x) {//传地址引用
LinkNode* current = first->link;//
while (current/指针有指向的时候执行循环体/ && current->data != x) {
current = current->link;
/递归下去，全链遍历/
}
return current;
}
/我一直很奇怪为什么链表没有进行编号，怎么判断位置？其实灭有进行编号，只是进行了
i次遍历，执行完成之后，找到的的就是第i个数据/
template LinkNode* List::Locate(int i) {//改
if (i < 0) return NULL;//判断输入合法性
LinkNode* current = first;
int k = 0;
while (current/指针有指向执行循环体/ && k < i) {
current = current->link;//=first->link 机第一个结点
k++;
}//未找到返回NULL
return current;
}
//locate返回的是指向i的data的指针，下面这个函数则是返回指针指向i的data
/这个函数可以返回第i个结点的值/
/*
template bool List::getData(int i, T& x) {
if (i <= 0) return NULL;
LinkNode* current = Locate(i);
cout <<“f” << first->data << endl;
cout << first->link->data << endl;
if (!current//指针没有有指向//) return false;
else {
x = current->data;
//return true;// cout << x << endl;
}
}/
//获取第i个值，用x返回，不过为了安全性，加了Const，所以并不能真正的获取值，但是可以检测出该结点有没有值，因此函数为bool型
template bool List::getData(int i, T& x)const {
if (i <= 0) return NULL;
LinkNode current = Locate(i);
if (!current)//指针没有有指向，换言之就是说链表为空或者说这个链表是一个空链数据域没有放入值//)
return false; //无值返回0
else {
x = current->data;//X用俩保存第i个指针的值
return true; //有值返回则返回1
}
}
//将第i个值x代替
template void List::setData(int i, T& x) {
if (i <= 0) return; //判断输入合法性
LinkNode* current = Locate(i); //用定位函数locate,找到i个位置，并用current来保存
if (!current) return;//判断current的合法性，即是否有指向
else current->data = x; //并将传入的数赋值给该指针所指向的data值
}
//在第i个位置插入值x，定位函数灰常好用哎
//这里注意到一个细节，这个函数没有用const修饰，可以发现有些函数用了const修饰，有些没有，可以考虑一下为什马🐎
template bool List::Insert(int i, T& x) {
LinkNode* current = Locate(i);//用定位函数locate,找到i个位置，并用current来保存
if (!current) return false;//判断输入合法性
LinkNode* newNode = new LinkNode(x);/建立一个新的结点，这是用来干什么的呢？！而且这个节点还是已经初始化的，data = x
下一步那肯定是要吧这个结点并入链中了/
if (!newNode) {
cerr << “Memory allocating error!” << endl;
exit(1);
}/这个函数是用来判断分配空间是否成功的，就实验而言,没有影响，但是为了程序的健壮性，没有毛病/
newNode->link = current->link; /新结点的link变成指向第i + 1个结点，这里最重要的是理解节点的整体性，万不可把link和LIinkNode分开看
，新结点现在篡位i已经成功了一半了，有了后继没有前驱，也就是说现在有两个指针current和newNode->link指向第i+1个结点/
current->link = newNode;/前驱来了，将第i个结点指针指向新结点/
return true;/篡位成功/
}
//remove移除结点，用的还是保存删除那一套
template bool List::Remove(int i, T& x) {//很常规的传地址参数
LinkNode* current = Locate(i - 1);//老样子，这次保存的是第i-1个结点
if (!current || !current->link) /常规判断是否有指向，和他的下一个指针（第i个指针）是否有指向/
return false;
LinkNode* del = current->link;/定义一个del结点指针来保存第i个指针/
current->link = del->link;/将第i-1个的结点指针link指向第i+1个结点这时第i个已经孤立出去了///这里我有点疑问
x = del->data;/将/
delete del;
return true;
}
//输出链表数据
template void List::output() {
LinkNode* current = first->link;/指向第一个节点/
while (current) {/指针有指向，然后遍历数据/
cout << current->data << endl;
current = current->link;/递归/
}
}
/*重载符号 = //和构造函数的函数体二毛一样//复制构造函数，将=号进行重载/
template List& List::operator = (List& L) {//改
T value;/定义一个值/
LinkNode destptr = L.first, * srcptr = L.first;/那么问题来了，为什么使用两个first呢
哼哼哼，经过实验，明明就是一样的,/
makeEmpty();//先清空，后复制
while (srcptr->link)
{
value = srcptr->link->data;
destptr->link = new LinkNode(value);
destptr = destptr->link;
srcptr = srcptr->link;
}
destptr->link = NULL;
return *this;
}
/值得学习借鉴，用枚举方式来进行前插后插输入的选择，这是静态的，是我的话会用switch()
分支结构，感觉会比较的智能/
template void List::input(T endTag, InsMod im) {
if (im == INF) inputFront(endTag);
else inputRear(endTag);
}
/也许会有疑问，埃纳缅不是有构造函数进行链表创建了嘛？没有错，但那只是形成了逻辑上的链表
斌没有进行参数实例化，而这个输入函数是进行将链表data域填充的，扦插和后插只不过是一种
数据的排列方式，链表还是那个链表，关键数据从哪个打他开始放/
template void List::inputFront(T endTag) {//改，添加
LinkNode* newNode;/定义一个新的结点，这里没有初始化但是为什么可以编译通过呢？！因为
结点结构体中已经用构造函数执行了默认初始化/
T val;//定义一个新的变量
cin >> val;//输入一个变量的值
while (val != endTag) {
newNode = new LinkNode(val);/只要不为结束符，就将输入的值data存入新结点中/
if (!newNode) {/判断新结点内存分配/
cerr << “Memory allocating error!” << endl;
exit(1);
}
newNode->link = first->link;/原本first->link代表的是第一个结点，现在新的结点作为第一个结点了/
first->link = newNode;/那么first指针进行迁移，变成指向新结点，那么first依然是first/
cin >> val;/熟悉的递归/
}
}
/后插法，估计也没什么太大的变化，哇哈哈哈//到这一步我也大概清楚了，为什么会使用保存指针变量了/
template void List::inputRear(T endTag) {//改
LinkNode* newNode, * last = first;/大家看这里差别就来了，同样是初始化，为什么newNode不需要初始化，哈哈哈//熟悉的newNode，还是保存指针变量那一套/
T val;/定义变量/
while (last->link != NULL)/干嘛呢这是，检验下一个结点是否为空？？！！感觉不是很有意义/
last = last->link;/然后进行循链遍历结点/
cin >> val;//输入值
while (val != endTag) {
newNode = new LinkNode(val);/将值放在结点的data域中/
if (!newNode) {/老一套喽，健壮/
cerr << “Memory allocating error!” << endl;
exit(1);
}
last->link = newNode;/原本这个last->link指向的是第一个结点，原来循环遍历的用处在这里
last指针不断后移/
last = newNode;/这时last和newNode进行绑定了，之后所有新建的newNode都会在前一个newNode后面，也就是last的后面/
/换个说法last需要不断的进行更新，不能一直为一个指针，因为指针是没u有link域的，无法指向下一个结点/
cin >> val;/递归/
}
last->link = NULL;/终止条件，就设定的嘛/
}
template void List::Sort() {
}
/*反转链表函数，这个函数用的时候，链表不为空 /
template void List::Inverse() {
LinkNode h, * p, * pr;/三个变量，看起来很麻烦的样子/
h = NULL;/h为一个空，指向也为空，起点到的是保存变量的作用，其实感觉可以不初始化时不行的/
p = first->link;/这其实是一个遍历变量，第一个结点/
/我们先看一下第一次遍历是/
while § {//p有指向
pr = h;//pr为空
h = p;//h为第一个结点
/*从这里已经开始进行递归了*/
p = h->link;//h指向下一个结点，即第二个结点
h->link = pr;//这是的pr已经不是空了，而是h,指向改变
}
first->link = h;/*这时的已经到达最后一个结点了，直接把头结点安上区即可*/
}
/这个函数的p是用来保存变量的，可以理解为他是一个先锋，冲的最快，然后把他的结点给h然后继续向前冲/
/回答一下const问题，允许对链表有改变的不用const,不允许的用const/
#endif
#include
#include “LinkedList.h”
using namespace std;
int main() {
/*List<int> list;
list.input(-1, INR);
int x;
int m=list.getData(3,x);
cout << m;*/
List<int> list;
list.input(-1, INR);
cout << "The initial list in the file is:\n" << list << endl;
list.Inverse();
cout << "Inverse the list, then the list is:\n" << list << endl;
cout << "========================================\n";
int i, elem;
cout << "Test the Insert, Remove and Search function:\n";
cout << "Each test will terminate by an invaid input.";
cout << "\n----------------------------------------\n";
cout << "1. Test the Insert(int i, T &elem):\n";
while (1) {
cout << "Input the index i and data elem to insert: ";
cin >> i >> elem;
if (!cin) {
cin.clear();
cin.ignore(100, '\n');
break;
}
if (i < 0) break;
if (list.Insert(i, elem)) cout << "Insert successful!\n";
else cout << "Insert failed!\n";
}
cout << "\nAfter inserted\n" << list << endl;
cout << "----------------------------------------\n";
cout << "2. Test the Remove(int i, T &elem):\n";
while (1) {
cout << "Input the index i in which you want to remove: ";
cin >> i;
if (!cin) {
cin.clear();
cin.ignore(100, '\n');
break;
}
if (i < 0) break;
if (list.Remove(i, elem)) cout << "The element " << elem << " has been removed!\n";
else cout << "Remove failed!\n";
}
cout << "\nAfter removed\n" << list << endl;
cout << "----------------------------------------\n";
cout << "3. Test the Search(T &elem):\n";
while (1) {
cout << "Input the element you want to search: ";
cin >> elem;
if (!cin) {
cin.clear();
cin.ignore(100, '\n');
break;
}
if (elem < 0) break;
LinkNode<int>* p = list.Search(elem);
if (p) cout << "The element " << elem << " is in the list.\n";
else cout << "The element is not exist!\n";
}
cout << "\n----------------------------------------\n";
cout << "End test!" << endl;
return 0;
}
|