t数组的局限：编译期就需要知道大小； 内存连续，插入困难
// 链表节点类 包含一个信息 和指向下一个 节点的指针
clas IntLLNode{
public:
IntLLNode(){// 默认构造函数 没有info信息
nextPtr_ = 0;// 空指针
}
IntLLNode(int data, IntLLNode* in = 0){// 第二个构造函数
info_ = data;
nextPtr_ = in;
}
public:
int info_; // 包含一个信息 对用户很重要
IntLLNode* nextPtr_;// 指向下一个 节点的指针 用于将节点连接起来组成链表
}
// 定义一个 节点指针
IntLLNode* pt = new IntLLNode(10);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt
//
// [pt] ----> | 10 | 也就是 pt->info_ 也就是 (*pt).info_
// | \ | 也就是 pt->nextPtr_ 也就是 (*pt).nextPtr_
// 再定义一个节点
pt->nextPtr = new IntLLNode(30);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt->nextPtr_
//
// [pt] ----> | 10 |
// | | -----> | 30 | 也就是 pt->nextPtr_->info_
// | \ | 也就是 pt->nextPtr_->nextPtr_
// 再定义一个节点
pt->nextPtr_->nextPtr_ = new IntLLNode(50);
//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt->nextPtr_->nextPtr_
//
// [pt] ----> | 10 |
// | | -----> | 30 |
// | | ------> | 50 | 也就是 pt->nextPtr_->nextPtr_->info_
// | \ | 也就是 pt->nextPtr_->nextPtr_->nextPtr_
//************************ intSLList.h **************************
// 单链表 实现类
#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST
// 单个节点
// 定义一个 节点指针
// IntLLNode* pt = new IntLLNode(10);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt
//
// [pt] ----> | 10 | 也就是 pt->info_ 也就是 (*pt).info_
// | \ | 也就是 pt->nextPtr_ 也就是 (*pt).nextPtr_
class IntSLLNode {
public:
IntSLLNode() {// 默认构造函数 没有info信息
next = 0;// 空指针
}
IntSLLNode(int data, IntSLLNode *ptr = 0) {// 第二个构造函数
info = data;
next = ptr;
}
public:
int info; // 包含一个信息 对用户很重要
IntSLLNode *next; // 指向下一个 节点的指针 用于将节点连接起来组成链表
};
// 链表 类 保存了一个 头节点 和 一个尾节点
class IntSLList {
public:
IntSLList() {// 默认构造函数 这里定义和实现
head = tail = 0;// 节点 和 一个尾节点 指针赋值为 空
}
~IntSLList();// 默认析构函数 只有定义 实现在 cpp文件中
int isEmpty() {//为空链表是否
return head == 0;
}
void addToHead(int); // 从头部添加 节点
void addToTail(int); // 从尾部添加 节点
int deleteFromHead(); // 从头部删除 节点 并返回该节点的信息
int deleteFromTail(); // 从尾部删除 节点 并返回该节点的信息
void deleteNode(int);//删除
bool isInList(int) const;
void printAll() const;//打印所有的节点的信息
private:
IntSLLNode *head, *tail;// 保存了一个 头节点 和 一个尾节点
};
#endif
head ---> | 5 |
| | ---> | 7 |
| | ---> | 4 | <-------- tail
| |
新建一个节点
| 9 | head ---> | 5 |
| | | | ---> | 7 |
| | ---> | 4 | <-------- tail
| |
新节点指向 head 指向的地址 new IntSLLNode9, head);
| 9 | head ---> | 5 |
| | -------> | | ---> | 7 |
| | ---> | 4 | <-------- tail
原头结点指向新节点 head = new IntSLLNode(9,head);
head ---> | |
| 9 |
| | -------> | 5 |
| | ---> | 7 |
| | ---> | 4 | <-------- tail
| |
head ---> | 5 |
| | ---> | 7 |
| | ---> | 4 | <-------- tail
| |
尾部新建一个节点 new IntSLLNode(9);
head ---> | 5 |
| | ---> | 7 |
| | ---> | 4 | <-------- tail
| | | 9 |
| \ | tail指向的节点 指向这个新节点 tail->next = new IntSLLNode(9)
head ---> | 5 |
| | ---> | 7 |
| | ---> | 4 | <-------- tail
| | --------> | 9 |
| \ |
尾节点tail 指向新的 尾节点 tail = tail->next;
head ---> | 5 |
| | ---> | 7 |
| | ---> | 4 |
| | --------> | 9 | <-------- tail
| \ |
//一些成员函数
assign(iterator first, iterator last) 删除所有节点，在first到last插入元素
assign(size_type n, el) 删除所有节点，向其中插入n个el
back() 尾节点元素
front() 第一个节点元素
clear() 删除所有节点
empty() 判断是否为空
erase() 删除一个节点
insert() 插入一个元素
pop_back() 删除最后一个节点
pop_front() 删除第一个节点
push_back() 在表尾插入
push_front() 在表头插入
sort() 排序
swap() 与另一个链表互换
unique() 从有序链表中删除重复的元素
#include <iostream>
#include <list>//链表
#include <algorithm>// 算法
#include <deque>//队列
#include <functional>
using namespace std;
// 打印链表每一个元素
template<class T>
void printList(const list<T>& lst, char *s) {
cout << s << ": ";
for (typename list<T>::const_iterator i = lst.begin(); i != lst.end(); ++i)
cout << *i << ' ';
cout << endl;
}
int main() {
list<int> lst1;// 创建空链表
printList(lst1,"lst1"); // lst1 is empty
list<int> lst2(3,7);
printList(lst2,"lst2"); // lst2 = (7 7 7)
for (int j = 1; j <= 5; j++)// lst1 = (1 2 3 4 5)
lst1.push_back(j);//尾后插入元素
list<int>::iterator i1 = lst1.begin(), i2 = i1, i3;
i2++; i2++; i2++;
list<int> lst3(++i1,i2);
printList(lst3,"lst3"); // lst3 = (2 3)
list<int> lst4(lst1);
printList(lst4,"lst4"); // lst4 = (1 2 3 4 5)
i1 = lst4.begin();
lst4.splice(++i1,lst2);
printList(lst2,"lst2"); // lst2 is empty
printList(lst4,"lst4"); // lst4 = (1 7 7 7 2 3 4 5)
lst2 = lst1;
printList(lst2,"lst2"); // lst2 = (1 2 3 4 5)
i2 = lst2.begin();
lst4.splice(i1,lst2,++i2);
printList(lst2,"lst2"); // lst2 = (1 3 4 5)
printList(lst4,"lst4"); // lst4 = (1 7 7 7 2 2 3 4 5)
i2 = lst2.begin();
i3 = i2;
lst4.splice(i1,lst2,i2,++i3);
printList(lst2,"lst2"); // lst2 = (3 4 5)
printList(lst4,"lst4"); // lst4 = (1 7 7 7 2 1 2 3 4 5)
lst4.remove(1);
printList(lst4,"lst4"); // lst4 = (7 7 7 2 2 3 4 5)
lst4.sort();
printList(lst4,"lst4"); // lst4 = (2 2 3 4 5 7 7 7)
lst4.unique();
printList(lst4,"lst4"); // lst4 = (2 3 4 5 7)
lst1.merge(lst2);
printList(lst1,"lst1"); // lst1 = (1 2 3 3 4 4 5 5),
printList(lst2,"lst2"); // lst2 is empty
lst3.reverse();
printList(lst3,"lst3"); // lst3 = (3 2)
lst4.reverse();
printList(lst4,"lst4"); // lst4 = (7 5 4 3 2)
lst3.merge(lst4,greater<int>());
printList(lst3,"lst3"); // lst3 = (7 5 4 3 3 2 2)
printList(lst4,"lst4"); // lst4 is empty
lst3.remove_if(bind2nd(not_equal_to<int>(),3));
printList(lst3,"lst3"); // lst3 = (3 3)
lst3.unique(not_equal_to<int>());
printList(lst3,"lst3"); // lst3 = (3 3)
return 0;
}