List-概述：

　　列表List是一个线性链表结构（Double—Linked Lists，双链表），它的数据由若干个节点构成，每一个节点都包括一个信息块Info（即实际存储的数据）、一个前驱指针Pre和一个后驱指针Post。

它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。

 

 

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. 约瑟夫环问题：  故事背景略， 请自行百度（我这是有多懒！）。 输入三个正整数， 分别为 n， k, m。 即：共有n个人围成一个队列， 有一个人在从第k个人开始数， 数到第m个， 第m个人出队。然后从他后面那个人开始， 继续开始数， 同样数到的第m个出队。 如果数到队列末尾， 就接着数第一个人，，， 输出这n个人的 出队序列。

　　输入示例： 5 3 3

　　输出示例： 5 3 2 4 1

 

 

     链表实现

1 #include 
       
         2 #include 
        
          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）\n"; 14             continue; 15         }16         list
         
           Li(n);17         list
          
           ::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 
       
         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）\n"; 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 }