2.1 线性表的定义和特点

线性表

定义：由n（n≥0）个数据元素（节点） a₁ ,a₂, ...a_n组成的有序列。

• 其中数据元素的个数 n 定义为表的长度；
• 当 n=0 时称为空表；
• 将非空的线性表（n>0）记作：（ a₁ ,a₂, ...a_n）；
• 这里的数据元素a_i（1≤i≤n）只是一个抽象的符号，其具体含义在不同情况下可以不同。

逻辑特征

• 在非空的线性表，有且仅有一个开始结点 a₁，它没有直接前趋，而仅有一个直接后继 a₂；

• 有且仅有一个终端结点a_n，它没有直接后继，而仅有一个直接前趋 a_n-1；

• 其余的内部结点 a_i（2≤i≤n-1）都有且仅有一个直接前趋 a_i-1 和一个直接后继 a_i+1 。

线性表是一种典型的线性结构。

2.2案例引入

顺序存储结构存在问题

• 存储空间分配不灵活

• 运算的空间复杂度高

==> 链式存储结构

总结

• 线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
• 许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。
• 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。

2.3 线性的类型定义

抽象数据类型线性表的定义如下：

ADT list{

数据对象：D ={a_i|a_i属于Elemset,(i=1,2,...,n,n≥0)}

数据关系：R={<a_i-1,a_i>|a_i-1,a_i属于D,(I=2,3,...,n)}

基本操作：

InitList(&L); DestroyList(&L);

ListInsert(&L,i,e); ListDelete(&L,i&e);

......等等

}ADT List

基本操作（一）

• InitList(&L) (Initialization List) ---初始化操作，建立一个空的线性表L

  • 操作结果：构造一个空的线性表L。

    Status InitList_Sq(SqList &L){ //构造一个空的顺序表
      L.elem = new ElemType[MAXSIZE];//为顺序表分配空间
      if(!L.elem)exit(OVERFLOW);   //存储分配失败
      L.length=0;                  //空表长度为0
      return OK;
    }
    

• DestroyList(&L) --- 销毁已存在的线性表 L

  • 初始条件：线性表L已经存在

  • 操作结果：销毁线性表L。

    void DestroyList(SqList &L){
      if(L.elem)delete L.elem;  //释放存储空间
    }
    

• ClearList(&L) --- 将线性表清空

  • 初始条件：线性表L已经存在。
  • 操作结果：将线性表L重置为空表。

• ListEmpty(L)

  • 初始条件：线性表L已经存在。
  • 操作结果：若线性表L为空表，则返回TURE；否则返回FALSE。

• ListLength(L)

  • 初始条件：线性表L已经存在。
  • 操作结果：返回线性表L中的数据元素个数。

• GetElem(L,i,&e) --- 顺序表的查找

  • 初始条件：线性表L已经存在，1≤i≤ListLength(L)。

  • 操作结果：用e返回线性表L中第i个数据元素的值。

• LocateElem(L,e,compare())

  • 初始条件：线性表L已经存在，compare()是数据元素判定函数。
  • 操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。

• PriorElem(L,cur_e,&pre_e)

  • 初始条件：线性表L已经存在。
  • 操作结果：若cur_e是L的数据元素，且不是第一个，则pre_e返回它的前驱，否则操作失败，pre_e无意义。

• NextElem(L,cur_e,&next_e)

  • 初始条件：线性表L已经存在。
  • 操作结果：若cur_e是L的数据元素，且不是最后一个，则next_e返回它的后继，否则操作失败，next_e无意义。

• ListInsert(&L,i,e)

  • 初始条件：线性表L已经存在，1≤i≤ListLength(L)+1。
  • 操作结果：在L的第 i 个位置之前插入新的数据元素 e ，L 的长度加一。

  插入元素 e 之前（长度为 n）： （a₁,a₂,...,a_i-1,a_i,...,a_n）

  插入元素 e 之后（长度为 n+1）： （a₁,a₂,...,a_i-1,e,a_i,...,a_n）

• ListDelete(&L,i,&e)

  • 初始条件：线性表 L 已经存在，1≤i≤ListLength(L)

  • 操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减一。

    • 删除前 （长度为 n）

      （a₁,a₂,...,a_i-1,a_i,a_i+1,...,a_n）

    • 删除后 （长度为 n-1）

      （a₁,a₂,...,a_i-1,a_i+1,...,a_n）

