- //main.cpp 部分
- #include"List.cpp"
- int main()
- {
- StaticList<int> SL;
- SL.Insert(2,1);
- SL.Insert(4,2);
- SL.Insert(1,3);
- SL.Insert(9,4);
- SL.Insert(20, 5);
- SL.Insert(3, 6);
- std::cout <<"原始的静态链表如下:" << std::endl;
- SL.show();
- SL.Insert(100, 2);
- std::cout << "在静态链表中第 2 个位置插入 100 后结果如下:" << std::endl;
- SL.show();
- int m;
- int delete_index = 5;
- SL.Delete(m, delete_index);
- std::cout << "删除的对应" << delete_index << "处的值为:" << m << std::endl;
- std::cout << "删除后的静态链表如下:" << std::endl;
- SL.show();
- int find_val = 2;
- int index = SL.Find(find_val);
- std::cout << "查找到" << find_val << "在列表中的位置为:" << index << std::endl;
- return 0;
- }
- //List.h
- #pragma once
- #include<iostream>
- #include<vector>
- const int MAXSIZE = 20;
- template<typename ElemType>
- class StaticList;
- template<typename ElemType>
- class Node
- {
- friend class StaticList<ElemType>;
- private:
- ElemType data;
- int cur;
- };
- template<typename ElemType>
- class StaticList
- {
- public:
- StaticList();
- virtual ~StaticList();
- bool Insert(const ElemType& v, int index = 1);
- bool Delete(ElemType& v, int index = 1);
- int Find(const ElemType v);
- void show()const;
- private:
- int NewSpace();
- void DeleteSpace(int index);
- bool Empty()const;
- bool Full()const;
- std::vector<Node<ElemType>*> StList;
- int Length = 0;
- };
- //List.cpp
- #include"List.h"
- #include<iostream>
- #include<algorithm>
- template<typename ElemType>
- StaticList<ElemType>::StaticList():Length(0)
- {
- for (int i = 0; i <MAXSIZE - 1; ++i)
- {
- Node<ElemType>* node = new Node<ElemType>();
- StList.push_back(node);
- }
- for (ElemType i = 0; i <MAXSIZE - 1; ++i)
- (*StList[i]).cur = i + 1;
- Node<ElemType>* node = new Node<ElemType>();
- StList.push_back(node);
- (*StList[MAXSIZE - 1]).cur = 0;
- }
- template<typename ElemType>
- StaticList<ElemType>::~StaticList()
- {
- std::for_each(StList.begin(), StList.end(), [](Node<ElemType>* node) { delete node; });
- }
- template<typename ElemType>
- bool StaticList<ElemType>::Insert(const ElemType& v, int index)
- {
- if (Full())
- {
- std::cout <<"Can't insert element." << std::endl;
- return false;
- }
- if (index<1 || index>Length + 1)
- {
- std::cout <<"The invalid index" << std::endl;
- return false;
- }
- int k = NewSpace();
- int j = MAXSIZE - 1;
- if (k)
- {
- (*StList[k]).data = v;
- for (int i = 1; i <= index - 1; ++i)
- {
- j = (*StList[j]).cur;
- }
- (*StList[k]).cur = (*StList[j]).cur;
- (*StList[j]).cur = k;
- ++Length;
- return true;
- }
- return false;
- }
- template<typename ElemType>
- bool StaticList<ElemType>::Delete(ElemType& v, int index)
- {
- if (Empty())
- {
- std::cout <<"Can't delete element in an empty list!\n";
- return false;
- }
- if (index < 1 || index>Length)
- {
- std::cout <<"The invalid index!\n";
- return false;
- }
- int k = MAXSIZE - 1;
- int i = 1;
- for (; i <= index - 1; ++i)
- {
- k = (*StList[k]).cur;
- }
- i = (*StList[k]).cur;
- (*StList[k]).cur = (*StList[i]).cur;
- v = (*StList[i]).data;
- DeleteSpace(i);
- --Length;
- return true;
- }
- template<typename ElemType>
- int StaticList<ElemType>::Find(const ElemType v)
- {
- if (Empty())
- {
- std::cout <<"Can't find value in an empty List!\n";
- return -1;
- }
- int i = 1;
- while (0 != i && (*StList[(*StList[i]).cur]).data != v)
- i = (*StList[i]).cur;
- ++i;
- if (0 == i)
- {
- std::cout << "Can't find the value "<< v <<" in the list" << std::endl;
- return -1;
- }
- return i;
- }
- template<typename ElemType>
- void StaticList<ElemType>::show()const
- {
- if (Empty())
- {
- std::cout <<"The List is empty" << std::endl;
- return;
- }
- int k = (*StList[MAXSIZE - 1]).cur;
- std::cout << "The List is:" << std::endl;
- for (int i = 1; i <= Length; ++i)
- {
- std::cout << (*StList[k]).data << " ";
- k = (*StList[k]).cur;
- }
- std::cout << std::endl;
- }
- template<typename ElemType>
- bool StaticList<ElemType>::Full()const
- {
- if (Length> MAXSIZE - 2)
- return true;
- return false;
- }
- template<typename ElemType>
- bool StaticList<ElemType>::Empty()const
- {
- return (0 == Length);
- }
- template<typename ElemType>
- void StaticList<ElemType>::DeleteSpace(int index)
- {
- (*StList[index]).cur = (*StList[0]).cur;
- (*StList[0]).cur = index;
- }
- template<typename ElemType>
- int StaticList<ElemType>::NewSpace()
- {
- int i = (*StList[0]).cur;
- if ((*StList[0]).cur)
- {
- (*StList[0]).cur = (*StList[i]).cur;
- }
- return i;
- }
来源: http://www.bubuko.com/infodetail-3319845.html