2022年2022年链表的基本操作 .pdf

《2022年2022年链表的基本操作 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年链表的基本操作 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C+ 链表基本操作#include #include struct Node int num ; Node *next ; ; Node* Create() /链表创建 int n= 0 ; Node *p1,*p2,*head; p1=p2=new Node; cinp1-num; head=NULL; while (p1-num!=0 ) if (n=1 ) head=p1; elsep2-next=p1; p2=p1; p1= new Node; cinp1-num; n+; p2-next=NULL; return head; 名师资料总结 - - -精品资料欢迎下载 - - - -

2、- - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - int ListLength(Node L) /链表的计数 Node p=L; int count=0; while(p-next) count+; p=p-next; return count; int Search(Node &L , int value) /链表的查找 Node p=L; int index=0; while(p) if(p-num= value) return index; p=p-next; index+; re

3、turn 0; void Print(Node *head) /输出链表 Node* p=head; while (p) coutnumnext; coutnext; delete temp; Node *ReverseList(Node *head) /链表逆序（循环方法） Node *p,*q,*r; p=head; /一开始 p 指向第一个节点q=p-next; /q指向第二个节点while (q!=NULL) /如果没到链尾 /以第一次循环为例r=q-next; /r暂时存储第三个节点q-next=p; /没执行此句前，q-next指向第三个节点/执行之后， q-next指向第一个节点

4、p p=q; /之后 p 指向第二个节点q=r; /q指向第三个节点/即.p=q=r.变为 .p=qnext=NULL; /最后原来的链头变为链尾，把它指向NULL 。head=p; /原来的链尾变成链头return head; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - Node *ReverseList2(Node *head)/链表逆序（递归方法） if (!head) return NULL; Node *temp

5、= ReverseList2 (head-next); if (!temp) return head; head-next-next = head; head-next = NULL; return temp; 递归时 ,head可以分别用head ，head1,head2 .headn-1, headn来表示总共n+1个节点temp = ReverseList2( head-next ); 此句的递归一直将参数传进来的。Node* head 递归到headn 然后判断下列语句：else if( !headn-next ) return headn; 将返回值传给temp,此时 temp指向链

6、尾,由于在此次返回,故此次没有执行最后的else的那部分的语句,返回上一级即是headn-1 那一级 ,继续执行下面的headn-1-next-next = headn-1; headn-1-next = NULL; /此两句将最后两个逆序连接, return temp; /之后返回 temp比上一层的temp即是执行 temp = ReverseList2( head-next )赋值 ,因为递归的口都是在这里的,如果说好理解点也可以将temp来编号同理在返回 temp后,继续执行headn-2-next-next = headn-2; headn-2-next = NULL; return

7、 temp; . 一直到head时 即是原链表的第一个节点,在对其 head-next = NULL后,此时以temp 所指向的节点为链头的逆序链表就形成了. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - /已知两个链表head1 和 head2 各自有序，请把它们合并成一个链表依然有序。（循环方法）/(保留所有结点，即便大小相同）Node *Merge(Node *head1 , Node *head2) if ( head

8、1 = NULL) return head2 ; if ( head2 = NULL) return head1 ; if ( head1-num num ) head = head1 ; head1= head1-next; else head = head2 ; head2 = head2-next ; Node *temp = head ; while ( head1 != NULL & head2 != NULL) if ( head1-num num ) temp-next = head1 ; head1 = head1-next ; temp =temp-next; else te

9、mp-next = head2; head2 = head2-next ; temp =temp-next; if (head1 = NULL) temp-next = head2; if (head2 = NULL) temp-next = head1; return head; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - /已知两个链表head1 和 head2 各自有序，请把它们合并成一个链表依然有序。（递归方法）No

10、de *MergeRecursive(Node *head1 , Node *head2) if ( head1 = NULL ) return head2 ; if ( head2 = NULL) return head1 ; Node *head = NULL ; if ( head1-num num ) head = head1 ; head-next = MergeRecursive(head1-next,head2); else head = head2 ; head-next = MergeRecursive(head1,head2-next); return head ; 从递归

11、函数的定义不难看出，这个函数定义中递归调用时形参发生改变，即是当前节点的下一个节点，每一次递归都按照这个规律逐次遍历两个有序链表的每一个节点，判断大小后使head指向数据域较小的节点，由堆栈空间的思想可知递归到最后指向NULL时才返回两个链表的某一个头节点，而此时head-next=head2，head=head1链表的最后一个节点，该语句就使得这样一个指向关系确立起来。以上均通过理想的有序链表，即链表 1 的任何一个数据值都小于链表2 来做分析， 其他的情况讨论方式类似。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心

12、整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - Node* Delete(Node* head , int num) /删除节点 if (head=NULL) coutList is Nullnum!=num & p1-next) p2=p1; p1=p1-next; if (p1-num=num) if (p1=head) head=p1-next; elsep2-next=p1-next; elsecoutDo not Find The Num numnum=num; if (head=NULL) head=p0; p0-next=NULL; return head; while (p1-numnum & p1-next) p2=p1; p1=p1-next; if (p1-num=p0-num) if (p1=head) head=p0; else p2-next=p0; p0-next=p1; else p1-next=p0; p0-next=NULL; return head; void main() 省略不写 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -