双向链表 - 简书

双向链表

由于对c语言不熟悉,写了很多注释.

初始化代码

#include <stdio.h>
#include <stdlib.h>
/**
 typedef可以使用它来为类型取一个新的名字
 */
typedef struct Node pNode;//结构体变量pNode
/**
 c 结构体
 Node为结构体标签
 data是标准的变量定义
 */
struct Node
{
    int data;
    //星号*是用来指定一个变量是指针
    pNode *prev;
    pNode *next;
};
/* 初始化链表,从尾巴接入 */
pNode *InitList(pNode **head, int n)
{
    pNode *p, *s;
    
    //以结构体Node为大小分配一块内存转为Node
    //并在head 指针变量 中储存此内存的地址
    (*head) = (pNode *)malloc(sizeof(pNode));
    
    //分配内存失败时退出
    if((*head) == NULL)
       exit(0);
    
    //NULL为空指针常量
    //在head.next 和 prev 指针变量 中储存NULL常量的地址
    (*head)->next = NULL;
    (*head)->prev = NULL;
    
    //在p指针变量 中储存head的地址
    p = (*head);
    
    int i;
    for (i = 0; i < n; ++i) {
        s = (pNode *)malloc(sizeof(pNode));
        if(s == NULL)
            exit(0);
        printf("Input the value of the %dth node:",i + 1);
        
        //控制台输入,保存到s->data
        scanf("%d",&s->data);
        
        s->next = NULL;
        p->next = s;
        s->prev = p;
        p = s;
    }
    return p;
}

初始化图示

双向链表初始化.png

删除单个

/*删除链表中某个元素，令p的前驱节点和后驱节点相互指向即可，如果p是尾节点则直接将前驱节点指向NULL*/
void DelNumqList(pNode **head,int n)
{
    int i;
    pNode *p;
    p = (*head)->next;
    for (i = 1; i < n; ++i) {
        p = p->next;
    }
    if(p->next == NULL)
    {
        p->prev->next = NULL;
        free(p);
    }
    else
    {
        p->next->prev = p->prev;
        p->prev->next = p->next;
        free(p);
    }
}

删除单个图示

双向链表删除单个.png

测试代码

/*遍历打印**/
void PrintList(pNode *head)
{
    pNode *p;
    p = head->next;
    if(head->next == NULL)
        printf("the list is empty");
    while (p != NULL) {
        printf("%d",p->data);
        p = p->next;
    }
    printf("\n");
}

/*清空链表**/
void DeleteList(pNode **head)
{
    pNode *p;
    while ((*head)->next != NULL) {
        p = (*head);
        p->next->prev = NULL;
        (*head) = p->next;
        free(p);
    }
}
/* 查找链表内的某个值*/
int SearchList(pNode *head)
{
    int number;
    printf("Values are about to be deleted:");
    scanf("%d",&number);
    pNode *p;
    p = head->next;
    while (p != NULL) {
        if(p->data == number)
        {
            return number;
        }
        p = p->next;
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    int n, element, flag;
    pNode *head, *last;
    printf("Please input the size of the list:");
    scanf("%d",&n);
    last = InitList(&head, n);
    printf("%d %d \n",head->next->data, last->data);
    PrintList(head);
    
    flag = SearchList(head);
    if(flag >0 && flag <= n)
    {
        DelNumqList(&head, flag);
        PrintList(head);
    }
    else
        printf("Element does not exist, cannot be deleted\n");
    
    
    DeleteList(&head);
    PrintList(head);
    return 0;
}