logo资料库

【灰灰考研】算法必背100题.pdf

发布时间：2022-06-06 发布人：admin 分类：说明书 资料大小：6.44M 资料格式：pdf 举报 版权申诉
第1页 / 共133页
第2页 / 共133页
第3页 / 共133页
第4页 / 共133页
第5页 / 共133页
第6页 / 共133页
第7页 / 共133页
第8页 / 共133页
资料共133页，剩余部分请下载后查看
    【灰灰考研】算法必背 100 题 灰灰考研 2021 年计算机考研 算法必背 100 题 灰灰考研 顺序表、栈、队列 ................................................................................................................... 2 KMP ......................................................................................................................................... 44 树 ............................................................................................................................................. 47 图 ............................................................................................................................................. 78 查找、排序、其他算法 ......................................................................................................... 87 408 精选算法题 .................................................................................................................... 100 皮皮灰精选算法百题 1
    【灰灰考研】算法必背 100 题 顺序表、栈、队列 1. 顺序表的插入元素操作 引入：如果我们要实现 ListInsert(SeqList *L, int i, ElemType e)，即在顺序表 L 中的第 i 个 位置插入新元素 e，应该如何操作？ 1. 如果插入位置不合理，结束程序，输出异常信息 2. 如果线性表长度大于或者等于数组长度，结束程序，输出异常信息 3. 从顺序表的最后一个元素开始向前遍历到第 i 个位置，依次将其向后移动一个位置。 4. 将元素插入指定位置 i 处 5. 表长增加 1 下面在第三个存储位置插入元素作为例子，其中 new 为要插入的新元素。 //初始条件：顺序线性表 L 已存在，1 ≤ i ≤ ListLength(L） //操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 int ListInsert(SeqList *L,int i,ElemType *e){ int k； if(L->length==MAXSIZE)/*顺序线性表已经满*/ return ERROR; if（i<1 || i>L->length+1)/*当 i 不在范围内时*/return ERROR; if(i<=L->1ength){/*若插入数据位置不在表尾*/ for(k=L->length-1；k>=i-1；k--)/*将要插入位置后的数据元素向后移动 一位*/ L->data[k+1]=L->data[k]; } L->data[i-1]=e;/*将新元素插入*/ L->length++; return OK; } 灰灰点评： 在上述代码中，核心语句为 for 循环里面的判断，对顺序表进行插入操作，应该先进 行位置移动，然后才能进行插入操作。所以顺序线性表的插入，时间复杂度为 O(n)。 2
    【灰灰考研】算法必背 100 题 2. 顺序表的删除元素操作 假如你要从一个顺序线性表删除某个元素，实现 ListDelete(SqList *L,int i,ElemType *e)， 即在 L 中的第 i 个位置删除一个元素 e，应该如何操作呢？ 首先整理算法思路： 1. 如果删除的元素位置不正确，结束程序，输出异常信息 2. 取出删除元素，放在元素 e 中 3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置 4. 表长减去 1 图 2-8 删除前 图 2-9 删除后 //初始条件：顺序线性表 L 已存在，1 ≤ i ≤ List.Length(L) //操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 int ListDelete(SqList *L,int i,ElemType *e){ int k; if (L->length==0)/*线性表为空*/ return ERROR; if(i<1|| i>L->length)/*删除位置不正确*/ return ERROR; *e=L->data[i-1]; if(i1ength){/*如果删除不是最后位置*/ for（k=i；klength;k++)/*将删除位置后继元素前移*/ L->data[k-1]=L->data[k]; } L->length--； return OK; } 灰灰点评： 该删除算法关键步骤是：从删除元素位置开始遍历到最后一个元素位置，分别依次将它 们向前移动一个位置，然后对第 i 个元素进行删除。因为在进行删除之前还需要一次跟插入 一样的移动操作，故删除的平均算法时间也为 O(n)。 3
    【灰灰考研】算法必背 100 题 3.单链表获取某个元素 算法思路： 1. 声明一个节点 p 指向链表的第一个节点，初始化 j 作为计数器，从 1 开始 2. 当 jnext; while(p && jnext； /*p 指向下一个节点*/ ++j; } if(!p || j > i) return ERROR; *e = p->data; return OK;} 灰灰点评：该算法核心是遍历链表，在遍历中搜寻指定的元素，算法虽然简单，但是如果出 现在代码题中当中切记要写上容错机制。 4
    【灰灰考研】算法必背 100 题 4.单链表插入元素 在任意位置插入一个节点 s，数据域值为 e 的节点，要如何实现呢？ 图 2-11 如何插入节点 答案： s->next = p->next; //第一步 p->next = s; //第二步 首先将 p 的后继节点 p->next 修改为 s 的后继节点，然后将节点 s 修改 p 的后继节点。 注意：顺序不能颠倒，如果颠倒了 p->next=s;s->next=p->next，这种情况下由于先断开了 p 与 p->next 之间的关系，进而导致了 s->next 找不到后继节点。 插入过程如图 2-12 所示： 图 2-12 链表插入图 单链表第 i 个数据插入节点的算法思想： 1. 声明一个节点 p 指向链表的第一个节点，初始化 j 作为计数器从 1 开始。 2. 当 jdata。 6. 单链表插入：s->next = p->next; p->next = s;。 7. 返回成功，算法结束。 5
    【灰灰考研】算法必背 100 题 具体代码如下： //初始条件：顺序线性表已存在，1 ≤ i ≤ ListLength（L） //操作结果：顺序表的在第 i 处插入新元素 e int ListInsert(LinkList *L,int i,ElemType e) { int j=1； LinkList p,s; p=*L； while (p && jnext; ++j； } if (!p || j>i) return ERROR; /*第 i 个元素不存在*/ s=(LinkList *) malloc (sizeof(Node))；/*生成新节点（C 标准函数）*/ s->data=e; s->next=p->next；/*将 p 的后继节点赋值给 s 的后继*） p->next=s;/*将 s 赋值给 p 的后继*/ return OK; } 6
    【灰灰考研】算法必背 100 题 5.双链表的插入操作 我们现在要实现存储元素为 e，节点为 s 插入到节点 p 与节点 p->next 中，如图所示 图 2-13 双链表插入图 //如图① s->prior = p; s->next = p->next; //如图② p->next->prior = s; //如图③ p->next = s; //如图④ 插入步骤关键在于他们插入的顺序，假设第 4 步先执行，则 p->next 提前变成了 s，由 于在第 2 步与第 3 步之间都用到了 p->next，最终插入失败。 6.双链表的删除操作 如果理解了插入操作，那么删除操作就比较简单了。以双链表为例，如下图删除节点 p 流程图所示，如果要删除节点 p，则需要如下步骤： 图 2-14 双链表删除节点 p->prior->next = p->next; //如图① p->next->prior = p->prior; //如图② free(p) //释放空间，不要漏掉 7
    【灰灰考研】算法必背 100 题 7.逆置 方法一：头插法 算法思想：修改指针即可，head 指针遍历链表不断向前移动，用 p 记录 head 的之前的 一个节点，修改各个节点指针域 next，指向 p，用一个 temp 指针指向（保存）head 的 下一个节点。 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    安全技术

    共收录1285份资料，累计4个分类，关注成员有19位，主要包括：网络攻防,系统安全,其它,网络安全

    热门标签

    网络攻防 系统安全 其它 网络安全

    最新资料