• ListTraverse(&L,visited())

  • 初始条件：线性表 L 已经存在
  • 操作结果：依次对线性表中的每个元素调用visited()

• 以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么"，至于"如何做"等实现细节，只有待确定了存储结构之后才考虑

• 在计算机内，线性表有两种基本的存储结构

  顺序存储结构和链式存储结构。

2.4 线性表的顺序表示和实现

线性的顺序表示又称为顺序存储结构或顺序映像。

顺序存储定义

把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

简言之，逻辑上相邻，物理上也相邻。

线性表的第1个数据元素 a₁ 的存储位置，称作线性表的起始位置或基地址。

顺序表中元素存储位置的计算

线性表顺序存储结构占用一片连续的存储空间。知道某个元素的存储位置就可以计算其他元素的存储位置。

 假设线性表的每个元素需占 *l* 个存储单元，则第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置之间满足关系：

        **LOC(a<sub>i+1</sub>) = LOC(a<sub>i</sub>) + *l***

由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：

        **LOC(a<sub>i+1</sub>) = LOC(a<sub>1</sub>) +（i-1）x *l***       

顺序表的特点

• 以物理位置相邻表示逻辑关系
• 任一元素均可随机存取。（优点）

顺序表的顺序存储表示

线性表长度可变（删除）

数组长度不可动态定义。 → 用变量表示顺序表的长度属性

#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
  typedef struct{
    ElemType elem[LIST_INIT_SIZE];
    int length; //当前长度
  }SqList;

顺序表的查找算法分析

• 在线性表 L 中查找与指定值 e 相同的数据元素的位置
• 从表的一端开始，逐个进行记录的关键字和给定值得比较。找到，返回该元素的位置序号，未找到，返回0。

int LocateElem(SqList L,ElemType e){
  //在线性表L中查找值为e的数据元素，返回其序号（是第几个元素）
  for(i=0;i<L.length;i++){
    if(L.elem[i] == e) return i+1;  
  }
  return 0;//查找失败，返回0
}

• 平均查找长度 ASL (Average Search Length):
  • 为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。

顺序表的插入

线性表的插入运算是指在表的第 i （1≤ i ≤n+1）个位置上，插入一个新结点 e ，使长度为 n 的线性表（a1,...,ai-1,ai,...,an）变成长度为 n+1 的线性表 （a1,...,ai-1,e,ai,...,an）

算法思想：

1. 判断插入位置 i 是否合法。
2. 判断顺序表的存储空间是否已满，若已满返回ERROR。
3. 将第 n 至第 i 位的元素依次向后移动一个位置，空出第 i 个位置。
4. 将要插入的新元素 e 放入第 i 个位置。

Status ListInsert_Sq(SqList &L,int i,ElemType e){
  if(i<1||i>L.lengtf+1) return ERROR; //i值不合法
  if(L.length == MAXSIZE) return ERROR;//当前存储空间已满
  for(int j=L.length-1;j>=i-1;j--){
    L.elem[j+1] = L.elem[j]  
  }
  L.elem[i-1] = e;
  L.length++;
  return OK;
}

顺序表的删除

线性表的删除运算是指将表的第 i (1 ≤ i ≤ n)个结点删除，使长度为 n 的线性表（a1,...,ai-1,ai,...,an）变成长度为 n-1 的线性表 （a1,...,ai-1,ai+1,...,an）

算法思想：

1. 判断删除位置 i 是否合法 （合法值为 1 ≤ i ≤ n）。

2. 将欲删除的元素保留在 e 中。

3. 将第 i+1 至第 n 位的元素依次向前移动一个位置。

4. 表长减1，删除成功返回OK。

   Status ListDelete_Sq(SqList &L,int i,&e){
     if(i<1||i>L.length) return ERROR;
     e = L.elem[i-1];
     for(int j=i;j<=L.length-1;j++){
       L.elem[j-1] = L.elem[j];
     }
     L.length--;
     return OK;
   }
   

算法分析

• 算法时间主要耗费在移动元素的操作上

  • 若删除尾结点，则根本无需移动（特别快）；

  • 若删除首节点，则表中n-1个元素全部前移（特别慢）；

  • 若要考虑在各种位置删除（共n种可能）的平均移动次数：
    

• 顺序表删除算法的平均时间复杂度为 O(n)。

