循环链表
/*头尾相连的链表，表中最后一个结点的指针域指向头结点从表中任一结点出发均可找到其他结点*//*a1的存储位置R->next->nextan的存储位置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;
} 链式存储结构的优缺点
/*链式存储结构的优点：
结点的空间可以动态申请和释放
数据元素的逻辑次序靠结点的指针表示，插入和删除元素时不用移动数据元素*/
/*链式存储结构的缺点：
存储密度小，每个结点的指针域需要额外占用存储空间，当每个结点的数据域所占字节不多时，指针域所占存储空间比重很大
存储密度=结点数据本所占空间/结点占用的空间总量*/
//一般的，存储密度越大，空间利用率越高