织梦CMS - 轻松建站从此开始！
高级搜索|网站地图|TAG标签RSS订阅[设为首页] [加入收藏]

罗索

搜索

热门标签:

当前位置: 主页>基础技术>C/CPP专题>

链表的常见操作

jackyhwei 发布于 2011-09-30 16:04 点击:次 
链表是数据结构的重要内容，在计算机程序中应用广泛，同时也是各公司笔试题目的重点。以下简单实现了链表的一些操作，包括创建、增加节点、删除节点、单链表逆置、合并有序链表等。
TAG:

链表是数据结构的重要内容，在计算机程序中应用广泛，同时也是各公司笔试题目的重点。

以下简单实现了链表的一些操作，包括创建、增加节点、删除节点、单链表逆置、合并有序链表等。

一、链表创建

链表主要有三种形式，包括单链表、双链表和循环链表。

单链表每个节点只包含一个后驱指针，双链表节点同时包含一个前驱指针和一个后驱指针，循环链表的尾节点的后驱指向头节点。

代码如下：

  1. /*单链表节点结构*/ 
  2. typedef structNodeType 
  3. { 
  4.   char elem; 
  5.   NodeType*next; 
  6. }Node; 
  7.  
  8. /*双链表节点结构*/ 
  9. typedef structDNodeType 
  10. { 
  11. char elem; 
  12.  DNodeType*next; 
  13.  DNodeType*prev; 
  14. }DNode; 
  15.  
  16. /* 
  17. 创建链表 
  18. */ 
  19. Node* CreateList(Node*head) 
  20. { 
  21. if(NULL== head)//分配头节点空间 
  22.  head=(Node*)malloc(sizeof(Node)), 
  23.  head->next=NULL; 
  24.  
  25.  Node*current=head ,*temp; 
  26. char ch; 
  27.  
  28. while(1) 
  29.  { 
  30.  cout<<"\n input elem:"; 
  31.  cin>>ch; 
  32. if('#' == ch)/*#结束输入*/ 
  33. break; 
  34.  temp=(Node*) malloc (sizeof(Node) ); 
  35.  temp->elem=ch; 
  36.  temp->next=NULL; 
  37.  current->next=temp;/*当前节点的后驱指向新节点*/ 
  38.  current=temp;/*当前节点为链表尾节点*/ 
  39.  
  40.  } 
  41.  
  42. return head; 
  43. } 
  44.  
  45.   
  46.  
  47. /*创建双链表*/ 
  48. DNode* DoubleList(DNode*head) 
  49. { 
  50. if(NULL== head)//分配头节点空间 
  51.  head=(DNode*)malloc(sizeof(DNode)) , head->prev=NULL ,head->next=NULL; 
  52.  
  53.  DNode*current=head ,*temp; 
  54. char ch; 
  55.  
  56. while(1) 
  57.  { 
  58.  cout<<"\n input elem:"; 
  59.  cin>>ch; 
  60. if('#' == ch)/*#结束输入*/ 
  61. break; 
  62.  temp=(DNode*) malloc (sizeof(DNode) ); 
  63.  temp->elem=ch; 
  64.  temp->next=NULL; 
  65.  current->next=temp;/*当前节点的后驱指向新节点*/ 
  66.  temp->prev=current;/*新节点的前驱指向当前节点*/ 
  67.  current=temp;/*当前节点为链表尾节点*/ 
  68.  
  69.  } 
  70.  
  71. return head; 
  72. } 
  73.  
  74.   
  75.  
  76. /*创建循环链表*/ 
  77. Node* CycleList(Node*head) 
  78. { 
  79. if(NULL== head)/*分配头节点空间*/ 
  80.  head=(Node*)malloc(sizeof(Node)),head->next=NULL; 
  81.  
  82.  Node*current=head ,*temp; 
  83. char ch; 
  84.  
  85. while(1) 
  86.  { 
  87.  cout<<"\n input elem:"; 
  88.  cin>>ch; 
  89. if('#' == ch)/*#结束输入*/ 
  90. break; 
  91.  temp=(Node*) malloc (sizeof(Node) ); 
  92.  temp->elem=ch; 
  93.  temp->next=NULL; 
  94.  current->next=temp;/*当前节点的后驱指向新节点*/ 
  95.  current=temp;/*当前节点为链表尾节点*/ 
  96.  
  97.  } 
  98.  current->next=head;/*尾节点指向头节点*/ 
  99. return head; 
  100. } 

二、链表操作

