2.3.3静态链表-与动态链表的差异 2.3.3静态链表-动态分配与释放的模拟 与动态链表使用上的差异 ,动态分配与释放的模拟 ,链表的结点是数组中的一个分量 ,思想：将未使用的分量用游标c山链成一个备用 ,数组分量中的cur代替动态链表中的指针城，用 使：播入时，取各用烧中的第一个结点作为插入 来指示直接后继或直接前驱结点在数组中的相对 的新结点：删除时将从链表中删除下来的结点链 接到备用链上 位置 ,数组的第0个分量可以视为（备用链的）头结点 ,初始化链表（算法2.14，P33) space[O].cur为备用鰱的头指针，cur为0表示空推针 ,以(O或)负数代表空指针NULL void InitSpace_SL(SLinkList &space){ 。以整型游标i代替动态指针p,以i=S[).cur代 for(i=0;i<MAXSIZE-1;i++) 替p=p->next取下一个元素的位置 space[i].cur=i+1; space[MAXSIZE-1].cur 0; 4973 5s07B 2.3.3静态链表-动态分配与释放的模拟 2.3.4动态链表与静态链表 。动态分配与释放的模拟 ·例2-1 。摸拟动态分配（算法2.15，P33) ·顺序表的实现：基本操作的简单替换 int Malloc_SL(SLinkList &space) i =space[o].cur; ·动态链表 if space[o].cur!=0 space[o].cur space[i].cur; ·无须转意求La、Lb的长度 return i; -原目的是为了控制线性表的边界 ,无须每次调用GetElem_L0 ,横拟动态释放（算法2.16，P33) 它可以和外层的循环合二为 void Free_SL(SLinkList &space,int k ,无须每次调用ListInsert L0 space[k].cur space[o].cur;space[o].cur=k; 可以引入指针变量记录La的尾结点的位置 可以利用Lb的原有轴点空间 -前提：b本贵不再被使用 51/73 假设蛙表均有头结点且是非捕环的 图 2.3.4动态链表与静态链表 2.3.4动态链表与静态链表 动态链表：算法需要重新整合】 使pa指向La的 静春表：有洁德来类化也精新盘自以 void Union_L(LinkList &La,LinkList &LbX{ for pa La;pa->next !NULL;pa=pa->next); 康次处b中8{BC8era=p3 c(pa)cu)i 依次处理Lb中 foPb5p-net1awU匹X 的是个储点 e=po->nex 在La中查找e 在La中童找e equai(spacelqa)data,)i if (gaNULL) qal.cur); 未查到，入 i证(q 020 La的属椰 pa->next pb->next; erpal.cur=space[pb]-cur pa pa->next; pb->next pb->next->next; ace[space[pb].cur].cur; pa->next NULL; space[paj.cur =0; Yelse 查到，取山的 }else pb=pb->next; }//end of for 下一个点 pb space[pb].cur; >//end of for 53/7万 5W万49/73 2.3.3 静态链表-与动态链表的差异 „ 与动态链表使用上的差异 „ 链表的结点是数组中的一个分量 „ 数组分量中的cur代替动态链表中的指针域，用 来指示直接后继或直接前驱结点在数组中的相对 位置 „ 数组的第0个分量可以视为(备用链的)头结点 „ 以(0或)负数代表空指针NULL „ 以整型游标i代替动态指针p，以i = S[i].cur代 替p = p->next取下一个元素的位置 50/73 2.3.3 静态链表-动态分配与释放的模拟 „ 动态分配与释放的模拟 „ 思想：将未使用的分量用游标cur链成一个备用 链；插入时，取备用链中的第一个结点作为插入 的新结点；删除时将从链表中删除下来的结点链 接到备用链上 „ 初始化链表(算法2.14, P33) space[0].cur为备用链的头指针，cur为0表示空指针 void InitSpace_SL(SLinkList &space){ for( i=0 ; i < MAXSIZE-1; i++) space[i].cur=i+1; space[MAXSIZE-1].cur = 0; } 51/73 2.3.3 静态链表-动态分配与释放的模拟 „ 动态分配与释放的模拟 „ 模拟动态分配(算法2.15, P33) int Malloc_SL(SLinkList &space){ i = space[0].cur; if ( space[0].cur!=0 ) space[0].cur = space[i].cur; return i; } „ 模拟动态释放(算法2.16, P33) void Free_SL(SLinkList &space, int k){ space[k].cur = space[0].cur; space[0].cur = k; } 52/73 2.3.4 动态链表与静态链表 „ 例2-1 „ 顺序表的实现：基本操作的简单替换 „ 动态链表 „ 无须特意求La、Lb的长度 ——原目的是为了控制线性表的边界 „ 无须每次调用GetElem_L() ——它可以和外层的循环合二为一 „ 无须每次调用ListInsert_L() ——可以引入指针变量记录La的尾结点的位置 „ 可以利用Lb的原有结点空间 ——前提：Lb本身不再被使用 „ 假设链表均有头结点，且是非循环的 53/73 2.3.4 动态链表与静态链表 „ 动态链表：算法需要重新整合！ void Union_L( LinkList &La, LinkList &Lb){ for ( pa = La; pa->next != NULL; pa=pa->next); for ( pb = Lb; pb->next !=NULL; ){ e = pb->next->data; for(qa = La->next; qa != NULL && !equal(qa->data, e) ; qa=qa->next); if (qa == NULL) { pa->next = pb->next; pa = pa->next; pb->next = pb->next->next; pa->next = NULL; } else pb = pb->next; }//end of for } 查到，取Lb的 下一个结点 使pa指向La的 最后一个结点 依次处理Lb中 的每一个结点 在La中查找e 未查到，插入 到La的尾部 54/73 2.3.4 动态链表与静态链表 „ 静态链表：和动态链表类似，也需要重新整合！ void Union_SL( SLinkList &space, int &sla, int &slb){ for ( pa = sla; space[pa].cur != 0; pa=space[pa].cur); for ( pb = slb; space[pb].cur!=0; ){ e = space[space[pb].cur]].data; for(qa = space[sla].cur; qa != 0 && !equal(space[qa].data, e) ; qa=space[qa].cur); if (qa == 0) { space[pa].cur = space[pb].cur; pa = space[pa].cur; space[pb].cur = space[space[pb].cur].cur; space[pa].cur = 0; } else pb = space[pb].cur ; }//end of for } 查到，取Lb的 下一个结点 使pa指向La的 最后一个结点 依次处理Lb中 的每一个结点 在La中查找e 未查到，插入 到La的尾部