c数据结构 -- 线性表之 复杂的链式存储结构

复杂的链式存储结构
  循环链表
    定义:是一种头尾相接的链表(即表中最后一个结点的指针域指向头结点,整个链表形成一个环)
    优点:从表中任一节点出发均可找到表中其他结点
    注意:涉及遍历操作时,终止条件是判断 p->next == L?
  双向链表
    定义:在单链表的每个结点离再增加一个指向直接前驱的指针域 prior,这样链表中就形成了有
      两个方向不用的链,故称为双向链表
  双向循环链表
    定义:
      和单链的循环表类似,双向链表也可以有循环表
      ·让头节点的前驱指针指向链表的最后一个结点
      ·让最后一个结点的后继指针指向头结点
    示例图(2张):

  c数据结构 --  线性表之 复杂的链式存储结构c数据结构 --  线性表之 复杂的链式存储结构

注意:
  在双向链表中有些操作(如:ListLength、GetElem等),
  因仅涉及一个方向的指针,故它们的算法与线性链表的相同。
  但在插入、删除时,需同时修改两个方向上的指针
算法:

  

            #include <stdio.h>
            #include <stdlib.h>
            #define ERROR 0
            #define OK 1
            // 双向循环链表 
            typedef struct Londe{
                int number; 
                struct Londe *prev; // 
                struct Londe *next; 
            }Londe; 
            typedef Londe *Linklist; // LinkList为指向结构体 Londe 的指针类型 
            // 初始化
            int initList_L(Linklist *L);
            // 通过索引获取结点对象
            Linklist getLinkListByI(Linklist *L,int i);
            // 遍历结点
            int showList_L(Linklist L);
            // 插入数据 
            int insertList_L(Linklist *L,int number);
            // 删除指定索引的结点
            int delLinkByI(Linklist *L,int i);
            int main(void){
                Linklist L = NULL;
                // 初始化单链表    
                initList_L(&L);
                // 插入数据
                insertList_L(&L,2);    
                insertList_L(&L,3);
                delLinkByI(&L,1); 
                showList_L(L);
            } 
            // 初始化
            int initList_L(Linklist *L){
                Linklist node = (Linklist)malloc(sizeof(Londe));
                if(!node){
                    return ERROR;
                }
                node->number = 1;
                node->next = node;
                node->prev = node;
                *L = node;
                return OK;
            }
            // 插入数据 
            int insertList_L(Linklist *L,int number){
                Linklist node = (Linklist)malloc(sizeof(Londe));
                
                if(!node){
                    return ERROR;
                }
                
                node->number = number;
                
                (*L)->prev->next = node;
                node->prev = (*L)->prev;
                node->next = (*L);
                (*L)->prev = node;
                return OK;
            }
            // 遍历结点
            int showList_L(Linklist L){
                Linklist temp = L;
                do{
                    printf("前驱指针%p;值:%d;后继指针%p \n",L->prev,L->number,L->next);
                    L = L->next;
                }while(temp != L);
                return OK;
            }
            // 通过索引获取结点对象
            Linklist getLinkListByI(Linklist *L,int i){
                int ii = 0;
                Linklist T = *L;
                while(ii != i){
                    T = T->next;
                    ii++;
                }
                return T;
            } 
            // 删除指定索引的结点
            int delLinkByI(Linklist *L,int i){
                printf("打点1");
                Linklist temp = getLinkListByI(L,i);
                printf("值是%d \n",temp->number);
                temp->prev->next = temp->next;
                temp->next->prev = temp->prev;
                return OK; 
            } 

 

上一篇:公交线路管理


下一篇:数据结构篇————线性表