美文网首页实用干货
【C语言实现】链式存储结构线性表(链表)

【C语言实现】链式存储结构线性表(链表)

作者: 仍有不归期 | 来源:发表于2020-06-07 00:41 被阅读0次

    链表相关的部分应用已更新 ：
    删除链表的倒数第N个节点
    合并两个有序链表
    反转链表

    有位同学希望我把链表讲的清楚一点，那这次就试试看。
    先来一波图


    图片啊.png 这是图片.png

    举个例子，假设有3个人，拿着3跟不同颜色的绳子。A拿着红绳，B拿着绿绳，C拿着蓝绳子。现在我们让3个人通过绳子牵着一起向前走，如果是A - B - C，那么A的红绳牵着是B，B的绿绳子牵的是C，而C没有牵着人。A ， B ，C三人、绳子整体是由一种特定的规律排列的。我们称 A 是 首元 也就是第一个节点

    每个节点都是由2部分组成的，也就是A和A手中的红绳。A是数据域，绳子是指针域。其实这里说的还不够恰当，其实节点除了数据域和指针域外还有第三个属性，也就是节点自己的“标志”，A手中的红绳其实就是B的标志，所以B一定是跟着A的。
    A->next = B
    ...
    ...
    ...
    白嫖老师课件的图hhha

    白嫖自老师课件的图
    是不是发现我说的还不如图，嗯，是这样的...
    线性表其实就是你去排队，然后你只能按规则前后排着，你如果要插队，

    ---------------必须要前面的所有人都同意------------

    没错，这就是重点。
    也是链表和顺序表的主要区别，链表的存取方式时顺序存取，而顺序表时随机存取。
    所以链表就很容易理解，知道链表什么意思后其实对他的各种操作就是在通过某种规则在搭建自己需要的结构。
    比如循环链表，我们只需要让尾元的next变量值是首元的地址就行了。
    last->next = top
    再比如双向链表，赋予了链表的更强的操作性，其实这些链表都只是由数据域和指针域组成，没有区别。

    node{
    //指针域
    node* pre;
    node* next;
    //数据域
    xxx  data;
}

    废话不多说...已经很多了。看代码怎么说话：

    1 结构定义
    2 初始化线性表
    3 按位查找
    4 按值查找
    5 求线性表长度 = 总空间大小/sizeof（Node） - 1
    6 插入（头插和尾插）
    7 Creat(Node *head, DataType a[], int n)//尾插法建立单链表
    8 Insert(Node head, int i, DataType x)//在线性表的第 i 个位置之前插入数据元素
    9 删除
    10 Destroy_List() //摧毁线性表
    11 Clear_List() //清空线性表
    12 List_Empty() //判断线性表是否为空
    13 Get_Prev() //返回当前元素的前一个元素值
    14 Get_Next() //返回当前元素的后一个元素值
    15 Traverse_Link(Node     head, visit( )) //遍历线性表

    1. 结构定义
    typedef int DataType;
//单链表的存储结构定义
struct Node{
    DataType data; //数据域
    struct Node *next; //指针域
};
typedef struct Node Node;
    2.0 初始化链表并赋值（2020/3/11）
    node* h = (node*)malloc(sizeof(node));//分配首元空间，记得需要强制转换void*为node*类型
h->next = NULL;

