美文网首页
线性表之链式表代码（c语言版）

线性表之链式表代码（c语言版）

作者: cccccttttyyy | 来源:发表于2019-03-07 14:03 被阅读0次

一、关键点

1. 传Linklist *L 和 LinkList L区别;

区别
L是指向定义的Node结构体指针的指针,所以(*L)是指向Node结构体的指针,可以用->运算符来访问结构体成员,即 (*L)->elem,当然, (**L)就是Node型结构体了,所以可以用点运算符来访问结构体成员,即 (**L).elem;
选择准则
如果函数会改变指针L的值,而你希望函数结束调用后保存L的值,那你就要用LinkList *L,这样,向函数传递的就是指针的地址,结束调用后,自然就可以去改变指针的值;
而如果函数只会修改指针所指向的内容,而不会更改指针的值,那么用LinkListL就行了;
(什么叫改变指针L的值？ 改变链表L首节点里面的data或next不算改变了其指针的值。改变了指针L的指向的地址，如初始化时声明并指向了新的地址才算改变了指针的值)

2. 对列表操作时，游标指针数量的选择

单向链表能根据某结点直接找到其后继结点，但无法找到其前驱结点，所以，如果要同时获取某结点与其前驱结点进行操作，要声明两个指针，一个记录当前结点，一个记录当前结点的前一结点。如PriorElem_L()函数 。
若对当前结点前驱结点不需操作，则直接声明一个指针指向当前结点即可。

二、代码

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

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
typedef int Status;
typedef int LElemType_L;

//链表表头不存数据
typedef struct LNode{
    LElemType_L data;
    struct LNode* next;
}LNode, *LinkList;

Status CmpGreater(LElemType_L e, LElemType_L data); //判断data是否大于e //若data大于e，返回TRUE
void PrintElem(LElemType_L e);                      //测试函数，打印整型
Status InitList_L(LinkList *L);
Status ClearList_L(LinkList L);
void DestroyList_L(LinkList *L);
Status ListEmpty_L(LinkList L);
int ListLength_L(LinkList L);
Status GetElem_L(LinkList L, int i, LElemType_L *e);
int LocateElem_L(LinkList L, LElemType_L e, Status(Compare)(LElemType_L, LElemType_L));
Status PriorElem_L(LinkList L, LElemType_L cur_e, LElemType_L *pre_e);
Status NextElem_L(LinkList L, LElemType_L cur_e, LElemType_L *next_e);
Status ListInsert_L(LinkList L, int i, LElemType_L e);
Status ListDelete_L(LinkList L, int i, LElemType_L *e);
Status ListTraverse_L(LinkList L, void(Visit)(LElemType_L));
//头插法
Status CreateList_HL(LinkList *L, int n);
//尾插法
Status CreateList_TL(LinkList *L, int n);



Status InitList_L(LinkList *L){
    (*L) = (LinkList)malloc(sizeof(LNode));
    if(!(*L)){
        exit(OVERFLOW);
    }
    (*L)->next = NULL;
    return OK;
}

Status ClearList_L(LinkList L){
    if(!L){
        return ERROR;
    }
    LinkList pre,p;
    pre = L->next;
    while(pre){
        p = pre->next;
        free(pre);
        pre = p;
    }
    L->next = NULL;
    return OK;
}

void DestroyList_L(LinkList *L){
    LinkList p;
    while(*L){
       p = (*L)->next;
       free(*L);
       (*L) = p;
    }
}

Status ListEmpty_L(LinkList L){
    if(L!=NULL&&L->next==NULL){
        return TRUE;
    }else{
        return FALSE;
    }
}

int ListLength_L(LinkList L){
    if(!L){
        return 0;
    }
    LinkList p;
    p = L->next;
    int i = 0;
    while(p){
        i++;
        p = p->next;
    }
    return i;
}

Status GetElem_L(LinkList L, int i, LElemType_L *e){
    LinkList p;
    p = L->next;
    int cur = 1;
    while(p&&cur<i){
            p = p->next;
            cur++;
    }
    if(!p||cur>i){
        return ERROR;
    }
    *e = p->data;
    return OK;
}

