算法学习 | 数据结构(一)-阿里云开发者社区

开发者社区> 梨好橙> 正文

算法学习 | 数据结构(一)

简介: 线性表是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。
+关注继续查看

引言

思考:如果我们需要用程序来表示一个多项式,如

$$ y = 3x^4+2x^2+1 $$

我们可以使用哪些东西呢?

数组

我们可以用一个数组a[i]来存储这个多项式

i 0 1 2 3 4
a[i] 1 0 2 0 3

我们可以看到这里我们用i来表示幂次,用a[i]来表示方程的系数。

但是这里有一个问题,如果我们要表示的式子是

$$ y = 5x^2+x^9 $$

我们需要一个分量为9的数组来存储这个多项式,我们仅仅用到了其中的两位。

链表

每个节点存储多项式中的一个非零项

typedef struct P *p;
typedef sturct P{
    int coef;
    int expon;
    p link;
}

链表上每个元素含有指数和系数两个值,在使用链表之后我们存储上面的多项式只需要两个分量。

什么是线性表?

线性表是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。

顺序存储

在顺序存储中元素在逻辑上和物理上都是相连的

主要操作

1.创建一个空表

List *MakeEmpty(){
    List *PtrL;
    //为PtrL申请空间
    PtrL=(List *)malloc(sizeof(List));
    PtrL->Last=-1;
    return Ptrl;
};

2.查找

int Find(ElementType X,List *PtrL){
    int i=0;
    while(i<=PtrL->Last&&PtrL->Data[i]!=X)
        i++;
    if(i>PtrL->Last) //当到最后一个都没有找到,返回-1
        return -1; 
    else return i;   //否则返回存储位置i
}

3.插入

在第i个位置插入一个值为X的元素

void Insert(ElementType X,int i,List *PtrL){
    int j;
    //判断表有没有满
    if(PtrL->Last==MAXSIZE-1){
        printf("表满");
        return 0;
    }
    //判断插入位置是否合法
    if(i<1||i>PtrL->Last+2){
        printf("位置不合法");
        return 0;
    }
    for(j=PtrL->Last;j>=i-1;j--){
        PtrL->Data[j+1]=PtrL->Data[j];
        }
    PtrL->Data[i-1]=X;
    PtrL->Last++;
    return;
    
}

4.删除

void Delete (int i,List *PtrL){
    int j;
    //检查元素位置是否合法
    if(i<1||Ptrl->Last+1){
        printf("不存在第%d个元素",i);
        return;
    }
    //把删除掉的元素之后的元素往前移动
    for(j=1;j<=PtrL->Last;j++){
        PrtL->Data[j-1]=PtrL->Data[j];
        }
    PtrL->Last--;
    return;
}

链式存储

元素在逻辑上相连,在物理上不一定相连

typedef struct Node{
    ElementType Data; //该元素存储的数据
    struct Node *Next;//表示下一个元素地址
}List;

List L,*Ptrl;

主要操作

1.求表长(遍历)

int Length(List *PtrL){
    List *p=PtrL;
    int j=0;
    //while循环遍历整个链表,每遍历一次j++
    while(p){
        p=p->Next;
        j++;
    }
    return j;
}

时间复杂度O(n)

2.查找

List *FindKth(int K,List *PtrL){
    List *p=PtrL;
    int i=1;
    //
    while(p!=NULL&&i<K){
        p=p->Next;
        i++;
    }
    if(i==K)return p;
    
    else return NULL;
}

3.插入

(1)先构造一个新结点

(2)找到第i-1个结点

(3)修改指针,插入结点

List *Insert(ElementType X,int i,List *PtrL){
    List *p,*s;
    //如果要插在头上
    if(i==1){
        s=(List*)malloc(sizeof(List));
        s->Data=X;
        s->Next=PtrL;
        return s;
    }
    //找i结点的位置
    p=FindKth(i-1,PtrL);
    if(p==NULL){
        printf("参数i错误");
        return NULL;
    }else{
        s=(List*)malloc(sizeof(List));
        s->Data=X;
        s->Next=p->Next;
        p->Next=s;
        return PtrL;
    }
} 

4.删除

(1)先找到链表的第i-1个结点

(2)再用指针s指向要删除的结点

(3)然后修改指针,删除s结点

(4)释放s所指结点的空间

