淄博网站开发招聘搜狗站长工具
单向链表 link list
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
实现类cpp intSLList.cpp
头部插入节点 head 和 tail 仅仅是保存了 一个(节点)存储的地址
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| \ |
双向向链表 link list 节点同时包含 指向前驱节点的指针 也包含 指向后继节点的指针
双向向链表
跳跃链表
跳跃链表
标准库中的链表 list #include
//一些成员函数assign(iterator first, iterator last) 删除所有节点，在first到last插入元素assign(size_type n, el) 删除所有节点，向其中插入n个elback() 尾节点元素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 emptylist<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 emptyprintList(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 emptylst3.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 emptylst3.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;
}