包括单链表的增加节点、删除节点、输出链表等

  1. /*在尾部插入节点#add 可以直接在指定参数节点插入*/ 
  2. Node*InsertNode(Node*head ,char elem) 
  3. { 
  4. if( NULL== head|| NULL== elem ) 
  5. return head; 
  6.  
  7.  Node*current=head->next;/*当前节点*/ 
  8.  Node*prev=head;/*前驱节点*/ 
  9.  Node*temp;/*过渡节点*/ 
  10.  
  11. while(current)/*移动至尾节点*/ 
  12.  { 
  13.  prev=current; 
  14.  current=current->next; 
  15.  } 
  16.  
  17.  temp=(Node*)malloc(sizeof(Node)); 
  18.  temp->elem=elem; 
  19.  temp->next=NULL; 
  20.  prev->next=temp;/*尾节点的后驱指向新节点*/ 
  21.  
  22. return head; 
  23. } 
  24.  
  25. /*删除节点*/ 
  26. Node*DeleteNode(Node*head,char elem) 
  27. { 
  28. if(NULL== head|| NULL== elem) 
  29. return head; 
  30. if(NULL== head->next) 
  31. return head; 
  32.  
  33.  Node*prev,*current; 
  34.  prev=head; 
  35.  current=head->next; 
  36.  
  37. while(current) 
  38.  { 
  39. if(current->elem== elem)/*匹配节点元素*/ 
  40.  { 
  41.  prev->next=current->next;/*前驱节点的后驱指向当前节点的下一个节点*/ 
  42.  free(current);/*释放当前节点*/ 
  43. return head; 
  44.  } 
  45.  prev=current; 
  46.  current=current->next;/*移动至下一个节点*/ 
  47.  } 
  48.  
  49. return head; 
  50.  
  51. } 
  52. /*输出链表*/ 
  53. void PrintList(Node*head) 
  54. { 
  55.  Node* current=head->next; 
  56.  cout<<"\n List are:"; 
  57. while(NULL!= current) 
  58.  { 
  59. if(NULL!= current->elem) 
  60.  cout<<setw(5)<<current->elem; 
  61.  current=current->next; 
  62.  } 
  63.  
  64.  cout<<"\n"; 
  65. } 

三、单链表逆置

单链表逆置在各公司的笔试题中比较常见，以下是其中一种实现。

算法描述：将链表中每一个节点插入到头结点之后。

代码如下：

  1. /*单链表逆置*/ 
  2. Node*ReverseList(Node*head) 
  3. { 
  4. if(NULL== head) 
  5. return head; 
  6. if(NULL== head->next) 
  7. return head; 
  8. if(NULL== head->next->next) 
  9. return head; 
  10.  
  11.  Node*curr=head->next;/*当前节点*/ 
  12.  head->next=NULL; 
  13.  Node*temp; 
  14.  
  15. while(curr) 
  16.  { 
  17.  temp=curr->next;/*暂存下一个节点*/ 
  18. /*把当前节点插入到head节点后*/ 
  19.  curr->next=head->next; 
  20.  head->next=curr; 
  21.  
  22.  curr=temp;/*移动至下一个节点*/ 
  23.  } 
  24.  
  25. return head; 
  26. } 

四、求单链表中间节点

在笔试题中比较常见，通常题目描述是：给出一个单链表，不知道节点N的值，怎样只遍历一次就可以求出中间节点。

算法描述：设立两个指针p1,p2，p1每次移动1个节点位置，p2每次移动2个节点位置，当p2移动到尾节点时，p1指向中间节点。

代码如下：

  1. /*求中间节点*/ 
  2. Node* MiddleNode(Node*head) 
  3. { 
  4. if(NULL== head) 
  5. return head; 
  6. if(NULL== head->next) 
  7. return head->next; 
  8.  
  9.  Node*p1,*p2; 
  10.  p1=head; 
  11.  p2=head; 
  12.  
  13. while(p2->next) 
  14.  { 
  15. /*p2节点移动2个节点位置*/ 
  16.  p2=p2->next; 
  17. if(p2->next)/*判断p2后驱节点是否存在，存在则再移动一次*/ 
  18.  p2=p2->next; 
  19. /*p1节点移动1个节点位置*/ 
  20.  p1=p1->next; 
  21.  
  22.  } 
  23. return p1; 
  24. } 

五、合并有序单链表

问题描述：合并2个有序单链表，合并后的链表也是排好序的。

算法描述：对链表A中的每一个节点元素，查找其在链表B中的插入位置，并在B中插入该元素。

