實(shí)驗(yàn)一-線性表的插入和刪除

實(shí)驗(yàn)報(bào)告提交郵箱：jsjrjjc_yuan@126.com實(shí)驗(yàn)一線性表的插入和刪除一、實(shí)驗(yàn)?zāi)康?、熟悉C++上機(jī)環(huán)境；2、掌握線性表的基本操作：查找、插入、刪除等運(yùn)算在鏈接存儲結(jié)構(gòu)上的運(yùn)算。二、實(shí)驗(yàn)內(nèi)容【任務(wù)1】：閱讀理解閱讀后面的程序，并將其輸入到計(jì)算機(jī)中，調(diào)試成功，運(yùn)算出結(jié)果。這個(gè)程序中我們創(chuàng)建了一個(gè)整數(shù)類型的升序單鏈表，演示了單鏈表的創(chuàng)建、輸出和刪除操作?！救蝿?wù)2】：完善功能構(gòu)造函數(shù)node*insert(node*head,intnum)，實(shí)現(xiàn)把一個(gè)結(jié)點(diǎn)插入鏈表，仍保持鏈表上各結(jié)點(diǎn)的升序關(guān)系，并在主函數(shù)中完成對你所添加函數(shù)的測試。三、算法描述建立含有若干個(gè)元素的升序單鏈表，對其進(jìn)行插入、刪除等操作，并將結(jié)果在屏幕上輸出。#include<iostream.h>structnode{intdata;node*next;};//建立一條有序鏈表node*create_sort(void){node*p1,*head=0;inta;cout<<"建立一條有序鏈表,請輸入數(shù)據(jù),以-1結(jié)束:";cin>>a;while(a!=-1){p1=newnode;p1->data=a;head=insert(head,p1);cin>>a;}return(head);}//輸出鏈表上各個(gè)結(jié)點(diǎn)的值voidprint(constnode*head){constnode*p;p=head;cout<<"鏈表上各個(gè)結(jié)點(diǎn)的數(shù)據(jù)為:\n";while(p!=NULL){cout<<p->data<<'\t';p=p->next;}cout<<'\n';}//刪除鏈表上具有指定值的一個(gè)結(jié)點(diǎn)node*delete_one_node(node*head,intnum){node*p1,*p2;if(head==NULL){cout<<"鏈表為空,無結(jié)點(diǎn)可刪!\n";return(NULL);}if(head->data==num){p1=head;head=head->next;deletep1;cout<<"刪除了一個(gè)結(jié)點(diǎn)!\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<<"刪除了一個(gè)結(jié)點(diǎn)!\n";}elsecout<<num<<"鏈表上沒找到要刪除的結(jié)點(diǎn)!\n";}return(head);}//釋放鏈表的結(jié)點(diǎn)空間voiddeletechain(node*h){node*p1;while(h){p1=h;h=h->next;deletep1;}cout<<"已釋放鏈表的結(jié)點(diǎn)空間!\n";}intcount(node*head)//求鏈表的結(jié)點(diǎn)數(shù){intn;node*p;p=head;n=0;while(p!=NULL){n=n+1;p=p->next;}return(n);}//刪除鏈表上第k個(gè)結(jié)點(diǎn)node*delete_k_node(node*head,intk){intj=1;node*p,*p1;if(head==NULL){cout<<"鏈表為空,無結(jié)點(diǎn)可刪!\n";return(NULL);}p=head;if(k==1){p=head;head=head->next;deletep;cout<<"刪除了第一個(gè)結(jié)點(diǎn)!\n";}else{p=find(head,k-1);//查找第k-1個(gè)結(jié)點(diǎn),并由p指向該結(jié)點(diǎn)if(p->next!=NULL){p1=p->next;p->next=p1->next;deletep1;cout<<"刪除了第"<<k<<"個(gè)結(jié)點(diǎn)!\n";}return(head);}//函數(shù)insert(node*head,intnum)實(shí)現(xiàn)把一個(gè)結(jié)點(diǎn)插入鏈表，仍保持鏈表上各結(jié)點(diǎn)的升序關(guān)系，你自己實(shí)現(xiàn)voidmain(void){node*head;intnum;intk;head=create_sort();print(head);cout<<"結(jié)點(diǎn)數(shù):"<<count(head)<<"\n";cout<<"輸入要刪除結(jié)點(diǎn)上的序號!\n";cin>>num;head=delete_k_node(head,k);print(head);cout<<"輸入要刪除結(jié)點(diǎn)上的整數(shù)!\n";cin>>num;head=delete_one_node(head,num);print(head);deletechain(head);cout<<"輸入要插入的整數(shù)!\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<<"建立一條有序鏈表,請輸入數(shù)據(jù),以-1結(jié)束:\n"; while(!(cin>>a)) //輸入整數(shù)，若不為整數(shù)則重輸 { cerr<<"輸入錯(cuò)誤！請重新輸入："; cin.clear(); cin.sync(); } while(a!=-1) { head=insert(head,a); while(!(cin>>a)) //輸入整數(shù)，若不為整數(shù)則重輸 { cerr<<"輸入錯(cuò)誤！請重新輸入："; cin.clear(); cin.sync(); } } return(head);}//刪除鏈表上具有指定值的一個(gè)結(jié)點(diǎn)node*delete_one_node(node*head,intnum){node*p1,*p2;if(head==NULL){cout<<"鏈表為空,無結(jié)點(diǎn)可刪!\n";exit(0);}if(head->data==num){p1=head;head=head->next;deletep1;system("cls");cout<<"刪除了一個(gè)結(jié)點(diǎn)!\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<<"刪除了一個(gè)結(jié)點(diǎn)!\n";}elsecout<<num<<"鏈表上沒找到要刪除的結(jié)點(diǎn)!\n";}return(head);}//求鏈表的結(jié)點(diǎn)數(shù)intcount(node*head){ intn; node*p; p=head; n=0; while(p!=NULL){ n=n+1; p=p->next; } return(n);}//釋放鏈表的結(jié)點(diǎn)空間voiddeletechain(node*h){node*p1;while(h){p1=h;h=h->next;deletep1;}cout<<"已釋放鏈表的結(jié)點(diǎn)空間!\n";}//刪除鏈表上第k個(gè)結(jié)點(diǎn)node*delete_k_node(node*head,intk){ while((find(head,k)==NULL)&&(k!=1)) //如果此序號，則重新輸入 { cout<<"該列表無此序號!請重新輸入："; while(!(cin>>k)) //輸入序號，若不為整數(shù)則重輸 { cerr<<"輸入錯(cuò)誤！請重新輸入："; cin.clear(); cin.sync(); } } intj=1; node*p,*p1; p=head; if(k==1){ p=head; head=head->next; deletep; system("cls"); cout<<"成功刪除了第一個(gè)結(jié)點(diǎn)!\n"; } else{ p=find(head,k);//查找第k-1個(gè)結(jié)點(diǎn),并由p指向該結(jié)點(diǎn) p1=p->next; p->next=p1->next; deletep1; system("cls"); cout<<"成功刪除了第"<<k<<"個(gè)結(jié)點(diǎn)!\n"; } return(head);}//查找第K個(gè)節(jié)點(diǎn)，返回該節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)的地址，否則返回NULLnode*find(node*head,intk){ if(head==NULL) { cout<<"鏈表為空,無結(jié)點(diǎn)可刪!\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<<"結(jié)點(diǎn)數(shù):"<<count(head)<<"\