考研笔记 | 数据结构 §2.线性表

  • 英语:

  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. 顺序存储的特点是利用物理上相邻表达元素之间的关系,
    链式存储是通过指针表示元素之间的关系。

-------文章到此结束  感谢您的阅读-------