List(表)类似于队列,不同于队列的是,list可以随机读取/修改/插入某一position,通过position这一位置信息就可以直接修改相应位置的元素。实现方式和队列的类似,多了个position的参数。
注意,因为list的定义使用了模板类,所以其定义和实现需要在同一个文件下,当然,也有其他方式实现二者分离,但比较复杂,网上有方法。
代码:
List.cpp
// 特别注意:模板类不能分离编译,类实现要在同一个文件下 enum Error_code {success,underflow,overflow,range_error}; const int max_list = 10; template <class List_entry> class List { public: // methods of the List ADT List(); int size()const; bool full()const; bool empty()const; void clear(); void traverse(void(*visit)(List_entry &)); //遍历 Error_code retrieve(int position, List_entry &x)const;//察看 Error_code replace(int position, const List_entry &x); Error_code remove(int position, List_entry &x);//移除并挂载 Error_code insert(int position, const List_entry &x);//插入 protected: // data members for a contiguous list implementation int count; List_entry entry[max_list]; }; template <class List_entry> List<List_entry>::List() { count = 0; for(int i = 0; i < max_list; i++) entry[i] = 0; } template <class List_entry> int List<List_entry>::size()const { return count; } template <class List_entry> bool List<List_entry>::full()const { return (count >= max_list); } template <class List_entry> bool List<List_entry>::empty()const { return count == 0; } template <class List_entry> void List<List_entry>::clear() { count = 0; } template <class List_entry> void List<List_entry>::traverse(void(*visit)(List_entry &x)) { //int i; for(int i = 0; i < count; i++) { (*visit)(entry[i]); } } template <class List_entry> Error_code List<List_entry>::retrieve(int position, List_entry &x)const { if(empty()) return underflow; if(position < 0 || position > count) return range_error; else { x = entry[position]; return success; } } template <class List_entry> Error_code List<List_entry>::replace(int position,const List_entry &x) { if(empty()) return underflow; if(position < 0 || position > count) return range_error; else { entry[position] = x; return success; } } template <class List_entry> Error_code List<List_entry>::remove(int position,List_entry &x) { if(empty()) return underflow; if(position < 0 || position > count) return range_error; x = entry[position]; for(int i = position; i < count-1; i++) entry[position] = entry[position+1]; count--; return success; } template <class List_entry> Error_code List<List_entry>::insert(int position,const List_entry &x) { if(full()) return overflow; if(position < 0 || position > count) return range_error; for(int i = count-1; i >= position; i--) entry[i+1] = entry[i]; entry[position] = x; count++; return success; }
main.cpp(可为其他文件名,只有代码中有main函数即可):
/* * main.cpp * * Created on: 2015年9月13日 * Author: Lv_Lang */ #include "List.cpp" #include <cstdio> void print(int &x) { printf("%d\n",x); } void test() { List<int> mylist; for(int i = 0; i < 10; i++) mylist.insert(i,i+1); int a,b; mylist.retrieve(1,a); printf("%d\n",a); mylist.replace(1,111); mylist.retrieve(1,b); printf("%d\n",b); int size = mylist.size(); printf("%d\n",size); mylist.traverse(print); } int main() { test(); return 0; }
在List的成员函数中,有一个比较有趣同时比较有用就是traverse遍历函数,这个函数的参数是一个函数的指针,而这个函数可以在后期(main函数)中自己定义,这个比较值得考究理解下其效用性。