Code Monkey home page Code Monkey logo

data-structure's Introduction

《数据结构》课本源码与习题解析

项目介绍

本项目中的源码与教材《数据结构-C语言版》[严蔚敏,吴伟民版]以及《数据结构题集-C语言版》[严蔚敏,吴伟民,米宁版]配套。

数据结构教材 数据结构题集
数据结构教材 数据结构题集

项目结构

本项目包含了教材源码习题源码,并分为4个版本,分别是:CFreeDev-C++CLionVisualC++,其中:

  • CFree 版本是早期上传的完整版本,该版本在CFree这个IDE下测试通过。此版本虽有瑕疵,但不会再实时维护,因为新的更新会在下面三个分支版本中呈现。
  • Dev-C++ 版本是指在Dev-C++这个IDE下测试通过的版本。
  • CLion 版本是指在CLion这个IDE下测试通过的版本。
  • VisualC++ 版本是指在Microsoft Visual C++ 2010这个IDE下测试通过的版本。

IDE的选择

CFree是一个优秀的国产软件,麻雀虽小五脏俱全,非常适合新手使用。不过该产品早已停更,在win10上有些兼容问题,需要调教。

Dev-C++是一个开源软件,同CFree一样小巧实用。最关键的是,可以兼容win10,推荐使用。

CLion需要掌握一点cmake知识,对笔记本性能要求也略高。不过JetBrains系列的产品,功能优秀没得说,强烈建议尝试。

Microsoft Visual C++是微软出品,该系列号称地表最强,不过复杂度也是很高,对于新手并不友好,需要耐心琢磨。如果将来不是走C/C++/C#等路线,可以先不使用。(注:从2018年开始,计算机二级C语言项目的考试中,已将VC++6换成了Microsoft Visual C++ 2010。所以如果有考级需求的同学,请自行熟悉该IDE)

习题解析中存储了《数据结构题集》中非代码题的解析,对于需要写代码解决的问题,参见 Dev-C++CLionVisualC++ 这三个版本中的源码。

注:
1. "CFree"是完整版本。"Dev-C++"/"CLion"/"VisualC++"是新增的版本,这三个版本最终会取代"CFree"版本。    
2. "CFree"版本既可以用CFree直接打开,也支持用Dev-C++打开,所以当使用CFree遇到兼容问题时,可尝试用Dev-C++。    
3. 上述四个版的代码是同步更新的,但是各版本之间相互独立,没有任何依赖关系,允许单独运行/测试。    
4. 对所有版本的代码均未充分测试,尤其是很多代码没有完成的边界检查(原因是此处以实现算法正确性为目的,而较少考虑程序的健壮性),所以如有BUG请到Issues反馈。    

更新目标

总的目标是保障正确性,提高可读性,降低学习难度,具体来说包含以下几点:

  1. ★★★项目工程化。
  2. 修复一些已知/潜在的BUG。
  3. 简化源码之间的引用关系,争取每个模块都可以单独运行测试。
  4. 修剪被引用源码中的次要内容,使得焦点更聚集,重点更突出。
  5. 增加注释与帮助信息,使源码展示更友好。
  6. 出自教材中的算法,会尽量使其代码与教材一致,如有改动,会在注释中提示。其它算法会视情形书写,不唯一。
  7. 修改部分被引入的结构,这一点需要视不同题目的要求而定;大多数被引入的结构会原封不动地保留下来。

使用方式

  • 开箱即用

将源码克隆/下载到本地后,可以查看各分支内的 README 文件以获取帮助信息

注意事项

  1. 本内容仅限个人学习使用,未经作者许可,不得用于商业用途
  2. 源码仅供参考,别抄作业
  3. 欢迎Star项目,并鼓励在Github提交Issues来反馈问题,在博客上发私信未必可以及时看到
    github

Commit图例

