三级偏软包过之数据结构三级1ppt课件

1、数据结构数据结构胡 杰: 2019-3-72主要内容 算法及其描述算法及其描述 基本概念和术语基本概念和术语 线性表线性表 栈和队列栈和队列 数组数组 树树 图图 查找查找 排序排序内容多内容多时间少时间少3什么是数据结构 解决一个具体问题的步骤：解决一个具体问题的步骤：从具体问题抽象出适当的数学模型设计解此模型的算法编写程序、测试得到结果梁架结构中应力：线性方程组预报人口增长：微分方程辅助医学诊断：贝叶斯模型4什么是数据结构 数值问题数值问题 例例1 1 知：游泳池的长知：游泳池的长lenlen和宽和宽widewide，求面积，求面积area area 建模型：建模

2、型： 数学模型：线性方程组数学模型：线性方程组问题涉及的对象：游泳池的长问题涉及的对象：游泳池的长lenlen、宽、宽widewide、面积、面积areaarea；对象之间的关系：对象之间的关系：area = len area = len wide wide5什么是数据结构 数值问题数值问题 例：已知游泳池的长例：已知游泳池的长lenlen和宽和宽widewide，求面积，求面积area area 编程：编程： main ( )main ( ) int len, wide ,area ; int len, wide ,area ; scanf (“%d %d%n”, &len, &am

3、p;wide); scanf (“%d %d%n”, &len, &wide); area = len area = len* *wide ;wide ; printf (“area=%d”, area); printf (“area=%d”, area); 6什么是数据结构 非数值问题非数值问题 在计算机上实现学生成绩系统的管理，必然要涉在计算机上实现学生成绩系统的管理，必然要涉及以下三个问题：及以下三个问题： 如何组织学生成绩表？如何组织学生成绩表？ 采用何种存储方式将表中的数据及数据之间的关采用何种存储方式将表中的数据及数据之间的关系存放到计算机的存储器中？系存放到计算机

4、的存储器中？ 在计算机上如何完成学生成绩系统的管理功能？在计算机上如何完成学生成绩系统的管理功能？7什么是数据结构 非数值问题非数值问题 例例: : 已知某级学生情况已知某级学生情况 , , 要求分班按入学成绩要求分班按入学成绩排列顺序。排列顺序。学号学号 姓名姓名 性别性别 出生日期出生日期 籍贯籍贯 入学成绩入学成绩 所在班级所在班级 00201 00201 杨润生杨润生 男男 82/06/01 82/06/01 广州广州 561 00 561 00计算机计算机2 200102 00102 石磊石磊 男男 83/12/21 83/12/21 汕头汕头 512 00 512 00计算机计算机

5、1 100202 00202 李梅李梅 女女 83/02/23 83/02/23 阳江阳江 532 00 532 00计算机计算机2 200301 00301 马耀先马耀先 男男 82/07/12 82/07/12 广州广州 509 00 509 00计算机计算机3 38什么是数据结构 非数值问题非数值问题 例例: : 迷宫问题。在迷宫中，每走到一处，接下来迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可

6、得一棵的过程中所有可能的通路都画出，则可得一棵“树树”。入口入口 出口出口9什么是数据结构 非数值问题非数值问题 例例: : 城市间交通网问题城市间交通网问题 出口出口10什么是数据结构 解决非数值计算问题的关键是要建立有效的数据结构来进行描述。 分析问题中所用到的数据是如何组织的； 研究数据之间的关系如何； 数据和数据之间的关系怎么存储到计算机中； 在这些数据上定义一个相应的运算。111.1 数据结构的基本术语 数据：能被计算机识别、存储和处理的的符号的集合，数据：能被计算机识别、存储和处理的的符号的集合，是计算机操作对象的总称。是计算机操作对象的总称。 数值、字符数值、字符 图形、图像图形

7、、图像声音、视频声音、视频 数据元素：数据的基本单位，亦称为结点、元素和记数据元素：数据的基本单位，亦称为结点、元素和记录等。在计算机程序中通常作为一个整体考虑和处理。录等。在计算机程序中通常作为一个整体考虑和处理。（例如：一个学生记录）（例如：一个学生记录） 数据项：数据结构中讨论的最小单位，数据元素是数数据项：数据结构中讨论的最小单位，数据元素是数据项的集合。亦称为域、字段等。（例如：学生记录据项的集合。亦称为域、字段等。（例如：学生记录中的学号。）中的学号。）121.1 数据结构的基本术语 数据结构：带结构的数据元素的集合。数据结构：带结构的数据元素的集合。 数据结构包括数据结构包括3

