数据结构——线性表(中--单链表)

四、链表

1.链式存储结构的特点

• （1）存储空间为任意的（连续，或不连续）
• （2）在存储每个数据元素的值的同时，附加存储与该元素相关的关系信息。

2.单链表

1)单链表的结点：数据域+指针域

2)单链表的2种形式：

• 不带头结点
• 带头结点

3)单链表基本操作的实现

-1- 初始化操作   InitLinkList(&L)

• 不带头结点的空单链表 L=NULL
• 带头结点的空单链表  L->next=NULL

Status InitLinkList( LinkList &L )
{ 
　   L = (LinkList)malloc(sizeof(LNode));     
       if( !L ) return OVERFLOW;            
       L->next = NULL;                    
       return OK; 
}

-2- 求表长操作   listLength(&L)

int listLength(LinkList L)
{   
　   LNode *p = L;                  
  　 int j = 0;                    
  　 while( p->next ){             
　          p = p->next;              
         　j ++;                    
　   }
  　 return  j; 
}

-3- 取元素操作  getElem(L, i, &e)

Status getElem(LinkList L, int i, LElemType &e)
{  
   　LNode *p=L->next;  
  　 int j=1 ; 
  　 while(p && j<i)
    {  
　　      p = p->next; 
          j++ ;
  　 }  
  　 if (p&&j==i) 
    {   
         e = p->data;  
         return OK;  
      }
  　 else  return ERROR;   
}

-4- 按值查找   locateElem(L, e)

LinkList locateElem(LinkList L, LElemType e)
{ 
   　LNode *p=L->next;               
   　while(  p && !equal(p->data, e)  )           
         　   p = p->next; 
  　 if( p ) return p;                    
   　else return NULL;                
}

-5- 插入操作  listInsert(&L, i, e)

Status listInsert(LinkList &L, int i, LElemType e)
{
   　LNode *p = L, *q;   
　   int j = 0;           
　   while (j<i-1&&p->next){  p=p->next;  j++;  } 
  　 if( j==i-1 ) {      
　　      q=(LNode*)malloc(sizeof(LNode));     
     　　 if(!q) return OVERFLOW;
     　　 q->data=e;                         
     　　 q->next=p->next;   
　　      p->next=q;
　　      return OK; 
  　 } 
  　 else return ERROR;                    
}

-6- 删除操作  listDelete(&L, i, &e)

Status listDelete(LinkList &L, int i, LElemType &e)
{ 
  　LNode *p = L, *q; 
  　 int j = 0;
   　while( j<i-1&&p->next ){ p=p->next; j++; } 
  　 if( j==i-1&&p->next ) {  
      　    q=p->next;
　　      p->next=q->next;　　
     　　 e=q->data;        
　　      free(q);  return OK;
   　}
  　 else return ERROR;
}

-7- 单链表的建立    creatList(&L, n)

• 正序创建 —— 尾插法

• void createList1(LinkList &L, int n)
  {  
     　LNode *p,*r; 
     　int i;
     　L=(LinkList)malloc (sizeof(LNode));     
     　r=L;                                
    　 for(i=1; i<=n; i++)
      {    
  　　      p=(LNode*)malloc(sizeof(LNode));    
        　　inputListElem(p->data);             
        　　r->next=p;   r=p;                             
     　}
  　   r->next=NULL;                       
  }
  
  

• 逆序创建 —— 头插法

• void createList2(LinkList &L, int n)
  {
      int i;
      LNode *p;
      L=(LinkList)malloc(sizeof(LNode)); 
      L->next=NULL; 　           
      for(i=1; i<=n; i++) 
      {
       　　 p=(LNode*)malloc(sizeof(LNode));   
            inputListElem(p->data);            
            p->next=L->next;                 
            L->next=p;       
       }
  }
  

3.双向链表

(1)双向链表的类型定义

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

(2)双向链表的基本操作的实现

-1- 初始化  InitDLinkList(&L)

Status InitDLinkList(DLinkList &L){ 
　   L=( DLinkList )malloc( sizeof( DLNode ) );     
       if( !L ) return OVERFLOW;            
       L->next = L->prior = NULL ;                    
       return OK; 
}

-2- 判空、求长度、取元素等操作

与单链表一致，把前驱结点忽略即可

-3- 插入   listInsert(&L, i, e)  

Status listInsert( DLinkList &L, int i, LElemType e ){
  　DLNode *p = L,*q;
      int j = 0;
  　while( j<i-1 && p->next ) {   p=p->next;   j++; } 
  　if( j==i-1){               
          q=( DLNode *) malloc( sizeof (DLNode) );
          if(!q) return OVERFLOW;
     　 q->data=e; 
          q->next=p->next;                           
          q->prior=p; 
          if(p->next)p->next->prior=q;
           p->next=q;
 　      return OK;　
      }
  　else return ERROR;        
}

-4- 删除  listDelete(&L, i, &e)  (1 ≤i≤n)

Status listDelete(DLinkList &L, int i, LElemType &e){ 
　   DLNode *p = L->next;  
  　 int j = 1;
  　 while( p && j<i ) {   p=p->next;     j++;  }
　   if ( p && j==i  ){                
　　      e=p->data;
　　      p->prior->next=p->next;
　　      if( p->next )  p->next->prior=p->prior;
　　      free(p);
      　　return OK;
  　 }
  　 else return ERROR;        
}

4.循环链表

(1)单循环链表

• 带头结点的循环单链表
• 不带头结点的循环单链表

(2)双向循环链表