一、线性表的概念

• $a_i$表项， $n$表长度
• 第一个表项是表头，最后一个是表尾

1. 逻辑特征

   1. 有且仅有一个开始节点，无直接前趋
   2. 有且仅有一个终端节点，没有后继
   3. 内部节点有且仅有一个直接前趋和一个直接后继

2. 存储方式

   1. 顺序存储方式——顺序表
   2. 链表存储方式——链表

二、顺序表

• 把线性表的节点按逻辑顺序依次存放在一组地址连续的存储单元里

特点

• 各表项的逻辑顺序与物理顺序一致
• 对各个表项可以魂顺序问，也可以随机访问

静态存储与动态存储

#define maxSize 100
typedef int T;
typedef struct{
    T data[maxSize];
    int n;
} SeqList;

typedef int T;
typedef struct{
    T *data;
    int maxSize, n;
} SeqList;

三、单链表

特点

• 每个元素（表项）由结点构成
• 线性结构
• 结点可以不连续存储

前插法建立单链表

在前面插入节点

后插法建立单链表

尾部可以有一个last指针，指向尾部，方便后插

链表置空算法

template <class T>
void List<T>::makeEmpty(){
    LinkNode<T> *q;
    while (first->link != NULL) {
    	q = first->link;              
        first->link = q->link;    //从链上摘下该结点
        delete q;
	}
 }；

四、单链表的变形：循环链表和双向链表

循环链表

尾指针last指向了假头指针fakeHead

特点：

• 扫描到尾部遇到的不是NULL，而是fakeHead。

  template <class T> 
  CircListNode<T> * CircList<T>::Search( T x ) 
  {
       //在链表中从头搜索其数据值为x 的结点
  	current = first->link;
      while ( current != first && current->data != x ) 
      	current = current->link;
      return current;
  }
  

双向循环链表

特点：

• 搜索的时候可以设置搜索方向d

  template <class T>
  DblNode<T> *DblList<T>::Search (T x, int d) {
      //在双向循环链表中寻找其值等于x的结点。
  	DblNode<T> *current = (d == 0)? first->lLink : first->rLink;
      //按d确定搜索方向
      while ( current != first && current->data != x )
      	current = (d == 0) ? current->lLink : current->rLink;
      if ( current != first ) return current; //搜索成功
      else return NULL;
       //搜索失败
  };
  

静态链表

为数组中每一个元素附加一个链接指针，形成静态链表结构。

一个二维数组，第一行存数值，第二行存指针（下一个节点的位置）

需要假头

特点

• 处理中不需要改变物理位置
• 数组定义的，存储中大小不会变

五、单链表的应用——多项式

1. 不同物理结构的优缺点

• 多项式顺序存储表示的缺点

  • 插入和删除时项数可能有较大变化，因此要移动大量数据
  • 不利于多个多项式的同时处理、有溢出问题

• 多项式链表存储表示的优点

  • 插入、删除方便，不移动元素
  • 多项式的项数可以动态地增长，不存在存储溢出问题。