8、3部分内容：部分内容： 逻辑结构，指数据之间的相互关系。逻辑结构，指数据之间的相互关系。 存储结构，指数据及其关系在计算机中的存储方式，存储结构，指数据及其关系在计算机中的存储方式，或数据的物理结构。或数据的物理结构。 运算，指对数据进行检索、插入、删除、合并、排序、运算，指对数据进行检索、插入、删除、合并、排序、计算、转换、输入和输出等操作过程。计算、转换、输入和输出等操作过程。 Data_Structure = (D, R)Data_Structure = (D, R)131.2 数据的逻辑结构 数据元素之间的相互关系，被称为数据的逻辑结构Logical Structure）。 不同的关系

9、构成不同的结构，通常有下列四类基本结构： 集合、线性结构、树形结构 、图状结构 141.2 数据的逻辑结构 线性结构线性结构表 1.4 考生成绩统计表 准 考 证 号 姓 名 语 文 外 语 数 学 物 理 化 学 总 分 20006 胡桃 110 135 140 130 120 635 20004 黎明 100 130 140 116 122 608 20001 肖红 120 100 126 100 120 566 20003 唐平 90 130 130 100 95 545 20002 程程 100 110 120 90 100 520 20005 房芳 80 100 90 80 85 4

10、35 数据元素之间的关系：一对一数据元素之间的关系：一对一151.2 数据的逻辑结构 树形结构树形结构 例：家族的族谱，假设某家族有例：家族的族谱，假设某家族有10个成员个成员A，B，C，D，E，F，G， H，I， J，他们之间的血缘，他们之间的血缘关系可以用如下图表示。关系可以用如下图表示。J JI IA AC CB BD DH HG GF FE E数据元素之间的关系：一对多数据元素之间的关系：一对多161.2 数据的逻辑结构 图图/网结构网结构 例：城市之间的航线组成的数据结构例：城市之间的航线组成的数据结构数据元素之间的关系：多对多数据元素之间的关系：多对多171.3 数据的存储结构 数

11、据的存储结构是数据逻辑结构在计算机存储器中的表示映像），又称物理结构。 存储结构包括数据元素的表示和关系的表示。 顺序 链接 索引 散列181.3 数据的存储结构 顺序存储结构顺序存储结构 将逻辑上相邻的数据元素存储在物理位置上也相将逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元里，即将所有数据元素相继存放在邻的存储单元里，即将所有数据元素相继存放在一个连续相邻的存储区里。一个连续相邻的存储区里。 用存储结点间的位置关系来表示结点之间的逻辑用存储结点间的位置关系来表示结点之间的逻辑关系。关系。 顺序存储结构通常可以用顺序存储结构通常可以用C/C+语言的数组来描语言的数组来描述。述。191

12、.3 数据的存储结构 顺序存储结构顺序存储结构 例：用顺序存储方式表示例：用顺序存储方式表示一周一周7天，数据结构为：天，数据结构为： DS（D, R） DSun, Mon, Tue, Wed, Thu, Fri, Sat R = , , , , , 存储地址数组的下标数据域10000Sun10011Mon10022Tue10033Wed10044Thu10055Fri10066Sat201.3 数据的存储结构 链接存储结构链接存储结构 存储每个结点信息的同时，需要增加一个指针来存储每个结点信息的同时，需要增加一个指针来表示结点间的逻辑关系。表示结点间的逻辑关系。 不要求逻辑上相邻的结点在物理

13、位置上亦相邻，不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。结点间的逻辑关系由附加的指针字段表示。 每个结点由两部分组成：每个结点由两部分组成： 数据域：存储结点本身的信息；数据域：存储结点本身的信息； 指针域：存储该结点的后继或前驱结点的存指针域：存储该结点的后继或前驱结点的存储单元地址。储单元地址。211.3 数据的存储结构 链接存储结构链接存储结构 221.3 数据的存储结构 索引存储方式索引存储方式 索引存储方法是在存储结点信息的同时，建立一索引存储方法是在存储结点信息的同时，建立一个附加的索引表。个附加的索引表。 索引表中每一项称为一个索引项。索引表

14、中每一项称为一个索引项。 索引项的一般形式是：（关键字，地址）索引项的一般形式是：（关键字，地址）231.3 数据的存储结构 索引存储方式索引存储方式存储地址 1001 1003 1004 1005 1008 1009 1010 1012职工号姓名性别年龄0029王东男450005张红女250002李明男350038陈平女400031郭华男550043胡涛男370017李平女300048杨元男50关键字存储地址0002100400051003001710100029100100311008003810050043100900481012（b索引表（a文件数据区241.3 数据的存储结构 散列方

15、式散列方式 基本思想：根据结点的关键字基本思想：根据结点的关键字Key直接计算出该直接计算出该结点的存储地址。结点的存储地址。 即以线性表中的每个结点的关键字即以线性表中的每个结点的关键字Key为自变量，为自变量，通过一个确定的函数关系通过一个确定的函数关系f，计算出对应的函数值，计算出对应的函数值f(key)，然后把这个值解释为一块连续存储空间，然后把这个值解释为一块连续存储空间的存储地址，将结点存储到的存储地址，将结点存储到f(key)所指的存储单所指的存储单元中，使每个关键字和结构中一个的存储地址相元中，使每个关键字和结构中一个的存储地址相对应。对应。251.3 数据的存储结构 散列方式

