纯C语言实现线性链表

佚名 5年前 (2019-05-19) 算法 1113人围观抢沙发百度已收录

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

typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode;

LNode *InitList(LNode *L);//初始化
LNode *DestroyList(LNode *L);//销毁
void ClearList(LNode *L);//清空列表
int ListEmpty(LNode *L);//判空
int ListLength(LNode *L);//返回链表长度
int GetElem(LNode *L, int i, ElemType *e);//获取第i个元素
LNode* LocateElem(LNode *L, ElemType e);//定位值为e的位置
ElemType PriorElem(LNode *L, ElemType cur_e);//查找前驱
ElemType NextElem(LNode *L, ElemType cur_e);//查找后继
int ListInsert(LNode *L, int i, ElemType e);//插入元素
int ListDelete(LNode *L, int i);//删除第i个元素
void TraverseList(LNode *L);//遍历线性表

//初始化
LNode *InitList(LNode *L){
    int x;
    LNode *p = NULL;//记录前一个节点
    LNode *q = NULL;//记录后一个节点

    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    p = L;

    printf("输入直到-1为止\n");
    while(1){
        scanf("%d", &x);
        if(x == -1) {
            printf("初始化成功\n");
            break;
        }
        //初始化并赋值
        q = (LNode *)malloc(sizeof(LNode));
        if(q){
            q->data = x;
            q->next = NULL;
            //和前一个节点连接
            p->next = q;
            //遍历下去
            p = p->next;
        }else{
            printf("空间不足，初始化失败\n");
            return NULL;
        }

    }
    return L;
}

//销毁
LNode *DestroyList(LNode *L){
    LNode *p = L->next;//记录前一个元素
    LNode *q = p->next;//记录后一个元素
    while(q){
        free(p);
        p = q;
        q = q->next;
    }
    free(p);
    free(L);
    printf("销毁成功\n");
    return NULL;
}

//清空列表
void ClearList(LNode *L){
    LNode *p = L->next;
    while(p){
        p->data = 0;
        p = p->next;
    }
    printf("清空成功\n");
}

//判空,1为空,0不为空
int ListEmpty(LNode *L){
    return L->next == NULL;
}

//返回链表长度，返回链表长度
int ListLength(LNode *L){
    int len = 0;
    if(ListEmpty(L)) return 0;
    LNode *p = L->next;
    while(p){
        len++;
        p = p->next;
    }
    return len;
}

//获取第i个元素，将值保存到参数e中,返回是否获取的状态
int GetElem(LNode *L, int i, ElemType *e){
    if(ListEmpty(L)){
        printf("空链表\n");
        return 0;
    }
    LNode *p = L->next;
    int j = 1;
    while(p && j<i){
        p = p->next;
        j++;
    }
    //i值不合法 >length 或者 <=0
    if(!p||j>i) {
        printf("获取元素的位置%d不合法\n", i);
        return 0;
    }
    *e = p->data;
    printf("第%d个元素是%d\n",i,*e);
    return 1;
}

//定位值为e的位置，返回指针指向节点
LNode* LocateElem(LNode *L, ElemType e){
    LNode *p = L->next;
    while(p && p->data!=e){
        p = p->next;
    }
    return p;
}

//查找值为e的前驱，返回前驱元素
ElemType PriorElem(LNode *L, ElemType cur_e){
    LNode *p = L->next;
    int idx = 1;
    while(p && p->data!=cur_e){
        p = p->next;
        idx++;
    }
    if(!p || idx>ListLength(L)){
        printf("查不到此元素\n");
        return cur_e;
    }
    ElemType e = NULL;
    GetElem(L, idx-1, &e);
    if(e){
        printf("%d的前驱是%d\n", cur_e, e);
    }else{
        printf("%d无前驱或获取元素的位置不合法\n",cur_e);
    }
    return e;
}

//查找值为e的后继
ElemType NextElem(LNode *L, ElemType cur_e){
    LNode *Locate = LocateElem(L, cur_e);
    if(Locate && Locate->next){
        printf("%d的后继是%d\n", cur_e, Locate->next->data);
    }else{
        printf("%d无后继或获取元素的位置不合法\n",cur_e);
    }
    return Locate->next->data;
}

//插入元素
int ListInsert(LNode *L, int i, ElemType e){
    LNode *p = L;
    int j = 0;
    //指向要插入的前一个节点
    while(p && (j<i-1)){
        p = p->next;
        j++;
    }
    if(!p || j>i-1){
        printf("插入失败\n");
        return 0;}
    LNode *nLNode = (LNode *)malloc(sizeof(LNode));
    nLNode->data = e;
    nLNode->next = p->next;
    p->next = nLNode;
    printf("插入成功\n");
    return 1;
}

//删除第i个元素
int ListDelete(LNode *L, int i){
    LNode *p = L;
    LNode *q = NULL;
    int j = 0;
    //指向要删除的前一个节点
    while((p->next && (j<i-1))){
        p = p->next;
        j++;
    }
    if(!(p->next) || (j>i-1)){
        printf("删除失败\n");
        return 0;
    }
    q = p->next; //q指向即将删除的节点
    p->next = q->next;
    free(q);
    printf("删除成功\n");
    return 1;
}

//遍历线性表
void TraverseList(LNode *L){
    if(ListEmpty(L)){
        printf("空链表");
        return;
    }
    LNode *p = L->next;
    while(p){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}


int main(){
    ElemType e = NULL;
    LNode *L = NULL;
    LNode *Locate = NULL;//用于定位查找到的节点

    //初始化测试
    L = InitList(L);

    //遍历测试
    TraverseList(L);

//    //长度测试
//    printf("线性表长度为%d\n", ListLength(L));

//    //获取第i个元素测试
//    GetElem(L, 1, &e);
//    //非法操作
//    GetElem(L, 999, &e);

//    //获取值为2的元素位置测试
//    Locate = LocateElem(L, 2);
//    if(Locate){
//        printf("值为2的元素被Locate指向\n");
//    }else{
//        printf("没有值为2的元素被指向\n");
//    }

//    //获取元素值为2的前驱测试
//    PriorElem(L, 2);
//    //非法操作
//    GetElem(L, 1, &e);
//    PriorElem(L, e);

//    //获取元素值为2的后继测试
//    NextElem(L, 2);
//    //非法操作
//    GetElem(L, ListLength(L), &e);
//    NextElem(L, e);

//    //插入元素测试
//    printf("第3个位置插入999\n");
//    ListInsert(L, 1, 999);
//    TraverseList(L);
//    //非法操作
//    printf("第999位置插入999\n");
//    ListInsert(L, 999, 999);
//    TraverseList(L);

//    //删除元素测试
//    printf("删除第3个位置\n");
//    ListDelete(L, 3);
//    TraverseList(L);
//    //非法操作
//    printf("删除第999位置\n");
//    ListDelete(L, 999);
//    TraverseList(L);

//    //清空链表测试
//    ClearList(L);
//    TraverseList(L);

    //销毁测试
    L = DestroyList(L);
    TraverseList(L);
    printf("线性表长度为%d\n", ListLength(L));

}