首页 > > 程序设计 > C/C++ >

数据结构—链表

2020-05-29 16:01:41来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

数据结构—链表

看了这个妈妈再也不担心我的链表啦QVQ.....

3.1链表的定义

找了一堆感觉都是废话

3.2动态内存分配

malloc：

fp = (数据类型*)malloc(sizeof(数据类型))

free：

free(void *fp)

3.3链表的建立

typedef struct list
{
    int num;
    struct list *next;
}node;
typedef node *link;
?
link creat_list(int n)
{
    link head;
    link ptr;
    int i;
?
    head = (link)malloc(sizeof(node));
    if(!head)
    {
        cout << "内存分配失败" << endl;
        return 0;
    }
    head->next = NULL;
    ptr = head;
?
    cout << "输入n个数据" << endl;
    for(i = 1; i <= n; ++i)
    {
        scanf("%d", &ptr->num);
        ptr->next = (link)malloc(sizeof(node));
        if(!ptr->next)
        {
            cout << "内存分配失败" << endl;
            return 0;
        }
        ptr->next->next = NULL;
        ptr = ptr->next;
    }
    return head;
}

3.4链表的遍历

link find_node(link head, int num)
{
    link ptr;
    ptr = head;
    while (ptr != NULL)
    {
        if(ptr->num == num)
            return ptr;
        ptr = ptr->next;
    }
    cout << "node" << endl;
    return ptr;
}

3.5链表的连接

link concatenate(link ptr1, link ptr2)
{
    link ptr;
    ptr = ptr1;
    while(ptr->next != NULL) //让ptr1的尾巴指向ptr2的头
        ptr = ptr->next;
    ptr->next = ptr2;
    return ptr1;
}

3.6链表内节点的删除

三种情况：

  • 删除第一个节点

  • 删除最后一个节点

  • 删除中间节点

link delete_node(link head, link ptr)
{
    link previous;
    if(ptr == head) //删头
        return head->next;
    else
    {
        previous = head;
        while (previous->next != ptr)
        {
            previous = previous->next;
        }
        previous->next = ptr->next;
    }
    free(ptr); //有借有还，再借不难
    return head;
}

3.7释放链表的内存空间

link destroy_list(link head)
{
    link ptr;
    while(head != NULL)
    {
        ptr = head;
        head = head->next;
        free(ptr);
    }
}

3.8链表内节点的插入

与删除一样会有三种情况

link insert_node(link head, link ptr, int value) //插入在ptr之后
{
    link new_node = (link)malloc(sizeof(node));
    if(!new_node)
    {
        cout << "分配内存失败" << endl;
        return NULL;
    }
    new_node->num = value;
    new_node->next = NULL;
    if(ptr == NULL) //头插
    {
        new_node->next = head;
        return new_node;
    }
    else
    {
        if(ptr->next == NULL) //尾插
            ptr->next = new_node;
        else //中间插
        {
            new_node->next = ptr->next;
            ptr->next = new_node;
        }
        
    }
    return head;
}

3.9链表结构的反转

link invert_list(link head)
{
    link mid, last;
    mid = NULL;
    while(head != NULL)
    {
        last = mid;
        mid = head;
        head = head->next;
        mid->next = last;
    }
    return mid;
}

让我们看看具体是怎么来的：

  1. 执行while之前 head指向链表第一个 mid == NULL， last无值

  2. 执行一次 head指向链表第二个 mid 指向 链表第一个 last == NULL

  3. 再执行一次 head指向链表第三个 mid 指向 链表第二个 last 指向 链表第一个 并且 mid的前驱是last

  4. 反复直到反转完成 返回mid 也就是反转后的头节点

3.10循环链表结构

头尾相连的链表

3.10.1首先建立链表