顺序表的特点

1. 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致。
2. 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等。

• 这种存取元素的方法被称为 随机存取法

顺序表的操作算法分析

• 时间复杂度

  • 查找、插入、删除算法的平均时间复杂度为 O(n)

• 空间复杂度

  • 显然，顺序表操作算法的空间复杂度S(n) = O(1)

    （没有占用辅助空间）

顺序表有缺点

• 优点
  • 存储密度大（结点本身所占存储量/结点结构所占存储量）
  • 可以随机存取表中任一元素
• 缺点 （为克服这一缺点 ==> 链表）
  • 在插入、删除某一元素时，需要移动大量元素
  • 浪费存储空间
  • 属于静态存储形式，数据元素的个数不能自由扩充

2.5 线性表的链式表示和实现

与链式存储有关的术语

1. 结点：数据元素的映像。由数据域和指针域两部分组成
2. 链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
3. 单链表、双链表、循环链表：
   • 结点只有一个指针域的链表，称为单链表或者线性链表
   • 结点有两个指针域的链表，称为双链表
   • 首尾相接的链表称为循环链表
4. 头指针、头结点和首元结点：
   • 头指针：是指向链表中第一个结点的指针
   • 首元结点：是指链表中存储第一个元素 a₁ 的结点
   • 头结点：是在链表的首元结点之前附设的一个结点；

如何表示空表

• 无头结点时，头指针为空时表示空表
• 有头结点时，当头结点的指针域为空时表示空表

在链表中设置头结点有什么好处？

1. 便于首元结点的处理

   首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理；

2. 便于空表和非空表的统一处理

   无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。

链表（链式存储结构）的特点

1. 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
2. 访问时只能通过头指针近入链表，并通过每个节点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等，这种存取元素的方法被称为顺序存取法。

顺序表：随机存取

链表：顺序存取

单链表的存储结构

typedef struct Lnode{     //声明节点的类型和指向结点的指针类型
  ElemType data;          //结点的数据域
  struct Lnode *next;     //结点的指针域
}Lnode, *LinkList         //LinkList为指向结构体Lnode的指针类型

定义链表L: LinkList L;

定义结点指针p: *LNode p; LinkList p

单链表基本操作的实现

• 单链表的初始化（即构造一个空表）

  • 算法步骤

    1. 生成新结点作头结点，用头指针 L 指向头结点。
    2. 将头结点的指针域置空

  • 算法描述

    Status InitList_L(LinkList &L){
      L = new LNode; //或 L = （LinkList）malloc(sizeof(Lnode));
      L->next = NULL;
      return OK;
    }
    

• 判断链表是否为空

  空表：链表中无元素，称为空链表（头指针和头结点仍然在）

  • 算法思路：判断头结点指针域是否为空

    int ListEmpty(LinkList L){ //若L为空表，则返回1，否则返回0
     if(L ->next) //非空
       return 0;
      else
       return 1;
    }
    

• 单链表的销毁

  • 算法思路：从头指针开始，依次释放所有结点

    Status DestroyList_L(LinkList &L){ //销毁单链表L
      Lnode *p; //或 LinkList p;
      while(L){
        P=L;
        L=L->next;
        delete p;
      }
    }
    

• 清空链表

  链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在）

  • 算法思路：依次释放所有结点，并将头结点指针域置为空

    Status ClearList_L(LinkList &L){ //将L重置为空表
      Lnode *p,*q //或 LinkList p,q;
      p=L->next;
      while(p){         //没到表尾
        q = p->next;
        delete p;
        p = q;
      }
      L->next = NULL;   //头结点指针域为空
      return OK;
    }
    

• 求单链表的表长

  • 算法思路：从首元结点开始，依次计数所有结点

    int ListLenght(LinkList L){//返回L中数据元素个数
      LinkList p; //Lnode *p;
      p = L->next;             //p指向第一个结点
      i=0;
      while(p){                //遍历单链表，统计节点数
        i++
        p = p->next;
      }
      return i;
    }
    

