数据结构 ————指针、结构体

C语言描述如下:
main() {
int i,max,a[10]; printf("请输入个整数:"); for(i=0;i<10;i++) scanf("%d",&a[i]); max=a[0]; i=1; while(i<10){ if(a[i]>max) max=a[i]; i++; } printf("10个整数中的最大值为: %d\n",max);
2） 非数值问题 例 2 已知研究生选课情况，安排课程考试的日程。 1）问题涉及的对象：课程——可用课程名表示 ——不能用数值表示 2）对象之间的关系：同一研究生选修的课程不能安排在同一 时间考试，同一研究生选修的课程之间有 某种“冲突”关系 ——课程之间的这种关系不能用方程或 函数表示 3）数据及数据之间的关系如何存储？ 4）如何求解 ？
§1.1.2 本课程的研究对象
数据结构是研究什么的？这是课程最基本的问题，关 系到我们为什么要学习数据结构这门课程。
数值问题与非数值问题
有的同学可能想：我们在学习程序设计时，例如学习C语言时，学 习过各种数据类型数据如何表达，如何存储，如何处理，如整型变量， 可用标识符表达，在内存中它们通常是占用16个二进制位，可对它们作 加减乘除操作，但是C语言中学习过的关于数据的知识，只能求解一些简 单的计算问题和应用问题，如果你要想设计求解比较复杂的问题的程序 ，比如 比word简单的多的文本编辑程序，你还需要进一步的学习。 从应用问题涉及的对象来分可分为数值问题和非数值问题。数值 问题就是我们平时所说的计算问题，如已知圆的半径，要求圆的面 积。非数值问题就是问题中涉及的对象不能用数来表达的那些问题 。

第11章结构体、联合体与位运算本章介绍结构体、联合体及枚举类型等三种新的构造型数据类型以及位运算的基本方法，包括结构体的含义；结构体类型变量的定义、引用及初始化方法；结构体数组的定义和数组元素的引用；结构体类型指针的概念及链表的基本操作方法；联合体的含义；联合体类型变量的定义方法；枚举类型的定义； TYPEDEF的作用和位运算的基本方法等。

11.1 结构体类型通过前面有关章节的学习，我们认识了整型、实型、字符型等C语言的基本数据类型，也了解了数组这样一种构造型的数据结构，它可以包含一组同一类型的元素。

但仅有这些数据类型是不够的。

在实际问题中，有时需要将不同类型的数据组合成一个有机的整体，以便于引用。

例如，在新生入学登记表中，一个学生的学号、姓名、性别、年龄、总分等，它们属于同一个处理对象，却又具有不同的数据类型。

如图11-1。

每增加、删减或查阅一个学生记录，都需要处理这个学生的学号、姓名、性别、年龄、总分等数据，因此，有必要把一个学生的这些数据定义成一个整体。

图11-1虽然数组作为一个整体可用来处理一组相关的数据，但不足的是，一个数组只能按序组织一批相同类型的数据。

对于一组不同类型的数据，显然不能用一个数组来存放，因为数组中各元素的类型和长度都必须一致。

为了解决这个问题，Ｃ语言中给出了另一种构造数据类型——“结构体”。

11.1.1 结构体类型与结构体变量结构体是一种构造类型，它由若干“成员”组成。

每一个成员可以是一个基本数据类型或者又是一个构造类型。

结构体既然是一种构造而成的数据类型，那么在使用之前必须先定义它，如同在调用函数之前要先定义或声明一样。

定义一个结构体类型的一般形式为：struct 结构体名{ 成员1 类型1；成员2 类型2；...成员n 类型n；}；“结构体”这个词是根据英文单词structure译出的。

结构体中的每个成员均须作类型说明，成员名的命名应符合标识符的书写规定，成员名可以与程序中的变量名同名，二者不代表同一对象，互不干扰。

可以用类Pascal语言，本书采用类C语言
2021/8/17
39
算法的五个特性
有穷性 算法必须是经过有限的步骤操作完成。
确定性 可行性
算法中每一条指令必须有确切的含义，读者理解时不会产生 二义性。有任何条件下，算法只有唯一的一条执行路径，即 对于相同的输入只能得出相同的输出。
一个算法是能行的，即算法中描述的操作都是可以通过已经 实现的基本运算执行有限次来实现的。
物理 总分 名次 54 67 71
2021/8/17
13
数据对象
▪ 数据对象是性质相同的数据元素的集合，是 数据的一个子集。如整数数据对象。
▪ 某个班级的45位同学的数据（姓名，性别， 地址，联系电话，家长姓名，照片）。
2021/8/17
14
3. 数据结构(Data Structure)
▪ 数据结构是指数据相互之间存在一种或多种 特定关系的数据元素集合。
▪ 所以在讨论算法的时间复杂度时，我们就简单计算 语句的频度。
2021/8/17
43
矩阵的相乘
▪ 二个矩阵的相乘
n
cij aik •bkj k1
a11 a12 a1n b11 b12 b1n c11 c12 c1n
a21
a22
a2nb21
b22
b2n
c21c22 源自c2n an1 an2 ann bn1 bn2 bnn cn1 cn2 cnn
▪ 结构类型：其可以分割的，如数组，结构体 等(struct ,union)。
▪ 通常数据类型可以看成是程序设计语言中已 实现的数据结构。
2021/8/17
17
5. 抽象数据类型ADT
ADT包括定义和实现两个方面。定义独立于实 现。定义仅给出一个ADT的逻辑特性，不必 考虑如何在计算机中实现。

《数据结构》第五版清华大学自动化系李宛洲2004年5月目录第一章数据结构--概念与基本类型 (6)1.1概述 (6)1.1.1数据结构应用对象 (6)1.1.2学习数据结构的基础 (7)1.1.2.1 C语言中的结构体 (7)1.1.2.2 C语言的指针在数据结构中的关联作用 (8)1.1.2.3 C语言的共用体(union)数据类型 (12)1.1.3数据结构定义 (15)1.2线性表 (17)1.2.1 顺序表 (18)1.2.2 链表 (20)1.2.2.1链表的基本结构及概念 (20)1.2.2.2单链表设计 (22)1.2.2.3单链表操作效率 (29)1.2.2.4双链表设计 (30)1.2.2.5链表深入学习 (32)1.2.2.6稀疏矩阵的三元组与十字链表 (36)1.2.3 堆栈 (41)1.2.3.1堆栈结构 (41)1.2.3.2基本操作 (42)1.2.3.3堆栈与递归 (44)1.2.3.4递归与分治算法 (45)1.2.3.5递归与递推 (49)1.2.3.6栈应用 (52)1.2.4 队列 (57)1.2.4.1队列结构 (57)1.2.3.2队列应用 (59)1.3非线性数据结构--树 (64)1.3.1 概念与术语 (64)1.3.1.1引入非线性数据结构的目的 (64)1.3.1.2树的定义与术语 (65)1.3.1.3树的内部节点与叶子节点存储结构问题 (66)1.3.2 二叉树 (66)1.3.2.1二叉树基本概念 (66)1.3.2.2完全二叉树的顺序存储结构 (68)1.3.2.3二叉树遍历 (69)1.3.2.4二叉树唯一性问题 (71)1.3.3 二叉排序树 (72)1.3.3.1基本概念 (72)1.3.3.2程序设计 (73)1.3.4 穿线二叉树 (79)1.3.4.1二叉树的中序线索化 (80)1.3.4.2中序遍历线索化的二叉树 (81)1.3.5 堆 (82)1.3.5.1建堆过程 (83)1.3.5.2在堆中插入节点 (85)1.3.6 哈夫曼树 (86)1.3.6.1最佳检索树 (86)1.3.6.2哈夫曼树结构与算法 (88)1.3.6.3 哈夫曼树应用 (90)1.3.6.4哈夫曼树程序设计 (92)1.3.7 空间数据结构----二叉树深入学习导读 (95)1.3.7.1k-d树概念 (96)1.3.7.2k-d树程序设计初步 (97)1.4非线性数据结构--图 (100)1.4.1图的基本概念 (100)1.4.2图形结构的物理存储方式 (103)1.4.2.1相邻矩阵 (103)1.4.2.2图的邻接表示 (104)1.4.2.3图的多重邻接表示 (106)1.4.3图形结构的遍历 (107)1.4.4无向连通图的最小生成树（minimum-cost spanning tree:MST） (110)1.4.5有向图的最短路径 (113)1.4.5.1单源最短路径（single-source shortest paths） (113)1.4.5.2每对顶点间最短路经（all-pairs shortest paths） (116)1.4.6拓扑排序 (117)第二章检索 (123)2.1顺序检索 (123)2.2对半检索 (124)2.2.1 对半检索与二叉平衡树 (124)2.2.2对半检索思想在链式存储结构中的应用---跳跃表 (127)2.3分块检索 (133)2.4哈希检索 (134)2.4.1哈希函数 (135)2.4.2闭地址散列 (136)2.4.2.1线性探测法和基本聚集问题 (136)2.4.2.2删除操作造成检索链的中断问题 (138)2.4.2.3随机探测法 (139)2.4.2.4平方探测法 (140)2.4.2.5二次聚集问题与双散列探测方法 (141)2.4.3开地址散列 (142)2.4.4哈希表检索效率 (142)第三章排序 (145)3.1交换排序方法 (145)3.1.1直接插入排序 (145)3.1.2冒泡排序 (147)3.1.3 选择排序 (148)3.1.4 树型选择排序 (149)3.2S HELL排序 (150)3.3快速排序 (152)3.4堆排序 (154)3.5归并排序 (156)3.6数据结构小结 (159)3.6.1 数据结构的基本概念 (159)3.6.2 数据结构分类 (159)3.6.2.1数据结构中的指针问题 (160)3.6.2.2线性表的效率问题 (161)3.6.2.3二叉树 (161)3.6.3排序与检索 (161)3.7算法分析的基本概念 (162)3.7.1基本概念 (162)3.7.2上限分析 (164)3.7.3下限分析 (164)3.7.4空间代价与时间代价转换 (165)第6章高级数据结构内容--索引技术 (167)6.1基本概念 (167)6.2线性索引 (168)6.2.1 线性索引 (168)6.2.2 倒排表 (169)6.32-3树 (170)6.3.1 2-3树定义 (172)6.3.2 2-3树节点插入 (173)6.4B+树 (178)6.4.1 B+树定义 (178)6.4.2 B+树插入与删除 (180)6.4.3 B+树实验设计 (182)第一章数据结构--概念与基本类型1.1概述1.1.1数据结构应用对象计算机应用可以分为两大类，一类是科学计算和工业控制，另一类是商业数据处理。