美文网首页
单链表

单链表

作者: 青辰m | 来源:发表于2018-06-02 12:42 被阅读0次

链式存储（内存块分成指针域和数据域）

一思路

定义常量：

typedef struct LNode
{
    ElemType data;//结点的数据域

    struct LNode *next;//结点的指针域

}LNode,*LinkList;//LNode结构体的名字，LinkList结构体的地址

初始化单链表:分配一个头结点

LNode *InitLinkList()
{
    LNode *head;//头结点的指针

    head=(LNode*)malloc(sizeof(LNode));

    if(head==NULL)  return NULL;//分配失败

    head->next=NULL;

    return head;

}

添加数据：分配一个结构体类型的结点，将上一位元素的指针指向结点

int InputLinkList(LNode *head,int n)
{

    LNode *p;
    LNode *s;//专门记录新生成结点的地址
    int i=1;

    p=head;//p指针指示链表的头部，以方便输入数据
    
    while(i<=n)
    {
        s=(LNode *)malloc(sizeof(LNode));
        
        if(s==NULL)  return -1;//地址分配不成功    
            scanf("%d",&s->data);
        s->next=NULL;
        p->next=s;
        p=p->next;
        i++;
    }
    return 1;
}

显示数据：定义一个指针指向头结点，再依次遍历。
结束条件p->next==NULL

void OutputLinkList(LNode *head)
{
    LNode *p;

    p=head->next;

    while(p!=NULL)
    {
        printf("%d ",p->data);

        p=p->next;
    }
}

插入数据：判断插入位置是否合法
定义一个指针（p）从头结点开始遍历，指向插入位置的前一个结点
插入结点（s）,s->next=p->next; p->next=s;

int InsertLinkList(LNode *head,int i,ElemType e)
{
    LNode *p;
    LNode *s;

    int j;//计数，记录带插入数据的前一个位置

    p=head;
    j=0;

    while(p!=NULL&&j<i-1)
    {
        p=p->next;

        j++;
    }
    //判断插入点的位置是否合法
    if(j>i-1||p==NULL)  return -1;

    s=(LNode*)malloc(sizeof(LNode));

    if(s==NULL)  return 0;//分配节点空间失败

    s->data=e;

    s->next=p->next;

    p->next=s;

    return 1;

}

删除数据：将前一个结点（p）指向后一个节点 p->next=p->next->next
注意：避免空间的浪费，先用一个变量储存待删除的结点，最后放空（free）

int DeleteLinkList(LNode *head,int i,ElemType *e)
{
    LNode *p;//指向待删除结点的前驱结点
    LNode *q;//指向待删除节点
    
    int j;

    p=head;
    
    j=0;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;

        j++;
    }
    //判断删除点的位置是否合法
    if(j>i-1||p==NULL) return -1;

    q=p->next;

    p->next=q->next;//or p->next=p->next->next;

    *e=q->data;

    free(q);
    return 1;
}

查找：依次遍历，比较数据域的数据（while(p!=NULL&&p->data!e)）

int LocateLinkList(LNode *head,ElemType e)
{
    int i=1;
    LNode *p;
    p=head;
    while(p!=NULL&&p->data!=e)
    {
        p=p->next;
        i++;
    }
    if(p==NULL) return -1;
    return i;
}

二：优缺点

        优点：
                  可使用零散的空间    不用分配空间 
        缺点：
                  删除和修改总是需要从头遍历。

整体代码：

/*
功能：单链表的操作：初始化、插入数据、删除数据等
开发者：冯筱静
版本：Version1.0
开发时间：2018-3-28 11:16
*/
#include <stdio.h>
#include<stdlib.h>

//定义单链表中操作的数据类型
typedef int ElemType;

//定义单链表中每一个结点的形式
typedef struct LNode
{
    ElemType data;//结点的数据域

    struct LNode *next;//结点的指针域

}LNode,*LinkList;

//初始化单链表

LNode *InitLinkList()
{
    LNode *head;//头结点的指针

    head=(LNode*)malloc(sizeof(LNode));

    if(head==NULL)  return NULL;//分配失败

    head->next=NULL;

    return head;

}

//向链表中添加n个数据

int InputLinkList(LNode *head,int n)
{

    LNode *p;
    LNode *s;//专门记录新生成结点的地址
    int i=1;

    p=head;//p指针指示链表的头部，以方便输入数据
    
    while(i<=n)
    {
        s=(LNode *)malloc(sizeof(LNode));
        
        if(s==NULL)  return -1;//地址分配不成功

        scanf("%d",&s->data);

        s->next=NULL;

        p->next=s;

        p=p->next;

        i++;
    }
    return 1;

}

//向链表中指定位置添加数据

int InsertLinkList(LNode *head,int i,ElemType e)
{
    LNode *p;
    LNode *s;

    int j;//计数，记录带插入数据的前一个位置

    p=head;
    j=0;

    while(p!=NULL&&j<i-1)
    {
        p=p->next;

        j++;
    }
    //判断插入点的位置是否合法
    if(j>i-1||p==NULL)  return -1;

    s=(LNode*)malloc(sizeof(LNode));

    if(s==NULL)  return 0;//分配节点空间失败

    s->data=e;

    s->next=p->next;

    p->next=s;

    return 1;

}

