本文包含以下内容：
一、线性表的介绍以及抽象ADT
二、顺序表及顺序表的实现
三、链表及链表的实现
四、顺序表和链表的比较
五、总结
参考书目：《数据结构与算法分析》【美】Clifford A.Shaffer著
一、线性表的介绍以及抽象ADT
1.什么是线性表？
关键字：线性、有序、有限。
所谓线性，是一个元素接着一个元素，就像一条线那样排放。而不是离散散乱的，或者一堆一堆的。
所谓有序，不是说表中的元素要按照从小到大或者从大到小排列，而是说每个元素都有它自己的位置
所谓有限，表中的元素个数不能是无穷多。
2.线性表应该有什么样的属性和操作
属性：表头、表尾、长度。
操作：增删改查
线性表中最重要的概念应该是当前位置，一切的操作都是对当前位置的操作。
比如getvalue()得到当前位置的值，insert()在当前位置添加元素，remove()，移除当前位置的元素
3.抽象ADT
template<typename E> class List { private: void operator = (const List&) {}; List(const List&); public: List() {}; virtual ~List() {}; virtual void clear()=0; virtual void insert(const E&it)=0; virtual void append(const E&it)=0; virtual E remove()=0; virtual void moveToStart() =0; virtual void moveToEnd()=0; virtual void pre()=0; virtual void next()=0; virtual int length()const = 0; virtual int currPos()const = 0; virtual void moveToPos(int pos) = 0; virtual const E& getValue()const {}; }; 4.关于抽象ADT的一些解释常量引用参数、常量函数、常量引用返回值
常量引用参数：
virtual void insert(const E&it)=0; virtual void append(const E&it)=0;常量引用确保函数在操作过程中不会改变被引用参数的值常量函数
virtual int length()const = 0; virtual int currPos()const = 0; virtual int length()const = 0; virtual int currPos()const = 0; 常成员函数不能更新任何数据成员，本身是一个只读函数。一个对象的所有成员函数会返回一个指向该对象的隐含this指针，对于常成员函数，返回的是一个常this指针。
virtual int length()const = 0; virtual int currPos()const = 0; 常量引用返回值 virtual const E& getValue()const {};如果一个常成员函数想返回其对象的引用，则应该返回一个常引用。换句话说，如果一个常函数，它返回的内容是this对象的一部分，则它应该返回一个常引用。
二、顺序表及顺序表的实现
1.什么是顺序表？
顺序表是通过数组来实现的线性表
2.顺序表应该具有那些属性？
maxsize,length,curr以及一个数组指针
3.顺序表的实现
#include<assert.h> #define default size 100 template<typename E> class AList { private: E* list; int lenght; int maxsize; int curr; public: AList(int size = defaultsaize){ maxsize = size; length = 0; curr = 0; list = new E[maxsize];// } ~AList() { delete[] list; } void clear(){ delete[] list; length = curr = 0; list = new E[maxsize]; } void moveToStart() { curr = 0; }; void moveToEnd() { if (length > 0)curr = length - 1; else curr = 0; }; void pre() { if (curr > 0)curr = curr - 1; }; void next() { if (curr + 1 < maxsize)curr + curr + 1; }; int insert(const E&item){ assert(length < maxsize, "数组越界"); //把curr右边的数全部往右移一位 for (int i = length; i > curr; i--) list[i] = list[i - 1]; list[curr] = item; length++; return item; } int remove(){ //把curr右边的数往左移一位 assert(curr>=0&&curr<length, "当前没有可以移除的元素"); E temp = list[curr]; for (int i = curr; i < length - 1; i++) list[i] = list[i + 1]; length--; return temp; } int append(const E&item) { assert(length < maxsize, "数组越界"); list[length] = item; lenght++; return item; } int getLength()const { return length }; int grtCurrPos()const { return curr }; const E& getValue()const { assert(curr >= 0 && curr < length, "No element"); return list[curr]; } };三、链表及链表的实现
1.什么是链表？
使用一个个独立的结点来实现的线性表，每个独立的结点都包含当前结点的值以及指向下一个元素的指针。
链表强调的是相对位置
2.链表应该有哪些属性
length,指向头部的头指针head,指向当前结点的指针curr(实际上该指针指向的是当前结点右边的一个结点，后面会在讲解原因)
为了能在常数时间里实现对尾部的访问，我们还需要一个指向尾部结点的 tail指针
当链表为空的时候，没有元素可以让head curr tail来指向，在 插入或删除函数中会需要一些特别的处理代码，为了简便和减少出现错，
我们引进一个特殊的头结点，该节点表示表头，没有值，指针指向下一个元素， 链表为空时，表头结点的指针指向NULL
3.链表的实现
<pre name="code" class="cpp" style="font-size: 13.3333px;">template<typename E> class node { public: E element; node* next; node() { next = NULL; } node(const E& Element, node*Next = NULL) { element = element; next = Next; } }; template<typename E> class LList{ private: node<E>* curr; node<E>*head; node<E>*tail; int length; void Init(){ tail = curr = head = new node<E>; length = 0; } void RemoveAll(){ while (head != NULL) { curr = head; head = head->next; delete curr; } } public: LList() { Init(); } ~LList() { RemoveAll(); } void clear() { RemoveAll(); Init(); } void moveToStart(){ assert(head != NULL, "There is no element"); curr = head; } void moveToEnd(){ assert(tail != NULL, "There is no element"); curr = tail; } void pre(){ assert(head->next != NULL, "There is no pre element"); node<E>* temp = head; while (temp->next != curr) temp = temp->next; curr = temp; } void next(){ assert(curr->next != NULL, "There is no next ellement"); curr = curr->next; } void insert(const E&item){ curr->next = new node*(item, curr->next); if (tail == curr)tail = curr->next; length++; } void remove(){ assert(curr->next != NULL, "error"); if (tail == curr->next)tail = curr; node<E>* temp = curr->next; curr->next = temp->next; delete temp; length--; } void append(const E&item){ tail->next = new node<E>*(item, NULL); tail = tail->next; length++; } int getCurrPos()const{ int cnt = 0; node<E>* temp = head; while (temp != curr) { temp = tem->next; cnt++; } return cnt; } int getLength()const{ return length; } const E&getValut()const{ assert(curr ->next!=NULL, "no element"); return curr->next->element; } };四.顺序表和链表的比较
访问任意位置，顺序表的 时间是常数，链表则不一定
任意位置插入元素，链表的时间是常数，线性表不一定
空间上，链表的指针往往会占用更多的空间，但是链表的长度不用一开始固定，方便 。而线性表要给他一个maxsize，超过maxsize的部分 是不能使用的。
五.总结
复习了线性表了、链表、顺序表
遗忘的 知识：常引用参数、常成员函数、常引用返回值
注意：const总是对它左边的起限定作用，除非它自身已经在最左。
