循环链表与双向链表

循环链表

 /*头尾相连的链表，表中最后一个结点的指针域指向头结点   从表中任一结点出发均可找到其他结点*/    /*a1的存储位置R->next->next   an的存储位置R*/  

 带尾指针的双向链表的合并

具体步骤

   p存储Ta表头结点
   Tb表头连接到Ta表尾
   释放Tb表头
   修改指针

 LinkList Connect(LinkList Ta,LinkList Tb){   //Ta,Tb分别表示两个链表的尾指针  	p=Ta->next;                              //p存储Ta表头结点 	Ta->next=Tb->next->next;                 //Tb表头连接到Ta表尾 	free(Tb->next);                          //释放Tb表头 	Tb->next=p;                              //修改指针 	return Tb; } //时间复杂度为O(1);  

 

双向链表

/*单链表的结点->有指示后继的指针域->找后继结点方便   即查找某一个结点的后继结点执行的时间复杂度为O(1);*/

 
双向链表的定义

 typedef struct DuLNode{ 	ElemType data; 	struct DuLNode *prior,*next;            //与单链表不同的是双向链表定义的时候多了一个前驱结点  }DuLNode,*DuLinkList;  

 

双向循环链表

/*让头结点的前驱指针指向最后一个结点
  让尾结点的后继指针指向头结点*/

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

 双向链表的插入

 void Listlnsert_DuL(DuLinkList &L,int i,ElemType e){    //在第i个结点前插入数据元素为e的结点  	DuLinkList p;                 //找到第i个结点  	p=L->next; 	j=1; 	while(p&&j<i){                 		p=p->next; 		++j; 	} 	if(!p||j>i){                  //第i个元素不存在  		return ERROR; 	}  	s=(DuLinkList)malloc(sizeof(DuLNode)); 	s->sata=e; 	s->prior=p->prior;           //插入的关键步骤  	p->prior->next=s; 	s->next=p; 	p->prior=s; }     

双向链表的删除

  void ListDelete_DuL(DuLinkList &L,int i,ElemType e){   //删除带头结点的双向链表L的第i个元素，并用e值返回  		DuLinkList p;                 //找到第i个结点  	p=L->next; 	j=1; 	while(p&&j<i){                 		p=p->next; 		++j; 	} 	if(!p||j>i){                  //第i个元素不存在  		return ERROR; 	} 	e=p->data; 	p->prior->next=p->next;       //关键步骤  	p->next->prior=p->prior; 	free(p); 	return OK; }   

 链式存储结构的优缺点

/*链式存储结构的优点： 
  结点的空间可以动态申请和释放
  数据元素的逻辑次序靠结点的指针表示，插入和删除元素时不用移动数据元素*/
 
 
/*链式存储结构的缺点：
存储密度小，每个结点的指针域需要额外占用存储空间，当每个结点的数据域所占字节不多时，指针域所占存储空间比重很大
存储密度=结点数据本所占空间/结点占用的空间总量*/
  
//一般的，存储密度越大，空间利用率越高