//显示链表中的数据
void OutputLinkList(LNode *head)
{
    LNode *p;

    p=head->next;

    while(p!=NULL)
    {
        printf("%d ",p->data);

        p=p->next;
    }
}

//删除数据（不能删除的：空链，删除位置不合法）

/*int DeleteLinkList(LNode *head,int i)
{
    LNode *p;
    LNode *q;
    int j;
    p=head;
    q=head;
    for(j=1;j<i;j++)
    {
        p=p->next;
    }
    q=p->next;
    p->next=q->next;
    return 1;
}*/
//删除链表中指定位置的数据元数，删除数由一个指针变量带回结果
int DeleteLinkList(LNode *head,int i,ElemType *e)
{
    LNode *p;//指向待删除结点的前驱结点
    LNode *q;//指向待删除节点
    
    int j;

    p=head;
    
    j=0;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;

        j++;
    }
    //判断删除点的位置是否合法
    if(j>i-1||p==NULL) return -1;

    q=p->next;

    p->next=q->next;//or p->next=p->next->next;

    *e=q->data;

    free(q);
    return 1;
}

//修改数据
int UpdateLinkList(LNode *head,int i,ElemType e)
{
    LNode *p;
    int j=0;
    p=head;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;

        j++;
    }
    //判断修改点的位置是否合法
    if(j>i-1||p==NULL) return -1;
    p=p->next;
    p->data=e;
    
    return 1;
}

//链表的查找
int LocateLinkList(LNode *head,ElemType e)
{
    int i=1;
    LNode *p;
    p=head;
    while(p!=NULL&&p->data!=e)
    {
        p=p->next;
        i++;
    }
    if(p==NULL) return -1;
    return i;
}

int main()
{
    LNode *head;

    int flag;

    int n,i,loc,a,b,c,d;

    ElemType e;

    head=InitLinkList();

    if(head==NULL)
    {
        printf("单链表初始化失败\n");
    }
    else
    {
        printf("单链表初始化成功\n");
    }
    printf("请输入要构建链表数据的个数:");

    scanf("%d",&n);

    printf("请输入要构建链表数据:");

    InputLinkList(head,n);

    printf("请输入需要插入的位置：");
    scanf("%d",&i);
    printf("请输入需要插入的数据：");
    scanf("%d",&loc);
    InsertLinkList(head,i,loc);
    OutputLinkList(head);

    printf("请输入需要删除的位置：");
    scanf("%d",&a);
    DeleteLinkList(head,a,&e);
    printf("\n删除的数据是：%d",e);

    printf("\n请输入需要修改的位置：");
    scanf("%d",&b);
    printf("请输入需要修改的数据：");
    scanf("%d",&c);
    UpdateLinkList(head,b,c);

    printf("请输入需要查找的数据:");
    scanf("%d",&e);
    d=LocateLinkList(head,e);
    printf("查找的元素位置是：%d",d);

    printf("\n当前链表中的数据为:");

    OutputLinkList(head);

    return 0;
}

头结点、头指针、首元结点的区别

头指针：指向链表第一个结点（或为头结点或为首元结点）的指针，单链表可由头指针唯一地确定。
头结点：在链表的第一个结点之前附设的一个结点，头结点的指针域指向表中的第一个结点。
首元结点：链表中存放第一个数据元素 a1的结点，在带头结点的链表中，它是头结点的下一个结点。

相关文章

  • 单链表 C++

    单链表 C++ 题目 1、创建单链表2、初始化单链表3、释放单链表4、获取单链表中元素的数量5、输出单链表中的所有...

  • 线性表：顺序表和链表

    顺序表（数组）优缺点 链表优点 单链表使用 单链表结构 单链表初始化 单链表初始化 单链表建立: 头插法 尾插法 ...

  • 单向链表算法

    单向链表 反转单向链表 单链表查找倒数第k个节点 单链表递归倒序打印 单链表排序 单链表删除重复节点

  • 链表基本操作

    1、删除单链表节点 2、插入单链表结点 单链表具体实现

  • 25_静态单链表的实现

    关键词： 单链表的一个缺点、静态单链表设计思路、静态单链表的继承层次结构、静态单链表的实现思路、静态单链表的实现 ...

  • 线性表的链式存储-单链表

    单链表操作 [x] 单链表的创建（尾插法、头插法） [x] 单链表的查找操作 [x] 单链表的删除操作 [x] 单...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下： 1.1 递归反转整个单链表...

  • 单链表反转

    单链表 单链表反转 递归方法

  • JavaScript数据结构2——单链表

    以下的代码包括了以下几部分 单链表初始化 单链表的插入 单链表的删除 单链表的创建（头插法） 单链表的创建（尾插法...

  • 链表

    链表：通过“指针”将零散的内存块联系起来。常见链表结构：单链表、循环链表和双链表。 单链表 对比数组学习单链表 循...

网友评论

      本文标题：单链表

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|单链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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