【数据结构】线性表

一元多项式的表示

  1. 一元多项式：

[f(x)=a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^n ]

  1. 运算：
    加、减、乘
  2. 分析：
    关键数据：项数、系数和指数
  3. 顺序存储结构直接表示
    eg:(f(x)=5x^2+1),a[]={1,0,0,0,0,5};
    进行运算很方便，但也有问题：比如(x+3x^{2000})
  4. 顺序存储结构表示非零项
    可以用结构数组表示
    运算也还方便（每一项有序存储）
  5. 链表结构存储非零项
typedef struct Polynode *Polynomial;//这种写法很好记，也很规整
struct Polynode{
    int coef;
    int expon;
    Polynomial link;
};
  1. 启示：
    （1）同一个问题可以有不同的表示方法
    （2）有一类共性问题：有序线性序列的组织和管理

线性表（Linear List）

  1. 定义
    由同类型数据元素构成的有序序列的线性结构
    长度
    空表
    表头、表尾
  2. ADT描述
类型名称：线性表
数据对象集：线性表是n个元素构成的有序序列($a_1,a_2,...,a_n$)
操作对象集：线性表$Lin List$，整数$i$表示位置，元素$X in ElementType$，线性表的基本操作有：
(1)List MakeEmpty()初始化一个空线性表L
(2)ElementType FindKth(int K,List L). 根据位序K，返回相应元素
(3)int Find(ElementType X,List L). 查找元素X第一次出现的位置
(4)void Insert(ElementType X,int i,List L) 在位序i前插入一个新元素X
(5)void Delete(int i,List L) 删除指定位序i的元素
(6)int Length(List L) 返回线性表L的长度n
  1. 线性表的顺序存储实现
    利用数组的连续存储空间顺序存放线性表的各元素
typedef struct LNode *List;
struct LNode{
    ElementType Data[MAXSIZE];
    int Last;
};
struct LNode L;//如果是结构体本身，访问结构体的成员用.运算符
List PtrL;//如果是指向结构体的指针，访问成员用->运算符

访问下标为i的元素：L.Data[i]或Ptrl->Data[i]
线性表的长度：L.Last+1或Ptrl->Last+1

(1). 初始化

List MakeEmpty(){
    List Ptrl;
    Ptrl = (List)malloc(sizeof(struct LNode));
    Ptrl->Last =-1;
    return Ptrl;
}

注：1. 结构体的指针是不能用的，需要malloc一下，否则其大小就是个指针大小（可能8个字节）简记为结构体的指针需要malloc()一下就好了 https://blog.csdn.net/lafengxiaoyu/article/details/53032963
2. 内存对齐 结构体所占总内存并非各成员内存的简单相加，有个对齐机制 https://blog.csdn.net/bailang_zhizun/article/details/83821370

（2）查找

int Find(ElementType X,List PtrL){
    int i=0;
    while(i<=PtrL->Last && PtrL->Data[i]!=X) //Last就是最后一个元素的下标，没有的时候就是-1呀，有一个的时候在0
        i++;
    if(i>PtrL->Last)    return -1;//如果没找到，返回-1
    else return i;
}

(3)插入

void Insert(ElementType X,int i,List PtrL){
    int j=0;
    if(PtrL->Last==MAXSIZE-1){     //检验表满或位置合法
    std::cout<<"表已满";
    return;
    }
    if(i<1||i>PtrL->Last+2){
    std::cout<<"位置不合法";
    return;
    }
    for(j=PtrL->last;j>=i-1;j++) PtrL->Data[j+1]=PtrL->Data[j];//要看清楚i指示的是第i个位置还是下标为i
    PtrL->Data[i-1]=X;
    PtrL->Last++;//不要忘记Last更新一下
    return;
}

(4)删除

