C语言编程技巧分析 教学课件 作者 kj第8章 结构体共用体和枚举类型以及链表编程技巧分析.ppt

8.3.3关于链表知识编程技巧分析 例8.10 分析： （1）要删除特定值结点，需要先遍历单链表，找到待删除的位置。 （2）删除指针变量p指向的结点，首先需要先得到p指向的结点的前面一个结点。因此，需要用指针变量q指向p所指向的结点的前面一个结点。 （3）删除结点不仅要修改指针的指向，还要用free函数释放被删除结点所占据的内存。 8.3结构体、共用体和枚举类型以及链表编程技巧分析 8.3结构体、共用体和枚举类型以及链表编程技巧分析 8.3.3关于链表知识编程技巧分析 例 8.11 对于单向链表，设计一个函数，从尾到头反过来输出每个结点的值，要求不破坏单链表。 程序如下： void print_node(struct node *head) {if (head == NULL) return ; else {print_node(head-next); printf(%d , head-data); } } 分析： （1） 如果允许破坏此单向链表，则可以先把此单向链表倒置，再依次输出所有结点。这种方法简单明了，输出每个结点容易实现。 （2） 本程序用递归程序实现，利用递归算法可以使得输出倒序。 8.3结构体、共用体和枚举类型以及链表编程技巧分析 8.3.3关于链表知识编程技巧分析 （3） 用上述的递归程序需要多次的函数调用，效率低下，可以考虑直接用堆栈的方法实现。先顺序依次访问单向链表，把读到的数据压入到堆栈中，全部读完后再从堆栈中弹出就可以反过来输出每个结点的值了。考虑到压栈、出栈的开销，可以用一个数组代替堆栈。 程序如下： struct node {int data; struct node *next;}; void print_node(struct node *head) {struct node *p=head-next; /*head指向的是头结点。p指向第一个元素。*/ int stack[100]; /*模拟堆栈，假定结点元素类型为整型，不超过100个结点*/ int i=0; while(p!=NULL) {stack[++i]=p-data; p=p-next; } while(i0) printf(“%d,”,stack[i--]); } 8.3结构体、共用体和枚举类型以及链表编程技巧分析 8.3.3关于链表知识编程技巧分析 例8.12 编写函数，将两个有序的单向链表合并，要求在原有的结点基础上修改指针的指向，不产生新的结点。程序如下： struct Node { int num; struct Node *next ; }; struct Node *MergeList(struct Node *head1,struct Node *head2) /*按升序合并*/ {struct Node *head,*temp; if(head1==NULL) return head2; if(head2==NULL) return head1; if(head1-num=head2-num) {head=head1; head1=head1-next;} else {head=head2; head2=head2-next;} temp=head; 8.3结构体、共用体和枚举类型以及链表编程技巧分析 8.3.3关于链表知识编程技巧分析 while ( head1 != NULL head2 != NULL) {if ( head1-num = head2-num ) {temp-next = head1 ; head1 = head1-next ; temp =temp-next; } else {temp-next = head2; head2 = head2-next ; temp =temp-next; } } if (head1 == NULL) temp-next = head2; if (head2 == NULL) temp-next = head1; return head; } 8.3结构体、共用体和枚举类型以及链表编程技巧分析 8.3.3关于链表知识编程技巧分析 分析：程序的算法如下： （1）设置指针head1指向单向链表1，指针head2指向单向链表2，指针head指向合并后的单向链表的表头，指