int LocateElem_L(LinkList L, LElemType_L e, Status(Compare)(LElemType_L, LElemType_L)){
    if(!L||L->next==NULL){
        return -1;
    }
    LinkList p;
    p = L->next;
    int cur =1;
    while(p){
        if(Compare(e,p->data)){
            return cur;
        }else{
            p = p->next;
            cur++;
        }
    }
    return -1;
}

Status PriorElem_L(LinkList L, LElemType_L cur_e, LElemType_L *pre_e){
    if(!L||L->next==NULL){
        return ERROR;
    }
    LinkList p ,q;
    p = L->next;
    if(p->data==cur_e){
        return ERROR;
    }
    while(p){
        q = p->next;
        if(q&&q->data==cur_e){
            *pre_e = p->data;
            return OK;
        }
        p=q;
    }
    return ERROR;
}

Status NextElem_L(LinkList L, LElemType_L cur_e, LElemType_L *next_e){
    if(!L||L->next==NULL){
        return ERROR;
    }
    LinkList p;
    p = L->next;
    while(p){
        if(p->data==cur_e){
            if(p->next){
                *next_e = p->next->data;
                return OK;
            }
        }
        p = p->next;
    }
    return ERROR;
}

Status ListInsert_L(LinkList L, int i, LElemType_L e){
    if(!L){
        return ERROR;
    }
    LinkList p=L;
    int cur =1;
    while(p&&cur<i){
        p=p->next;
        cur++;
    }
    if(!p||cur>i){
        return ERROR;
    }else{
        LinkList temp = (LinkList)malloc(sizeof(LNode));
        if(!temp){
            exit(OVERFLOW);
        }
        temp->data = e;
        temp->next = p->next;
        p->next = temp;
        return OK;
    }
}

Status ListDelete_L(LinkList L, int i, LElemType_L *e){
    if(!L||L->next==NULL){
        return ERROR;
    }
    LinkList p,pre;
    int cur = 1;
    pre = L;
    p = L->next;
    while(p&&cur<i){
        pre = p;
        p=p->next;
        cur++;
    }
    if(!p||cur>i){
        return ERROR;
    }else{
        pre->next = p->next;
        *e = p->data;
        free(p);
        return OK;
    }
}

Status ListTraverse_L(LinkList L, void(Visit)(LElemType_L)){
    if(!L||L->next==NULL){
        return ERROR;
    }
    LinkList p;
    p = L->next;
    while(p){
        Visit(p->data);
        p=p->next;
    }
    return OK;
}

