以上操作为线性单链表的最基本的操作，其他操作可以是上述操作的组合。如，执行“在线性表L中寻找值为X的结点，并删除之”操作时，可先执行LNode FindPrefious(ElemType X, LinkList L)，再执行void ListDelete(LNode Pre)。 又如，执行“把一个值为X的新结点插入结点P之前”，可先执行LNode FindPrefious(ElemType X, LinkList L)，再执行LinkList NewLNode((ElemType X)，最后执行void ListInsert(LNode Pre, LNode S)。
我特意向大家推荐这种”坚持使用头结点“和“锁定前驱结点”的设计方法，这正是我和一般书本上有着不同理解的地方。有些书上的例程有时设置一个头结点，还有些根本就不使用头结点，也许是他们认为头结点占地方罢，但我认为为了更方便的编程实现我们的意图和更好的编程风格---主要指代码清晰易读，我再一次吐血推荐我的设计方法。因为这种设计方法就像一把万能钥匙---也许有些夸张了，呵呵！一般书上的例程在删除或插入结点时，要分别讨论链表头，链表中和链表尾三种不同的情况，采取不同的操作；而我上面所列的”删除“和”插入“操作可以全面搞定对链表中任意位置的结点（头结点除外）插入和删除功能。（除了”把新结点插入到链表尾“，但这可以组合执行LNode IsLast(LinkList L)和void ListInsert(LNode Pre, LNode S)）。 举一个实际的例子。已知集合A={1，2，3，4，5}，B={3，4，5，6，7，8，9，11}，求集合A和B的交集。 算法思路是先把集合A和B分别存入两个单向链表LA和LB中，以LA的结点P为研究对象，遍历LB，看是否有与其同值的结点，根据情况判断是否执行删除结点P的指令。最后得到的LA就是集合A和B的交集。 具体的实现如下所示，因为函数部分已经包含在“线性表的单链表基本操作的算法实现“中，所以不做重复，只把其他的部分列出来。程序经过测试，可以运行。 #include #include #include typedef int ElemType; typedef struct Node{ ElemType data; struct Node *next; } *LNode, *LinkList; LinkList CreateList(ElemType a[], ElemType len);//用来构造一个链表 。。。//其他函数声明 int main(void) { LNode LA, LB, Pre,Flag; ElemType X, A[5]={1,2,3,4,5}, B[8]={3,4,5,6,7,8,9,11}; //把集合A和B分别存入两个单向链表LA和LB中 LA = CreateList(A, 5); LB = CreateList(B, 8); //以LA的结点P为研究对象，遍历LB，看是否有与其同值的结点，根据情况判断是否执行删除结点P的指令 Pre = LA; while(Pre->next) { X = Pre->next->data; Flag = FindPrefious(X, LB); if(!Flag) ListDelete(Pre); else Pre = Pre->next; } //输出集合A和B的交集 Pre = LA; printf("集合A和B的交集:\n"); if(!Pre->next) printf("交集为空集!"); else while(Pre->next) { X = Pre->next->data; printf("%2d", X); Pre = Pre->next; } system("pause"); return 0; } LinkList CreateList(ElemType a[], ElemType len)//用来构造一个链表 { LNode L, S; ElemType i; L = InitList(); //构造一个空的线性表 for(i=0; i { S = NewLNode(a[i]); //构造一个数据域为a[i]的新结点 ListInsert(L, S); //把新结点S插到头结点后面。 } return L; }
评论