带头结点的单链表

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

typedef int dataType;

// 带头结点的单链表
typedef struct linkNode
{
    dataType data;
    struct linkNode *next;
}node,*linkList;

// 1.初始化带头结点的单链表
void init(linkList *head)
{
    node *p = (node*)malloc(sizeof(node));
    p->next = NULL;
    *head = p;
}

// 2.输出链表
void display(linkList head)
{
    node *p = head->next;
    if(!p)
    {
        printf("单链表为空！\n");
        return;
    }
    while (p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

// 3.在链表尾部插入元素
void rearInsert(linkList *head, dataType x)
{
    node *p = *head,*q; // head初值为头结点
    q = (node*) malloc(sizeof(node));
    q->data = x;
    q->next = NULL;
    while (p->next) // 找到尾结点
        p = p->next;
    p->next = q;
}

// 4.查找第i个结点
node *find(linkList head, int i)
{
    node *p = head->next; // p为工作指针，初值为头结点的下一结点
    if(i < 0)
    {
        printf("索引非法!");
        exit(1);
    }
    if(i == 0)
        return head;
    int j = 1;
    while (p && i!=j)
    {
        p = p->next;
        j++;
    }
    return p;
}

// 5.在单链表的第i个位置后插入元素x
void insert(linkList *head, int i, dataType x)
{
    node *p = find(*head,i),*q;
    q = (node*) malloc(sizeof(node));
    q->data = x;
    q->next = p->next;
    p->next = q;
}

// 6.删除单链表中值为x的元素
void del(linkList *head, dataType x)
{
    node *p = (*head)->next,*pre = *head;
    while (p && p->data != x)
    {
        pre = p;
        p = p->next;
    }
    if(p)
    {
        pre->next = p->next;
        free(p);
    } else printf("没有找到该结点，无法删除！\n");
}

int main()
{
    linkList list; // 声明头指针
    init(&list); // 初始化单链表
    display(list); // 输出单链表
    for (int i = 1; i <= 10; i++)
        rearInsert(&list,i); // 插入结点
    display(list);
    int i = 2;
    node *n = find(list,i);
    if(n)
        printf("第%d个结点的值是%d\n",i,n->data);
    else
        printf("第%d个结点不存在！\n",i);
    dataType x = 0;
    printf("在第%d个结点后插入一个值为%d的结点\n",i,x);
    insert(&list,i,x);
    display(list);
    printf("在带头结点的单链表中删除一个值为%d的结点\n",x);
    del(&list,x);
    display(list);
    return 0;
}