学步园

顺序表上实现的基本运算

1.表的初始化
   void InitList（SeqList *L）
     {\\顺序表的初始化即将表的长度置为0
            L-＞length=0；
    }

2.求表长
    int ListLength（SeqList *L）
       { \\求表长只需返回L-＞length
          return L-＞length;
      }

3.取表中第i个结点
  DataType GetNode（L，i）
      {\\取表中第i个结点只需返回和L-＞data[i-1]即可
          if (i<1||i> L-＞length-1)
                  Error("position error")；
          return L-＞data[i-1]；
       }

4.查找值为x的结点
  【参见参考书】

5. 插入
（1） 插入运算的逻辑描述
　　线性表的插入运算是指在表的第i（1≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表： 
          （a1，…，ai-1，ai，…an）
变成长度为n+1的线性表： 
          （a1，…，ai-1，x，ai，…an）
注意：
　    ① 由于向量空间大小在声明时确定，当L-＞length≥ListSize时，表空间已满，不可再做插入操作
    　② 当插入位置i的值为i＞n或i＜1时为非法位置，不可做正常插入操作

（2） 顺序表插入操作过程
　　在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。
    　具体过程见【动画演示】

（3）具体算法描述
   void InsertList(SeqList *L，DataType x，int i)
     {//将新结点 x插入L所指的顺序表的第i个结点ai的位置上
       int j;
       if (i<1||i>L->length+1)
           Error("position error");//非法位置，退出运行
       if (L->length>=ListSize)
           Error("overflow");     //表空间溢出，退出运行
       for(j=L->length-1;j>=i-1;j--)
            L->data[j+1]=L->data[j];//结点后移
       L->data[i-1]=x;      //插入x
       L->Length++;        //表长加1
     }

（4）算法分析
① 问题的规模
　     表的长度L-＞length（设值为n）是问题的规模。
② 移动结点的次数由表长n和插入位置i决定
　     算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。
     当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1)
     当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n)
③ 移动结点的平均次数Eis(n) 
      
          
  其中：
    　在表中第i个位置插入一个结点的移动次数为n-i+1
    　pi表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置（1≤i≤n+1）上的插入结点的机会是均等的，则
                 p1=p2=…=pn+1=1/(n+1)

    　因此，在等概率插入的情况下，

       
    即在顺序表上进行插入运算，平均要移动一半结点。

单链表

1、链接存储方法
    　链接方式存储的线性表简称为链表（Linked List）。
    　链表的具体存储表示为：
　　① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
　　② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
注意：
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

2、链表的结点结构
  ┌──┬──┐
  │data│next│
  └──┴──┘ 
      　data域--存放结点值的数据域
      　next域--存放结点的直接后继的地址（位置）的指针域（链域）
注意：
   　 ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
    　②每个结点只有一个链域的链表称为单链表（Single Linked List）。
【例】线性表（bat，cat，eat，fat，hat，jat，lat，mat）的单链表示如示意图

3、头指针head和终端结点指针域的表示
    　单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。
注意：
    　链表由头指针唯一确定，单链表可以用头指针的名字来命名。
【例】头指针名是head的链表可称为表head。
　　终端结点无后继，故终端结点的指针域为空，即NULL。

4、单链表的一般图示法
    　由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可以表示为下图形式。

      
5、单链表类型描述
  typedef char DataType; //假设结点的数据域类型为字符
  typedef struct node{   //结点类型定义
       DataType data;    //结点的数据域
       struct node *next;//结点的指针域
     }ListNode;
  typedef ListNode *LinkList;
  ListNode *p;
  LinkList head;
  注意：
    　①LinkList和ListNode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确）
    　②LinkList类型的指针变量head表示它是单链表的头指针
    　③ListNode *类型的指针变量p表示它是指向某一结点的指针

6、指针变量和结点变量

┌────┬────────────┬─────────────┐ 
│　　　　│　　　　指针变量　　　　│　　　　 结点变量  　　　 │
├────┼────────────┼─────────────┤
│  定义  │在变量说明部分显式定义  │在程序执行时，通过标准    │
│        │                        │函数malloc生成            │
├────┼────────────┼─────────────┤
│  取值  │ 非空时，存放某类型结点 │实际存放结点各域内容      │
│        │的地址                  │                          │
├────┼────────────┼─────────────┤
│操作方式│ 通过指针变量名访问     │ 通过指针生成、访问和释放 │
└────┴────────────┴─────────────┘
   
