《数据结构》课程PPT教学课件（讲稿）第一章 数据结构基础

第一章数据结构基础 要想成为一名真正的程序员,数据结构是必备的基础知识。 只有学过数据结构,才能真正有效规范地组织程序中的数据。而 在实际编程中,有些问题必须通过特定的数据结构才能更方便地 解决。因此数据结构是每一个搞计算机的人都应当十分掌握的知 识。 要想全面而系统地学习数据结构的知识,这里的介绍显然是 不充分的,建议应当找来专门介绍数据结构的书籍学习。如果你 只想掌握一般层次的知识,或是已经学过数据结构,只是为了深 入地学习本书后续的内容而进行回顾和复习,那么本章的介绍是 足够的

第一章 数据结构基础 要想成为一名真正的程序员，数据结构是必备的基础知识。 只有学过数据结构，才能真正有效规范地组织程序中的数据。而 在实际编程中，有些问题必须通过特定的数据结构才能更方便地 解决。因此数据结构是每一个搞计算机的人都应当十分掌握的知 识。 要想全面而系统地学习数据结构的知识，这里的介绍显然是 不充分的，建议应当找来专门介绍数据结构的书籍学习。如果你 只想掌握一般层次的知识，或是已经学过数据结构，只是为了深 入地学习本书后续的内容而进行回顾和复习，那么本章的介绍是 足够的

11什么是数据结构 数据结构就是指计算机内部数据的组织形式和存储方法。 我们再熟悉不过的数组就是一种简单而典型的线性数据结构类型 。本章中将更加具体地介绍一些常用的数据结构,主要包括:线 性结构、树、图。 线性结构是最常用,也是最简单的一种数据结构。还有 种常用的数据结构叫做图状结构,简称图结构。图结构中数据元 素之间存在着“多对多”的关系,因此图结构较树结构,线性结 构要复杂得多。在处理一些复杂的问题中,图结构往往能派上用 场

1.1 什么是数据结构 数据结构就是指计算机内部数据的组织形式和存储方法。 我们再熟悉不过的数组就是一种简单而典型的线性数据结构类型 。本章中将更加具体地介绍一些常用的数据结构，主要包括：线 性结构、树、图。 线性结构是最常用，也是最简单的一种数据结构。还有一 种常用的数据结构叫做图状结构，简称图结构。图结构中数据元 素之间存在着“多对多”的关系，因此图结构较树结构，线性结 构要复杂得多。在处理一些复杂的问题中，图结构往往能派上用 场

12顺序表 在计算机内部存储一张线性表(线性结构的数表), 最为方便简单的就是用一组连续地址的内存单元来存储整张 线性表。这种存储结构称为顺序存储结构,这种存储结构下 的线性表就叫做顺序表。如图1-1所示,就是顺序表的示意 000H 0001H+ 内存空间地址连 有唯一的4 续,数据顺序存储← 名称标识4 图1-1顺序表的示意4

1.2 顺序表 在计算机内部存储一张线性表（线性结构的数表）， 最为方便简单的就是用一组连续地址的内存单元来存储整张 线性表。这种存储结构称为顺序存储结构，这种存储结构下 的线性表就叫做顺序表。如图1-1所示，就是顺序表的示意

121顺序表的定义 定义一张顺序表也就是在内存中开辟一段连续的存储 空间,并给它一个名字来标识。只有定义了一个顺序表, 才能利用该顺序表存放数据元素,也才能对该顺序表进行 各种操作。 有两种定义顺序表的方法,一是静态地定义一张顺序 表;二是动态生成一张顺序表

1.2.1 顺序表的定义 定义一张顺序表也就是在内存中开辟一段连续的存储 空间，并给它一个名字来标识。只有定义了一个顺序表， 才能利用该顺序表存放数据元素，也才能对该顺序表进行 各种操作。 有两种定义顺序表的方法，一是静态地定义一张顺序 表；二是动态生成一张顺序表

