c++ 中的链表
2019-01-11 16:35:05 ypj131 阅读数 84

Lists将元素按顺序储存在链表中. 与 向量(vectors)相比, 它允许快速的插入和删除,但是随机访问却比较慢.


assign() 给list赋值 
back() 返回最后一个元素 
begin() 返回指向第一个元素的迭代器 
clear() 删除所有元素 
empty() 如果list是空的则返回true 
end() 返回末尾的迭代器 
erase() 删除一个元素 
front() 返回第一个元素 
get_allocator() 返回list的配置器 
insert() 插入一个元素到list中 
max_size() 返回list能容纳的最大元素数量 
merge() 合并两个list 
pop_back() 删除最后一个元素 
pop_front() 删除第一个元素 
push_back() 在list的末尾添加一个元素 
push_front() 在list的头部添加一个元素 
rbegin() 返回指向第一个元素的逆向迭代器 
remove() 从list删除元素 
remove_if() 按指定条件删除元素 
rend() 指向list末尾的逆向迭代器 
resize() 改变list的大小 
reverse() 把list的元素倒转 
size() 返回list中的元素个数 
sort() 给list排序 
splice() 合并两个list 
swap() 交换两个list 
unique() 删除list中重复的元素

 

2019-03-12 20:26:13 weixin_43293737 阅读数 19

一、List定义:
List是stl实现的双向链表,与向量(vectors)相比, 它允许快速的插入和删除,但是随机访问却比较慢。使用时需要添加头文件
#include
二、List定义和初始化:

list<int> lst1;           //创建空list
list<int> lst2(5);       //创建含有5个元素的list
list<int> lst4(lst2);    //使用lst2初始化lst4

三、List常用操作函数:
增:
Lst1.insert() 插入一个元素到list中
Lst1.push_back() 在list的末尾添加一个元素 ;Lst1.push_front() 在list的头部添加一个元素
删:
Lst1.clear() 删除所有元素
Lst1.erase() 删除一个元素
Lst1.pop_back() 删除最后一个元素 ;Lst1.pop_front() 删除第一个元素
Lst1.remove() 从list删除指定元素 ;Lst1.remove_if() 按指定条件删除元素
Lst1.unique() 删除list中重复的元素
改:
Lst1.resize() 改变list的大小
Lst1.reverse() 把list的元素倒转
查:
Lst1.front() 返回第一个元素 ;Lst1.back() 返回最后一个元素
Lst1.empty() 如果list是空的则返回true
Lst1.max_size() 返回list能容纳的最大元素数量 ;Lst1.size() 返回list中的元素个数

其他的一些操作:
Lst1.assign() 给list赋值
Lst1.get_allocator() 返回list的配置器
Lst1.merge() 合并两个list
Lst1.begin() 返回指向第一个元素的迭代器 ;Lst1.end() 返回末尾的迭代器
Lst1.rbegin() 返回指向第一个元素的逆向迭代器 ;Lst1.rend() 指向list末尾的逆向迭代器
Lst1.sort() 给list排序
Lst1.splice() 合并两个list
Lst1.swap() 交换两个list

list的基本操作

