数据结构知识点（2）——线性表

content
{:toc}

线性表的定义和特点

线性表：由n（n≥0）个数据特性相同的元素构成的有限序列。
特点：
① 存在唯一的一个被称为“第一个”的数据元素；
② 存在唯一的一个被称为“最后一个”的数据元素；
③ 除第一个之外，结构中的每个数据元素均只有一个前驱；
④ 出最后一个之外，结构中的每个数据元素均只有一个后继。

线性表的类型定义

ADT List{
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,…,n, n≥0 }
数据关系：R1＝{ |ai-1 ,ai∈D, i=2,…,n } i是位序
基本操作：
InitList(&L){构造空的线性表L}
Destroy（&L）{销毁}
ListEmpty（L）{若L为空返回TRUE}
ListLength（L）{返回L中的元素个数，即表长}
PriorElem（L,cur_e,&pre_e）{cur_e为一个元素且不是第一个，则用pre_e返回它的前驱}
NextElem（L,cur_e,&next_e）
GetElem(L,i,&e){用e返回L中第i个元素的值}
LocateElem（L,e,compare()）{返回L中第一个与e满足compare()的元素位序，否则返回0}
ListTraverse（L,visit()）{依次对L的每个元素调用visit()函数}
ClearList（&L）{置空}
PutElem（&L，i,e）{把e覆盖第i个位置，是改变元素，不是插入}
ListInsert（&L,i,e）{插入的位置是i的前面}
ListDelete(&L,i,&)
}ADT List

线性表的顺序表示和实现

线性表的顺序存储表示

线性表的顺序存储表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，通常也称这种存储结构额线性表为顺序表。
只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

由于线性表的长度可变，且所需最大的存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组表示线性表。

//---顺序表的存储结构---    
#define MAXSIZE 100    //顺序表可能达到的最大长度    
typedef struct
{
&nbsp;&nbsp;ElemType *elem;    //存储空间的基地址，ElemType可由用户自定义
&nbsp;&nbsp;int length;    //当前长度
}SqList;    //顺序表的结构类型为SqList

案例一：多项式的顺序存储结构类型定义

#define MAXSIZE 100    //顺序表可能达到的最大长度    
typedef struct
{
&nbsp;&nbsp;float coef;    //系数
&nbsp;&nbsp;float expn;    //指数
}Polynomial;
typedef struct
{
&nbsp;&nbsp;Polynomial *elem;    //存储空间的基地址，Polynomial由用户自定义
&nbsp;&nbsp;int length;    //当前长度
}SqList;    //顺序表的结构类型为SqList

案例二：图书数据的顺序存储结构类型定义

#define MAXSIZE 10000    //图书表可能达到的最大长度    
typedef struct    //图书信息定义
{
  char no[20];    //图书ISBN
  char name[50];  //图书名字
}Book;
typedef struct
{
  Book *elem;    //存储空间的基地址，Book由用户自定义
  int length;    //当前长度
}SqList;    //顺序表的结构类型为SqList

在上述定以后，可通过变量定义语句SqList L;将L定义成SqList类型的变量；
使用L.elem[i-1]访问序号为i的图书记录。

顺序表中基本操作的实现

初始化

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

或者：

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

销毁

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

清空

void ClearList(SqList &L) 
{
   L.length=0;                //将线性表的长度置为0
}

线性表长度

int GetLength(SqList L)
{
   return (L.length);             
}

判断线性表是否为空

int IsEmpty(SqList L)
{
  if (L.length==0) return 1;      
   else return 0;
}

取值

//根据指定位置，获取相应位置数据元素的内容
int GetElem(SqList L,int i,ElemType &e)
{
  if (i<1||i>L.length) return ERROR;   
   //判断i值是否合理，若不合理，返回ERROR
  e=L.elem[i-1];   //第i-1的单元存储着第i个数据
  return OK;
}

查找

int LocateELem(SqList L,ElemType e)
{
  for (i=0;i< L.length;i++)
      if (L.elem[i]==e) return i+1;                
  return 0;
}

插入

Status ListInsert_Sq(SqList &L,int i ,ElemType e){
   if(i<1 || i>L.length+1) return ERROR;	         //i值不合法
   if(L.length==MAXSIZE) return ERROR;    //当前存储空间已满     
   for(j=L.length-1;j>=i-1;j--) 
       L.elem[j+1]=L.elem[j];    //插入位置及之后的元素后移
    L.elem[i-1]=e;                     //将新元素e放入第i个位置
  ++L.length;		     	//表长增1
  return OK;
}

