姓名：Far_Rainbow
    学号： 202505000X
    专业： 软件工程
    年级：2020级

    实验名称：实验3 单链表的基本操作实现

    实验内容：

    （1）实验目的
    通过该实验，深入理解链表的逻辑结构、物理结构等概念，掌握链表基本操作的编程实现，熟练掌握C语言中指针的操作。和实验2对比，掌握线性结构两种不同存储方式的区别。

    （2）实验内容
    编程实现链表下教材第二章定义的线性表的基本操作，最好用菜单形式对应各个操作，使其编程一个完整的小软件。注意，每个功能模块一定要考虑非法的情况，并作出相应的提示，例如：求前驱，要分别能够测试第一个元素的前驱、其他正常的元素的前驱、输入一个在表中不存在的元素求其前驱，这三种情况应给出相应的提示语和结果值；插入和删除时要考虑插入或删除的位置是否合法等。

    （3）实验要求：
    菜单项包括：

    1. 初始化或重置链表
    2. 销毁链表
    3. 清空链表
    4. 链表长度
    5. 指定位置的元素值
    6. 链表已存在元素的位序
    7. 求输入元素的直接前驱
    8. 求输入元素的直接后继
    9. 在第i个位置插入一个元素
    10. 删除第i个元素
    11. 输出有的链表元素
    12. 初始化并用头插法（或尾插法）输入元素
    13. 实现单链表的逆序存放
      要求：所有的提示语和输出语句不允许出现在自定义的函数中，只能在main函数中出现提示语。
      注：销毁链表时需要循环释放每个结点所占用的空间。
      注：求前驱是指，输入一个元素值（而不是位置），求该元素在顺序表中的直接前驱元素值。求后继是指：输入一个元素值（而不是位置），求该元素在顺序表中的直接后继元素值。

    （4）验收/测试用例
    参考实验2

    实验类型：验证性

    实验的重难点：链表的定义和实现

    实验环境：TDM-GCC 4.9.2 64-bit

    实验步骤及完成任务情况：

    一、设计思想

    1. 采用模板实现泛型编程，可创建任意数据类型的单链表；
    2. 采用链式存储方式，插入删除时间复杂度都是实验3 单链表的基本操作实现 - 图1#card=math&code=O%281%29&id=uXxHU)

    二、主要源代码

    1. #include <iostream>
    2. using std::cin;
    3. using std::cout;
    4. using std::endl;
    6. template <typename T> struct Lnode {
    7.     T data;
    8.     Lnode<T>* next;
    9. };
    11. template <typename T> class List {
    12. private:
    13.     int _length;
    14.     Lnode<T>* header;
    16. public:
    17.     void init() {header = new Lnode<T>; header->next = NULL; _length = 0;}
    18.     void destroy();
    19.     void clear();
    20.     List() {header = NULL; }
    21.     ~List() {destroy(); }
    22.     bool exist() const {return header != NULL ? 1 : 0;} 
    23.     bool isempty() const {return _length > 0 ? 0 : 1; }
    24.     int getlength() const {return _length; }
    25.     Lnode<T>* find(int pos);
    26.     int elemlocate(T const& e);
    27.     Lnode<T>* priornode(T const& e);
    28.     Lnode<T>* nextnode(T const& e);
    29.     Lnode<T>* insert(int pos, T const& e);
    30.     T remove(int pos);
    31.     void traverse();
    32.     void create(int n);
    33.     Lnode<T>* reverse();
    34. };
    36. template <typename T> void List<T>::destroy()
    37. {
    38.     if (!exist())    return;
    39.     Lnode<T>* p = header, *q;
    40.     while(p){
    41.         q = p->next;
    42.         delete p;
    43.         p = q;
    44.     }
    45.     header = NULL;
    46.     _length = 0;
    47. }
    49. template <typename T> void List<T>::clear()
    50. {
    51.     Lnode<T>* p = header->next, *q;
    52.     while(p){
    53.         q = p->next;
    54.         delete p;
    55.         p = q;
    56.     }
    57.     _length = 0;
    58. }
    60. template <typename T> Lnode<T>* List<T>::find(int pos)
    61. {
    62.     int count = 0;
    63.     Lnode<T>* p = header->next;
    64.     while(p){
    65.         count ++;
    66.         if(count == pos)    return p;
    67.         p = p->next;
    68.     }
    69.     return NULL;
    70. }
    72. template <typename T> int List<T>::elemlocate(T const& e)
    73. {
    74.     int count = 0;
    75.     Lnode<T>* p = header->next;
    76.     while(p)
    77.     {
    78.         count ++;
    79.         if(p->data == e)    return count;
    80.         p = p->next;
    81.     }
    82.     return 0;
    83. }
    85. template <typename T> Lnode<T>* List<T>::priornode(T const& e) //////
    86. {
    87.     Lnode<T>* p = header->next, *q;
    88.     while(p)
    89.     {
    90.         q = p->next;
    91.         if(q && q->data == e)    return p;
    92.         p = q;
    93.     }
    94.     return NULL;
    95. }
    97. template <typename T> Lnode<T>* List<T>::nextnode(T const& e) //////
    98. {
    99.     Lnode<T>* p =header->next, *q;
    100.     while(p){
    101.         q = p->next;
    102.         if(q && p->data == e)    return q;
    103.         p = q;
    104.     }
    105.     return NULL;
    106. }
    108. template <typename T> Lnode<T>* List<T>::insert(int pos, T const& e)
    109. {
    110.     int count = 0;
    111.     Lnode<T>* p = header; //注意考虑插入到首元结点的位置，故不用p=header->next; 
    112.     Lnode<T>* q = new Lnode<T>;
    113.     q->data = e;
    114.     while(p){
    115.         count ++;
    116.         if(count == pos){
    117.             q->next = p->next;
    118.             p->next = q;
    119.             ++ _length;
    120.             return q;
    121.         }
    122.         p = p->next;
    123.     }
    124.     return NULL;
    125. }
    127. template <typename T> T List<T>::remove(int pos) // 删不了第一个元素 和非法情况 
    128. {
    129.     int count = 0;
    130.     Lnode<T>* p = header->next, *q;
    131.     while(p)
    132.     {
    133.         q = p->next;
    134.         count ++;
    135.         if(count == pos-1){
    136.             p->next = q->next;
    137.             T e = q->data;
    138.             delete q;
    139.             -- _length;
    140.             return e ;
    141.         }
    142.         p = q;
    143.     }
    144. }
    146. template <typename T> void List<T>::traverse()
    147. {
    148.     Lnode<T>* p = header->next;
    149.     while(p){
    150.         cout<<p->data<<' ';
    151.         p = p->next;
    152.     }
    153. }
    155. template <typename T> void List<T>::create(int n)
    156. {
    157.     Lnode<T>* p;
    158.     while(n --)
    159.     {
    160.         p = new Lnode<T>;
    161.         cout<<"请输入想要插入的值：";
    162.         cin>>p->data;
    163.         p->next = header->next;
    164.         header->next = p;
    165.         ++ _length;
    166.     }
    167. }
    169. template <typename T> Lnode<T>* List<T>::reverse()
    170. {
    171.     if(header == NULL || header->next == NULL)    return header;
    172.     Lnode<T>* now = header->next, *pre = NULL, *next = NULL;
    173.     while(now){
    174.         next = now->next;
    175.         now->next = pre;
    176.         pre = now;
    177.         now = next;
    178.     }
    179.     header->next = pre;
    180.     return header;
    181. }
    183. int main()
    184. {
    185.     cout<<"\n   基单链表的基本操作实现\n\n";
    186.     cout<<"1---初始化一个单链表\n";
    187.     cout<<"2---销毁单链表\n";
    188.     cout<<"3---清空单链表\n";
    189.     cout<<"4---求单链表长度\n";
    190.     cout<<"5---获取线性表中指定位置的元素\n";
    191.     cout<<"6---获取单链表元素的位置\n";
    192.     cout<<"7---求前驱\n";
    193.     cout<<"8---求后继\n";
    194.     cout<<"9---在单链表指定位置插入元素\n";
    195.     cout<<"10--删除单链表指定位置的元素\n";
    196.     cout<<"11--显示单链表\n";
    197.     cout<<"12--初始化并用头插法输入元素\n";
    198.     cout<<"13--实现单链表的逆序存放\n"; 
    199.     cout<<"\n\t退出，输入一个负数！\n\n";
    200.     List<int> L;
    201.     while(true)
    202.     {
    203.         int myOption;
    204.         cout<<"\n请输入操作序号：";
    205.         cin>>myOption;
    206.         switch(myOption){
    207.             case 1:{
    208.                 if(L.exist()){
    209.                     cout<<"初始化失败，单链表已存在！\n";
    210.                     break; 
    211.                 }
    212.                 L.init();
    213.                 cout<<"初始化成功!\n";
    214.                 break;
    215.             }
    216.             case 2:{
    217.                 if (!L.exist()){
    218.                     cout<<"销毁失败，单链表不存在\n";
    219.                     break; 
    220.                 }
    221.                 L.destroy();
    222.                 cout<<"销毁成功！\n";
    223.                 break;
    224.             } 
    225.             case 3:{
    226.                 if (!L.exist()){
    227.                     cout<<"清空失败，单链表不存在\n";
    228.                     break; 
    229.                 }
    230.                 if (L.isempty()) ; 
    231.                 else    L.clear();
    232.                 cout<<"清空成功！\n"; 
    233.                 break;
    234.             }
    235.             case 4:{
    236.                 if (!L.exist()){
    237.                     cout<<"请先创建单链表！\n";
    238.                     break; 
    239.                 }
    240.                 cout<<"单链表的长度是"<<L.getlength()<<endl; 
    241.                 break;
    242.             }
    243.             case 5:{
    244.                 if (!L.exist()){
    245.                     cout<<"单链表不存在，请先创建单链表！\n";
    246.                     break; 
    247.                 }
    248.                 if (L.isempty()){
    249.                     cout<<"单链表为空，请先插入元素！\n";
    250.                     break;
    251.                 }
    252.                 cout<<"请输入你要获取元素的位置：";
    253.                 int pos;
    254.                 cin>>pos;
    255.                 Lnode<int>* ptr = L.find(pos);
    256.                 if (!ptr) {
    257.                     cout<<"不存在该位置的元素\n";
    258.                     break;
    259.                 }
    260.                 cout<<"第"<<pos<<"位元素是 "<<ptr->data<<endl; 
    261.                 break;
    262.             }
    263.             case 6:{
    264.                 if (!L.exist()){
    265.                     cout<<"单链表不存在，请先创建单链表！\n";
    266.                     break; 
    267.                 }
    268.                 if (L.isempty()){
    269.                     cout<<"单链表为空，请先插入元素！\n";
    270.                     break;
    271.                 }
    272.                 cout<<"请输入您要获取位置的元素：";
    273.                 int e;
    274.                 cin>>e;
    275.                 if (!L.elemlocate(e)){
    276.                     cout<<"单链表中不存在该元素！\n";
    277.                     break;
    278.                 }
    279.                 cout<<"元素"<<e<<"的位置是"<<L.elemlocate(e)<<endl; 
    280.                 break;
    281.             }
    282.             case 7:{
    283.                 if (!L.exist()){
    284.                     cout<<"单链表不存在，请先创建单链表！\n";
    285.                     break; 
    286.                 }
    287.                 if (L.isempty()){
    288.                     cout<<"单链表为空，请先插入元素！\n";
    289.                     break;
    290.                 }
    291.                 cout<<"请输入您要获取前驱的元素：";
    292.                 int pos, e;
    293.                 cin>>e;
    294.                 Lnode<int>* ptr = L.priornode(e);
    295.                 if (!ptr){
    296.                     cout<<"获取失败，该元素不存在或无前驱！\n";
    297.                     break; 
    298.                 }
    299.                 cout<<"元素"<<e<<"的前驱元素是"<<(ptr-1)->data<<endl;
    300.                 break;
    301.             }
    302.             case 8:{
    303.                 if (!L.exist()){
    304.                     cout<<"单链表不存在，请先创建单链表！\n";
    305.                     break; 
    306.                 }
    307.                 if (L.isempty()){
    308.                     cout<<"单链表为空，请先插入元素！\n";
    309.                     break;
    310.                 }
    311.                 cout<<"请输入您要获取后继的元素：";
    312.                 int e;
    313.                 cin>>e;
    314.                 Lnode<int>* ptr = L.nextnode(e);
    315.                 if (!ptr){
    316.                     cout<<"获取失败，该元素不存在或无后继！\n";
    317.                     break; 
    318.                 }
    319.                 cout<<"元素"<<e<<"的后继元素是"<<(ptr+1)->data<<endl;
    320.                 break;
    321.             }
    322.             case 9:{
    323.                 if (!L.exist()){
    324.                     cout<<"单链表不存在，请先创建单链表！\n";
    325.                     break; 
    326.                 }
    327.                 cout<<"请输入指定位置：";
    328.                 int pos;
    329.                 cin>>pos;
    330.                 cout<<"请输入想要插入的值：";
    331.                 int e;
    332.                 cin>>e;
    333.                 if (!L.insert(pos, e)){
    334.                     cout<<"插入失败，请重新尝试！\n";
    335.                     break;
    336.                 }
    337.                 else    cout<<"插入完毕！\n";
    338.                 break;
    339.             }
    340.             case 10:{
    341.                 if (!L.exist()){
    342.                     cout<<"单链表不存在，请先创建单链表！\n";
    343.                     break; 
    344.                 }
    345.                 if (L.isempty()){
    346.                     cout<<"单链表为空！\n";
    347.                     break;
    348.                 }
    349.                 cout<<"请输入你要删除的元素的位置：";
    350.                 int pos;
    351.                 cin>>pos;
    352.                 int e = L.remove(pos);
    353.                 if (!e){
    354.                     cout<<"删除失败，请重新尝试！\n";
    355.                     break;
    356.                 }
    357.                 else    cout<<"删除完毕！"<<"被删除的元素是"<<e<<endl;;
    358.                 break;
    359.             }
    360.             case 11:{
    361.                 if (!L.exist()){
    362.                     cout<<"单链表不存在，请先创建单链表！\n";
    363.                     break; 
    364.                 }
    365.                 if (L.isempty()){
    366.                     cout<<"单链表为空！\n";
    367.                     break;
    368.                 }
    369.                 cout<<"单链表的所有元素是：";
    370.                 L.traverse();
    371.                 cout<<endl;
    372.                 break;
    373.             } 
    374.             case 12:{
    375.                 if (!L.exist()){
    376.                     cout<<"单链表不存在，请先创建单链表！\n";
    377.                     break; 
    378.                 }
    379.                 cout<<"请输入你想插入的元素个数：";
    380.                 int n;
    381.                 cin>>n;
    382.                 L.create(n);
    383.                 break;
    384.             } 
    385.             case 13:{
    386.                 if (!L.exist()){
    387.                     cout<<"单链表不存在，请先创建单链表！\n";
    388.                     break; 
    389.                 }
    390.                 if (L.isempty()){
    391.                     cout<<"单链表为空！\n";
    392.                     break;
    393.                 }
    394.                 cout<<"逆置前的单链表为：";
    395.                 L.traverse();
    396.                 cout<<endl<<"逆置后的单链表为：";
    397.                 L.reverse();
    398.                 L.traverse();
    399.                 cout<<endl;
    400.                 break;
    401.             }
    402.         }
    403.         if(myOption >13 || myOption == 0)    cout<<"\n请输入小于13的正整数\n\n";
    404.         if(myOption < 0){
    405.             cout<<"\n退出程序！\n";
    406.             break;
    407.         }
    408.     } 
    409.     return 0;
    410. }