美文网首页
算法与数据结构03（基础篇）——循环链表

算法与数据结构03（基础篇）——循环链表

作者: 叶孤城1993 | 来源:发表于2020-04-02 15:45 被阅读0次
    image

    定义结构体

    typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

    尾插法创建链表

    前面讲过，链表的尾插法创建，新节点放在尾节点之后，但是循环链表要注意新尾节点的next指向

    image

    完整函数片段

    /*
 1、链表是否已经存在
 2、若不存在，创建新节点，头指针指向新节点，新节点->next指向新节点
 3、若已存在，尾插法向后新增节点，新的尾节点->next指向首元节点，即*L
 */
Status CreateList(LinkList *L)
{
    int item;
    LinkList temp = NULL; // 每次创建的新节点
    LinkList fp = NULL; // 标记尾节点
    
    while (1) {
        
        scanf("%d",&item); // 输入创建的新值
        
        if (item == 0) break;  // 输入为0时，结束创建
        
        if (*L == NULL)
        {
            // 创建首元节点
            temp = (LinkList)malloc(sizeof(Node));
            if (temp == NULL) return 0;
            
            temp->data = item; // 向节点写入数据
            temp->next = temp; // 首元节点的next指向自己，因为只有自己一个节点
            
            fp = temp;  // 首元节点也是尾节点
            *L = temp;  // 头指针指向首元节点
        }
        else
        {
            // 向链表后追加新节点，并更新尾节点
            // 创建新节点
            temp = (LinkList)malloc(sizeof(Node));
            if (temp == NULL) return 0;
            temp->data = item;
            
            // 新节点next指向尾节点的next   因为是循环，尾节点的next其实就是*L,
            // temp->next = fp->next;
            temp->next = *L;
            
            // 尾节点指向新节点
            fp->next = temp;
            // 更新尾节点
            fp = temp;
        }
    }
    
    return 1;
}

int main(int argc, const char * argv[]) {
    
    LinkList head;
    // 创建
    CreateList(&head);
    // 输出链表
    PrintList(head);
    
    return 0;
}

    输出结果

    image

    遍历

    void PrintList(LinkList L)
{
    if (L == NULL)
    {
        printf("链表为空！");
    }
    else
    {
        /*
         第一种遍历方式
         */
//        LinkList temp = L;
//        do{
//            printf("%5d",temp->data);
//            temp = temp->next;
//        }while (temp != L);
        
        /*
         第二种遍历方式
        */
//        LinkList temp = L;
//        while (temp->next != L) {
//            printf("%5d",temp->data);
//            temp = temp->next;
//        }
//        printf("%5d\n",temp->data);
        
        /*
         第三种遍历方式
        */
        LinkList temp = L;
        for (; temp->next!=L; temp = temp->next) {
            printf("%5d",temp->data);
        }
        printf("%5d\n",temp->data);
    }
}

    插入

    注意： 插入数据是需要判断是不是插入在首节点位置 why?

    插入位置在首元节点

    image 
    temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
temp->data = m;

// 1、找到尾节点target
for (target = *L; target->next != *L; target = target->next) ;
// 2、新节点指向首节点
temp->next = *L;
// 3、尾节点指向新节点
target->next = temp;
// 4、头指针指向新首元节点
*L = temp;

    插入在其他任意位置

    image 
    int i; // 辅助确定插入位置

temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
temp->data = m;

// 1、找到插入位置的前一个节点target
for (i = 1, target = *L; target->next != *L && i != index-1; i++,target = target->next) ;
// 2、新节点 指向 target的后节点
temp->next = target->next;
// 3、target 指向 新节点
target->next = temp;

    完整函数片段

    /// 插入数据
