0%

  1. 线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列。

  2. 特点:

    1. a₁是唯一的“第一个”数据元素,又称“表头元素”
    2. an是唯一的“最后一个”数据元素,又称“表尾元素”
    3. 除a₁外每个元素有且仅有一个直接前驱;
    4. 除an外每个元素有且仅有一个直接后继
  3. 定义:“数组+长度”

    1
    2
    3
    4
    5
    #define MaxSize=50
    typedef struct{    
    ElemType data{MaxSize};
    int length;
    }Sqlist;//静态分配
    1
    2
    3
    4
    5
    6
    #define InitSize 100
    L.data=(ElemType*)Malloc sizeof(ElemType)*InitSize;
    typedef struct{
    ElemType *data;
    int MaxSize,length;
    }SeqList;//动态分配
  4. 链表的基本操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    InitList(&L)//初始化表
    Length(L)//求表长
    LocateElem(L,e)//按值查找
    GetElem(L,i)//按位查找
    ListInsert(&L,i,e)//按位插入
    ListDelete(&L,i,&e)//按位删除
    PrintList(L)//遍历并打印
    Empty(L)//判定表不空
    PriorElem(L,e,&Prior)NextElem(L,e,&next)//求前驱、后继
    DestoryList(&L)//销毁链表
  5. 在第i处插入新元素e

    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool ListInsert(Sqlist &L,int i,ElemType e){
    if(L. length>=MaxSize||i<1||i>L. length+1)
    return false;
    for(int j=L. length;j>=i;j--)//将i个元素后移
    L. data[j]=L. data[j-1];
    L. data[i-1]=e;
    L. length++;
    return true;
    }//最好O(1),最坏O(n),平均O(n)
  6. 删除第i个位置的元素,将该元素用e返回

    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool ListDelete(Sqlist &L,int i,int &e){
    if(i>L. length||i<1)
    return flase;
    e=L. data[i-1];
    for(int j=i;j<length;j++)//将i后元素前移
    L. data[j-1]=L. data[j];
    L. length--;
    return true;
    }//最好O(1),最坏O(n),平均O(n)
  7. 单链表:线性表的链式存储。

  8. 对链表的结点,除了存放元素自身,还要存放指向后继的指针。单链表结点

  9. 类型定义:“数据+指针”

    1
    2
    3
    4
    typedef struct LNode{
    ElemType data;//数据域
    Struct LNode *next;//指针域
    }LNode,*Linklist;
  10. 访问、遍历数据

    1
    2
    3
    4
    5
    6
    7
    void VisitLinklist(Linklist){
    P=L->next;
    while(p!=NULL){
    visit(P->data);//主体,可换做其他,如,print(P->data);
    P=P->next;
    }
    }
  11. 头插法建立单链表

    头插法建立单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Linklist CreatList(Linklist &L){
    LNode *S,int x;
    L=(Linklist)malloc(sizeof(LNode));//头结点
    L->next-NULL;//空表
    scanf("%d",&x);
    for(i=0;i<9999;i++){
    S=(LNode*)malloc(sizeof(LNode));
    S->data=x;S->next=L->next;L->next=S;
    scanf("%d",&x);
    }
    return L;
    }//读入数据顺序与生成链表中元素顺序相反,O(n)
  12. 尾插法建立单链表

    尾插法建立单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Linklist CreatList(Linklist &L){
    int x;
    L=(Linklist)malloc(sizeof(LNode));//头结点
    LNode *S,*r=L;//r为表尾指针
    Scanf("%d",&x);
    for(i=0;i<9999;i++){
    S=(LNode*)malloc(sizeof(LNode));
    S->data=x;r->next=S;r=S;
    scanf("%d",&x);
    }
    r->next=NULL;
    return L;
    }//得到的顺序与原顺序相同
  13. 按序号查找结点值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    LNode *GetElem(Linklist L,int i){
    int j=1;LNode *P=L-next;
    if(i==0) return L;
    if(i<1) return NULL;
    while(P&&j<i){
    P=P->next;
    j++;
    }
    return P;
    }//O(n)
  14. 按值查找:查找给定值e

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    LNode *GetElem(Linklist L,int i){
        int j=1;LNode *P=L-next;
        if(i==0) return L;
        if(i<1) return NULL;
        while(P&&j<i){
            P=P->next;
            j++;
        }
        return P;
    }//O(n)
  15. 插入结点

    单链表插入结点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool ListInsert(Linklist &L,int i,ElemType x){
    P=L;j=0;
    while(P&&j<i-1){
    P=P->next;j++;
    }
    if(P&&j==i-1){
    S=(Linklist)malloc(sizeof(LNode));
    S->data=x;S>next=P->next;P>next=S;
    return ture;
    }
    else return flase;
    }//O(n),若给定结点后插入O(n)
  16. 删除结点

    单链表删除结点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool ListDelete(Linklist &L,int &x){
    P=L;j=0;
    while(P&&j<i-1){
    P=P->next;j++;
    }
    if(P&&j==i-1&&P-next){
    S=P->next;P-next=S->next;x=S-next;
    free(S);
    return true;
    }
    else return flase;
    }//O(n)
  17. 双链表:定义

    双链表结点

    1
    2
    3
    4
    typedef struct DNode{
    ElemType data;
    Struct DNode *Prior,*next;
    }DNode,*DLinklist;
  18. 静态链表:定义

    静态链表

    1
    2
    3
    4
    5
    #define MaxSize 50
    typedef struct{
    ElemType data;
    int next;
    }SLinkList[MaxSize]//用数组存储,以next=-1作结束标志
  19. 顺序存储的特点是利用物理上相邻表达元素之间的关系,
    链式存储是通过指针表示元素之间的关系。

  1. 算法具备:可执行性、确定性、有穷性(输入、输出)。

  2. 数据项是构成数据元素的最小单位。

  3. 数据结构:逻辑结构、存储结构、数据的运算。

  4. 逻辑结构:集合、线性结构、树型结构、图或网状结构。

  5. 线性结构:线性表、栈与队列、串、数组。

  6. 存储结构:顺序存储、链接存储,索引存储、散列存储(如,hash)。

  7. 逻辑结构指数据的组织形式数据间的逻辑关系。

  8. 数据结构是一门研究在非数值计算的程序设计问题中计算机的操作对象及对象间的关系和施加于对象的操作等学科。

  9. 数据类型是一个值的集合和一组定义在此集合上的操作的总称。

  10. 抽象数据类型(ADT)是指一个数学模型以及定义在该模型上妹子操作。 其定义仅取决于它的一组逻辑特定,与其在计算机内部如何表示和实现无关系,不论内部结构如何变化,只要其数学特性不变,都不影响其外部的使用。

  11. 相同与区别:二者实质上是一个概念。 抽象数据类型的范围更广,它已不在局限于机器已定义和实现的数据类型,还包括用户在设计软件时自行定义的数据类型。

  12. 使用抽象数据类型的好处:使用抽象数据类型定义的软件、模块含定义、表示与实现三个部分,封装在一起对用户透明(提供接口),而不必了解实现细节。其使程序设计不再是“艺术”,而是像“科学”迈进了一步。

  13. 数据的逻辑结构与存储结构无关。运算定义在逻辑结构上依赖于存储结构实现。

  14. 逻辑结构相同,但存储结构不同。如,线性表:顺序表、线性链表。

  15. 逻辑结构不同,但存储结构相同。如,栈与队列。

  16. 数据结构的评价很复杂

    1. 所选数据是否正确、完整地刻画了问题基本特征;

    2. 是否容易实现。

  17. 算法评价:正确性、易读性、健壮性、时空效率(运行)。

  18. 算法的时间复杂性:算法输入规模的函数。 算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目,且与此数目有关的其他参数。有时考虑算法最坏情况下的时间复杂度或平均时间复杂度。

  19. 算法:对特定问题求解步骤的描述,是指令的有限序列,其中每一条指令表示一个或多个操作。

  20. 频度:该语句在算法中重复执行的次数 $O(1)<O(\log_2n)<O(n)<O(n\log_2n)<O(n^2)<O(n^2)<O(2^n)<O(n!)<O(n^n)$

很早就萌生了想就《金刚经》写一些什么,但一直拖着(若是早能写出,以为契机再读金刚经,也许也不会发生后面这么多事)。这篇文章心乱时写不出来,心静时写不出来,心烦时更是写不出来。这一年多来,发生了很多事,寥寥数笔,几经删改。总算勉强通畅。但留下这几笔粗糙,以为此刻此心印证。

1. 希腊字母简表

希腊字母名称,读音,大小写等。

心灵鸡汤