1 //SLinkList.h  2   3 #ifndef _SLINK_LIST_  4 #define _SLINK_LIST_  5   6 template<typename T>  7 class SLinkList  8 {  9 public: 10     SLinkList(int maxz = 100); 11     ~SLinkList(); 12     void CreateList(int n); 13     void Insert(int i, T e); 14     T Delete(int i); 15     T GetElem(int i); 16     int Locat(T e); 17     int Empty(); 18     int Full(); 19     int Length(); 20     void Clear(); 21     void ListDisplay(); 22 private: 23     struct Tcomp 24     { 25         T data;  26         int cur;       //存储该元素下一个元素 数组对应的下标. 27     }; 28     Tcomp *sls;        //存储数据元素的一维数组 29     int av;            //备用链表表头 30     int sl;            //静态链表表头 31     int maxLen;        //链表可能的最大长度 32 }; 33  34 template<typename T> 35 SLinkList<T>::SLinkList(int maxsz) : maxLen(maxsz)  //创建长度为maxsz空表 36 { 37     sls = new Tcomp[maxLen]; 38     sl = -1;                  39     for (int i = 0; i < maxLen; i++) {              //存放该元素后继所在的数组下标 40         sls[i].cur = i + 1;              41     } 42     sls[maxLen - 1].cur = -1;                       //表示他后面的结点为空 43     av = 0; 44 } 45  46 template<typename T> 47 SLinkList<T>::~SLinkList() 48 { 49     delete[]sls; 50 } 51  52 template<typename T> 53 void SLinkList<T>::CreateList(int n) 54 { 55     int value; 56     if (n > maxLen) throw "参数非法空间溢出"; 57     cout << "请依次输入" << n << "个元素值:\n"; 58     for (int i = 1; i <= n; i++) {             //从1位置开始 59         cin >> value; 60         Insert(i, value); 61     } 62 } 63  64 template<typename T> 65 void SLinkList<T>::Insert(int i, T e) 66 { 67     int m, j = 0, k; 68     m = av;                              //备用结点的第一个结点 准备使用 69     if (av == -1) throw "备用链表为空"; 70     av = sls[av].cur;                    //得到最新表头，将 备用结点 往后移一结点，更新 71     if (sl == -1)                        //空链情况 72     { 73         sls[m].data = http://www.mamicode.com/e;                 //备用链表第一个结点的下标(m), 该下标位置的元素赋值为e 74         sls[m].cur = -1;                 //表示他后面(下一个)的结点为空(以后一直在他前面插入元素) 75         sl = m;                          //sl--数组最后一个元素的cur,用来存放第一个插入元素下标，相当于头结点 76     } 77     else if (i == 1)                     //插在表头 78     { 79         sls[m].data =http://www.mamicode.com/ e;  80         //置 该元素下一个元素 数组对应的下标为 上一次的头结点(就是说把该元素插入在上一次插入的元素之前) 81         sls[m].cur = sl;                  82         sl = m;                          //sl--存放第一个插入元素的下标，相当于头结点,将当前元素下标置为头结点 83     } 84     else { 85         k = sl;                          //找前驱(头)结点 86         while (j < i - 1 && k != -1)     //-1为尾结点标志，标志着该元素后为空 87         { 88             j++; 89             //向下一个元素位置查找 90             if (j < i - 1) k = sls[k].cur;  91         } 92         if (j != i - 1) throw "Station Exception !"; 93         sls[m].data = http://www.mamicode.com/e;                 //还是用上一次av得到的值来储存值，改变下一元素指向 94         sls[m].cur = sls[k].cur;         //将下一元素的下标置为 通过i位置 对应的k值 的下一位置 95         sls[k].cur = m;                  //再用m的位置 覆盖 k的下一个元素位置, m->next, m(达到这种效果) 96     } 97 } 98  99 template<typename T>100 T SLinkList<T>::Delete(int i)101 {102     int m, j = 0, k;103     if (sl == -1) throw "Static LinkList is empty !";104     else if (i == 1)                      //删除链头105     {106         m = sl;                           //得到头结点107         sl = sls[sl].cur;                 //得到下一次的头结点108         sls[m].cur = av;                  //将m的下一个位置置为 备用结点的下标109         av = m;                           //将备用结点的表头，置成 头结点(相当于中间的部分被删除)110         return sls[m].data;               //返回删除的结点111     }112     else113     {114         k = sl;115         while (j < i - 1 && k != -1)      //找前驱结点k,删除k结点后的结点116         {117             j++; 118             if (j < i - 1) k = sls[k].cur; 119         }                                 120         if (j != i - 1) throw "Station Exception !";121         m = sls[k].cur;                   //得到k的下一结点122         sls[k].cur = sls[m].cur;          //k->next = k->next->next123         sls[m].cur = av;                  //m->next = av(备用结点)124         av = m;                           //将 备用结点的表头，置成 头结点(相当于中间的部分被删除)125         return sls[m].data;               126     }                                     127 }128 129 template<typename T>130 int SLinkList<T>::Locat(T e)131 {132     int k = sl, j = 0;                   //sl--相当于首结点133     while (k != -1 && sls[k].data != e) {134         k = sls[k].cur; j++;135     }136     if (k == -1) return -1;137     else138         return j + 1;139 }140 141 template<typename T>142 void SLinkList<T>::Clear()143 {144     sl = -1;                     //头结点置为-1145     for (int i = 0; i < maxLen; i++) {146         sls[i].cur = i + 1;      //恢复初始化147     }148     sls[maxLen - 1].cur = -1;    //下一个位置为空的标志149     av = 0;                      //备用结点的表头设置 0150 }151 152 template<typename T>153 T SLinkList<T>::GetElem(int i)154 {155     int k = sl, j = 0;           // k--指向首结点156     while (j < i && k != -1)157     {158          j++;159          if (j < i) k         = sls[k].cur;160     }161     if (j == i) return (sls[k].data);162     else163         throw "Station Exception !";164 }165 166 template<typename T>167 int SLinkList<T>::Empty()168 {169     if (sl == -1) return 1;170     else 171         return 0;172 }173 174 template<typename T>175 int SLinkList<T>::Full()176 {177     //备用结点的表头等于 元素结束标志时(第一次在空链插入元素时,在最后的元素后的空元素置为-1,然后插入元素都是在元178     //素的前端插入 )179     if (av == -1) return 1;180     else return 0;181 }182 183 template<typename T>184 int SLinkList<T>::Length()185 {186     int k = sl, len = 0;187     while (k != -1) {188         len++; k = sls[k].cur;189     }190     return len;191 }192 193 template<typename T>194 void SLinkList<T>::ListDisplay()195 {196     int k = sl, kase = 0;197     while (k != -1)198     {199         cout << kase++ << "\t" << sls[k].data << endl;200         k = sls[k].cur;201     }202 }203 204 #endif

 1 //main_Test_SLinkList.cpp 2 #include "SLinkList.h" 3 #include <iostream> 4 #include <cstdio> 5 using namespace std; 6  7 char pause; 8 typedef int T; 9 10 int main()11 {12     int i;13     T e;14     SLinkList<int> L(100);15     system("cls");16     int choice;17     do 18     {19         cin >> choice;20         switch (choice)21         {22         case 1:23             cout << "请输入要创建的链表中元素的个数1:" << endl;24             cin >> i; cout << endl;25             L.CreateList(i); 26             break;27         case 2:28             cout << "请输入插入元素位置:";29             cin >> i; cout << endl;30             cout << "请输入插入元素的值:"; cin >> e;31             cout << endl;32             try {33                 L.Insert(i, e);34             }35             catch (char *err) {36                 cout << err << endl;37             }38             break;39         case 3:40             cout << "请输入删除位置:";41             cin >> i; cout << endl;42             try {43                 e = L.Delete(i);44                 cout << "被删除的元素为: " << e << endl;45             }46             catch (char *err) {47                 cout << err << endl;48             }49             cin.get(pause); system("pause");50             break;51         case 4:52             cout << "请输入要查询的元素位置:"; cin >> i;53             try {54                 e = L.GetElem(i);55                 cout << "第" << i << "个元素值为:" << e << endl;56             }57             catch (char *err) {58                 cout << err << endl;59             }60             break;61         case 6:62             L.Clear(); cout << "表已清空" << endl;63             cin.get(pause);64             system("pause");65             break;66         case 10:67             L.ListDisplay(); cout << endl;68             cin.get(pause); system("pause");69             break;70         case 11:71             cout << "结束运行\n";72             break;73         default:74             break;75         }76     } while (choice != 11);77     78     return 0;79 80 }