數(shù)據(jù)結(jié)構(gòu)雙向鏈表

數(shù)據(jù)結(jié)構(gòu)實驗報告二〇一二年數(shù)據(jù)結(jié)構(gòu)《實驗1》實驗報告實驗項目1：線性表存儲及運(yùn)算學(xué)號姓名課程號實驗地點(diǎn)指導(dǎo)教師時間評語：按時完成實驗；實驗內(nèi)容和過程記錄完整；回答問題完整、正確；實驗報告的撰寫認(rèn)真、格式符合要求；無抄襲的行為。成績教師簽字線性表鏈?zhǔn)酱鎯Γp向鏈表）插入、刪除運(yùn)算1、預(yù)習(xí)要求：線性表的插入、刪除相關(guān)概念及運(yùn)算，完成線性表元素的插入、刪除。2、實驗?zāi)康模海?）了解線性表的插入、刪除相關(guān)概念；（2）理解線性表的插入、刪除過程和結(jié)構(gòu)定義；（3）掌握算法轉(zhuǎn)換為程序的過程中的變化。3、實驗內(nèi)容及要求：（1）分別建立包含10個數(shù)據(jù)元素的鏈?zhǔn)酱鎯€性表；（2）從鍵盤輸入一個數(shù)據(jù)元素，插入到線性表中第k（包含0號位置）個位置；（3）從鍵盤輸入一個數(shù)據(jù)元素關(guān)鍵字或位置k（包含1號位置），從線性表中刪除相應(yīng)數(shù)據(jù)元素；（4）給出程序及插入、刪除前和插入、刪除后線性表結(jié)果。4、實驗設(shè)備（環(huán)境）及要求硬件：支持IntelPentiumⅡ及其以上CPU，內(nèi)存128MB以上、硬盤1GB以上容量的微機(jī)。軟件：配有Windows98/2000/XP操作系統(tǒng)，安裝VisualC++。5、實驗時間：6學(xué)時6、該文檔的文件名不要修改，存入<學(xué)號><姓名>命名的文件夾中7、該表中的數(shù)據(jù)只需填空，已有內(nèi)容不要修改實驗結(jié)果（運(yùn)行結(jié)果界面及源程序，運(yùn)行結(jié)果界面放在前面）：插入結(jié)果：刪除結(jié)果：//頭文件#defineStudentEType#defineHeadETypeint#include<iostream.h>#include<stdlib.h>#include<string.h>#include<iomanip.h>//以下是數(shù)據(jù)類型的定義structStudent{ charname[8]; charnumber[8]; charsex[6]; intage; charplace[10];};structDoubleNode{ ETypedata; DoubleNode*plink; DoubleNode*nlink;};structHeadNode{ HeadETypeHdata; DoubleNode*first;};typedefHeadNode*DoubleChainList;//voidCreatDoubleChainList(DoubleChainList&L){//創(chuàng)建一個空雙向鏈表 L=newHeadNode; L->first=NULL; //L->Hdate="HeadNode類型的數(shù)據(jù)值"}voidOutputDoubleChainList(DoubleChainList&L){//逐個地輸出鏈表L中的數(shù)據(jù)元素 DoubleNode*current=L->first; cout<<"L->first-》"; while(current) { current=current->nlink; cout<<"nlink"<<"--->"; } cout<<"NULL"<<endl; cout<<endl; current=L->first; cout<<setiosflags(ios::left)<<setw(11)<<"學(xué)號:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->data.number; current=current->nlink; } cout<<endl; current=L->first; cout<<setw(11)<<"姓名:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->; current=current->nlink; } cout<<endl; current=L->first; cout<<setw(11)<<"性別:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->data.sex; current=current->nlink; } cout<<endl; current=L->first;cout<<setw(11)<<"年齡:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->data.age; current=current->nlink; } cout<<endl; current=L->first; cout<<setw(11)<<"住址:"; while(current) { cout<<setw(9)<<setiosflags(ios::left)<<current->data.place; current=current->nlink; } cout<<endl; current=L->first; cout<<"NULL<---"; while(current) { current=current->nlink; cout<<"plink"<<"<---"; }cout<<endl;}intLengthDoubleChainList(DoubleChainList&L){//返回鏈表的節(jié)點(diǎn)數(shù) DoubleNode*current=L->first; intlen=0; while(current) { len++; current=current->nlink; } returnlen;}voidDestoryDoubleChainList(DoubleChainList&L){//刪除鏈表中所有數(shù)據(jù)節(jié)點(diǎn)，并釋放空間,從前向后依次刪除 DoubleNode*current=L->first; while(L->first) { current=current->nlink; deleteL->first; L->first=current; }}boolGetElemDoubleChainList(DoubleChainList&L,intk,EType&result){//L中第k個元素取至x中，如不存在返回false，存在返回true if(k<1)returnfalse; DoubleNode*current=L->first; intindex=1; while(index<k&¤t) { current=current->nlink; index++; } if(current) { result=current->data; returntrue; } returnfalse;//k值太大，不存在第k個節(jié)點(diǎn)}DoubleNode*SearchDoubleChainList(DoubleChainList&L,EType&x){//查找關(guān)鍵字，如果找到返回x的地址，否則返回NULL DoubleNode*current=L->first; while(current&&strcmp(current->data.number,x.number)) current=current->nlink; if(current)returncurrent; returnNULL;}boolInsertDoubleChainList(DoubleChainList&L,intk,EType&x){//在鏈表L中的第k個數(shù)據(jù)元素之后插入新節(jié)點(diǎn) if(k<0)returnfalse; intindex=1; DoubleNode*current=L->first; while(current&&index<k) {//找到第k個數(shù)據(jù)節(jié)點(diǎn) index++; current=current->nlink; } if(k>0&&!current)returnfalse; DoubleNode*q=newDoubleNode; q->data=x; if(k) {//插在current之后 q->nlink=current->nlink; q->plink=current; DoubleNode*p=current->nlink; if(p) p->plink=q; current->nlink=q; } else {//作為第一個元素節(jié)點(diǎn)插入 q->nlink=L->first; q->plink=NULL; DoubleNode*p=L->first; if(p) p->plink=q; L->first=q; } returntrue;}boolDeleteDoubleChainList(DoubleChainList&L,intk){//刪除第k個數(shù)據(jù)元素節(jié)點(diǎn) if(k<1||!L->first)returnfalse; DoubleNode*current=L->first;DoubleNode*p; if(k==1) {//刪除的是第一個節(jié)點(diǎn) p=current->nlink; if(p) p->plink=NULL; L->first=p; } else { intindex=1; while(index<k-1&¤t) { current=current->nlink; index++; } while(current||current->nlink) { p=current->nlink; if(p->nlink) { current->nlink=p->nlink; deletep; p=current->nlink; p->plink=current; } else { current->nlink=NULL; deletep; }returntrue; } } returntrue;}boolMoveFirstDoubleChainList(DoubleChainList&L,intk){//在雙向鏈表L中將第k個數(shù)據(jù)元素移至表首 if(k<1||!L->first)returnfalse; DoubleNode*current=L->first; DoubleNode*p; if(k==1) returntrue; //是鏈表中第一個結(jié)點(diǎn),直接返回 else { DoubleNode*q=L->first; for(intindex=1;index<k-1&&q;index++) q=q->nlink; if(!q||!q->nlink)returnfalse; current=q->nlink;//current指向第k個結(jié)點(diǎn) if(current->nlink) { q->nlink=current->nlink; p=current->nlink; p->plink=q; } else q->nlink=NULL; } p=L->first; current->nlink=L->first;//被刪除結(jié)點(diǎn)current指向第一個結(jié)點(diǎn) p->plink=current; current->plink=NULL; L->first=current; //表頭指針指向被刪除結(jié)點(diǎn)current returntrue;}voidInvertDisplayDoubleChainList(DoubleNode*p){//遞歸方式逆向輸出線性表L中的所有元素 if(p) { InvertDisplayDoubleChainList(p->nlink); cout<<p->data.age<<"--->"; }}intSearchDeleteDoubleChainList(DoubleChainList&L,EType&x){//查找關(guān)鍵字，如果找到返回x的地址，否則返回NULL DoubleNode*current=L->first; intindex=1; while(current&&strcmp(current->data.number,x.number)) { current=current->nlink; index++; } if(current)returnindex; return0; }boolInvertDoubleChainList(DoubleChainList&L){//實現(xiàn)雙向鏈表L數(shù)據(jù)元素逆向 DoubleNode *p=L->first; DoubleNode *current; L->first=NULL; while(p) { current=p; p=p->nlink; current->nlink=L->first; L->first=current; } returntrue;}//下面是主程序voidmain(){ DoubleNode *p; DoubleChainList L; EType x,result; intn,choice,k,m; CreatDoubleChainList(L);//創(chuàng)建一個鏈表 cout<<"請輸入學(xué)生人數(shù)："<<endl;cin>>n; for(inti=0;i<n;i++) { p=newDoubleNode; cout<<"name=";cin>>p->; cout<<"number=";cin>>p->data.number; cout<<"sex=";cin>>p->data.sex; cout<<"age=";cin>>p->data.age; cout<<"place=";cin>>p->data.place; cout<<endl; p->nlink=L->first; L->first=p; } while(true) { cout<<endl; cout<<"************************線性表雙向鏈表存儲的運(yùn)算*****************"<<endl; cout<<"*1--------輸出鏈表中的所有元素*"<<endl; cout<<"*2--------計算鏈表長度*"<<endl;cout<<"*3-------在鏈表中查找符合查找關(guān)鍵字searchkey(學(xué)號)的元素刪除*"<<endl; cout<<"*4--------在鏈表中查找第K個元素*"<<endl; cout<<"*5--------在鏈表中查找符合查找關(guān)鍵字searchkey(學(xué)號)的元素*"<<endl; cout<<"*6--------在鏈表中插入新元素到第k個元素后面*"<<endl; cout<<"*7--------在鏈表中刪除第k個元素*"<<endl; cout<<"*8--------將第K個元素移至第1個元素位置*"<<endl; cout<<"*9--------刪除第m到第n個結(jié)點(diǎn)*"<<endl; cout<<"*10-------鏈表逆向*"<<endl;cout<<"*11--------刪除鏈表中的所有數(shù)據(jù)元素節(jié)點(diǎn)*"<<endl; cout<<"*0--------退出*"<<endl; cout<<"******************************************************************"<<endl; cout<<"請選擇處理功能："; cin>>choice; cout<<endl; system("cls"); switch(choice) { case1: {// 1--------輸出線性表中的所有元素 cout<<"************輸出鏈表中的所有元素*************"<<endl; cout<<endl; OutputDoubleChainList(L); cout<<endl; break; }case2: {//2---------計算鏈表長度 cout<<"************計算鏈表長度**********"<<endl<<endl; cout<<"此操作前鏈表狀態(tài)："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"線性表長度="<<LengthDoubleChainList(L)<<endl<<endl; break; } case3: {//3-------在鏈表中查找符合查找關(guān)鍵字searchkey(學(xué)號)的元素刪除cout<<"************在鏈表中刪除第k個元素**********"<<endl<<endl; cout<<"此操作前鏈表狀態(tài)："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"輸入查找刪除關(guān)鍵字number:"<<endl;cin>>x.number; cout<<"查找刪除結(jié)果:"<<endl<<endl; k=SearchDeleteDoubleChainList(L,x); if(DeleteDoubleChainList(L,k)) OutputDoubleChainList(L); else cout<<"K值范圍不正確！"<<endl<<endl; break; } case4: {//4--------在鏈表中查找第K個元素cout<<"************在鏈表中查找第K個元素**********"<<endl<<endl; cout<<"此操作前鏈表狀態(tài)："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"請輸入要查找第幾個元素"<<endl;cin>>k; if(GetElemDoubleChainList(L,k,result)) { cout<<"第"<<k<<"個數(shù)據(jù)元素的值"<<endl; cout<<"姓名"<<<<'\t'; cout<<"學(xué)號"<<result.number<<'\t'; cout<<"性別"<<result.sex<<'\t'; cout<<"年齡"<<result.age<<'\t'; cout<<"住址"<<result.place<<endl; } else cout<<"k值范圍不對"<<endl; break; } case5: {//5--------在鏈表中查找符合查找關(guān)鍵字searchkey(學(xué)號)的元素cout<<"************在鏈表中查找符合查找關(guān)鍵字searchkey(學(xué)號)的元素**********"<<endl<<endl; cout<<"此操作前鏈表狀態(tài)："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"輸入查找關(guān)鍵字number:"<<endl;cin>>x.number; p=SearchDoubleChainList(L,x); cout<<"查找結(jié)果:"<<endl<<endl; if(p) { cout<<"學(xué)號："<<p->data.number<<endl; cout<<"姓名："<<p-><<endl; cout<<"性別："<<p->data.sex<<endl; cout<<"年齡："<<p->data.age<<endl; cout<<"住址："<<p->data.place<<endl<<endl; } else cout<<"?。。?！無此學(xué)號的人！！?。?<<endl<<endl; break; } case6: {//6--------在鏈表中插入新元素到第k個元素后面 cout<<"************在鏈表中插入新元素到第k個元素后面**********"<<endl<<endl; cout<<"此操作前鏈表狀態(tài)："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"輸入插入點(diǎn)K值：";cin>>k; cout<<"輸入要插入的數(shù)據(jù)值X："<<endl<<endl;cout<<"name=";cin>>; cout<<"number=";cin>>x.number; cout<<"sex=";cin>>x.sex; cout<<"age=";cin>>x.age; cout<<"place=";cin>>x.place; cout<<"插入數(shù)據(jù)X到第"<<k<<"個記錄后面的結(jié)果:"<<endl<<endl; if(InsertDoubleChainList(L,k,x)) OutputDoubleChainList(L); else cout<<"K值范圍不正確！"<<endl<<endl; break; } case7: {//7--------在鏈表中刪除第k個元素 cout<<"************在鏈表中刪除第k個元素**********"<<endl<<endl; cout<<"此操作前鏈表狀態(tài)："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"刪除第幾個結(jié)點(diǎn)：";cin>>k; cout<<"刪除第"<<k<<"個結(jié)點(diǎn)后的結(jié)果:"<<endl<<endl; if(DeleteDoubleChainList(L,k)) OutputDoubleChainList(L); else cout<<"K值范圍不正確！"<<endl<<endl; break; } case8: {//8--------將第K個元素移至第1個元素位置cout<<"************將第K個元素移至第1個元素位置**********"<<endl<<endl; cout<<"此操作前鏈表狀態(tài)："<<endl<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"請輸入想要移至第1個元素位置的編號k:";cin>>k; cout<<"進(jìn)行此操作后的結(jié)果如下:"<<endl; if(MoveFirstDoubleChainList(L,k)) {OutputDoubleChainList(L); } else cout<<"K值范圍不正確！"<<endl<<endl; break; } case9: //9---------刪除第m到第n個結(jié)點(diǎn) { cout<<"*******************************鏈表原狀態(tài)*****************************"<<endl; OutputDoubleChainList(L); cout<<endl; cout<<"**********************在鏈表中刪除第i到第j個結(jié)點(diǎn)**********************"<<endl<<endl; cout<<"輸入起點(diǎn)m值：";c