#include<iostream> using namespace std; #define ELEMENT_NOT_FOUND -1;
template<typename E> class Array { private: int m_size; // 元素数量 int m_capacity; // 数组容量 E * m_elements; // 指向首地址 void outOfBounds(int index) { throw index; } void rangeCheck(int index); // 检查下标(get,set) void rangeCheckForAdd(int index); // 检查下标(add) void ensureCapacity(int capacity); // 检查容量及扩容 public: Array(int capacity = 10); ~Array(); int size(); // 元素的数量 bool isEmpty(); // 是否为空 int indexOf(E element); // 查看元素的位置 bool contains(E element); // 是否包含某个元素 E set(int index, E element); // 设置index位置的元素 E get(int index); // 返回index位置对应的元素 void add(int index, E element); // 往index位置添加元素 void add(E element); // 添加元素到最后面 E remove(int index); // 删除index位置对应的元素 void clear(); // 清除所有元素 }; template<typename E> void Array<E>::rangeCheck(int index) { if (index < 0 || index >= m_size) outOfBounds(index); } template<typename E> void Array<E>::rangeCheckForAdd(int index) { if(index < 0 || index > m_size) outOfBounds(index); } template<typename E> void Array<E>::ensureCapacity(int capacity) { int oldCapacity = m_capacity; if (oldCapacity >= capacity) return; // 新容量为旧容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); E *newElements = new E[newCapacity]; for (int i = 0; i < m_size; i++) { newElements[i] = m_elements[i]; } delete[] m_elements; // 释放原空间 m_elements = newElements; m_capacity = newCapacity; cout << oldCapacity << "扩容为" << newCapacity << endl; }
template<typename E> Array<E>::Array(int capacity) { m_capacity = (capacity < 10) ? 10 : capacity; m_elements = new E[m_capacity]; } template<typename E> Array<E>::~Array() { delete[] m_elements; } template<typename E> int Array<E>::size(){ return m_size; } template<typename T> bool Array<T>::isEmpty() { return m_size == 0; } template<typename E> int Array<E>::indexOf(E element) { for (int i = 0; i < m_size; i++) { if (m_elements[i] == element) return i; } return ELEMENT_NOT_FOUND; } template<typename E> bool Array<E>::contains(E element) { return indexOf(element) != ELEMENT_NOT_FOUND; } template<typename E> E Array<E>::set(int index, E element) { rangeCheck(index); E old = element; m_elements[index] = element; return old; } template<typename E> E Array<E>::get(int index) { rangeCheck(index); return m_elements[index]; } template<typename E> void Array<E>::add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(m_size + 1); // 0 1 2 3 4 5 // 1 2 3 5 6 7 // index=3, element=4 for (int i = m_size; i > index; i--) { m_elements[i] = m_elements[i-1]; } m_elements[index] = element; m_size++; } template<typename E> void Array<E>::add(E element) { add(m_size, element); } template<typename E> E Array<E>::remove(int index) { rangeCheck(index); E old = m_elements[index]; // 0 1 2 3 4 5 // 1 2 3 5 6 7 // index=2 for (int i = index; i < m_size; i++) { m_elements[i] = m_elements[i + 1]; } m_elements[--m_size] = NULL; return old; } template<typename E> void Array<E>::clear() { // m_elements = nullptr; // 不可行，直接清除了整个指针指向的地址 for (int i = 0; i < m_size; i++) { m_elements[i] = NULL; } m_size = 0; }
int main() { Array<int> array; for (int i = 0; i < 30; i++) { array.add(i); } cout << "array.set(0, 99): " << array.set(0, 99) << endl; cout << "array.remove(0): " << array.remove(0) << endl; cout << "array.isEmpty(): " << array.isEmpty()<< endl; cout << "array.cotains(5): " << array.contains(5) << endl; cout << "size = " << array.size() << endl; array.add(10, 99); cout << "array.add(10, 99), size = " << array.size() << endl;
for (int i = 0; i < array.size() ; i++) { if (i != 0) { cout << ", "; } cout << array.get(i); } }
//https://blog.csdn.net/weixin_43734095/java/article/details/104598981 /* 10扩容为15 15扩容为22 22扩容为33 array.set(0, 99): 99 array.remove(0): 99 array.isEmpty(): 0 array.cotains(5): 1 size = 30 array.add(10, 99), size = 31 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 99, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 , 22, 23, 24, 25, 26, 27, 28, 29
*/ //Thinking in C++ p 400 #include <iostream> #include <cstdio> #include <cstdlib> #include <fstream> #include <string> //#include "../require.h" inline void require(bool requirement, const std::string& msg = "Requirement failed"){ using namespace std; if (!requirement) { fputs(msg.c_str(), stderr); fputs("\n", stderr); exit(1); } }
inline void requireArgs(int argc, int args, const std::string& msg = "Must use %d arguments") { using namespace std; if (argc != args + 1) { fprintf(stderr, msg.c_str(), args); fputs("\n", stderr); exit(1); } }
inline void requireMinArgs(int argc, int minArgs, const std::string& msg = "Must use at least %d arguments") { using namespace std; if(argc < minArgs + 1) { fprintf(stderr, msg.c_str(), minArgs); fputs("\n", stderr); exit(1); } }
inline void assure(std::ifstream& in, const std::string& filename = "") { using namespace std; if(!in) { fprintf(stderr, "Could not open file %s\n", filename.c_str()); exit(1); } }
inline void assure(std::ofstream& out, const std::string& filename = "") { using namespace std; if(!out) { fprintf(stderr, "Could not open file %s\n", filename.c_str()); exit(1); } }
//#include "fibonacci.h" int fibonacci(int n) { const int sz = 100; require(n < sz); static int f[sz]; // Initialized to zero f[0] = f[1] = 1; // Scan for unfilled array elements: int i; for(i = 0; i < sz; i++) if(f[i] == 0) break; while(i <= n) { f[i] = f[i-1] + f[i-2]; i++; } return f[n]; }
class IntStack { enum { ssize = 100 }; int stack[ssize]; int top; public: IntStack() : top(0) {} void push(int i) { require(top < ssize, "Too many push()es"); stack[top++] = i; } int pop() { require(top > 0, "Too many pop()s"); return stack[--top]; } }; template<class T> class Array { enum { size = 100 }; T A[size]; public: T& operator[](int index) ; // {//非内联成员函数的定义,这时编译器需要在成员函数定义之前看到template声明 // require(index >= 0 && index < size, // "Index out of range"); // return A[index]; // } };
//引用模板的类名的地方，必须伴有该模板的参数列表，例如在Array<T>::operator[]中 template<class T> T& Array<T>::operator[](int index) { require(index >= 0 && index < size, "Index out of range"); return A[index]; }
// STACKTEMPLATE_H template<class T> class StackTemplate { enum { ssize = 100 }; T stack[ssize]; int top; public: StackTemplate() : top(0) {} void push(const T& i) { require(top < ssize, "Too many push()es"); stack[top++] = i; } T pop() { require(top > 0, "Too many pop()s"); return stack[--top]; } int size() { return top; } };
int main() { IntStack is1; // Add some Fibonacci numbers, for interest: for(int i = 0; i < 20; i++) is1.push(fibonacci(i)); // Pop & print them: for(int k = 0; k < 20; k++) std::cout << is1.pop() << ' '; std::cout << std::endl; Array<int> ia; Array<float> fa; for(int i = 0; i < 20; i++) { ia[i] = i * i; fa[i] = float(i) * 1.414; } for(int j = 0; j < 20; j++) std::cout << j << ": " << ia[j] << ", " << fa[j] << std::endl; //Thinking in C++ p 407 StackTemplate<int> is2; for(int i = 0; i < 20; i++) is2.push(fibonacci(i)); for(int k = 0; k < 20; k++) std::cout << is2.pop() << std::endl; std::ifstream in("StackTemplateTest.cpp"); assure(in, "StackTemplateTest.cpp"); std::string line; StackTemplate<std::string> strings; while(getline(in, line)) strings.push(line); while(strings.size() > 0) std::cout << strings.pop() << ' '; std::cout << std::endl;
return 0; } /* 6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1
0: 0, 0 1: 1, 1.414 2: 4, 2.828 : : 17: 289, 24.03817: 289, 24.038 18: 324, 25.452 19: 361, 26.866
6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 Could not open file StackTemplateTest.cpp
*/
