實驗報告-線性表基本操作

PAGEPAGE1計算機學院實驗報告專用紙實驗室：網絡實驗室機號：網20實驗日期：2008年3月21日姓名XXX班級課程名稱數據結構任課教師實驗項目名稱線性表基本操作指導教師實驗組別X同組者無教師評語及成績：實驗成績：教師簽字：（請按照實驗報告的有關要求書寫。一般必須包括：1、實驗目的；2、實驗內容；3、實驗步驟與方法；4、實驗數據與程序清單；5、出現(xiàn)的問題與解決方法；6、實驗結果、結果分析與體會等內容）1、實驗目的（1）掌握使用C或C++上機調試程序的基本方法；（2）掌握線性表的基本操作：初始化、插入、刪除、取數據元素等運算在順序存儲結構和鏈表存儲結構上的程序設計方法。2、實驗內容建立一個數據域定義為整型的單鏈表，根據輸入的整數，進行插入、刪除、取數據元素等操作。3、實驗步驟和方法（1）認真閱讀和掌握和本實驗相關的教材內容；（2）認真閱讀和掌握本章相關內容的程序，分析、理解給出的示例程序；（3）上機調試程序，并設計輸入數據運行程序；（4）保存和打印出程序的運行結果，并結合程序進行分析；（5）按照你對線性表的操作需要，重新改寫主程序并運行，打印出文件清單和運行結果。4、實驗數據與程序清單計算機學院實驗報告附頁姓名XXX班級實驗名稱線性表基本操作和簡單程序1）頭文件模塊#includeiostream.h>//頭文件#include<malloc.h>//庫頭文件動態(tài)分配內存空間typedefintelemtype;//定義數據域的類型typedefstructlinknode//定義結點類型{elemtypedata;//定義數據域structlinknode*next;//定義結點指針}nodetype;2）創(chuàng)建單鏈表nodetype*create()//建立單鏈表，由用戶輸入各結點data域之值，//以0表示輸入結束{elemtyped;//定義數據元素dnodetype*h=NULL,*s,*t;//定義結點指針inti=1;cout<<"建立一個單鏈表"<<endl;while(1){cout<<"輸入第"<<i<<"結點data域值：";cin>>d;if(d==0)break;//以0表示輸入結束if(i==1)//建立第一個結點{h=(nodetype*)malloc(sizeof(nodetype));//表示指針hh->data=d;h->next=NULL;t=h;//h是頭指針}else//建立其余結點{s=(nodetype*)malloc(sizeof(nodetype));s->data=d;s->next=NULL;t->next=s;t=s;//t始終指向生成的單鏈表的最后一個節(jié)點}i++;}returnh;}3）輸出單鏈表中的元素voiddisp(nodetype*h)//輸出由h指向的單鏈表的所有data域之值{nodetype*p=h;計算機學院實驗報告附頁姓名XXX班級實驗名稱線性表基本操作和簡單程序cout<<"輸出一個單鏈表:"<<endl<<"";if(p==NULL)cout<<"空表";while(p!=NULL){cout<<p->data<<"";p=p->next;}cout<<endl;}4）計算單鏈表的長度intlen(nodetype*h)//返回單鏈表的長度{inti=0;nodetype*p=h;while(p!=NULL){p=p->next;i++;}returni;}5）尋找第i個節(jié)點nodetype*find(nodetype*h,inti)//返回第i個節(jié)點的指針{nodetype*p=h;intj=1;if(i>len(h)||i<=0)returnNULL;//i上溢或下溢celse{while(p!=NULL&&j<1)//查找第i個節(jié)點，并由p指向該節(jié)點{j++;p=p->next;}returnp;}}6）單鏈表的插入操作nodetype*ins(nodetype*h,inti,elemtypex)//在單鏈表head中第i個節(jié)點//（i>=0）之后插入一個data域為x的節(jié)點{nodetype*p,*s;s=(nodetype*)malloc(sizeof(nodetype));//創(chuàng)建節(jié)點s計算機學院實驗報告附頁姓名XXX班級實驗名稱線性表基本操作和簡單程序s->data=x;s->next=NULL;if(i==0)//i=0:s作為該單鏈表的第一個節(jié)點{s->next=h;h=s;}else{p=find(h,i);//查找第i個節(jié)點，并由p指向該節(jié)點if(p!=NULL){s->next=p->next;p->next=s;}returnh;}}7）單鏈表的刪除操作nodetype*del(nodetype*h,inti)//刪除第i個節(jié)點{nodetype*p=h,*s;intj=1;if(i==1)//刪除第1個節(jié)點{h=h->next;free(p);}else{p=find(h,i-1);//查找第i-1個節(jié)點，并由p指向該節(jié)點if(p!=NULL&&p->next!=NULL){s=p->next;//s指向要刪除的節(jié)點p->next=s->next;free(s);}elsecout<<"輸入i的值不正確"<<endl;}returnh;}8）釋放節(jié)點空間voiddispose(nodetype*h)//釋放單鏈表的所有節(jié)點占用的空間{nodetype*pa=h,*pb;計算機學院實驗報告附頁姓名XXX班級實驗名稱線性表基本操作和簡單程序if(pa!=NULL){pb=pa->next;if(pb==NULL)//只有一個節(jié)點的情況free(pa);else{while(pb!=NULL)//有兩個及以上節(jié)點的情況{free(pa);pa=pb;pb=pb->next;}free(pa);}}}9)主程序模塊:#include"slink.h"http://包含頭文件slinkvoidmain(){nodetype*head;//定義節(jié)點指針變量head=create();//創(chuàng)建一個單鏈表disp(head);//輸出單鏈表cout<<"單鏈表長度:"<<len(head)<<endl;ins(head,2,0);//在第二個節(jié)點之后插入以0為元素的節(jié)點disp(head);//輸出新鏈表del(head,2);//刪除第二個節(jié)點disp(head);//輸出新鏈表}5、實驗結果建立一個單鏈表：輸入第1結點data域值：1輸入第2結點data域值：2輸入第3結點data域值：3輸入第4結點data域值：4輸入第5結點data域值：5輸入第6結點data域值：6輸入第7結點data域值：7輸入第8結點data域值：8輸入第9結點data域值：9輸入第10結點data域值0：輸出一個單鏈表：計算機學院