C++中实现链表的删除和颠倒

时间：2022-01-29 23:27:35

MFC工程中关于链表的操作

1.对于给定的整数n，编写算法删除链表中第n个节点，该链表的第一个节点由first指向。

由于C++中没有关于node的标准头文件，要先手动定义node类，此处只定义了简单的data和next指针以及析构函数部分的内容：

 class node

 {

 public:

     node(const int &in,node *nextnode = NULL);

     virtual ~node();

     node*next;

     int data;

 };

#include"node.h"之后就可以定义节点了。

 node *p1,*p2,*p3;

     p1=new node();

     p2=new node(,p1);

     p3=new node(,p2);

此处定义出的链表 图示如下：

p3-->p2-->p1

3 -->2 -->1

关于eraseValue函数的定义：

 template <typename T>

 void eraseValue(node*first,const T&n)

 {

     node *curr=first,*pre=NULL;

     if(n==)

     {

         first=first->next;

         delete curr;

     }

     else {for(int i=;i<n;i++)

     {

         pre=curr;

         curr=curr->next;

     }

         pre->next=curr->next;

         delete curr;}

 }

函数调用及输出（改）：

当n=1时会报错，有待解决。

     node *cur=p3;

     eraseValue(p3,);

     CString temp,str;

     while(cur->data!=NULL)

     {

         temp.Format("%d ",cur->data);

         str+=temp;

         cur=cur->next;

     }

     AfxMessageBox(str);

2.编写一个算法来颠倒链表，不要复制链表元素，而是重置链接和指针，使得first指向原来的最后一个节点，且节点之间所有链接都反向。

未经输出测试：

 template <typename T>

 void reverse(node*first,const T&n)

 {

     node *front=NULL;

     for(int i=;i<n-;i++)

     {

         node *curr=first,*pre=NULL;

         while(curr->next!=NULL)

         {

             pre=curr;

             curr=curr->next;

         }

         if(i==&&curr->next==NULL) front=curr;

         pre->next=NULL;

         curr->next=pre;

     }

     if(i=n-) first->next=front;

     front=first;

 }

初学c++和数据结构，有错误请尽管指出，感激不尽！！

相关文章