void Delete(int i,List PtrL){
    if(PtrL->Last==-1){
        cout<<"空表";
        return;
    }
    if(i<1||i>PtrL->Last+1){
        cout<<"位置不合法";
        return;
    }
    int j;
    for(j=i-1;j<PtrL->Last){
        PtrL->Data[j]=PtrL->Data[j+1];
    }
    PtrL->Last--;
    return;
}
  1. 线性表的链式存储实现
    不要求逻辑上相邻的两个元素物理上也相邻
typedef struct LNode *List;
struct Lnode{
    ElementType Data;
    List Next;
};
struct Lnode L;
List PtrL;

(1)求表长

int Length(List PtrL){
    List p=PtrL;
    int j=0;
    while(p){
        p=p->Next;
        j++;    
    }
    return j;
}

(2)查找
查找第K个

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;
}

查找某个元素

List Find(ElementType X, List PtrL){
    List p=PtrL;
    while(p!=NULL&&p->Data!=X){
        p=p->Next;
    }
    if(p->Data==X) return p;
    else return NULL;
}

（3）插入
先构造一个新节点，s指向；再找到链表的第i-1个节点，用p指向；修改指针，插入节点

void Insert(ElementType X, int i,List PtrL){
    List s,p=PtrL;
    if(i==1){//插入为第一个的时候，更换了表头，所以需要特殊处理一下。因为表头的地址就是该链表的地址
        s=(List)malloc(sizeof(struct LNode));
        s->Data=X;
        s->Next=PtrL;
        return s;
    }
    p=FindKth(i-1,PtrL);//利用寻找第K个元素的函数，找到第i-1个节点的地址
    if(p==NULL){
        cout<<"参数错误";
        return NULL;
    }
    else{
        s=(List)malloc(sizeof(struct LNode));
        s->Data=X;
        s->Next=p->Next;
        p->Next=s;
        return PtrL;
    }
}

（4）删除
先找到第i-1个节点，用p指向；用指针s指向要被删除的节点；修改指针，删除s所指的结点；释放s所指的节点

void Delete(int i,List PtrL){
    List s,p;
    if(i==1){//删除头节点。两种可能，一种是链表本身就是空的，删除不成功。另一种是链表本身不是空
        s=PtrL;
        if(PtrL!=NULL) PtrL=PtrL->Next;
        else return NULL;
        free(s);
        return PtrL;
    }
    p=FindKth(i-1,PtrL);
    if(p==NULL){//这个情况经常漏写
        cout<<"不存在";
        return NULL;
    }
    else{
        s=p->Next;
        p->Next=s->Next;
        free(s);
        return PtrL;
    }
   
}

广义表

  1. 问题：二元多项式怎么表示？
    分析：将二元多项式看成关于x的一元多项式

[P(x,y)=(9y^2+4)x^{12}+(15y^3-y)x^8+3x^2 ]

“复杂”链表
2. 广义表(Generalized List)
广义表是线性表的推广
对于线性表而言,n个元素都是基本的单元素
广义表中，这些元素不仅可以是单元素也可以是另一个广义表

typedef struct GNode *GList;
struct GNode{
    int Tag;
    union{
    ElementType Data;
    Glist Sublist;
    }URegion;
    GList Next;
};
  1. 多重链表
    链表中的节点同时隶属于多个链
    多重链表中节点的指针域会有多个，如前面例子包含了next和Sublist两个指针域
    但包含两个指针域的链表并不一定是多重链表，比如双向链表，不是多重链表

多重链表有广泛的用途，基本上如树、图这样相对复杂的数据结构都可以采用多重链表的方式存储。

  1. 矩阵的十字链表表示
    矩阵可以用二维数组表示，但数组表示有两个缺陷：（1）大小需要事先确定（2）对于稀疏矩阵将造成大量空间浪费

分析：
采用十字链表来存储稀疏矩阵
只存储矩阵非0元素项 数据域：行坐标、纵坐标、数值
每个结点通过两个指针域，把同行、同列串起来：行指针 列指针

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/maxwell-maxwill/p/12308012.html