数据结构与算法（C语言版）__链表的迭代器

1
#include<list>

1
2
3
4
5
6
7
8
9
//MyList.h
template<class Type>
class ListIterator{
public:
    Boolean NotNull();
    Boolean NextNotNull;
    Type* First();
    Type* Next();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#ifndef MYLIST_H
#define MYLIST_H

#include<iostream>

template<class Type> class List;
template<class Type> class ListIterator;
template<class Type>
class ListNode{
    friend class List<Type>;
    friend class ListIterator<Type>;
private:
    Type data;
    ListNode *link;
    ListNode(Type);//构造函数
};

template<class Type>
class List{
    friend class ListIterator<Type>;
public:
    List(){ first = 0; };
    void Delete(Type);
    void Insert(Type);
    void Invert();
    void Concatenate(List<Type>);
    void Show();//测试使用的函数
private:
    ListNode<Type>*first;
};

template<class Type>
class ListIterator{
public:
    ListIterator(const List<Type>& l) :list(l), current(l.first){};
    bool NotNull();
    bool NextNotNull();
    Type* First();
    Type* Next();
private:
    const List<Type> &list;
    ListNode<Type>* current;

};

template<class Type>
bool ListIterator<Type>::NotNull(){
    if (current)return true;
    else return false;
}

template<class Type>
bool ListIterator<Type>::NextNotNull(){
    if (current && current->link)return true;
    else return false;
}

template<class Type>
Type* ListIterator<Type>::First(){
    if (list.first)return &list.first->data;
    else return 0;
}

template<class Type>
Type* ListIterator<Type>::Next(){
    if (current){
        current = current->link;
        return &current->data;
    }
    else return 0;
}
//插入是往最前面插入
template<class Type>
void List<Type>::Insert(Type k){
    ListNode<Type> *newnode = new ListNode<Type>(k);//k是存放节点里面的数据；
    newnode->link = first;
    first = newnode;
}

template<class Type>
ListNode<Type>::ListNode(Type element){
    data = element;
    link = 0;
}

template<class Type>
void List<Type>::Show(){
    for (ListNode <Type> *current = first; current; current = current->link){
        std::cout << current->data;
        if (current->link)cout << " -> ";
    }
    std::cout << std::endl;
}

template<class Type>
void List<Type>::Invert(){
    ListNode<Type> *p = first, *q = 0;
    while (p){
        ListNode<Type> *r = q; q = p;
        p = p->link;
        q->link = r;
    }
    first = q;
}

template<class Type>
void List<Type>::Delete(Type k){
    ListNode<Type> *previous = 0;//前一个
    ListNode<Type> *current;
    for (current = first; current && current->data != k; previous = current, current = current->link){
        ;//什么都不做，空循环，找到要被删除的节点
    }
    if (current){
        if (previous){
            previous->link = current->link;
        }
        else{
            first = first->link;
        }
        delete current;
    }
}

template<class Type>
void List<Type>::Concatenate(List<Type>b){
    if (!first){ first = b.first; return; }
    if (b.first){
        ListNode<Type>*p;
        for (p = first; p->link; p = p->link);//空循环
        p->link = b.first;
    }
}
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<list>//C++STL中的链表
#include "MyList.h"
using namespace std;

int main(){
    cout << "测试：" << endl;

    cout << "这是标准C++ STL中的链表和迭代器：" << endl;
    std::list<int> listIntegers;
    listIntegers.push_front(5);
    listIntegers.push_back(15);
    listIntegers.push_back(25);
    listIntegers.push_back(35);
    std::list<int>::iterator i = listIntegers.begin();//返回一个迭代器，指向链表里的第一个数据
    while (i != listIntegers.end()){
        cout << *i * 10<< "->";
        ++i;
    }
    cout << endl;

    cout << "这是我的链表和迭代器：" << endl;
    List<int> initList;
    initList.Insert(5);
    initList.Insert(15);
    initList.Insert(25);
    initList.Insert(35);
    ListIterator<int>li(initList);
    //迭代是一种手段，可以一个一个的处理数据，想怎么处理就怎么处理
    if (li.NotNull()){
        cout << *li.First() * 10;
        while (li.NextNotNull())
            cout << " -> " << *li.Next() * 10;
        cout << endl;
    }
    initList.Show();
    initList.Delete(15);
    initList.Show();
    initList.Delete(20);
    initList.Show();
    initList.Invert();
    initList.Show();

    List<char> charList;
    charList.Insert('a');
    charList.Insert('b');
    charList.Insert('c');
    charList.Insert('d');
    charList.Show();

    charList.Invert();
    charList.Show();

    List<char> char2List;
    char2List.Insert('e');
    char2List.Insert('f');
    char2List.Show();

    char2List.Invert();
    char2List.Show();

    charList.Concatenate(char2List);
    charList.Show();

    system("pause");
    return 0;

}