实验一-线性表的插入和删除

实验报告提交邮箱：jsjrjjc_yuan@126.com实验一线性表的插入和删除一、实验目的1、熟悉C++上机环境；2、掌握线性表的基本操作：查找、插入、删除等运算在链接存储结构上的运算。二、实验内容【任务1】：阅读理解阅读后面的程序，并将其输入到计算机中，调试成功，运算出结果。这个程序中我们创建了一个整数类型的升序单链表，演示了单链表的创建、输出和删除操作。【任务2】：完善功能构造函数node*insert(node*head,intnum)，实现把一个结点插入链表，仍保持链表上各结点的升序关系，并在主函数中完成对你所添加函数的测试。三、算法描述建立含有若干个元素的升序单链表，对其进行插入、删除等操作，并将结果在屏幕上输出。#include<iostream.h>structnode{intdata;node*next;};//建立一条有序链表node*create_sort(void){node*p1,*head=0;inta;cout<<"建立一条有序链表,请输入数据,以-1结束:";cin>>a;while(a!=-1){p1=newnode;p1->data=a;head=insert(head,p1);cin>>a;}return(head);}//输出链表上各个结点的值voidprint(constnode*head){constnode*p;p=head;cout<<"链表上各个结点的数据为:\n";while(p!=NULL){cout<<p->data<<'\t';p=p->next;}cout<<'\n';}//删除链表上具有指定值的一个结点node*delete_one_node(node*head,intnum){node*p1,*p2;if(head==NULL){cout<<"链表为空,无结点可删!\n";return(NULL);}if(head->data==num){p1=head;head=head->next;deletep1;cout<<"删除了一个结点!\n";}else{p2=p1=head;while(p2->data!=num&&p2->next!=NULL){p1=p2;p2=p2->next;}if(p2->data==num){p1->next=p2->next;deletep2;cout<<"删除了一个结点!\n";}elsecout<<num<<"链表上没找到要删除的结点!\n";}return(head);}//释放链表的结点空间voiddeletechain(node*h){node*p1;while(h){p1=h;h=h->next;deletep1;}cout<<"已释放链表的结点空间!\n";}intcount(node*head)//求链表的结点数{intn;node*p;p=head;n=0;while(p!=NULL){n=n+1;p=p->next;}return(n);}//删除链表上第k个结点node*delete_k_node(node*head,intk){intj=1;node*p,*p1;if(head==NULL){cout<<"链表为空,无结点可删!\n";return(NULL);}p=head;if(k==1){p=head;head=head->next;deletep;cout<<"删除了第一个结点!\n";}else{p=find(head,k-1);//查找第k-1个结点,并由p指向该结点if(p->next!=NULL){p1=p->next;p->next=p1->next;deletep1;cout<<"删除了第"<<k<<"个结点!\n";}return(head);}//函数insert(node*head,intnum)实现把一个结点插入链表，仍保持链表上各结点的升序关系，你自己实现voidmain(void){node*head;intnum;intk;head=create_sort();print(head);cout<<"结点数:"<<count(head)<<"\n";cout<<"输入要删除结点上的序号!\n";cin>>num;head=delete_k_node(head,k);print(head);cout<<"输入要删除结点上的整数!\n";cin>>num;head=delete_one_node(head,num);print(head);deletechain(head);cout<<"输入要插入的整数!\n"cin>>num;head=insert(head,num)；print(head);}#include<iostream>#include<iomanip>usingnamespacestd;structnode{intdata;node*next;};//建立一条升序单链表node*create_sort(void){ node*head=NULL; inta; cout<<"建立一条有序链表,请输入数据,以-1结束:\n"; while(!(cin>>a)) //输入整数，若不为整数则重输 { cerr<<"输入错误！请重新输入："; cin.clear(); cin.sync(); } while(a!=-1) { head=insert(head,a); while(!(cin>>a)) //输入整数，若不为整数则重输 { cerr<<"输入错误！请重新输入："; cin.clear(); cin.sync(); } } return(head);}//删除链表上具有指定值的一个结点node*delete_one_node(node*head,intnum){node*p1,*p2;if(head==NULL){cout<<"链表为空,无结点可删!\n";exit(0);}if(head->data==num){p1=head;head=head->next;deletep1;system("cls");cout<<"删除了一个结点!\n";}else{p2=p1=head;while(p2->data!=num&&p2->next!=NULL){p1=p2;p2=p2->next;}if(p2->data==num){p1->next=p2->next;deletep2;system("cls");cout<<"删除了一个结点!\n";}elsecout<<num<<"链表上没找到要删除的结点!\n";}return(head);}//求链表的结点数intcount(node*head){ intn; node*p; p=head; n=0; while(p!=NULL){ n=n+1; p=p->next; } return(n);}//释放链表的结点空间voiddeletechain(node*h){node*p1;while(h){p1=h;h=h->next;deletep1;}cout<<"已释放链表的结点空间!\n";}//删除链表上第k个结点node*delete_k_node(node*head,intk){ while((find(head,k)==NULL)&&(k!=1)) //如果此序号，则重新输入 { cout<<"该列表无此序号!请重新输入："; while(!(cin>>k)) //输入序号，若不为整数则重输 { cerr<<"输入错误！请重新输入："; cin.clear(); cin.sync(); } } intj=1; node*p,*p1; p=head; if(k==1){ p=head; head=head->next; deletep; system("cls"); cout<<"成功删除了第一个结点!\n"; } else{ p=find(head,k);//查找第k-1个结点,并由p指向该结点 p1=p->next; p->next=p1->next; deletep1; system("cls"); cout<<"成功删除了第"<<k<<"个结点!\n"; } return(head);}//查找第K个节点，返回该节点前一个节点的地址，否则返回NULLnode*find(node*head,intk){ if(head==NULL) { cout<<"链表为空,无结点可删!\n"; exit(0); } if(k<2) { returnNULL; } else { node*p; p=head; inti; for(i=2;(i<k)||(p->next==NULL);i++) { if(p->next==NULL) { returnNULL; } p=p->next; } returnp; }}node*insert(node*head,inta){ node*p1; p1=newnode; p1->data=a; p1->next=NULL; if(head==NULL) { returnp1; } else { node*p2; p2=head; if((p2->data)>(p1->data)) { p1->next=p2; returnp1; } while(p2->next!=NULL) { if(((p2->data)<=(p1->data))&&((p2->next->data)>=(p1->data))) { p1->next=p2->next; p2->next=p1; returnhead; } p2=p2->next; } p2->next=p1; returnhead; }}voidmain(void){node*head;intnum;intk;head=create_sort();print(head);cout<<"结点数:"<<count(head)<<"\