数据结构与算法--第12讲.pptVIP

一、稳定伴侣问题 设有n个男孩m1,m2,…,mn与n个女孩w1,w2,…, wn。 每一个男孩mi都依照他喜爱这n个女孩的程度列成一张表，最喜欢的女孩排在第1位，最不喜爱的女孩排在第n位；同样地，每个女孩wi也按照她喜爱n个男孩的程度列成一张表。 要求把男孩与女孩进行配对，使得：如果mp与wq在一对的话，那么满足如下条件： 对mp的喜爱表格中排在wq之前的女孩而言，她的伴侣在她的表格中一定排在mp之前。 对wq的喜爱表格中排在mp之前的男孩而言，他的伴侣在他的表格中一定排在wq之前。 不稳定情况 m 分析问题 第一步：初始化关系矩阵 Matrixint man(n, n), woman(n, n); // 矩阵类模板 templateclass ElemType class Matrix { protected: ElemType *elems; // 存储矩阵元素 int rows, cols; // 矩阵行数和列数 public： ElemType operator()(int i, int j); // 重载函数运算符！！！ 分析问题 第二步：将男孩入等待栈，准备依次配对； 分析问题 第三步：对女孩构建rank表。 如果woman(i, j)=w,则rank(i,w)=j 分析问题 第四步，开始配对。 分析问题 取栈顶元素4 分析问题 取栈顶元素3 分析问题 取栈顶元素2 分析问题 取栈顶元素1 分析问题 看下一个next[] 分析问题 重新看4的下一个 算法实现 while (!waiting.Empty()) { int boy, girl; waiting.Top(boy); // 取出等待婚约的男孩 girl = man(boy, next[boy]++); // 当前男孩boy中意的女孩 if (womanEngagement[girl] == FREE) { // 当前女孩girl还没有婚约 womanEngagement[girl] = boy; manEngagement[boy] = girl; // 配对 waiting.Pop(boy); // 男孩boy出栈 } else 算法实现 else if (rank(girl, boy) rank(girl, womanEngagement[girl])) {//女孩与男孩womanEngagement[girl]解除婚约,改与男孩boy配对 waiting.Pop(boy); waiting.Push(womanEngagement[girl]); // 男孩womanEngagement[girl]重回等待栈中 womanEngagement[girl] = boy; manEngagement[boy] = girl;// 配对 coutelse: boy girlendl; } } 二、广义表 General List 由于广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，因此在教材中和“数组”合为一章。 但广义表比数组更为复杂，它兼有“多层次”的特点，特别是它的存储表示和操作的实现和树的操作极为类似。 人工智能等领域的LISP语言使用的一种数据结构，是对线性表的一个推广。 二、广义表 General List 定义： n(?0)个表元素组成的有限序列 记作 GL = (a1, a2, a3, …, an) 说明： GL是表名,ai是表元素,它可以是表(称为子表),可以是数据元素(称为原子)。 n为表的长度。n=0的广义表为空表 例如： A = ( ) 空表 无表头，无表尾，表长为0； B = (x,y,z) 单元素表 表头为x，表尾为(y,z)，表长为3； C = (B,y,z) 非单元素表 表头为B，表尾为(y,z)，表长为3； D = (x,(y,z)) 非单元素表 表头为x，表尾为((y,z))，表长为2； E=( x,E ) 递归表 表头为x，表尾为(E)，表长为2。 广义表的深度 广义表的深度 表头和表尾 若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。 对非空广义表：称第一个元素为GL的表头，其余元素组成的表称为GL的表尾； B = (a,(b,c,d)) 表头：a 表尾 ((b,c,d)) 即 HEAD（B）=a, TAIL(B)=((b,c,d)), C = (e) 表头：e 表尾 ( ) D = (A,B,C,f )