数据结构——单链表

借了一本超级坑爹的数据结构的书，Adam Drozdek 陈曙晖翻译的，大家绝对不要去借，太坑了，一大堆的错误。开始学C++和数据结构。坚持！

  1 #include <iostream>
  2 #include "Linked.h"
  3 
  4 using namespace std;
  5 
  6 //单链表
  7 
  8 //析构函数
  9 IntSLList::~IntSLList()
 10 {
 11     for(IntNode* p ;!isempty();)
 12     {
 13         p = head->next;
 14         delete head;
 15         head = p;
 16     }
 17 }
 18 
 19 //addtohead
 20 void IntSLList::addToHead(int el)
 21 {
 22     head = new IntNode(el,head);
 23     if(tail == 0)
 24     {
 25         tail = head;
 26     }
 27 }
 28 
 29 //addtotail
 30 void  IntSLList::addToTail(int el)
 31 {
 32     if(tail != 0)
 33     {
 34         tail->next = new IntNode(el);
 35         tail = tail->next;
 36     }
 37     else
 38     {
 39         head = tail = new IntNode(el);
 40     }
 41 }
 42 
 43 //deleteFromHead
 44 int IntSLList::deleteFromHead()
 45 {
 46     int el = head->info;
 47     IntNode* tmp = head;
 48     if(tail == head)
 49     {
 50         head = tail = 0;
 51     }
 52     else
 53     {
 54         head = head->next;
 55     }
 56     delete tmp;
 57     return el;
 58 }
 59 
 60 //deleteFromTail
 61 int IntSLList::deleteFromTail()
 62 {
 63     int el = tail->info;
 64     if(head == tail)
 65     {
 66         delete head;
 67         head = tail = 0;
 68     }
 69     else
 70     {
 71         IntNode* tmp;
 72         for(tmp = head;tmp->next != tail;tmp=tmp->next); //为了把tmp指针移到tail前一个
 73         delete tail;
 74         tail = tmp;
 75         tail->next = 0;
 76     }
 77     return el;
 78 }
 79 
 80 //deleteNode，关键在于el是内部点
 81 void IntSLList::deleteNode(int el)
 82 {
 83     if(head != 0)
 84     {
 85         if(head == tail && el == head->info)  //just one node
 86         {
 87             delete head;
 88             head = tail = 0;
 89         }
 90         else //more nodes
 91         {
 92             if(el == head->info)
 93             {
 94                 IntNode* tmp = head;
 95                 head = head->next;
 96                 delete tmp;
 97             }
 98             else
 99             {
100                 IntNode* pred,* tmp;
101                 for(pred=head,tmp=head->next;tmp!=0 && (tmp->info == el);pred=pred->next,tmp=tmp->next);//find address
102                 if(tmp != 0)
103                 {
104                     pred->next = tmp->next;
105                     if(tmp == tail)
106                     {
107                         tail = pred;
108                     }
109                     delete tmp;
110                 }
111             }
112         }
113     }
114 }
115 
116 int main()
117 {
118     IntSLList isl;
119     isl.addToHead(12);
120     isl.deleteFromTail();
121 }

Linked.h

 1 #ifndef LINKED_H_INCLUDED
 2 #define LINKED_H_INCLUDED
 3 
 4 class IntNode
 5 {
 6 public:
 7     int info;
 8     IntNode* next;
 9     IntNode(int el,IntNode* ptr=0)
10     {
11         info = el;
12         next = ptr;
13     }
14 };
15 
16 class IntSLList
17 {
18 public:
19     IntSLList()
20     {
21         head = tail = 0;
22     }
23     ~IntSLList();
24     int isempty()
25     {
26         return head == 0;
27     }
28     void addToHead(int);
29     void addToTail(int);
30     int deleteFromHead();
31     int deleteFromTail();
32     void deleteNode(int);
33     bool IsInList(int) const;
34 
35 private:
36     IntNode* head,*tail;
37 };
38 
39 
40 #endif // LINKED_H_INCLUDED