单链表

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

#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define YES 1
#define NO 0

typedef int ElemType;
typedef int Status;

#pragma warning(disable:4996)

/*
单链表的存储结构定义
*/
typedef struct Node
{
    ElemType data;    // 数据域
    struct Node* next;    // 指针域
}LinkNode, * LinkList;
// *LinkList为LinkNode类型的指针
// 定义指向结点的指针： LinkNode *p 等价于 LinkList p


/*
初始化(构造一个带头结点空表)
*/
Status InitList(LinkList* L)
{
    *L = (LinkNode*)malloc(sizeof(LinkNode));
    (*L)->next = NULL;

    return OK;
}

前插法

/*
单链表的建立（前插法）
*/
void CreateList_Head(LinkList L, int n)
{
    ElemType e;

    for (int i = 0; i < n; i++) {
        LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode)); // 生成新结点
        scanf("%d", &e);
        p->data = e; // 输入元素值
        p->next = L->next;
        L->next = p; // 插入到表头
    }
}

尾插法

/*
单链表的建立（尾插法）
*/
void CreateList_Rear(LinkList L, int n)
{
    ElemType e;

    LinkList r = L; // 尾指针r指向头结点
    for (int i = 0; i < n; i++) {
        LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode)); // 生成新结点
        scanf("%d", &e); // 输入元素值
        p->data = e;
        p->next = NULL;
        r->next = p; // 插入到表尾
        r = p; // r指向新的尾结点
    }
}


/*
清空，将L重置为空表
*/
Status ClearList(LinkList L)
{
    LinkNode* p;
    LinkNode* q;
    p = L->next; // p指向第一个结点

    while (p) // 没到表尾
    {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL; // 头结点指针域为空

    return OK;
}


/*
求表长，返回L中数据元素个数
*/
int GetListLength(LinkList L)
{
    LinkNode* p = L->next; // p指向第一个结点
    int len = 0;

    // 遍历单链表,统计结点数
    while (p) {
        len++;
        p = p->next;
    }

    return len;
}


/*
判断表是否为空
*/
Status IsListEmpty(LinkList L)
{
    // 若L为空表，则返回YES，否则返回NO
    if (L->next) // 非空
        return NO;
    else
        return YES;
}


/*
取值（根据位置i获取相应位置数据元素的内容，0<i<=len）
*/
Status GetElem(LinkList L, int i, ElemType* e)
{
    LinkNode* p = L->next;
    int j = 1; // 初始化

    // 向后扫描，直到p指向第i个元素或p为空
    while (p && j < i) {
        p = p->next;
        j++;
    }

    if (!p || j > i) {
        return ERROR; // 第i个元素不存在
    }

    (*e) = p->data; // 若存在，取第i个元素

    return OK;
}

获取数据所在位置

/*
查找（根据指定数据，获取数据所在位置）
*/
LinkNode* LocateELem(LinkList L, ElemType e)
{
    // 返回L中值为e的数据元素的地址，查找失败返回NULL
    LinkNode* p = L->next;

    while (p && p->data != e) {
        p = p->next;
    }

    return p;
}

获取数据所在位序

/*
查找（根据指定元素，返回指定元素位序，0<序号<=len）
*/
int SearchElem(LinkList L, ElemType e)
{
    // 返回L中值为e的数据元素的位置序号，查找失败返回0
    LinkNode* p = L->next;
    int j = 1;

    while (p && p->data != e)
    {
        p = p->next; j++;
    }

    if (p) {
        return j;
    }
    else {
        return 0;
    }
}


/*
插入，将元素插入到指定位序（插在第 i 个结点之前，0<i<=len+1）
*/
Status InsertElem(LinkList L, int i, ElemType e)
{
    LinkList p = L;
    int j = 0;

    // 寻找第i-1个结点
    while (p && j < i - 1) {
        p = p->next;
        j++;
    } 

    if (!p || j > i - 1) {
        return ERROR; // i大于表长 + 1或者小于1
    }

    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode)); //生成新结点s
    s->data = e; // 将结点s的数据域置为e
    s->next = p->next; // 将结点s插入L中
    p->next = s;

    return OK;
}