16、散列方式 例：已知一组待存储的关键字为例：已知一组待存储的关键字为40，68，6，20，49，24，53，16，1，45，14，88），散列），散列地址为地址为T0.12。假设用除留取余法构造的散列函。假设用除留取余法构造的散列函数为：数为：H(key) = f(key) = key%13。 261.4 算法和算法分析 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。 算法特性： 有穷性 确定性 可行性 输入，零个或多个输入。 输出，一个或多个输出。程序并不需要满足有穷性操作系统）程序并不需要满足有穷性操作系统）271.4 算法和算法分析 算法描述方式算

17、法描述方式 流程图流程图 自然语言自然语言 伪代码伪代码 程序设计语言程序设计语言 描述算法的唯一要求：精确地描述计算过程。描述算法的唯一要求：精确地描述计算过程。C/C+281.4 算法和算法分析 算法设计要求算法设计要求 正确性正确性 健壮性健壮性 （如对非法数据的处理和反应）（如对非法数据的处理和反应） 可读性可读性 简单性简单性 （采用的数据结构和方法的简单程度）（采用的数据结构和方法的简单程度） 时间效率高时间效率高 存储空间少存储空间少291.4 算法和算法分析 算法时间复杂度算法时间复杂度 语句频度，算法中所有语句的执行次数之和。语句频度，算法中所有语句的执行次数之和。 一个算法

18、的语句频度是其求解问题规模一个算法的语句频度是其求解问题规模n的函数，的函数，记为记为T(n)。 如果有某个函数如果有某个函数F(n)，使得当问题规模，使得当问题规模n趋于无穷趋于无穷大时，有：大时，有： 则将则将O(F(n)称作算法的时间复杂度。称作算法的时间复杂度。limnT(n)F(n)= 常数常数 0只需分析只需分析主要部分主要部分301.4 算法和算法分析 算法时间复杂度算法时间复杂度 例：下面算法为求例：下面算法为求n个自然数的和个自然数的和S=1+2+3+n。请给出该算法的语句频度。请给出该算法的语句频度。 sum(int n) int i, s=0; for (i=1;iT(n

19、)n= 2 0算法复杂度为算法复杂度为O(F(n) = O(n)311.4 算法和算法分析 例：100元买100支笔, 其中钢笔 3元/支, 圆珠笔 2元/支, 铅笔 0.5元/支，写算法输出各种组合方案。时间复杂度为O (n3)#define N 100void scheme() int i, j, k, count, money; for (i = 0; i=N; i+ ) for (j = 0; j=N; j+ ) for (k=0; k=N; k+) count=i+j+k; money=3*i+2*j+0.5*k; if ( count=N & money=N) printf

20、 (“%d, %d, %d n%”, i, j, k) ; 321.4 算法和算法分析 解法2： # define N 100 void scheme( ) int i, j; for (i=0; i=N/3; i+) for (j=0; j=0个数据元素a1, a2, a3, , an组成的有限序列。记作A =（ a1, a2, a3, , an ） A是表名； ai1=iMAXSIZE) /* 检查顺序表的检查顺序表的长度长度 */ printf(nt溢出错误溢出错误!n); /* 打印错误信息打印错误信息 */ return (0); /* 插入失败函数插入失败函数返回返回0 */ el

21、se if (i(*l).len+1) printf(nt该位置不存在该位置不存在!n); return(0); /* 结点插入失败，函数返结点插入失败，函数返回回0 */432.3 顺序表的基本运算 插入运算插入运算 else /* 在第在第i个结点个结点ai 位置插入值为位置插入值为x的结点的结点 */ for (j = (*l).len-1; j=i-1; j-) (*l).ej+1 = (*l).ej; /*将结点依次后移将结点依次后移*/ (*l).ei-1 = x; /* 将将x插入第插入第i个结点个结点*/ (*l).len = (*l).len+1; /* 线性表长度加线性表长

22、度加1 */ return(1); /* 结点插入成功，函数返回结点插入成功，函数返回1 */ /* INSERT_SQLIST */442.3 顺序表的基本运算 删除运算删除运算 将线性表中第将线性表中第i个或符合要求的数据元素删除，个或符合要求的数据元素删除，使长度为使长度为n的线性表：的线性表： ( a1, , ai1 , ai , ai+1 , an ) 变成为长度为变成为长度为n-1的线性表：的线性表： ( a1, , ai1, ai+1, an )452.3 顺序表的基本运算 删除运算删除运算 过程：过程： 检查给定结点的删除位置是否正确，若删除位检查给定结点的删除位置是否正确，若

23、删除位置有错，则显示出错信息，退出程序运行；置有错，则显示出错信息，退出程序运行； 把表中第把表中第 i+1n 个结点之间的所有结点依次个结点之间的所有结点依次向前移动一个位置；向前移动一个位置； 将线性表的长度减将线性表的长度减1。462.3 顺序表的基本运算 删除运算删除运算 int delete_Sqlist (l, i) /* 顺序表中删除第顺序表中删除第i个结点个结点*/ sequenlist *l; int i; /* 删除第删除第i个位置上的结点个位置上的结点 */ int j; if (i(*l).len) printf(nt该结点不存在该结点不存在!n); return (0

24、); else for (j=i-1; jdatahead-nexthead=NULL，则该链表称为空表。（不带表头结点）（不带表头结点）562.4 线性表的链接存储结构 单链表单链表 head head是头是头指针指针ai-1ai-1a ai ia2a2a1a1ai+ai+1 1nanan 头结点头结点headhead（带表头结点）（带表头结点）572.4 线性表的链接存储结构 双向链表双向链表 双向链表中结点：双向链表中结点：headheadabC582.4 线性表的链接存储结构 循环链表循环链表592.4 线性表的链接存储结构 循环链表循环链表602.4 线性表的链接存储结构 双向循环链

25、表双向循环链表headhead (b)空的双向循环链表（c非空的双向循环链表headheadabC612.5 链表的基本运算 单链表的建立运算单链表的建立运算 用头插法新建一个带头结点的单链表过程：用头插法新建一个带头结点的单链表过程： 调用调用malloc函数，建立链表的头结点函数，建立链表的头结点head； 调用调用malloc函数，建立新的结点函数，建立新的结点p； 给新结点的数据域赋值，将新结点的指针域指给新结点的数据域赋值，将新结点的指针域指向向head所指的结点；所指的结点； 将链表头结点将链表头结点head的指针域修改为新结点的指针域修改为新结点p； 重复上述步骤，直至输入结束标

26、志重复上述步骤，直至输入结束标志0时时为止。为止。62 linklist * hhead_creat() datatype x; linklist *head, *p; /head为头指针 head=(struct node*)malloc(LEN); head-data=-999; /给表头结点数据域赋值 head-next=NULL; printf(n随机输入一组正整数以0结束输入:n); scanf(%d, &x); /输入第一个结点数据值 while (x!=0) /输入数据，以0为结束符 p=(struct node*)malloc(LEN); /* 生成新结点 p-data

27、=x;/给新结点的数据域赋值 p-next=head-next; /将新结点插入表头结点之后 head-next=p; scanf(“%d”, &x); /输入下一个结点的值 return(head);/函数返回链表头指针head /* CREATE_HEADHEAD*/632.5 链表的基本运算 单链表的建立运算单链表的建立运算 用尾插法建立带头结点的单链表的过程：用尾插法建立带头结点的单链表的过程： 调用调用malloc函数，生成一个头结点函数，生成一个头结点head； 调用调用malloc函数，开辟新的存储单元函数，开辟新的存储单元p； 给新结点的数据域赋值，将新结点的指针域设置

28、给新结点的数据域赋值，将新结点的指针域设置为空；为空； 将新结点链接到链表的尾结点将新结点链接到链表的尾结点rear之后，修改表之后，修改表尾指针尾指针rear； 重复上述步骤，直至输入结束标志重复上述步骤，直至输入结束标志0为止。为止。64linklist *hrear_creat() int x; linklist *head, *p, *rear; /* head, rear为头、尾指针 */ head=(struct node*)malloc(LEN); /* 建单链表头结点 */ head-data=-999; rear = head; /* 尾指针的初值为头结点head */ pr

29、intf(tt请随机输入互不相同的正整数以0作为结束:nntt); scanf(%d, &x); /* 读入第一个结点的值 */ while (x!=0) /* 输入数据，以0为结束符 */ p=(struct node*)malloc(LEN); /* 生成一个新结点 */ p-data=x; /* 给新结点的数据域赋值 */ rear-next=p; /* 新结点插入到表尾*rear之后 */ rear=p; /* 将尾指针rear指向新的尾结点 */ scanf(%d, &x); /* 输入下一个结点的数据 */ rear-next=NULL; /*将链表尾结点rear指

30、针域置空 */ return(head); /* 函数返回单链表的头指针head */* CREATE_HEADREAR */652.5 链表的基本运算 单链表的查找运算单链表的查找运算 由于逻辑相邻的结点并没有存储在物理相邻的单由于逻辑相邻的结点并没有存储在物理相邻的单元中，所以链表的遍历或查找运算，不能像顺序元中，所以链表的遍历或查找运算，不能像顺序表那样随机访问任意一个结点，而只能从链表的表那样随机访问任意一个结点，而只能从链表的头指针头指针head出发，顺着链域出发，顺着链域next逐个结点往下搜逐个结点往下搜索，直到找到所需要的结点为止或者当链表为空索，直到找到所需要的结点为止或者当

31、链表为空时结束查找。时结束查找。662.5 链表的基本运算 按值查找运算按值查找运算 在带头结点的单链表中查找是否存在给定值为在带头结点的单链表中查找是否存在给定值为key的结点。的结点。 基本思想：从链表的头结点开始，依次将链表中基本思想：从链表的头结点开始，依次将链表中结点的数据域与结点的数据域与key进行比较，若找到给定值进行比较，若找到给定值key，则查找成功，函数返回该结点的位置；若没有找则查找成功，函数返回该结点的位置；若没有找到给定值到给定值key，则查找失败，函数返回，则查找失败，函数返回NULL。672.5 链表的基本运算 按值查找运算按值查找运算 linklist *key

32、_search(head, key) linklist *head; datatype key; linklist *p=head; /* 从头结点开始扫描从头结点开始扫描 */ while(p!=NULL)&(p-data!=key) p=p-next; /* 扫描下一扫描下一个结点个结点 */ if(p-data=key) return(p); /* 查找成功返回指向该结查找成功返回指向该结点指针点指针 */ else return (NULL); /* 查找失败，函数返回查找失败，函数返回空指针空指针 */ /* KEY_SEARCH */682.5 链表的基本运算 按序号查找运

33、算按序号查找运算 在带头结点表长为在带头结点表长为n的单链表中，查找第的单链表中，查找第i个结点，个结点，仅当仅当1in时，时，i值是合法的。值是合法的。 基本思想：从表的头结点开始查找，用指针基本思想：从表的头结点开始查找，用指针p指指向当前结点，用向当前结点，用 j 作为计数器累计当前扫描过的作为计数器累计当前扫描过的结点数。结点数。j的初值为的初值为0，指向表头结点，当，指向表头结点，当p扫描下扫描下一个结点时，计数器一个结点时，计数器j相应地加相应地加1。 当当j = i时，指针时，指针p所指的结点就是要找的第所指的结点就是要找的第i个结个结点。点。 692.5 链表的基本运算 lin

34、klist *node_search(head, i) linklist *head; int i; linklist *p; int j; p=head; j=0; /* 从头结点开始扫描 */ while(p-next!=NULL)&(jnext; /* 扫描下一个结点 */ j+; /* 统计已扫描结点的个数 */ if(i=j) return(p); else return(NULL); /* 若找不到，则返回空指针 */ /* NO_SEARCH */702.5 链表的基本运算 单链表的插入单链表的插入 假设指针假设指针p指向单链表中某个结点，指针指向单链表中某个结点，指针s

35、指向值指向值为为x的新待插结点。的新待插结点。 若将新结点若将新结点s插入结点插入结点p之后，则称为后插；之后，则称为后插； 若将新结点若将新结点s插到结点插到结点p之前，则称为前插。之前，则称为前插。 后插运算后插运算y yx xz zp pheadheada as s712.5 链表的基本运算 单链表的插入单链表的插入 后插运算后插运算要求：插入“58”，保持有序。72 linklist * insert_behind (head, x) linklist *head; int x linklist *s, *p; s=(struct node*)malloc(LEN); /* 建立新结点

36、 */ s-data=x; /* 将x值赋给sdata */ p=findnode(head, x); /* 寻找结点值为x插入位置p */ s-next=p-next; /* 新结点s后继指向原p结点后继 */ p-next=s; /* p结点的后继指向新结点s */ return(head); /* 返回带头结点的单链表头指针*/ /* INSERT_BEHIND */ linklist *findnode(head, x) linklist *head; int x; linklist *p=head; while(p-next!=NULL)&(p-next-datanext;

37、/* 在表中查找合适的插入位置 */ return(p); /* 返回结点的合适的插入位置 */ /* FINDNODE */732.5 链表的基本运算 单链表的插入单链表的插入 前插运算前插运算742.5 链表的基本运算 单链表的插入单链表的插入 linklist *insert_ahead (linklist * head, int x, int i) linklist *s, *q;/* q为第为第i个结点的前个结点的前驱结点驱结点 */ s=(struct node*)malloc(LEN); /* 建立新结建立新结点点s */ s-data=x; /* 将将x值赋给值赋给sdata

38、*/ q=node_search(head, i-1); /* 寻找结点前寻找结点前驱结点驱结点q */ s-next=q-next; /* 新结点新结点s后继指向原后继指向原q结结点后继点后继 */ q-next=s; /* q结点的后继指向新结点结点的后继指向新结点s */ return(head); /* 返回带头结点单链返回带头结点单链表头指针表头指针*/ /* INSERT_AHEAD */752.5 链表的基本运算 单链表的删除单链表的删除 在链表中删除数据值为在链表中删除数据值为x的结点，并由系统收回其的结点，并由系统收回其占用的存储空间，过程：占用的存储空间，过程： 假设有两个

39、指针假设有两个指针p和和q，p指向要删除的结点，指向要删除的结点，q指向指向p的前驱结点；的前驱结点； 从链表从链表head的头结点开始，依次向后进行搜索，的头结点开始，依次向后进行搜索，当当q-next=p 并且并且p-data=x时，则待删除结点时，则待删除结点p的前驱结点的前驱结点q被找到；被找到； 修改修改p的前驱结点的前驱结点q的指针域，将的指针域，将q的后继指向的后继指向被删除结点被删除结点p的后继结点；的后继结点； 删除删除p结点并释放该结点所占用的存储空间结点并释放该结点所占用的存储空间762.5 链表的基本运算 单链表的删除单链表的删除见教材p69算法2-1177linkli

40、st *key_delete(linklist *head, int x) linklist *p, *q;/* p是被删除结点，q是p的前驱结点 */ p=head; while(p!=NULL)&(p-data!=x) q=p; p=p-next; if (p!=NULL) /* 若该结点存在，则删除之 */ q-next=p-next; /* 修改p前驱结点q指针域 */ free(p); /* 释放结点空间 */ return(head); /* 函数返回链表头指针*/ else printf(ntt要删的x=%d结点不存在，请重输数据!n, x); return(NULL);

41、 /* KEY_DELETE */782.5 链表的基本运算 双向链表的插入双向链表的插入 前插运算前插运算792.5 链表的基本运算 双向链表的插入双向链表的插入 后插运算后插运算802.5 链表的基本运算 双向链表的删除双向链表的删除812.5 链表的基本运算 循环链表的运算循环链表的运算 循环链表的优点：从链表中任何一个结点出发都循环链表的优点：从链表中任何一个结点出发都可以遍历表中所有的结点。可以遍历表中所有的结点。 循环链表的运算和单链表的主要差别：当链表遍循环链表的运算和单链表的主要差别：当链表遍历时，其终止条件不同：历时，其终止条件不同： 单链表中，用指针域是否为空作为判断条件；

42、单链表中，用指针域是否为空作为判断条件； 循环链表中，以结点的指针域是否等于表头循环链表中，以结点的指针域是否等于表头结点或开始遍历的结点作为结束条件。结点或开始遍历的结点作为结束条件。82单链表上查找、插入和删除运算的时间分析单链表上查找、插入和删除运算的时间分析 设Pi是单链表上查找第i个元素的概率，在长度为n的带头结点的单链表中可能进行查找的位置为i=0, 1, 2, , n。 在等概率情况下P1=P2=Pi=1/(n+1)。若查找成功时，则单链表中查找任意位置上数据元素的平均比较次数为： 单链表上查找、插入、删除算法的平均时间复杂度为O(n)。avg00111(1)(0 1 21)11

43、122nniiin nnEPiinnnnn 83顺序表和链表的比较 空间性能的比较空间性能的比较 存储密度：存储结点中数据域占用的存储量与存存储密度：存储结点中数据域占用的存储量与存储结点所占用的存储量之比称为存储密度。存储储结点所占用的存储量之比称为存储密度。存储密度越大，则存储空间的利用率就越高。密度越大，则存储空间的利用率就越高。 顺序表的存储密度是高于链表的存储密度。顺序表的存储密度是高于链表的存储密度。 但是，顺序表要求事先估计容量，这是比较困难但是，顺序表要求事先估计容量，这是比较困难的。的。84顺序表和链表的比较 时间性能的比较时间性能的比较 当线性表的主要操作是查找运算时，最好

44、采用顺当线性表的主要操作是查找运算时，最好采用顺序存储结构。序存储结构。 对于需要频繁地进行插入和删除操作的线性表，对于需要频繁地进行插入和删除操作的线性表，最好采用链接存储结构。最好采用链接存储结构。 若链表的插入和删除操作主要发生在表的首、尾若链表的插入和删除操作主要发生在表的首、尾两端，采用尾指针表示的单循环链表则是最好的两端，采用尾指针表示的单循环链表则是最好的选择。选择。85线性表 习题863.1 栈 栈是限定仅能在表尾一端进行插入、删除操作的栈是限定仅能在表尾一端进行插入、删除操作的线性表。线性表。（a1, a2, . , ai -1, ai , ai+1, , an ）插入删除8

45、73.1 栈 栈的特点后进先出883.2 栈的顺序存储结构 用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指示栈顶元素在顺序栈中的位置。 顺序栈可以用一个一维数组和一个记录栈顶位置的整型变量来实现。 顺序栈的三种形态：空栈、满栈和非满非空栈通过栈顶指针top体现）。 栈底可以设在数组的任意位置，栈顶随着进栈和退栈操作不断变化。893.2 栈的顺序存储结构 定义定义 #define MAX 100; typedef struct seqstack datatype eMAX; int top; seqstack; seqstack *S；emaxtops903.2 栈的顺序存

46、储结构 例如，假设顺序栈S为(A, B, C, D, E, F)，栈中最多能存储6个元素。请给出顺序栈S进栈和退栈时，其栈顶指针top和栈的变化情况。 913.3 栈的链式存储结构 以某种形式的链表作为栈的存储结构，其组织形式与单链表类似。 设一个栈S为(A, B, C)，链栈存储结构如下：923.3 栈的链接存储结构 依次插入两个元素D, E后： 从栈中删除栈顶元素E： 当链栈中所有的元素全部出栈后，top=NULL。933.4 顺序栈的基本运算 1顺序栈的初始化顺序栈的初始化 void InitStack(seqstack *S) S-top=-1; /* 将顺序栈设置为空栈将顺序栈设置为

47、空栈 */ 943.4 顺序栈的基本运算 2顺序栈判空顺序栈判空 int Empty(seqstack *S) if(S-toptop=MAX-1) /* 检查顺序栈是否满检查顺序栈是否满 */ printf(栈满溢出错误！栈满溢出错误！n); return(NULL); /* 插入元素失败插入元素失败 */ else S-top+; /* 栈顶指针指向下一个栈顶指针指向下一个空单元空单元 */ S-eS-top=x; /* 将新结点插入栈顶将新结点插入栈顶 */ return(S); /* 插入成功，返回新栈顶指针插入成功，返回新栈顶指针 */ 963.4 顺序栈的基本运算 4顺序栈的出栈顺

48、序栈的出栈 datatype Pop(seqstack *S) datatype x; /* 保存栈顶元素数据值保存栈顶元素数据值 */ if (Empty(S) /* 检查顺序栈是否检查顺序栈是否为空为空 */ printf(“下溢错误下溢错误! ”)；return(0); /* 删除失败删除失败 */ else /* 若顺序栈非空删除之若顺序栈非空删除之*/ x = S-eS-top; /* 暂存栈顶元素暂存栈顶元素 */ S-top-; return (x); 973.4 链栈的基本运算 1链栈的进栈链栈的进栈 linkstack *Push_LStack( linkstack *top

49、, datatype x) linkstack *p; p = (struct node*)malloc(sizeof(linkstack); p-data=x; p-next=top; top=p; return(top); 983.4 链栈的基本运算 2链栈的出栈链栈的出栈 linkstack *Pop_LStack(linkstack *top, datatype datap) linkstack *p; if (top=NULL) printf(“栈空！栈空！”); return(NULL); else *datap=top-data; p=top; top=top-next; fre

50、e(p); return(top); 993.5 共享栈 在同时建立两个栈的情况下，可将这两个栈的栈底分别设置在数组的两端。 除非空间总容量耗尽，否则不会出现栈满的情况。1003.6 栈在递归过程中的作用 所谓递归，是指一个函数、过程或者数据结构，若在其定义的内部又直接或者间接出现有定义自身的应用，则称其是递归的或者是递归定义的。 在调用一个函数程序的过程中又直接或间接地调用该函数程序自身，称为函数的递归调用。1013.6 栈在递归过程中的作用 一般函数的调用机制 A( )A( )B( );B( ); C( )C( ) B( )B( )C( );C( ); 调用调用返回返回函数调用顺序 A B

51、 C函数返回顺序 C B A后调用的函数先返回 函数调用机制可通过栈来实现计算机正是利用栈来实计算机正是利用栈来实现函数的调用和返回的现函数的调用和返回的1023.6 栈在递归过程中的作用 递归函数：一个直接调用自己或通过一系列调用递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。间接调用自己的函数称为递归函数。A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接调用自己B间接调用自己1033.6 栈在递归过程中的作用 递归算法的编写 1将问题用递归的方式描述定义） 2根据问题的递归描述定义编写递归算法 递归定义包括两项 1基本项终止项）：递归终

52、止时问题的解； 2递归项：将问题分解为与原问题性质相同，但规模较小的问题；1043.6 栈在递归过程中的作用 递归算法的编写 例：采用递归算法求解正整数n的阶乘n！）。正整数n的阶乘的递归定义为：1(0)!(1)!(0)nnnnn1053.6 栈在递归过程中的作用 递归算法的编写 float Fact(int n) /* 递归方法求n的阶乘 */ float f = 0.0; if (nfront Rear + QueueSize front 若rear head = MAXSIZE-1； sq-rear = MAXSIZE-1； 1254.3 循环队列的运算 2循环队列判空循环队列判空 in

53、t Cir_Empty (sequeue *sq) if (sq-rear= =sq-head) return(1); else return(0); 1264.3 循环队列的运算 3循环队列的入队循环队列的入队 int Cir_EnQueue(sequeue *sq，datatype x) if(sq-head= =(sq-rear+1)% MAXSIZE) printf(队列为满队列为满); return (0); else sq-rear=(sq-rear+1)% MAXSIZE; sq-esq-rear=x; return(1); 1274.3 循环队列的运算 4循环队列的出队循环队列

54、的出队 datatype Cir_DeQueue(sequeue *sq) if (Cir_Empty (sq) printf(“队列已空！不能执行出队队列已空！不能执行出队”); return(0); else sq-head=(sq-head+1) % MAXSIZE; return(sq-esq-head); 1284.4 链队列的运算 1链接队列初始化链接队列初始化 /* 带头结点的链接队列带头结点的链接队列*/ viod Llink_InitQueue (head, rear) linkqueue *head, *rear head=(struct node*)malloc(LEN)

55、; head-data=-999; head-next=NULL; rear=head; 1294.4 链队列的运算 2链接队列的入队链接队列的入队 #define LEN sizeof(linkqueue) void Llink_EnQueue (datatype x) p=(struct node*)malloc(LEN); p-data=x; p-next=NULL; rear-next=p; rear=p; 1304.4 链队列的运算 4链接队列的出队链接队列的出队 datatype Link_DeQueue(linkqueue *head) datatype x; if (Empty

56、(head, rear)= =1) printf(队列为空队列为空!n); return (NULL); else s=head-next; x=s-data; head-next=s-next-next; free(s); return (x); 131队列 习题1325 数组 数组是由nn1个相同类型的数据元素a1, a2, a3, , an组成的有限序列，也可以称为向量。 可用数组下标来区分各元素，一个下标惟一地对应一个元素，元素的下标一般具有固定的上界和下界。1335 数组 一维数组一维数组An，由，由a1, a2, , an1, an这这n个元个元素组成，每个元素有一个确定元素位置的

57、下标。素组成，每个元素有一个确定元素位置的下标。 二维数组二维数组Amn，由，由mn个元素组成，每个元个元素组成，每个元素由两个能确定元素位置的下标组成。素由两个能确定元素位置的下标组成。1345.1 数组的存储结构 多维数组通常采用顺序存储方式，即把数组中各元素的值按某种次序存放在计算机的一组连续存储单元中。 一组连续的存储单元存放多维数组就必须按照某种次序将数组中的元素排成一个线性序列，然后将这个线性序列顺序存放到计算机中。1355.1 数组的存储结构 一维数组的顺序存储结构一维数组的顺序存储结构 一维数组一维数组A中第中第i个元素个元素ai的存储位置的计算公的存储位置的计算公式为：式为：

58、 Loc(ai) = Loc(a1) + (i-1)*d (1i n) C+中，下标从中，下标从0开始开始关键是计算关键是计算准确个数准确个数1365.1 数组的存储结构 二维数组的两种顺序存储方式二维数组的两种顺序存储方式 1以行序为主序行优先）；以行序为主序行优先）； 2以列序为主序列优先）。以列序为主序列优先）。 1375.1 数组的存储结构 当Amn按“行优先存储时的存储位置计算公式： Loc(ai,j) = Loc(a0,0) + (nij )d 当Amn按“列优先“存储时的存储位置计算公式： Loc(ai,j) = Loc(a0,0) + (mji )d下标从下标从0，0到到m-1

59、, n-1)1385.2 转置矩阵运算 对于一个mn的矩阵A，它的转置矩阵B是一个nm的矩阵，且Bi，j）= Aj，i），1in，1jm。 Void TransMat ( MatType A , MatType B , int m , int n ) int i , j ; for ( i = 0; im; i+ ) for ( j=0; j=j）。则其存储分配情况如图所示。1425.3 对称阵的压缩存储 在压缩结构中，为了便于访问对称矩阵A中元素并能进行处理，必须通过给定的一组下标i, j找到对称矩阵中任一元素aij在一维数组Bk中的存储位置，即在aij和Bk之间找到一个对应关系。K = i

60、 ( i 1 ) 2+ j 1 当当 i = j j ( j 1 ) 2+ i 1 当当 i = j 1435.3 三角矩阵的压缩存储 以主对角线划分，三角矩阵分为两种：上三角矩阵和下三角矩阵。 所谓上三角矩阵，是指下三角不包括主角线中的元素均为常数c的n阶方阵。下三角矩阵正好相反，其主对角线上方均为常数c。在多数情况下，三角矩阵的常数c为0。 对于任何一个n阶下三角矩阵都具有下述性质：当ij时，aij=c；同理，对于任何一个n阶上三角矩阵：当ij时，aij=c。1445.3 三角矩阵的压缩存储 三角矩阵采用压缩存储方式时，只存储矩阵的下三角元素或上三角元素。如果让矩阵中所有重复元素c共享一个存储单元，那么三角矩阵中n2个元素就可以压缩存储到一维数组Bn(n+1)/2中，其中重复元素c