数据结构基础 from Coursera

What's inside

Syllabus

欢迎来到数据结构基础

欢迎你学习《数据结构基础》！相信大家听说过一个著名的公式“程序 = 数据结构 + 算法”，掌握数据结构和相关算法是设计程序来解决实际问题的基础能力。如何在解决一个问题的过程中把信息抽象出来？数据管理应当以什么样的方法存储？应当使用什么算法去求解问题？所选择的算法是否高效？学习了概论内容之后，你将对数据结构和相关算法有基本的了解，掌握一些算法效率分析的基本方法。另外，本模块还补充了编程作业指南和C++面向对象知识。重点：问题求解、数据结构的基本概念（逻辑、存储、运算），抽象数据类型，算法和算法的复杂度分析。难点：问题建模，抽象数据类型的理解，算法复杂度渐进分析。PS：我们这门课程一直处在不断地建设与优化当中，吸取了很多以往课程的经典视频，所以如果你看到视频中出现了不同课程的名字，也不要惊讶哦，因为你正在集百家所长：）

线性表

线性结构是最简单而应用最广泛的一种数据结构，在不同的场合会采取不同的存储结构和实现方法。本模块将介绍一种简单的线性结构——线性表，就是同类型的元素排成的一个线性序列，并且介绍了线性表的两种实现方法，即顺序表和链表。如何来实现顺序表和链表？什么时候应该用顺序表，什么时候链表更好？这一模块可以让你学会使用线性表及其相关的一些操作，解决一些简单问题，并考察分析时间空间上的效率，例如约瑟夫问题。重点：线性结构的逻辑定义，线性表的各种分类，顺序表、链表的定义和相关操作。难点：注意顺序表、链表的各种时间空间效率讨论，包括插入删除检索等在各种概率分布情况下的讨论。链表要特别注意表头结点的作用，链表指针的正确操作。PS：我们这门课程一直处在不断地建设与优化当中，吸取了很多以往课程的经典视频，所以如果你看到视频中出现了不同课程的名字，也不要惊讶哦，因为你正在集百家所长：）

栈与队列

日常生活中，你会发现如果桌上有一叠盘子，大家都只会拿最上面的那一个，食堂排队的时候，你总是先找到队尾加入，而排在队首的同学打完饭之后就会离开。也就是说，有的时候你也许只需要在线性序列的一端或两端进行操作，对应的就是栈和队列这两种受限的线性表，他们是最简单的基础数据结构，应用也最广泛。栈和队列有哪些特殊的操作？栈和队列能解决什么样的问题？学习完本章之后，你就可以用栈和队列这种数据结构，来解决与“先进先出”、“先进后出”有关的实际问题了，如宽度优先搜索、表达式求值等。重点：栈的 LIFO 特性，深度优先搜索，理解递归中栈的作用；队列的 FIFO 特性，宽度优先搜索。难点：机械的递归转非递归，简单理解就可以了，不需要掌握；顺序队列的实现假溢出处理。

字符串

生活中不仅仅只有数值或单个字符，很多情况下，由若干个字符构成的字符串能表达更明确的信息。在计算机中，字符串是如何存储的？有哪些相关操作？字符串常用的运算——模式匹配有哪些相关算法？你将会了解到字符串在计算机中的存储形式，常用的字符串操函数，以及模式匹配的一些高效的算法，并在实际问题中运用字符串处理技术。重点：掌握字符串的基本概念（注意‘\0’结束符），KMP快速模式匹配。难点：KMP快速模式匹配在一些重复子串问题中的应用。

二叉树基础

你是不是发现，在线性表中查找一个元素每次都要遍历整个表？效率如此低下，怎么改进呢？解决方案是使用非线性的数据结构——树型结构，这一章主要介绍一种最基础而最重要的非线性结构——二叉树。二叉树有哪些性质？如何在一棵二叉树中寻找一个特定的元素？如何来实现一棵二叉树？学习完这一模块，你会对二叉树的概念，以及一些简单的相关操作有基本的了解。重点：二叉树、满二叉树、完全二叉树的概念和性质，二叉树的前中后序各种深度优先遍历，二叉树宽度优先遍历。难点：栈在二叉树非递归深搜中的应用。

二叉树应用

