CS-Note

第二章-线性表

WanXing2022年7月28日大约 6 分钟

2.1 线性表的定义和基本操作

1. 线性表的定义

  • 定义

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

  • 特点

    1. 表中元素个数有限
    2. 表中元素具有逻辑上的顺序性，表中元素有其先后次序
    3. 表中元素都是数据元素，每个元素都是单个元素
    4. 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
    5. 表中元素具有抽象性(逻辑关系)

  • 注-有点像函数

函数：一个 x 值只能对应一个 y 值 线性表：一个索引值只能有一个映射值

2.线性表的基本操作

2.2 线性表的顺序表示

1. 顺序表的定义 Sequence List

  • 线性表的顺序存储 -> 顺序表

  • 顺序表的特点是表中元素的逻辑顺序与其物理顺序相同

  • 顺序表的结构类型定义

    • 静态分配
    • 动态分配
    • C 的初始动态分配语句
    • L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize;
    • C++的初始动态分配语句
    • L.data = new ElemType[InitSize];

2.顺序表上基本操作的实现

  • 1.插入操作
    • 最好情况：表尾插入，时间复杂度为O(1)O(1)
    • 最坏情况：表头插入，时间复杂度为O(n)O(n)
    • 平均情况：Eins=1n+1∑i=1n+1(n−i+1)=1n+1(n+⋯+1+0)=n2E_{ins} = \frac 1{n+1} \sum^{n+1}_{i=1}(n-i+1) = \frac 1{n+1}(n+\cdots + 1 + 0) = \frac n2 ，时间复杂度为O(n)O(n)

exp

// 插入操作代码 后移赋值
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1 )          // i值不合法
        return false;
    else if (L.length >= MAXSIZE)            // 当前存储空间已满
        return false;
    for (int j = L.length ; j >= i ; j--)
        L.elem[j] = L.elem[j - 1];           // 插入位置及之后位置后移
    L.elem[i - 1] = e;                       // 将新元素放入第i个位置
    L.length++;                              //表长增加1
    return true;
}
  • 2.删除操作
    • 最好情况：删除表尾元素，时间复杂度为O(1)O(1)
    • 最坏情况：删除表头元素，时间复杂度为O(n)O(n)
    • 平均情况：Edel=1n∑i=1n(n−i)=1n(n−1)n2=n−12E_{del} = \frac 1n \sum^n_{i=1}(n-i)=\frac 1n \frac {(n-1)n}2 = \frac{n-1}2 ，时间复杂度为O(n)O(n)
// 删除操作代码 赋值前移
bool ListDelete(SqList& L, int i, ElemType e) {
    if (i < 1 || i > L.length)             // 判断i值是否合理
        return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++)
        L.elem[j - 1] = L.elem[j];
    L.length--;
    return true;
}
  • 3.按值查找（顺序查找）
    • 最好情况：查找的元素就在表头，时间复杂度为O(1)O(1)
    • 最坏情况：查找的元素在表尾（或不存在），时间复杂度为O(n)O(n)
    • 平均情况：Efind=1n∑i=1ni=n+12E_{find} = \frac 1n \sum^n_{i=1}i= \frac{n+1}2 ，时间复杂度为O(n)O(n)
// 按值查找（顺序查找）代码
int LocateElem(SqList &L, ElemType e){
    int i;
    for(i = 0; i < L.length; i++){
      if(L.data[i] == e)
        return i+1;   //返回的是位序
    }
    return 0;
}
  • 4.按位查找
    • 时间复杂度为O(1)O(1)

2.3 线性表的链式表示

1.单链表的定义

  • 线性表的链式存储又称单链表

  • 结点的类型定义

typedef struct LNode{     // 声明结点的类型和指向结点的指针类型
  ElemType data;        //结点的数据域
  struct LNode *next;   // 结点的指针域
}LNode,*LinkList;         // LinkList为指向结构体LNode的指针类型

注 : 实际上，这一部分代码实际上等价于

typedef struct LNode LNode; //将结构体重命名为LNode`
typedef struct LNode *LinkList; //将结构体指针重命名为LinkList