代码如下：

  1. /*合并有序单链表*/ 
  2. Node* MergeList(Node*h1,Node* h2) 
  3. { 
  4. if(NULL== h1|| NULL== h2) 
  5. return h1; 
  6. if(NULL== h1->next ) 
  7. return h2; 
  8. if(NULL== h2->next) 
  9. return h1; 
  10.  
  11.  Node* curr1,*curr2,*prev1,*temp; 
  12.  prev1=h1;/*链表1的前驱节点*/ 
  13.  curr1=h1->next;/*链表1的当前节点*/ 
  14.  curr2=h2->next;/*链表2的当前节点*/ 
  15.  temp=h2; 
  16. while(curr2) 
  17.  { 
  18. while(curr1&&curr1->elem< curr2->elem)/*链表1指针移动至大或等于链表2当前元素的位置*/ 
  19.  prev1=curr1,curr1=curr1->next; 
  20.  
  21. /*在链表1中插入链表2的当前元素*/ 
  22.  temp=curr2->next;/*暂存链表2的下一个节点*/ 
  23.  prev1->next=curr2; 
  24.  curr2->next=curr1; 
  25.  
  26. /*链表1移动至新节点*/ 
  27.  curr1=curr2; 
  28. /*链表2移动至下一个节点*/ 
  29.  curr2=temp; 
  30.  } 
  31.  
  32. return h1; 
  33. } 

六、判断链表是否有环

判断链表是否有环即是判断链表是否为循环链表，算法较为简单，一次遍历判断尾指针是否指向头指针即可。代码如下：

  1. /*判断链表是否有环(循环链表)*/ 
  2. bool IsCycleList(Node*head) 
  3. { 
  4. if(NULL== head) 
  5. return false; 
  6. if(NULL== head->next) 
  7. return false; 
  8.  Node*current=head->next; 
  9. while(current) 
  10.  { 
  11. if(head== current->next) 
  12. return true; 
  13.  current=current->next; 
  14.  } 
  15. return false; 
  16. } 

七、总结及源文件

以上实现了链表的一些常见操作，源文件LinkList.cpp全部代码如下：　

/*
 * 作者： 达闻东
 * 修改日期：2010-04-28 17:10
 * 描述： 实现链表的常见操作
*/

  1. #include<iostream> 
  2. #include<iomanip> 
  3. using namespace std; 
  4.  
  5. /*单链表节点结构*/ 
  6. typedefstruct NodeType 
  7. { 
  8. char elem; 
  9.  NodeType*next; 
  10. }Node; 
  11.  
  12. /*双链表节点结构*/ 
  13. typedefstruct DNodeType 
  14. { 
  15. char elem; 
  16.  DNodeType*next; 
  17.  DNodeType*prev; 
  18. }DNode; 

/*创建链表*/

  1. Node* CreateList(Node*head) 
  2. { 
  3. if(NULL== head)//分配头节点空间 
  4.  head=(Node*)malloc(sizeof(Node)), 
  5.  head->next=NULL; 
  6.  
  7.  Node*current=head ,*temp; 
  8. char ch; 
  9.  
  10. while(1) 
  11.  { 
  12.  cout<<"\n input elem:"; 
  13.  cin>>ch; 
  14. if('#' == ch)/*#结束输入*/ 
  15. break; 
  16.  temp=(Node*) malloc (sizeof(Node) ); 
  17.  temp->elem=ch; 
  18.  temp->next=NULL; 
  19.  current->next=temp;/*当前节点的后驱指向新节点*/ 
  20.  current=temp;/*当前节点为链表尾节点*/ 
  21.  
  22.  } 
  23.  
  24. return head; 
  25. } 

/*输出链表*/

  1. void PrintList(Node*head) 
  2. { 
  3.  Node* current=head->next; 
  4.  cout<<"\n List are:"; 
  5. while(NULL!= current) 
  6.  { 
  7. if(NULL!= current->elem) 
  8.  cout<<setw(5)<<current->elem; 
  9.  current=current->next; 
  10.  } 
  11.  cout<<"\n"; 
  12. } 

/*插入节点*/

  1. Node*InsertNode(Node*head,char elem) 
  2. { 
  3. if( NULL== head|| NULL== elem) 
  4. return head; 
  5.  
  6.  Node*current=head->next;/*当前节点*/ 
  7.  Node*prev=head;/*前驱节点*/ 
  8.  Node*temp;/*过渡节点*/ 
  9.  
  10. while(current)/*移动至尾节点*/ 
  11.  { 
  12.  prev=current; 
  13.  current=current->next; 
  14.  } 
  15.  
  16.  temp=(Node*) malloc(sizeof(Node) ); 
  17.  temp->elem=elem; 
  18.  temp->next=NULL; 
  19.  prev->next=temp;/*尾节点的后驱指向新节点*/ 
  20.  
  21. return head; 
  22. } 

