线性表-双链表 （四）

代码： double-list.rar  

插入节点时，都是将 *prior *next 指向了 data 首地址

*prior *next,就是，上一个、下一个 结点的首地址


list.h 文件

#ifndef _LIST_H
#define _LIST_H

typedef char ElemType;
/*typedef struct _stu
{

}ElemType;*/

typedef struct _node
{
    ElemType data; //数据域
    struct _node *prior,*next;
}LIST;

LIST *init_list();
int insert_elem(LIST *l,ElemType *e,int i);
int delete_elem(LIST *l,int i);
int get_length(LIST *l);

#endif

list.c 文件

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

//初始化
LIST *init_list()
{
    LIST *l=(LIST *)malloc(sizeof(LIST));//开辟 head 结点
    if(l == NULL)exit(1);

    l->prior=l->next=NULL;  //初始化 head 结点 prior next=NULL
    return l;
}


int insert_elem(LIST *l,ElemType *e,int i)
{
    int j=1;

    LIST *p=l; //指向 head 结点
    LIST *new;

    if(i < 1)
        return 1;

    new=(LIST *)malloc(sizeof(LIST));
    if(new==NULL)
        return 1;
    new->data=*e;
    new->prior=NULL;
    new->next=NULL;

    while(j<i)      //因为从head 开始，所以这里是定位到 i-1 个结点
    {
        p=p->next;    //p 指向 i-1 结点
        j++;
    }

    new->next=p->next;   //prior next 都是指向了首地址=data地址
    new->prior=p;
    if(p->next!=NULL)// p 不是最后一个结点
        new->next->prior=new;
    p->next=new;//插入节点时，都是将 *prior *next 指向data 首地址
    return 0;
}

int delete_elem(LIST *l,int i)
{
    LIST *p=l;  //指向了 head 结点
    LIST *tmp;

    int j=1;

    while(j<i)  //定位到 i-1 结点
    {
        p=p->next;
        j++;
    }

    tmp=p->next;  //指向要删除的结点
    p->next=tmp->next;
    if(tmp->next!=NULL) //tmp不是最后结点，
        tmp->next->prior=p;  // i+1 结点 指向 i-1 结点
    free(tmp);

    return 0;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int main()
{
    ElemType ch1='a';
    ElemType ch2='b';
    ElemType ch3='c';
    LIST *list;
    list=init_list(); // 初始化 爽链表，malloc head 头结点

    insert_elem(list,&ch1,1);  //插入 结点
    insert_elem(list,&ch2,1);
    insert_elem(list,&ch3,3);
    printf("1=%c\n",list->next->data);  //打印 结点data 数据
    printf("2=%c\n",list->next->next->data);
    printf("3=%c\n",list->next->next->next->data);
    printf("length=%d\n",get_length(list));  //显示  结点数

    delete_elem(list,1);            //删除结点
    printf("1=%c\n",list->next->data);
    printf("2=%c\n",list->next->next->data);
    delete_elem(list,2);           //删除结点
    printf("1=%c\n",list->next->data);
    printf("length=%d\n",get_length(list));  //显示结点数
    return 0;
}

显示：

ywx@yuweixian:~/yu/data-struct/book/double-list$ ./main
1=b
2=a
3=c
length=3
1=a
2=c
1=a
length=1