Code666 (代码贴、代码片段)

[C++] C++链表的相关操作（建立、插入、删除、查找、逆置） →→→→→进入此内容的聊天室

来自 , 2019-04-21, 写在 C++, 查看 137 次.
URL http://www.code666.cn/view/414e773d
  1. #include<iostream>
  2. using namespace std;
  3. typedef int T;
  4. class List{
  5.         struct Node{
  6.                 T data;
  7.                 Node *next;
  8.                 Node(const T&d):data(d),next(NULL){}
  9.                 //Node(){}
  10.         };
  11.         Node *head;
  12.         int len;
  13. public:
  14.         List():len(0),head(NULL){}
  15.        
  16.         void push_front(const T&d)//头插法
  17.         {
  18.                 Node *p=new Node(d);
  19.                 if(head==NULL) head=p;
  20.                 else
  21.                 {
  22.                         p->next=head;//使p和head指向相同
  23.                         head=p;
  24.                 }
  25.         }
  26.        
  27.         void push_back(const T&d)//尾插法
  28.         {
  29.                 static Node *r;//防止r在出了这个作用域之后就释放
  30.                 Node *p=new Node(d);
  31.                 if(head==NULL) {head=p;r=p;}
  32.                 else
  33.                 {
  34.                         r->next=p;
  35.                         r=p;
  36.                         r->next=NULL;
  37.                 }
  38.         }
  39.  
  40.         Node *&getptr(int pos)//得到指定链表中的位置
  41.         {
  42.                 if(pos<0) pos=0;
  43.                 if(pos==0) return head;
  44.                 Node *p=head;
  45.                 for(int i=0;i<pos-1;i++)
  46.                         p=p->next;
  47.                 return p->next;
  48.         }
  49.        
  50.         void insert(const T&d,int pos)//在任意位置插入
  51.         {
  52.                 Node *&pn=getptr(pos);
  53.                 Node *p=new Node(d);
  54.                 p->next=pn->next;
  55.                 pn->next=p;
  56.         }
  57.        
  58.         int Num()//统计结点个数
  59.         {
  60.                 Node *p=head;
  61.                 int cnt=0;
  62.                 while(p)
  63.                 {
  64.                         cnt++;
  65.                         p=p->next;
  66.                 }
  67.                 return cnt;
  68.         }
  69.  
  70.         void clear()//清空链表
  71.         {
  72.                 while(head)
  73.                 {
  74.                         Node *p=head->next;
  75.                         delete head;
  76.                         head=p;
  77.                 }
  78.         }
  79.  
  80.         void erase(int pos)//删除指定位置的元素
  81.         {
  82.                 if(pos<0) return;
  83.                 Node *&p=getptr(pos);//引用保证是原始指针
  84.                 Node *pn=p;
  85.                 p=p->next;
  86.                 delete pn;
  87.         }
  88.        
  89.         void remove(const T&d)//删除指定元素
  90.         {
  91.                 int pos=0;
  92.                 Node *p=head;
  93.                 while(p)
  94.                 {
  95.                         if(p->data==d)
  96.                         {
  97.                                 erase(pos);
  98.                                 return;
  99.                         }
  100.                         p=p->next;
  101.                         pos++;
  102.                 }
  103.         }
  104.        
  105.         void set(int pos,const T& d)//修改指定位置处的元素
  106.         {
  107.                 if(pos<0) return;
  108.                 getptr(pos)->data=d;
  109.         }
  110.        
  111.         void revise()//单链表的逆置
  112.         {
  113.                 Node  *p,*q;
  114.                 p=head->next;
  115.                 head->next=NULL;
  116.                 while(p!=NULL)
  117.                 {
  118.                         q=p->next;
  119.                         p->next=head;
  120.                         head=p;
  121.                         p=q;
  122.                 }
  123.         }      
  124.  
  125.         void print()//输出
  126.         {
  127.                 Node *p=head;
  128.                 while(p)
  129.                 {
  130.                         cout<<p->data<<' ';
  131.                         p=p->next;
  132.                 }
  133.                 cout<<endl;
  134.         }
  135. };
  136.  
  137. int main()
  138. {
  139.         List l;
  140.         /*
  141.         l.push_front(1);
  142.         l.push_front(2);
  143.         l.push_front(3);
  144.         l.push_front(4);
  145.         l.print();
  146.         */
  147.         l.push_back(5);
  148.         l.push_back(6);
  149.         l.push_back(7);
  150.         l.push_back(8);
  151.         l.insert(9,1);
  152.         l.insert(10,2);
  153.         l.print();//5 6 9 10 7 8
  154.         cout<<"Num="<<l.Num()<<endl;
  155.         l.erase(1);
  156.         l.print();//5 9 10 7 8
  157.         l.remove(9);
  158.         l.print();//5 10 7 8
  159.         l.set(1,3);
  160.         l.print();//5 3 7 8
  161.         l.revise();
  162.         l.print();//8 7 3 5
  163.         l.clear();
  164.         cout<<"Num="<<l.Num()<<endl;
  165.         return 0;
  166. }
  167.  

回复 "C++链表的相关操作（建立、插入、删除、查找、逆置）"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666