数据结构chapter 10 选讲内容

《数据结构chapter 10 选讲内容》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、10-Jun-211补充内容10-Jun-212静态链表某些高级语言中可能不支持指针操作，在这种情况下可以用数组来实现链表结构，这种链表称为静态链表静态链表中各个节点均是数组的元素，它的定义如下：#defineMAXSIZE1000typedefstruct{ElemTypedata;intcur;}component,SLinkList[MAXSIZE];在这种结构中，除了一个数据域之外，还有一个游标域，它用来代替指针表示下一个节点在数组中的位置在静态链表中插入和删除元素时只需要游标的值而不需要移动元素1

2、0-Jun-213静态链表示例假设线性表为{ZHAO,QIAN,SUN,LI,ZHOU}则用静态链表表示为：删除元素SUN之后的结构为：ZHAO2QIAN3SUN4LI5ZHOU0101234567下标数组内容ZHAO2QIAN4LI5ZHOU0101234567下标数组内容10-Jun-214静态链表的查找算法intLocateElem_SL(SLinkListS,ElemTypee){//在静态链表中查找第1个值为e的元素//若找到则返回其位置，否则返回0i=S[0].cur;while(!i&&S[i

3、].data!=e)i=S[i].cur;returni;}10-Jun-215静态链表的空间分配与回收由于静态链表是用数组来实现的，因此在插入元素时候，需要从数组的空余空间中找出一个单元给新插入的元素使用当删除元素后，该元素所占用的空间需要进行回收，以便该空间能被重新使用为此可以采用下面的方法：初始时，将数组所有空余空间组成一个链式结构，头节点的cur域指向第一个空余的空间当插入新元素的时候，将头节点cur域指向的空间分给新插入的元素使用，同时修改cur指向下一个空余空间当删除一个元素时候，将该空间的插入

4、空余空间链表的头部10-Jun-216数组空间初始化voidInitSpace_SL(SLinkList&space){for(i=0;i

5、e[0].cur)space[0].cur=space[i].cur;returni;}ZHAO2QIAN34503012345下标数组内容i=3ZHAO2QIAN34504012345下标数组内容10-Jun-218回收空间voidFree_SL(SLinkList&space,intk){//将下标为k的空闲节点回收到备用链表中space[k].cur=space[0].cur;space[0].cur=k;}ZHAO2QIAN3SUN4LI005012345下标数组内容k=353ZHAO2QIAN3S

6、UNLI00012345下标数组内容5410-Jun-219删除节点算法voidDelete_SL(SLinkList&space,ElemTypee){//删除值为e.data的节点,假定S为头节点p=S;k=space[p].cur;while(k!=0&&space[k].data!=e.data){p=k;k=space[k].cur;}space[p].cur=space[k].cur;Free_SL(space,k);}ZHAO3QIAN4SUN00250S2345e=QIAN534ZHAO3Q

7、IAN4SUN00250Spk4510-Jun-2110在表尾插入节点算法voidInsert_SL(SLinkList&space,ElemTypee){//插入值为e.data的节点,假定r尾节点位置，插入后尾节点位置不变i=Malloc_SL(space);space[i].data=e.data;space[i].cur=space[r].cur;space[r].cur=i;}ZHAO3QIAN4SUN00250S23r5e50ZHAO3QIAN4SUN00200Spkrie.data10-Jun

8、-2111用静态链表实现(A-B)U(B-A)由终端输入元素先建立集合A的静态链表S，然后在输入集合B的元素的同时查找S表，如果存在和B相同的元素，则从S表中删除它，否则将该元素插入S表voiddifference(SLinkList&space,int&s){InitSpace_SL(space);S=Malloc_SL(space);//S为头节点r=S;scanf(“%d,%d”,&m,&n);for(j=