数据结构第二章：线性表

Abstract：线性表。

线性结构

1.特点：

• 存在唯一的首位元素a1
• 存在唯一的末位元素an
• 除第一个元素外，每个元素有且仅有一个直接前驱
• 除最后一个元素外，每个元素有且仅有一个直接后继

线性表

2.1 线性表的逻辑结构

1.线性表：由n(n>=0)个类型相同的数据元素（a1，a2,…,an）构成的有限序列。记作L = （a1，a2,…,an）。

• 同一类型的数据元素构成的线性结构
• 两种存储结构：顺序存储 & 链式存储
• 基本操作：插入，删除，检索
• 数据元素之间是一种线性关系，数据元素“一个接一个的排列”

2.表长（表的长度）：线性表中数据元素的数目。
3.空表：不含数据元素的线性表。

线性表的特点

• 有限性，元素个数有限，n > = 0
• 元素具有逻辑上的顺序性，在序列中各元素排列有先后次序（但不必按大小排列）
• 元素都是数据元素，每个表元素都是单个元素
• 元素的数据类型相同，意味着每个表元素占有相同数量的存储空间
• 元素具有抽象性：我们仅关注元素间的逻辑关系，不考虑元素表示什么内容

线性表、顺序表、链表的本质区别：线性表是一种**逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构**，两者属于不同层面的概念，因此不要将其混淆。

抽象数据类型的线性表

• ADT：三元组，包括数据对象，数据关系，基本操作。

  ADT List
  { 数据对象：D={ai|ai∈ElemSet,i=1,2,,…n,n>=0}
  数据关系：R1={| ai-1,ai∈D,i=2,,…n}
  基本操作：
  1.IniList(&L) //构造空表L。
  2.DestroyList(&L) //销毁线性表L
  3.ClearList(&L) //置L为空表
  4.ListEmpty(L) //判断L是否为空表。若L为空表，则返回true,否则返回false。
  5.ListLength(L) //求表L的长度
  6.GetElem(L,i,&e) //取元素ai,由e返回ai
  7.LocateElem(L,e,compare()) //查找符合条件的元素
  8.ListInsert(&L,i,e) //元素ai之前插入新元素e
  9.ListDelete(&L,i,&e) //删除第i个元素
  10.DeleteElem(&L,x) //删除元素值为x的元素

        … …     }ADT List   
  

为什么有的在L前加了&而有的没加：当操作对线性表或其中的元素作了修改，则是&L；若无修改，则为L。

• 定义：一个数学模型以及定义在该模型上的一组操作。
• 作用：抽象数据类型可以使我们更容易描述现实世界。
• 关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。

操作

• 基本操作
• 可利用基本操作组成更复杂的操作

  EG.将线性表Lb中的且不在线性表La中的数据元素合并到La中。

  //算法：判断两个线性表的长度——用循环结构将符合条件的元素插入La中（判断Lb中的每个元素是否在La中，不在的话就插入）        
  void union(List &La, List &Lb) //合并线性表 
  {
      La_len = ListLength(La); 
      Lb_len = ListLength(Lb);    
      for (i=1;i<=Lb_len;i++) 
      {
          GetElem(Lb,i,e) //取Lb的第i个数据元素赋给e；即依次取出所有Lb中的元素    
          if(!LocateElem(La,e,equal)) 
            ListInsert(La,++La_len,e); //判断e在La中是否存在，不存在则插入
      }
  }

2.2 线性表的顺序存储及运算（顺序表）

顺序表

