数据结构数据结构Email: 2013-3-7级偏软包过之数据结构三级课件主要内容算法及其描述算法及其描述基本概念和术语基本概念和术语线性表线性表栈和队列栈和队列数组数组树树图图查找查找排序排序内容多内容多时间少时间少2级偏软包过之数据结构三级课件什么是数据结构解决一个具体问题的步骤：解决一个具体问题的步骤：从具体问题抽象出适当的数学模型设计解此模型的算法编写程序、测试得到结果梁架结构中应力：线性方程组预报人口增长：微分方程辅助医学诊断：贝叶斯模型3级偏软包过之数据结构三级课件什么是数据结构数值问题数值问题例1 已知：游泳池的长len和宽wide，求面积area 建模型建模型：数学模型：线性方程组问题涉及的对象：游泳池的长len、宽wide、面积area；对象之间的关系：area = len wide4级偏软包过之数据结构三级课件什么是数据结构数值问题数值问题例：已知游泳池的长len和宽wide，求面积area 编程：编程： main ( ) int len, wide ,area ; scanf (“%d %d%n”, &len, &wide); area = len*wide ; printf (“area=%d”, area); 5级偏软包过之数据结构三级课件什么是数据结构非数值问题非数值问题在计算机上实现学生成绩系统的管理，必然要涉及以下三个问题：如何组织学生成绩表？采用何种存储方式存储方式将表中的数据及数据之间的数据之间的关系关系存放到计算机的存储器中？在计算机上如何完成学生成绩系统的管理功能？6级偏软包过之数据结构三级课件什么是数据结构非数值问题非数值问题例: 已知某级学生情况 , 要求分班按入学成绩排列顺序。学号学号 姓名姓名 性别性别 出生日期出生日期 籍贯籍贯 入学成绩入学成绩 所在班级所在班级 00201 杨润生 男 82/06/01 广州 561 00计算机200102 石磊 男 83/12/21 汕头 512 00计算机100202 李梅 女 83/02/23 阳江 532 00计算机200301 马耀先 男 82/07/12 广州 509 00计算机37级偏软包过之数据结构三级课件什么是数据结构非数值问题非数值问题例: 迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树”。入口入口 出口出口8级偏软包过之数据结构三级课件什么是数据结构非数值问题非数值问题例: 城市间交通网问题 出口出口9级偏软包过之数据结构三级课件什么是数据结构解决非数值计算问题的关键是要建立有效的数据数据结构结构来进行描述。分析问题中所用到的数据是如何组织的；研究数据之间的关系数据之间的关系如何；数据和数据之间的关系怎么存储怎么存储到计算机中；在这些数据上定义一个相应的运算运算。10级偏软包过之数据结构三级课件1.1 数据结构的基本术语 数据数据：能被计算机识别、存储和处理的的符号的集合，是计算机操作对象的总称。 数值、字符数值、字符 图形、图像图形、图像声音、视频声音、视频数据元素数据元素：数据的基本单位，基本单位，亦称为结点、元素结点、元素和记记录录等。在计算机程序中通常作为一个整体考虑和处理。（例如：一个学生记录）数据项数据项：数据结构中讨论的最小单位最小单位，数据元素是数据项的集合。亦称为域域、字段字段等。（例如：学生记录中的学号。）11级偏软包过之数据结构三级课件1.1 数据结构的基本术语数据结构数据结构：带结构的数据元素的集合。数据结构包括3部分内容：逻辑结构逻辑结构，指数据之间的相互关系。存储结构存储结构，指数据及其关系在计算机中的存储方式，或数据的物理结构。运算运算，指对数据进行检索、插入、删除、合并、排序、计算、转换、输入和输出等操作过程。Data_Structure = (D, R)12级偏软包过之数据结构三级课件1.2 数据的逻辑结构数据元素之间的相互关系，被称为数据的逻辑结数据的逻辑结构构（Logical Structure）。不同的关系构成不同的结构，通常有下列四类基本结构：集合、线性结构线性结构、树形结构树形结构 、图状结构图状结构 13级偏软包过之数据结构三级课件1.2 数据的逻辑结构线性结构线性结构数据元素之间的关系：一对一数据元素之间的关系：一对一14级偏软包过之数据结构三级课件1.2 数据的逻辑结构树形结构树形结构例：家族的族谱，假设某家族有10个成员A，B，C，D，E，F，G， H，I， J，他们之间的血缘关系可以用如下图表示。J JI IA AC CB BD DH HG GF FE E数据元素之间的关系：一对多数据元素之间的关系：一对多15级偏软包过之数据结构三级课件1.2 数据的逻辑结构图图/网结构网结构例：城市之间的航线组成的数据结构数据元素之间的关系：多对多数据元素之间的关系：多对多16级偏软包过之数据结构三级课件1.3 数据的存储结构数据的存储结构是数据逻辑结构在计算机存储器中的表示（映像），又称物理结构。存储结构包括数据元素数据元素的表示和关系关系的表示。顺序顺序链接链接索引散列17级偏软包过之数据结构三级课件1.3 数据的存储结构顺序存储结构顺序存储结构将逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元里，即将所有数据元素相继存放在一个连续相邻的存储区里。用存储结点间的位置关系来表示结点之间的逻辑用存储结点间的位置关系来表示结点之间的逻辑关系关系。顺序存储结构通常可以用C/C+语言的数组数组来描述。18级偏软包过之数据结构三级课件1.3 数据的存储结构顺序存储结构顺序存储结构例：用顺序存储方式表示一周7天，数据结构为：DS（D, R）DSun, Mon, Tue, Wed, Thu, Fri, SatR = , , , , , 存储地址数组的下标数据域10000Sun10011Mon10022Tue10033Wed10044Thu10055Fri10066Sat19级偏软包过之数据结构三级课件1.3 数据的存储结构链接存储结构链接存储结构存储每个结点信息的同时，需要增加一个指针指针来表示结点间的逻辑关系。不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示逻辑关系由附加的指针字段表示。每个结点由两部分组成：数据域数据域：存储结点本身的信息；指针域指针域：存储该结点的后继（或前驱）结点的存储单元地址。20级偏软包过之数据结构三级课件1.3 数据的存储结构链接存储结构链接存储结构21级偏软包过之数据结构三级课件1.3 数据的存储结构索引存储方式索引存储方式索引存储方法是在存储结点信息的同时，建立一个附加的索引表索引表。索引表中每一项称为一个索引项。索引项的一般形式是：（关键字，地址）（关键字，地址）22级偏软包过之数据结构三级课件1.3 数据的存储结构索引存储方式索引存储方式存储地址 1001 1003 1004 1005 1008 1009 1010 1012职工号姓名性别年龄0029王东男450005张红女250002李明男350038陈平女400031郭华男550043胡涛男370017李平女300048杨元男50关键字存储地址0002100400051003001710100029100100311008003810050043100900481012（b）索引表（a）文件数据区23级偏软包过之数据结构三级课件1.3 数据的存储结构散列方式散列方式基本思想：根据结点的关键字根据结点的关键字KeyKey直接计算出该结直接计算出该结点的存储地址点的存储地址。即以线性表中的每个结点的关键字Key为自变量，通过一个确定的函数关系f，计算出对应的函数值f(key)f(key)，然后把这个值解释为一块连续存储空间的存储地址存储地址，将结点存储到f(key)所指的存储单元中，使每个关键字和结构中一个的存储地址相对应。24级偏软包过之数据结构三级课件1.3 数据的存储结构散列方式散列方式例：已知一组待存储的关键字为（40，68，6，20，49，24，53，16，1，45，14，88），散列地址为T0.12。假设用除留取余法构造的散列函数为：H(key) = f(key) = key%13。 25级偏软包过之数据结构三级课件1.4 算法和算法分析算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法特性：有穷性有穷性确定性确定性可行性可行性输入输入，零个零个或多个输入。输出输出，一个一个或多个输出。程序并不需要满足有穷性（操作系统）程序并不需要满足有穷性（操作系统）26级偏软包过之数据结构三级课件1.4 算法和算法分析算法描述方式算法描述方式流程图流程图自然语言自然语言伪代码伪代码程序设计语言程序设计语言描述算法的唯一要求：精确地描述计算过程。C/C+27级偏软包过之数据结构三级课件1.4 算法和算法分析算法设计要求算法设计要求正确性正确性健壮性健壮性 （如对非法数据的处理和反应）（如对非法数据的处理和反应）可读性可读性简单性简单性 （采用的数据结构和方法的简单程度）（采用的数据结构和方法的简单程度）时间效率高时间效率高存储空间少存储空间少28级偏软包过之数据结构三级课件1.4 算法和算法分析算法时间复杂度算法时间复杂度语句频度语句频度，算法中所有语句的执行次数之和。一个算法的语句频度是其求解问题规模n的函数，记为T(n)。如果有某个函数F(n)，使得当问题规模n趋于无穷大时，有：则将O(F(n)称作算法的时间复杂度。limnT(n)F(n)=常数常数0只需分析只需分析主要部分主要部分29级偏软包过之数据结构三级课件1.4 算法和算法分析算法时间复杂度算法时间复杂度例：下面算法为求n个自然数的和S=1+2+3+n。请给出该算法的语句频度。 sum(int n) int i, s=0; for (i=1;iT(n)n=20算法复杂度为算法复杂度为O(F(n)=O(n)30级偏软包过之数据结构三级课件1.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 (“%d, %d, %d n%”, i, j, k) ; 31级偏软包过之数据结构三级课件1.4 算法和算法分析解法2：# define N 100void 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是表名；ai（1=iMAXSIZE) /* 检查顺序表的长度 */ printf(nt溢出错误!n); /* 打印错误信息 */ return (0); /* 插入失败函数返回0 */ else if (i(*l).len+1) printf(nt该位置不存在!n); return(0); /* 结点插入失败，函数返回0 */42级偏软包过之数据结构三级课件2.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; /* 线性表长度加1 */ return(1); /* 结点插入成功，函数返回1 */ /* INSERT_SQLIST */43级偏软包过之数据结构三级课件2.3 顺序表的基本运算删除运算删除运算将线性表中第i个（或符合要求的）数据元素删除，使长度为n的线性表： ( a1, , ai1 , a ai i , ai+1 , an ) 变成为长度为n-1的线性表：( a1, , ai1, ai+1, an )44级偏软包过之数据结构三级课件2.3 顺序表的基本运算删除运算删除运算过程：过程： 检查给定结点的删除位置是否正确，若删除位置有错，则显示出错信息，退出程序运行； 把表中第 i+1n 个结点之间的所有结点依次向前移动一个位置； 将线性表的长度减1。45级偏软包过之数据结构三级课件2.3 顺序表的基本运算删除运算删除运算int delete_Sqlist (l, i) /* 顺序表中删除第i个结点*/sequenlist *l; int i; /* 删除第i个位置上的结点 */ int j; if (i(*l).len) printf(nt该结点不存在!n); return (0); else for (j=i-1; jdatahead-nexthead=NULL，则该链表称为空表空表。（不带表头结点）（不带表头结点）55级偏软包过之数据结构三级课件2.4 线性表的链接存储结构单链表单链表 headhead是头指针是头指针a ai-i-1 1a ai ia a2 2a a1 1a ai+i+1 1na an n 头结点头结点headhead（带表头结点）（带表头结点）56级偏软包过之数据结构三级课件2.4 线性表的链接存储结构双向链表双向链表双向链表中结点：headheadabC57级偏软包过之数据结构三级课件2.4 线性表的链接存储结构循环链表循环链表58级偏软包过之数据结构三级课件2.4 线性表的链接存储结构循环链表循环链表59级偏软包过之数据结构三级课件2.4 线性表的链接存储结构双向循环链表双向循环链表headhead (b)空的双向循环链表（c）非空的双向循环链表headheadabC60级偏软包过之数据结构三级课件2.5 链表的基本运算单链表的建立运算单链表的建立运算用头插法头插法新建一个带头结点的单链表过程： 调用malloc函数，建立链表的头结点head； 调用malloc函数，建立新的结点p； 给新结点的数据域赋值，将新结点的指针域指向head所指的结点； 将链表头结点head的指针域修改为新结点p； 重复上述步骤，直至输入结束标志0时为止。61级偏软包过之数据结构三级课件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=x;/给新结点的数据域赋值 p-next=head-next; /将新结点插入表头结点之后 head-next=p; scanf(“%d”, &x); /输入下一个结点的值 return(head);/函数返回链表头指针head /* CREATE_HEADHEAD*/62级偏软包过之数据结构三级课件2.5 链表的基本运算单链表的建立运算单链表的建立运算用尾插法尾插法建立带头结点的单链表的过程： 调用malloc函数，生成一个头结点head； 调用malloc函数，开辟新的存储单元p； 给新结点的数据域赋值，将新结点的指针域设置为空； 将新结点链接到链表的尾结点rear之后，修改表尾指针rear； 重复上述步骤，直至输入结束标志0为止。63级偏软包过之数据结构三级课件linklist *hrear_creat() int x; linklist *head, *p, *rear; /* head, rear为头、尾指针 */ head=(struct node*)malloc(LEN); /* 建单链表头结点 */ head-data=-999; rear = head; /* 尾指针的初值为头结点head */ printf(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指针域置空 */ return(head); /* 函数返回单链表的头指针head */* CREATE_HEADREAR */64级偏软包过之数据结构三级课件2.5 链表的基本运算单链表的查找运算单链表的查找运算由于逻辑相邻的结点并没有存储在物理相邻的单元中，所以链表的遍历或查找运算，不能像顺序表那样随机访问任意一个结点，而只能从链表的从链表的头指针头指针head出发，顺着链域出发，顺着链域next逐个结点往下搜逐个结点往下搜索，直到找到所需要的结点为止或者当链表为空索，直到找到所需要的结点为止或者当链表为空时结束查找。时结束查找。65级偏软包过之数据结构三级课件2.5 链表的基本运算按值查找运算按值查找运算在带头结点的单链表中查找是否存在给定值为key的结点。基本思想基本思想：从链表的头结点开始，依次将链表中结点的数据域与key进行比较，若找到给定值key，则查找成功，函数返回该结点的位置；若没有找到给定值key，则查找失败，函数返回NULL。66级偏软包过之数据结构三级课件2.5 链表的基本运算按值查找运算按值查找运算linklist *key_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 */67级偏软包过之数据结构三级课件2.5 链表的基本运算按序号查找运算按序号查找运算在带头结点表长为n的单链表中，查找第第i个个结点，仅当1in时，i值是合法的。基本思想基本思想：从表的头结点开始查找，用指针p指向当前结点，用 j 作为计数器计数器累计当前扫描过的结点数。j的初值为0，指向表头结点，当p扫描下一个结点时，计数器j相应地加1。当j = i时，指针p所指的结点就是要找的第i个结点。 68级偏软包过之数据结构三级课件2.5 链表的基本运算linklist *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 */69级偏软包过之数据结构三级课件2.5 链表的基本运算单链表的插入单链表的插入假设指针p指向单链表中某个结点，指针s指向值为x的新待插结点。若将新结点s插入结点p之后，则称为后插后插；若将新结点s插到结点p之前，则称为前插前插。后插运算后插运算y yx xz zp pheadheada as s70级偏软包过之数据结构三级课件2.5 链表的基本运算单链表的插入单链表的插入后插运算后插运算要求：插入“58”，保持有序。71级偏软包过之数据结构三级课件linklist * insert_behind (head, x) linklist *head; int x linklist *s, *p; s=(struct node*)malloc(LEN); /* 建立新结点 */ 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; /* 在表中查找合适的插入位置 */ return(p); /* 返回结点的合适的插入位置 */* FINDNODE */72级偏软包过之数据结构三级课件2.5 链表的基本运算单链表的插入单链表的插入前插运算前插运算73级偏软包过之数据结构三级课件2.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 */ q=node_search(head, i-1); /* 寻找结点前驱结点q */ s-next=q-next; /* 新结点新结点s后继指向原后继指向原q结点后继结点后继 */ q-next=s; /* q结点的后继指向新结点s */ return(head); /* 返回带头结点单链表头指针*/* INSERT_AHEAD */74级偏软包过之数据结构三级课件2.5 链表的基本运算单链表的删除单链表的删除在链表中删除数据值为x的结点，并由系统收回其占用的存储空间，过程： 假设有两个指针p和q，p指向要删除的结点，q指向p的前驱结点； 从链表head的头结点开始，依次向后进行搜索，当q-next=p 并且p-data=x时，则待删除结点p的前驱结点q被找到； 修改p的前驱结点q的指针域，将q的后继指向被删除结点p的后继结点； 删除p结点并释放该结点所占用的存储空间75级偏软包过之数据结构三级课件2.5 链表的基本运算单链表的删除单链表的删除见教材p69算法2-1176级偏软包过之数据结构三级课件linklist *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); /* KEY_DELETE */77级偏软包过之数据结构三级课件2.5 链表的基本运算双向链表的插入双向链表的插入前插运算前插运算78级偏软包过之数据结构三级课件2.5 链表的基本运算双向链表的插入双向链表的插入后插运算后插运算79级偏软包过之数据结构三级课件2.5 链表的基本运算双向链表的删除双向链表的删除80级偏软包过之数据结构三级课件2.5 链表的基本运算循环链表的运算循环链表的运算循环链表的优点循环链表的优点：从链表中任何一个结点出发都可以遍历表中所有的结点。循环链表的运算和单链表的主要差别：当链表遍历时，其终止条件不同： 单链表中，用指针域是否为空作为判断条件； 循环链表中，以结点的指针域是否等于表头结点或开始遍历的结点作为结束条件。81级偏软包过之数据结构三级课件单链表上查找、插入和删除运算的时间分析单链表上查找、插入和删除运算的时间分析设Pi是单链表上查找第i个元素的概率，在长度为n的带头结点的单链表中可能进行查找的位置为i=0, 1, 2, , n。在等概率情况下P1=P2=Pi=1/(n+1)。若查找成功时，则单链表中查找任意位置上数据元素的平均比较次数为：单链表上查找、插入、删除算法的平均时间复杂度为O(n)。82级偏软包过之数据结构三级课件顺序表和链表的比较空间性能的比较空间性能的比较存储密度存储密度：存储结点中数据域占用的存储量与存储结点所占用的存储量之比称为存储密度存储密度。存储密度越大，则存储空间的利用率就越高。顺序表的存储密度是高于链表的存储密度顺序表的存储密度是高于链表的存储密度。但是，顺序表要求事先估计容量顺序表要求事先估计容量，这是比较困难的。83级偏软包过之数据结构三级课件顺序表和链表的比较时间性能的比较时间性能的比较当线性表的主要操作是查找运算查找运算时，最好采用顺顺序序存储结构。对于需要频繁地进行插入和删除插入和删除操作的线性表，最好采用链接链接存储结构。若链表的插入和删除操作主要发生在表的首、尾两端，采用尾指针表示的单循环链表则是最好的选择。84级偏软包过之数据结构三级课件线性表习题85级偏软包过之数据结构三级课件3.1 栈栈是限定仅能在表尾一端进行插入、删除操作的栈是限定仅能在表尾一端进行插入、删除操作的线性表。线性表。（a1, a2, . , ai -1, ai , ai+1, , an ）插入删除86级偏软包过之数据结构三级课件3.1 栈栈的特点后进先出后进先出87级偏软包过之数据结构三级课件3.2 栈的顺序存储结构用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指示栈顶元素在顺序栈中指示栈顶元素在顺序栈中的位置的位置。顺序栈可以用一个一维数组和一个记录栈顶位置的整型变量来实现。顺序栈的三种形态：空栈、满栈和非满非空栈（通过栈顶指针top体现）。栈底可以设在数组的任意位置，栈顶随着进栈和退栈操作不断变化。88级偏软包过之数据结构三级课件3.2 栈的顺序存储结构定义定义 #define MAX 100; typedef struct seqstack datatype eMAX; int top; seqstack; seqstack *S；emaxtops89级偏软包过之数据结构三级课件3.2 栈的顺序存储结构例如，假设顺序栈S为(A, B, C, D, E, F)，栈中最多能存储6个元素。请给出顺序栈S进栈和退栈时，其栈顶指针top和栈的变化情况。90级偏软包过之数据结构三级课件3.3 栈的链式存储结构以某种形式的链表作为栈的存储结构，其组织形式与单链表类似。设一个栈S为(A, B, C)，链栈存储结构如下：91级偏软包过之数据结构三级课件3.3 栈的链接存储结构依次插入两个元素D, E后：从栈中删除栈顶元素E：当链栈中所有的元素全部出栈后，top=NULL。92级偏软包过之数据结构三级课件3.4 顺序栈的基本运算1顺序栈的初始化顺序栈的初始化 void InitStack(seqstack *S) S-top=-1; /* 将顺序栈设置为空栈 */ 93级偏软包过之数据结构三级课件3.4 顺序栈的基本运算2顺序栈判空顺序栈判空 int Empty(seqstack *S) if(S-toptop=MAX-1) /* 检查顺序栈是否满 */ printf(栈满溢出错误！n); return(NULL); /* 插入元素失败 */ else S-top+; /* 栈顶指针指向下一个空单元 */ S-eS-top=x; /* 将新结点插入栈顶 */ return(S); /* 插入成功，返回新栈顶指针 */ 95级偏软包过之数据结构三级课件3.4 顺序栈的基本运算4顺序栈的出栈顺序栈的出栈 datatype Pop(seqstack *S) datatype x; /* 保存栈顶元素数据值 */ if (Empty(S) /* 检查顺序栈是否为空 */ printf(“下溢错误! ”)；return(0); /* 删除失败 */ else /* 若顺序栈非空删除之*/ x = S-eS-top; /* 暂存栈顶元素 */ S-top-; return (x); 96级偏软包过之数据结构三级课件3.4 链栈的基本运算1链栈的进栈链栈的进栈linkstack *Push_LStack( linkstack *top, datatype x) linkstack *p; p = (struct node*)malloc(sizeof(linkstack); p-data=x; p-next=top; top=p; return(top); 97级偏软包过之数据结构三级课件3.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; free(p); return(top); 98级偏软包过之数据结构三级课件3.5 共享栈在同时建立两个栈的情况下，可将这两个栈的栈底分别设置在数组的两端。除非空间总容量耗尽，否则不会出现栈满的情况。99级偏软包过之数据结构三级课件3.6 栈在递归过程中的作用所谓递归递归，是指一个函数、过程或者数据结构，若在其定义的内部又直接或者间接出现有定义自身的应用，则称其是递归的或者是递归定义的。在调用一个函数（程序）的过程中又直接或间接地调用该函数（程序）本身，称为函数的递归调用。100级偏软包过之数据结构三级课件3.6 栈在递归过程中的作用 一般函数的调用机制 A( )A( )B( );B( ); C( )C( ) B( )B( )C( );C( ); 调用调用返回返回函数调用顺序 A B C函数返回顺序 C B A后调用的函数先返回 函数调用机制可通过栈来实现函数调用机制可通过栈来实现计算机正是利用栈来实计算机正是利用栈来实现函数的调用和返回的现函数的调用和返回的101级偏软包过之数据结构三级课件3.6 栈在递归过程中的作用递归函数递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接调用自己B间接调用自己102级偏软包过之数据结构三级课件3.6 栈在递归过程中的作用递归算法的编写1）将问题用递归的方式描述（定义）2）根据问题的递归描述（定义）编写递归算法递归定义包括两项1）基本项（终止项）基本项（终止项）：递归终止时问题的解；2）递归项）递归项：将问题分解为与原问题性质相同，但规模较小的问题；103级偏软包过之数据结构三级课件3.6 栈在递归过程中的作用递归算法的编写例：采用递归算法求解正整数n的阶乘（n！）。正整数n的阶乘的递归定义为：104级偏软包过之数据结构三级课件3.6 栈在递归过程中的作用递归算法的编写 float Fact(int n) /* 递归方法求n的阶乘 */ float f = 0.0; if (nfront Rear + QueueSize front 若rear head = MAXSIZE-1； sq-rear = MAXSIZE-1；124级偏软包过之数据结构三级课件4.3 循环队列的运算2循环队列判空循环队列判空int Cir_Empty (sequeue *sq) if (sq-rear= =sq-head) return(1); else return(0); 125级偏软包过之数据结构三级课件4.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); 126级偏软包过之数据结构三级课件4.3 循环队列的运算4循环队列的出队循环队列的出队datatype Cir_DeQueue(sequeue *sq) if (Cir_Empty (sq) printf(“队列已空！不能执行出队”); return(0); else sq-head=(sq-head+1) % MAXSIZE; return(sq-esq-head); 127级偏软包过之数据结构三级课件4.4 链队列的运算1链接队列初始化链接队列初始化/* 带头结点的链接队列*/viod Llink_InitQueue (head, rear)linkqueue *head, *rear head=(struct node*)malloc(LEN); head-data=-999; head-next=NULL; rear=head; 128级偏软包过之数据结构三级课件4.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; 129级偏软包过之数据结构三级课件4.4 链队列的运算4链接队列的出队链接队列的出队datatype Link_DeQueue(linkqueue *head) datatype x; if (Empty(head, rear)= =1) printf(队列为空!n); return (NULL); else s=head-next; x=s-data; head-next=s-next-next; free(s); return (x); 130级偏软包过之数据结构三级课件队列习题131级偏软包过之数据结构三级课件5 数组数组是由n（n1）个相同类型的数据元素a1, a2, a3, , an组成的有限序列，也可以称为向量。可可用数组下标来区分各元素用数组下标来区分各元素，一个下标惟一地对应一个元素，元素的下标一般具有固定的上界和下界。132级偏软包过之数据结构三级课件5 数组一维数组一维数组An，由a1, a2, , an1, an这n个元素组成，每个元素有一个确定元素位置的下标。二维数组二维数组Amn，由mn个元素组成，每个元素由两个能确定元素位置的下标组成。133级偏软包过之数据结构三级课件5.1 数组的存储结构多维数组通常采用顺序存储方式，即把数组中各各元素的值按某种次序存放在计算机的一组连续存元素的值按某种次序存放在计算机的一组连续存储单元中储单元中。一组连续的存储单元存放多维数组就必须按照某种次序次序将数组中的元素排成一个线性序列线性序列，然后将这个线性序列顺序存放到计算机中。134级偏软包过之数据结构三级课件5.1 数组的存储结构一维数组的顺序存储结构一维数组的顺序存储结构一维数组A中第i个元素ai的存储位置的计算公式为： Loc(ai) = Loc(a1) + (i-1)*d (1i n)C+中，下标从中，下标从0开始开始关键是计算关键是计算准确个数准确个数135级偏软包过之数据结构三级课件5.1 数组的存储结构二维数组的两种顺序存储方式二维数组的两种顺序存储方式1）以行序为主序（行优先）；）以行序为主序（行优先）；2）以列序为主序（列优先）。）以列序为主序（列优先）。136级偏软包过之数据结构三级课件5.1 数组的存储结构当Amn按“行优先行优先”存储时的存储位置计算公式：Loc(ai,j) = Loc(a0,0) + (nij )d当Amn按“列优先列优先“存储时的存储位置计算公式： Loc(ai,j) = Loc(a0,0) + (mji )d下标从（下标从（0，0）到（）到（m-1,n-1)137级偏软包过之数据结构三级课件5.2 转置矩阵运算对于一个mn的矩阵A，它的转置矩阵B是一个nm的矩阵，且B（i，j）= A（j，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）。则其存储分配情况如图所示。141级偏软包过之数据结构三级课件5.3 对称阵的压缩存储在压缩结构中，为了便于访问对称矩阵A中元素并能进行处理，必须通过给定的一组下标（i, j）找到对称矩阵中任一元素aij在一维数组Bk中的存储位置，即在在aij和和Bk之间找到一个对应关系之间找到一个对应关系。K = i ( i 1 ) 2+ j 1 当当 i = j j ( j 1 ) 2+ i 1 当当 i = j 142级偏软包过之数据结构三级课件5.3 三角矩阵的压缩存储 以主对角线划分，三角矩阵分为两种：上三角矩阵和下三角矩阵。所谓上三角矩阵，是指下三角（不包括主角线）中的元素均为常数c的n阶方阵。下三角矩阵正好相反，其主对角线上方均为常数c。在多数情况下，三角矩阵的常数c为0。对于任何一个n阶下三角矩阵都具有下述性质：当ij时，aij=c；同理，对于任何一个n阶上三角矩阵：当ij时，aij=c。143级偏软包过之数据结构三级课件5.3 三角矩阵的压缩存储三角矩阵采用压缩存储方式时，只存储矩阵的下三角元素或上三角元素。如果让矩阵中所有重复元素c共享一个存储单元，那么三角矩阵中n2个元素就可以压缩存储到一维数组Bn(n+1)/2中，其中重复元素c放在数组的最后一个单元中。若按“行优先顺序”存储下三角矩阵中的元素，则矩阵下三角元素的压缩存储情况如下图所示。 144级偏软包过之数据结构三级课件5.3 三角矩阵的压缩存储三角矩阵A中任一元素aij在一维数组Bk中的存储位置。上三角关系下三角关系K i*(2n-i+1)/2+j-I i jK i*(i+1)/2+j i = jn*(n+1)/2 i j145级偏软包过之数据结构三级课件5.3 对角矩阵的压缩存储 若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为n阶对角矩阵。其主对角线上下方各有b条次对角线，称b为矩阵半带宽，（2b+1）为矩阵的带宽。对于半带宽为b（0=b=(n-1)/2 ）的对角矩阵，其|i-j|e的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先顺序存放的。为了找到A中各列所有的非零元素，可对A的三元组表a-data的第二列从第一行起多次扫描所有的三元组表，按列号从小到大依次形成转置矩阵三元组表b-data中的所有元素。156级偏软包过之数据结构三级课件TSMatrix *transmat(TSMatrix *a)/* 普通转置运算 */ int an, bn; col; /* col指示a的列号，即b的行号 */ TSMatrix *b; /* 存放转置后的矩阵B */ b-m=a-n; b-n=a-m; /* 将行数和列数交换 */ b-t = a-t; /* 非零元素个数*/ if (b-t0) /* 若有非零元素，则转置 */ bn=1; for(col=1; coln; col+) /* 按a列序转置 */ for(an=1; ant; an+) /* 扫描三元组表 */ if(a-ean.j=col) b-ebn.i=a-ean.j; b-ebn.j=a-ean.i; b-ebn.v=a-ean.v; bn+; /* b-data结点序号加1 */ return(b); /* TRANSMAT */157级偏软包过之数据结构三级课件5.4 稀疏矩阵的压缩存储稀疏矩阵按稀疏矩阵按A的的行序行序转置算法转置算法基本思想：按照A的三元组表a-e的顺序进行转置，并且将转置后的三元组一次置入b-data中恰当的位置上。需要预先确定矩阵A中各列第一个非零元素在b-e中的正确位置。为了确定这些位置，在转置前应该先求出求出A中各中各列非零元素的个数列非零元素的个数，进而求得各列第一个非零元素在b-e中的起始位置。 158级偏软包过之数据结构三级课件5.4 稀疏矩阵的压缩存储稀疏矩阵按稀疏矩阵按A的的行序行序转置算法转置算法算法实现：设置两个一维数组num和cpot。数组numcol用于统计矩阵A中第col列的非零元素个数，数组cpotcol用于表示矩阵A第col列中第一个第一个非零元素在b-data中的恰当的存储位置。cpotcol值可按下列公式得到：159级偏软包过之数据结构三级课件5.4 稀疏矩阵的压缩存储稀疏矩阵按稀疏矩阵按A的的行序行序转置算法转置算法160级偏软包过之数据结构三级课件TSMatrix *fast_transmat(TSMatrix *a) int ano, bno; int col; TSMatrix *b; /* 存放转置后的矩阵 */ int numSMAX; /* num表示a中各列非零元素个数 */ int cpotSMAX; b-c=a-r; /* 将行数和列数交换 */ b-r=a-c; b-t=a-t; /* 将非零元素个数赋给矩阵B */ if(b-t0) /* 若有非零元素，则转置 */ for (col=1; colr; col+) numcol=0; for(an=1; ant; an+) col = a-ean.j; numcol=numcol+1; 161级偏软包过之数据结构三级课件 cpot1=1; for(col=2;colr;col+) cpotcol = cpotcol-1 + numcol-1; for(an=1;ant; an+) col =a-ean.j; bn=cpotcol; b-ebn.i=a-ean.j; b-ebn.j=a-ean.i; b-ebn.v=a-ean.v; cpotcol=cpotcol+1; /* FOR */ /* IF */ return(b); /* FAST_TRANSMAT */162级偏软包过之数据结构三级课件5.4 稀疏矩阵的压缩存储稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示rheaddheadclistmnnodet163级偏软包过之数据结构三级课件5.4 稀疏矩阵的压缩存储稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示164级偏软包过之数据结构三级课件数组习题165级偏软包过之数据结构三级课件