void Read(node *h, int n){//调用read顺序输入
    int x;
    node *p = h;
    int i;
    for(i = 0 ; i < n ; ++i){
        scanf("%d", &x);
        node* t = (node*)malloc(sizeof(node));
        t->data = x;
        t->next = NULL;//要记得给尾元做上标记
        p->next = t;
        p = p->next;
    }
}
    2.1 InitList(Node *head)//初始化线性表
    Node *InitList(Node *head){//传入头节点
    head = (Node*)malloc(sizeof(Node)); //给头节点分配内存空间
    head -> next = NULL; //将指针域置为NULL，避免错误访问
    return head; //将分配好空间后的头节点返回
}
    3. Get(Node *head, int i)//取线性表中第 i 个数据元素的值
    DataType Get(Node *head, int i){
    Node *p = head -> next; //定义p指针指向第一个节点
    int count = 1;
    while(count < i && p != NULL){//开始计数，直到第i个节点跳出循环
        ++count;
        p = p -> next;
    }
    if(p == NULL){ //如果节点为空，返回信息，退出
        printf("访问错误\n");
        exit(0);
    }
    return p -> data; //返回节点数据域值
}
    4. Locate(Node *head, DataType x) //返回给定值在线性表中的位置
    int Locate(Node *head, DataType x){
    Node *p = head -> next; //定义p指针指向第一个节点
    int count = 1; //从第一个节点开始计数
    while(p != NULL){
        if(p -> data == x) //如果找到了，返回节点位置
            return count;
        ++count;
        p = p -> next;
    }

    return 0; //未找到，返回0
}
    5. Length(Node *head)//求线性表的长度
    //求线性表长度 = 总空间大小/sizeof（Node） - 1
int Length(Node *head){
    if(head == NULL){
        printf("---线性表未创建---");
        return -1;
    }
    int count = 0; //计数变量count = 0
    Node *p = head -> next; //定义p指针指向第一个节点
    while(p != NULL){
        p = p -> next; //向前传递
        ++count; //计数
    }
    return count; //返回长度
}
    6. 插入（头插和尾插）
    //插入数据(头插法)
void Push_Head(Node *head, DataType data){
    Node *np = Create_Node(data); //创建一个新的节点
    np->next = head -> next;
    head->next = np;
}

//插入数据(尾插法)
void Push_Tail(Node *head, DataType data){
    Node* p = head;
    while (p -> next != NULL){//找到最后一个节点
        p = p -> next;
    }
    Node *np = Create_Node(data);
    p -> next = np; //插入元素
}
    7. Creat(Node *head, DataType a[], int n)//尾插法建立单链表
    //建立单链表（尾插法）
Node *Creat(Node *head, DataType a[], int n){
    head = InitList(head);

    int i;
    for(i = 0 ; i < n ; ++i){ //循环插入元素
        Push_Tail(head, a[i]); //尾插
    }
    return head;
}
    8. Insert(Node *head, int i, DataType x)//在线性表的第 i 个位置之前插入数据元素
    void Insert(Node *head, int i, DataType x){
    Node *p = head; //p指向头节点，因为第一个节点要通过头节点来插入
    int count = 0;

    while(p != NULL && count < i - 1){
        p = p -> next;
        ++count;
    }
    //跳出循环时p指向第i - 1个节点

    if(p == NULL){ //如果第i-1个节点为空，则插入节点失败，返回
        printf("插入节点失败");
        exit(-1);
    }
    //插入第i个节点
    Node *s = (Node*)malloc(sizeof(Node));
    s -> data = x;
    s -> next = p -> next;
    p -> next = s;
}
    9. 删除

    Delete(Node *head, Node *s)

    //删除节点
DataType Delete(Node *head, Node *s){
    Node* p = s; //把要删除的节点保存起来
    DataType x = p -> data;
    While(head -> next != s){
        head = head -> next;
    }
    head -> next = s -> next; //连接它的前节点与后节点
    free(p); //释放
    return x;
}

    Delete_L(Node *head, int i)//删除线性表中第 i 个数据元素

    //按位删除节点
DataType Delete_L(Node *head, int i){
    Node *p = head;
    int len = Length(head);
    if(i > len)
        printf("删除失败");
        exit(-1);
    }
    int j;
    for(j = 1 ; j < i ; ++j){
        p = p -> next;
    }
    int x = Delete(head, p -> next); //这里只是为了用上Delete(),最好像注释那样写
    /*
    Node *q = p -> next;
    int x = q -> data; //存储被删除节点的数据
    p -> next = q -> next; //取出q节点
    free(q); //释放空间
    */
    return x; //返回被删除节点的数据
}
    10. Destroy_List() //摧毁线性表
    //摧毁线性表
Node *Destroy_List(Node *head){
    Node* p = head;
    while(p != NULL){//依次回收节点
        p = head -> next;
        free(head);
        head = p;
    }
    return NULL; //返回后许重新赋值给头节点
}
    11. Clear_List() //清空线性表
    //Clear_List()