• 取值——取单链表中第 i 个元素的内容

  • 算法思路：分别取出表中第 i 个元素。从链表的头指针出发，顺着链域 next 逐个结点往下搜索，直至搜索到第 i 个结点为止。因此，链表不是随机存取结构。

    Status GetElem_L(LinkList L,int i,ElemType &e){//获取线性表 L 中的某个元素的内容，通过变量 e 返回
      p = L->next;j=1;//初始化
      while(p&&j<i){  //向后扫描，直到 P 指向第 i 个元素或 p 为空
        p = p->next;
        ++j;
      }
      if(!p || j>i) return ERROR; //第 i 个元素不存在
      e = p->data;                //取第 i 个元素
      return OK;
    }//GetElem_L
    

• 查找：

  • 按值查找——根据指定数据获取该数据所在的位置（地址）

    Lnode *LocateElem_L(LinkList, Elemtype e){
      //在线性表 L 中查找值为 e 的数据元素
      //找到，则返回 L 值为 e 的数据元素的地址，查找失败返回 NULL
      p = L->next;
      while(p&&p->data!=e){
        p = p->next;
      }
      return p;
    }
    

  • 按值查找——根据指定数据获取该数据位置序号

    //在线性表L中查找值为 e 的数据元素的位置序号 
    int LocateElem_L(LinkList L,Elemtype e){
      //返回 L 中值为 e 的数据元素的位置序号，查找失败返回0
      p = p->next;j=1;
      while(p&&p->data!=e){
        p = p->next;
        j++;
      }
      if(p){
        return j;
      }else{
        return 0;
      }
    }
    

• 插入——在第 i 个结点前插入值为 e 的新结点

  • 算法步骤

    1. 首先找到 a_i-1 的存储位置 p 。
    2. 生成一个数据域为 e 的新结点 s 。
    3. 插入新结点：① 新节点的指针域指向结点 a_i ②结点 a_i-1 的指针域指向新结点
       • s -> next = p ->next;
       • p ->next = s;

    //在 L 中第 i 个元素之前插入数据元素 e
    Status ListInsert_L(LinkList &L,int i,ElemType e){
      p = L;j = 0;
      while(p && j<i-1){p=p->next;++j;} //寻找第i-1个结点，p指向i-1结点
      if(!p||j>i-1)return ERROR;  //i大于表长+1或者小于1，插入位置非法
      s = new LNode; s->data = e; //生成新结点s,将结点s的数据域置为e
      s->next = p->next;          //将结点s插入L中
      p->next = s;
      return OK;
    }//ListInsert_L
    

• 删除——删除第 i 个结点

  • 算法步骤

    1. 首先找到 a_i-1 的存储位置 p ，保存要删除的 a 的值。
    2. 令 p->next 指向 a_i+1 。 p ->next = p->next->next；
    3. 释放结点 a_i 的空间。

    //将线性表 L 中的第 i 个数据元素删除
    Status ListDelete_L(LinkList &L,int i,ElemType &e){
      p=L;j=0;
      while(p->next &&j<i-1){p=p->next;++j}////寻找第i个结点，p指向其前驱
      if(!(p->next)||j>i-1) return ERROR; //删除位置不合理
      q=p->next;                          //临时保存被删结点的地址以备释放
      p->next = q->next;                  //改变删除结点前驱结点的指针域
      e = q->data;                        //保存删除结点的数据域
      delet q;                            //释放删除结点的空间
      return OK;
    }//ListDelete_L
    

• 建立单链表：头插法——元素插入在链表头部，也叫前插法

  • 算法分析

    1. 从一个空表开始，重复读入数据
    2. 生成新结点，将读入数据存放到新结点的数据域中
    3. 从最后一个结点开始，依次将各结点插入到链表的前端

    void CreateList_H(LinkList &L,int n){
      L = new LNode;
      L -> next = NULL; //先建立一个带头结点的单链表
      for(i=n;i>0;--i){
        p = new LNode;  //生成新结点 p=(LNode*)malloc(sizrof(LNode));
        cin>>p->data;   //输入元素值 scanf(&p->data);
        p->next = L->next;  //插入到表头
        L->next = p;
      }
    }//CreateList_H        算法时间复杂度: O(n)
    

• 建立单链表：尾插法——元素插入在链表尾部，也叫后插法

  • 算法分析：

    1. 从一个空表 L 开始，将新结点逐个插入到链表的尾部，尾指针 r 指向链表的尾结点。
    2. 初始时， r 同 L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r 指向新结点。

    void CreateList_R(LinkList &L,int n){ //正位序输入n个元素的值，建立带表头结点的单链表L
      L = new LNode;
      L -> next = NULL;
      r = L;     //尾指针r指向头结点
      for(i=n;i<n;i++){
        p = new LNode;      //生成新结点，输入元素值
        p -> next = NULL;
        r -> next = p;      //插入到表尾
        r = p;              //r指向新的尾结点
      }
    }//CreateList_R       算法时间复杂度: O(n)
    