Status CreateList_HL(LinkList *L, int n){
    (*L) = (LinkList)malloc(sizeof(LNode));
    if(!L){
        exit(OVERFLOW);
    }
    (*L)->next = NULL;
    int a;
    for(int i =0 ;i<n;i++){
        scanf("%d",&a);
        LinkList p;
        p = (LinkList)malloc(sizeof(LNode));
        if(!p){
            exit(OVERFLOW);
        }
        p->data = a;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

Status CreateList_TL(LinkList *L, int n){
    (*L) = (LinkList)malloc(sizeof(LNode));
    if(!L){
        exit(OVERFLOW);
    }
    (*L)->next = NULL;
    LinkList tail;
    tail = (*L);
    int a;
    for(int i =0 ;i<n;i++){
        scanf("%d",&a);
        LinkList p;
        p = (LinkList)malloc(sizeof(LNode));
        if(!p){
            exit(OVERFLOW);
        }
        p->data = a;
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
}

Status CmpGreater(LElemType_L e, LElemType_L data)
{
    return data>e ? TRUE : FALSE;
}

void PrintElem(LElemType_L e)
{
    printf("%d ", e);
}


int main(int argc, char **argv){
LinkList L;
    int i;
    LElemType_L e;

    printf("▼1\n▲函数 InitList_L 测试...\n");           //1.函数InitList_L测试
    {
        printf("初始化单链表 L ...\n");
        InitList_L(&L);
        printf("\n");
    }

    printf("▼4\n▲函数 ListEmpty_L 测试...\n");      //4.函数ListEmpty_L测试
    {
        ListEmpty_L(L) ? printf(" L 为空！！\n") : printf(" L 不为空！\n");
        printf("\n");
    }

    printf("▼10\n▲函数 ListInsert_L 测试...\n");        //10.函数ListInsert_L测试
    {
        for(i=1; i<=6; i++)
        {
            printf("在 L 第 %d 个位置插入 \"%d\" ...\n", i, 2*i);
            ListInsert_L(L, i, 2*i);
        }
        printf("\n");
    }

    printf("▼12\n▲函数 ListTraverse_L 测试...\n");  //12.函数ListTraverse_L测试
    {
        printf(" L 中的元素为：L = ");
        ListTraverse_L(L, PrintElem);
        printf("\n\n");
    }

    printf("▼5\n▲函数 ListLength_L 测试...\n");     //5.函数ListLength_L测试
    {
        printf(" L 的长度为 %d \n", ListLength_L(L));
        printf("\n");
    }

    printf("▼11\n▲函数 ListDelete_L 测试...\n");        //11.函数ListDelete_L测试
    {
        ListDelete_L(L, 6, &e);
        printf("删除 L 中第 6 个元素 \"%d\" ...\n", e);
        printf(" L 中的元素为：L = ");
        ListTraverse_L(L, PrintElem);
        printf("\n\n");
    }

    printf("▼6\n▲函数 GetElem_L 测试...\n");            //6.函数GetElem_L测试
    {
        GetElem_L(L, 4, &e);
        printf(" L 中第 4 个位置的元素为 \"%d\" \n", e);
        printf("\n");
    }

    printf("▼7\n▲函数 LocateElem_L 测试...\n");     //7.函数LocateElem_L测试
    {
        i = LocateElem_L(L, 7, CmpGreater);
        printf(" L 中第一个元素值大于 \"7\" 的元素的位置为 %d \n", i);
        printf("\n");
    }

    printf("▼8\n▲函数 PriorElem_L 测试...\n");      //8.函数PriorElem_L测试
    {
        PriorElem_L(L, 6, &e);
        printf("元素 \"6\" 的前驱为 \"%d\" \n", e);
        printf("\n");
    }

    printf("▼9\n▲函数 NextElem_L 测试...\n");           //9.函数NextElem_L测试
    {
        NextElem_L(L, 6, &e);
        printf("元素 \"6\" 的后继为 \"%d\" \n", e);
        printf("\n");
    }

    printf("▼2\n▲函数 ClearList_L 测试...\n");      //2.函数ClearList_L测试
    {
        printf("清空 L 前：");
        ListEmpty_L(L) ? printf(" L 为空！！\n") : printf(" L 不为空！\n");
        ClearList_L(L);
        printf("清空 L 后：");
        ListEmpty_L(L) ? printf(" L 为空！！\n") : printf(" L 不为空！\n");
        printf("\n");
    }

    printf("▼3\n▲函数 DestroyList_L 测试...\n");        //3.函数DestroyList_L测试
    {
        printf("销毁 L 前：");
        L ? printf(" L 存在！\n") : printf(" L 不存在！！\n");
        DestroyList_L(&L);
        printf("销毁 L 后：");
        L ? printf(" L 存在！\n") : printf(" L 不存在！！\n");
        printf("\n");
    }

    printf("▼13\n▲函数 CreateList_HL 测试...\n");       //13.函数CreateList_HL测试
    {
        LinkList L;
        printf("头插法建立单链表 L = ");
        CreateList_HL(&L, 5);
        ListTraverse_L(L, PrintElem);
        printf("\n\n");
    }


    printf("▼14\n▲函数 CreateList_TL 测试...\n");       //14.函数CreateList_TL测试
    {
        LinkList L;
        printf("尾插法建立单链表 L = ");
        CreateList_TL(&L, 5);
        ListTraverse_L(L, PrintElem);
        printf("\n\n");
    }
    system("pause");
    return 0;

}

三、结果

image.png

相关文章

网友评论

      本文标题：线性表之链式表代码（c语言版）

      本文链接：https://www.haomeiwen.com/subject/umccpqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|线性表之链式表代码（c语言版）|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！