从零开始数据结构的生活(二)

线性表

一、什么线性表

​ 线性表就是具有<font color="red">相同的数据类型</font>的n(n≥0)个元素的有限序列,除了表头和表尾都具有唯一的前驱和后继。

1.特点

 - 个数有限
 - 逻辑上拥有顺序性,表中元素有先后顺序
 - 都是数据元素
 - 数据类型相同  

2.基本操作

  • InitList(&L): 初始化表。构建一个空的线性表
  • Length(L): 求表长。
  • LocateElem(L, e):按值查找元素,e为要查找的值
  • getElem(L,i):按位查找操作。获取表L的第i个位置的元素的值
  • ListInsert(&L, i, e): 插入操作
  • ListDelete(&L, i, &e):删除操作
  • PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值
  • Empty(L):判空操作
  • DestoryList(&L):销毁操作

二、顺序表

1. 定义

​ 以地址连续的存储单元依次存储线性表中的数据元素称为顺序表

2. 特点

  • 随机访问,通过首元素和元素序号可以O(1)内找到指定元素
  • 存储密度高,每个节点只存储数据元素
  • 逻辑上和物理上元素都相邻,所以插入和删除操作需要移动大量的元素

四、链表

1. 定义

​ 以链式存储的线性表称为单链表,除了表结点外还要有一个指向t后继的指针

typeof struct LNode{    //定义单链表结点类型
    ElemTyppe data;     //数据域
    struct LNode *next; //指针域
}LNode, *LinkList;
带头结点的指针

优点

  • 首结点的操作和其他操作一致,比如删除,插入等
  • 空和非空链表不用特殊处理,不是这样如果空要进行空间释放

2. 单链表的实现

  • 采用头插法建立单链表

LinkList List_HeadInsert(LinkList &L) {
    LNode *s; int x;
    L = (LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next = NULL; //初始化空链表
    scanf("%d", &x); //输入结点的值
    while(x!=9999){ //输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode)); //创建新节点
        s->data = x;
        s->next = L->next; //图中操作①
        L->next = s; //图中操作②
        scanf("%d", &x);
    }
    return L;
}

使用头插法输入的元素是顺序相反的,你最早输入的在最后,最晚输入的最前面。每个结点插入的时间复杂度是O(1),设链表长为n,则总时间复杂度为O(n)。

  • 采用尾插法建立单链表

LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L; //r为表尾指针
    scanf("%d", &x);  //输入结点的值
    while(x!=9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d", &x);
    }
    r->next=NULL;
    return L;
}
  • 按序号查找结点值

    LNode *GetElem(LinkList L, int i) {
        int j = 1; // 计数初始值为1
        LNode *p = L->next; //头结点指针赋给p
        if(i==0)
            return L; //若i等于0,则返回头结点
        if(i<1)
            return NULL; //若i无效,则返回NULL
        while(p&&j<i) {
            p=p->next;
            j++;
        }
        return p; //返回第i个结点的指针,若i大于表长返回NULL
    }
  • 按值查找结点值

    Lnode *LocateElem(LinkList L,ElemType e){
        LNode *p = L->next;
        while(p!=NULL&&p->data!=e) 
            p=p->next;
        return p;
    }
  • 插入结点操作

    void insertElem(LinkList &L, int i, LNode s){
        LNode *p = getElem(L, i-1);
        s->next=p->next;
        p=>next=s;
    }
  • 删除结点操作

    void deleteElem(LinkList &L,int i){
        LNode *p = getElem(L, i);
        LNode *q = p->next;
        p->next = q->next;
        free(q);
    }
  • 求表长操作

    int lenLinkList(LinkList L){
        int n = 0;
        LNode *p = L->next;
        while(p!=NULL){
            p = p->next;
            n++;
        }
        return n;
    }

3. 双链表

typedef struct DNode{
    ElemType data; //数据域
    struct DNode *prior, *next; //前驱和后继指针
}DNode, *DLinkList;
DNode getElem(int i, DLinkList L){
    int j = 1; //计数
    DNode *p = L->next;
    if(i==0)
        return L;
    if(i<0)
        return NULL;
    while(p!=NULL && j<i) {
        p = p->next;
    }
    return p;
}
//插入操作
void insertDLinkList(DLinkList &L, int i,LNode s) {
    DNode *p = getElem(i-1,L);
    s->next = p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}
//删除操作
void deleteDNode(DLinkList &L,int i) {
    DNode *p = getElem(i, L);
    DNode *q = p->next;
    p->next = q->next;
    q->next =->prior=p;
    free(q); //释放空间结点
}

五、顺序表和链表的区别

  • 读写方式

    • 顺序表可以顺序读取也可以随机读取
    • 链表只能顺序读取
  • 逻辑结构和物理结构

    • 顺序表逻辑结构上相邻,物理结构上也相邻连续
    • 链表逻辑结构上相邻,但物理结构上分散
  • 查找、插入和删除操作

    • 顺序表

      • 按值查找有序时使用折半查找为O(logn),无序时为O(n)
      • 按序号查找为O(1)
      • 插入、删除均为O(n)
    • 链表

      • 按值和按序号均为O(n)
      • 插入和删除均为O(1)
  • 空间分配

    • 顺序表:连续的一部分空间,会造成外部碎片,需要预分配,可能会溢出
    • 链表:不连续的空间,利用空间充分
最后修改:2020 年 08 月 10 日
如果觉得我的文章对你有用,请随意赞赏