使用C++来实现简单的链表。

定义结构体

typedef struct data{
    int number;
    string name;
    string sex;
}data;
typedef struct mylist{
    data *information;
    mylist *prior;
    mylist *next;
}mylist;

链表中的某个节点需要有一个prior指向它的前一个节结点的地址

一个data用来存储该结点的各种类型的数据

一个next用来指向它的后一个节点的地址

其中,data数据也可以是包括了更多类型数据的结构体。

新建一个顺序链表

malloc是动态内存分布,因为链表不像数组一样一开始就分配好了内存,所以用malloc函数用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址,当无法知道内存具体位置的时候,想要绑定真正的内存空间,就需要用到动态的分配内存,且分配的大小就是程序要求的大小。

head 表示头结点,end表示尾结点,一开始尾结点就是头结点

每按顺序创建一个新结点p时,让尾结点指向新结点,即end->next=p,同时p->prior=end,说明p的前一个结点是end,再让p成为尾结点,即end=p。如此添加n个结点

最后再让头结点,尾结点都指向NULL,返回头结点

mylist *creat_normal_list(int n)
{
    mylist *head,*normal,*end;
    head=(mylist*)malloc(sizeof(mylist));
    head->information=(data*)malloc(sizeof(data));
    end=head;
    for (int i = 0; i < n; i++) {
        normal=(mylist*)malloc(sizeof(mylist));
        normal->information=(data*)malloc(sizeof(data));
        cout<<"input the number :"<<endl;
        cin>>normal->information->number;
        cout<<"------------------"<<endl;
        end->next=normal;
        normal->prior=end;
        end=normal;
    }
    end->next=NULL;
    head->prior=NULL;
    return head;
}

定义更改节点数据的函数

//该函数表示更改第n个结点的data   循环表示遍历该链表的结点一直到第n个
void change_point(mylist *mylist1,int n,data *information){
    mylist *p;
    p=mylist1;
    for (int i = 0; i < n; i++) {
        p=p->next;
    }
    p->information=information;
}

定义删除节点的函数

//该函数表示删除第n个结点  循环表示遍历链表直到找到第n个结点p为止 
void delete_point(mylist *mylist1,int n){
    mylist *p;
    p=mylist1;
    for (int i = 0; i <n ; i++) {
        p->prior->next=p->next;
        p->next->prior=p->prior;
    }
}
    // 后面两句分别表示
        //p的prior指向的结点的next指向p的next  即p的前一个结点的后一个结点(还是p)的next指向p的后一个结点  
        //p的next指向的结点的prior指向p的prior  即p的后一个结点的前一个结点(还是p)的prior指向p的前一个结点
        //这两句可以调换先后顺序

定义插入结点的函数

//该函数表示第n个位置  插入一个新的结点insertpoint
void insert_point(mylist *mylist1,int n,data *information){
    mylist *p;
    p=mylist1;
    for (int i = 0; i <n-1 ; i++) {
        p=p->next;
        mylist *insertpoint;
        insertpoint=(mylist*)malloc(sizeof(mylist));
        insertpoint->information=information;
        insertpoint->next=p->next;
        p->next=insertpoint;
        insertpoint->prior=p;
        // 循环表示一直找到第n-1个结点为止,让p为第n-1个结点
        //然后让insertpoint的next指向p的next
        //再让 p的next指向 insertpoint
        //最后让 insertpoint的prior指向p
    }
}

定义寻找结点的函数

//该函数表示寻找第n个结点  以上的函数中均包含该函数的结构
void *search_point(mylist *mylist1,int n){
    mylist *p;
    p=mylist1;
    for (int i = 0; i < n; i++) {
        p=p->next;
    }
    return p;
}

定义输出结点的函数

//该函数表示输出第n个结点的data 
void print_point(mylist *mylist1,int n){
    mylist *p;
    p=mylist1;
    for (int i = 0; i < n; i++) {
        p=p->next;
    }
    cout<<"the number is:"<<p->information->number<<endl;
}

定义输出链表的函数

//输出整个链表
void print_list(mylist *point)
{
    mylist *p;
    p=point;
    for(;p->next!=NULL;)
    {
        print_point(p,1);
        p=p->next;
    }
}

定义输出连续结点的函数

//输出第m到n个节点的data
void print_list_part(mylist *list,int m,int n)
{
    int distance=n-m;
    mylist *p;
    p=list;
    for(int i=0;i<m-1;i++)
    {
        p=p->next;
    }
    for(int i=0;i<distance+1;i++)
    {
        print_point(p,1);
        p=p->next;
    }
}

主函数

int main() {
    mylist *head;
    head=creat_normal_list(4);
    print_point(head,4);
    print_list(head);
    print_list_part(head,1,2);
    return 0;
}

输出结果如下图

Last modification:July 12th, 2020 at 01:16 am