①生成结点变量的标准函数
    　p=( ListNode *)malloc(sizeof(ListNode))；
//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中
②释放结点变量空间的标准函数 
    　free(p)；//释放p所指的结点变量空间
③结点分量的访问 
　    利用结点变量的名字*p访问结点分量
 方法一：(*p).data和(*p).next
 方法二：p-﹥data和p-﹥next
④指针变量p和结点变量*p的关系 
    指针变量p的值——结点地址
    　结点变量*p的值——结点内容
    　(*p).data的值——p指针所指结点的data域的值
    　(*p).next的值——*p后继结点的地址
　　*((*p).next)——*p后继结点
注意：
   　 ① 若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。
   　 ② 有关指针类型的意义和说明方式的详细解释，【参考C语言的有关资料】。

单链表的运算

1、建立单链表
    　假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符'\n'为输入条件结束标志符。动态地建立单链表的常用方法有如下两种：

（1） 头插法建表
① 算法思路
    　从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。
    

    　具体方法【参见动画演示】
注意：
    　该方法生成的链表的结点次序与输入顺序相反。

② 具体算法实现
    LinkList CreatListF(void)
      {//返回单链表的头指针
          char ch;
          LinkList head;//头指针
          ListNode *s;  //工作指针
          head=NULL;    //链表开始为空
          ch=getchar(); //读入第1个字符
          while(ch!='\n'){
              s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
              s->data=ch;   //将读入的数据放入新结点的数据域中
              s->next=head;
              head=s;
              ch=getchar();  //读入下一字符
            }
          return head;
       } 

广义表的概念

    　广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

循环链表（Circular Linked List）

    　循环链表是一种首尾相接的链表。

1、循环链表
（1）单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。

（2）多重链的循环链表——将表中结点链在多个环上。

2、带头结点的单循环链表

注意：
    　判断空链表的条件是head==head->next;

3、仅设尾指针的单循环链表
    　用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。带尾指针的单循环链表可见下图。

          
注意：
    　判断空链表的条件为rear==rear->next;

4、循环链表的特点
    　循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
【例】在链表上实现将两个线性表（a1，a2，…，an）和（b1，b2，…，bm）连接成一个线性表（a1，…，an，b1，…bm）的运算。

    分析：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。

       
    　相应的算法如下：
      LinkList Connect(LinkList A,LinkList B)
       {//假设A，B为非空循环链表的尾指针
          LinkList p=A->next;//①保存A表的头结点位置
          A->next=B->next->next;//②B表的开始结点链接到A表尾
          free(B->next);//③释放B表的头结点
          B->next=p;//④
          return B;//返回新循环链表的尾指针
    } 
注意：
    　①循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
   　②在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。

双链表

1、双向链表（Double Linked List）
    　双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。
   
注意：
    　①双链表由头指针head惟一确定的。
    　②带头结点的双链表的某些运算变得方便。
    　③将头结点和尾结点链接起来，为双（向）循环链表。

2、双向链表的结点结构和形式描述
①结点结构(见上图a)
      
②形式描述 
    typedef struct dlistnode{
         DataType data;
         struct dlistnode *prior,*next;
      }DListNode;
    typedef DListNode *DLinkList;
    DLinkList head;

3、双向链表的前插和删除本结点操作
    　由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。
①双链表的前插操作
      
    void DInsertBefore(DListNode *p,DataType x)
      {//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
        DListNode *s=malloc(sizeof(DListNode));//①
        s->data=x;//②
        s->prior=p->prior;//③
        s->next=p;//④
        p->prior->next=s;//⑤
        p->prior=s;//⑥
       }
②双链表上删除结点*p自身的操作
      
    void DDeleteNode(DListNode *p)
      {//在带头结点的双链表中，删除结点*p，设*p为非终端结点
          p->prior->next=p->next;//①
          p->next->prior=p->prior;//②
          free(p);//③
      } 
注意：
    　与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。
    　上述两个算法的时间复杂度均为O(1)。

顺序表和链表的比较

    顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：
