List-概述:
list <TYPE> c |
产生一个空list,其中没有任何元素 |
list<TYPE> c1(c2) |
产生一个与c2同型的list(每个元素都被复制) |
list<TYPE> c(n) |
产生拥有n个元素的list,都以default构造函数初始化 |
list<TYPE> c(n, type) |
产生拥有n个元素的list,每个元素都是type的副本 |
list<TYPE> c (beg, end) |
产生一个list,并以[start, end)区间内的元素为初始 |
c.~list<TYPE>() |
销毁所有元素,释放内存 |
TYPE &back() TYPE &front() |
返回对最后一个元素的引用 返回对第一个元素的引用 |
iterator begin() iterator end() |
返回指向第一个元素的迭代器 返回指向末尾(最后一个元素之后)的迭代器 |
void clear() |
清空链表 |
bool empty() |
如果链表为空返回true,否则返回false |
iterator erase(iterator pos) iterator erase(iterator start, iterator end) |
删除pos所指元素并返回下一元素迭代器 删除[start, end)之间的元素,并返回最后一个被删除元素的下一个元素的迭代器 |
iterator insert( iterator pos, const TYPE &val ) |
插入一个值为value的元素在pos位置并返回其迭代器,原pos及以后的元素后移 |
void insert( iterator pos, size_type num, const TYPE &val) |
插入num个值为value的元素在pos位置,原pos及以后元素后移 |
…… |
链表实现
1 #include <iostream> 2 #include <list> 3 using namespace std; 4 5 int main() 6 { 7 int n, k, m; 8 cout << "请分别输入总人数: n, 开始位置: k, 循环节: m." << endl; 9 while (cin >> n >> k >> m) 10 { 11 if(k>n||n<0||k<0||m<0) 12 { 13 cout << "输入有误, 请注意(k < n, k, m, n > 0) "; 14 continue; 15 } 16 list<int> Li(n); 17 list<int>::iterator it = Li.begin(), pos = Li.begin(); // 用pos的指示走到的位置 18 // 初始化链表 19 for( int i = 1; it != Li.end(); ++i, ++it) 20 *it = i; 21 22 int t = (k-2+n) % n + 1; 23 while(--t) // 初始化 pos 指示的位置即:从(k-1)开始数 24 { 25 pos++; 26 if(pos == Li.end()) 27 pos = Li.begin(); 28 } 29 while(n--) // 队列中剩余的人数 n 30 { 31 int t = m; 32 while(t--) // 走m步 33 { 34 pos++; 35 if(pos == Li.end()) 36 pos = Li.begin(); // 走 m 步后的pos指示的位置 37 } 38 cout << *pos << ", "; // 出队 39 it = pos; it--; // 用 it 暂存 pos的位置,由于pos将被删除, 40 //所以下次开始数的位置为现在pos所指位置的前一个位置 41 Li.erase(pos); // 删除 出队的人。 42 pos = it; 43 } 44 cout << endl << endl; 45 cout << "请分别输入总人数: n, 开始位置: k, 循环节: m." << endl; 46 47 } 48 return 0; 49 }
附数组实现
1 #include <iostream> 2 const int MAXN = 50; 3 using namespace std; 4 5 int n, k, m, a[MAXN]; 6 7 int Move(int p, int t); // 输入开始位置 p, 固定循环长度t; 返回:出队人的位置 8 9 int main() 10 { 11 cout << "请分别输入总人数: n, 开始位置: k, 循环节: m." << endl; 12 while((cin >> n >> k >> m)) 13 { 14 if(k>n) 15 { 16 cout << "输入有误, 请注意(k < n, k, m, n > 0) "; 17 continue; 18 } 19 for(int i = 1; i <= n; i++) a[i] = n; 20 int left = n; // left 为队列中还剩余的人数。 21 int p = k-1 + n; 22 while(left) 23 { 24 p = Move(p, m); 25 cout << p << ", "; 26 left--; 27 a[p] = 0; // 标记这个位置的人已经出队。 28 } 29 cout << endl << endl; 30 cout << "请分别输入总人数: n, 开始位置: k, 循环节: m." << endl; 31 } 32 return 0; 33 } 34 35 int Move (int p, int t) 36 { 37 while(t--) 38 { 39 do { p = p % n + 1; } while(a[p] == 0); // 忽略已经出队的人 40 } 41 return p; 42 }