数据结构之线性表(顺序表、单链表、双链表)(三)-阿里云开发者社区

开发者社区> pqo7bvdsfj67q> 正文

数据结构之线性表(顺序表、单链表、双链表)(三)

简介: 数据结构之线性表(顺序表、单链表、双链表)
+关注继续查看



单链表的插入过程


【说明】:


1、要在带头结点的单链表第i(0≤i≤size)个结点前插入一个存放数据元素x的结点,首先要在单链表中寻找到第i-1个结点并由指针p指示,然后动态申请一个结点存储空间并由指针q指示,并把数据元素x的值赋予新结点的数据元素域(即q->data=x),最后修改新结点的指针域指向ai结点(即q->next=p->next),并修改ai-1结点的指针域使之指向新结点q(即p->next= q)。插入过程如上图所示。


2、循环条件由两个子条件逻辑与组成,其中子条件p->next != NULL保证指针所指结点存在,子条件j<i-1保证最终让指针p指向ai-1结点。


代码实现:


int ListInsert(SLNode *head,int i,DataType x)
{
   //在带头结点的单链表head的第i(0<=i<=size)个结点前
    //插入一个存放数据元素x的结点。插入成功则返回1,失败则返回0
    SLNode *p,*q;
    int j;
    p=head;
    j=-1;
    while(p->next!=NULL&&j<i-1)
    //最终让指针p指向第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(j!=i-1)
    {
        printf("插入元素位置参数错!");
        return 0;
    }
   
    //生成新结点,并赋值
    q=(SLNode *)malloc(sizeof(SLNode));
    q->data=x;
    //插入步骤
    q->next=p->next;
    p->next=q;
    return 1;
}


单链表的删除ListDelete


【说明】:


1、要在带头结点的单链表中删除第i(0≤i≤size-1)个结点,首先要在单链表中寻找到第i-1个结点并由指针p指示,然后让指针s指向ai结点(即s=p->next),并把数据元素a i的值赋予x(即*x=s->data),最后把ai结点脱链(即p->next=p->next->next),并动态释放ai结点的存储空间,即free(s)。删除过程如上图所示。


2、循环条件由三个子条件逻辑与组成,其中子条件p->next!=NULL保证ai-1结点存在,子条件p->next->next!=NULL保证ai结点存在,子条件j<i-1保证最终让指针p指向ai-1结点。与插入函数相比,删除函数的循环条件多了子条件p->next->next!=NULL。这是因为删除函数要删除ai结点,若没有子条件p->next->next!=NULL保证ai结点存在,则当ai结点不存在时,动态释放语句free(s)将因指针s为空而出错。


注意:在循环条件中,前两个子条件的次序不能颠倒,否则在ai-1结点不存在时,会因指针p->next->next不存在而出错


代码实现:


int ListDelete(SLNode *head,int i,DataType *x)
{
    SLNode *p,*s;
    int j;
    p=head;
    j=-1;
    while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)
        //循环结束时指针p指向第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(j!=i-1)
    {
        printf("删除元素位置参数错!");
        return 0;
    }
    s=p->next;
    *x=s->data;            
    p->next=p->next->next;//删除
    free(s);        //释放指针s所指向结点的内存空间
    return 1;
}


单链表取数据元素


取数据元素函数和删除函数基本类同,主要差别是,取数据元素函数的循环条件改为j<i,并且不删除ai结点。


代码实现:


int ListGet(SLNode *head,int i,DataType *x)
{
    SLNode *p;
    int j;
    p=head;
    j=-1;
    while(p->next!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    if(j!=i)
    {
        printf("取元素位置出错!");
        return 0;
    }
    *x=p->data;
    return 1;
}


撤销单链表


单链表的结点空间是在程序运行时动态申请的,而系统只负责自动回收程序中静态分配的内存空间,所以,和顺序表相比,单链表要增加一个撤销单链表操作,释放动态申请的内存空间。


代码实现:


void Destroy(SLNode **head)
{
    SLNode *p,*p1;
    p=*head;
    while(p!=NULL)
    {
        p1=p;
        p=p->next;
        free(p1);
    }
    *head=NULL;
}

单链表实例


1、编程实现建立一个线性表,首先依次输入数据元素1, 2, 3,…,10,然后删除数据元素5,最后依次显示当前表中的数据元素。要求使用单链表。


代码如下:


include <stdio.h>      //包含printf()函数
#include <stdlib.h>     //包含exit()函数
#include <malloc.h>     //包含malloc()等函数
//2020.05。04  微信公众号:C语言与CPP编程
typedef int DataType;   //定义DataType为int
#include "LinList.h"    //包含单链表文件
int main(int argc, char* argv[])
{
    SLNode *head;   //定义头指针变量
    int i,x;
    ListInitiate(&head);    //初始化
    for(i = 0;i < 10; i++)      //插入10个数据元素
    {
        if(ListInsert(head,i,i+1) == 0)
        {
            printf("错误!\n");
            return ;
        }
    }
    for(i = 0;i < ListLength(head); i++)    //显示当前的数据元素中的值
    {
        if(ListGet(head,i,&x) == 0) //取元素值到x变量中
        {
            printf("错误!\n");
            return ;
        }
        else
        {
            printf("%d ",x);    //显示
        }
    }
    printf("\n");
    if(ListDelete(head,4,&x) == 0)  //删除下标为四(值为5)的数据元素
    {
        printf("错误!\n");
        return ;
    }
    for(i = 0;i < ListLength(head); i++)    //显示当前的数据元素中的值
    {
        if(ListGet(head,i,&x) == 0) //取元素值到x变量中
        {
            printf("错误!\n");
            return ;
        }
        else
        {
            printf("%d ",x);    //显示
        }
    }
    printf("\n");
    Destroy(&head);     //撤消单链表
    return 0;
}

2、设头指针为head,并设带头结点单链表中的数据元素递增有序,编写算法将数据 元素x插入到带头结点单链表的适当位置上,要求插入后保持单链表数据元素的递增有序。


算法思路:从链表的第1个数据元素结点开始,逐个比较每个结点的data域值和x的值,当data小于等于x时,进行下一个结点的比较;否则,就找到了插入结点的合适位置,此时申请新结点把x存入,然后把新结点插入;当比较到最后一个结点仍有data小于等于x时,则把新结点插入单链表尾。


代码如下:


void LinListInsert(SLNode*head,DataType x)
{
    SLNode*curr,*pre,*q;
    //循环初始化
    curr = head->next;      //curr指向第一个数据元素结点
    pre = head;             //pre指向头结点
    //循环定位插入位置
    while(curr != NULL && curr->data <= x)
    {
        pre = curr;
        curr = curr->next;
    }
    //申请一个结点并把x存入data域
    if((q = (SLNode*)malloc(sizeof(SLNode))) == NULL) exit(1);
    q->data = x;
    //把新结点插入pre所指结点后
    q->next = pre->next;
    pre->next = q;
}

3、设head为单链表的头指针,并设单链表带有头结点,编写算法将单链表中的数据元素按照其值递增有序的顺序进行就地排序。


代码如下:


void LinListSort(SLNode *head)
{
    SLNode*curr,*pre,*p,*q;
    p = head->next;
    head->next = NULL;
    while(p != NULL)
    {
        curr = head->next;
        pre = head;
        while(curr != NULL && curr->data <= p->data)
        {
            pre = curr;
            curr = curr->next;
        }
        q = p;
        p = p->next;
        q->next = pre->next;
        pre->next = q;
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
一文快速搞定Redis_数据类型及JavaApi操作
大家好,我是**ChinaManor**,直译过来就是中国码农的意思,我希望自己能成为国家复兴道路的铺路人,大数据领域的耕耘者,平凡但不甘于平庸的人。
7 0
15 年老兵谈阿里云大规模机器学习实践
  近年来,机器学习技术的发展归因于我们有极其庞大的数据用来训练算法。当企业需要落地大规模机器学习时,往往会面临很多难题,如何解决这些问题?如何系统了解大规模机器学习落地的技巧?其适用场景是什么?InfoQ 希望通过该选题解决这些问题,并推动企业在大规模机器学习方面的实践。本文,InfoQ 有幸采访了阿里云机器学习研究员林伟,听他分享自己的经验和见解。
6 0
与数据隐私相关的 AI 关键问题
  本文最初发表在 Towards Data Science 博客,经原作者 Alexandros Zenonos 授权,InfoQ 中文站翻译并分享。   隐私不仅是与人工智能有关的问题,也是任何与数据相关的领域普遍关注的问题。隐私是关于人们对其个人数据和基于这些数据所做的决定的控制。
6 0
如果你有拖延症,程序员不如试试这个技巧提升效率?
  要吃掉一头大象,每次吃一口。   ——克雷顿·艾布拉姆斯(Creighton Abrams)   造成拖延的首要原因之一,同时也是造成生产力低下的祸根,就是总是在感慨一个问题:好忙啊,问题好大啊……实际上,你并没有真正试着去解决问题。当我们从任务的全貌来审视任务的时候,它们看起来比真实情况都要大,并且更吓人。   在本文中,我会谈及一个能够帮助你克服拖延的提高生产力的窍门:分解任务。通过将大任务分解为小任务,你会发现自己更有动力去完成它们,也更加稳妥地向着目标前进。
9 0
偏序关系
偏序 关系 离散数学
6 0
PG+MySQL第9课-实时精准营销
通常业务场景会涉及基于标签条件圈选目标客户、基于用户特征值扩选相似人群、群体用户画像分析这些技术,本文将围绕这三个场景去介绍在实施精准营销里面的PG数据库的使用
6 0
程序员真的是吃青春饭吗?如何面对传说中的 35 岁职业焦虑?
  正走在这条路上的你或许也曾想过这些问题。这一次,力扣邀请到了《高效制胜——程序员面试典型题解》作者吴江(迈克老师),分享他 35 岁跳槽,并拿到了技术负责人 Offer,实现收入增长的故事和面试准备经验。   — 01 —   “35 岁危机”真有那么可怕吗?   在 2018 年快过春节的时候,我们部门突然被通知要开一个会,会上通知我们部门要在明年的这个时候被整体裁掉。我在这家五百强外企已经待了五年,当时虽然有这个预感,但是真的听到正式通知时,不免还是感觉有点震惊。
5 0
阿里巴巴数据库分库分表的实践(6)
阿里巴巴数据库分库分表的实践(6)
9 0
IT运维人员,把握现在展望未来
  近年来,互联网在中国的发展势头迅猛并呈现出广阔前景。根据中国互联网络信息中心报告显示,截至2020年3月,我国网民规模已经达到9.04亿,互联网普及率增至67.0%,超全球平均水平。   互联网强劲发展的背后是整个IT行业的蓬勃。国家统计局发布的2019平均工资数据表明,工资最高的行业是信息传输、软件和信息技术服务业,IT行业从业人员平均年薪已超16万元。
8 0
Keras之父写给年轻程序员的33条忠告
  代码是一种交流方式,Keras 之父 Fran?ois Chollet 在本文中为我们总结了在开发过程中、API 设计中及软件职业生涯中应该关注哪些要点。原则是形式化的直觉,比原始模式识别适用于更广泛的情况,Fran?ois Chollet 的这份原则清单将带你领略大师的品味。
9 0
123
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载