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

开发者社区> 人工智能> 正文

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

简介: 线性表是数据结构的一种,一个线性表是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两个指针域。

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

版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章