C++链表应用
#include
#include
struct Node {
int num ; Node *next ; };
Node* Create() // 链表创建 { int n=0;
Node *p1,*p2,*head; p1=p2=new Node; cin>>p1->num; head=NULL;
while (p1->num!=0) {
if (n==1) {
head=p1; } else
p2->next=p1; p2=p1;
p1=new Node; cin>>p1->num; n++; }
p2->next=NULL;
return head; }
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++; }
return 0; }
void Print(Node *head) // 输出链表 {
Node* p=head; while (p) {
cout
void Destruct(Node *head) // 清空链表 {
Node *current = head, *temp = NULL; while (current) {
temp = current;
current = current ->next; 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 指向第一个节点 p p=q; // 之后 p 指向第二个节点 q=r; //q 指向第三个节点
// 即 ...p=>q=>r... 变为 ...p<=q<=r... }
head->next=NULL; // 最后原来的链头变为链尾，把它指向 NULL 。 head=p; // 原来的链尾变成链头 return head; }
Node *ReverseList2(Node *head) // 链表逆序（递归方法） {
if (!head) {
return NULL; }
Node *temp = 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 指向链尾 , 由于在此次返回 , 故此次没有执行最后的 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 temp; .....
一直到 head 时 即是原链表的第一个节点 , 在对其 head->next = NULL 后 , 此时以 temp 所指向的
节点为链头的逆序链表就形成了 .
// 已知两个链表 head1 和 head2 各自有序， 请把它们合并成一个链表依然有序。（循环方法） //( 保留所有结点， 即便大小相同）
Node *Merge(Node *head1 , Node *head2) {
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 ; }
Node *temp = head ;
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; }
// 已知两个链表 head1 和 head2 各自有序， 请把它们合并成一个链表依然有序。（递归方法）Node *MergeRecursive(Node *head1 , Node *head2) {
if ( head1 == NULL ) return head2 ; if ( head2 == NULL)