(1)项目需求
构造带有头结点的单链表数据结构，实现初始化、清空和销毁操作，在两端插入元素和删除元素操作并在链表中查找操作，在指定位置插入和删除元素操作，移除元素操作
(2)解决思路
① 定义节点类型，定义单链表类型，构造创建新节点的函数。
② 初始化、清空和销毁操作：初始化操作负责将参数指向的单链表类型变量初始
化为空链表。清空操作的作用是将一个链表清空。销毁操作负责销毁一个链表。
③ 在两端插入元素和删除元素操作：包括从链表头部插入和删除元素，从链表尾部插入和删除元素。
④ 在链表中查找操作 : 查找操作用于在参数指向的链表中，
查找首个值等于待插入参数的元素。并返回结点的首地址，返回的地址可供使用者修改结点信息。
⑤ 在指定位置插入和删除元素操作：插入和删除元素都涉及到前后位置指针的指向问题，
有多种解决方案。以插入元素为例，将元素插入指定位置、指定位置之 4前和指定位置之后等。
⑥ 移除元素：用于删除链表中所有满足某个条件的元素。
删除单向链表中的结点需要修改前驱结点的指针域，链表的首元结点没有前驱结点，需要考虑如何处理。

定义结构体以及初始化

typedef struct LinkList //typedef是重命名的含义，此时LinkList * 和 List 含义一致，都是指向结点的指针 {
    int data;//数据域     LinkList* next;//指针域 }*List; //指向结点的指针 //初始化链表 void init_List(List &L) {
    //初始化后链表第一个结点就是头结点     L = (List)malloc(sizeof(LinkList));//为链表分配空间     L->data = 0;//数据域为零     L->next = NULL;//指针指向空 } //清空链表 void clear_List(List &L) {
    if (L->next != NULL)//如果头结点连着的第一个结点不为NULL     {
        L->next = NULL;//置为NULL，此时链表只有头结点，相当于清空链表     }
    printf("清空链表成功");
} //销毁链表 void destory_List(List &L) {
    if (L != NULL)//当头结点不为空时     {
        free(L);//删除头结点地址         L = NULL;//将指针指向NULL，彻底销毁链表     }
    printf("销毁链表成功");
}

增加结点

1、头插

//头插法 void headAdd_List(List &L) {
    List ptr = L->next;//ptr指针初始化指向首元结点，也就是除了头结点的第一个结点     int value = 0;//用来赋值为插入结点的data属性     printf("输入头插的结点值："); 
    scanf("%d", &value);
    List s = (List)malloc(sizeof(LinkList));//s 为待插入结点     s->data = value;//将value赋值给s data属性     s->next = ptr;//s 指向 ptr，即指向头结点的下一个结点     L->next = s;//L头结点指向s,那么现在s结点就插入 }

2、尾插

//尾插法 void tailAdd_List(List &L) {
    int value = 0;//用来赋值为插入结点的data属性     printf("输入尾插的结点值：");
    scanf("%d", &value);
    List s = (List)malloc(sizeof(LinkList));//s 为待插入结点     s->data = value;//将value赋值给s data属性     List ptr = L->next;//ptr指针初始化指向首元结点，也就是除了头结点的第一个结点     if (ptr == NULL)//此时链表为空     {
        s->next = L->next;
        L->next = s;
    }
    else {
        List pre = NULL;//创建pre指针         while (ptr)//当ptr不为NULL时         {
            pre = ptr;//将pre指向ptr             ptr = ptr->next;//ptr指向他的下一个结点         }//循环结束时，pre指向链表最后一个结点,ptr指向最后一个结点的下一个结点         s->next = ptr;//待插入s结点指向ptr         pre->next = s;//将s结点插入到链表最后，尾插完成     }
}

3、指定位置插入

//插入操作 void insert_List(List &L,int n,int data) {
    List ptr = L->next;
    List pre = NULL;
    List s = (List)malloc(sizeof(LinkList));//s 为待插入结点     s->data = data;//将形参列表的data数据赋值给s的data属性     s->next = NULL;
    if (n<1)
    {
        printf("插入位置错误!");
    }
    else if (n == 1)
    {
        printf("调用头插法，请重写输入元素值：");
        headAdd_List(L);//如果插入第一个位置，调用头插法     }
    else     {
        for (int i = 1; i < n; i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }//循环结束后，ptr指向待插入的位置,pre指向待插入位置的前一个位置         s->next = ptr;//插入s结点         pre->next = s;
    }
}

删除结点

1、头删

