第二章 线性表

线性表定义

• 由n(n>=0) 个数据特性相同的元素构成的有限序列

n： 线性表的长度 n=0：空表

线性表实现

顺序表（顺序存储）

• 用一组地址连续的存储单元依次存储的线性表的数据元素

逻辑上相邻，物理上也相邻

由元素首地址和长度 两部分构成

B

基本操作：（文本语言实现）

• 初始化 O(1)

  1. 顺序表初始化 ，为顺序表再内存中开辟数据空间大小
  2. 定义一个变量elem指向这片空间的首地址

• 取值O(1)

  1. 判断i<=i<=length,若不符合，返回false
  2. 否则 取elem[i-1]

• 顺序表查找O(n)

  给定要查找的元素，返回元素的位置

  1. 从第一个元素开始查找，依次和查找的元素比较，若要查找的元素与之相等，返回i+1

  2. 若整个顺序表都没有要查找的元素，查找失败，返回false

• 插入（ASL=n/2）

  插入元素 插入位置i

    1. 判断插入的位置是否合法 1<=i<=(length+1)
  

  2. 判断顺序表是否满了，若满返回false
  3. 从n开始到i的元素依次向后移动一个位置(从后往前)
  4. 将插入的元素放入i位置
  5. 将顺序表的长度length+1

• 删除(ASL=(n-1)/2)

  删除某个元素 ，删除位置

      1. 判断i 是否合法  1<=i<=length,不合法返回false
         2. 合法，将删除元素的位置i到n,依次向前移动一个位置
         3. 讲顺序表长度length-1
  

链表

用一组任意的存储单元存储线性表的数据元素（逻辑上连续，物理不连续）

• 单链表：

image-20200403150956182

头指针 头节点 没有值 首元结点

单链表基本操作

    **单链表初始化**

       1. 生成一个新节点，作为头节点，用头节点L 指向头结点
          2. 头结点指针域置空

<img src="https://i.loli.net/2020/05/22/j5sxF7ynmG13Z8B.png" alt="image-20200403151547792" style="zoom: 50%;" />

带头节点判空 L.next==NULL

不带头节点判空 L==NULL

单链表取值（n-1）/2

1. 用指针p 指向首元结点，定义一个计数器j=1
2. 从首元结点开始依次向后查看每一个要查的元素 若 p->data==c，返回查找元素
3. 如果指针p 指向null还没有要查找的元素 返回false

单链表插入

1. 生成一个新结点，将数据域设置成E.
    2. 将一个指针p 指向插入元素之前
        3.  新节点的指针域zhi'xiang'g  S 为定义新节点  （s->next=p.next    p.next=s）

顺序表和单链表插入比较 如果插入数据量大 单链表好

如果要大量的查找 ，顺序表好

A

单链表删除

1. 将指针p 移动到删除结点前
2. 定义一个指针q 指向p的指针域
3. 将p的指针域指向q的指针域
4. 释放删除结点空间

循环链表(单项循环链表和双向循环链表)

对于循环链表如何判断 一个结点是否为最后一个结点

• p->next=L p指向的结点为最后一个结点

如何判断他是一个空表

• L->next==L; L的指针域还是L 哈哈 空表

如何判断一个单链表是最后一个结点

• p->next==null

• 双向循环链表

          双向链表插入
  

若指针移动到插入之前p,将指针q插入其中

1. q->prior=p;
2. q->next=p->next;
3. p->next->prior=q;
4. p->next=q;

          双向链表删除 

指针移动到删除结点上p

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

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

free(p)

存储密度

数据元素本身占用的存储量/结点结构占用的存储量

算法

线性表的合并

A和B两个线性表合并

A=(1,2,3,4)

B=(5,6,7,1,2)

1. 先取A的表长 m和B的表长n

2. 从B中第一个元素到最后一个元素查找，判定没一个元素是否在A中存在，若存在则插入

void merglist(List A,List B)
{
    m=Length(A); //A的长度m
    n=Length(B);//B的长度 n
    for(int i=1;i<=n;i++)   //遍历B的元素
    {
       GetElem(B,i,e);  //取B中元素 赋值给e
        
        if(!LocateElem(A,e))//如果e不存在A 顺序表中
        {
            ListInsert(A,++m,e);//将元素e 加入到A后面
        }    
    }
}

顺序有序表合并

void meList(List A,List B,List *C)
{
    m=Length(A);  //A的长度
    n=Length(B);  //B的长度
    LC=m+n;  //C的长度
    C=malloc(LC*sizeof(List));  // 初始化C
    pA=A.elem;  //将A的首地址指向pA
    pB=A.elem; //将B的首地址指向pB
    pc=C.elem; //将C的首地址指向pC
    pA_last=PA+m-1;   //将A的尾地址指向pA_last
    pB_last=PB+n-1;  //将B的尾地址指向pB_last
    while(pA<=pA_last&&pB<=pB_last)  //a表和b表都还没有到达表尾部
    {
        if(*pA<*pB)    // 依次摘取两节点 小的结点插入c中
        {
            *pc++=*pA++；
        }
        else{
            *pc++=*pB++； 
        }
        
    }
    
     while(pA<=pA_last) //如果A 没有查完，B 查完了，将A 剩下的元素插入C 后
     {
          *pc++=*pA++；
     }
    
      while(pA<=pA_last)
     {
          *pc++=*pB++；  //如果B  没有查完 ，A 查完了，将B 剩下的元素插入c后
     }
    
}