和动态链表一样，以上操作为线性静态单链表的最基本的操作，其他操作可以是上述操作的组合。
例如要实现“判断结点P是否为链表L的尾结点”操作，函数如下： int IsLLast(SLink L, Position P) { if(LContaiP(L, P) return IsLast(P); return 0; } 如果你仔细的阅读这些代码，你会发现动态链表和静态链表的基本操作的实现算法很相似，游标实现的接口和指针实现是一样的。静态链表可以代替动态链表实现，实际上在程序的其余部分不需要变化，而且速度更快。 同样的让我们用一个实际的例子说明。已知集合A={1，2，3，4，5}，B={3，4，5，6，7，8，9，11}，求集合A和B的交集的非，即（A-B）并（B-A）。 算法思路是先把集合A和B分别存入两个单向链表LA和LB中，以LB的结点P为研究对象，遍历LA，看是否有与其同值的结点，若有删除与结点P相同的结点，否则把结点P插入链表LA。最后得到的LA就是集合A和B的交集的非。 具体的实现如下所示，因为函数部分已经包含在“线性表的静态单链表基本操作的算法实现“中，所以不做重复，只把其他的部分列出来。程序经过测试，可以运行。 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #define MAXSIZE 100//链表的最大长度 typedef int Position; typedef int SLink; typedef int ElemType; typedef struct Node{ ElemType data; Position next; } SLinkList[MAXSIZE]; SLink CreateList(ElemType a[], ElemType len);//用来构造一个链表 。。。//其他函数声明 int main(void) { SLink LA, LB; Position P, Pre, S; ElemType X, A[5]={1,2,3,4,5}, B[8]={3,4,5,6,7,8,9,1}; InitSpace_SL(Space);//构造一个“模拟空间分配站”,为全局变量 //把集合A和B分别存入两个单向链表LA和LB中 LA = CreateList(A, 5); LB = CreateList(B, 8); //以LB的结点P为研究对象，遍历LA，看是否有与其同值的结点，若有删除与结点P相同的结点，否则把结点P插入链表LA。 P = Space[LB].next; while(P) { X = Space[P].data; //把结点P的值赋给X Pre = FindPrefious(X, LA); //判断LA中是否有与P同值的结点 ，返回同值结点的前驱 if(Pre) //若有，删除结点PA SListDelete(Pre); else //否则 { S = NewSLNode(X); //构造一个数据域为X的新结点，即复制结点P到S SListInsert(LA, S); //把结点S插入链表LA } P = Space[P].next; //继续分析链表中的下一个结点 } //输出集合A和B的交集的非 Pre = LA; printf("集合A和B的交集的非:\n"); if(!Space[Pre].next) printf("交集的非为空集!"); else //输出链表LA的所有结点的值 while(Space[Pre].next) { X = Space[Space[Pre].next].data; printf("%d ", X); Pre = Space[Pre].next; } system("pause"); return 0; } SLink CreateList(ElemType a[], ElemType len)//用来构造一个链表 { SLink L, S; int i; L = InitList(); //构造一个空的线性表 for(i=0; i<len; i++) { S = NewSLNode(a[i]); //构造一个数据域为a[i]的新结点 SListInsert(L, S); //把新结点S插到头结点后面。 } return L; } 如果你用静态链表去做“求集合A和B的交集”的题目，你会发现，它的主函数部分和用动态链表做几乎一样。 提问：如果要同时求集合A和B的交集以及交集的非 ，又该怎么办呢？ 提示：算法思路是先把集合A和B分别存入两个单向链表LA和LB中，以LB的结点P为研究对象，遍历LA，看是否有与其同值的结点，若有删除与结点P相同的结点，否则把结点P插入链表LA；还要根据情况判断是否执行删除结点P的指令，以便得到A和B的交集。最后得到的LA就是集合A和B的交集的非；而LB是集合A和B的交集。 主函数部分： int main(void) { SLink LA, LB; Position PreA, PreB, S; ElemType X, A[5]={1,2,3,4,5}, B[8]={3,4,5,6,7,8,9,11}; InitSpace_SL(Space);//构造一个“模拟空间分配站”,为全局变量 //把集合A和B分别存入两个单向链表LA和LB中 LA = CreateList(A, 5); LB = CreateList(B, 8); //以LB的结点P为研究对象，遍历LA，看是否有与其同值的结点，若有删除与结点P相同的结点，否则把结点P插入链表LA。 //还要根据情况判断是否执行删除结点P的指令 PreB = LB; //PreB表示结点P的前驱，在所有的操作中，我们都不直接操作被处理的结点，而是操作其前驱 while(Space[PreB].next) { X = Space[Space[PreB].next].data; //把结点PB的值赋给X PreA = FindPrefious(X, LA); //判断LA中是否有与PB同值的结点 ，返回同值结点的前驱 if(PreA) //若有，删除结点PA，继续分析链表中的下一个结点 { SListDelete(PreA); PreB = Space[PreB].next; } else //否则 { S = NewSLNode(X); //构造一个数据域为X的新结点，即复制结点PB到S SListInsert(LA, S);//把结点S插入链表LA SListDelete(PreB); //删除链表LB的结点PB } } //输出集合A和B的交集的非 PreA = LA; printf("集合A和B的交集的非:\n"); if(!Space[PreA].next) printf("交集的非为空集!"); else while(Space[PreA].next) { X = Space[Space[PreA].next].data; printf("%d ", X); PreA = Space[PreA].next; } //输出集合A和B的交集 PreB = LB; printf("\n集合A和B的交集:\n"); if(!Space[PreB].next) printf("交集为空集!"); else while(Space[PreB].next) { X = Space[Space[PreB].next].data; printf("%d ", X); PreB = Space[PreB].next; } system("pause"); return 0; }
评论