callmepicacho/data-structres

浙江大学《数据结构》上课笔记 + 数据结构实现 + 课后题题解

Data-Structres

我的博客 ：叫我皮卡丘

前言

**大学MOOC上浙大的《数据结构》广受好评，原因有二，一是基础，简单易懂，老师讲得也清楚，另一大优点就是配套的每周相应知识点的编程题了，有难有易，容易题帮助巩固知识点，难题开阔视野。

笔记加入了一些自己的想法，题解也有思路说明

课程地址：https://www.icourse163.org/course/ZJU-93001

现将笔记和题解记录如下

基本概念

基本概念

题目名称	考察知识点	难易度
最大子列和问题	时间复杂度、算法优化	简单
Maximum Subsequence Sum	时间复杂度	中等
二分查找	二分查找算法	简单

线性结构

线性表

堆栈

队列

题目名称	考察知识点	难易度
两个有序链表序列的合并	线性表	简单
一元多项式的乘法与加法运算	线性表	中等
Reversing Linked List	线性表	中等
Pop Sequence	栈	中等

树

树的定义

二叉树的遍历

二叉搜索树

平衡二叉树

堆

哈夫曼树

并查集的实现和优化

题目名称	考察知识点	难易度
树的同构	树的性质	简单
List Leaves	树的建立与遍历	简单
Tree Traversals Again	树的遍历	中等
是否同一棵二叉搜索树	BST的建立与遍历	简单
Root of AVL Tree	AVL的调整	简单
Complete Binary Search Tree	BST的花样(?)建立	中等
二叉搜索树的操作集	BST的操作集合	简单
堆中的路径	最小堆的建立	简单
File Transfer	并查集	中等
Huffman Codes	哈夫曼树编码	中等

图

图的定义

图的遍历

最短路径

最小生成树

题目名称	考察知识点	难易度
列出连通集	图的遍历	简单
Saving James Bond - Easy Version	图的遍历	简单
六度空间	图的遍历	中等
哈利·波特的考试	最短路径	简单
旅游规划	最短路径	简单
公路村村通	最小生成树	简单

排序

排序

题目名称	考察知识点	难易度
排序	用来测试排序算法	简单
Insert or Merge	插入排序、归并排序	简单
Insertion or Heap Sort	插入排序、堆排序	简单
统计工龄	桶排序	简单
PAT Judge	结构体排序	中等
Sort with Swap(0, i)	表排序	简单

散列查找

散列查找

题目名称	考察知识点	难易度
电话聊天狂人	散列查找	简单
Hashing	散列查找	简单
QQ帐户的申请与登陆	散列查找	简单
Hashing - Hard Version	散列查找、拓扑排序	中等

KMP

题目名称	考察知识点	难易度
KMP 串的模式匹配	串的匹配	中等

注：Saving James Bond - Hard Version 和 关键活动 实在没时间做了...

完结撒花，弱弱求个 star~

data-structres's Issues

关于数组存储的线性表的删除

void Delete(int i,List L){
    int j;
    if(i < 0 || L->Last <i){  //位置越界，而删除最多到 L->Data[L->Last]
        printf("L->Data[%d]不存在元素",i);
        return;
    }
    for(j=i;j<=L->Last;j++)   // 从前往后依次向前挪一个，将 a[i] 覆盖了 
        L->Data[j-1] = L->Data[j];
    L->Last--;  // Last仍然指向最后元素
    return;
}

你这 传入的 i 是 下表，所以

for(j=i;j<=L->Last;j++)   // 从前往后依次向前挪一个，将 a[i] 覆盖了 
        L->Data[j-1] = L->Data[j];

应该改成

for(j=i+1;j<=L->Last;j++)   // 从前往后依次向前挪一个，将 a[i] 覆盖了 
        L->Data[j-1] = L->Data[j];

呃～题目的英文好像不太对 应该是 Data-Structures

循环队列

循环队列一直添加元素，理论上队满了，但是没有提示队满。

你好，发现一个Bug，7-1 Maximum Subsequence Sum

7-1 Maximum Subsequence Sum这道题的代码在OJ有一组数据过不了，题目要求的是如果全为负数，则输出0，你的代码是只要最大和小于0则输出0。
还有就算我有个疑问，当最大和前面有一串0的时候，我感觉你这个程序也会出错，但是OJ在判这组数据的时候你的代码是对的，而我选择条件是<=时清零，但在这组数据却会出错。我不太理解，倘若你有时间可否交流一下这个问题

您好，发现一个bug。

上课Demo 2.数组存储的线性表.c中的ElementType FindKth(int K,List L)第三行return;应为return -1；