void Clear_List(Node *head){
    Destroy_List(head -> next);//摧毁除头节点以外其他节点
    head -> next = NULL; //给头节点指针域置空
}
    12. List_Empty() //判断线性表是否为空
    int List_Empty(Node *head){
    if(head->next == NULL)return 0;
    return 1;
    //return Length(head) > 0; //空 0 非空 1
}
    13. Get_Prev() //返回当前元素的前一个元素值
    DataType Get_Prev(Node *head, DataType x){
    int l = Locate(head, x) - 1; //获取前一个元素的序号
    if(l > 0)
        return Get(head,l);  //通过Get得到数据
    else{
        printf("当前元素已经是第一个元素");
        exit(-1);
    }
}
    14. Get_Next() //返回当前元素的后一个元素值
    DataType Get_Next(Node *head, DataType x){
    int l = Locate(head, x) + 1; //获取后一个元素的序号
    if(l < Length(head))
        return Get(head,l) ; //通过Get得到数据
    else{
        printf("当前元素已经是最后一个元素");
        exit(-1);
    }
}
    15. Traverse_Link(Node* head, visit( )) //遍历线性表
    void Traverse_Link(Node* head, void visit()){
    Node *p = head -> next;
    while(p != NULL){
        visit(p); //调用自定义功能函数
        p = p -> next;
    }
}

    测试：

    #include"Link.h"
#include<stdio.h>

void print(Node *p){
    printf("%d ", p -> data);
}

int main(){
    Node *head;
    int a[5] = {1, 2, 3, 4, 5};
    head = Creat(head,a,5);
    printf("%d\n", Get(head,3));
    Traverse_Link(head, print);

    printf("\n线性表是否为空(0空 1非空）：%d\n" , List_Empty(head));

    printf("线性表长度: %d\n", Length(head));

    Clear_List(head);
    printf("线性表长度: %d\n", Length(head));

    head = Destroy_List(head);
    printf("线性表长度: %d\n", Length(head));

    return 0;
}