你需要在一堆数据中快速查找某一个元素？你需要经常删除数据中的最大值？你需要对一些信息进行最优编码？在学习了二叉树这种数据结构之后，我们可以对二叉树附加一些限制条件，使得二叉树满足一些特殊的性质，并方便我们进行插入、删除、修改的操作，从而可以用来解决相关的实际问题。在这一模块中，你将学到二叉搜索树、堆与优先队列、Huffman树这三种最常用的特殊二叉树，了解他们的性质和实现方法。重点：二叉搜索树的索引性质，在二叉搜索树中插入删除的操作，Huffman树、堆的性质和应用。难点：在各种特殊二叉树中插入删除结点时要注意保持该数据结构的性质而且尽量保持各种操作的性能。

树

生活中，树形结构是很多客观事物与关系的抽象模型，例如亲属关系可以形成一个族谱，公司的上下级关系可以形成一个人事表。不过这些树形结构中，父结点往往都不止一个子结点，说明二叉树的表达能力不足以表示这些常见的客观问题。本章将引入树和森林的概念，介绍树的存储结构和多种表示方法。在实际应用中，你可以根据不同的情境，使用不同存储方式的树，从而解决相关的问题。重点：树的深搜、宽搜遍历，树的左子/右兄表示，父结点表示法与并查集运算，树的顺序存储（输入/输出都要考虑）。难点：树的各种应用基本上都基于遍历框架，需要注意左子/右兄表述方法中的对右兄弟链的访问；树的顺序存储通常也适应于二叉树的情况，可以用于完成建树的操作。

图

实际生活中可以用图的形式描述的问题随处可见，例如通信网络、社交网络等。图通常用来描述一个网状关系，图的结点描述了个体的信息，结点与结点之间的边描述了个体之间的关系，边还可以有权重，描述了这种关系的强弱程度。在这一章中，除了图的存储结构、遍历方法，你还会学到图结构的实际应用，如最短路径和最小生成树这两类最常见、最经典问题的解决方法。重点：图的深搜、宽搜框架；图的相邻矩阵、邻接表、十字链表等存储方法。图的最短路Dijkstra算法、Floyd算法，最小生成树Prim、Kruskal算法。难点：基于这图搜索框架的应用，例如拓扑排序；图的不同存储方式，适应范围和时空复杂度；最短路、最小生成树等综合应用。

期末考试，新征程起航！

恭喜大家完成了《数据结构基础》这门课的所有教学模块，现在就让我们一鼓作气完成期末考试，给这段难忘的学习里程画上一个圆满的句号吧！期末考试的题目将帮助你全方位地回顾课程中的重难点，让你体会到我们一路学习过后的成长与进步。如果测试没有一次通过也不要紧，只要认真复习相应的教学视频，一定能找到答案，我们的自助平台课程鼓励你反复尝试直到取得满意的成绩，加油！如果你成功地通过了测试，那我们就相约在专项课程的下一门《高级数据结构与算法》中见咯！

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

教授具有丰富的项目开发与结构层次设计的专业知识，有利于提升学习效果。

适合学习过 C/C++ 语言，希望将编程知识应用于实际问题解决的学习者。

课程内容涵盖数据结构的基础知识和应用，有助于培养扎实的数据结构基础。

提供大量经典数据结构，如线性表、栈、队列、二叉树、图等，扩展学习者的知识面。

重视算法效率分析，帮助学习者掌握问题求解的有效方法。

附有教材，方便学习者查阅和深入理解课程内容。

Reviews summary

Learn basic data structures

Students appear to have mixed reviews for this course on basic data structures. The course content appears to be comprehensive, but one reviewer reported that the pace of the course was too fast.

Fast pace

"讲得太快了"

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in 数据结构基础 with these activities:

Watch tutorials on data structures

Show steps

Provides visual and interactive explanations that can clarify concepts and show real-world applications.

Browse courses on Data Structures

Show steps

Find tutorials on platforms like YouTube, Coursera, or Udemy.
Watch the tutorials and take notes.
Practice the concepts shown in the tutorials.

Complete linear algebra exercises

Show steps

Helps solidify and reinforce concepts of linear transformations, vector spaces, matrices, and their application.

Browse courses on Matrices

Show steps

Find practice problems and exercises online or in textbooks.
Solve the practice problems.
Check your answers and identify areas for improvement.

Write a blog post on binary tree traversal

Show steps

Requires a deep understanding of the topic, helps reinforce concepts, and can benefit others by sharing knowledge.

Browse courses on Binary Trees

Show steps

Research different binary tree traversal algorithms.
Implement the algorithms in a programming language.
Write a blog post explaining the algorithms and their applications.

