指针_链表_结构体_类 2021-02-17

1. //C语言双向链表 
2. #include <stdio.h>
3. struct Node{  //结构体节点 
4.  int val;
5.  struct Node *next,*pre;
6.  Node(int v){ //构造函数 
7.    val=v;
8.    next=NULL;
9.    pre=NULL;
10.   }
11. };
12. void push_back(struct Node *head,int val) {//插入尾节点
13.   struct Node *tmp=new struct Node(val);
14.   while(head->next!=NULL){
15.     head=head->next;
16.   }
17.   head->next=tmp;
18.   tmp->pre = head;
19. }
20. void push_front(struct Node **head,int val){//插入首节点
21.   struct Node *tmp=new struct Node(val);
22.   tmp->next=*head;
23.   (*head)->pre=tmp;
24.   *head=tmp;
25. }
26. void pop_front(struct Node **head){//删除首节点
27.   *head=(*head)->next;
28.   delete (*head)->pre;
29.   (*head)->pre=NULL;
30. }
31. void pop_back(struct Node *head){//删除尾节点
32.   while(head->next!=NULL){
33.     head=head->next;
34.   }
35.   head->pre->next=NULL;
36.   delete head;  
37. }
38. void insert(struct Node *head,int pos,int val){//插入节点
39.   struct Node *tmp=new struct Node(val);
40.   while(head->next!=NULL&&pos-->0){
41.     head=head->next;
42.   }
43.   tmp->pre=head;
44.   tmp->next=head->next;
45.   head->next=tmp;
46. }
47. void erase(struct Node *head,int pos){//删除节点
48.   if(pos==0) return;
49.   while(head->next!=NULL&&pos-->0){
50.     head=head->next;
51.   }
52.   head->pre->next=head->next;
53.   delete head;
54. }
55. void print_node(struct Node *head){//打印链表 
56.   while(head!=NULL){
57.     printf("%d ",head->val);
58.     head=head->next;
59.   }
60.   printf("\n");
61. }
62. int get_size(struct Node *head){//获取链表长度 
63.   int s=0;
64.   while(head!=NULL){
65.     head=head->next;
66.     s++;
67.   }
68.   return s;
69. }
70. int main(int argc, char *argv[])
71. {
72.   struct Node *list=new struct Node(5);
73.   push_back(list,8);
74.   push_back(list,6);
75.   push_back(list,3);
76.   print_node(list);
77.   pop_back(list);
78.   print_node(list);
79.   push_front(&list,1);
80.   print_node(list);
81.   pop_front(&list);
82.   print_node(list);
83.   insert(list,1,9);
84.   print_node(list);
85.   erase(list,2);
86.   print_node(list);
87.   printf("size=%d\n",get_size(list));
88.   return 0;
89. }
90. /*
91. 5 8 6 3
92. 5 8 6
93. 1 5 8 6
94. 5 8 6
95. 5 8 9 6
96. 5 8 6
97. size=3
98. */