┌───┬───────────────┬───────────────┐
│      │       　　顺序表　　　       │　　       链表　　　         │
├─┬─┼───────────────┼───────────────┤
│基│分│静态分配。程序执行之前必须明确│动态分配只要内存空间尚有空闲，│
│于│配│规定存储规模。若线性表长度n变 │就不会产生溢出。因此，当线性表│
│空│方│化较大，则存储规模难于预先确定│的长度变化较大，难以估计其存储│ 
│间│式│估计过大将造成空间浪费，估计太│规模时，以采用动态链表作为存储│
│考│  │小又将使空间溢出机会增多。    │结构为好。                    │
│虑├─┼───────────────┼───────────────┤
│  │存│为1。当线性表的长度变化不大， │<1                            │
│  │储│易于事先确定其大小时，为了节约│                              │
│  │密│存储空间，宜采用顺序表作为存储│                              │
│  │度│结构。                        │                              │
├─┼─┼───────────────┼───────────────┤
│基│存│随机存取结构，对表中任一结点都│顺序存取结构，链表中的结点，需│
│于│取│可在O（1）时间内直接取得      │从头指针起顺着链扫描才能取得。│
│时│方│线性表的操作主要是进行查找，很│                              │
│间│法│少做插入和删除操作时，采用顺序│                              │
│考│  │表做存储结构为宜。            │                              │
│虑├─┼───────────────┼───────────────┤
│  │插│在顺序表中进行插入和删除，平均│在链表中的任何位置上进行插入和│
│  │入│要移动表中近一半的结点，尤其是│删除，都只需要修改指针。对于频│
│  │删│当每个结点的信息量较大时，移动│繁进行插入和删除的线性表，宜采│
│  │除│结点的时间开销就相当可观。    │用链表做存储结构。若表的插入和│
│  │操│                              │删除主要发生在表的首尾两端，则│
│  │作│                              │采用尾指针表示的单循环链表为宜│
└─┴─┴───────────────┴───────────────┘

    存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即

    存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）

1、广义表定义
    　广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。
  其中：
    　①ai--或者是原子或者是一个广义表。
　  　②广义表通常记作：
              Ls=( a1，a2，…，ai，…，an)。
　　  ③Ls是广义表的名字，n为它的长度。
　 　 ④若ai是广义表，则称它为Ls的子表。
  注意：
    　①广义表通常用圆括号括起来，用逗号分隔其中的元素。
    　②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
    　③若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a1，a2，…，an)称为Ls的表尾。
   　 ④广义表是递归定义的

2、广义表表示
（1）广义表常用表示
　　① E=()
     　E是一个空表，其长度为0。
　　② L=(a，b)
     　L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表
　　③ A=(x，L)=(x，(a，b))
     　A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。
　　④ B=(A，y)=((x，(a，b))，y)
　     B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。
　　⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
     　C的长度为2，两个元素都是子表。
　　⑥ D=(a，D)=(a，(a，(a，(…))))
     　D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。

（2）广义表的深度
　　一个表的"深度"是指表展开后所含括号的层数。
  【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。

（3）带名字的广义表表示
    　如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：
①E()
②L(a，b)
③A(x，L(a，b))
④B(A(x，L(a，b))，y)
⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))
⑥D(a，D(a，D(…)))

（4）广义表的图形表示
（a）广义表的图形表示：
   　 ①图中的分支结点对应广义表
   　 ②非分支结点一般是原子
    　③但空表对应的也是非分支结点。
　　【例】下图给出了几个广义表的图形表示。

             
（b）广义表的图形形状划分： 
　　 ①与树对应的广义表称为纯表，它限制了表中成分的共享和递归
　 　②允许结点共享的表称再入表
  【例】上图(d),子表A是共享结点，它既是C的一个元素，又是子表B的元素；
　　 ③允许递归的表称为递归表
  【例】上图(e)，表D是其自身的子表。

（5）递归表、再人表、纯表、线性表之间的关系满足：
       
  　  广义表不仅是线性表的推广，也是树的推广。

3、广义表运算
    　由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图(见第7章)建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。
    　在此，只讨论广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。
    　根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。
  【例】
      head(L)=a， tail(L)=(b)
      head(B)=A， tail(B)=(y)
  由于tail(L)是非空表，可继续分解得到：
      head(tail(L))=b， tail(tail(L))=()
  对非空表A和(y)，也可继续分解。
  注意:
    　广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。