/*删除节点*/

  1. Node*DeleteNode(Node*head,char elem) 
  2. { 
  3. if(NULL== head|| NULL== elem) 
  4. return head; 
  5. if(NULL== head->next) 
  6. return head; 
  7.  
  8.  Node*prev,*current; 
  9.  prev=head; 
  10.  current=head->next; 
  11.  
  12. while(current) 
  13.  { 
  14. if(current->elem== elem)/*匹配节点元素*/ 
  15.  { 
  16.  prev->next=current->next;/*前驱节点的后驱指向当前节点的下一个节点*/ 
  17.  free(current);/*释放当前节点*/ 
  18. return head; 
  19.  } 
  20.  prev=current; 
  21.  current=current->next;/*移动至下一个节点*/ 
  22.  } 
  23. return head; 
  24. } 

/*单链表逆置*/

  1. Node*ReverseList(Node*head) 
  2. { 
  3. if(NULL== head) 
  4. return head; 
  5. if(NULL== head->next) 
  6. return head; 
  7. if(NULL== head->next->next) 
  8. return head; 
  9.  
  10.  Node*curr=head->next;/*当前节点*/ 
  11.  head->next=NULL; 
  12.  Node*temp; 
  13.  
  14. while(curr) 
  15.  { 
  16.  temp=curr->next;/*暂存下一个节点*/ 
  17. /*把当前节点插入到head节点后*/ 
  18.  curr->next=head->next; 
  19.  head->next=curr; 
  20.  
  21.  curr=temp;/*移动至下一个节点*/ 
  22.  } 
  23. return head; 
  24. } 

/*求中间节点*/

  1. Node* MiddleNode(Node*head) 
  2. { 
  3. if(NULL== head) 
  4. return head; 
  5. if(NULL== head->next) 
  6. return head->next; 
  7.  
  8.  Node*p1,*p2; 
  9.  p1=head; 
  10.  p2=head; 
  11.  
  12. while(p2->next) 
  13.  { 
  14. /*p2节点移动2个节点位置*/ 
  15.  p2=p2->next; 
  16. if(p2->next)/*判断p2后驱节点是否存在，存在则再移动一次*/ 
  17.  p2=p2->next; 
  18. /*p1节点移动1个节点位置*/ 
  19.  p1=p1->next; 
  20.  } 
  21. return p1; 
  22. } 

/*合并有序单链表*/

  1. Node* MergeList(Node* h1,Node* h2) 
  2. { 
  3. if(NULL== h1|| NULL== h2) 
  4. return h1; 
  5. if(NULL== h1->next) 
  6. return h2; 
  7. if(NULL== h2->next) 
  8. return h1; 
  9.  
  10. Node* curr1,*curr2,*prev1,*temp; 
  11.  prev1=h1;/*链表1的前驱节点*/ 
  12.  curr1=h1->next;/*链表1的当前节点*/ 
  13.  curr2=h2->next;/*链表2的当前节点*/ 
  14.  temp=h2; 
  15. while(curr2) 
  16.  { 
  17. while(curr1&& curr1->elem< curr2->elem)
  18. /*链表1指针移动至大或等于链表2当前元素的位置*/ 
  19.  prev1=curr1,curr1=curr1->next; 
  20.  
  21. /*在链表1中插入链表2的当前元素*/ 
  22.  temp=curr2->next;/*暂存链表2的下一个节点*/ 
  23.  prev1->next=curr2; 
  24.  curr2->next=curr1; 
  25.  
  26. /*链表1移动至新节点*/ 
  27.  curr1=curr2; 
  28. /*链表2移动至下一个节点*/ 
  29.  curr2=temp; 
  30.  } 
  31. return h1; 
  32. } 

/*创建双链表*/

  1. DNode* DoubleList(DNode*head) 
  2. { 
  3. if(NULL== head)//分配头节点空间 
  4.  head=(DNode*)malloc(sizeof(DNode)) ,head->prev=NULL , head->next=NULL; 
  5.  
  6.  DNode*current=head ,*temp; 
  7. char ch; 
  8.  
  9. while(1) 
  10.  { 
  11.  cout<<"\n inputelem:"; 
  12.  cin>>ch; 
  13. if('#' == ch)/*#结束输入*/ 
  14. break; 
  15.  temp=(DNode*) malloc (sizeof(DNode) ); 
  16.  temp->elem=ch; 
  17.  temp->next=NULL; 
  18.  current->next=temp;/*当前节点的后驱指向新节点*/ 
  19.  temp->prev=current;/*新节点的前驱指向当前节点*/ 
  20.  current=temp;/*当前节点为链表尾节点*/ 
  21.  } 
  22. return head; 
  23. } 