outputs:
3
1 2 3 4 5
线性表是否为空(0空 1非空）：1
线性表长度: 5
线性表长度: 0
---线性表未创建---线性表长度: -1

    终于写完了，如果有bug再陆续修改。
    下面放

    完整代码：

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

typedef int DataType;
//单链表的存储结构定义
struct Node{
    DataType data; //数据域
    struct Node *next; //指针域
};
typedef struct Node Node;

//初始化链表
Node *InitList(Node *head){//传入头节点
    head = (Node*)malloc(sizeof(Node)); //给头节点分配内存空间
    head -> next = NULL; //将指针域置为NULL，避免错误访问
    return head; //将分配好空间后的头节点返回
}

//求线性表长度 = 总空间大小/sizeof（Node） - 1
int Length(Node *head){
    if(head == NULL){
        printf("---线性表未创建---");
        return -1;
    }
    int count = 0; //计数变量count = 0
    Node *p = head -> next; //定义p指针指向第一个节点
    while(p != NULL){
        p = p -> next; //向前传递
        ++count; //计数
    }
    return count; //返回长度
}

//按位查找
DataType Get(Node *head, int i){
    Node *p = head -> next; //定义p指针指向第一个节点
    int count = 1;
    while(count < i && p != NULL){//开始计数，直到第i个节点跳出循环
        ++count;
        p = p -> next;
    }
    if(p == NULL){ //如果节点为空，返回信息，退出
        printf("访问错误\n");
        exit(0);
    }
    return p -> data; //返回节点数据域值
}

//按值查找
int Locate(Node *head, DataType x){
    Node *p = head -> next; //定义p指针指向第一个节点
    int count = 1; //从第一个节点开始计数
    while(p != NULL){
        if(p -> data == x) //如果找到了，返回节点位置
            return count;
        ++count;
        p = p -> next;
    }

    return 0; //未找到，返回0
}

//插入元素
void Insert(Node *head, int i, DataType x){
    Node *p = head; //p指向头节点，因为第一个节点要通过头节点来插入
    int count = 0;

    while(p != NULL && count < i - 1){
        p = p -> next;
        ++count;
    }
    //跳出循环时p指向第i - 1个节点

    if(p == NULL){ //如果第i-1个节点为空，则插入节点失败，返回
        printf("插入节点失败");
        exit(-1);
    }
    //插入第i个节点
    Node *s = (Node*)malloc(sizeof(Node));
    s -> data = x;
    s -> next = p -> next;
    p -> next = s;
}
//创建新节点
Node *Create_Node(DataType data){
    Node* np = (Node*)malloc(sizeof(Node));//为新节点开辟空间
    np->next = NULL;     //新节点指向NULL;
    np->data = data;
    return np; //返回新节点地址
}

//插入数据(头插法)
void Push_Head(Node *head, DataType data){
    Node *np = Create_Node(data); //创建一个新的节点
    np->next = head -> next;
    head->next = np;
}

//插入数据(尾插法)
void Push_Tail(Node *head, DataType data){
    Node* p = head;
    while (p -> next != NULL){//找到最后一个节点
        p = p -> next;
    }
    Node *np = Create_Node(data);
    p -> next = np; //插入元素
}

//建立单链表（尾插法）
Node *Creat(Node *head, DataType a[], int n){
    head = InitList(head);

    int i;
    for(i = 0 ; i < n ; ++i){ //循环插入元素
        Push_Tail(head, a[i]); //尾插
    }
    return head;
}

//删除节点
DataType Delete(Node *head, Node *s){
    Node* p = s; //把要删除的节点保存起来
    DataType x = p -> data;
    while(head -> next != s){
        head = head -> next;
    }
    head -> next = s -> next; //连接它的前节点与后节点
    free(p); //释放
    return x;
}

//按位删除节点
DataType Delete_L(Node *head, int i){
    Node *p = head;
    int len = Length(head);
    if(i > len){
        printf("删除失败");
        exit(-1);
    }
    int j;
    for(j = 1 ; j < i ; ++j){
        p = p -> next;
    }
    int x = Delete(head, p -> next); //这里只是为了用上Delete(),最好像注释那样写
    /*
    Node *q = p -> next;
    int x = q -> data; //存储被删除节点的数据
    p -> next = q -> next; //取出q节点
    free(q); //释放空间
    */
    return x; //返回被删除节点的数据
}


//摧毁线性表
Node *Destroy_List(Node *head){
    Node* p = head;
    while(p != NULL){//依次回收节点
        p = head -> next;
        free(head);
        head = p;
    }
    return NULL; //返回后许重新赋值给头节点
}

//Clear_List()
void Clear_List(Node *head){
    Destroy_List(head -> next);//摧毁除头节点以外其他节点
    head -> next = NULL; //给头节点指针域置空
}

int List_Empty(Node *head){
    return Length(head) > 0; //空 0 非空 1
}

DataType Get_Prev(Node *head, DataType x){
    int l = Locate(head, x) - 1; //获取前一个元素的序号
    if(l > 0)
        return Get(head,l);  //通过Get得到数据
    else{
        printf("当前元素已经是第一个元素");
        exit(-1);
    }
}

DataType Get_Next(Node *head, DataType x){
    int l = Locate(head, x) + 1; //获取后一个元素的序号
    if(l < Length(head))
        return Get(head,l);  //通过Get得到数据
    else{
        printf("当前元素已经是最后一个元素");
        exit(-1);
    }
}

void Traverse_Link(Node* head, void visit()){
    Node *p = head -> next;
    while(p != NULL){
        visit(p); //调用自定义功能函数
        p = p -> next;
    }
}

    附上顺序表链接：https://www.jianshu.com/p/cf7642e48a4e
    参考书籍：
    部分内容参考自
    数据结构（C语言版）
    数据结构与算法（C++版）

    相关文章

      网友评论

        本文标题：【C语言实现】链式存储结构线性表(链表)

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

        延伸阅读

        深度阅读

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

        栏目导航

        热点阅读

        实用干货

        关于我们|服务条款|联系我们|【C语言实现】链式存储结构线性表(链表)|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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