List *Delete(int i,List *PtrL){
    List *p,*s;
    //若要删除第一个结点
    if(i==1){
        s=PtrL;
        if(PtrL!=NULL) PtrL=PtrL->Next;
        else return NULL;
        free(s);
        return PtrL;
    }
    //找i结点位置
    p=FindKth(i-1,PtrL);
    if(p==NULL){
        printf("第%d个结点不存在",i-1);
        return NULL;
    }else if(p->Next==NULL){
        printf("第%d个结点不存在",i);
        return NULL;
    }else{
        s=p->Next;
        p->Next=s->Next;
        free(s);
        return PtrL;
    }
}

广义表

广义表是线性表的推广,在广义表中,这些元素不仅是单元素也可以是另外一个广义表

typedef struct GNode{
    int Tag;  //标志域:0是单元素,1是广义表
    union{    //Data与SubList共用存储空间
        ElementType Data;
        struct GNode *SubList;
    }URegion;
    sturct GNode *Next;
}GList;

多重链表中结点的指针域会有多个,上面的程序中包含了Data和SubList两个指针域。

多重链表有广泛的用途,后面的树和图这样的数据结构都可以使用多重链表实现存储,我们将在后面和他有更深的接触!

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

相关文章
Impala 如何高效查询 OSS 数据 | 学习笔记
快速学习 Impala 如何高效查询 OSS 数据。
23 0
CCAI 2017 | 小数据学习对人工智能究竟有着怎样的影响?
中国人工智能大会(CCAI),由中国人工智能学会发起,目前已成功举办两届,是中国国内级别最高、规模最大的人工智能大会。秉承前两届大会宗旨,由中国人工智能学会、阿里巴巴集团 & 蚂蚁金服主办,CSDN、中国科学院自动化研究所承办,云栖社区作为独家直播合作伙伴的第三届中国人工智能大会(CCAI 2017)将于 7 月 22-23 日在杭州召开。
6233 0
GO学习笔记 - 数据校验
基于asaskevich/govalidator实现Golang数据校验
602 0
mongodb数据结构学习1--增删改查
插入文档 在数据库中,数据插入是最基本的操作,在MongoDB使用db.collection.insert(document)语句来插入文档; document是文档数据,collection是存放文档数据的集合。
837 0
【NIPS2017现场+数据也疯狂】最佳论文大奖公布,算法关注度超越深度学习排第一
第三十一届NIPS正式开幕!新智元编辑部结合“V直播”,为你带来现场报道!本届会议有8500人注册,3240篇提交论文,覆盖156个子领域,有7844位不同的作者,2093位专家评审,9747条评审意见……辉煌的数字,必将成就难忘的会议。本文后附3篇最佳论文及1篇经典论文解读。
3013 0
《Web安全之机器学习入门》一 1.5 算法和数据的辩证关系
本节书摘来自华章出版社《Web安全之机器学习入门》一 书中的第1章,第1.5节,作者:刘焱,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1003 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
12035 0
Spark学习之数据读取与保存(4)
Spark学习之数据读取与保存(4) 1. 文件格式 Spark对很多种文件格式的读取和保存方式都很简单。 如文本文件的非结构化的文件,如JSON的半结构化文件,如SequenceFile结构化文件。通过扩展名进行处理。 2. 读取/保存文本文件 Python中读取一个文本文件 input = sc.textfile("file:///hom
1326 0
【玩转数据系列八】机器学习算法的离线调度实现-广告CTR预测
整套实验使用了阿里云机器学习进行数据挖掘工作,通过大数据开发套件进行调度和推送。具体的业务场景是:通过历史数据在阿里云机器学习平台上面训练模型,通过大数据开发进行调度,每天凌晨对于每天的广告投放CTR预测,甄选出符合标准的广告推送出去。
9389 0
数据结构学习笔记——最大子列和问题
PTA 中国大学MOOC-陈越、何钦铭-数据结构 01-复杂度1 最大子列和问题(20 分) 给定K个整数组成的序列{ N​1​​ , N​2​​ , ..., N​k},“连续子列”被定义为{ N​i , N​i+1​​ , ..., N​j},其中 1≤i≤j≤K。
1024 0
+关注
梨好橙
4年前:计科小白 现在:计科老白
10
文章
467
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载