#include <iostream>
using namespace std;
#include "list"//列表集合
void main71()
{
	list<int> l;
	cout << "list的大小:" << l.size() << endl;
	for (int i = 0; i<10; i++)
	{
		l.push_back(i); //尾部插入元素 尾插法
	}
	cout << "list的大小:" << l.size() << endl;

	list<int>::iterator it = l.begin();

	while (it != l.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	//list不能随机访问容器中的值,即不能it+5这样的操作。只能一个一个的走it++
	//0	 1	2	3	4	5
	//              ▲
	it = l.begin();
	it++;
	it++;
	it++;
	//it = it + 5;  //不支持随机的访问容器

	l.insert(it, 100); //请问100插入在链表哪个位置
	for (list<int>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}

	//结论1 链表的结点index 序号是从0号位置开始
	//		在3号位置插入元素, 让原来的3号位置变成4号位置  原来的4号位置变成5号位置
	//左开右闭的形式 [0,3)

}
//list 删除
void main72()
{
	list<int> l;
	cout << "list的大小:" << l.size() << endl;
	for (int i = 0; i<10; i++)
	{
		l.push_back(i); //尾部插入元素 尾插法
	}
	cout << "list的大小:" << l.size() << endl;

	for (list<int>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;

	//0	 1	2	3	4	5
	//          ▲
	list<int>::iterator it1 = l.begin();
	list<int>::iterator it2 = l.begin();
	it2++;
	it2++;
	it2++;

	l.erase(it1, it2);//要想删除一个区间段。只能用指针++一步一步的指向那个末尾位置,不能直接l.begin()+3

	for (list<int>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;

	l.insert(l.begin(), 100);
	l.insert(l.begin(), 100);
	l.insert(l.begin(), 100);

	l.erase(l.begin()); //删除该位置的元素
	l.remove(100); //移除所有100元素的值  remove
	for (list<int>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
2009-04-20 21:37:00 panyunlai 阅读数 564

#include<fstream.h>
#include<process.h>
#include<iomanip.h>
#include<string.h>
const char*file_name="stuinfo.txt";

class Student
{
public:
Student();
~Student();
void add_info();//添加学生信息
void del_info();//删除学生信息
void search_info_name();//通过学生名字来查找信息
void search_info_Snum();//通过学号来查找信息
void out_all_info();//输出所有学生的信息
void creat_file();//创建文件,学生的信息保存在文件里,即使退出了程序,下次运行还可以找到学生的信息
int get_info();//从文件中获取学生的信息
int search_file();//判断是否存在一个保存学生信息的文件
protected:
char name[10];//学生名字最长为10个字符
long Snum;//学号是长整行
int Chinese,English,Math,Computer;//语文 英语 数学 计算机 共四门课
Student *head,*next;//创建链表使用的指针
};

/**
*构造函数,用来创建对象同时初始化相关指针变量
*/
Student::Student()
{
head=NULL;
next=NULL;
}

/**
*判断是否存在一个保存学生信息的文件
*/
int Student::search_file()
{
ifstream input_file;
input_file.open(file_name);
if(!input_file)//不存在文件
return 0;
else
input_file.close();//存在文件
return 1;
}

/**
*从文件中获取学生的信息
*/
int Student::get_info()
{
Student *temp,*loop;
temp=new Student();
loop=new Student();
ifstream out_file;
out_file.open(file_name,ios::beg);//打开文件,设置读指针在文件的开头
if(!out_file)//打开文件失败
{
cout<<"Fail to get information from the file!";
cout<<"/nPress any key to exit.";
cin.get();
exit(0);//结束程序
}
while(!out_file.eof())//循环读文件,直到读到了文件的末尾
{
//文件的结构是:文件的一行就是一个学生的信息, 从左到右是:学号 姓名 语文 英语 数学 计算机
//这些信息可以在本程序提供的功能生成并保存到文件里
out_file>>(temp->Snum)>>(temp->name)>>(temp->Chinese)>>(temp->English)>>(temp->Math)>>(temp->Computer);
if(temp->Snum==0) break;
//使用链表把学生的信息保存到内存中
if(head==NULL) head=temp;
else
{
if(head->Snum>temp->Snum)
{
temp->next=head;
head=temp;
}
else
{
loop=head;
while(loop->next!=NULL)
{
if(loop->next->Snum>temp->Snum)
{
temp->next=loop->next;
loop->next=temp;
break;
}
loop=loop->next;
}
if(loop->next==NULL)
{
loop->next=temp;
temp->next=NULL;
}
}
}
temp=new Student;
loop=new Student;
}
out_file.close();//关闭文件
if(head==NULL) return 0;
else return 1;
}

/**
*创建文件,可以增加学生的信息
*/
void Student::creat_file()
{
Student *temp,*loop;
temp=new Student;
loop=new Student;
ofstream creat_file;
creat_file.open(file_name,ios::beg);
if(!creat_file)
{
cout<<"Fail to creat stdent information file!";
cout<<"/nPress any key to exit.";
cin.get();
exit(0);
}
cout<<"-----------------------------------------------------------"<<endl;
cout<<"Now creat file of student information."<<endl;
cout<<"Input the number of the student (0 to end):";
cin>>temp->Snum;//输入学号
while(temp->Snum!=0)//学号不为0
{
cout<<"Input the name of the student:";
cin>>temp->name;//姓名
cout<<"Input the score of Chinese:";
cin>>temp->Chinese;//语文
cout<<"Input the score of English:";
cin>>temp->English;//英语
cout<<"Input the score of Math:";
cin>>temp->Math;//数学
cout<<"Input the score of Computer Science:";
cin>>temp->Computer;//计算机
creat_file<<temp->Snum<<" "<<temp->name<<" "<<temp->Chinese<<" "<<temp->English<<" "<<temp->Math<<" "<<temp->Computer<<endl;
temp=new Student;
loop=new Student;
cout<<"/n/nInput the number of the student (0 to end):";
cin>>temp->Snum;//输入学号
}
creat_file<<0;
creat_file.close();
}
/**
*输出所有学生的信息
*/
void Student::out_all_info()
{
Student*temp;
temp=new Student;
cout<<"-----------------------------------------------------------"<<endl;
cout<<"The flowing is the information of the students."<<endl<<endl;
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl;
temp=head;
while(temp!=NULL)//循环读链表,输出所有学生的信息
{
cout<<(temp->Snum)<<setw(9)<<(temp->name)<<setw(9)<<(temp->Chinese)<<setw(9)<<(temp->English)
<<setw(9)<<(temp->Math)<<setw(12)<<(temp->Computer)<<endl;
temp=temp->next;
}
}
/**
*通过姓名查找信息
*/
void Student::search_info_name()
{
Student *temp;
char name[10];
temp=new Student;
cout<<"-----------------------------------------------------------"<<endl;
cout<<"Input the name of the student you want to search:";
cin>>name;//输入姓名
temp=head;
while(temp!=NULL&&strcmp(temp->name,name)!=0)//在链表中逐个的比较姓名
temp=temp->next;
if(temp==NULL)//没有找到信息,就是说找不到需要查找姓名的学生的信息
cout<<"Sorry,no such student of the name you input!"<<endl;
else//输出学生的信息
{
cout<<"The flowing is the information of the student "<<name<<endl;
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl;
cout<<(temp->Snum)<<setw(9)<<(temp->name)<<setw(9)<<(temp->Chinese)<<setw(9)<<(temp->English)
<<setw(9)<<(temp->Math)<<setw(12)<<(temp->Computer)<<endl;
}
}
/**
*通过学号查找信息
*/
void Student::search_info_Snum()
{
Student*temp;
long num;
temp=new Student;
cout<<"---------------------------------------------------------"<<endl;
cout<<"Input the number of the student you want to search:";
cin>>num;//输入学号
temp=head;
while(temp!=NULL&&temp->Snum!=num)//比较学号
temp=temp->next;
if(temp==NULL)//没有找到信息
cout<<"Sorry,no such student of the number you input!"<<endl;
else//输出信息
{
cout<<"The flowing is the information of the student "<<num<<endl;
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl;
cout<<(temp->Snum)<<setw(9)<<(temp->name)<<setw(9)<<(temp->Chinese)<<setw(9)<<(temp->English)
<<setw(9)<<(temp->Math)<<setw(12)<<(temp->Computer)<<endl;
}
}
/**
*增加学生的信息
*/
void Student::add_info()
{
Student *temp,*loop,*loop1;
temp=new Student;
loop=new Student;
loop1=new Student;
cout<<"-----------------------------------------------------------"<<endl;
cout<<"Now add information of student."<<endl;
cout<<"Input the number of the student (0 to end):";
cin>>temp->Snum;//输入学号
loop1=temp;
while(temp->Snum!=0)//学号不为0
{
cout<<"Input the name of the student:";
cin>>temp->name;//姓名
cout<<"Input the score of Chinese:";
cin>>temp->Chinese;//语文
cout<<"Input the score of English:";
cin>>temp->English;//英语
cout<<"Input the score of Math:";
cin>>temp->Math;//数学
cout<<"Input the score of Computer Science:";
cin>>temp->Computer;//计算机
if(head==NULL) head=temp;//将信息添加到链表中
else
{
if(head->Snum>temp->Snum)
{
temp->next=head;
head=temp;
}
else
{
loop=head;
while(loop->next!=NULL)
{
if(loop->next->Snum>temp->Snum)
{
temp->next=loop->next;
loop->next=temp;
break;
}
loop=loop->next;
}
if(loop->next==NULL)
{
loop->next=temp;
temp->next=NULL;
}
}
}
temp=new Student;
loop=new Student;
cout<<"/n/nInput the number of the student (0 to end):";
cin>>temp->Snum;
}
cout<<"/nThe information you input is the flowing."<<endl;
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl;
while(loop1!=NULL)
{
cout<<(loop1->Snum)<<setw(9)<<(loop1->name)<<setw(9)<<(loop1->Chinese)<<setw(9)<<(loop1->English)
<<setw(9)<<(loop1->Math)<<setw(12)<<(loop1->Computer)<<endl;
loop1=loop1->next;
}


}
/**
*通过学号删除信息
*/
void Student::del_info()
{
Student *temp,*loop1,*loop2;
long snum;
temp=new Student;
loop1=new Student;
loop2=new Student;
cout<<"----------------------------------------------------------"<<endl;
cout<<"Input the number of the student you want to delete:";
cin>>snum;//输入学号
temp=head;
while(temp!=NULL&&temp->Snum!=snum)//通过学号查找信息
{
loop1=temp;
temp=temp->next;
}
if(temp==NULL)//没有相应学号的学生信息
cout<<"Sorry,no such student of the number you input!"<<endl;
else
{
loop1->next=temp->next;//跳过链表的一个节点temp
cout<<"The information you delete is the flowing."<<endl;
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl;
cout<<(temp->Snum)<<setw(9)<<(temp->name)<<setw(9)<<(temp->Chinese)<<setw(9)<<(temp->English)
<<setw(9)<<(temp->Math)<<setw(12)<<(temp->Computer)<<endl;
if(temp->Snum==head->Snum) head=head->next;
delete temp;//删除节点
}
}
/**
*析构函数,只用程序的正常结束才会执行改函数,并且把学生的信息保存到文件中
*/
Student::~Student()
{
Student*temp;
temp=new Student;
ofstream write_file;
write_file.open(file_name,ios::beg);
if(!write_file)
{
cout<<"Fail to write the information to the file!"<<endl;
cout<<"Press any key to exit.";
cin.get();
exit(0);
}
temp=head;
while(temp!=NULL)
{
write_file<<temp->Snum<<" "<<temp->name<<" "<<temp->Chinese<<" "<<temp->English<<" "<<temp->Math<<" "<<temp->Computer<<endl;
temp=temp->next;
}
write_file<<0;
write_file.close();
}
/**
*主函数,主要提供一些菜单选项
*/
void main()
{
char select;
int selection;
Student student;
cout<<"/n########################################################"<<endl;
if(student.search_file()==0)
{
cout<<"There is no file of student information."<<endl;
cout<<"Do you want to creat it?(Y/N):";
cin>>select;
if(select=='Y'||select=='y')
student.creat_file();
else
exit(0);
}
if(student.get_info()==0)
{
cout<<"There is no information in the file"<<endl;
cout<<"Do you want to add information to the file?(Y/N):";
cin>>select;
if(select=='y'||select=='Y')
student.add_info();
else exit(0);
}
cout<<"/n/n##########################################################"<<endl;
cout<<"Information of students.Selections are flowing."<<endl;
cout<<"Input number 1 to search information by name."<<endl;
cout<<"Input number 2 to search information by number."<<endl;
cout<<"Input number 3 to add nuw information to the file."<<endl;
cout<<"Input number 4 to delete information from the file."<<endl;
cout<<"Input number 5 to view all the students' information."<<endl;
cout<<"Input other numbers to exit."<<endl;
cout<<"Input your selection please:";
cin>>selection;
while(selection>=1&&selection<=5)
{
if(selection==1) student.search_info_name();
if(selection==2) student.search_info_Snum();
if(selection==3) student.add_info();
if(selection==4) student.del_info();
if(selection==5) student.out_all_info();
cout<<"/n/n########################################################"<<endl;
cout<<"Information of students.Selections are flowing."<<endl;
cout<<"Input number 1 to search information by name."<<endl;
cout<<"Input number 2 to search information by number."<<endl;
cout<<"Input number 3 to add nuw information to the file."<<endl;
cout<<"Input number 4 to delete information from the file."<<endl;
cout<<"Input number 5 to view all the students' information."<<endl;
cout<<"Input other numbers to exit."<<endl;
cout<<"Input your selection please:";
cin>>selection;
}
}

2017-05-24 19:57:38 mir_age 阅读数 130

为什么要使用链表

我们知道,数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元,相同数组的位置和距离都是固定的,也就是说,任何一个数组元素的地址都可一个简单的公式计算出来,因此这种结构可以有效的对数组元素进行随机访问。但若对数组元素进行插入和删除操作,则会引起大量数据的移动,从而使简单的数据处理变得非常复杂,低效。
为了能有效地解决这些问题,一种称为“链表”的数据结构得到了广泛应用。

什么是链表

链表是一种动态数据结构,他的特点是用一组任意的存储单元(可以是连续的,也可以是不连续的)存放数据元素。
链表中每一个元素称为节点,每一个节点都是由数据域和指针域组成的,每个结点中的指针域指向下一个结点。链表的第一个节点称为表头。Head是头指针,表示链表的开始,用来指向第一个节点,而最后一个指针的指针域为NULL(空地址),表示链表的结束。
可以看出链表结构必须利用指针才能实现,即一个节点中必须包含一个指针变量,用来存放下一个节点的地址。
实际上,链表中的每个节点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表,这是最简单的链表结构。
再c++中实现一个单链表结构比较简单。例如,可定义单链表结构的最简单形式如下

struct Node
{
int Data;
Node *link;
};
typedef Node* NodePter;

首先构造链表的开头部分
NodePtr head;
用new操作符创建动态变量,它将成为链表的第一个节点
head = new Node;
然后,为新节点的成员变量赋值:
head -> data = 3;
head -> link = Null;

在表头插入节点

struct Node
{
int Data;
Node *link;
};
typedef Node* NodePter;

void head_insert(NodePtr& head, int the_number);

void head_insert(NodePtr& head, int the_number)
{
    NodePtr temp_ptr;
    temp_ptr = new Node; //新建由temp_ptr指向的动态变量
    temp_ptr->data = the_number;//将数据放到新节点中
    temp_ptr->link = head;//使新节点的link成员指向原始列表的head节点
    head = temp_ptr;//使head指针指向新节点
}

要考虑到列表不包含任何内容的可能性。什么都没有的列表称为空列表。如果指针变量head本应指向链表的表头节点,但你希望指出链表为空,可以令:
head = NULL;

搜索链表

struct Node
{
int Data;
Node *link;
};
typedef Node* NodePter;

NodePtr search(NodePtr head, int target);

//使用cstddef:
NodePtr search(NodePtr head, int target)
{
    NodePtr here = head;
    if (here == NULL)    //处理空列表
    {
        retrun NUll;
    }
    else
    {
        while(here->data != target && here->link != NULL)
            here = here->link;
        if (here->data == target)
            return here;
        else
            return NULL;
    ]
}

在列表中插入和删除节点

插入

struct Node
{
int Data;
Node *link;
};
typedef Node* NodePter;

void insert(NodePtr after_me, int the_number);
//after_me指向链表中的某一个节点

void insert(NodePtr after_me, int the_number)
{
    NodePtr temp_ptr;
    temp_ptr = new Node;
    temp_ptr->data = the_number;
    temp_ptr->link = after_me->link;
    after_me->link = temp_ptr;
}

删除
before->link = discard->link;
delete discard;

链表的变体

双链表

struct Node
{
int Data;
Node *forward_link;
Node *back_link;
};
typedef Node* NodePter;

树是特殊的数据结构,具体的说,在树中可沿着某个路径跟随链接,从顶部(根)节点抵达任何节点。注意,树中没有回路。
每个节点都有两个链接指向其他节点(或为NULL)。这种形式的树称为二叉树。
树不是链表,但采用和链表相似的方法使用链接(指针)。在二叉树中,节点类型的定义在本质上等同于双链表的节点类型定义。
二叉树能高效率的存储和检索数据,留作以后学习。

类构成的链表实战

1.定义Node类的接口文件

//头文件Node.h
//这是一个节点类的接口
namespace linkedlistofclasses
{
    class Node
    {
    public:
        Node();
        Node(int value, Node *next);
        //初始化节点的构造函数
        int getData() const;
        //检索这个节点的值
        Node *getLink() const;
        //检索链表的下一个节点
        void setData(int value);

        void setLink(Node *next);

    private:
        int data;
        Node *link;
    };
    typedef Node* NodePtr;
}

2.Node类的实现文件

#include <iostream>
#include "Node.h"

namespace linkedlistofclasses
{
    Node::Node() : data(0), link(NULL)
    {
        //有意留空
    }
    Node::Node(int value, Node *next) : data(value), link(next)
    {
        //有意留空
    }

    int Node::getData() const
    {
        return data;
    }
    Node* Node::getLink() const
    {
        return link;
    }
    void Node::setData(int value)
    {
        data = value;
    }
    void Node::setLink(Node *next)
    {
        link = next;
    }
}

3.使用Node类的程序

#include <iostream>
#include "Node.h"

using namespace std;
using namespace linkedlistofclasses;

void head_insert(NodePtr &head, int the_number)
{
    NodePtr temp_ptr;
    temp_ptr = new Node(the_number, head);
    head = temp_ptr;
}

int main(){
    NodePtr head, tmp;

    head = new Node(0, NULL);
    for (int i = 1; i < 5; i++)
    {
        head_insert(head, i);
    }
    tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->getData() << endl;
        tmp = tmp->getLink();
    }
    //退出程序前删除链表中的所有节点
    tmp = head;
    while (tmp != NULL)
    {
        NodePtr nodeToDelete = tmp;
        tmp = tmp->getLink();
        delete nodeToDelete;
    }
    return 0;
}

至此,完成对链表的初步学习

2016-11-26 11:56:14 qq_15015129 阅读数 388

链表基本操作

  • 生成链表
  • 插入结点
  • 查找结点
  • 删除结点
  • 遍历链表
  • 清空链表
//
//  test.h
//  XCODE
//
//  Created by vassago 
//  

#ifndef Node_h
#define Node_h
//类模板的定义
template <class T>
class Node {
private:
    Node<T> *next;  //指向后继结点的指针
public:
    T data; //数据域
    Node (const T &data, Node<T> *next = 0);    //构造函数
    void insertAfter(Node<T> *p);   //在本结点之后插入一个同类结点p
    Node<T> *deleteAfter(); //删除本结点的后继结点,并返回其地址
    Node<T> *nextNode();            //获取后继结点的地址
    const Node<T> *nextNode() const;     //获取后继结点的地址
};

//类的实现部分
//构造函数,初始化数据和指针成员
template <class T>
Node<T>::Node(const T& data, Node<T> *next ) : data(data), next(next) { }
//返回后继结点的指针
template <class T>
Node<T> *Node<T>::nextNode() {
    return next;
}
//返回后继结点的指针
template <class T>
const Node<T> *Node<T>::nextNode() const {
    return next;
}
//在当前结点之后插入一个结点p
template <class T>
void Node<T>::insertAfter(Node<T> *p) {
    p->next = next; //p结点指针域指向当前结点的后继结点
    next = p;    //当前结点的指针域指向p
}
//删除当前结点的后继结点,并返回其地址
template <class T> Node<T> *Node<T>::deleteAfter() {
    Node<T> *tempPtr = next;//将欲删除的结点地址存储到tempPtr中
    if (next == 0)  //如果当前结点没有后继结点,则返回空指针
        return 0;
    next = tempPtr->next;//使当前结点的指针域指向tempPtr的后继结点
    return tempPtr;         //返回被删除的结点的地址
}

#endif /* Node_h */
#include<iostream>
#include "Node.h"
using namespace std;
typedef long long LL;
template<typename T>
class LinkedList {
private:
    //数据成员:
    Node<T> *front, *rear;  //表头和表尾指针
    Node<T> *prevPtr, *currPtr;   //记录表当前遍历位置的指针,由插入和删除操作更新
    int size;   //表中的元素个数
    int position;   //当前元素在表中的位置序号。由函数reset使用

    //函数成员:
    //生成新结点,数据域为item,指针域为ptrNext
    Node<T> *newNode(const T &item,Node<T> *ptrNext=NULL);

    //释放结点
    void freeNode(Node<T> *p);

    //将链表L 拷贝到当前表(假设当前表为空)。
    //被拷贝构造函数、operator = 调用
    void copy(const LinkedList<T>& L);

public:
    LinkedList();   //构造函数
    LinkedList(const LinkedList<T> &L);  //拷贝构造函数
    ~LinkedList();  //析构函数
    LinkedList<T> & operator = (const LinkedList<T> &L); //重载赋值运算符

    int getSize() const;    //返回链表中元素个数
    bool isEmpty() const;   //链表是否为空

    void reset(int pos = 0);//初始化游标的位置
    void next();    //使游标移动到下一个结点
    bool endOfList() const; //游标是否到了链尾
    int currentPosition() const;    //返回游标当前的位置

    void insertFront(const T &item);    //在表头插入结点
    void insertRear(const T &item);     //在表尾添加结点
    void insertAt(const T &item);       //在当前结点之前插入结点
    void insertAfter(const T &item);    //在当前结点之后插入结点

    T deleteFront();    //删除头结点
    void deleteCurrent();   //删除当前结点

    T& data();              //返回对当前结点成员数据的引用
    const T& data() const;   //返回对当前结点成员数据的常引用

    //清空链表:释放所有结点的内存空间。被析构函数、operator= 调用
    void clear();
};

template <class T> //生成新结点
Node<T> *LinkedList<T>::newNode(const T& item, Node<T>* ptrNext)
{
    Node<T> *p;
    p = new Node<T>(item, ptrNext);
    if (p == NULL)
    {
        cout << "Memory allocation failure!\n";
        exit(1);
    }
    return p;
}

template <class T>
void LinkedList<T>::freeNode(Node<T> *p) //释放结点
{
    delete p;
}

template <class T>
void LinkedList<T>::copy(const LinkedList<T>& L) //链表复制函数
{
    Node<T> *p = L.front;   //P用来遍历L
    int pos;
    while (p != NULL)   //将L中的每一个元素插入到当前链表最后
    {
        insertRear(p->data);
        p = p->nextNode();
    }
    if (position == -1) //如果链表空,返回
        return;
    //在新链表中重新设置prevPtr和currPtr
    prevPtr = NULL;
    currPtr = front;
    for (pos = 0; pos != position; pos++)
    {
        prevPtr = currPtr;
        currPtr = currPtr->nextNode();
    }
}

template <class T>  //构造一个新链表,将有关指针设置为空,size为0,position为-1
LinkedList<T>::LinkedList() : front(NULL), rear(NULL),
prevPtr(NULL), currPtr(NULL), size(0), position(-1)
{}

template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L)  //拷贝构造函数
{
    front = rear = NULL;
    prevPtr = currPtr = NULL;
    size = 0;
    position = -1;
    copy(L);
}

template <class T>
LinkedList<T>::~LinkedList()    //析构函数
{
    clear();
}

template <class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)//重载"="
{
    if (this == &L) // 不能将链表赋值给它自身
        return *this;
    clear();
    copy(L);
    return *this;
}

template <class T>
int LinkedList<T>::getSize() const  //返回链表大小的函数
{
    return size;
}

template <class T>
bool LinkedList<T>::isEmpty() const //判断链表为空否
{
    return size == 0;
}

template <class T>
void LinkedList<T>::reset(int pos)  //将链表当前位置设置为pos
{
    int startPos;
    if (front == NULL)  // 如果链表为空,返回
        return;
    if (pos < 0 || pos > size - 1)  // 如果指定位置不合法,中止程序
    {
        std::cerr << "Reset: Invalid list position: " << pos << endl;
        return;
    }
    // 设置与遍历链表有关的成员
    if (pos == 0)   // 如果pos为0,将指针重新设置到表头
    {
        prevPtr = NULL;
        currPtr = front;
        position = 0;
    }
    else    // 重新设置 currPtr, prevPtr, 和 position
    {
        currPtr = front->nextNode();
        prevPtr = front;
        startPos = 1;
        for (position = startPos; position != pos; position++)
        {
            prevPtr = currPtr;
            currPtr = currPtr->nextNode();
        }
    }
}

template <class T>
void LinkedList<T>::next()  //将prevPtr和currPtr向前移动一个结点
{
    if (currPtr != NULL)
    {
        prevPtr = currPtr;
        currPtr = currPtr->nextNode();
        position++;
    }
}

template <class T>
bool LinkedList<T>::endOfList() const   // 判断是否已达表尾
{
    return currPtr == NULL;
}

template <class T>
int LinkedList<T>::currentPosition() const  // 返回当前结点的位置
{
    return position;
}

template <class T>
void LinkedList<T>::insertFront(const T& item)   // 将item插入在表头
{
    if (front != NULL)  // 如果链表不空则调用Reset
        reset();
    insertAt(item); // 在表头插入
}

template <class T>
void LinkedList<T>::insertRear(const T& item)   // 在表尾插入结点
{
    Node<T> *nNode;
    prevPtr = rear;
    nNode = newNode(item);  // 创建新结点
    if (rear == NULL)   // 如果表空则插入在表头
        front = rear = nNode;
    else
    {
        rear->insertAfter(nNode);
        rear = nNode;
    }
    currPtr = rear;
    position = size;
    size++;
}

template <class T>
void LinkedList<T>::insertAt(const T& item) // 将item插入在链表当前位置
{
    Node<T> *nNode;
    if (prevPtr == NULL)    // 插入在链表头,包括将结点插入到空表中
    {
        nNode = newNode(item, front);
        front = nNode;
    }
    else    // 插入到链表之中. 将结点置于prevPtr之后
    {
        nNode = newNode(item);
        prevPtr->insertAfter(nNode);
    }
    if (prevPtr == rear)    //正在向空表中插入,或者是插入到非空表的表尾
    {
        rear = nNode;   //更新rear
        position = size;    //更新position
    }
    currPtr = nNode;    //更新currPtr
    size++; //使size增值
}

template <class T>
void LinkedList<T>::insertAfter(const T& item)  // 将item 插入到链表当前位置之后
{
    Node<T> *p;
    p = newNode(item);
    if (front == NULL)   // 向空表中插入
    {
        front = currPtr = rear = p;
        position = 0;
    }
    else    // 插入到最后一个结点之后
    {
        if (currPtr == NULL)
            currPtr = prevPtr;
        currPtr->insertAfter(p);
        if (currPtr == rear)
        {
            rear = p;
            position = size;
        }
        else
            position++;
        prevPtr = currPtr;
        currPtr = p;
    }
    size++;              // 使链表长度增值
}

template <class T>
T LinkedList<T>::deleteFront()  // 删除表头结点
{
    T item;
    reset();
    if (front == NULL)
    {
        cerr << "Invalid deletion!" << endl;
        exit(1);
    }
    item = currPtr->data;
    deleteCurrent();
    return item;
}

template <class T>
void LinkedList<T>::deleteCurrent() // 删除链表当前位置的结点
{
    Node<T> *p;
    if (currPtr == NULL)    // 如果表空或达到表尾则出错
    {
        cerr << "Invalid deletion!" << endl;
        exit(1);
    }
    if (prevPtr == NULL)    // 删除将发生在表头或链表之中
    {
        p = front;  // 保存头结点地址
        front = front->nextNode();  //将其从链表中分离
    }
    else    //分离prevPtr之后的一个内部结点,保存其地址
        p = prevPtr->deleteAfter();

    if (p == rear)  // 如果表尾结点被删除
    {
        rear = prevPtr; //新的表尾是prevPtr
        position--; //position自减
    }
    currPtr = p->nextNode();    // 使currPtr越过被删除的结点
    freeNode(p);    // 释放结点,并
    size--; //使链表长度自减
}

template <class T>
T& LinkedList<T>::data()    //返回一个当前结点数值的引用
{
    if (size == 0 || currPtr == NULL)   // 如果链表为空或已经完成遍历则出错
    {
        cerr << "Data: invalid reference!" << endl;
        exit(1);
    }
    return currPtr->data;
}

template <class T>
void LinkedList<T>::clear() //清空链表
{
    Node<T> *currPosition, *nextPosition;
    currPosition = front;
    while (currPosition != NULL)
    {
        nextPosition = currPosition->nextNode(); //取得下一结点的地址
        freeNode(currPosition); //删除当前结点
        currPosition = nextPosition;    //当前指针移动到下一结点
    }
    front = rear = NULL;
    prevPtr = currPtr = NULL;
    size = 0;
    position = -1;
}
//test_main
int main()
{
    LinkedList<int> list;
    list.insertAt(1);
    list.insertAfter(2);
    list.insertRear(3);
    list.insertFront(4);
    while(!list.isEmpty()){
        cout<<list.data()<<endl;
        list.deleteCurrent();
    }
    return 0;
}

C++ 链表

阅读数 687

在开发中比较常用,但是STL的list又很复杂,自己写了个简单的list,3个函数,够自己平时用了。#ifndef_WZY_LIST_H_#define_WZY_LIST_H_#includetemplateclass_Node{public: T_data; _Node*_link;};templateclass_Lis

博文 来自: wei801004

C++链表

阅读数 85

1#include2#include3usingnamespacestd;4constintMAX_NUM=5;56/**7*节点类8*/9template10classNode{11public:12Node(Tdata,Node*next=NULL,No

博文 来自: qq_33215972

链表 C++

阅读数 180

2016.8.22C++第十四天链表定义:物理单元存取不连续的数据结构,数据元素之间通过‘指针’进行连接(链表中每一个元素->节点)节点组成;1⃣️数据 2⃣️指针(因为元素间不连续,通过指针进行连接)注意:没有下表符重载,可以在任意位置操作,从头结点遍历到尾节点1⃣️单向链表2⃣️双向链表3⃣️循环链表#include#include#incl

博文 来自: zhanghow

c++ 链表

阅读数 597

一、问题描述1、题目内容:集合的并、交和差运算编写一个能演示执行集合的并、交和差运算的程序。2、基本要求由用户输入两组整数分别作为两个集合的元素,由程序计算它们的交、并和差集,并将运算结果输出。3、测试数据测试数据为两组正整数,范围最好在0~35000之间。S1={3,5,6,9,12,27,35};S2={5,8,10,12,27,31,2,51,55,63};

博文 来自: zhandeen

c++链表

阅读数 247

带tail尾指针的写法:1#include02using namespace std;03class linklist{04private:05    clas

博文 来自: Autii
没有更多推荐了,返回首页