標題: C++語言 線性表的插入和刪除 [打印本頁]
作者: daming    時間: 2014-12-30 01:28
標題: C++語言 線性表的插入和刪除
本帖最后由 daming 于 2014-12-30 02:14 編輯


  3. #include<iostream.h>

  5. struct node
  6. {
  7. int data;
  8. node *next;
  9. };

  11. //建立一條升序鏈表 (尾插法:最后建立的結(jié)點是表頭，故應(yīng)降序輸入)
  12. node *creat_sort()
  13. {
  14. node *p1,*head=NULL;
  15. int a;
  16. cout<<"建立一條有序鏈表，請輸入數(shù)據(jù)，以-1結(jié)束:\n";
  17. cin>>a;
  18. while(a!=-1){
  19.   p1=new node;
  20.   p1->data=a;
  21.   p1->next=head;
  22.   head=p1;
  23.   cin>>a;
  24. }
  25. return head;
  26. }

  28. //輸出鏈表上各個結(jié)點的值
  29. void print(const node *head)
  30. {
  31. const node *p;
  32. p=head;
  33. cout<<"鏈表上各個結(jié)點的數(shù)據(jù)為：\n";
  34. while(p!=NULL){
  35.   cout<<p->data<<'\t';
  36.   p=p->next;
  37. }
  38. cout<<endl;
  39. }

  41. //刪除鏈表上具有指定值的一個結(jié)點
  42. node *delete_one_node(node *head,int num)
  43. {
  44. node *p1,*p2;
  45. if(head==NULL){
  46.   cout<<"鏈表為空，無結(jié)點可刪!\n";
  47.   return NULL;
  48. }
  49. if(head->data==num){
  50.   p1=head;
  51.   head=head->next;
  52.   delete p1;
  53.   cout<<"刪除了一個結(jié)點!\n";
  54. }
  55. else{
  56.   p2=p1=head;
  57.   while(p2->data!=num&&p2->next!=NULL){
  58.    p1=p2;
  59.    p2=p2->next;
  60.   }
  61.   if(p2->data==num){
  62.    p1->next=p2->next;
  63.    delete p2;
  64.    cout<<"刪除了一個結(jié)點!\n";
  65.   }
  66.   else
  67.    cout<<num<<"鏈表上沒有找到要刪除的結(jié)點!\n";
  68. }
  69. return head;
  70. }

  72. //釋放鏈表的結(jié)點空間
  73. void deletechain(node *h)
  74. {
  75. node *p1;
  76. while(h){
  77.   p1=h;
  78.   h=h->next;
  79.   delete p1;
  80. }
  81. cout<<"已釋放鏈表的結(jié)點空間!\n";
  82. }

  84. //求鏈表的結(jié)點數(shù)
  85. int count(node *head)
  86. {
  87. int n;
  88. node *p;
  89. p=head;
  90. n=0;
  91. while(p!=NULL){
  92.   n=n+1;
  93.   p=p->next;
  94. }
  95. return n;
  96. }
  97. ////查找第k個結(jié)點
  98. node *find(node *head,int k)
  99. {
  100. int i;
  101. node *p;
  102. i=1;
  103. p=head;
  104. while(i<k){
  105.   i++;
  106.   p=p->next;
  107. }
  108. return p;
  109. }
  110. //刪除鏈表上第K個結(jié)點
  111. node *delete_k_node(node *head,int k)
  112. {
  113. int j=1;
  114. node *p,*p1;
  115. if(head==NULL){
  116.   cout<<"鏈表為空，無結(jié)點可刪!\n";
  117.   return NULL;
  118. }
  119. p=head;
  120. if(k==1){
  121.   p=head;
  122.   head=head->next;
  123.   delete p;
  124.   cout<<"刪除了第一個結(jié)點!\n";
  125. }
  126. else{
  127.   p=find(head,k-1); //查找第k-1個結(jié)點，并由p指向該結(jié)點
  128.   if(p->next!=NULL){
  129.    p1=p->next;
  130.    p->next=p1->next;
  131.    delete p1;
  132.    cout<<"刪除了第"<<k<<"個結(jié)點!\n";
  133.   }
  134. }
  135. return head;
  136. }

  138. //插入一個結(jié)點，不改變鏈表上的升序關(guān)系
  139. node *insert(node *head,int num)
  140. {
  141. node *p1,*p2,*p3;
  142. p1=head;
  143. p2=head->next;
  144. while(!(((p1->data)<=num)&&((p2->data)>=num))){
  145.   p1=p1->next;
  146.   p2=p2->next;
  147. }
  148. p3=new node;
  149. p3->data=num;
  150. p1->next=p3;
  151. p3->next=p2;
  152. return head;
  153. }

  155. //測試函數(shù)
  156. void main()
  157. {
  158. node *head;
  159. int num;
  160. head=creat_sort();
  161. print(head);
  162. cout<<"結(jié)點數(shù):"<<count(head)<<endl;
  163. cout<<"輸入要刪除結(jié)點上的序號!\n";
  164. cin>>num;
  165. head=delete_k_node(head,num);
  166. print(head);
  167. cout<<"輸入要刪除結(jié)點上的整數(shù)!\n";
  168. cin>>num;
  169. head=delete_one_node(head,num);
  170. print(head);
  171. cout<<"輸入要插入的整數(shù)!\n";
  172. cin>>num;
  173. head=insert(head,num);
  174. print(head);
  175. deletechain(head);
  176. }

  178. /**********************************************

  180. 建立一條有序鏈表，請輸入數(shù)據(jù)，以-1結(jié)束:
  181. 9 8 6 5 4 3 2 1 -1
  182. 鏈表上各個結(jié)點的數(shù)據(jù)為：
  183. 1       2       3       4       5       6       8       9
  184. 結(jié)點數(shù):8
  185. 輸入要刪除結(jié)點上的序號!
  186. 1
  187. 刪除了第一個結(jié)點!
  188. 鏈表上各個結(jié)點的數(shù)據(jù)為：
  189. 2       3       4       5       6       8       9
  190. 輸入要刪除結(jié)點上的整數(shù)!
  191. 2
  192. 刪除了一個結(jié)點!
  193. 鏈表上各個結(jié)點的數(shù)據(jù)為：
  194. 3       4       5       6       8       9
  195. 輸入要插入的整數(shù)!
  196. 7
  197. 鏈表上各個結(jié)點的數(shù)據(jù)為：
  198. 3       4       5       6       7       8       9
  199. 已釋放鏈表的結(jié)點空間!
  200. Press any key to continue
  201. **************************************/
復制代碼






歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1