122向顺序表中插入元素 下面介绍如何在长度为n的顺序表中的第个位置插入新元素 item。 所谓在长度为n的顺序表中的第价个位置插入新元素是指在顺序 表第1个数据元素和第个数据元素之间插入一个新元素item 函数 nserelem的作用是在顺序表 Sqlist中第个位置上插入元 素item,并将顺序表长度加1。其实现过程如下。 (1)判断插入元素的位置是否合法。一个长度为n的顺序表的 可能插入元素的位置是1~n+1,因此如果1或者n+1或者表满 n== Maxsize(因为表的内存大小固定不变)的插入都是非法的。 (2)将顺序表的1以后的元素顺序后移一个元素的位置,即 将顺序表从第个元素到第n个元素顺序后移一个元素的位置。 (3)在表的第个位置(下标为1)上插入元素item,并将表 长加

1.2.2 向顺序表中插入元素 下面介绍如何在长度为n的顺序表中的第i个位置插入新元素 item。 所谓在长度为n的顺序表中的第i个位置插入新元素是指在顺序 表第i-1个数据元素和第i个数据元素之间插入一个新元素item。 函数InserElem的作用是在顺序表Sqlist中第i个位置上插入元 素item，并将顺序表长度加１。其实现过程如下。 （1）判断插入元素的位置是否合法。一个长度为n的顺序表的 可能插入元素的位置是1~n+1，因此如果in+1或者表满 n==MaxSize（因为表的内存大小固定不变）的插入都是非法的。 （2）将顺序表的i-1以后的元素顺序后移一个元素的位置，即 ：将顺序表从第i个元素到第n个元素顺序后移一个元素的位置。 （3）在表的第i个位置（下标为i-1）上插入元素item，并将表 长加1

123从顺序表中删除元素 下面介绍如何删除长度为n的顺序表中的第个位置的元 素 所谓删除长度为n的顺序表中的第个位置的元素,就是 指将顺序表第个位置上的元素去掉。 函数 Delelem的作用是从顺序表 Sqlist中删除第个位置 的元素,并将表的长度值减1。其实现过程如下 (1)判断要删除的元素是否合法。对于一个长度为n的 顺序表,删除元素的合法位置是1~n,因此如果in都 是不合法的。 (2)将顺序表的第位置以后的元素依次前移,这样就 将第i个元素覆盖掉了,也就起到删除第个位置元素的作用。 (3)最后将表长减1

1.2.3 从顺序表中删除元素 下面介绍如何删除长度为n的顺序表中的第i个位置的元 素。 所谓删除长度为n的顺序表中的第i个位置的元素，就是 指将顺序表第i个位置上的元素去掉。 函数DelElem的作用是从顺序表Sqlist中删除第i个位置 的元素，并将表的长度值减1。其实现过程如下。 （1）判断要删除的元素是否合法。对于一个长度为n的 顺序表，删除元素的合法位置是1~n，因此如果in都 是不合法的。 （2）将顺序表的第i位置以后的元素依次前移，这样就 将第i个元素覆盖掉了，也就起到删除第i个位置元素的作用。 （3）最后将表长减1

124实例与分析 前面介绍了静态顺序表和动态顺序表的定义,创建, 插入元素,删除元素等方法。下面通过具体的实例巩固学到 的知识。 【实例1-1】创建一个静态的顺序表存放整数,大小为 10,完成以下的操作: (1)输入6个整数,打印出顺序表中的内容,并显示 表中剩余的空间个数。 (2)在顺序表中的第3个位置插入元素0,打印出顺序 表中的内容,并显示表中剩余的空间个数。 (3)再试图插入表中第11个位置整数0,程序提示超 出范围 (4)删除表中第6个元素,打印出顺序表中的内容, 并显示表中剩余的空间个数

1.2.4 实例与分析 前面介绍了静态顺序表和动态顺序表的定义，创建， 插入元素，删除元素等方法。下面通过具体的实例巩固学到 的知识。 【实例1-1】创建一个静态的顺序表存放整数，大小为 10，完成以下的操作： （1）输入6个整数，打印出顺序表中的内容，并显示 表中剩余的空间个数。 （2）在顺序表中的第3个位置插入元素0，打印出顺序 表中的内容，并显示表中剩余的空间个数。 （3）再试图插入表中第11个位置整数0，程序提示超 出范围 （4）删除表中第6个元素，打印出顺序表中的内容， 并显示表中剩余的空间个数

