数据结构—链表

0
12

看了这个妈妈再也不担心我的链表啦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;
}

<

发布回复

请输入评论!
请输入你的名字