线性表的链式存储结构-单链表（c语言版）

什么是链式存储？

借助元素存储地址的指针表示数据元素之间的逻辑关系。

什么是线性表的链式存储结构？

在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

线性表（链式存储）的基本操作

1.初始化
2.销毁
3.清空
4.获取长度
5.判空
6.取值
7.插入
8.删除

定义结构体

//定义一个链表的结点（元素） 
typedef struct LNode{
    int data;//数据域
    struct LNode *next;//指向自己类型的指针域  
}LNode,*LinkList;//LinkList 为LNode类型的指针

初始化单链表

//（1）初始化操作
int InitList_L(LinkList &L) {
    L=(LinkList)malloc(sizeof(LNode));//生成一个LNode类型的 头 结点 
    L->next=NULL;
    return 0;
}

销毁单链表

//（2）销毁链表
int DestroyList_L(LinkList &L){
    LinkList p;
    while(L){
        p = L;
        L = L->next;
        free(p);
    }
    return 0;
}

清空单链表

//（3）清空链表 
int ClearList_L(LinkList &L){
    LinkList p,q;
    p=L->next;  //指向第一个结点 
    while(p){
        q=p->next;
        free(p);
        p=q;
    }
    L->next = NULL;//头结点的指针域指向NULL 
    return 0;
}

获取单链表的长度

//（4）获取链表的长度 
int GetListLength_L(LinkList L){
    LinkList p = L->next; 
    int j = 0;
    while(p){
        p = p->next;
        j++;
    }
    return j;
}

判断单链表是否为空

//（5）判断链表是否为空
int IsEmpty(LinkList L){
    if(L->next){
        return 0;
    }else{
        return 1;
    }
}

获取单链表中指定位置的元素

//（6）取值（获取链表指定位置的数据） 
int GetElem_L(LinkList L,int i){
    int j=0;
    LinkList p=L->next;
    while(p&&j<i-1){
        p = p->next;
        j++;
    }
    return p->data;
}

向单链表中插入一个元素

//（7）插入 在链表的指定位置插入元素
int InsertList_L(LinkList &L,int i,int data) {
    LinkList p = L ;int j = 0;
    while(p&&j<i-1){ //寻找插入结点的位置 
        p = p->next; 
        ++j;
    }//当j>=i时 p 所指的位置为需要插入的位置 
    if(!p) return 1; //链表为空 或 插入位置大于表长
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = data;
    s->next = p->next;
    p->next = s;
    return 0;
}

删除单链表中指定位置的元素

//（8）删除 删除指定位置的元素
int DeleteList_L(LinkList &L,int i){
    LinkList p = L;
    int j=0;
    while(p&&j<i-1){
        p = p->next;
        ++j;
    }
    if(!(p->next)) return 1;
    LinkList q = p->next;//临时保存需要删除的结点 
    p->next = q->next;
    free(q);
    return 0;
}

完整代码

#include <stdio.h>
#include <stdlib.h>
//定义一个链表的结点（元素） 
typedef struct LNode{
    int data;//数据域
    struct LNode *next;//指向自己类型的指针域  
}LNode,*LinkList;//LinkList 为LNode类型的指针 
//（1）初始化操作
int InitList_L(LinkList &L) {
    L=(LinkList)malloc(sizeof(LNode));//生成一个LNode类型的 头 结点 
    L->next=NULL;
    return 0;
}
//（2）销毁链表
int DestroyList_L(LinkList &L){
    LinkList p;
    while(L){
        p = L;
        L = L->next;
        free(p);
    }
    return 0;
}
//（3）清空链表 
int ClearList_L(LinkList &L){
    LinkList p,q;
    p=L->next;//指向第一个结点 
    while(p){
        q=p->next;
        free(p);
        p=q;
    }
    p->next = NULL;//头结点的指针域指向NULL 
    return 0;
}
//（4）获取链表的长度 
int GetListLength_L(LinkList L){
    LinkList p = L->next; 
    int j = 0;
    while(p){
        p = p->next;
        j++;
    }
    return j;
} 
//（5）判断链表是否为空
int IsEmpty(LinkList L){
    if(L->next){
        return 0;
    }else{
        return 1;
    }
} 
//（6）取值（获取链表指定位置的数据） 
int GetElem_L(LinkList L,int i){
    int j=0;
    LinkList p=L->next;
    while(p&&j<i-1){
        p = p->next;
        j++;
    }
    return p->data;
} 
//（7）插入 在链表的指定位置插入元素
int InsertList_L(LinkList &L,int i,int data) {
    LinkList p = L ;int j = 0;
    while(p&&j<i-1){ //寻找插入结点的位置 
        p = p->next; 
        ++j;
    }//当j>=i时 p 所指的位置为需要插入的位置 
    if(!p) return 1; //链表为空 或 插入位置大于表长
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = data;
    s->next = p->next;
    p->next = s;
    return 0;
}
//（8）删除 删除指定位置的元素
int DeleteList_L(LinkList &L,int i){
    LinkList p = L;
    int j=0;
    while(p&&j<i-1){
        p = p->next;
        ++j;
    }
    if(!(p->next)) return 1;
    LinkList q = p->next;//临时保存需要删除的结点 
    p->next = q->next;
    free(q);
    return 0;
} 
main(){
    LinkList L;
    //初始化
    int initStatus;//初始化状态 
    int isEmpty;//是否为空 
    int insertStatus;//插入状态 
    int deleteStatus;//删除状态 
    int listLength;//链表长度 
    int destroyStatus;//销毁状态 


    initStatus = InitList_L(L);
    if(initStatus==0){
        printf("初始化成功！\n");
    } else{
        printf("初始化失败！\n");
    }

    isEmpty = IsEmpty(L);
    if(isEmpty==0){
        printf("链表不为空\n");
    } else{
        printf("链表为空\n"); 
    }


    insertStatus = InsertList_L(L,1,1); //插入元素 1 
    insertStatus = InsertList_L(L,2,2); //插入元素 2 
    insertStatus = InsertList_L(L,2,3); //插入元素 3
    if(insertStatus==0){
        printf("插入成功！\n");
    }else{
        printf("插入失败！\n");
    }


    listLength = GetListLength_L(L); 
    printf("插入后链表长度： %d\n",listLength);    

    isEmpty = IsEmpty(L);
    if(isEmpty==0){
        printf("链表不为空\n");
    } else{
        printf("链表为空\n"); 
    }

    int t5 = GetElem_L(L,3);
    printf("第三个位置元素为： %d\n",t5);    

    deleteStatus = DeleteList_L(L,2); 
    if(deleteStatus==0){
        printf("删除成功\n");
    }else{
        printf("删除失败\n");
    }

    listLength = GetListLength_L(L); 
    printf("删除后链表长度： %d\n",listLength);

    destroyStatus = DestroyList_L(L);
    if(destroyStatus==0){
        printf("销毁成功\n");
    } else{
        printf("销毁失败\n");
    }
}