13链表 与顺序表相同,链表也是一种线性表,它的数据的逻 辑组织形式是一维的。而与顺序表不同的是,链表的物理存 储结构是用一组地址任意的存储单元存储数据的。也就是说 它不像顺序表那样占据一段连续的内存空间,而是将存储 单元分散在内存的任意地址上。在链表结构中,存储的每个 数据元素记录都存放到幢淼囊桓鼋岬悖node)中,而每个 结点之间由指针将其连接在一起,这样就形成了一条如同“ 链”的结构。 head 1249 1356 1021 1249 B C D 1356 1475 1021 Null

1.3 链表 与顺序表相同，链表也是一种线性表，它的数据的逻 辑组织形式是一维的。而与顺序表不同的是，链表的物理存 储结构是用一组地址任意的存储单元存储数据的。也就是说 ，它不像顺序表那样占据一段连续的内存空间，而是将存储 单元分散在内存的任意地址上。在链表结构中，存储的每个 数据元素记录都存放到幢淼囊桓鼋岬悖node）中，而每个 结点之间由指针将其连接在一起，这样就形成了一条如同“ 链”的结构

13.1创建一个链表 建立一条长度为n的链表的全过程,共分为以下几个步骤。 (1)用 malloc函数在内存的动态存储区中开辟一块大小为 sizeof(( LNode)的空间,并将其地址赋值给 Linklist类型变量p,然 后将数据e存入该结点的数据域data,指针域存放NULL。其中数 据e由函数Get获得。 (2)如果指针变量list为空,说明本次生成的结点为第一个 结点,所以将p赋值给ist,ist是 Linklist类型变量,只用来指向 第一个链表结点,因此它是该链表的头指针,最后要返回。 (3)如果指针变量list不为空,则说明本次生成的结点不是 第一个结点,因此将p赋值给r→neto (4)再将p赋值给r,目的是使r再次指向最后的结点,以便 生成链表的下一个结点,即:保证r永远指向原先链表的最后一个 结点。 (5)最后将生成的链表的头指针ist返回主调函数,通过 ist就可以访问到该链表的每一个结点,并对该链表进行操作

1.3.1 创建一个链表 建立一条长度为n的链表的全过程，共分为以下几个步骤。 （1）用malloc函数在内存的动态存储区中开辟一块大小为 sizeof(LNode)的空间，并将其地址赋值给LinkList类型变量p,然 后将数据e存入该结点的数据域data，指针域存放NULL。其中数 据e由函数Get获得。 （2）如果指针变量list为空，说明本次生成的结点为第一个 结点，所以将p赋值给list，list是LinkList类型变量，只用来指向 第一个链表结点，因此它是该链表的头指针，最后要返回。 （3）如果指针变量list不为空，则说明本次生成的结点不是 第一个结点，因此将p赋值给r->next。 （4）再将p赋值给r，目的是使r再次指向最后的结点，以便 生成链表的下一个结点，即：保证r永远指向原先链表的最后一个 结点。 （5）最后将生成的链表的头指针list返回主调函数，通过 list就可以访问到该链表的每一个结点，并对该链表进行操作

132向链表中插入结点 下面介绍如何在指针q指向的结点后面插入结点。该过 程的步骤如下: (1)先创建一个新结点,并用指针p指向该结点。 (2)将q指向的结点的next域的值(即q的后继结点的 指针)赋值给p指向结点的next域。 (3)将p的值赋值给q的next域

1.3.2 向链表中插入结点 下面介绍如何在指针q指向的结点后面插入结点。该过 程的步骤如下： （1）先创建一个新结点，并用指针p指向该结点。 （2）将q指向的结点的next域的值（即q的后继结点的 指针）赋值给p指向结点的next域。 （3）将p的值赋值给q的next域