void headDelete_List(List &L) {
    printf("执行头删：\n");
    List ptr = L->next;//ptr指针初始化指向首元结点，也就是除了头结点的第一个结点     L->next = ptr->next;//直接让头结点指向首元结点的下一个结点，跳过首元结点就是删除     delete ptr;//将首元结点地址删除     ptr = NULL;//指针指向空，防止空指针异常 }

2、尾删

//尾删 void tailDelete_List(List& L) {
    printf("执行尾删：\n");
    List ptr = L;//ptr指针指向头结点     List pre = NULL;//创建结点pre     while (ptr->next)//当ptr的下一个结点不为NULL时     {
        pre = ptr;//将pre指向ptr         ptr = ptr->next;//ptr指向他的下一个结点     }//循环结束时，pre指向链表最后一个结点的前一个结点,ptr指向链表最后一个结点     pre->next = NULL;//将pre的next指针置为空，删除掉     free(ptr);//释放删除掉的ptr指针 }

3、指定位置删除

void delete_List(List & L, int n) {
    List ptr = L->next;
    List pre = NULL; if (n<1)
    {
        printf("删除位置有误!");
    }
    else if (n == 1)
    {
        headDelete_List(L);//调用头删     }
    else     {
        for (int i = 1; i < n ;i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }//循环结束后，ptr指向待插入的位置,pre指向待插入位置的前一个位置         pre->next = ptr->next;//删除该位置的结点         delete ptr;//删除ptr地址         ptr = NULL;//防止空指针异常     }
   
}

查找修改结点

List find_List(int data,List &L) {
    int i = 1;
    List ptr = L->next;
    while (ptr)//当结点不为空时     {
        if (ptr->data == data)
        {
            printf("该元素在链表的位置为第 %d个\n",i);
            return ptr;//找到就返回地址         }
        i++;
        ptr = ptr->next;//继续遍历     }
    printf("链表中没有该元素\n");
    return NULL;
}

移除结点

//移除元素 void cancel_List(List &L,int n) {
    List ptr = L->next;
    List pre = L;
    while (ptr)//ptr不空时     {
        if (ptr->data == n)//如果和传进来的n相等         {
            pre->next = ptr->next;//删除改结点             delete ptr;//删除地址             ptr = pre;//重新指向前一个结点         }
        else {
            pre = ptr;//如果ptr不和n相等，让pre往后走             ptr = ptr->next;//ptr向后遍历         }
    }
}

最终效果

编辑

双链表的基本操作

初始化建表

typedef int ElemType;//将整型数据重命名为int typedef int Status;//整型重命名为Status //双链表的数据结构定义 typedef struct DouNode {
    ElemType data; //数据域 struct DouNode* head; //前驱指针 struct DouNode* next; //后继指针 }DousList, * LinkList;// 结点指针 //双链表的创建 void CreateDouList(LinkList &L, int n) {
    LinkList  ptr; int i;
    L = (LinkList)malloc(sizeof(DousList)); //为头结点申请空间 L->next = NULL;
    L->head = NULL;
    L->data = n;//L->data记录结点的个数 ptr = L; for (i = 0; i < n; i++)
    { int value = 0;
        scanf("%d",&value);
        LinkList me = (LinkList)malloc(sizeof(DouNode));
        me->data = value; //节点数据域 me->next = NULL;
        me->head = NULL;
        ptr->next = me;     
        me->head = ptr;
        ptr = ptr->next; //尾插法建表 }
}

遍历双链表

//双链表的遍历 void DisPlayList(LinkList L) {
    printf("当前链表数据为：\n");
    LinkList ptr= L->next; while (ptr)
    {
        printf("%d ",ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

指定位置插入结点

void InsertNode(LinkList &L, int n, ElemType data) {
    LinkList pre=NULL;
    LinkList ptr = L->next;
    LinkList me = (LinkList)malloc(sizeof(DouNode));
    me->head = NULL;
    me->next = NULL;
    me->data = data; if (n<1 || n>L->data)
    {
        printf("插入位置有误!"); return ;
    } else if (n == 1)
    {
        ptr->head = me;
        me->next = ptr;
        L->next = me;
        me->head = L;
        L->data++;
    } else { for (int i = 1; i < n; i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }
        ptr->head = me;
        me->next = ptr;
        pre->next = me;
        me->head = pre;
        L->data++;
    }
    
}

指定位置删除结点

Status DeleteNode(LinkList& L, int n, ElemType* v) {
    LinkList ptr = L->next; if (n<1 || n>L->data)
    {
        printf("删除位置有误!"); return -1;
    } else { for (int i = 1; i < n; i++)
        {
            ptr = ptr->next;
        }
        v= &ptr->data;
        ptr->head->next = ptr->next;
        ptr->next->head = ptr->head;
       

    }
    L->data--; return *v;
}

查找结点位置

void FindNode(LinkList L, ElemType data) { int i = 0;
    LinkList ptr = L; while (ptr) {
        i++;
        ptr=ptr->next; if (ptr->data == data) {
            printf("该元素在链表中的位置为：%d\n",i);
        }
    }
}