• 顺序分配：将线性表中的元素依次存放到计算机存储器中一组连续地址的存储单元中，这种分配方式称为顺序分配或顺序映像。由此得到的存储结构称为顺序存储结构或向量(一维数组）。 逻辑上相邻的两个元素在物理位置上也相邻，但物理相邻不一定逻辑相邻。

一般形式：i——an——存储地址：LOC(i) = a1+（i-1） d （1<=i<=n）
a1：表的首地址/元素a1的地址；
d：1个数据元素所占存储单元的数目；
maxleng：最大长度，为某个常数 [序号maxleng——存储地址：b+(maxleng-1)p]

只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
需用一个变量last 记录当前线性表中最后一个元素在数组中的位置，即last 起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1.
线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。
假设表L的起始位置为LOC(A)，sizeof(ElemType)是每个数据元素所占用存储空间的大小。

• 顺序访问
• 随机访问

从结构性上考虑，通常将data 和last 封装成一个结构作为顺序表的类型：

typedef struct
{ datatype data[MAXSIZE];
   int last;
} SeqList;

定义一个顺序表：SeqList L ; 表长＝L.last+1，线性表中的数据元素a1至an分别存放在L.data[0]至L.data[L.last]中;
有时定义一个指向SeqList 类型的指针更为方便：
SeqList L ；L是一个指针变量，线性表的存储空间通过L=malloc(sizeof(SeqList)) 操作来获得, L中存放的是顺序表的地址. 表长表示为（L）.last或L－＞last+1，线性表的存储区域为L->data ，线性表中数据元素的存储空间为：
L－＞data[0] ~ L－＞data[L－＞last]。

• 线性表顺序结构在C语言中的定义（静态分配）?

#define maxleng 100    
typedef struct         
  { ElemType elem[maxleng]；//下标:0,1,...,maxleng-1   
    int length；            //表长 
   } SqList；  
  SqList La；  
   ..........  
 其中：typedef---别名定义，SqList----结构类型名    
       La----结构类型变量名    
       La.length---表长    
       La.elem[0]----a1    
       La.elem[La.length-1]---an

• 线性表顺序结构在C语言中的定义（动态分配）

 #define LIST_INIT_SIZE 100 
 #define LISTINCREMENT 10       
 typedef struct         
   { ElemType *elem；//存储空间基地址   
     int length；    //表长 
     int listsize;   //当前分配的存储容量   
                     //（以sizeof(ElemType)为单位   
    } SqList；  
   SqList Lb；  
其中：   typedef--别名定义，   SqList---结构类型名          
         Lb---结构类型变量名   Lb.length---表长     
         Lb.elem[0]---a1       Lb.elem[Lb.length-1]--an

顺序表上的基本运算

1.初始化

即构造一个空表；将L设为指针参数，首先动态分配存储空间，然后，将表中last 指针置为－1，表示表中没有数据元素。

SeqList *init_SeqList( )
{ SeqList *L;
L=malloc(sizeof(SeqList));
L->last=-1; return L;
}

2.插入运算

在表的第i个位置上插入一个值为x 的新元素，插入后使原表长为n的表:(a1，a2，… ，ai-1，ai，ai+1，… ，an)成为表长为n+1 表：(a1，a2，…，ai-1，x，ai，ai+1，…，an ) ，1<=i<=n+1。

步骤：移-让-放-改

• (1) 将ai～an 顺序向下移动，为新元素让出位置；
• (2) 将x 置入空出的第i个位置；
• (3) 修改last 指针(相当于修改表长)，使之仍指向最后一个元素。

表长Maxsize = L.last+1；L.last = Maxsize -1;
若L.last = Maxsize -1，则表满

int Insert_SeqList(SeqList *L，int i，datatype x)
{ int j;
if (L->last==MAXSIZE－1)
{ printf(＂表满＂); return(-1); } /*表空间已满，不能插入*/
if (i<1 || i>L->last+2) /*检查插入位置的正确性*/
{ printf(＂位置错＂);return(0); }
for(j=L->last;j>=i-1;j--)
L->data[j+1]=L->data[j]; /* 结点移动*/
L->data[i-1]=x; /*新元素插入*/
L->last++; /*last仍指向最后元素*/
return (1); /*插入成功，返回*/
}
//先处理异常情况，再处理循环

注意：

• (1) 顺序表中数据区域有MAXSIZE个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。
• (2) 要检验插入位置的有效性，这里i 的有效范围是：1<=i<=n+1，其中n 为原表长。
• (3) 注意数据的移动方向。

插入算法的时间性能分析：顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入x ，从ai 到an 都要向下移动一个位置，共需要移动n－i＋1个元素，而i 的取值范围为：1<= i<= n+1，即有n＋1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：

在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为Ｏ(n)

3. 删除运算DeleteList(L,i)

将表中第i 个元素从线性表中去掉，删除后使原表长为n 的线性表：
(a1，a2，… ，ai-1，ai，ai+1，…，an)成为表长为n－1 的线性表：(a1，a2，… ，ai-1， ai+1，… ，an)。i 的取值范围为：1<=i<=n 。

//算法：先判断元素ai的合法性——若不合法则返回Error/若合法则继续——定位ai元素（在第i-1号地址）并赋给变量e——用循环结构将ai后的所有元素往前挪一位（共L.length-1个元素；赋值法）
int ListDelete_Sq(SqList  &L,int I,ElemType &e)     
{if (i<1 || i>L.length)     
          return ERROR; 
 e=L.elem[i-1]; 
 for(j=i;j<=L.length-1;j++) 
	 L.elem[j-1]=L.elem[j]; 
 L.length--;  return OK;    
}

步骤：

• 将ai+1～an 顺序向上移动。
• 修改last指针(相当于修改表长)使之仍指向最后一个元素。

int Delete_SeqList(*SeqList *L, int i)
{int j;
if (i < 1 || i > L->last+1) /*检查空表及删除位置的合法性*/
{print ("不存在第i个元素"), return(0);}
for(j=i;j<=L->last;j++)
L->data[j-1]=L->data[j]; /*向上移动*/
L->last--;
return(1); /*删除成功*/}

注意：

• （1）删除第i个元素，i的取值为1<=i<=n ,否则第i个元素不存在，因此，要检查删除位置的有效性。
• （2）当表空时不能做删除，因表空时L->last的值为-1，条件（i<1 ||="" i="">L->last+1）也包括了对表空的检查。
• （3）删除ai 之后，该数据已不存在，如果需要，先取出ai ，再做删除。

删除算法的时间性能分析：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素ai+1～an 都要向上移动一个位置，共移动了n-i 个元素，所以平均移动数据元素的次数：

顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。

4.按值查找

线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。在顺序表中完成该运算最简单的方法是：从第一个元素a1 起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与x 相等的元素，返回-1。

int Location_SeqList(SeqList *L, datatype x)
{ int i=0;
while(i<=L.last && L->data[i]!= x)
i++;
if (i>L->last) return -1;
else return i; /*返回的是存储位置*/
}

主要运算是比较。显然比较的次数与x在表中的位置有关，也与表长有关。当a1=x 时，比较一次成功。当an=x 时比较n 次成功。平均比较次数为（n+1）/2，时间性能为O(n)。

顺序表应用举例

1.顺序表的划分

Q：将顺序表(a1，a2，… ，an) 重新排列为以a1 为界的两部分：a1 前面的值均比a1 小，a1 后面的值都比a1 大(这里假设数据元素的类型具有可比性, 不妨设为整型)，这一操作称为划分。a1 也称为基准。

思路：从第二个元素开始到最后一个元素，逐一向后扫描：

• （1）当前数据元素aI 比a1 大时，表明它已经在a1 的后面，不必改变它与a1 之间的位置，继续比较下一个。
• （2）当前结点若比a1 小，说明它应该在a1 的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。

{ int i,j;
datatype x,y;
x=L->data[0]; /* 将基准置入x 中*/
for(i=1;i<=L->last;i++)
if(L->data[i]<x) /*当前元素小于基准*/
{ y = L->data[i];
for(j=i-1;j>=0;j--) /*移动*/
L－>data[j+1]=L->data[j];
L->data[0]=y;
}
}

本算法中，有两重循环，外循环执行n－1次，内循环中移动元素的次数与当前数据的大小有关，当第ｉ个元素小于a1 时，要移动它上面的i-1个元素，再加上当前结点的保存及置入，所以移动i-1+2次，在最坏情况下，a1 后面的结点都小于a1 ，故总的移动次数为：

最坏情况下移动数据时间性能为Ｏ(ｎ２)

2.合并顺序表并按顺序排列

Q：有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。

算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。

void merge(SeqList A, SeqList B, SeqList *C)
{ int i,j,k;
i=0;j=0;k=0;
while ( i<=A.last && j<=B.last )
if (A.date[i]<B.date[j])
C->data[k++]=A.data[i++];
else C->data[k++]=B.data[j++];
while (i<=A.last )
C->data[k++]= A.data[i++];
while (j<=B.last )
C->data[k++]=B.data[j++];
C->last=k-1;
}

算法的时间性能是O(m+n)，其中m是A的表长，n是B的表长。

3.比较两个线性表的大小

Q：比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。A′和B′分别为A 和B 中除去最大共同前缀后的子表。

例如A=(x,y,y,z,x,z)， B=(x,y,y,z,y,x,x,z)，两表最大共同前缀为(x,y,y,z) 。则A′=（x,z）， B′=（y,x,x,z），若A′=B′= 空表，则A=B；若A′=空表且B′≠空表，或两者均不空且A′首元素小于B′首元素，则AB。

算法思路：首先找出A、B的最大共同前缀；然后求出A′和B′，之后在按比较规则进行比较，A>B 函数返回1；A=B返回0；A<B返回-1。算法如下：

int compare( A,B,m,n)
int A[],B[];
int m,n;
{ int i=0,j,AS[],BS[],ms=0,ns=0; /*AS,BS作为A′,B′*/
while (A[i]==B[i]) i++; /*找最大共同前缀*/
for (j=i;j<m;j++)
{ AS[j-i]=A[j];ms++; } /*求A′,ms为A′的长度*/
for (j=i;j<n;j++)
{ BS[j-i]=B[j];ns++; } /*求B′,ms为B′的长度*/
if (ms==ns&&ms==0) return 0;
else if (ms==0&&ns>0 || ms>0 && ns>0 && AS[0]<BS[0]) return –1;
else return 1;
}

算法的时间性能是O( m+n )

顺序结构的评价

优点：

• 随机存取结构，存取任何元素的时间都是一个常数，速度快
• 结构简单，元素逻辑相邻也物理相邻
• 不适用指针，节省存储空间

缺点：

• 插入和删除元素需要移动大量元素，消耗时间
• 需要一个连续的存储空间
• 插入元素可能发生“溢出”
• 自由区中的存储空间不能被其他数据占用/共享

2.3 线性表的链式存储结构及运算

• 顺序表：存贮特点是用物理上的相邻实现了逻辑上的相邻，要求用连续的存储单元顺序存储线性表中各元素，因此，对顺序表插入、删除时需要通过移动数据元素来实现，影响了运行效率。
• 链表：用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。

单链表

链表：通过一组任意的存储单元来存储线性表中的数据元素

为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai 之外，还需要和ai一起存放其后继ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点”。

• data：存放ai自身的信息
• next：存放ai的直接后继ai+1的地址（用指针存储地址；*next）

• 数据域：存放数据元素信息
• 指针域：存放其后继地址

链表：n个元素的线性表通过每个结点的指针域拉成了一个“链子”；链表由一个个结点构成。

单链表：每个结点只有一个指向后继的指针的链表

typedef struct node
{ datatype data;
struct node *next;
} LNode，*LinkList；

//定义头指针变量：
LinkList H；

注意：

• LNode是结点的类型，LinkList是指向Lnode类型结点的指针类型
• 最后一个结点没有后继, 其指针域必需置空
• 我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心
• 通常我们用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L、H 中， 头指针为“NULL”则表示一个空表

• 通常将标识一个链表的头指针说明为LinkList类型的变量，如LinkList L ; 当L有定义时，值要么为NULL，则表示一个空表；要么为第一个结点的地址，即链表的头指针；将操作中用到指向某结点的指针变量说明为LNode 类型，如LNode p， 则语句：

      p=malloc(sizeof(LNode))；
  

则完成了申请一块Lnode 类型的存储单元的操作，并将其地址赋值给变量p。

P所指的结点为p，p的类型为LNode型，所以该结点的数据域为(p).data 或p->data，指针域为(p).next 或p->next。free(p)则表示释放p 所指的结点。

单链表基本运算

1.建立单链表

(1)在链表的头部插入结点建立单链表：

链表：动态管理的存储结构；链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个结点，然后插在链表的头部。

因为是在链表的头部插入，故读入数据的顺序和线性表中的逻辑顺序是相反的。

LinkList Creat_LinkList1( )
{ LinkList L=NULL；/*空表*/
Lnode *s;
int x; /*设数据元素的类型为int*/
scanf(＂%d＂,&x);
while (x!=flag)
{ s=malloc(sizeof(LNode));
s->data=x;
s->next=L; L=s;
Scanf (＂%d＂,&x);
}
return L;
}

(2)在单链表的尾部插入结点建立单链表：

• 头插入与尾插入的区别：
  • 头插入：读入数据元素的顺序与生成链表中的元素顺序相反
  • 尾插入：使词序一致；每次将新结点插入到链表的尾部，所以需加入一个指针r 用来始终指向链表中的尾结点，以便能够将新结点插入到链表的尾部

算法思路：

初始状态：头指针H=NULL，尾指针r=NULL; 按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到r 所指结点的后面，然后r 指向新结点。H=NULL r=NULL /初始状态/

LinkList Creat_LinkList2( )
{ LinkList L=NULL;
Lnode *s,*r=NULL;
int x; /*设数据元素的类型为int*/
scanf(＂%d＂,&x);
while (x!=flag)
{ s=malloc(sizeof(LNode)); s->data=x;
if (L==NULL) L=s; /*第一个结点的处理*/
else r->next=s; /*其它结点的处理*/
r=s; /*r 指向新的尾结点*/
scanf(＂%d＂,&x);
}
if ( r!=NULL) r->next=NULL; /*对于非空表，最后结点的指针域放空指针*/
return L;
}

算法解释：

• 第一个结点的处理和其它结点不同，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针， 需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。
• “第一个结点”的问题在很多操作中都会遇到，如在链表中插入结点时，将结点插在第一个位置和其它位置是不同的，在链表中删除结点时，删除第一个结点和其它结点的处理也是不同的
• 头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理成为一致
• 头结点：数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空

2.求表长

算法思路：设一个移动指针ｐ和计数器ｊ，初始化后，ｐ所指结点后面若还有结点，ｐ向后移动，计数器加1。

(1)设L是带头结点的单链表(线性表的长度不包括头结点):

int Length_LinkList1 (LinkList L)
{ Lnode * p=L; /* p指向头结点*/
int j=0;
while (p->next)
{ p=p->next; j++ } /* p所指的是第j 个结点*/
return j;
}

(2)设L是不带头结点的单链表：

int Length_LinkList2 (LinkList L)
{ Lnode * p=L;
int j;
if (p==NULL) return 0; /*空表的情况*/
j=1; /*在非空表的情况下，p所指的是第一个结点*/;
while (p->next )
{ p=p->next; j++ }
return j;
}

不带头结点的单链表空表情况要单独处理，而带上头结点之后则不用。

时间复杂度均为O(n)。

3.查找操作

(1) 按序号查找Get_Linklist(L,i)：
算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止。没有第ｉ个结点时返回空。

Lnode * Get_LinkList(LinkList L, Int i);
/*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/
{ Lnode * p=L;
int j=0;
while (p->next !=NULL && j<i )
{ p=p->next; j++; }
if (j==i) return p;
else return NULL;
}

(2) 按值查找即定位Locate_LinkList(L,x)

算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止。找不到时返回空。算法如下：

Lnode * Locate_LinkList( LinkList L, datatype x)
/*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/
{ Lnode * p=L->next;
while ( p!=NULL && p->data != x)
p=p->next;
return p;
}

4.插入

(1)后插结点：

设p指向单链表中某结点，s指向待插入的值为x的新结点，将s插入到p的后面，插入示意图如图2.13。操作如下：

①s->next=p->next;
②p->next=s;

注意：两个指针的操作顺序不能交换。

(2)前插结点：

设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将s插入到p的前面，插入示意图如图，与后插不同的是：首先要找到p的前驱q，然后再完成在q之后插入s，设单链表头指针为L，操作如下：

q=L;
while (q->next!=p)
q=q->next; /*找*p的直接前驱*/
s->next=q->next;
q->next=s;

后插操作的时间复杂性为O(1)，前插操作因为要找p 的前驱，时间性能为O(n)；其实我们关心的更是数据元素之间的逻辑关系，所以仍然可以将s 插入到*p 的后面，然后将ｐ->data与s->data交换即可，这样即满足了逻辑关系，也能使得时间复杂性为O(1)。

(3)插入运算Insert_LinkList(L,i,x)

算法思路：
1.找到第i-1个结点；若存在继续2，否则结束
2.申请、填装新结点；
3.将新结点插入。结束。

算法如下：

int Insert_LinkList( LinkList L, int i, datatype x)
/*在单链表L的第i个位置上插入值为x的元素*/
{ Lnode * p,*s;
p=Get_LinkList(L,i-1); /*查找第i-1个结点*/
if (p==NULL)
{ printf(＂参数i错＂);return 0; } /*第i-1个不存在不能插入*/
else {
s=malloc(sizeof(LNode)); /*申请、填装结点*/
s->data=x;
s->next=p->next; /*新结点插入在第i-1个结点的后面*/
p->next=s
return 1;
}

5. 删除

(1)删除结点：

设p指向单链表中某结点，删除*p。操作示意图如图所示。

通过示意图可见，要实现对结点p的删除，首先要找到p的前驱结点*q，然后完成指针的操作即可。指针的操作由下列语句实现：

q->next=p->next;
free(p);

显然找p前驱的时间复杂性为O(n)。若要删除p的后继结点(假设存在)，则可以直接完成：

s=p->next;
p->next=s->next;
free(s);

该操作的时间复杂性为O(1) 。

(2)删除运算：Del_LinkList(L,i)

算法思路：
1.找到第i-1个结点；若存在继续2，否则结束；
2.若存在第i个结点则继续3，否则结束；
3.删除第i个结点，结束。

算法如下：
int Del_LinkList(LinkList L，int i)
/删除单链表L上的第i个数据结点/
{ LinkList p,s;
p=Get_LinkList(L,i-1); /查找第i-1个结点/
if (p==NULL)

{ printf(＂第i-1个结点不存在＂);return -1; }
else { if (p->next==NULL)
{ printf(＂第i个结点不存在＂);return 0; }
else
{ s=p->next; /s指向第i个结点/
p->next=s->next; /从链表中删除/
free(s); /释放s */
return 1;
}
算法2.13。算法2.13的时间复杂度为O(n)。

通过上面的基本操作我们得知：

• (1) 在单链表上插入、删除一个结点，必须知道其前驱结点。
• (2) 单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。

顺序表和链表的比较

顺序存储有三个优点：

(1) 方法简单，各种高级语言中都有数组，容易实现。
(2) 不用为表示结点间的逻辑关系而增加额外的存储开销。
(3) 顺序表具有按元素序号随机访问的特点。
(4)顺序表存储密度大

两个缺点：

(1) 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。
(2) 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

如何选取存储结构：

• 基于存储的考虑

顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。
顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对＂MAXSIZE＂要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于１的。

• 基于运算的考虑

在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。

• 基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。

循环链表

单循环链表：最后一个结点的指针域是空指针，若将该链表头指针置入该指针域，则使链表头尾结点相连，即构成单循环链表。（头尾相连，尾指针域指向头结点地址）

单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其它较大的变化。

• 对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表
• 有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R 来标识，可以使得操作效率得以提高

例如：对两个单循环链表H1 、H2 的连接操作，是将H2 的第一个数据结点接到H1 的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R1 、R2 来标识，则时间性能为O(1)

p= R1 –>next; /*保存R1 的头结点指针*/
R1->next=R2->next->next; /*头尾连接*/
free(R2->next); /*释放第二个表的头结点（因为一个链表只能有一个头结点，而头结点本身作用在于存放第一个结点数据域的地址）*/
R2->next=p; /*组成循环链表*/

双向链表

• 单链表的结点只有一个指向后继结点的指针域，因此若已知某结点的指针为p，其后继结点的指针则为p->next ，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n)，如果也希望找前驱的时间性能达到O(1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，结点的结构为如图所示，用这种结点组成的链表称为双向链表

typedef struct dlnode
{ datatype data;
struct dlnode *prior,*next;
}DLNode,*DLinkList;

和单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构。

设p 指向双向循环链表中的某一结点，即p 中是该结点的指针，则p->prior->next 表示的是p 结点之前驱结点的后继结点的指针，即与p 相等；类似，p->next->prior 表示的是p 结点之后继结点的前驱结点的指针，也与p 相等，所以有以下等式：

双向链表中结点的插入：设p 指向双向链表中某结点，s 指向待插入的值为x 的新结点，将s 插入到p 的前面，插入示意图如图所示。操作如下：

1 s->prior=p->prior;
2 p->prior->next=s;
3 s->next=p;
4 p->prior=s;

双向链表中结点的删除：
设p 指向双向链表中某结点，删除*p。
操作如下：
①p->prior->next=p->next;
②p->next->prior=p->prior;
free(p);

静态链表

优点：采用静态空间分配方式，且插入和删除操作时不需要移动元素

规模较大的结构数组sd[MAXSIZE] 中有两个链表:

其中链表SL是一个带头结点的单链表，表示了线性表(a1, a2, a3, a4, a5)，而另一个单链表AV是将当前sd 中的空结点组成的链表。

#define MAXSIZE … /*足够大的数*/
typedef struct
{datatype data;
int next;
}SNode; /*结点类型*/
SNode sd[MAXSIZE];
int SL,AV; /*两个头指针变量*/

这种链表的结点中也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组的下标)，称之为静态指针，这种链表称之为静态链表，空指针用-1表示，因为上面定义的数组中没有下标为-1的单元。

SL是用户的线性表，AV模拟的是系统存储池中空闲结点组成的链表，当用户需要结点时，例如向线性表中插入一个元素，需自己向AV申请，而不能用系统函数malloc来申请，相关的语句为：

 if(AV!=-1)
{ t=AV;
AV=sd[AV].next;
}

所得到的结点地址(下标)存入了t 中；不难看出当AV表非空时，摘下了第一个结点给用户。当用户不再需要某个结点时，需通过该结点的相对地址t 将它还给AV，相关语句为： sd[t].next=AV;AV=t;而不能调用系统的free 函数。交给AV表的结点链在了AV的头部。

下面通过线性表插入这个例子看静态链表操作

在带头结点的静态链表SL的第i个结点之前插入一个值为x的新结点。设静态链表的存储区域sd为全局变量。

int Insert_SList( int SL, datatype x, int i)
{ int p,s;
p=SL; j=0;
while(sd[p].next!=-1 && j<i-1)
{p=sd[p].next;j++;} /*找第i-1个结点*/
if(j==i-1)
{ if(AV!=-1) /*若AV表还有结点可用*/
{t=AV;
AV=sd[AV].next; /*申请、填装新结点*/
sd[t].data=x;
sd[t].next=sd[p].next; /*插入*/
sd[p].next=t;
return 1; /*正常插入成功返回*/
}
else{printf(＂存储池无结点＂);return 0;}
/*未申请到结点，插入失败*/
else{printf(＂插入的位置错误＂);return -1;}
/*插入位置不正确，插入失败*/
}

单链表应用举例

1.已知单链表H，写一算法将其倒置。即实现如图操作。(a)为倒置前，(b)为倒置后。

算法思路：从右往左依次取原链表中的每个结点，将其作为第一个结点插入新链表，指针p用来指向当前结点，p为空时结束。

void reverse (Linklist H)
{ LNode *p;
p=H->next; /*p指向第一个数据结点*/
H->next=NULL; /*将原链表置为空表H*/
while (p)
{ q=p; p=p->next;
q->next=H->next; /*将当前结点插到头结点的后面*/
H->next=q;
}
}

该算法只是对链表中顺序扫描一边即完成了倒置，所以时间性能为O(n)。

2.已知单链表L，写一算法，删除其重复结点，即实现如图操作。(a)为删除前，(b)为删除后。

算法思路：用指针p 指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之；p 指向下一个；依此类推，p 指向最后结点时算法结束。

void pur_LinkList( LinkList H )
{
	LNode *p, *q, *r;
	p = H->next;                                    /*p指向第一个结点*/
	if ( p == NULL )
		return;
	while ( p->next )
	{
		q = p;
		while ( q->next )                       /* 从*p的后继开始找重复结点*/
		{
			if ( q->next->data == p->data )
			{
				r	= q->next;      /*找到重复结点，用r指向，删除*r */
				q->next = r->next; 
				free( r );
			} /*if*/
			else q = q->next;
		} /*while(q->next)*/
		p = p->next;                            /*p指向下一个，继续*/
	} /*while(p->next)*/
}

该算法的时间性能为O(n2)

3.设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。

算法思路：利用A、B两表有序的特点，依次进行比较，将当前值较小者摘下，插入到C表的头部，得到的C表则为递减有序的。

LinkList merge( LinkList A, LinkList B )
/*设A、B均为带头结点的单链表*/
{
	LinkList C; LNode *p, *q;
	p	= A->next; q = B->next;
	C	= A; /*C表的头结点*/
	C->next = NULL;
	free( B );
	while ( p && q )
	{
		if ( p->data < q->data )
		{
			s = p; p = p->next;
		}else                   { s = q; q = q->next; } /*从原AB表上摘下较小者*/
		s->next = C->next; /*插入到C表的头部*/
		C->next = s;
	}                                                       /*while */
	if ( p == NULL )
		p = q;
	while ( p ) /* 将剩余的结点一个个摘下，插入到C表的头部*/
	{
		s	= p; p = p->next;
		s->next = C->next;
		C->next = s;
	}
}

该算法的时间性能为O(m+n)

纠错

p = H -> next :指向H表的首结点

前后之分：next方向是后，prior方向是前。

在单链表中，增加一个头节点的目的是为了方便运算的实现。

将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为 O(n)_。

在一个长度为n（n>1）的带头节点的单链表上，另设有尾指针r（指向尾节点），执行删除单链表的尾节点_操作与链表的长度有关。

已知一个长度为n的单链表中所有节点是递增有序的，找最小值节点的算法的时间复杂度为 O(1).

带表头结点的双循环链表L为空表的条件是 :L -> next == L

某线性表最常用的操作是在尾元素之后插入一个元素和删除尾元素，则采用 循环双链表_ 存储方式最节省运算时间

如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用只有开始数据节点指针没有尾节点指针的循环双链表_。

在长度为n的 只有表头指针的不带表头节点的循环单链表_ 上，删除第一个元素，其算法的时间复杂度为O(n)。

在单链表中，要删除某一指定的节点，必须找到该节点的 _前驱 节点。

求一个单链表长度的算法的时间复杂度为 O(n)_。

疑问？

循环单链表与循环双链表的区别？

双链表的插入删除操作算法？