typedef struct clist
{
    int data;
    struct clist *next;
}cnode;
typedef cnode *clink;
?
clink creat_list(int n)
{
    clink head;
    clink ptr;
    int i;
?
    head = (clink)malloc(sizeof(cnode));
    if(!head)
    {
        cout << "内存分配失败" << endl;
        return 0;
    }
    head->next = NULL;
    ptr = head;
?
    cout << "输入n个数据" << endl;
    for(i = 1; i <= n; ++i)
    {
        scanf("%d", &ptr->data);
        ptr->next = (clink)malloc(sizeof(cnode));
        if(!ptr->next)
        {
            cout << "内存分配失败" << endl;
            return 0;
        }
        ptr->next->next = NULL;
        ptr = ptr->next;
    }
    ptr->next = NULL;
    return head;
}

3.10.2循环链表内节点的插入

  • 情况一 ：插在链表的头部成为链表的新开始

    • 将新节点的指针指向链表的第一个节点

    • 找到最后一个节点且将其指针指向新节点

    • 返回新节点 为链表新头部

  • 情况二：除情况一的其他情况，假设插在ptr之后

    • 将新节点的指针指向ptr下一节点

    • 将ptr的下一节点设为新节点

clink insert_node(clink head, clink ptr, int value)
{
    clink new_node = (clink)malloc(sizeof(cnode));
    clink previous;
    if(!new_node)
    {
        cout << "分配内存失败" << endl;
        return NULL;
    }
    new_node->data = value;
    new_node->next = NULL;
    if(head == NULL) //原先就是空表
    {
        new_node->next = new_node;
        return new_node;
    }
    if(ptr == NULL) // 头插
    {
        new_node->next = head;
        previous = head;
        while(previous->next != NULL)
            previous = previous->next;
        previous->next = new_node;
        head = new_node;
    }
    else
    {
        new_node->next = ptr->next;
        ptr->next = new_node;
    }
    return head;
}

3.10.3循环链表内节点的删除

  • 情况一：删第一个

    • 将链表的开始移向下一节点

    • 将最后一个节点指向第二个节点

  • 情况二：除情况一的其他情况，删除ptr

    • 找到ptr的前一个节点

    • 将ptr前一个节点的后继设为ptr的后继

clink delete_node(clink head, clink ptr)
{
    clink previous;
    if(head == NULL) //空表
        return NULL;
    previous = head;
    if(head != head->next) //不止一个节点
        while(previous->next != ptr)
            previous = previous->next;
?
    if(ptr == head) //头插
    {
        head = head->next;
        previous->next = ptr->next;
    }
    else
    {
        previous->next = ptr->next;
    }
    free(ptr);
    return head;
}

 

3.11双向链表结构

3.11.1双向链表的建立

俩个指针，一个指向前驱，一个指向后继

typedef struct dlist
{
    int data;
    struct dlist *front; //后继
    struct dlist *back; //前驱
}dnode;
typedef dnode *dlink;
?
dlink create_dlist(int *arr, int len)
{
    dlink head, before, new_node;
    int i;
    head = (dlink)malloc(sizeof(dnode));
    if(!head)
    {
        cout << "内存分配失败" << endl;
        return NULL;
    }
    head->data = arr[0];
    head->back = NULL;
    head->front = NULL;
    before = head;
    for(i = 1; i < len; ++i)
    {
        new_node = (dlink)malloc(sizeof(dnode));
        new_node->data = arr[i];
        new_node->front = NULL;
        new_node->back = before;
        before = new_node;
    }
    return head;
}

3.11.2双向链表的插入

  • 情况一：头插

    • 将新节点的指针front指向双向链表的开始

    • 将表头的back指向新节点

    • head = new_node

  • 情况二：尾插

    • 将最后一个节点的front指向新节点

    • 新节点的back指向尾部

  • 情况三：中间插，假设在ptr之后

    • 新节点的前驱指向ptr

    • 新节点的后继变为ptr的后继

    • ptr的后继指向新节点

    • 原ptr后继的前驱指向新节点