/// @param L 链表（链表的头指针）
/// @param index 插入位置 1是首元节点 所以插入位置要从1开始
/// @param m 插入的节点数据
Status ListInsert(LinkList *L, int index, int m)
{
    LinkList target = NULL; // 插入的节点的前一个节点
    LinkList temp = NULL;   // 新节点
    
    if (index < 1) return ERROR;
    
    if (index == 1)
    {
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
        
        temp->data = m;
  
        // 1、找到尾节点target
        for (target = *L; target->next != *L; target = target->next) ;
        
        // 2、新节点指向首节点
        temp->next = *L;
        // 3、尾节点指向新节点
        target->next = temp;
        // 4、头指针指向新首元节点
        *L = temp;
    }
    else
    {
        int i; // 辅助确定插入位置
        
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
        
        temp->data = m;
        
        // 1、找到插入位置的前一个节点target
        for (i = 1, target = *L; target->next != *L && i != index-1; i++,target = target->next) ;
        // 2、新节点 指向 target的后节点
        temp->next = target->next;
        // 3、target 指向 新节点
        target->next = temp;
    }
    
    return OK;
}
    image

    删除

    删除首元节点

    image 
    // 1、找到尾节点target
for (target = *L; target->next != *L; target = target->next);
temp = *L; // temp要删除的节点

// 2、尾节点指向删除节点后的节点
target->next = (*L)->next;

// 3、首指针指向尾节点后的节点
*L = target->next;

// 4、释放
free(temp);

    删除其他任意节点

    image 
    int i;
// 1、找到尾节点target  和 要删除的temp
for (i=1, target = *L; target->next != *L && i < index-1; target = target->next, i++);
temp = target->next;

// 2、target指向temp的后一个节点
target->next = temp->next;

// 3、释放
free(temp);

    完整函数片段

    /// 删除指定位置的节点
/// @param L 链表
/// @param index 位置
Status ListDelete(LinkList *L, int index)
{
    if (*L == NULL) return ERROR;
    
    // 只剩一个节点
    if ((*L)->next == *L) {

        (*L) = NULL;
        return ERROR;
    }
    
    LinkList target , temp;
    
    if (index == 1)
    {
        // 删除首元节点
        
        // 1、找到尾节点target
        for (target = *L; target->next != *L; target = target->next);
        temp = *L; // temp要删除的节点
        
        // 2、尾节点指向删除节点后的节点
        target->next = (*L)->next;
        // 3、首指针指向尾节点后的节点
        *L = target->next;
        // 4、释放
        free(temp);
    }
    else
    {
        // 删除其他任意节点
        
        int i;
        
        // 1、找到尾节点target  和 要删除的temp
        for (i=1, target = *L; target->next != *L && i < index-1; target = target->next, i++);
        temp = target->next;
        
        // 2、target指向temp的后一个节点
        target->next = temp->next;
        
        // 3、释放
        free(temp);
    }
    
    return OK;
}
    image

    查询

    下面的实现代码，本质还是遍历

    根据位置查询值

    ElemType FindValue(LinkList L, int index)
{
    int i; // 辅助确定插入位置
    LinkList target;
    
    // 1、找到插入位置的前一个节点target
    for (i = 1, target = L; target->next != L && i != index-1; i++,target = target->next) ;
    
    return target->next->data;
}

    根据值查询位置

    int FindIndex(LinkList L, ElemType v)
{
    int i = 1;
    LinkList temp = L;
    
    for (; temp->next!=L && temp->data != v; temp = temp->next,i++) ;
    
    if (temp->next == L && temp->data != v)
        return -1;
    
    return i;
}
    image

    1、为什么插入、删除都要注意是不是首元节点？

    需要变更头指针指向新的首元节点

    2、博客外的问题：创建链表时，是不是双指针？具体什么含义？

    struct Node *LinkList; // 存储节点实体在内存中的地址，所以指针->实体节点
LinkList L;
CreateList(&L); // 传指针L的地址 : 指针的指针
.
.
.
Void CreateList(LinkList *pL)
{
    // pL 已经不是上面的L *pL 才是上面的L
    // 所以到这里， pL 就是指向L的指针 L指向实体节点
    // malloc 函数返回的开辟的内存空间的地址，所以要用指针接收
    *pL = (LinkList)malloc(sizeof(Node));
    // *pL 里存的就是节点的内存地址
    // 所以pL里存的是节点的内存地址的地址
}

    相关文章

      网友评论

          本文标题：算法与数据结构03（基础篇）——循环链表

          本文链接：https://www.haomeiwen.com/subject/mzmxphtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|算法与数据结构03（基础篇）——循环链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！