序号 emoji 在本项目中的含义 简写标记
(0) 🎉 初始化项目 :tada:
(1) 📝 更新文档,包括但不限于README :memo:
(2) 💡 发布新的源码 :bulb:
(3) ♻️ 重构,主要指修改已有的源码与注释 :recycle:
(4) ✏️ 校对,主要指更正错别字、修改源码排版、更新注释等 :pencil2:
(5) 🐛 修复代码中的BUG :bug:

相关链接

个人博客

脚注

Commit信息中的emoji参考来源:

附:教材源码目录

内容 包含算法 备注
01 绪论 Status 定义一些共享常量和函数
02 线性表 SqList 顺序表 2.3、2.4、2.5、2.6 线性表的顺序存储结构
Union A=A∪B 2.1
MergeSqList C=A+B 2.2、2.7 归并顺序表
LinkList 链表 2.8、2.9、2.10、2.11 线性表的链式存储结构
MergeList C=A+B 2.12 归并链表
SLinkList 静态链表 2.13、2.14、2.15、2.16
Difference (A-B)∪(B-A) 2.17
DuLinkList 双向循环链表 2.18、2.19
ELinkList 扩展的线性链表 2.20
MergeEList C=A+B 2.21 归并扩展的线性链表
Polynomial 一元多项式 2.22、2.23
03 栈和队列 SqStack 顺序存储结构
Conversion 进制转换 3.1 栈的应用
LineEdit 行编辑程序 3.2 栈的应用
Maze 迷宫寻路 3.3 栈的应用
Expression 表达式求值 3.4 栈的应用
Hanoi 汉诺塔 3.5 递归
LinkQueue 链列 链式存储结构
SqQueue 顺序队列 循环队列,顺序存储结构
BankQueuing 模拟银行排队 3.6、3.7 队列的应用
04 串 SString 顺序串 4.1、4.2、4.3、4.5 顺序存储
HString 堆串 4.4 顺序存储,动态分配内存
LString 块链串 顺序存储+链式存储
KMP KMP算法 4.6、4.7、4.8 字符串匹配算法
WordList 关键词索引 4.9、4.10、4.11、4.12、4.13、4.14 堆串和线性表的应用
05 数组和广义表 Array 多维数组
TSMatrix 稀疏矩阵 5.1、5.2 三元组顺序表存储方式
RLSMatrix 稀疏矩阵 5.3 行逻辑链接的顺序表存储方式
CrossList 稀疏矩阵 5.4 十字链表存储方式
GList-HT 广义表 5.5、5.6、5.7、5.8 头尾链表存储表示
GList-E 广义表 扩展线性链表存储表示
MPList m元多项式 链式存储
06 树和二叉树 SqBiTree 二叉树顺序存储结构
BiTree 二叉树的二叉链表存储结构 6.1、6.2、6.3、6.4
BiTriTree 二叉树的三叉链表存储结构
BiThrTree 线索二叉树 6.5、6.6、6.7
PTree 树的双亲表存储表示
CTree 树的孩子链表(带双亲)的存储表示
CSTree 树的二叉链表(孩子-兄弟)结构存储表示
MFSet 集合 6.8、6.9、6.10、6.11
HuffmanTree 赫夫曼树 6.12、6.13 又称"哈夫曼树"
PowerSet 冪集 6.14/6.15
NQueens N皇后问题 6.16
07 图 MGraph 图的邻接矩阵存储 7.1、7.2、7.4、7.5、7.6 有向图、有向网、无向图、无向网
ALGraph 图的邻接表存储 有向图、有向网、无向图、无向网
OLGraph 图的十字链表存储 7.3 有向图、有向网、无向图、无向网
AMLGraph 图的邻接多重表存储 无向图、无向网
SpanningTree 无向图的生成树 7.7、7.8 深度优先生成树
StronglyConnectedComponents 有向图强连通分量 Kosaraju算法和Tarjan算法
MinimumSpanningTree 无向网的最小生成树 7.9 Prim算法和Kruskal算法
ArticulationPoints 无向图的关节点 7.10、7.11
TopologicalSorting AOV-网的拓扑排序 7.12 有向图
CriticalPathMethod AOE-网的关键路径 7.13、7.14 有向网
ShortestPaths 最短路径算法 7.15、7.16 Dijkstra算法和Floyd算法
08 动态存储管理 BoundaryTagMethod 边界标识法 8.1
BuddySystem 伙伴系统 8.2
GarbageCollection 无用单元收集 8.3 无栈遍历广义表

