链表是数据结构的重要内容,在计算机程序中应用广泛,同时也是各公司笔试题目的重点。
以下简单实现了链表的一些操作,包括创建、增加节点、删除节点、单链表逆置、合并有序链表等。
一、链表创建
链表主要有三种形式,包括单链表、双链表和循环链表。
单链表每个节点只包含一个后驱指针,双链表节点同时包含一个前驱指针和一个后驱指针,循环链表的尾节点的后驱指向头节点。
代码如下:
/*单链表节点结构*/ typedef structNodeType { char elem; NodeType*next; }Node;
/*双链表节点结构*/ typedef structDNodeType { char elem; DNodeType*next; DNodeType*prev; }DNode;
/* 创建链表 */ Node* CreateList(Node*head) { if(NULL== head)//分配头节点空间 head=(Node*)malloc(sizeof(Node)), head->next=NULL;
Node*current=head ,*temp; char ch;
while(1) { cout<<"\n input elem:"; cin>>ch; if('#' == ch)/*#结束输入*/ break; temp=(Node*) malloc (sizeof(Node) ); temp->elem=ch; temp->next=NULL; current->next=temp;/*当前节点的后驱指向新节点*/ current=temp;/*当前节点为链表尾节点*/
}
return head; }
/*创建双链表*/ DNode* DoubleList(DNode*head) { if(NULL== head)//分配头节点空间 head=(DNode*)malloc(sizeof(DNode)) , head->prev=NULL ,head->next=NULL;
DNode*current=head ,*temp; char ch;
while(1) { cout<<"\n input elem:"; cin>>ch; if('#' == ch)/*#结束输入*/ break; temp=(DNode*) malloc (sizeof(DNode) ); temp->elem=ch; temp->next=NULL; current->next=temp;/*当前节点的后驱指向新节点*/ temp->prev=current;/*新节点的前驱指向当前节点*/ current=temp;/*当前节点为链表尾节点*/
}
return head; }
/*创建循环链表*/ Node* CycleList(Node*head) { if(NULL== head)/*分配头节点空间*/ head=(Node*)malloc(sizeof(Node)),head->next=NULL;
Node*current=head ,*temp; char ch;
while(1) { cout<<"\n input elem:"; cin>>ch; if('#' == ch)/*#结束输入*/ break; temp=(Node*) malloc (sizeof(Node) ); temp->elem=ch; temp->next=NULL; current->next=temp;/*当前节点的后驱指向新节点*/ current=temp;/*当前节点为链表尾节点*/
} current->next=head;/*尾节点指向头节点*/ return head; }
二、链表操作
包括单链表的增加节点、删除节点、输出链表等
添加节点
/*在尾部插入节点#add 可以直接在指定参数节点插入*/ Node*InsertNode(Node*head ,char elem) { if( NULL== head|| NULL== elem ) return head;
Node*current=head->next;/*当前节点*/ Node*prev=head;/*前驱节点*/ Node*temp;/*过渡节点*/
while(current)/*移动至尾节点*/ { prev=current; current=current->next; }
temp=(Node*)malloc(sizeof(Node)); temp->elem=elem; temp->next=NULL; prev->next=temp;/*尾节点的后驱指向新节点*/
return head; }
/*删除节点*/ Node*DeleteNode(Node*head,char elem) { if(NULL== head|| NULL== elem) return head; if(NULL== head->next) return head;
Node*prev,*current; prev=head; current=head->next;
while(current) { if(current->elem== elem)/*匹配节点元素*/ { prev->next=current->next;/*前驱节点的后驱指向当前节点的下一个节点*/ free(current);/*释放当前节点*/ return head; } prev=current; current=current->next;/*移动至下一个节点*/ }
return head;
} /*输出链表*/ void PrintList(Node*head) { Node* current=head->next; cout<<"\n List are:"; while(NULL!= current) { if(NULL!= current->elem) cout<<setw(5)<<current->elem; current=current->next; }
cout<<"\n"; }
三、单链表逆置
单链表逆置在各公司的笔试题中比较常见,以下是其中一种实现。
算法描述:将链表中每一个节点插入到头结点之后(#add 将head的next的next插入到head与其next之间)。
代码如下:
/*单链表逆置*/ Node*ReverseList(Node*head) { if(NULL== head) return head; if(NULL== head->next) return head; if(NULL== head->next->next) return head;
Node*curr = head->next;/*当前节点*/ head->next = NULL; Node*temp; while(curr) { temp = curr->next;/*暂存下一个节点*/ /*把当前节点插入到head节点后*/ curr->next = head->next; head->next = curr;
curr = temp;/*移动至下一个节点*/ }
return head; }
四、求单链表中间节点
在笔试题中比较常见,通常题目描述是:给出一个单链表,不知道节点N的值,怎样只遍历一次就可以求出中间节点。
算法描述:设立两个指针p1,p2,p1每次移动1个节点位置,p2每次移动2个节点位置,当p2移动到尾节点时,p1指向中间节点。
代码如下:
求中间节点
/*求中间节点*/ Node* MiddleNode(Node*head) { if(NULL== head) return head; if(NULL== head->next) return head->next;
Node*p1,*p2; p1=head; p2=head;
while(p2->next) { /*p2节点移动2个节点位置*/ p2=p2->next; if(p2->next)/*判断p2后驱节点是否存在,存在则再移动一次*/ p2=p2->next; /*p1节点移动1个节点位置*/ p1=p1->next;
} return p1; }
五、合并有序单链表
问题描述:合并2个有序单链表,合并后的链表也是排好序的。
算法描述:对链表A中的每一个节点元素,查找其在链表B中的插入位置,并在B中插入该元素。
代码如下:
/*合并有序单链表*/ Node* MergeList(Node*h1,Node* h2) { if(NULL== h1|| NULL== h2) return h1; if(NULL== h1->next ) return h2; if(NULL== h2->next) return h1;
Node* curr1,*curr2,*prev1,*temp; prev1=h1;/*链表1的前驱节点*/ curr1=h1->next;/*链表1的当前节点*/ curr2=h2->next;/*链表2的当前节点*/ temp=h2; while(curr2) { while(curr1&&curr1->elem< curr2->elem)/*链表1指针移动至大或等于链表2当前元素的位置*/ prev1=curr1,curr1=curr1->next;
/*在链表1中插入链表2的当前元素*/ temp=curr2->next;/*暂存链表2的下一个节点*/ prev1->next=curr2; curr2->next=curr1;
/*链表1移动至新节点*/ curr1=curr2; /*链表2移动至下一个节点*/ curr2=temp; }
return h1;
}
六、判断链表是否有环
判断链表是否有环即是判断链表是否为循环链表,算法较为简单,一次遍历判断尾指针是否指向头指针即可。
代码如下:
/*判断链表是否有环(循环链表)*/ bool IsCycleList(Node*head) { if(NULL== head) return false; if(NULL== head->next) return false; Node*current=head->next; while(current) { if(head== current->next) return true; current=current->next; } return false; }
七、总结及源文件
以上实现了链表的一些常见操作,源文件LinkList.cpp全部代码如下:
/* * 作者: 达闻东 * 修改日期:2010-04-28 17:10 * 描述: 实现链表的常见操作 * */ #include<iostream> #include<iomanip> using namespace std;
/*单链表节点结构*/ typedefstruct NodeType { char elem; NodeType*next; }Node;
/*双链表节点结构*/ typedefstruct DNodeType { char elem; DNodeType*next; DNodeType*prev; }DNode;
/*=============================================================================*/ /* 创建链表 */ Node* CreateList(Node*head) { if(NULL== head)//分配头节点空间 head=(Node*)malloc(sizeof(Node)), head->next=NULL;
Node*current=head ,*temp; char ch;
while(1) { cout<<"\n input elem:"; cin>>ch; if('#' == ch)/*#结束输入*/ break; temp=(Node*) malloc (sizeof(Node) ); temp->elem=ch; temp->next=NULL; current->next=temp;/*当前节点的后驱指向新节点*/ current=temp;/*当前节点为链表尾节点*/
}
return head; } /*=============================================================================*/ /* 输出链表 */ void PrintList(Node*head) { Node* current=head->next; cout<<"\n List are:"; while(NULL!= current) { if(NULL!= current->elem) cout<<setw(5)<<current->elem; current=current->next; }
cout<<"\n"; }
/*=============================================================================*/
/*插入节点*/
Node*InsertNode(Node*head,char elem) { if( NULL== head|| NULL== elem) return head;
Node*current=head->next;/*当前节点*/ Node*prev=head;/*前驱节点*/ Node*temp;/*过渡节点*/
while(current)/*移动至尾节点*/ { prev=current; current=current->next; }
temp=(Node*) malloc(sizeof(Node) ); temp->elem=elem; temp->next=NULL; prev->next=temp;/*尾节点的后驱指向新节点*/
return head;
} /*=============================================================================*/
/*删除节点*/ Node*DeleteNode(Node*head,char elem) { if(NULL== head|| NULL== elem) return head; if(NULL== head->next) return head;
Node*prev,*current; prev=head; current=head->next;
while(current) { if(current->elem== elem)/*匹配节点元素*/ { prev->next=current->next;/*前驱节点的后驱指向当前节点的下一个节点*/ free(current);/*释放当前节点*/ return head; } prev=current; current=current->next;/*移动至下一个节点*/ }
return head;
}
/*=============================================================================*/
/*单链表逆置*/ Node*ReverseList(Node*head) { if(NULL== head) return head; if(NULL== head->next) return head; if(NULL== head->next->next) return head;
Node*curr=head->next;/*当前节点*/ head->next=NULL; Node*temp;
while(curr) { temp=curr->next;/*暂存下一个节点*/ /*把当前节点插入到head节点后*/ curr->next=head->next; head->next=curr;
curr=temp;/*移动至下一个节点*/ }
return head;
}
/*=============================================================================*/
/*求中间节点*/ Node* MiddleNode(Node*head) { if(NULL== head) return head; if(NULL== head->next) return head->next;
Node*p1,*p2; p1=head; p2=head;
while(p2->next) { /*p2节点移动2个节点位置*/ p2=p2->next; if(p2->next)/*判断p2后驱节点是否存在,存在则再移动一次*/ p2=p2->next; /*p1节点移动1个节点位置*/ p1=p1->next;
} return p1;
}
/*=============================================================================*/
/*合并有序单链表*/ Node* MergeList(Node* h1,Node* h2) { if(NULL== h1|| NULL== h2) return h1; if(NULL== h1->next) return h2; if(NULL== h2->next) return h1;
Node* curr1,*curr2,*prev1,*temp; prev1=h1;/*链表1的前驱节点*/ curr1=h1->next;/*链表1的当前节点*/ curr2=h2->next;/*链表2的当前节点*/ temp=h2; while(curr2) { while(curr1&& curr1->elem< curr2->elem)/*链表1指针移动至大或等于链表2当前元素的位置*/ prev1=curr1,curr1=curr1->next;
/*在链表1中插入链表2的当前元素*/ temp=curr2->next;/*暂存链表2的下一个节点*/ prev1->next=curr2; curr2->next=curr1;
/*链表1移动至新节点*/ curr1=curr2; /*链表2移动至下一个节点*/ curr2=temp; }
return h1; } /*=============================================================================*/
/*创建双链表*/ DNode* DoubleList(DNode*head) { if(NULL== head)//分配头节点空间 head=(DNode*)malloc(sizeof(DNode)) ,head->prev=NULL , head->next=NULL;
DNode*current=head ,*temp; char ch;
while(1) { cout<<"\n inputelem:"; cin>>ch; if('#' == ch)/*#结束输入*/ break; temp=(DNode*) malloc (sizeof(DNode) ); temp->elem=ch; temp->next=NULL; current->next=temp;/*当前节点的后驱指向新节点*/ temp->prev=current;/*新节点的前驱指向当前节点*/ current=temp;/*当前节点为链表尾节点*/
} return head; }
/*=============================================================================*/ /*输出双链表*/ void PrintDoubleList(DNode*head) { if(NULL== head) return;
DNode* p; p=head; cout<<"\n DoubleListare:"; while(p->next) { p=p->next; if(p->elem) cout<<setw(5)<<p->elem;
}
cout<<"\n DoubleListare:"; while(p->prev) { if(p->elem) cout<<setw(5)<<p->elem; p=p->prev; }
}
/*=============================================================================*/ /*创建循环链表*/ Node* CycleList(Node*head) { if(NULL== head)/*分配头节点空间*/ head=(Node*)malloc(sizeof(Node)),head->next=NULL;
Node*current=head ,*temp; char ch;
while(1) { cout<<"\n inputelem:"; cin>>ch; if('#' == ch)/*#结束输入*/ break; temp=(Node*) malloc (sizeof(Node) ); temp->elem=ch; temp->next=NULL; current->next=temp;/*当前节点的后驱指向新节点*/ current=temp;/*当前节点为链表尾节点*/
} current->next=head;/*尾节点指向头节点*/ return head; } /*=============================================================================*/
/*判断链表是否有环(循环链表)*/ bool IsCycleList(Node*head) { if(NULL== head) return false; if(NULL== head->next) return false; Node*current=head->next; while(current) { if(head== current->next) return true; current=current->next; } return false; } int main() { Node* head,*p; Node* head2,*head3; DNode* dHead; char ch; head= NULL; head2=NULL; head3=NULL; dHead=NULL;
//head=(Node*)malloc ( sizeof( Node) ); //head->next= NULL;
//创建单链表 head=CreateList(head); PrintList(head);
head2=CreateList(head2); PrintList(head2);
//插入节点 cout<<"\n input elem toinsert:"; cin>>ch; InsertNode(head,ch); PrintList(head);
//删除节点 cout<<"\n input elem todelete:"; cin>>ch; DeleteNode(head,ch); PrintList(head);
//单链表逆置 head=ReverseList(head); cout<<"\n Reversed !"; PrintList(head);
//求中间节点 p=MiddleNode(head); cout<<"\n Middle Nodeis:"; cout<<p->elem<<endl;
//合并有序单链表 MergeList(head,head2); cout<<"\n Merged!"; PrintList(head);
//创建双链表 dHead=DoubleList(dHead); PrintDoubleList(dHead);
/*创建循环链表并判断是否有环*/ head3=CycleList(head3); cout<<IsCycleList(head3); return 0; }
|