dlink insert_node(dlink head, dlink ptr, int value)
{
    dlink new_node = (dlink)malloc(sizeof(dnode));
    if(!new_node)
    {
        cout << "内存分配失败" << endl;
        return NULL;
    }
    new_node->back = NULL;
    new_node->front = NULL;
    new_node->data = value;
    if(head == NULL) //空表
        return new_node;
    if(ptr == NULL) //头插
    {
        new_node->front = head;
        head->back = new_node;
        head = new_node;
    }
    else
    {
        if(ptr->front == NULL) //尾插
        {
            ptr->front = new_node;
            new_node->back = ptr;
        }
        else
        {
            ptr->front->back = new_node;
            new_node->front = ptr->front;
            new_node->back = ptr;
            ptr->front = new_node;
        }
        
    }
    return head;  
}

3.11.3双向链表节点的删除

  • 情况一：删头

    • 将指向链表开始节点的指针head指向第二个节点

    • 将第二个节点的前驱设为NULL

  • 情况二：删尾

    • 最后一节点的后继设为NULL

  • 情况三：删中间，删除ptr

    • ptr前驱的后继设为ptr后继的前驱

    • ptr后继的前驱设为ptr前驱的后继

dlink delete_node(dlink head, dlink ptr)
{
    if(ptr->back == NULL) //删头
    {
        head = head->front;
        head->back = NULL;
    }
    else
    {
        if(ptr->front == NULL) //删尾
        {
            ptr->back->front == NULL;
        }
        else
        {
            ptr->back->front = ptr->front;
            ptr->front->back = ptr->back;
        }
        
    }
    free(ptr);
    return head;
}

3.12循环双向链表

3.12.1建立

typedef struct dlist
{
    int data;
    struct dlist *front; //后继
    struct dlist *back; //前驱
}cdnode;
typedef cdnode *cdlink;
?
cdlink create_dlist(int *arr, int len)
{
    cdlink head, before, new_node;
    int i;
    head = (cdlink)malloc(sizeof(cdnode));
    if(!head)
    {
        cout << "内存分配失败" << endl;
        return NULL;
    }
    head->data = arr[0];
    head->back = NULL;
    head->front = NULL;
    before = head;
    for(i = 1; i < len; ++i)
    {
        new_node = (cdlink)malloc(sizeof(cdnode));
        new_node->data = arr[i];
        new_node->front = NULL;
        new_node->back = before;
        before = new_node;
    }
    head->back = new_node;
    new_node->front = head;
    //head->back = NULL;
    //new_node->front = NULL;
    return head;
}

  • 情况一：删除或插入第一个节点

  • 情况二：除情况一

3.12.2删除

cdlink delete_node(cdlink head, cdlink ptr)
{
    if(head == NULL)
        return NULL;
    if(ptr == head) head = head->front; //头
    ptr->back->front = ptr->front;
    ptr->front->back = ptr->back;
    free(ptr);
    return head;
}

 

3.12.3插入

cdlink insert_node(cdlink head, cdlink ptr, int value)
{
    cdlink new_node = (cdlink)malloc(sizeof(cdnode));
    if(!new_node)
    {
        cout << "内存分配失败" << endl;
        return NULL;
    }
    new_node->data = value;
    if(head == NULL) //空表
    {
        new_node->back = new_node;
        new_node->front = new_node;
        return new_node;
    }
    if(ptr == NULL) //头插
    {
        head->back->front = new_node;
        new_node->front = head;
        new_node->back = head->back;
        head->back = new_node;
        head = new_node;
    }
    else
    {
        ptr->front->back = new_node;
        new_node->front = ptr->front;
        new_node->back = ptr;
        ptr->front = new_node;
    }
    return head;
}

最后代码大汇总

#include <bits/stdc++.h>
using namespace std;

typedef struct list
{
    int num;
    struct list *next;
}node;
typedef node *link;

link creat_list(int n)
{
    link head;
    link ptr;
    int i;

    head = (link)malloc(sizeof(node));
    if(!head)
    {
        cout << "内存分配失败" << endl;
        return 0;
    }
    head->next = NULL;
    ptr = head;

    cout << "输入n个数据" << endl;
    for(i = 1; i <= n; ++i)
    {
        scanf("%d", &ptr->num);
        ptr->next = (link)malloc(sizeof(node));
        if(!ptr->next)
        {
            cout << "内存分配失败" << endl;
            return 0;
        }
        ptr->next->next = NULL;
        ptr = ptr->next;
    }
    return head;
}

