|
還有一個月，各個公司都會開始秋季招聘了，作為即將成為一個被面試的人，說實話，我很緊張也很激動，緊張的原因是我沒有進(jìn)行過技術(shù)面試，激動的原因是要看看這大學(xué)三年我到底學(xué)的怎么樣，到底哪些個公司會要我。而與此同時，學(xué)校還在進(jìn)行著每年一度的課程很多的小學(xué)期，耽誤著大家出去實習(xí)，耽誤著大家準(zhǔn)備找工作的時間，不知道學(xué)院的領(lǐng)導(dǎo)們到底是怎么想的。。 今天上午，把以前寫過的關(guān)于鏈表的代碼重新練習(xí)了一下，不全，只是一些常見的，包括：建立鏈表的相關(guān)操作，求鏈表的長度，對鏈表實現(xiàn)冒泡排序，完成單鏈表的逆序和逆序輸出，合并兩個已經(jīng)排好序的鏈表。 下面是代碼： 
 1 #include <iostream> 2 3 using namespace std; 4 5 struct Node 6 { 7 public: 8 int data; 9 Node *next; 10 Node(){}; 11 Node(int i) 12 { 13 data = i; 14 next = NULL; 15 } 16 }; 17 class List 18 { 19 public: 20 Node *head; 21 Node *curr; 22 List() 23 { 24 head = NULL; 25 curr = NULL; 26 } 27 void insert_from_tail(Node *tmp) 28 { 29 if(head == NULL) 30 { 31 head = new Node(); 32 head->next = tmp; 33 curr = tmp; 34 } 35 else 36 { 37 curr->next = tmp; 38 curr = tmp; 39 } 40 } 41 int length()const 42 { 43 int count = 0; 44 Node *tmp = head->next; 45 while(tmp != NULL) 46 { 47 tmp = tmp->next; 48 count++; 49 } 50 return count; 51 } 52 }; 53 //完成兩個節(jié)點(diǎn)的值的交換 54 void Swap(Node *t1,Node *t2) 55 { 56 int tmp = t1->data; 57 t1->data = t2->data; 58 t2->data = tmp; 59 } 60 //冒泡排序 61 void bubble_sort(List &l) 62 { 63 int len = l.length(); 64 for(int i = len-1 ; i > 0 ; --i) 65 { 66 Node *tmp = l.head->next; 67 for(int j = 0 ; j < i ; ++j) 68 { 69 if(tmp->data > tmp->next->data) 70 { 71 Swap(tmp,tmp->next); 72 } 73 tmp = tmp->next; 74 } 75 } 76 } 77 //完成單鏈表的逆序并輸出 78 void reverse_print(List &l) 79 { 80 if(l.head == NULL || l.head->next == NULL)//鏈表是空 81 { 82 return ; 83 } 84 Node *p1 = l.head->next; 85 Node *p2 = l.head->next->next; 86 p1->next = NULL;//這里一定要讓p1->next = NULL，因為逆序后p1實際上是鏈表的最后一個節(jié)點(diǎn) 87 while(p2 != NULL) 88 { 89 Node *tmp = p2->next; 90 p2->next = p1; 91 p1 = p2; 92 p2 = tmp; 93 } 94 l.head->next = p1;//注意這里第一個節(jié)點(diǎn)是p1，而不是p2 95 Node *p = l.head->next; 96 while(p != NULL) 97 { 98 cout<<p->data<<" "; 99 p = p->next; 100 } 101 cout<<endl; 102 } 103 //合并兩個單鏈表 104 void merge(List l1 ,List l2 ,List &l3) 105 { 106 Node *p1 = l1.head->next; 107 Node *p2 = l2.head->next; 108 while(p1 != NULL || p2 != NULL) 109 { 110 if(p2 == NULL || (p1 != NULL && p1->data <= p2->data)) 111 { 112 l3.insert_from_tail(p1); 113 p1= p1->next; 114 } 115 else 116 { 117 l3.insert_from_tail(p2); 118 p2 = p2->next; 119 } 120 } 121 } 122 int main() 123 { 124 /*---------------------------------------*/ 125 //初始化單鏈表 126 int i; 127 Node *p; 128 List l; 129 Node t[5] = {2,1,4,3,0}; 130 for(i = 0 ; i < 5 ; ++i) 131 { 132 l.insert_from_tail(&t[i]); 133 } 134 //單鏈表的長度 135 cout<<"初始化單鏈表的長度是："; 136 cout<<l.length()<<endl; 137 cout<<"初始化鏈表中的數(shù)據(jù)是："; 138 p = l.head->next; 139 while(p != NULL) 140 { 141 cout<<p->data<<" "; 142 p = p->next; 143 } 144 cout<<endl; 145 146 /*----------------------------------------*/ 147 //排序后的結(jié)果 148 bubble_sort(l); 149 cout<<"排序后鏈表中的數(shù)據(jù)是："; 150 p = l.head->next; 151 while(p != NULL) 152 { 153 cout<<p->data<<" "; 154 p = p->next; 155 } 156 cout<<endl; 157 /*----------------------------------------*/ 158 //逆序單鏈表 159 cout<<"逆序后鏈表中的數(shù)據(jù)是："; 160 reverse_print(l); 161 /*----------------------------------------*/ 162 //合并兩個拍好序的單鏈表 163 List l1,l2,l3; 164 Node t1[4] = {1,3,4,5}; 165 Node t2[4] = {2,6,7,8}; 166 for(i = 0 ; i < 4 ; ++i) 167 { 168 l1.insert_from_tail(&t1[i]); 169 l2.insert_from_tail(&t2[i]); 170 } 171 cout<<"{1，3，4，5}和{2，6，7，8}合并后的鏈表中的數(shù)據(jù)："; 172 merge(l1,l2,l3); 173 p = l3.head->next; 174 while(p != NULL) 175 { 176 cout<<p->data<<" "; 177 p = p->next; 178 } 179 cout<<endl; 180 return 0; 181 } 前一段時間問過一個去了人人網(wǎng)C++部門的師哥，說想去大公司的話，代碼能力必須過關(guān)哦~~~~ |
|
|
