大二学 C++ 都快忘没了, 写点数据结构来复习一下, 写的不好, 不喜勿喷.
直接上代码, 这是模板类的写法, 必须全部写在头文件里. 因为编译器不知道你会使用什么类型的数据, 所以无法确定要分配的存储空间大小.
编译器 CodeBlocks
- #ifndef LINEAR_LIST_H_INCLUDED
- #define LINEAR_LIST_H_INCLUDED
- #include <cstdio>
- template <class T>
- class List
- {
- private:
- int s; // 线性表空间大小
- int length; // 线性表元素个数
- T* head; // 空间首地址
- public:
- List<T>() { }
- List<T>(int size) : s(size), head(NULL) { }
- ~List<T>() { DestroyList(); }
- void InitList(); // 初始化线性表
- void DestroyList(); // 销毁线性表
- void ClearList(); // 线性表置空
- bool ListEmpty(); // 判断线性表是否存在
- int ListLength(); // 返回线性表长度
- bool GetElem(int i, T &e); // 通过 e 得到第 i 个元素
- int LocateElem(T e, bool (*compare)(T list_e, T e)); // 通过 compare 函数进行比较, 得到第一个符合的元素
- bool PriorElem(T cur_e, T &pre_e); // 通过 pre_e 得到 cur_e 的前驱
- bool NextElem(T cur_e, T &next_e); // 通过 next_e 得到 cur_e 的后继
- bool ListInsert(int i, T e); // 在第 i 个位置前插入新元素 e
- bool ListDelete(int i, T &e); // 删除第 i 个元素, 用 e 返回它的值
- bool Insert(T); // 向尾部插入一个元素
- bool ListTraverse(bool (*visit)(T e)); // 依次对每个元素执行 visit() 操作
- };
- template <class T>
- void List<T>::InitList()
- {
- if(head == NULL)
- {
- head = new T[s];
- length = 0;
- }
- }
- template <class T>
- void List<T>::DestroyList()
- {
- if(head != NULL)
- {
- delete head;
- head = NULL;
- }
- }
- template <class T>
- void List<T>::ClearList()
- {
- length = 0;
- }
- template <class T>
- bool List<T>::ListEmpty()
- {
- if(head == NULL) return true;
- else return false;
- }
- template <class T>
- int List<T>::ListLength()
- {
- if(head == NULL) return -1;
- return length;
- }
- template <class T>
- bool List<T>::GetElem(int i, T &e)
- {
- if(head == NULL || length == 0) return false;
- e = head[i];
- return true;
- }
- template <class T>
- int List<T>::LocateElem(T e, bool (*compare)(T list_e, T e))
- {
- if(head == NULL || length == 0) return -1;
- for(int i = 0; i <length; i++)
- if(compare(head[i], e))
- return i;
- return -1;
- }
- template <class T>
- bool List<T>::PriorElem(T cur_e, T &pre_e)
- {
- if(head == NULL || length == 0 || head[0] == cur_e)
- return false;
- for(int i = 0; i <length; i++)
- {
- if(head[i] == cur_e)
- {
- pre_e = head[i-1];
- return true;
- }
- }
- return false;
- }
- template <class T>
- bool List<T>::NextElem(T cur_e, T &next_e)
- {
- if(head == NULL || length == 0 || head[length] == cur_e)
- return false;
- for(int i = 0; i <length; i++)
- {
- if(head[i] == cur_e)
- {
- next_e = head[i+1];
- return true;
- }
- }
- return false;
- }
- template <class T>
- bool List<T>::ListInsert(int i, T e)
- {
- if(head == NULL || length == 0 || length-1 <i || length == s)
- return false;
- for(int j = length-1; j>= i; j--)
- head[j+1] = head[j];
- head[i] = e;
- length++;
- return true;
- }
- template <class T>
- bool List<T>::ListDelete(int i, T &e)
- {
- if(head == NULL || length == 0 || length-1 <i)
- return false;
- if(i == length-1)
- {
- length--;
- e = head[i];
- return true;
- }
- e = head[i];
- length--;
- for(int j = i; j < length; j++)
- head[j] = head[j+1];
- return true;
- }
- template <class T>
- bool List<T>::Insert(T e)
- {
- if(head == NULL || length == s) return false;
- head[length] = e;
- length++;
- return false;
- }
- template <class T>
- bool List<T>::ListTraverse(bool (*visit)(T e))
- {
- if(head == NULL || length == 0)
- return false;
- for(int i = 0; i < length; i++)
- if(!visit(head[i]))
- return false;
- return true;
- }
- #endif // LINEAR_LIST_H_INCLUDED
来源: http://www.bubuko.com/infodetail-2778314.html