link find_node(link head, int num)
{
    link ptr;
    ptr = head;
    while (ptr != NULL)
    {
        if(ptr->num == num)
            return ptr;
        ptr = ptr->next;
    }
    cout << "node" << endl;
    return ptr;
}

link concatenate(link ptr1, link ptr2)
{
    link ptr;
    ptr = ptr1;
    while(ptr->next != NULL)
        ptr = ptr->next;
    ptr->next = ptr2;
    return ptr1;
}

link delete_node(link head, link ptr)
{
    link previous;
    if(ptr == head)
        return head->next;
    else
    {
        previous = head;
        while (previous->next != ptr)
        {
            previous = previous->next;
        }
        previous->next = ptr->next;
    }
    free(ptr);
    return head;
}

link destroy_list(link head)
{
    link ptr;
    while(head != NULL)
    {
        ptr = head;
        head = head->next;
        free(ptr);
    }
}

link insert_node(link head, link ptr, int value) //插入在ptr之后
{
    link new_node = (link)malloc(sizeof(node));
    if(!new_node)
    {
        cout << "分配内存失败" << endl;
        return NULL;
    }
    new_node->num = value;
    new_node->next = NULL;
    if(ptr == NULL) //头插
    {
        new_node->next = head;
        return new_node;
    }
    else
    {
        if(ptr->next == NULL) //尾插
            ptr->next = new_node;
        else //中间插
        {
            new_node->next = ptr->next;
            ptr->next = new_node;
        }
        
    }
    return head;
}

link invert_list(link head)
{
    link mid, last;
    mid = NULL;
    while(head != NULL)
    {
        last = mid;
        mid = head;
        head = head->next;
        mid->next = last;
    }
    return mid;
}

int main()
{

    return 0;
}   
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef struct clist
{
    int data;
    struct clist *next;
}cnode;
typedef cnode *clink;

clink creat_list(int n)
{
    clink head;
    clink ptr;
    int i;

    head = (clink)malloc(sizeof(cnode));
    if(!head)
    {
        cout << "内存分配失败" << endl;
        return 0;
    }
    head->next = NULL;
    ptr = head;

    cout << "输入n个数据" << endl;
    for(i = 1; i <= n; ++i)
    {
        scanf("%d", &ptr->data);
        ptr->next = (clink)malloc(sizeof(cnode));
        if(!ptr->next)
        {
            cout << "内存分配失败" << endl;
            return 0;
        }
        ptr->next->next = NULL;
        ptr = ptr->next;
    }
    ptr->next = NULL;
    //ptr->next = head;
    return head;
}

clink insert_node(clink head, clink ptr, int value)
{
    clink new_node = (clink)malloc(sizeof(cnode));
    clink previous;
    if(!new_node)
    {
        cout << "分配内存失败" << endl;
        return NULL;
    }
    new_node->data = value;
    new_node->next = NULL;
    if(head == NULL) //原先就是空表
    {
        new_node->next = new_node;
        return new_node;
    }
    if(ptr == NULL) // 头插
    {
        new_node->next = head;
        previous = head;
        while(previous->next != NULL)
            previous = previous->next;
        previous->next = new_node;
        head = new_node;
    }
    else
    {
        new_node->next = ptr->next;
        ptr->next = new_node;
    }
    return head;
}

clink delete_node(clink head, clink ptr)
{
    clink previous;
    if(head == NULL) //空表
        return NULL;
    previous = head;
    if(head != head->next) //不止一个节点
        while(previous->next != ptr)
            previous = previous->next;

    if(ptr == head) //头插
    {
        head = head->next;
        previous->next = ptr->next;
    }
    else
    {
        previous->next = ptr->next;
    }
    free(ptr);
    return head;
}

int main()
{
    
    return 0;
}

 

#include <bits/stdc++.h>
using namespace std;

typedef struct dlist
{
    int data;
    struct dlist *front; //后继
    struct dlist *back; //前驱
}dnode;
typedef dnode *dlink;

