實驗一-線性表的插入和刪除

實驗報告提交郵箱：jsjrjjc_yuan@126.com實驗一線性表的插入和刪除一、實驗目的1、熟悉C++上機環(huán)境；2、掌握線性表的基本操作：查找、插入、刪除等運算在鏈接存儲結構上的運算。二、實驗內容【任務1】：閱讀理解閱讀后面的程序，并將其輸入到計算機中，調試成功，運算出結果。這個程序中我們創(chuàng)建了一個整數類型的升序單鏈表，演示了單鏈表的創(chuàng)建、輸出和刪除操作?！救蝿?】：完善功能構造函數node*insert(node*head,intnum)，實現(xiàn)把一個結點插入鏈表，仍保持鏈表上各結點的升序關系，并在主函數中完成對你所添加函數的測試。三、算法描述建立含有若干個元素的升序單鏈表，對其進行插入、刪除等操作，并將結果在屏幕上輸出。#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)實現(xiàn)把一個結點插入鏈表，仍保持鏈表上各結點的升序關系，你自己實現(xiàn)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個節(jié)點，返回該節(jié)點前一個節(jié)點的地址，否則返回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)<<"\