LNode是一个具象的结构体类型，指向的是包含某个数据类型的数据域和指针域的结构体类型。

而LinkList是LNode的指针类型，它占用一定内存空间，内存空间中的值是一个LNode类型结构体的地址。相比LNode，它显得有些“虚无缥缈”。

  • 通常用头指针来表示一个单链表，头结点是带头结点链表中第一个结点

2.单链表上基本操作的实现

  • 1.采用头插法建立单链表

    • 时间复杂度O(n)O(n)
// 带头结点
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);
  }
}

  • 2.采用尾插法建立单链表

    • 时间复杂度O(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;    //r指向新表尾结点
    scanf("%d",&x);
  }
  r->next = NULL;   //表尾结点置空
  return L;
}

头插尾插（带头不带头）open in new window

单链表操作open in new window

  • 3.按序号查找结点值

    • 时间复杂度O(n)O(n)
LNode *GetElem(LinkList L,int i){
  int j = 1;
  LNode* p = L->next;   //第一个结点赋值给p
  if(i == 0) return L;    // 若i等于0，则返回头结点
  if(i < 1) return NULL;    // 若i无效，则返回头结点
  while(p && j < i){
    p = p->next;
    j++;
  }
  e = p->data;
  return p;   //返回第 i 个结点的指针或 NULL
}

  • 4.按值查找表结点

    • 时间复杂度O(n)O(n)
LNode *LocateElem(LinkList L,ElemType e){
  LNode* p = L->next;
    while(p && p->data != e){
      p = p->next;
    }
    return p;   //找到返回指针，找不到返回 NULL
}

  • 5.插入结点操作

    • 时间复杂度O(n)O(n) ，开销主要在查找第i-1个元素
// 前插 s插到p 之前
// s为待插入结点指针 

p = GetElem(L,i-1);   //查找插入位置前驱
s->next = p->next;
p-next = s;
    • 时间复杂度O(1)O(1)
// 后插 s插到p 之后
// s为待插入结点指针 

s->next = p->next;
p->next = s;    //前插
temp = p->data;
p->data = s->data;
s->data = temp;   //交换s、p数据域
  • 6.删除结点操作
    • 时间复杂度O(n)O(n)
//找前驱
p = GetElem(L,i-1);   //找到前驱
q = p->next;    //q指向被删结点
p->next = q->next;    //断开q
free(q);
    • 时间复杂度O(1)O(1)
// 删除p后继
q = p-next;   //q指向*p后继
p->data = p->next->data;    //和后继交换数据域
p->next = q->next;    //*q结点断开
free(q);    //释放存储空间
  • 7.求表长操作

求表长

3.双链表

  • 1.结点类型定义
typedef struct DuLNode{
  Elemtype data;
  struct DuLNode *prior,*next;
}DuLNode, *DuLinkList;

  • a.双链表的插入操作

    • 时间复杂度O(n)O(n)
// 在p后插入结点，s为待插入结点
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;

  • b.双链表的删除操作

    • 时间复杂度O(n)O(n)
//删除 p 之后的结点 q
p->next = q->next;
q->next->prior = p;
free(q);

  • 2.循环链表

    • 循环单链表：尾指针指向头结点
    • 循环双链表：头结点prior指向表尾结点

  • 3.静态链表

    • 结点类型定义
#define MaxSize 100
typydef struct{
	ElemType data;
	int next;
}SlinkList[MaxSize];

静态链表以 next == -1作为结束标志

  • 4.顺序表和链表的比较

    • 存储（读写）方式：顺序表可以随机也可以顺序，链表只能从头存取
    • 逻辑结构与物理结构：顺序存储相邻，链式不一定
    • 查找、插入和删除操作：按值、按序号
    • 空间分配
    • 在实际应用中应该怎样选取存储结构呢？
      • 基于存储的考虑
      • 基于运算的考虑
      • 基于环境的考虑

    表长可预估，经常查、搜 -->顺序表

    经常增、删 -->链表

Loading...
Wish you a better day
Copyright © 2022 WanXing