3.1 单链表

 

1.单链表简介

   数组在编程语言中用的非常有用，但是属数组至少有两个缺点
 (1) 编译时就得知道数组的大小
 (2) 在计算机内存中是连续存储的，这就意味着在数组中插入或删除一个数据，就需要调整其他数据。
而使用链表结构就不存在这些问题
下图表示一个链表的结构及其构造过程。
 
上图所示的链表中的每个节点都是下面类定义（节点值为整数型）的一个实例：
这是一种C++面向对象的写法，在C语言中，我们习惯定义成结构体。
  1. classIntSLLNode{
  2. public:
  3. IntSLLNode(){//第一个构造函数初始化next指针为NULL
  4. next =0;
  5. }
  6. IntSLLNode(int i,IntSLLNode*in =0){//第二个构造函数设置两个成员数据的值
  7. info = i; next = in;
  8. }
  9. int info;
  10. IntSLLNode*next;//指向下一个节点，这个节点的类型与本节点相同,这里要定义成公有成员，以便实施链表的操作
  11. };
节点包含两个数椐成员： info 和 next，  info 成员用于对用户有用的存储， next 是用于连接链表节点对从而形成链表结构。
有了这个定义我们就可以构造上图所示的链表了：
IntSLLNode *p = new IntSLLNode(10);
p->next = new IntSLLNode(8);
p->next->next = new IntSLLNode(50);
这里仅定义了一个头指针p来访问数据，不是很方便，在实际操作中一般会定义两个指针或更多指针方便操作。

 

2.单链表操作

链表节点类型已经由类IntSLLNode定义好了，接下来就是定义一个类实施对链表的各种错作，单链表的操作无非是增删查改
定义下面的类IntSLList
  1. classIntSLList{
  2. public:
  3. IntSLList(){
  4. head = tail =0;
  5. }
  6. ~IntSLList();
  7. int isEmpty(){
  8. return head ==0;
  9. }
  10. void addToHead(int);
  11. void addToTail(int);
  12. int deleteFromHead();// delete the head and return its info;
  13. int deleteFromTail();// delete the tail and return its info;
  14. void deleteNode(int);
  15. bool isInList(int)const;
  16. void printAll()const;
  17. private:
  18. IntSLLNode*head,*tail;//两个私有成员变量，分别是指向单链表的头和尾的指针
  19. };

2.1 插入
（1）添加到链表开头
四步：
  • 创建一个空节点
  • 初始化节点值el
  • 添加新节点到链表最前面，并将新节点的next指向头节点，也就是head的当前值
  • 将head更新为指向新节点的指针
  1. voidIntSLList::addToHead(int el){
  2. head =newIntSLLNode(el,head);//一句话就完成了四步，这就是C++的魅力了
  3. if(tail ==0)
  4. tail = head;
  5. }
（2）添加到链表末尾
四步：
  • 创建一个空节点
  • 初始化节点值el，因为该节点要添加到链表的末尾，所以将新节点的next设置为NULL
  • 让原链表的尾节点的next指向新建的尾节点，这样就将新节点添加到了末尾
  • 将tail更新为指向新节点的指针
  1. voidIntSLList::addToTail(int el){
  2. if(tail !=0){// 先判断链表是否为空
  3. tail->next =newIntSLLNode(el);
  4. tail = tail->next;
  5. }
  6. else head = tail =newIntSLLNode(el);
  7. }
 
2.2 删除
（1）删除头节点并返回它的值
为了程序的严谨需要考虑两种特殊情况：
  • 一种是试图从一个空链表删除一个节点。
  • 二是链表只有一个节点的情况。
  1. intIntSLList::deleteFromHead(){
  2. if(!isEmpty())//检查链表链表是否为空
  3. {
  4. int el = head->info;
  5. IntSLLNode*tmp = head;
  6. if(head == tail)//加入链表只有一个节点;
  7. head = tail =0;
  8. else head = head->next;
  9. delete tmp;
  10. return el;
  11. }
  12. else 
  13. //std::cout<<"The List is Empty!"
  14. return0;
  15. }
