数据结构|实现一个链表[4]

福贵

发布于 2020-05-29 15:43:08

3310

发布于 2020-05-29 15:43:08

文章被收录于专栏：合集

链表的实现

先要构建合适的链表结构。下面是构建双向循环链表，应该是结构最复杂的链表。

typedef struct JD{
        int data;
        struct JD *prior;
        struct JD *next;
    }JD;    //创建JD

如上面的代码，就是构建了链表在内存中的存储结构，int data是需要存储的int数据。struct JD *prior则是定义指向前面一个链表结构体的指针。struct JD *next同理是指向下一个链表结构体的指针。所以这个链表的结构共计三个部分，记录数据，指向下一个链表块，指向上一个链表块。那么怎么实现链表的创建呢。首先我们定义一个当前选中的链表结构体，作为head。第一个元素的时候，需要我们自己把两个指针各自指向自己，记录数据也需要手动填充。之后则是开辟新的空间，添加下一个链表块。

    for(;i<10;i++){
        node=(JD *)malloc(sizeof(JD));
        node->data=a[i];
        p->next=node;
        node->prior=p;
        p=p->next;
    }

如上面，一共需要设置10长度的链表。node=(JD *)malloc(sizeof(JD))开辟了一个链表元素长度的空间，并且按照我们定义的JD结构生成。node->data=a[i]设置我们需要记录的值。p->next=node把前一个元素的next指针指向当前的node，node->prior=p把当前node的指向前一个指针的指向前一个元素p。p=p->next把当前的元素设置到下一个。

等到结束之后，有两种处理方式，最后一个节点的指向后一个元素的指针为NULL，则链表结束。另一个则是构成循环链表，把最后一个链表的指向下一个元素的指针指到head。

p->next=head;
head->prior=p;

p是当前的node，最后一个时则表示最后一个node。p->next=head指向的链表的头，head->prior=p指向的结尾node。关于头部的处理

JD *node,*p,*head;
p=(JD *)malloc(sizeof(JD));
head=p;

为了找到链表的遍历入口，我们可以使用指针记录head的地址。结尾附上源代码

#include "stdio.h"
#include "malloc.h"

typedef struct JD{
        int data;
        struct JD *prior;
        struct JD *next;
    }JD;    //创建JD

JD *createList(){   //
    int a[10]={1,4,9,16,25,36,49,64,81,100},i=0;
    JD *node,*p,*head;
    p=(JD *)malloc(sizeof(JD));
    head=p;
    for(;i<10;i++){
        node=(JD *)malloc(sizeof(JD));
        node->data=a[i];
        p->next=node;
        node->prior=p;
        p=p->next;
    }
    p->next=head;
    head->prior=p;
    return p;
}
void printList1(JD *p){
    int i=0;
    JD *temp=p;

    printf("顺序打印:");

    while(temp->data!=1){
        temp=temp->next;
    }   //从1开始打印

    for(;i<10;i++){
        printf("%d ",temp->data);
        temp=temp->next;
    }

    printf("\n\n");
}
void printList2(JD *p){
    
    int i=0;
    JD *temp=p;

    printf("逆序打印:");

    for(;i<10;i++){
        printf("%d ",temp->data);
        temp=temp->prior;
    }

    printf("\n\n");
}
void delete25(JD *p){
    int i=0;

    while(p->data!=1){
        p=p->next;
    }   //从1开始打印

    printf("删除25后打印:");

    for(;i<9;i++){
        if(p->data!=25){
        printf("%d ",p->data);
        p=p->next;
        }
        if(p->next->data==25){
            p->next=p->next->next;
            p->next->prior=p;
        }   //删除25
        
    }

    printf("\n\n");
}
void add50(JD *p){
    int i=0;

    JD *node;
    node=(JD *)malloc(sizeof(JD));
    node->data=50;  //创建50的结点

    printf("增加50后打印:");
    
    while(p->data!=49){
        p=p->next;
        if(p->data==49){
            node->prior=p;
            node->next=p->next;
            p->next=node;
            p->next->prior=node;
        }
    }

    while(p->data!=1)
        p=p->next;  //确保从1开始打印

    for(;i<10;i++){
        printf("%d ",p->data);
        p=p->next;
    }

    printf("\n");
}
int main(){

    JD *head;
    head=createList();//创建双向循环链表
    
    printList1(head);//顺序打印链表
    
    printList2(head);   //逆序打印链表

    delete25(head);//删除25并顺序打印
    
    add50(head);//增加50并顺序打印

    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-05-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法