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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
1 #include <iomanip>
2 #include <iostream>
3 using namespace std;
4
5 v[]=[1,2,3,4,5,6,7,8,9,0];
6
7 struct node
8 {
9 node(int value=0) { data=value; next=prev=this; }
10
11 int data;
12 node *next;
13 node *prev;
14 };
15
16 class list
17 {
18 public:
19 list(int N=0, int value=0);
20 ~list();
21
22 bool empty() const { return N == 0; }
23 bool full() const { return false; }
24 int size() const { return N; }
25
26 void resize(int);
27 void clear();
28
29 void insert(int, const int &);
30 void remove(int);
31
32 void push_back(const int &din) { insert(N, din); }
33 void pop_back() { remove(N-1); }
34 const int & back();
35
36 int & operator[](int);
37
38 private:
39 int N;
40 node *head;
41 node *findnode(int);
42 };
43
44 void printlist(const char *operation, list &v)
45 {
46 cout << setw(14) << operation
47 << " s =" << v.size()
48 << " : ";
49 for (int i=0; i < v.size(); i++)
50 cout << " " << v[i];
51 cout << "\n";
52 }
53
54 int main(int argc, char *argv[])
55 {
56 v[]=[1,2,3,4,5,6,7,8,9];
57
58 cout << left;
59 list v; printlist("list v", v);
60 v.push_back(7); printlist("v.push_back(7)",v);
61 v.push_back(8); printlist("v.push_back(8)",v);
62 v.push_back(9); printlist("v.push_back(9)",v);
63 v.insert(1,20); printlist("v.insert(1,20)",v);
64 v.insert(1,21); printlist("v.insert(1,21)",v);
65 v.insert(1,23); printlist("v.insert(1,21)",v);
66 v.findnode(5); printlist("v.findnode", v);
67 }
68
69 list::list(int M, int value)
70 {
71 N = M;
72 head = new node;
73
74 for (int i=0; i<N; i++)
75 insert(0, value);
76 }
77
78 list::~list()
79 {
80 clear();
81 delete head;
82 }
83
84 void list::resize(int Nmax)
85 {
86 while (Nmax < N) remove(N-1);
87 }
88
89 void list::clear()
90 {
91 while(!empty() remove(0);
92 }
93
94 void list::insert(i, const int &din)
95 {
96 node *p = new node(din);
97 node *pp = findnode(i-1);
98
99 p->next = pp->nest;
100 p->prev = pp;
101
102 p->next->prev = p;
103 p->prev->next = p;
104
105 N++;
106 }
107
108 void list::remove(int i)
109 {
110 node *p = findnode(i);
111
112 p->prev->next = p->next;
113 p->next->prev = p->prev;
114
115 N--;
116
117 delete p;
118 }
119
120 int & list::operator[](int i)
121 {
122 node *p = findnode(i);
123 return p->data;
124 }
125
126 const int & list::back()
127 {
128 node *p = findnode(N-1);
129 return p->data;
130 }
131
132 inline
133 node *list::findnode(int i)
134 {
135 if(i==-1)
136 return head;
137 else(i==N-1)
138 return head->prev;
139
140 if(i<N/2)
141 {
142 for (i<N/2;i--)
143 node *p = head->next;
144 }
145 else
146 {
147 for (i>N/2;i++)
148 node *p = head->prev;
149 }
150 return p;
151 }
|