单链表的查找、插入、删除算法时间效率分析

1. 查找：
   • 因线性链表只能顺序存取，即在查找时要从头指针找起，查找时间复杂度为 O(n)。
2. 插入和删除：
   • 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
   • 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n)。

2.5.3 循环链表

循环链表：是一种头尾相接的链表 （即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）。

优点：从表中任一结点出发均可找到表中其他结点。

注意：由于循环链表中没有 NULL 指针，故涉及遍历操作时，其终止条件就不再像非循环链表那种判断 p 或 p->next 是否为空，而是判断它们是否等于头指针。

注意：表的操作常常是在表的收尾位置上进行

带尾指针循环链表的合并（将Tb合并在Ta之后）

分析有哪些操作？

• p 存表头结点
• Tb表头连接到 Ta 表尾
• 释放 Tb 表头结点
• 修改指针

LinkList Connect(LinkList Ta,LinkList Tb){
                                       //假设Ta、Tb都是非空的单循环链表
  p=Ta->next;                          //①p存表头结点
  Ta->next = Tb->next->next;           //②Tb表头连结Ta表尾
  delete Tb->next;                     //③释放Tb表头结点
  Tb->next = p;                        //④修改指针
  return Tb; 
}

2.5.4 双向链表

单链表的结点→有指示后继的指针域→找后继结点方便；

即：查找某及诶单的后继结点的执行时间为O(1)。

→无指示前驱的指针域→找前驱结点难；

即：查找某结点的前驱结点的执行时间为O(n)。

定义

双链表：子啊单链表的每个结点里再增加一个指向其直接前驱的指针域 prior ,这样链表中就形成了有两个方向不同的链，故称为双向链表。

双向链表的结构可定义如下：

typedef struct DuLNode{
  Elemtype  data;
  struct DuLNode  &prior,*next;
}DuLNode,*DuLinkList;

双向循环链表

和单链的循环表类似，双向链表也可以有循环表

• 让头结点的前驱指针指向链表的最后一个结点
• 让最后一个结点的后继指针指向头结点。

双向链表特性

1. 双向链表结构的对称性（设指针 p 指向某一结点）：

   p->prior->next = p = p->next->prior

2. 在双向链表中有些操作（如：Lis他Length、GetElem等），因仅涉及一个方向的指针，故它们的算法与线性表的相同。但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为 O(n)。

【算法2.13】双向链表的插入

void ListInsert_DuL(DuLinkList &L,Int i,ElemType e){
  //在带头结点的双向循环链表 L 中第 i 个位置之前插入元素 e
  if(!(p = GetElemP_DuL(L,i))) return ERROR;
  S = new DuLNode;
  s -> data = e;
  s -> prior = p -> prior;
  p -> prior -> next = s;
  s -> next = p;
  p -> prior = s;
  return OK;
}//ListInsert_DuL

[算法2.14] 双向链表的删除

void ListDelete_DuL(DuLink &L,Int i,ElemType &e){
  //删除带头结点的双向循环链表 L 的第 i 个元素， 并用 e 返回
   if(!(p = GetElemP_DuL(L,i))) return ERROR;
   e = p -> data;
   p -> prior = p -> next;
   p -> next -> prior = p -> prior;
  free(p);
  return OK;
}//ListDelete_DuL

单链表、循环链表和双向链表的时间效率比较

2.6 顺序表和链表的比较

链式存储结构的优点

• 结点空间可以动态申请和释放
• 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。

链式存储结构的缺点

• 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
• 链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该节点，这增加了算法的复杂度。

存储密度

存储密度是指节点数据本身所占的存储量和整个结构结构中所占的存储量之比，即：

一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1（100%），而链表的存储密度小于1。

比较

2.7 线性表的应用

1.[算法2.15] 线性表的合并

• 问题描述：
  假设利用两个线性表 La 和 Lb 分别表示两个集合 A 和 B，现要求一个新的集合 A = A ∪ B
  