dlink create_dlist(int *arr, int len)
{
    dlink head, before, new_node;
    int i;
    head = (dlink)malloc(sizeof(dnode));
    if(!head)
    {
        cout << "内存分配失败" << endl;
        return NULL;
    }
    head->data = arr[0];
    head->back = NULL;
    head->front = NULL;
    before = head;
    for(i = 1; i < len; ++i)
    {
        new_node = (dlink)malloc(sizeof(dnode));
        new_node->data = arr[i];
        new_node->front = NULL;
        new_node->back = before;
        before = new_node;
    }
    return head;
}

dlink insert_node(dlink head, dlink ptr, int value)
{
    dlink new_node = (dlink)malloc(sizeof(dnode));
    if(!new_node)
    {
        cout << "内存分配失败" << endl;
        return NULL;
    }
    new_node->back = NULL;
    new_node->front = NULL;
    new_node->data = value;
    if(head == NULL) //空表
        return new_node;
    if(ptr == NULL) //头插
    {
        new_node->front = head;
        head->back = new_node;
        head = new_node;
    }
    else
    {
        if(ptr->front == NULL) //尾插
        {
            ptr->front = new_node;
            new_node->back = ptr;
        }
        else
        {
            ptr->front->back = new_node;
            new_node->front = ptr->front;
            new_node->back = ptr;
            ptr->front = new_node;
        }
        
    }
    return head;  
}

dlink delete_node(dlink head, dlink ptr)
{
    if(ptr->back == NULL) //删头
    {
        head = head->front;
        head->back = NULL;
    }
    else
    {
        if(ptr->front == NULL) //删尾
        {
            ptr->back->front == NULL;
        }
        else
        {
            ptr->back->front = ptr->front;
            ptr->front->back = ptr->back;
        }
        
    }
    free(ptr);
    return head;
}

int main()
{

    return 0;
}
#include <bits/stdc++.h>
using namespace std;

typedef struct dlist
{
    int data;
    struct dlist *front; //后继
    struct dlist *back; //前驱
}cdnode;
typedef cdnode *cdlink;

cdlink create_dlist(int *arr, int len)
{
    cdlink head, before, new_node;
    int i;
    head = (cdlink)malloc(sizeof(cdnode));
    if(!head)
    {
        cout << "内存分配失败" << endl;
        return NULL;
    }
    head->data = arr[0];
    head->back = NULL;
    head->front = NULL;
    before = head;
    for(i = 1; i < len; ++i)
    {
        new_node = (cdlink)malloc(sizeof(cdnode));
        new_node->data = arr[i];
        new_node->front = NULL;
        new_node->back = before;
        before = new_node;
    }
    head->back = new_node;
    new_node->front = head;
    //head->back = NULL;
    //new_node->front = NULL;
    return head;
}

cdlink delete_node(cdlink head, cdlink ptr)
{
    if(head == NULL)
        return NULL;
    if(ptr == head) head = head->front; //头
    ptr->back->front = ptr->front;
    ptr->front->back = ptr->back;
    free(ptr);
    return head;
}

cdlink insert_node(cdlink head, cdlink ptr, int value)
{
    cdlink new_node = (cdlink)malloc(sizeof(cdnode));
    if(!new_node)
    {
        cout << "内存分配失败" << endl;
        return NULL;
    }
    new_node->data = value;
    if(head == NULL) //空表
    {
        new_node->back = new_node;
        new_node->front = new_node;
        return new_node;
    }
    if(ptr == NULL) //头插
    {
        head->back->front = new_node;
        new_node->front = head;
        new_node->back = head->back;
        head->back = new_node;
        head = new_node;
    }
    else
    {
        ptr->front->back = new_node;
        new_node->front = ptr->front;
        new_node->back = ptr;
        ptr->front = new_node;
    }
    return head;
}

int main()
{

    return 0;
}

 


原文链接:https://www.cnblogs.com/xiguan/p/12989587.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：C++ 在名称空间中使用using声明和using编译指令

下一篇：C++ 关键字decltype

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签