和动态链表一样，以上操作为线性静态单链表的最基本的操作，其他操作可以是上述操作的组合。 例如要实现“判断结点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; }

评论