/*
删除（删除第 i 个结点）
*/
Status DeleteElem(LinkList L, int i, ElemType* e)
{
    LinkList p = L;
    int j = 0;

    // 寻找第i个结点，并令p指向其前驱
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }

    if (!(p->next) || j > i - 1) {
        return ERROR; // 删除位置不合理
    }

    LinkNode* q = p->next; // 临时保存被删结点的地址以备释放
    p->next = q->next; // 改变删除结点前驱结点的指针域
    (*e) = q->data; // 保存删除结点的数据域
    free(q); // 释放删除结点的空间

    return OK;
}



/*
销毁
*/
Status DestroyList(LinkList L)
{
    LinkList p;
    while (L)
    {
        p = L;
        L = L->next;
        free(p);
    }

    return OK;
}


/*
遍历打印链表
*/
void PrintLinkList(LinkList L)
{
    LinkNode* p = L->next;

    while (p)
    {
        printf("%d", p->data);
        p = p->next;
        if (p) {
            printf(" ");
        }
    }
}


int main() {
    // 测试数据：1 32 80 60 44 7 9 10
    LinkList L;

    Status a1 = InitList(&L);
    printf("初始化：\na1 = %d\n", a1);

    printf("\n头插法：");
    CreateList_Head(L, 8);
    printf("链表打印：");
    PrintLinkList(L);

    Status a2 = ClearList(L);
    printf("\n\n清空链表：a2 = %d\n", a2);
    printf("链表打印：");
    PrintLinkList(L);

    printf("\n\n尾插法：");
    CreateList_Rear(L, 8);
    printf("链表打印：");
    PrintLinkList(L);

    printf("\n\n求表长：");
    int len1 = GetListLength(L);
    printf("\nlen1 = %d\n", len1);

    printf("\n判断是否为空：\n");
    Status a3 = IsListEmpty(L);
    printf("a3 = %d\n", a3);

    printf("\n取值：\n");
    ElemType e1;
    Status a4 = GetElem(L, 9, &e1);
    printf("a4 = %d, e1 = %d\n", a4, e1);
    a4 = GetElem(L, 1, &e1);
    printf("a4 = %d, e1 = %d\n", a4, e1);
    a4 = GetElem(L, 3, &e1);
    printf("a4 = %d, e1 = %d\n", a4, e1);
    a4 = GetElem(L, 8, &e1);
    printf("a4 = %d, e1 = %d\n", a4, e1);

    printf("\n查询元素地址：\n");
    ElemType e2 = 1;
    LinkNode* p1 = LocateELem(L, e2);
    printf("p1 = %p, p1->data = %d\n", p1, p1->data);
    ElemType e3 = 6;
    LinkNode* p2 = LocateELem(L, e3);
    printf("p2 = %p\n", p2);
    ElemType e4 = 10;
    LinkNode* p3 = LocateELem(L, e4);
    printf("p3 = %p, p3->data = %d\n", p3, p3->data);

    printf("\n查询元素序号：\n");
    int a5 = SearchElem(L, e2);
    printf("a5 = %d\n", a5);
    int a6 = SearchElem(L, e3);
    printf("a6 = %d\n", a6);
    int a7 = SearchElem(L, e4);
    printf("a7 = %d\n", a7);

    printf("\n插入元素：\n");
    Status a8 = InsertElem(L, 9, 99);
    printf("a8 = %d\n", a8);
    printf("链表打印：");
    PrintLinkList(L);
    a8 = InsertElem(L, 1, 11);
    printf("\na8 = %d\n", a8);
    printf("链表打印：");
    PrintLinkList(L);

    printf("\n\n删除元素：\n");
    ElemType e5;
    Status a9 = DeleteElem(L, 3, &e5);
    printf("链表打印：");
    PrintLinkList(L);

    printf("\n\n销毁链表：");
    Status a10 = DestroyList(L);
    printf("\n%p", L);
    printf("\n%p", L->next);

    return 0;
}

测试结果：

手机扫一扫

移动阅读更方便

你可能感兴趣的文章