注意：上面的程序实际上有一个问题，程序开始用if语句检查了链表是否为空，假如为空就就会执行else的操作返回0；而对于调用
这个方法的语句并不知道返回的0是头节点本身的值是0，还是因为链表为空而返回的0。最好的解决方法是调用此方法之前就判定一
下链表是否为空。
（2）删除尾节点并返回它的值
该删除操作由成员函数 deleteFromTail实现。 问题在删除了尾节点之后， tail应当指向链表的新末尾节点，也就是说， tail 必须反方向移动一个节点，但是因为从最后一个节点到它的前驱节点没有直接的链接，所以无法进行反方向移动。 因此必须从链表的幵头查找这个前驱 节点，并恰好在tail前面停止。这个任务是通过在for在 循环中用个临时变量temp遍历链表完成的 。
  2. intIntSLList::deleteFromTail(){
  3. int el = tail->info;
  4. if(head == tail){// if only one node on the list;
  5. delete head;
  6. head = tail =0;
  7. }
  8. else{// if more than one node in the list,
  9. IntSLLNode*tmp;// find the predecessor of tail;
  10. for(tmp = head; tmp->next != tail; tmp = tmp->next);
  11. delete tail;
  12. tail = tmp;// the predecessor of tail becomes tail;
  13. tail->next =0;
  14. }
  15. return el;
  16. }
（3） 删除值为el的节点
前面讨论的这两种刪除操作是从开头或者末尾删除一个节点。如果要刪除一个包含特定整数的节点，而不关心这个节点在链表中的位置就需要使用不同的方法。这个节点也许正好在链表的开头、末尾，或者在链表中的任何位置。简单地说，必须先找到这个节点， 然后将其前驱节点与后继节点连接，从而将其从链表中删除。因为不知道该节点在什么位置, 操作复杂得多。
将前驱结点以及后继节点连接起来就 能从链表中删除这个节点 ，但是因为链表只有向后的链接，因此无法从某个节点获得其前驱。完成这个忏务的方法之一是先扫描链表找到处要删除的节点，然后再次扫描链表找到它的前驱，另一种方法如下图所示，借助两个指针变量pred和tmp。
前面的图只讨论了 一种情况，还有下面几种情况：
  • 试图从空链表中刪除节点，此时函数立即退出。
  • 从单节点链表中删除唯一的节点： head 和 tail都设置成 null
  • 从至少有两个节点的链表中刪除第一个节点，此吋需要更新 head
  •  从至少有两个节点的链表中刪除最后一个节点，此吋需要更新 tail
  •  链表中不存在包含某个数字的节点：不进行任何操作.
  1. voidIntSLList::deleteNode(int el){
  2. if(head !=0)  // if non-empty list;
  3. {
  4. if(head == tail && el == head->info){// if only one
  5. delete head;// node on the list;
  6. head = tail =0;
  7. }
  8. elseif(el == head->info){// if more than one node on the list
  9. IntSLLNode*tmp = head;
  10. head = head->next;
  11. delete tmp;// and old head is deleted;
  12. }
  13. else{// if more than one node in the list
  14. IntSLLNode*pred,*tmp;
  15. for(pred = head, tmp = head->next;// and a non-head node
  16. tmp !=0&&!(tmp->info == el);// is deleted;
  17. pred = pred->next, tmp = tmp->next)
  18. if(tmp !=0){
  19. pred->next = tmp->next;
  20. if(tmp == tail)
  21. tail = pred;
  22. delete tmp;
  23. }
  24. }
  25. }
  26. }
2.3 查找
插入和删除操作都对链表进行了修改。查找操作扫描已有的链表，以确定其中是否包含某个数， 在此用布尔成员函数 isInList()实现这个操作。
  1. boolIntSLList::isInList(int el)const{
  2. IntSLLNode*tmp;
  3. for(tmp = head; tmp !=0&&!(tmp->info == el); tmp = tmp->next);
  4. return tmp !=0;
  5. }





【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/star91/p/4761742.html