删除

Status ListDelete_Sq(SqList &L,int i,ElemType &e){
   if((i<1)||(i>L.length)) return ERROR;	 //i值不合法
   e=L.elem[i-1];                              //将欲删除的元素保留在e中
  for (j=i;j<=L.length-1;j++)                   
　  　L.elem[j-1]=L.elem[j];       //被删除元素之后的元素前移  
   --L.length;               	      //表长减1
  return OK;
}

线性表的链式表示和实现

单链表的定义和表示

结点：存储本身的信息以及存储指示其后继信息的存储映像；
数据域：存储数据元素信息的域称为数据域；
指针域：存储直接后继存储位置的域；
n个结点链接成一个链表，又由于此链表的每个结点只包含一个指针域，故又称线性链表或单链表；
链表分为：单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表；
其中单链表、循环链表和双向链表用于实现线性表的链式存储，其他形式多用于实现树和图等非线性结构；

单链表时非随机存取的存储结构，取第i个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构。

//---单链表的存储结构---
typedef struct LNode{
     ElemType   data;       //数据域
     struct LNode  *next;   //指针域
}LNode,*LinkList;   // *LinkList为Lnode类型的指针

LinkList与LNode本质上是等价的。通常使用LinkList定义单链表，强调定义的是某个单链表的头指针；
用LNode定义指向单链表中任一结点的指针变量。

链表增加头结点的作用：
（1）便于首元结点的处理：首元结点地址保存在头结点的指针域中，使其和其他数据元素操作一样；
（2）便于空表和非空表的统一处理：当不设头结点时，假设L为单链表的头指针，则当单链表的长度n为0的空表时，L指针为空（L==NULL）；当增加头结点后，无论链表是否为空，头指针都是指向头结点的非空结点，即若为空表，头结点的指针域为空（L->next==NULL)；

单链表基本操作的实现

初始化

Status InitList_L(LinkList &L){ 
   L=new LNode;                    	
   L->next=NULL;　　　　　
   return OK; 
}

销毁

Status DestroyList_L(LinkList &L){
    LinkList p;
       while(L)
        {
            p=L;  
            L=L->next;
            delete p;  
        }
     return OK;
 }

清空

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

求表长

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

判断是否为空

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

取值

Status GetElem_L(LinkList L,int i,ElemType &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 L，Elemtype e) { 
  p=L->next; 
  while(p &&p->data!=e)  
        p=p->next;                		
  return p; 	//返回L中值为e的数据元素的位置，查找失败返回NULL 
}

插入

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

删除

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

创建单链表（前插法）

void CreateList_F(LinkList &L,int n){ 
     L=new LNode; 
      L->next=NULL; //先建立一个带头结点的单链表 
      for(i=n;i>0;--i){ 
        p=new LNode; //生成新结点 
        cin>>p->data; //输入元素值 
        p->next=L->next;L->next=p; 	//插入到表头 
     } 
}//CreateList_F

创建单链表（后插法）

void CreateList_L(LinkList &L,int n){ 
      //正位序输入n个元素的值，建立带表头结点的单链表L 
      L=new LNode; 
      L->next=NULL; 	
      r=L; 	//尾指针r指向头结点 
      for(i=0;i<n;++i){ 
        p=new LNode;	　	//生成新结点 
        cin>>p->data;   		//输入元素值 
        p->next=NULL; r->next=p; 	    	//插入到表尾 
        r=p; 	//r指向新的尾结点 
      } 
}//CreateList_L

循环链表

循环链表：最后一个结点的指针域指向头结点，形成一个环，因此从表中任一结点出发均可找到表中其他结点。
循环单链表的操作和单链表基本一致，差别在于：当链表遍历时，判别当前指针p是否指向表尾的终止条件不同。在单链表中，判断条件为p!=NULL或p->next!=NULL再循环单链表中判断条件为p!=L或p->next!=L
循环链表的合并

双向链表

//---双向链表的存储结构---
typedef struct DuLNode{
    ElemType   data;              
    struct DuLNode  *prior;  
    struct DuLNode  *next;  
}DuLNode, *DuLinkList

双向循环链表

双向链表的插入

Status ListInsert_DuL(DuLinkList &L,int i,ElemType 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;
}

双向链表的删除

Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
   if(!(p=GetElemP_DuL(L,i)))     return ERROR;
   e=p->data;
   p->prior->next=p->next;     ①
   p->next->prior=p->prior;    ②
   delete p; 
   return OK;
}