标题: 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. //建立一条升序链表 (尾插法:最后建立的结点是表头，故应降序输入)
  12. node *creat_sort()
  13. {
  14. node *p1,*head=NULL;
  15. int a;
  16. cout<<"建立一条有序链表，请输入数据，以-1结束:\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. //输出链表上各个结点的值
  29. void print(const node *head)
  30. {
  31. const node *p;
  32. p=head;
  33. cout<<"链表上各个结点的数据为：\n";
  34. while(p!=NULL){
  35.   cout<<p->data<<'\t';
  36.   p=p->next;
  37. }
  38. cout<<endl;
  39. }

  41. //删除链表上具有指定值的一个结点
  42. node *delete_one_node(node *head,int num)
  43. {
  44. node *p1,*p2;
  45. if(head==NULL){
  46.   cout<<"链表为空，无结点可删!\n";
  47.   return NULL;
  48. }
  49. if(head->data==num){
  50.   p1=head;
  51.   head=head->next;
  52.   delete p1;
  53.   cout<<"删除了一个结点!\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<<"删除了一个结点!\n";
  65.   }
  66.   else
  67.    cout<<num<<"链表上没有找到要删除的结点!\n";
  68. }
  69. return head;
  70. }

  72. //释放链表的结点空间
  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<<"已释放链表的结点空间!\n";
  82. }

  84. //求链表的结点数
  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个结点
  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个结点
  111. node *delete_k_node(node *head,int k)
  112. {
  113. int j=1;
  114. node *p,*p1;
  115. if(head==NULL){
  116.   cout<<"链表为空，无结点可删!\n";
  117.   return NULL;
  118. }
  119. p=head;
  120. if(k==1){
  121.   p=head;
  122.   head=head->next;
  123.   delete p;
  124.   cout<<"删除了第一个结点!\n";
  125. }
  126. else{
  127.   p=find(head,k-1); //查找第k-1个结点，并由p指向该结点
  128.   if(p->next!=NULL){
  129.    p1=p->next;
  130.    p->next=p1->next;
  131.    delete p1;
  132.    cout<<"删除了第"<<k<<"个结点!\n";
  133.   }
  134. }
  135. return head;
  136. }

  138. //插入一个结点，不改变链表上的升序关系
  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. //测试函数
  156. void main()
  157. {
  158. node *head;
  159. int num;
  160. head=creat_sort();
  161. print(head);
  162. cout<<"结点数:"<<count(head)<<endl;
  163. cout<<"输入要删除结点上的序号!\n";
  164. cin>>num;
  165. head=delete_k_node(head,num);
  166. print(head);
  167. cout<<"输入要删除结点上的整数!\n";
  168. cin>>num;
  169. head=delete_one_node(head,num);
  170. print(head);
  171. cout<<"输入要插入的整数!\n";
  172. cin>>num;
  173. head=insert(head,num);
  174. print(head);
  175. deletechain(head);
  176. }

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

  180. 建立一条有序链表，请输入数据，以-1结束:
  181. 9 8 6 5 4 3 2 1 -1
  182. 链表上各个结点的数据为：
  183. 1       2       3       4       5       6       8       9
  184. 结点数:8
  185. 输入要删除结点上的序号!
  186. 1
  187. 删除了第一个结点!
  188. 链表上各个结点的数据为：
  189. 2       3       4       5       6       8       9
  190. 输入要删除结点上的整数!
  191. 2
  192. 删除了一个结点!
  193. 链表上各个结点的数据为：
  194. 3       4       5       6       8       9
  195. 输入要插入的整数!
  196. 7
  197. 链表上各个结点的数据为：
  198. 3       4       5       6       7       8       9
  199. 已释放链表的结点空间!
  200. Press any key to continue
  201. **************************************/
复制代码






欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1