算法学习 | 数据结构（一）

引言

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

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

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

数组

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

我们可以看到这里我们用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两个指针域。

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