data-structure's People

Contributors

kangjianwei avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

data-structure's Issues

VisualC++/CourseBook/0209_ELinkList

/*
 * 向尾部添加
 *
 * 将s所指的一串结点链接在链表L后面
 */
Status Append(ELinkList* L, Link s) {
    int count;
    
    if(L == NULL || (*L).head == NULL || s == NULL) {
        return ERROR;
    }
    
    count = 0;
    (*L).tail->next = s;
    
    // 确定新的尾结点位置
    while(s != NULL) {
        (*L).tail = s;
        s = s->next;
        count++;
    }
    
    (*L).len += count;
    
    return OK;
}

循环体中的内容可能有点问题,append操作,应该是将链表“s”链接到“L”上, (*L).tail = s;单单改变了尾结点并没有链接,循环体是不是改为

while(s != NULL) {
        (*L).tail->next = s;
        (*L).tail = s;
        s = s->next;
        count ++;
    }

HeapString.c#L248 Bug

It seems that there is a bug in this line in the StrDelete_H function:

for(i=pos-1; i+len<=(*S).length; i++)
    (*S).ch[i] = (*S).ch[i+len];

We can see that the max value of (i + len) is (*S).length, that means in the for loop:
(*S).ch[i+len] will be (*S).ch[(*S).length].
However, the last element in the String S is S.ch[(*S).length-1].

So the correct code should be:

for(i=pos-1; i+len<(*S).length; i++)
    (*S).ch[i] = (*S).ch[i+len];

ListDelete问题

https://github.com/kangjianwei/Data-Structure/blob/master/CLion/CourseBook/0204_LinkList/LinkList.c
line327

/*
 * ████████ 算法2.10 ████████
 *
 * 删除
 *
 * 删除链表第i个位置上的元素,并将被删除元素存储到e中。
 * 删除成功则返回OK,否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置,从1开始计数
 */
Status ListDelete(LinkList L, int i, ElemType* e) {
    LinkList p, q;
    int j;
    
    // 确保链表存在且不为空表
    if(L == NULL || L->next == NULL) {
        return ERROR;
    }
    
    p = L;
    j = 0;
    
    // 寻找第i-1个结点,且保证该结点的后继不为NULL
    while(p->next != NULL && j < i - 1) {
        p = p->next;
        ++j;
    }
    
    // 如果遍历到头了,或者i的值不合规(比如i<=0),说明没找到合乎目标的结点
    if(p->next == NULL || j > i - 1) {
        return ERROR;
    }
    
    // 删除第i个结点
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    
    return OK;
}

寻找第i-1个位置不就是第i个节点吗?
// 删除第i个结点
q = p->next;
为啥还要在 p->next

Visual C++ 2019 配置静态库不成功?

