数据结构

数据结构笔记——线性表的链式表示（循环与双向链表）

概念

循环链表：头尾相接的链表：表中的最后一个节点的next指向头节点，构成一个环。

循环停止的条件为p的next是否为头指针

双向链表：在单链表的每个节点里增添一个指向前驱节点的指针prior

双向循环链表：头节点的prior指向链表尾节点，尾节点的next指向头节点

typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;

基本操作

带尾指针循环链表的合并

复杂度O(1)

LinkList Connect(LinkList Ta,LinkList Tb){
    LinkList p=Ta->next; //p暂存为Ta的头节点
    Ta->next=Tb->next->next; //将Ta的的尾节点连接到Tb的第一个具有数值的节点（头节点的下一个）
    free(Tb->next);//释放Tb的头节点
    Tb->next=p;//将Tb的尾节点连接到Ta的头节点
    return Tb;
}

双向链表的查找

DuLinkList GetElem_DuL(DuLinkList L,int i){
    DuLinkList p=L;
    int j=0;
    while (p->next!=NULL&&j<i+1)
    {
        p=p->next;
        j++;
    }
    return p;
}

双向链表的插入

void ListInsert_DuL(DuLinkList L,int i,ElemType e){
    DuLinkList p=GetElem_DuL(L,i);
    if(p==NULL){
        return ERROR;
    }
    DuLinkList s=(DuLinkList)malloc(sizeof(DuLNode));
    s->data=e;
    s->prior=p->prior; //将要插入的节点的前驱节点改为原节点的前驱节点
    p->prior->next=s; //将原节点的前驱节点的后驱节点改为要插入的节点
    s->next=p; //要插入的节点后驱节点改为原节点
    p->prior=s; //原节点的前驱节点改为要插入的节点

    return OK;
}

双向链表的删除

void ListDelete_DuL(DuLinkList L,int i,ElemType *e){
    DuLinkList p=GetElem_DuL(L,i);
    if(p==NULL){
        return ERROR;
    }
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}

Comment