/*输出双链表*/

  1. void PrintDoubleList(DNode*head) 
  2. { 
  3. if(NULL== head) 
  4. return; 
  5.  
  6.  DNode* p; 
  7.  p=head; 
  8.  cout<<"\n DoubleListare:"; 
  9. while(p->next) 
  10.  { 
  11.  p=p->next; 
  12. if(p->elem) 
  13.  cout<<setw(5)<<p->elem; 
  14.  
  15.  } 
  16.  
  17.  cout<<"\n DoubleListare:"; 
  18. while(p->prev) 
  19.  { 
  20. if(p->elem) 
  21.  cout<<setw(5)<<p->elem; 
  22.  p=p->prev; 
  23.  } 
  24. } 

/*创建循环链表*/

  1. Node* CycleList(Node*head) 
  2. { 
  3. if(NULL== head)/*分配头节点空间*/ 
  4.  head=(Node*)malloc(sizeof(Node)),head->next=NULL; 
  5.  
  6.  Node*current=head ,*temp; 
  7. char ch; 
  8.  
  9. while(1) 
  10.  { 
  11.  cout<<"\n inputelem:"; 
  12.  cin>>ch; 
  13. if('#' == ch)/*#结束输入*/ 
  14. break; 
  15.  temp=(Node*) malloc (sizeof(Node) ); 
  16.  temp->elem=ch; 
  17.  temp->next=NULL; 
  18.  current->next=temp;/*当前节点的后驱指向新节点*/ 
  19.  current=temp;/*当前节点为链表尾节点*/ 
  20.  
  21.  } 
  22.  current->next=head;/*尾节点指向头节点*/ 
  23. return head; 
  24. } 

/*判断链表是否有环(循环链表)*/

  1. bool IsCycleList(Node*head) 
  2. { 
  3. if(NULL== head) 
  4. return false; 
  5. if(NULL== head->next) 
  6. return false; 
  7.  Node*current=head->next; 
  8. while(current) 
  9.  { 
  10. if(head== current->next) 
  11. return true; 
  12.  current=current->next; 
  13.  } 
  14. return false; 
  15. } 
  16. int main() 
  17. { 
  18.  Node* head,*p; 
  19.  Node* head2,*head3; 
  20.  DNode* dHead; 
  21. char ch; 
  22.  head= NULL; 
  23.  head2=NULL; 
  24.  head3=NULL; 
  25.  dHead=NULL; 
  26.  
  27. //head=(Node*)malloc ( sizeof( Node) ); 
  28. //head->next= NULL; 
  29.  
  30. //创建单链表 
  31.  head=CreateList(head); 
  32.  PrintList(head); 
  33.  
  34.  head2=CreateList(head2); 
  35.  PrintList(head2); 
  36.  
  37. //插入节点 
  38.   cout<<"\n input elem toinsert:"; 
  39.  cin>>ch; 
  40.  InsertNode(head,ch); 
  41.  PrintList(head); 
  42.  
  43. //删除节点 
  44.   cout<<"\n input elem todelete:"; 
  45.  cin>>ch; 
  46.  DeleteNode(head,ch); 
  47.  PrintList(head); 
  48.  
  49. //单链表逆置 
  50.   head=ReverseList(head); 
  51.  cout<<"\n Reversed !"; 
  52.  PrintList(head); 
  53.  
  54. //求中间节点 
  55.  p=MiddleNode(head); 
  56.  cout<<"\n Middle Nodeis:"; 
  57.  cout<<p->elem<<endl; 
  58.  
  59. //合并有序单链表 
  60.  MergeList(head,head2); 
  61.  cout<<"\n Merged!"; 
  62.  PrintList(head); 
  63.  
  64. //创建双链表 
  65.  dHead=DoubleList(dHead); 
  66.  PrintDoubleList(dHead); 
  67.  
  68. /*创建循环链表并判断是否有环*/ 
  69.  head3=CycleList(head3); 
  70.  cout<<IsCycleList(head3); 
  71. return 0; 
  72. } 


 

(达闻东)
本站文章除注明转载外，均为本站原创或编译欢迎任何形式的转载，但请务必注明出处，尊重他人劳动，同学习共成长。转载请注明：文章转载自：罗索实验室 [http://www.rosoo.net/a/201109/15081.html]
本文出处：网络　作者：达闻东
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
相关文章
发表评论
请自觉遵守互联网相关的政策法规，严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
最新评论 进入详细评论页>>
栏目列表
将本文分享到微信
织梦二维码生成器
推荐内容
热点内容