One other activity

Expand to see all activities and additional details

Show all four activities

Build a data structure visualization tool

Show steps

Requires a comprehensive understanding of data structures, enhances problem-solving abilities, and demonstrates practical application.

Browse courses on Data Structures

Show steps

Design the user interface for the visualization tool.
Implement the algorithms for visualizing different data structures.
Test and debug the visualization tool.
Document the usage of the visualization tool.

Career center

Learners who complete 数据结构基础 will develop knowledge and skills that may be useful to these careers:

Machine Learning Engineer

As a Machine Learning Engineer, you'll design and develop machine learning models. This course will help you understand how to organize and manage data, and how to choose the right algorithms for your machine learning tasks.

See salaries and explore the career path for Machine Learning Engineer

Database Administrator

As a Database Administrator, you'll be responsible for managing and maintaining databases. This course will teach you the data structures and algorithms used to organize and manage data in databases, helping you to ensure high performance and reliability.

See salaries and explore the career path for Database Administrator

Data Engineer

As a Data Engineer, you'll play a crucial role in building and maintaining the infrastructure that supports data-driven decision-making. This course will help you master the fundamentals of data structures and algorithms, which will empower you to design efficient and scalable data pipelines and data warehouses.

See salaries and explore the career path for Data Engineer

Computer Scientist

Computer Scientists research and develop new ways to use computers. This course lays a good foundation for the data structures and algorithms you'll need for groundbreaking research, which may include AI, cybersecurity, or other cutting-edge domains.

See salaries and explore the career path for Computer Scientist

Software Engineer

As a Software Engineer, you'll design and develop software programs. Some may choose to specialize in backend, frontend, or mobile development, but all can benefit from the data structures covered in this course. It will help you architect efficient, scalable, and maintainable software systems.

See salaries and explore the career path for Software Engineer

Software Architect

As a Software Architect, you'll be responsible for designing and maintaining the overall structure of a software application. This course will help you design robust and efficient software systems by understanding how to organize and manage data. It may be particularly helpful for those specializing in backend development.

See salaries and explore the career path for Software Architect

Actuary

As an Actuary, you will use mathematical and statistical methods to assess risk. This course will help you understand the fundamentals of probability and data structures, which are essential for actuarial work.

See salaries and explore the career path for Actuary

Artificial Intelligence Engineer

As an AI Engineer, you will be responsible for designing, developing, and deploying AI systems. This course may be useful in developing the data structures and algorithms that underpin machine learning models.

See salaries and explore the career path for Artificial Intelligence Engineer

Business Analyst

As a Business Analyst, you'll use data to identify and solve business problems. This course will help you understand the fundamentals of data structures and algorithms, which are essential for business analysis.

See salaries and explore the career path for Business Analyst

Operations Research Analyst

As an Operations Research Analyst, you'll use mathematical and analytical techniques to improve the efficiency of systems. This course will help you understand the fundamentals of data structures and algorithms, which are essential for operations research.

See salaries and explore the career path for Operations Research Analyst

Information Security Analyst

As an Information Security Analyst, you'll be responsible for preventing and mitigating security breaches. This course may be useful as you'll learn about data structures and algorithms can help you to detect and respond to security threats more effectively.

See salaries and explore the career path for Information Security Analyst

Financial Analyst

As a Financial Analyst, you'll use data to make investment recommendations. This course will help you understand the fundamentals of data structures and algorithms, which are essential for financial analysis.

See salaries and explore the career path for Financial Analyst

Quantitative Analyst

As a Quantitative Analyst, you'll use mathematical and statistical models to make trading decisions. This course will help you understand the fundamentals of data structures and algorithms, which are essential for quantitative analysis.

See salaries and explore the career path for Quantitative Analyst

Data Analyst

Data Analysts translate raw datasets into digestible insights to help businesses make informed decisions and fine-tune operations. As a Data Analyst, you'll make use of your knowledge of data structures to uncover patterns and trends in collected data. You'll likely also work with data mining, statistical analysis, machine learning, and data visualization tools, so this course may be useful to you.

See salaries and explore the career path for Data Analyst

Data Scientist

Data Scientists employ their skills in data analysis, modeling, and machine learning to help businesses understand and leverage their data for competitive advantage. You'll need to master data structures to organize and process massive datasets in order to uncover insights and trends. This course may be useful to you for building this foundation.

See salaries and explore the career path for Data Scientist