数据结构c语言版笔记

数据结构实验与习题

杨秀金 汪沁 编

浙江万里学院计算机系

1

内 容 简 介

数据结构是计算机专业的核心课，是重要的专业基础课。实践是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课下独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致，相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一方面提高联系实际分析解决问题的能力。正是基于以上的原因编写了这本“数据结构实验与习题”。

本参考书包括C语言基础知识、上机实验习题和书面作业练习题三部分。

在C语言基础知识部分，主要介绍了输入/输出、函数及参数传递和结构体的概念应用。这部分内容非常重要，掌握的是否熟练会直接影响“数据结构“的学习。

在实验部分，包括有完整的C语言源程序例题，介绍了一些设计数据结构题目所需的C语言常用的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已

数据结构(C语言版)课件

第二章 线性表19:09

数据结构(C语言版)课件

第2章 第3章 第4章 第5章

线性表 栈和队列 串 数组和广义表

线性结构(逻辑、存储 和运算)

线性结构的定义：若结构是非空有限集，则有且仅有一个开始结 点和一个终端结点，并且所有结点都最多只有一个 直接前趋和一个直接后继。 可表示为：(a1 ,

a2

, ……,

a n)

数据结构(C语言版)课件

线性结构表达式：(a1 ,

a2

, ……,

a n)

线性结构的特点：① 只有一个首结点和尾结点； ② 除首尾结点外，其他结点只有一个直接前驱和一 个直接后继。简言之，线性结构反映结点间的逻辑关系是 一对一 的

线性结构包括线性表、堆栈、队列、字符串、数 组等等，其中，最典型、最常用的是

线性表19:09

数据结构(C语言版)课件

第2章

线性表

教学目标1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种 存储结构的不同特点及其适用场合

19:09

数据结构(C语言版)课件

教学内容2.1 线性表的类型定义 2.2 线性表的顺序表示和实现

2.3 线性表的链式表示和实现2.4 线性表的应用

19:09

数据结构(C语言版)课

数据结构习题一 1/8

习题一

一、 单选题

1. 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行

( )。

A. HL=p; p->next=HL; B. p->next=HL->next; HL->next=p; C. p->next=HL; p=HL; D. p->next=HL; HL=p;

2. 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ ）个元素. A. n B.n-1 C. n+1 D.不确定 3. 下述哪一条是顺序存储方式的优点？（ ）

A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快

4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元

素占一个空间，问A[2

第一章 习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽

（3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型

（5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作

（9）有限性、输入、可行性 4、（1）A（2）C（3）C

5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章 习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定

（4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A

B：H、L、I、E、A C：F、M

D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C

3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什

《数据结构(C语言版)》复习重点

重点在二、三、六、七、九、十章，考试内容两大类：概念，算法

第1章、绪论

1. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

3. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 其4类基本结构：集合、线性结构、树形结构、图状结构或网状结构 4. 逻辑结构：是数据元素之间的逻辑关系的描述。 5. 物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。

其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构 6. 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

其5个重要特性：有穷性、确定性、可行性、输入、输出

7. 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n)) ；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。 例如： (a) {++x;s=0;}

(b

数据结构(C语言版) 实验报告

姓名： 学号： 指导老师：

实验1

实验题目：单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。

实验主要步骤：

1、分析、理解给出的示例程序。

2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序：

（1） 增加插入结点的功能。

（2） 将建立链表的方法改为头插入法。

程序代码:

#include"stdio.h" #include"string.h" #include"stdlib.h"

#include"ctype.h"

typedef struct node //定义结点 {

char data[10]; //结点的数据域为字符串 struct node *next; /

数据结构复习资料

一、填空题

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。

2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。

3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。

4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。

5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。

7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。

8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。

数据结构复习资料 由 其直接前驱结点的链域的值 指示。

19． 在n个结点的单链表中要删除已知结点*p，

需找到它的前驱结点的地址，其时间复杂度为O（n）。 1. 数据结构是一门研究非数值计算的程序设计问

20.栈只能在 栈顶 插入和删除元素；对于队列题中计算机的 操作对象 以及它们之间的 关

只能在 队尾 插入和 队首 删除元素。 系 和运算等的学科。

21. 栈是一种特殊的线性表，允许插入和删除运算2. 数据结构被形式地定义为（D, R），其中D是 数的一端称为 栈顶 。不允许插入和删除运算据元素 的有限集合，R是D上的 关系 有限

的一端称为 栈底 。 集合。

22. 队列 是被限定为只能在表的一端进行插3. 数据结构包括数据的 逻辑结构 、数据的 存储

入运算，在表的另一端进行删除运算的线性表。 结构 和数据的 运算 这三个方面的内容。

4. 数据结构按逻辑结构可分为两大类，它们分别是 26． 由３个结点所构成的二叉

树有 5 种形态。 线性结构 和

《数据结构》课程实验指导

《数据结构》实验教学大纲

课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统 总学时/实验学时：64/16 总学分/实验学分：3.5/0.5

一、课程简介

数据结构是计算机各专业的重要技术基础课。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

二、实验的地位、作用和目的

数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根

数据结构（C语言版）考研复习题

第一章 绪论

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

1.2 常用的存储表示方法有哪几种?

1.3 算法的时间复杂度仅与问题的规模相关吗?

1.4 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大\记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣? 函数 大\表示 优劣 (1) T1(n)=5n-3n+60lgn 5n+O(n) (2) T2(n)=3n+1000n+3lgn 3n+O(n) (3) T3(n)=8n+3lgn 8n+O(lgn) (4) T4(n)=1.5n+6000nlgn 1.5n+O(nlgn)

2

2

2

2

2

2

2

2

第二章 线性表