按照图示配置了静态库,但是好像没成功,我对Visual的使用并不熟悉,并且尝试解决问题失败。
错误:
`已启动生成…
1>------ 已启动生成: 项目: 0604_BiThrTree, 配置: Debug Win32 ------
1>BiThrTree.c

1>C:\Users\22318\Desktop\Data-Structure-master\VisualC++\CourseBook\0604_BiThrTree\BiThrTree.c(37,14): warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>C:\Users\22318\Desktop\Data-Structure-master\VisualC++\CourseBook\0604_BiThrTree\BiThrTree.c(132,9): warning C4996: 'scanf': This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>LINK : warning LNK4217: 符号“_printf”(在“ BiThrTree-main.obj”中定义)已由“Status.lib(Status.obj)”(函数“_PressEnterToContinue”中)导入

1>Status.lib(Status.obj) : error LNK2019: 无法解析的外部符号 __imp__fscanf,函数 _ReadData 中引用了该符号

1>Status.lib(Status.obj) : error LNK2019: 无法解析的外部符号 __imp____iob_func,函数 _PressEnterToContinue 中引用了该符号

1>C:\Users\22318\Desktop\Data-Structure-master\VisualC++\CourseBook\Debug\0604_BiThrTree.exe : fatal error LNK1120: 2 个无法解析的外部命令

1>已完成生成项目“0604_BiThrTree.vcxproj”的操作 - 失败。
========== 生成: 成功 0 个,失败 1 个,最新 0 个,跳过 0 个 ==========`

习题6.51的问题

习题6.51,当右子树的根节点符号和当前节点符号同级时,也需要加括号,而您代码中这种情况是不加的。

dev C++ ExerciseBook 代码3.16 127行

// 如果调度序列为空,但是入口处存在未调度的车厢,或者中转栈里存在未处理的车厢,则表示发生错误
if(seq[k] == '\0' && (En[i] || StackEmpty(S)))
是不是应该是
if(seq[k] == '\0' && (En[i] || !StackEmpty(S)))

习题6.58的问题

书中说到“若p原来有左子树,则令它为x的右子树”,即使x为p的左子树,而原来p的左子树做为x的右子树。在这里理解可能有些偏差?

习题2.28的问题

习题2.28第(2)问,需要释放A中无用的节点。当while循环完毕,如果A表还剩节点没有遍历到,则需要释放。

关于include包含.c文件的问题

个人感觉通过include直接包含.c文件的写法有点非主流。而且容易造成命名冲突,全局变量冲突之类的问题。一般来说都是将声明和宏写到.h文件里,然后include用于包含.h文件。
而.c文件之间的依赖关系由调用gcc时候的参数说明。更简易的方法是使用makefile记录这些文件之间的依赖关系。

strlwr是非标准库中的函数,需要修改

在C语言标准库中,确实没有名为strlwr的函数来将整个字符串转换为小写字母。strlwr函数实际上是Windows系统特有的扩展函数,用于将字符串中的所有字符转换为小写。

7.12 Dijkstra 算法正确性试证明

假设点集 Vertex 中所含子集 A,对于从 A 出发的边集 Edge,若选定其中权重最小的边 Em,Em 指向点 B,可知:

  • Edge 中不存在权重小于 Em 的边
  • 对于 Edge 中除 Em 外的任意边 E*
    • weight( E* ) > weight( Em ),则对于 E* 所指向的点 V* 不存在边 EV 指向 B 使得 weight( E* ) + weight( EV ) <= weight( Em )
    • weight( E* ) = weight( Em ),当且仅当 E* 所指向的点 V* 中存在指向 B 的 EV 有 weight( EV ) == 0 时, weight( E* ) + weight( EV ) = weight( Em ) 此时 A --Em--> B 等价于 A --E*--> V* --EV--> B

对于 A + B = A* 的边集 Edge + EdgeB = Edge* 中权重最小的边 Em* 所指向的点 C 同理可证

参考《数据结构(C语言版)》--严蔚敏 P188

TestData_DN_M.txt has a bug

▲07 图/01 MGraph/TestData_DN_M.txt has a bug:

弧数应该是10?因为弧的集合中包含10条弧。

图类型→1(有向网)
顶点数→6
弧数→9
弧是否带有其他信息→0
顶点集→◤A,B,C,D,E,F◢
弧的集合→◤A,B,1◢◤A,F,3◢◤B,C,5◢◤C,A,6◢◤C,D,5◢◤D,A,9◢◤D,F,8◢◤E,D,4◢◤F,C,7◢◤F,E,5◢

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.