1. //类链表结构与迭代器 
2. #include <iostream>
3. #include <string>
4. using namespace std;
5. 
6. class list
7. {
8. public:
9.  struct Node
10.   {
11.     int val;
12.     Node *next;
13.     Node(int v){
14.       val=v;
15.       next=NULL;
16.     }
17.     Node(){
18.       val=0,next=NULL;
19.     }
20.   };
21.   class iterator
22.   {
23.   public:
24.     iterator(Node *node){ptr=node;}
25.     iterator& operator ++(){
26.       ptr=ptr->next;
27.       return *this;
28.     }
29.     iterator* operator ++(int){
30.       iterator *t=this;
31.       ptr=ptr->next;
32.       return t;
33.     }
34.     int& operator *(){
35.       return ptr->val;
36.     }
37.     bool operator ==(const iterator &it){
38.       return ptr==it.ptr;
39.     }
40.     bool operator !=(const iterator &it){
41.       return ptr!=it.ptr;
42.     }
43.   private:
44.     Node *ptr;
45.   };
46.   list():head(NULL),tail(NULL),m_size(0){}
47.   ~list(){clear();}
48.   void push_back(int v)
49.   {
50.     Node *tmp=new Node(v);
51.     ++m_size;
52.     if(head==NULL){
53.       head=tail=tmp;
54.       return;
55.     }
56.     tail->next=tmp;
57.     tail=tmp;
58.   }
59.   void pop_back()
60.   {
61.     Node *t=head,*pre;
62.     while(t!=tail)
63.     {
64.       pre=t;
65.       t=t->next;
66.     }
67.     delete tail;
68.     tail=pre;
69.     tail->next=NULL;
70.     --m_size;
71.   }
72.   void insert(int pos,int v)
73.   {
74.     Node *tmp=new Node(v);
75. 
76.     if(pos==0){
77.       tmp->next=head;
78.       head=tmp;
79.     }
80.     else if(pos==-1 || pos>=m_size){
81.       push_back(v);
82.       return;
83.     }
84.     else{
85.       Node *t=head,*pre;
86.       while(t!=NULL && pos-->0){
87.         pre=t;
88.         t=t->next;
89.       }
90.       pre->next= tmp;
91.       tmp->next=t;
92.     }
93.     ++m_size;
94.   }
95.   void remove(int pos)
96.   {
97. 
98.     Node* tmp=NULL;
99.     if(pos==0){
100.      tmp=head->next;
101.      delete head;
102.      head=tmp;
103.    }
104.    else if(pos==-1 || pos>=m_size){
105.      pop_back();
106.      return;
107.    }
108.    else{
109.      Node *t=head,*pre;
110.      while(t!=NULL && pos-->0){
111.        pre=t;
112.        t=t->next;
113.      }
114.      pre->next=t->next;
115.      delete t;
116.    }
117.    m_size--;
118.  }
119.  void clear(){
120.    if(m_size==0) return;
121.    release(head);
122.    head=tail=NULL;
123.    m_size=0;
124.  }
125.  void print_node(){
126.    Node *t=head;
127.    while(t!=NULL){
128.      cout<<t->val<<" ";
129.      t=t->next;
130.    }
131.    cout<<endl;
132.  }
133.  Node* begin(){return head;}
134.  Node* end(){return NULL;}
135. private:
136.  void release(Node *node){
137.    if(node == NULL) return;
138.    release(node->next);
139.    delete node;
140.  }
141. private:
142.  Node *head,*tail;
143.  int m_size;
144. };
145. 
146. int main(int argc, char *argv[])
147. {
148.  list l1;
149.  l1.push_back(3);
150.  l1.push_back(7);
151.  l1.push_back(4);
152.  l1.push_back(5);
153.  l1.print_node();
154.  l1.insert(0,9);
155.  l1.print_node();
156.  l1.insert(3,8);
157.  l1.print_node();
158.  l1.remove(0);
159.  l1.print_node();
160.  l1.remove(3);
161.  l1.print_node();
162.  cout<<"this is iterator:"<<endl;
163.  for(list::iterator it=l1.begin();it!=l1.end();it++) 
164.    cout<<*it<<" ";cout<<endl; 
165.  return 0;
166. }
167. /*
168. 3 7 4 5
169. 9 3 7 4 5
170. 9 3 7 8 4 5
171. 3 7 8 4 5
172. 3 7 8 5
173. this is iterator:
174. 3
175. 7
176. 8
177. 5
178. */

1. //结构体与模板类的对比 
2. #include <iostream>
3. #include <algorithm>
4. using namespace std;
5. bool cmp(const int a)
6. {
7.  return a<10;
8. }
9. template <typename T>//模板 
10. class mycmp
11. {
12. public:
13.   mycmp(T v){value=v;}
14.   bool operator ()(const T a)
15.   {
16.     return a<value;
17.   }
18. private:
19.   T value;
20. };
21. int main(int argc, char *argv[])
22. {
23.   int a[]={1,3,4,5,6,7,8,9,11};
24.   cout<<count_if(a,a+sizeof(a)/sizeof(a[0]),cmp)<<endl;//输出a中小于10的元素个数 
25.   cout<<count_if(a,a+sizeof(a)/sizeof(a[0]),mycmp<int>(10))<<endl;//输出a中小于10的元素个数 
26.   cout<<count_if(a,a+sizeof(a)/sizeof(a[0]),mycmp<int>(8))<<endl;//输出a中小于8的元素个数 
27.   return 0;
28. }
29. /*
30. 8
31. 8
32. 6
33. */