Data: n≥0个元素 Relation:序列，1-1 Operation: 在当前位置插入insert 删除remove 改变或获取当前位置—prev，next，MovetoPos, currPos, movetoStart, movetoEnd 获得当前位置的元素值–getValue

获得线性表长度—length

左右分割（分割线前后元素可能为空）

<1,2,3, | 4>当前元素4

插入/删除都定义在当前位置

template <class Elem> class List 
private:
void operator =(const list&){ }
List (const List&){ }
public:
list(){ }
virual ~list(){ }
virtual void clear() = 0;
virtual void insert (const lem&) = 0;
virtual void append (const Elem&) = 0;
virtual Elem remove() = 0 ;

List1.insert(12);将实参插入当前元素之前

List1.prev();将当前位置向前移一个

List1.remove();删除当前位置处的元素

List1.append(20);将实参插入线性表的末尾 List1.moveToPos(6);将当前位置移到实参指定的位置

x =List1.getvalue();将当前位置元素的值赋给x List1.moveToStart();将当前位置移到表头

List1.next();将当前位置向后移一个

List1.moveToEnd();将当前位置移到表尾 i= List1.currPos();获取当前位置元素在表中的索引

l=List1.length());获取线性表的长度

4.1.2Array-based list(顺序表)
#

定义: 将线性表中的元素相继存放在一个连续的存储空间中。可用一维数组描述此存储结构

特点: 在物理空间顺序存储

一般用1个数组，3个整型变量可描述顺序表

√ 1个数组listArray存放各个元素值 √ 1个整型变量maxSize存放数组的大小 √ 1个整型变量listSize存放顺序表的实际长度,listSize <=maxsize √ 1个整数curr存放当前元素的下标

顺序表各种操作的实现及其时间复杂度: 插入insert，删除removeb O(n) listArray，listSize的值会改变

改变当前位置—prev,next，MovetoPos,movetoStart，movetoEnd O(1)根据要求改变变量curr的值 获得当前位置元素值或其索引——get Value，currPos O(1)，返回listArray[curr]，curr的值 获得线性表长度—length O(1) , return变量listSize的值

顺序表有表满情况: maxSize==listSize，不能再插入

1.AList MyList;假定当前MyList为:<12 | 32, 26, 78, 30, 15> 写出执行下列要求的调用语句（按顺序)

1）在元素78和30之间插入元素20;

MyList.moveToPos(4);
MyList.insert(20);

2）删除线性表中第一个元素12。

MyList.moveToStart();
MyList.remove();

int find(const Elem &item)
{
	for (int i = 0; i < listSize; i++)
		if (listArray[i] == item)
			return i;
	return -1;
}

void interchange(List<Elem> &list) 
{
	Elem temp = list.remove();
    // 不知道具体实现，所以略去异常处理
	list.next();
	list.insert(temp);
}

4.2 4.4 作业

4.1.3 Linked list (链表)
#

每个元素表项由结点组成
不可以连续存储
表可扩充
用两个类表达链表
- 链表结点类：Link
- 链表类：LList

template <typename E>
class Link
{
public:
    E data;
    Link<E> *next;
};

三个指针，一个整数可以描述一个链表

头指针/尾指针/当前指针curr（prev？）
结点个数cnt
- 注意，无表满情况，只要系统允许就可以一直插入
  - 有空问题：cnt==0，不可再删除
带无值头结点
- head结点不存储内容。
  - 为了放curr结点
- head指向无data结点
- curr指向当前结点前一个结点
  - 注意到对curr位置的选取在这里便利了插入删除操作
- 插入O(1)
  - S1: new p
  - S2: p->next = curr->next
  - S3: curr->next = p
- 删除O(1)
  - S1: temp = curr->next
  - S2: curr->next = p->next
  - S3: return temp, free temp
- 改变或获取当前位置
  - next, moveToStart, moveToEnd O(1)
  - prev, moveToPos O(n)
  - currPos O(n)

对比（空间占用）
#

AList
#

SC = DxE + 3x4（pos，maxSize，currSize）
E: 数据块大小
D: 最大数组空间
改动O(n)
移动O(1)
提前开辟空间
额外空间问题

LList
#

SC = (E+P)*n + 3P（头，curr，尾）
E: 数据块大小
P: 指针占用空间
n: 实际存放元素数量
改动O(1)
移动O(n)
不用提前开辟空间
- new，delete耗时……！
空间线性增长

平衡点
#

N = DE/P+E

大于n AList，小于n LList

4.1.4 Freelists
#

@对象池，享元模式……

重载new和delete运算符。

template <typename E>
class Link
{
private:
    static Link<E> *freelist; // Reference to freelist head
public:
    Link(Link<E> *n = NULL) : element(NULL), next(n){};
    Link(const E &e, Link<E> *n) : element(e), next(n){};
    const E &element;
    Link<E> *next;
    void *operator new(size t)
    { // Overloaded new operator
        if (freelist == NULL)
            return ::new Link;    // Create space
        Link<E> *temp = freelist; // Can take from freelist
        freelist = freelist->next;
        return temp; // Return the link
    }
    // Overloaded delete operator
    void operator delete(void *ptr)
    {
        ((Link<E> *)ptr)->next = freelist; // Put on freelist
        freelist = (Link<E> *)ptr;
    }
};