• 算法步骤

  依次取出 Lb 中的每个元素，执行以下操作：

  1. 在 La 中查找该元素
  2. 如果找不到，则将其插入 La 的最后

void union(List &a,List Lb){
  La_len = ListLength(La);
  Lb_len = ListLength(Lb);
  for(i=1,i<=Lb_len;i++){
    GetElem(Lb,i,e);
    if(!LocateElem(La,e)) ListInsert(&La,++La_len,e);
  }
}

2.有序表的合并

• 问题描述：

  已知线性表 La 和 Lb 中的数据元素按值非递减有序排列，现要求将 La 和 Lb 归并为一个新的线性表 Lc，且Lc 中的数据元素仍按值非递减有序排列。
  

• 算法步骤

  1. 创建一个空表 Lc
  2. 依次从 La 或 Lb 中 ”摘取“ 元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止
  3. 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
  pa = pa->next;
  pb = pb->next;
  pc = Lc = La; //用La的头结点作为Lc的头结点
  while(pa&&pb){
    if(pa->data<=pb->data){
      pc->next = pa;
      pc = pa;
      pa = pa->next;
    }else{
      pc->next = pb;
      pc = pb;
      pb = pb->next;
    }
    pc->next = pa?pa:pb; //插入剩余段
    delete Lb; //释放Lb的头结点
  }
}

2.8 案例分析与实现

【案例2.1】一元多项式的运算：实现两个多项式加、减、乘运算

【案例2.2】稀疏多项式

【案例2.3】图书管理系统

类C语言有关操作补充

1. C 语言的内存动态分配

SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);

• malloc(m)函数： 开辟 m 字节长度的地址空间，并返回这段空间的首地址

• sizeof(x)运算: 计算变量 x 的长度

• free(p)函数： 释放指针 p 所指变量的存储空间，即彻底删除一个变量

  需加载头文件：<stdlib.h>

2. C++ 的动态存储分配

new 类型名T （初值列表） EG:int *p1 = new int; or int *p1 = new int(10)
  功能：
     申请用于存放 T 类型对象的内存空间，并依初值列表赋以初值
  结果值：
     成功：T 类型的指针，指向新分配的内存
     失败：0 （NULL）

delete 指针P
  功能：
     释放指针 P 所指向的内存。P 必须是 new 操作的返回值

3. C++ 中的参数传递

• 函数调用时传送给形参表的实参必须与形参三个一致

  类型、个数、顺序

• 参数传递有两种方式

  • 传值方式（参数为整形、实型、字符型等）
  • 传地址
    • 参数为指针变量
    • 参数为引用类型
    • 参数为数组名

传值方式

• 把实参的值传送给函数局部工作区相应的副本中，函数使用这个副本执行必要的功能。函数修改的是副本的值，实参的值不变。

传地址方式--指针变量作参数

• 形参变化影响实参

  #include <iostream.h>
  void swap(float *m,float *n){
    float t;
    t = *m;
    *m = *n;
    *n = t;
  }
  

  void main(){
    float a,b,*p1,*p2;
    cin>>a>>b;
    p1 = &a;
    p2 = &b;
    swap(p1,p2);
    cout<<a<<endl<<b<<endl;
  }
  

• 形参变化不影响实参？？

  #include <iostream.h>
  void swap(float *m,float *n){
    float *t;
    t = m;
    m = n;
    n = t;
  }
  

  void main(){
    float a,b,*p1,*p2;
    cin>>a>>b;
    p1 = &a;
    p2 = &b;
    swap(p1,p2);
    cout<<a<<endl<<b<<endl;
  }
  

传地址方式--数组名作参数

• 传递的是数组的首地址
• 对形参数组所做的任何改变都将反映到实参数组中

传地址方式--引用类型作为参数

什么是引用？？？

引用：它用来给一个对象提供一个替代的名字。

#include <iostream.h>
void main(){
  int i=5;
  int &j=i;
  i=7;
  cout<<"i="<<i<<"j="<<j;
}
//j是一个引用类型，代表 i 的一个替代名，i 值改变时，j 值也跟着改变，所以会输出i=7,j=7

引用类型做形参的三点说明

1. 传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化。

2. 引用类型作参数，在内存中并没有产生实参的副本，它直接对实参操作；

   而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好。

3. 指针参数虽然也能达到与使用引用的效果，但在被调用函数中需要重复使用“*指针变量名” 的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。