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

数据结构,胡 杰Email: 2013-3-7,2,主要内容,算法及其描述基本概念和术语线性表栈和队列数组树图查找排序,3,什么是数据结构,解决一个具体问题的步骤：,从具体问题抽象出适当的数学模型,设计解此模型的算法,编写程序、测试,得到结果,梁架结构中应力：线性方程组预报人口增长：微分方程辅助医学诊断：贝叶斯模型,4,什么是数据结构,数值问题例1 已知：游泳池的长len和宽wide，求面积area 建模型：数学模型：线性方程组问题涉及的对象：游泳池的长len、宽wide、面积area；对象之间的关系：area = len wide,5,什么是数据结构,数值问题例：已知游泳池的长len和宽wide，求面积area 编程： main ( ) int len, wide ,area ; scanf (“%d %d%n”, &len, &wide); area = len*wide ; printf (“area=%d”, area); ,6,什么是数据结构,非数值问题在计算机上实现学生成绩系统的管理，必然要涉及以下三个问题：如何组织学生成绩表？采用何种存储方式将表中的数据及数据之间的关系存放到计算机的存储器中？在计算机上如何完成学生成绩系统的管理功能？,7,什么是数据结构,非数值问题例: 已知某级学生情况 , 要求分班按入学成绩排列顺序。,学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级 00201 杨润生 男 82/06/01 广州 561 00计算机200102 石磊 男 83/12/21 汕头 512 00计算机100202 李梅 女 83/02/23 阳江 532 00计算机200301 马耀先 男 82/07/12 广州 509 00计算机3,8,什么是数据结构,非数值问题例: 迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树”。,入口,出口,9,什么是数据结构,非数值问题例: 城市间交通网问题,出口,10,什么是数据结构,解决非数值计算问题的关键是要建立有效的数据结构来进行描述。分析问题中所用到的数据是如何组织的；研究数据之间的关系如何；数据和数据之间的关系怎么存储到计算机中；在这些数据上定义一个相应的运算。,11,1.1 数据结构的基本术语,数据：能被计算机识别、存储和处理的的符号的集合，是计算机操作对象的总称。 数值、字符 图形、图像声音、视频数据元素：数据的基本单位，亦称为结点、元素和记录等。在计算机程序中通常作为一个整体考虑和处理。（例如：一个学生记录）数据项：数据结构中讨论的最小单位，数据元素是数据项的集合。亦称为域、字段等。（例如：学生记录中的学号。）,12,1.1 数据结构的基本术语,数据结构：带结构的数据元素的集合。数据结构包括3部分内容：逻辑结构，指数据之间的相互关系。存储结构，指数据及其关系在计算机中的存储方式，或数据的物理结构。运算，指对数据进行检索、插入、删除、合并、排序、计算、转换、输入和输出等操作过程。Data_Structure = (D, R),13,1.2 数据的逻辑结构,数据元素之间的相互关系，被称为数据的逻辑结构（Logical Structure）。不同的关系构成不同的结构，通常有下列四类基本结构：集合、线性结构、树形结构 、图状结构,14,1.2 数据的逻辑结构,线性结构,数据元素之间的关系：一对一,15,1.2 数据的逻辑结构,树形结构例：家族的族谱，假设某家族有10个成员A，B，C，D，E，F，G， H，I， J，他们之间的血缘关系可以用如下图表示。,数据元素之间的关系：一对多,16,1.2 数据的逻辑结构,图/网结构例：城市之间的航线组成的数据结构,数据元素之间的关系：多对多,17,1.3 数据的存储结构,数据的存储结构是数据逻辑结构在计算机存储器中的表示（映像），又称物理结构。存储结构包括数据元素的表示和关系的表示。顺序链接索引散列,18,1.3 数据的存储结构,顺序存储结构将逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元里，即将所有数据元素相继存放在一个连续相邻的存储区里。用存储结点间的位置关系来表示结点之间的逻辑关系。顺序存储结构通常可以用C/C+语言的数组来描述。,19,1.3 数据的存储结构,顺序存储结构例：用顺序存储方式表示一周7天，数据结构为：DS（D, R）DSun, Mon, Tue, Wed, Thu, Fri, SatR = , , , , , ,20,1.3 数据的存储结构,链接存储结构存储每个结点信息的同时，需要增加一个指针来表示结点间的逻辑关系。不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。每个结点由两部分组成：数据域：存储结点本身的信息；指针域：存储该结点的后继（或前驱）结点的存储单元地址。,21,1.3 数据的存储结构,链接存储结构,22,1.3 数据的存储结构,索引存储方式索引存储方法是在存储结点信息的同时，建立一个附加的索引表。索引表中每一项称为一个索引项。索引项的一般形式是：（关键字，地址）,23,1.3 数据的存储结构,索引存储方式,（b）索引表,（a）文件数据区,24,1.3 数据的存储结构,散列方式基本思想：根据结点的关键字Key直接计算出该结点的存储地址。即以线性表中的每个结点的关键字Key为自变量，通过一个确定的函数关系f，计算出对应的函数值f(key)，然后把这个值解释为一块连续存储空间的存储地址，将结点存储到f(key)所指的存储单元中，使每个关键字和结构中一个的存储地址相对应。,25,1.3 数据的存储结构,散列方式例：已知一组待存储的关键字为（40，68，6，20，49，24，53，16，1，45，14，88），散列地址为T0.12。假设用除留取余法构造的散列函数为：H(key) = f(key) = key%13。,26,1.4 算法和算法分析,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法特性：有穷性确定性可行性输入，零个或多个输入。输出，一个或多个输出。,程序并不需要满足有穷性（操作系统）,27,1.4 算法和算法分析,算法描述方式流程图自然语言伪代码程序设计语言描述算法的唯一要求：精确地描述计算过程。,C/C+,28,1.4 算法和算法分析,算法设计要求正确性健壮性 （如对非法数据的处理和反应）可读性简单性 （采用的数据结构和方法的简单程度）时间效率高存储空间少,29,1.4 算法和算法分析,算法时间复杂度语句频度，算法中所有语句的执行次数之和。一个算法的语句频度是其求解问题规模n的函数，记为T(n)。如果有某个函数F(n)，使得当问题规模n趋于无穷大时，有：则将O(F(n)称作算法的时间复杂度。,30,1.4 算法和算法分析,算法时间复杂度例：下面算法为求n个自然数的和S=1+2+3+n。请给出该算法的语句频度。 sum(int n) int i, s=0; for (i=1;i=n;i+) / n+1次 s=s+i; / n次 printf(“%dn”, s); / 1次 /*sum*/,T(n) = (n+1)+n+1=2n+2,算法复杂度为O(F(n) = O(n),31,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) ; ,32,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 */,43,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 */,44,2.3 顺序表的基本运算,删除运算将线性表中第i个（或符合要求的）数据元素删除，使长度为n的线性表： ( a1, , ai1 , ai , ai+1 , an ) 变成为长度为n-1的线性表：( a1, , ai1, ai+1, an ),45,2.3 顺序表的基本运算,删除运算过程： 检查给定结点的删除位置是否正确，若删除位置有错，则显示出错信息，退出程序运行； 把表中第 i+1n 个结点之间的所有结点依次向前移动一个位置； 将线性表的长度减1。,46,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; jdata=-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*/,63,2.5 链表的基本运算,单链表的建立运算用尾插法建立带头结点的单链表的过程： 调用malloc函数，生成一个头结点head； 调用malloc函数，开辟新的存储单元p； 给新结点的数据域赋值，将新结点的指针域设置为空； 将新结点链接到链表的尾结点rear之后，修改表尾指针rear； 重复上述步骤，直至输入结束标志0为止。,64,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 */,65,2.5 链表的基本运算,单链表的查找运算由于逻辑相邻的结点并没有存储在物理相邻的单元中，所以链表的遍历或查找运算，不能像顺序表那样随机访问任意一个结点，而只能从链表的头指针head出发，顺着链域next逐个结点往下搜索，直到找到所需要的结点为止或者当链表为空时结束查找。,66,2.5 链表的基本运算,按值查找运算在带头结点的单链表中查找是否存在给定值为key的结点。基本思想：从链表的头结点开始，依次将链表中结点的数据域与key进行比较，若找到给定值key，则查找成功，函数返回该结点的位置；若没有找到给定值key，则查找失败，函数返回NULL。,67,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 */,68,2.5 链表的基本运算,按序号查找运算在带头结点表长为n的单链表中，查找第i个结点，仅当1in时，i值是合法的。基本思想：从表的头结点开始查找，用指针p指向当前结点，用 j 作为计数器累计当前扫描过的结点数。j的初值为0，指向表头结点，当p扫描下一个结点时，计数器j相应地加1。当j = i时，指针p所指的结点就是要找的第i个结点。,69,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 */,70,2.5 链表的基本运算,单链表的插入假设指针p指向单链表中某个结点，指针s指向值为x的新待插结点。若将新结点s插入结点p之后，则称为后插；若将新结点s插到结点p之前，则称为前插。后插运算,y,x,p,head,s,71,2.5 链表的基本运算,单链表的插入后插运算,要求：插入“58”，保持有序。,72,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 */,73,2.5 链表的基本运算,单链表的插入前插运算,74,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 */,75,2.5 链表的基本运算,单链表的删除在链表中删除数据值为x的结点，并由系统收回其占用的存储空间，过程： 假设有两个指针p和q，p指向要删除的结点，q指向p的前驱结点； 从链表head的头结点开始，依次向后进行搜索，当q-next=p 并且p-data=x时，则待删除结点p的前驱结点q被找到； 修改p的前驱结点q的指针域，将q的后继指向被删除结点p的后继结点； 删除p结点并释放该结点所占用的存储空间,76,2.5 链表的基本运算,单链表的删除,见教材p69算法2-11,77,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 */,78,2.5 链表的基本运算,双向链表的插入前插运算,79,2.5 链表的基本运算,双向链表的插入后插运算,80,2.5 链表的基本运算,双向链表的删除,81,2.5 链表的基本运算,循环链表的运算循环链表的优点：从链表中任何一个结点出发都可以遍历表中所有的结点。循环链表的运算和单链表的主要差别：当链表遍历时，其终止条件不同： 单链表中，用指针域是否为空作为判断条件； 循环链表中，以结点的指针域是否等于表头结点或开始遍历的结点作为结束条件。,82,单链表上查找、插入和删除运算的时间分析,设Pi是单链表上查找第i个元素的概率，在长度为n的带头结点的单链表中可能进行查找的位置为i=0, 1, 2, , n。在等概率情况下P1=P2=Pi=1/(n+1)。若查找成功时，则单链表中查找任意位置上数据元素的平均比较次数为：单链表上查找、插入、删除算法的平均时间复杂度为O(n)。,83,顺序表和链表的比较,空间性能的比较存储密度：存储结点中数据域占用的存储量与存储结点所占用的存储量之比称为存储密度。存储密度越大，则存储空间的利用率就越高。顺序表的存储密度是高于链表的存储密度。但是，顺序表要求事先估计容量，这是比较困难的。,84,顺序表和链表的比较,时间性能的比较当线性表的主要操作是查找运算时，最好采用顺序存储结构。对于需要频繁地进行插入和删除操作的线性表，最好采用链接存储结构。若链表的插入和删除操作主要发生在表的首、尾两端，采用尾指针表示的单循环链表则是最好的选择。,85,线性表,习题,86,3.1 栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表。,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,87,3.1 栈,栈的特点后进先出,88,3.2 栈的顺序存储结构,用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指示栈顶元素在顺序栈中的位置。顺序栈可以用一个一维数组和一个记录栈顶位置的整型变量来实现。顺序栈的三种形态：空栈、满栈和非满非空栈（通过栈顶指针top体现）。栈底可以设在数组的任意位置，栈顶随着进栈和退栈操作不断变化。,89,3.2 栈的顺序存储结构,定义 #define MAX 100; typedef struct seqstack datatype eMAX; int top; seqstack; seqstack *S；,emax,top,s,90,3.2 栈的顺序存储结构,例如，假设顺序栈S为(A, B, C, D, E, F)，栈中最多能存储6个元素。请给出顺序栈S进栈和退栈时，其栈顶指针top和栈的变化情况。,91,3.3 栈的链式存储结构,以某种形式的链表作为栈的存储结构，其组织形式与单链表类似。设一个栈S为(A, B, C)，链栈存储结构如下：,92,3.3 栈的链接存储结构,依次插入两个元素D, E后：从栈中删除栈顶元素E：当链栈中所有的元素全部出栈后，top=NULL。,93,3.4 顺序栈的基本运算,1顺序栈的初始化 void InitStack(seqstack *S) S-top=-1; /* 将顺序栈设置为空栈 */ ,94,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); /* 插入成功，返回新栈顶指针 */ ,96,3.4 顺序栈的基本运算,4顺序栈的出栈 datatype Pop(seqstack *S) datatype x; /* 保存栈顶元素数据值 */ if (Empty(S) /* 检查顺序栈是否为空 */ printf(“下溢错误! ”)；return(0); /* 删除失败 */ else /* 若顺序栈非空删除之*/ x = S-eS-top; /* 暂存栈顶元素 */ S-top-; return (x); ,97,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); ,98,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); ,99,3.5 共享栈,在同时建立两个栈的情况下，可将这两个栈的栈底分别设置在数组的两端。除非空间总容量耗尽，否则