单链表是上机时的作业,下面是简易实现,其中测试函数是抄来的

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

#define OK 1
#define NONONO 0

typedef int element_type;
typedef int Status;

typedef struct LINKLIST_NODE
{
    element_type data;
    struct LINKLIST_NODE *next;
} LinkListNode;

//  初始化单链表
Status LinkListInit(LinkListNode *L);
//  删除单链表
Status LinkListDestroy(LinkListNode *L);
//  清空单链表
Status LinkListClear(LinkListNode *L);
//  判断单链表为空
Status isLinkListEmpty(LinkListNode *L);
//  返回单链表当前长度
Status LinkListLength(LinkListNode *L);
//  用第三个参数 x 返回单链表中第 n 位的值
Status LinkListGetELement(LinkListNode *L, int n, element_type *x);
//  用第三个参数 n 返回单链表中值为 x 的项位置序号最小的一项的位置
Status LinkListGetLocation(LinkListNode *L, element_type x, int *n);
//  在单链表第 n 位插入值 x
Status LinkListInsert(LinkListNode *L, int n, element_type x);
//  删除单链表第 n 位的值,并用 x 返回其值
Status LinkListDelete(LinkListNode *L, int n, element_type *x);
//  从头遍历整个单链表
Status LinkListTrave(LinkListNode *L);

Status LinkListInit(LinkListNode *L)
{
    L = (LinkListNode *)malloc(sizeof(LinkListNode));
    assert(L);
    L->next = NULL;
    return OK;
}

Status LinkListDestroy(LinkListNode *L)
{
    LinkListNode *p = L;
    LinkListNode *tmp;
    while (p->next)
    {
        tmp = p;
        p = p->next;
    }
    return OK;
}

Status issLinkListEmpty(LinkListNode *L)
{
    return L->next == NULL;
}

Status LinkListClear(LinkListNode *L)
{
    LinkListNode *p = L->next;
    L->next = NULL;
    free(p);
    return OK;
}

Status LinkListLength(LinkListNode *L)
{
    int i = 0;
    LinkListNode *p = L->next;
    while (p)
    {
        i++;
        p = p->next;
    }
    free(p);
    return i;
}

Status LinkListGetElement(LinkListNode *L, int n, element_type *x)
{
    int tmp = 1;
    LinkListNode *p = L->next;
    while (p && tmp < n)
    {
        tmp++;
        p = p->next;
    }
    if (!p || tmp > n)
        return NONONO;
    *x = p->data;
    return OK;
}

Status LinkListGetLocation(LinkListNode *L, element_type x, int *n)
{
    int i = 0;
    LinkListNode *p = L->next;
    while (p)
    {
        i++;
        if (p->data == x)
            *n = i;
        p = p->next;
    }
    return 0;
}

Status LinkListInsert(LinkListNode *L, int n, element_type x)
{
    int tmp = 0;
    LinkListNode *s;
    LinkListNode *p = L;
    while (p && tmp < n - 1)
    {
        tmp++;
        p = p->next;
    }
    if (!p || tmp > n - 1)
    {
        return NONONO;
    }
    s = (LinkListNode *)malloc(sizeof(LinkListNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return OK;
}

Status LinkListDelete(LinkListNode *L, int n, element_type *x)
{
    LinkListNode *p = L;
    LinkListNode *tmp;
    for (int i = 0; i < n - 1; i++)
    {
        if (p->next == NULL)
            break;
        p = p->next;
    }
    if (issLinkListEmpty(L))
        return NONONO;
    tmp = p->next;
    p->next = tmp->next;
    *x = tmp->data;
    free(tmp);
    return OK;
}

Status LinkListTrave(LinkListNode *L)
{
    LinkListNode *tmp = L->next;
    while (tmp->next != NULL)
    {
        printf("-> %d ", tmp->data);
        tmp = tmp->next;
    }
    return OK;
}

void test_linklist()
{
    LinkListNode L;
    if (LinkListInit(&L))
    {
        element_type temp;
        printf("init success\n");
        if (issLinkListEmpty(&L))
            printf("list is empty\n");
        for (int i = 0; i < 10; i++)
            LinkListInsert(&L, i + 1, i);
        if (LinkListGetElement(&L, 1, &temp))
            printf("The first element is %d\n", temp);
        printf("length is %d\n", LinkListLength(&L));
        LinkListGetLocation(&L, 5, &temp);
        printf("The 5 at %d\n", temp);
        printf("List:");
        LinkListTrave(&L);
        LinkListDelete(&L, 1, &temp);
        printf("delete first element is %d\n", temp);
        printf("List:");
        LinkListTrave(&L);
        if (LinkListDestroy(&L))
            printf("\ndestroy success\n");
    }
}

int main(void)
{
    test_linklist();
    return 0;
}


Leave a Reply

Your email address will not be published. Required fields are marked *