线性表链式储存

以你之姓@ 2022-05-31 08:37 220阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    typedef int ElemType;
    
    
    typedef struct Node
    {
        ElemType data;
        struct Node* next;
    }*LinkList;
    
    
    //initate a linked list
    Status InitList(LinkList *h)//or &h
    {
        *h = (LinkList)malloc(sizeof(struct Node));//or h
        if (!(*h))//or h
            return ERROR;
        (*h)->next = NULL;//or h
        return OK;
    }
    
    //judge whether the linked list is empty or not
    Status ListEmpty(LinkList L)
    {
        if (!L->next)
            return TRUE;
        else
            return FALSE;
    }
    
    //insert element e into the linked list in the position of i
    Status ListInsert(LinkList *h, ElemType e, int i)
    {
        int j=1;
        LinkList p,q;
        p = *h;
        while (p&&j < i)
        {
            p = p->next;
            ++j;
        }
        if (!p || j > i)
            return ERROR;
        else
        {
            q = (LinkList)malloc(sizeof(struct Node));
            q->data = e;
            q->next = p->next;
            p->next = q;
            return OK;
        }
    }
    
    //delete the node in the position of i and return its element as e
    Status ListDelete(LinkList *h, int i, ElemType *e)
    {
        int j = 1;
        LinkList p, q;
        p = *h;
        while (p->next&&j < i)
        {
            p = p->next;
            ++j;
        }
        if (!p->next || j > i)
            return ERROR;
        else
        {
            q = p->next;
            *e = q->data;
            printf("delete %d", *e);
            p->next = q->next;
            free(q);
            return OK;
        }
    }
    
    //头插法,随机产生n个元素的值，建立带表头结点的单链线性表
    void CreateListHead(LinkList *h, int n)
    {
        LinkList p,pre;
        p = *h;
        p= (LinkList)malloc(sizeof(struct Node));
        int i = 0;
        srand(time(0));
        for (i; i < n; ++i)
        {
            pre = (LinkList)malloc(sizeof(struct Node));
            pre->data = rand() % n + 1;
            pre->next = p->next;
            p->next = pre;
    
        }
    }
    
    //尾插法,随机产生n个元素的值，建立带表头结点的单链线性表
    void CreateListTail(LinkList *h,int n)
    {
        LinkList p, pre;
        int i=0;
        p = *h;
        p= (LinkList)malloc(sizeof(struct Node));
        srand(time(0));
        for (i; i < n; i++)
        {
            pre= (LinkList)malloc(sizeof(struct Node));
            pre->data = rand() % n + 1;
            p->next = pre;
            p = pre->next;
        }
        p->next = NULL;
    }
    
    //直接搬运的不太重要的部分
    
    
    Status visit(ElemType c)
    {
        printf("%d ", c);
        return OK;
    }
    /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
    Status ClearList(LinkList *L)
    {
        LinkList p, q;
        p = (*L)->next;           /*  p指向第一个结点 */
        while (p)                /*  没到表尾 */
        {
            q = p->next;
            free(p);
            p = q;
        }
        (*L)->next = NULL;        /* 头结点指针域为空 */
        return OK;
    }
    
    /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
    int ListLength(LinkList L)
    {
        int i = 0;
        LinkList p = L->next; /* p指向第一个结点 */
        while (p)
        {
            i++;
            p = p->next;
        }
        return i;
    }
    
    /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    /* 操作结果：用e返回L中第i个数据元素的值 */
    Status GetElem(LinkList L, int i, ElemType *e)
    {
        int j;
        LinkList p;		/* 声明一结点p */
        p = L->next;		/* 让p指向链表L的第一个结点 */
        j = 1;		/*  j为计数器 */
        while (p && j<i)  /* p不为空或者计数器j还没有等于i时，循环继续 */
        {
            p = p->next;  /* 让p指向下一个结点 */
            ++j;
        }
        if (!p || j>i)
            return ERROR;  /*  第i个元素不存在 */
        *e = p->data;   /*  取第i个元素的数据 */
        return OK;
    }
    /* 初始条件：顺序线性表L已存在 */
    /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
    /* 若这样的数据元素不存在，则返回值为0 */
    int LocateElem(LinkList L, ElemType e)
    {
        int i = 0;
        LinkList p = L->next;
        while (p)
        {
            i++;
            if (p->data == e) /* 找到这样的数据元素 */
                return i;
            p = p->next;
        }
    
        return 0;
    }
    /* 初始条件：顺序线性表L已存在 */
    /* 操作结果：依次对L的每个数据元素输出 */
    Status ListTraverse(LinkList L)
    {
        LinkList p = L->next;
        while (p)
        {
            visit(p->data);
            p = p->next;
        }
        printf("\n");
        return OK;
    }
    
    //主函数
    int main()
    {
        LinkList L;
        ElemType e;
        Status i;
        int j, k;
        i = InitList(&L);
        printf("初始化L后：ListLength(L)=%d\n", ListLength(L));
        for (j = 1; j <= 5; j++)
            i = ListInsert(&L, 1, j);
        printf("在L的表头依次插入1～5后：L.data=");
        ListTraverse(L);
    
        printf("ListLength(L)=%d \n", ListLength(L));
        i = ListEmpty(L);
        printf("L是否空：i=%d(1:是 0:否)\n", i);
    
        i = ClearList(&L);
        printf("清空L后：ListLength(L)=%d\n", ListLength(L));
        i = ListEmpty(L);
        printf("L是否空：i=%d(1:是 0:否)\n", i);
    
        for (j = 1; j <= 10; j++)
            ListInsert(&L, j, j);
        printf("在L的表尾依次插入1～10后：L.data=");
        ListTraverse(L);
    
        printf("ListLength(L)=%d \n", ListLength(L));
    
        ListInsert(&L, 1, 0);
        printf("在L的表头插入0后：L.data=");
        ListTraverse(L);
        printf("ListLength(L)=%d \n", ListLength(L));
    
        GetElem(L, 5, &e);
        printf("第5个元素的值为：%d\n", e);
        for (j = 3; j <= 4; j++)
        {
            k = LocateElem(L, j);
            if (k)
                printf("第%d个元素的值为%d\n", k, j);
            else
                printf("没有值为%d的元素\n", j);
        }
    
    
        k = ListLength(L); /* k为表长 */
        for (j = k + 1; j >= k; j--)
        {
            i = ListDelete(&L, j, &e); /* 删除第j个数据 */
            if (i == ERROR)
                printf("删除第%d个数据失败\n", j);
            else
                printf("删除第%d个的元素值为：%d\n", j, e);
        }
        printf("依次输出L的元素：");
        ListTraverse(L);
    
        j = 5;
        ListDelete(&L, j, &e); /* 删除第5个数据 */
        printf("删除第%d个的元素值为：%d\n", j, e);
    
        printf("依次输出L的元素：");
        ListTraverse(L);
    
        i = ClearList(&L);
        printf("\n清空L后：ListLength(L)=%d\n", ListLength(L));
        CreateListHead(&L, 20);
        printf("整体创建L的元素(头插法)：");
        ListTraverse(L);
    
        i = ClearList(&L);
        printf("\n删除L后：ListLength(L)=%d\n", ListLength(L));
        CreateListTail(&L, 20);
        printf("整体创建L的元素(尾插法)：");
        ListTraverse(L);
    
    
        return 0;
    }