数据结构和算法笔记

o_O’’

算法的复杂度

推导大 O 表示法方法

1. 用常数 1 取代云心时间中的所有加法常数
2. 修改后的运行次数函数中,只保留最高项
3. 如果最高项存在且不是 1, 则去除与这个项相乘的常数

线性表

由零个或多个元素组成的有限序列

ADT

Data

Operation

InitList(*l) 初始化操作, 建立一个空的线性表 L

ListEmpty(L) 判断是否为空,<空: true,非空: false>

ClearList(*l) 清空线性表

GetElem(L, i, *e): 返回第 i 个元素给 e

LocateElem(L,e) 查找与给定值 e 相等的元素, < 存在: 返回 index, 不存在: 0>

ListInsert(*L,i,e) 第 i 个位置插入元素 e

ListDelete(*L,i,*e) 删除 L 中第 i 个元素, 返回 e 的 index

ListLength(L) 返回 l 的长度

endAdt

数组

插入操作

插入位置不合理, 抛出异常

长度大于表长度,则抛出异常或动态增加容量

从最后一个元素开始向前便利到第 i 个位置, 分别将它们向后移动一个位置

将要插入的元素放入位置 i 处

表长度 +1

删除操作

删除 index 不合理, 抛出异常

取出删除元素

从删除元素位置, 遍历到最后一个元素位置, 分别将它们向前移动一个位置

表长 -1

链表

头指针

指链表指向第一个头节点的指针, 若链表有头节点,则是指向头节点的指针

头指针具有表示作用, 所以常用头指针冠以链表的名字(指针变量的名字)

无论链表是否为空,头指针均不为空

头指针是链表的必要元素

头节点

头节点是为了操作的统一和方便而设立的, 放在第一个元素的节点之前, 其数据域一般无意义(可以用来存放链表的长度)

有了头节点,对在第一个元素节点前插入节点和删除节点和其它节点的操作就统一了

读取

获取链表地i个数据

声明一个节点 p 指向链表的第一个节点, 初始化 j 从 1 开始

当j>j时, 遍历链表, p的指针向后移动

当链表末尾指针为空, 说明第i个元素不存在

若查找成功,返回节点p的数据

Status GetElem(LinkList L, int i, ElemType *e)
{
    int j;
    LinkList p;

    p = L->next;
    j = 1;

    while (p && j < i)
    {
        p = p->next;
        ++j;
    }

    if (!p || j > i)
    {
        return 0;
    }
    *e = p->data;
    return 1;
}

插入