不带头结点的单链表

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

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

// 1.初始化不带头结点的单链表
void init(linkList *list)
{
    *list = NULL; // 表示链表指针指向空处
}

// 2.输出单链表元素
void display(linkList list)
{
    node *p = list; // p为工作指针，初值为第一个结点
    if(!p)
    {
        printf("链表为空！\n");
        return;
    }
    while (p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

// 3.查找单链表中的第i个元素
node *find(linkList list, int i)
{
    if(i < 1) return NULL;
    int j = 1;
    node *p = list;
    while (p && j!=i)
    {
        p = p->next;
        j++;
    }
    return p;
}

// 4.在单链表尾部插入元素
void rearInsert(linkList *list, dataType x)
{
    node *p = *list,*q; // p初值为当前链表指针指向的位置
    q = (node*)malloc(sizeof(node)); // 创建新节点
    q->data = x;
    q->next = NULL; // 新节点的指针域置空
    if(!p) *list = q; // 如果当前链表为空
    else
    {
        while (p->next) // 找到最后一个结点
            p = p->next;
        p->next = q;
    }
}

// 5.在单链表第i个位置后插入元素
void insert(linkList *list,int i,dataType x)
{
    node *p = *list,*q; // p初值为当前链表指针指向的位置
    q = (node*)malloc(sizeof(node)); // 创建新节点
    q->data = x;
    p = find(p,i); // 找到第i个结点
    if(!p)
    {
        if(i == 0) // 如果是在第1个元素前插入
        {
            q->next = *list; // 若在链表前插入，则把链表挂在新结点后
            *list = q; // 更新链表指针的的地址，让它指向q
        }
        else
        {
            printf("位置不存在，无法插入元素！\n");
            exit(1);
        }
    }
    else
    {
        q->next = p->next; // 把p结点后的结点挂在q结点后
        p->next = q; // 把新结点插入p结点后
    }
}

// 6.删除一个值为x的结点
void del(linkList *head, dataType x)
{
    node *p = *head,*pre = NULL; // p为工作指针，q为前驱指针
    if(!*head) // 1.链表为空时
    {
        printf("链表为空，无法删除！\n");
        exit(1); // 遇到错误终止程序
    }
    while (p && p->data != x) // 寻找x结点
    {
        pre = p;
        p = p->next;
    }
    if(p) // 找到x结点
    {
        if(!pre) // 如果要删除的是第一个结点
            *head = p->next;
        else pre->next = p->next;
        free(p);
    } else printf("未找到结点%d\n",x);
}

// 7.删除倒数第m个元素
void delM(linkList *list, int m)
{
    // p为链表的工作指针，pre为p的前驱指针，q指向待删结点
    node *p = *list, *pre = NULL, *q;
    if(!p)
    {
        printf("单链表为空，无法删除！\n");
        return;
    }
    int n = 0, i, j = 1; // n为链表个数，i、j为链表位序
    while (p) // 统计链表结点个数
    {
        n++;
        p = p->next;
    }
    i = n-m+1; // 删除的是第i个结点
    if(i < 1 || i > n)
    {
        printf("不存在该结点，无法删除！\n");
        return;
    }
    p = *list; // 重置p指针指回首结点
    while (p->next && j < i) // 寻找要删除的结点
    {
        j++;
        pre = p;
        p = p->next;
    }
    q = p; // q指向待删结点
    if(!pre) // 删除的是首结点
        *list = p->next;
    else
        pre->next = p->next;
    free(q);
}

int main()
{
    linkList list; // 声明一个指向链表的指针
    init(&list); // 初始化链表
    display(list);
    for (int i = 1; i <= 10; i++) // 循环插入值
        rearInsert(&list,i);
    display(list); // 输出链表
    int i = 1;
    node *n = find(list,i); // 查找第i个元素
    if(n) printf("链表的第%d个元素是%d\n",i,n->data);
    else printf("链表访问越界！\n");
    dataType x = 5;
    printf("在第%d个位置后面插入元素%d\n",i,x);
    insert(&list,i,x);
    display(list); // 输出链表
    printf("删除一个值为%d的元素\n",x);
    del(&list,x);
    display(list); // 输出链表
    printf("删除倒数第%d个元素\n",5);
    delM(&list,5);
    display(list); // 输出链表
    return 0;
}