第一篇：2012《數(shù)據(jù)結(jié)構(gòu)》上機實驗報告 鏈表
西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告
西華數(shù)學(xué)與計算機學(xué)院上機實踐報告
課程名稱：數(shù)據(jù)結(jié)構(gòu) 指導(dǎo)教師：唐劍梅 上機實踐名稱：
上機實踐編號：1 年級： 2011 姓名：蔣俊 學(xué)
號
：
***
上機實踐成績：
上機實踐日期：2012-11-6
上機實踐時間：8:00-9:30
一、實驗?zāi)康?/p>
1.了解線性表的邏輯結(jié)構(gòu)特性，以及這種特性在計算機內(nèi)的兩種存儲結(jié)構(gòu)。
2.重點是線性表的基本操作在兩種存儲結(jié)構(gòu)上的實現(xiàn)；其中以鏈表的操作為側(cè)重點；并進一步學(xué)習(xí)程序設(shè)計方法。
3.掌握棧這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲結(jié)構(gòu)，并能在現(xiàn)實生活中靈活運用。
4.掌握隊列這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲結(jié)構(gòu)，并能在現(xiàn)實生活中靈活運用。
5.了解和掌握遞歸程序設(shè)計的基本原理和方法。
6.掌握使用 C++面向?qū)ο蟮某绦蛟O(shè)計技術(shù)設(shè)計數(shù)據(jù)結(jié)構(gòu)源程序的方法。
二、實驗內(nèi)容
1.熟悉前面的【程序示例2】，按照約瑟夫問題的方法2，試著不設(shè)頭結(jié)點改寫原來的程序，上機調(diào)試運行。
2.用鏈表建立通訊錄。通訊錄內(nèi)容有：姓名、通訊地址、電話號碼。
要求：（1）通訊錄按姓名項的字母順序排列；
（2）能查找通訊錄中某人的信息；
[提示] 用鏈表來存放這個通訊錄，一個人的信息作為一個結(jié)點。成鏈的過程可以這樣考慮：先把頭結(jié)點后面的
西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告
char name[20];
// 姓名子域
NodeType *next;
// 指針域
};class Jose
//類聲明
{ private: NodeType *Head;
public:
Jose(){};
~Jose(){ };
void creat();
void outs();
};void Jose::creat(){ int i=0, n;
NodeType *newp, *pre;
cout<<“n
輸入總?cè)藬?shù) n=”;cin>>n;
pre=new NodeType;
Head=new NodeType;
pre->num=1;
cout<<“n 編號”<<1<<“的人
姓名=”;
cin>>pre->name;
cout<<“n 密碼”<<1<<“的人
密碼=”;
cin>>pre->psw;
Head=pre;
Head->next=Head;
for(i=1;i { newp=new NodeType; newp->num=i+1; cout<<“n 編號”< 姓名=”;cin>>newp->name; cout<<“n 密碼”< 密碼=”; cin>>newp->psw; newp->next=Head; pre->next=newp; pre=newp; } } void Jose::outs() { int m,i; NodeType *q=Head, *p; cout<<“n 輸入m值(m>=2)”;cin>>m; cout<<“n 根據(jù)m值，開始報數(shù)輸出：”< while(q->next!=q) 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 { for(i=1;i cout<<“編號為：”< cout<<“n 編號為:”< m=q->psw; p->next=q->next;delete q; q=p->next; } cout<<“編號為：”< cout<<“n 編號為:”< delete q;} int main() { Jose h; h.creat(); h.outs(); return 0;} 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 { char Add[20]; char name[20]; char tel[20]; };struct NodeType { ElemType data; NodeType *next;};class Sqlist { private: NodeType *Head; public: Sqlist(); ~Sqlist(); void creat(); void Insert(ElemType x); void Delet(ElemType x); void PrintOut(); };Sqlist::Sqlist(){ Head=new NodeType;Head->next=NULL;strcpy(Head->data.name,“姓名”);strcpy(Head->data.Add,“地址”);strcpy(Head->data.tel,“電話號碼”);} Sqlist::~Sqlist(){ NodeType *p=Head->next; while(p!=NULL) {Head->next=p->next; delete p; p=Head->next;} } void Sqlist::creat() //初步建立一個通訊錄 { NodeType*p,*s,*q;ElemType x; 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 int a;q=Head;cout<<“n 輸入姓名：”;cin>>x.name;cout<<“n 輸入通訊地址：”;cin>>x.Add;cout<<“n 輸入電話號碼：”;cin>>x.tel;p=new NodeType;p->data=x;Head->next=p;p->next=NULL;cout<<“輸入一個數(shù)。若為-1，結(jié)束輸入:”< while(a!=-1){ cout<<“n 輸入姓名：”;cin>>x.name;cout<<“n 輸入通訊地址：”;cin>>x.Add;cout<<“n 輸入電話號碼：=”;cin>>x.tel;s=new NodeType;s->data=x;if(strcmp(s->data.name,p->data.name)>0){ p->next=s;s->next=NULL; p=s;} else{ s->next=p;q->next=s;} q=q->next; cout<<“輸入一個數(shù)。若為-1，結(jié)束輸入:”< 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 s->data=x;q=Head;p=q->next;while(p!=NULL&&strcmp(p->data.name,x.name)<0){q=p;p=p->next;} s->next=p;q->next=s;} void Sqlist::Delet(ElemType x)//刪除 { NodeType *p,*q;q=Head;p=Head->next;while(p!=NULL&&strcmp(p->data.name,x.name)!=0){q=p;p=p->next;} if(p!=NULL){ q->next=p->next;delete p;cout<<“刪除結(jié)點成功”< { NodeType *p;p=Head->next;while(p!=NULL){ cout< data.name<<“ ”;cout< data.tel<<“ ”;cout< data.Add<<“ ”;p=p->next;} cout< Sqlist as; cout<<“n 通訊錄演示”; do{ cout<<“nn”; cout<<“nn 1.初步建立一個通訊錄（單鏈表） ”; 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 cout<<“nn 2.插入新的電話記錄 ”; cout<<“nn 3.刪除一個電話記錄”; cout<<“nn 4.結(jié)束程序”; cout<<“n******************************** ”; cout<<“n 請輸入你的選擇(1,2,3,4)”;cin>>k;switch(k){ case 1:{ as.creat();as.PrintOut();}break; case 2:{ cout<<“n 插入的數(shù)據(jù) 姓名”;cin>>e.name; cout<<“n 插入的數(shù)據(jù) 電話號”;cin>>e.tel; cout<<“n 插入的數(shù)據(jù) 地址”;cin>>e.Add; as.Insert(e);as.PrintOut(); }break; case 3:{ cout<<“n 被刪除的姓名= ”; cin>>e.name; as.Delet(e); as.PrintOut(); }break; default:break; } }while(k>=1&&k<4); cout<<“n 再見!”; return 0;} 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 const int MAXSIZE=100; // 數(shù)組的容量 class SqStack { private: ElemType elem[MAXSIZE]; int top; public: SqStack(); ~SqStack(){}; void SqStack::push(ElemType e); ElemType SqStack::pop(); void SqStack::PrintOut(); int SqStack::IsEmpty(); void f(ElemType N,ElemType M);};void SqStack::f(ElemType N,ElemType M){ SqStack s; ElemType e;while(N){ s.push(N%M); N=N/M;} while(!s.IsEmpty()){ e=s.pop(); if(e>=10) { e=e%10; switch(e) { case 1:cout<<“b”< case 2:cout<<“c”< case 3:cout<<“d”< case 4:cout<<“e”< case 5:cout<<“f”< default:cout<<“a”< } } else cout< 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 } cout< {cout<<“棧滿溢出”< return; } else{top++; elem[top]=e;} } ElemType SqStack::pop(){ElemType x; if(top==0) { cout<< “ 棧為空，不能出棧操作”< else { x=elem[top]; top--; return x;} } void SqStack::PrintOut() {int k; cout<<“n PrintOut Data:n”; for(k=top;k>=1;k--)cout< cout< else return 0;} void main(){ ElemType a,m;cout<<“請輸入一個正整數(shù):”< 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 五、總結(jié) 通過本次實驗，我熟悉了鏈表的操作，了解了線性表在現(xiàn)實生活中的運用，認識了順序存儲和鏈式存儲這兩種結(jié)構(gòu)。本次上機實踐基本完成了實驗內(nèi)容，但完成的不是很好，以后需要更加努力地掌握基本的知識。實驗內(nèi)容對于隊列的運用沒有涉及，希望以后有所涉及。 西華大學(xué)數(shù)計學(xué)院學(xué)生上機實踐報告 數(shù)據(jù)結(jié)構(gòu)實驗報告 課程 數(shù)據(jù)結(jié)構(gòu) _ 院 系 專業(yè)班級 實驗地點 姓 名 學(xué) 號 實驗時間 指導(dǎo)老師 數(shù)據(jù)結(jié)構(gòu)上機實驗報告1 一﹑實驗名稱： 實驗一——鏈表 二﹑實驗?zāi)康模?/p> 1.了解線性表的邏輯結(jié)構(gòu)特性； 2.熟悉鏈表的基本運算在順序存儲結(jié)構(gòu)上的實現(xiàn)，熟練掌握鏈式存儲結(jié)構(gòu)的描述方法； 3.掌握鏈表的基本操作（建表、插入、刪除等）4.掌握循環(huán)鏈表的概念，加深對鏈表的本質(zhì)的理解。5.掌握運用上機調(diào)試鏈表的基本方法 三﹑實驗內(nèi)容： （1）（2）（3）（4）創(chuàng)建一個鏈表 在鏈表中插入元素 在鏈表中刪除一個元素 銷毀鏈表 四﹑實驗步驟與程序 #include LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L; cout<<“請輸入一個鏈表：”< for(int i=0;i { p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data; p->next=q->next; q->next=p; q=p; } } int PrintLinkList(LinkList &L){//輸出鏈表L的數(shù)據(jù)元素 LinkList p; } void LinkListLengh(LinkList &L){//計算鏈表L的數(shù)據(jù)元素個數(shù)。int i=0;p=L->next;if(L->next==NULL){ } cout<<“鏈表的數(shù)據(jù)元素為:”;while(p) { cout< data<<“ ”; p=p->next;} cout<<“鏈表沒有元素!”< } LinkList p;p=L->next;while(p){ i++; p=p->next; } cout<<“鏈表的數(shù)據(jù)元素個數(shù)為:”< LinkList p,s;int j=0;p=L; while(p&&j } if(!p||j>i-1){ p=p->next;++j; } } cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//刪除鏈表L的第I個數(shù)據(jù)元素。 LinkList p,q;int j=0;p=L;while(p->next&&j } if(!(p->next)||j>i-1){ p=p->next;++j; } } cout<<“刪除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//銷毀鏈表L。 LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q; free(p);} p=q; free(L); cout<<“鏈表已經(jīng)被銷毀!”< LinkList L; int i,j,x;cout<<“第一次數(shù)據(jù)結(jié)構(gòu)上機實驗—鏈表”< CreatLinkList(L,j); LinkListLengh(L); PrintLinkList(L); cout<<“在第幾個元素前插入:”;cin>>i;cout<<“輸入插入的元素:”;cin>>x; InsertLinkList(L,i,x); LinkListLengh(L); PrintLinkList(L); cout<<“輸入刪除元素的位置:”;cin>>i; DeleteLinkList(L,i); LinkListLengh(L); PrintLinkList(L); cout<<“銷毀程序后為:”< DestroyLinkList(L);} 五﹑實驗結(jié)果 六﹑實驗心得體會： 鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動態(tài)地進行存儲分配的一種結(jié)構(gòu)。它可以根據(jù)需要開辟內(nèi)存單元。鏈表中每一個元素稱為“結(jié)點”，每個結(jié)點都應(yīng)包括兩個部分：一為用戶需要用的實際數(shù)據(jù)，二為下一個結(jié)點的地址。 實驗的程序設(shè)計規(guī)劃（實現(xiàn)的功能、分幾個模塊、子函數(shù)）（1）編寫鏈表創(chuàng)建子函數(shù)void CreatLinkList(L,j)（2）編寫鏈表插入子函數(shù) int InsertLinkList(LinkList &L, int i, int x)（3）鏈表的打印int PrintLinkList(LinkList &L)（4）編寫鏈表刪除子函數(shù) int DeleteLinkList(LinkList &L,int i)（5）編寫鏈表銷毀子函數(shù)void DestroyLinkList(LinkList &L)（6）編寫主函數(shù)Main()，通過功能菜單調(diào)用子函數(shù)（7）編譯調(diào)試程序 經(jīng)過多次的調(diào)試，修改，實驗結(jié)果終于正確了，在這個過程中，經(jīng)歷了不知道怎么進行聲明區(qū)的編寫如包含文件，宏定義，函數(shù)聲明，全局變量聲明，結(jié)構(gòu)體等的定義等的結(jié)合，到學(xué)會了使用先把程序主要規(guī)劃為四個部分來寫就簡單多了，第一，定義；第二，寫所要調(diào)用的子函數(shù)；第三，寫主函數(shù)，調(diào)用子函數(shù)；第四就是程序的編譯與調(diào)試，修改。數(shù)據(jù)結(jié)構(gòu)實驗需要我們對每個程序的算法有深刻的理解，才能應(yīng)用到實際中去，因此我們需要在做實驗之前要熟悉實驗的內(nèi)容，且先把所要實驗的程序?qū)懗鰜恚趯嶒炛芯涂梢圆檎义e誤并加以改正，這是一個成長的過程。 數(shù)據(jù)結(jié)構(gòu)上機實驗報告一﹑實驗名稱： 實驗二—隊列 二﹑實驗?zāi)康模?1.掌握隊列這種抽象數(shù)據(jù)類型的特點, 掌握棧與隊列在實際問題中的應(yīng)用和基本編程技巧,并能在相應(yīng)的問題中選用它;2.熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，特別是隊滿和隊空的描述方法； 3．掌握棧與隊列的數(shù)據(jù)類型描述及特點； 4.掌握棧的順序和鏈式存儲存表示與基本算法的實現(xiàn)； 5.掌握隊列的鏈式存儲表示與基本操作算法實現(xiàn);6.按照實驗題目要求，獨立完成實際程序的編寫編寫、調(diào)試和運行，并通過用例數(shù)據(jù)的運行過程抓獲相關(guān)屏面驗證程序設(shè)計的正確性； 7.認真書寫實驗報告，并按時提交。 三﹑實驗內(nèi)容： 對順序循環(huán)隊列，常規(guī)的設(shè)計方法是使用対尾指針和對頭指針，對尾指針用于指示當(dāng)前的対尾位置下標，對頭指針用于指示當(dāng)前的対頭位置下標。現(xiàn)要求： （1）掌握棧和隊列的特點，即后進先出和先進先出的原則。（2）設(shè)計一個使用對頭指針和計數(shù)器的順序循環(huán)隊列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊列，出隊列，取對頭元素和判斷隊列是否為空； （3）編寫主函數(shù)進行測試。 四﹑實驗步驟與程序 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){ } Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){ } void EnQueue(LinkQueue &Q,int e){ } int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“該鏈隊為空:”);else printf(“該鏈隊不為空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入隊成功”,e); } if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q){ } void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“隊首元素刪除成功”); } if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;printf(“隊首元素為:%d”,p->data);void OutQueue(LinkQueue &Q){ } void LengthQueue(LinkQueue &Q){ int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;while(p!=Q.rear->next){ } printf(“%d%,”,p->data);p=p->next; } printf(“該隊列的長度為:%d”,f);else { } p=Q.front->next;while(p!=Q.rear->next){ } printf(“該隊列的長度為:%d”,f);p=p->next;f++;void main(){ system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************鏈隊列功能菜單***********************n”);printf(“1:初始化鏈隊列，2:判斷鏈隊列是否為空, 3:進入隊列，4:取出隊首元素n”);printf(“5:輸出該隊列的所有元素,6:輸出該隊列的長度，7:結(jié)束程序，8:清屏n”); while(flag){ printf(“n請輸入操作符:”);scanf(“%d”,&i);switch(i){ case 1: int e,n,k;printf(“請輸入隊列的長度:”);scanf(“%d”,&n);printf(“請輸入隊列的元素:”);for(e=1;e<=n;e++){ } printf(“初始化鏈隊成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q); break;case 3: int j;printf(“請輸入要進入隊列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5: printf(“該隊列的元素為:”);OutQueue(Q);break; case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break; } } 五﹑實驗結(jié)果 六﹑實驗心得體會： 程序主要構(gòu)造了主函數(shù)main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等調(diào)用函數(shù)，實現(xiàn)了隊列的創(chuàng)立，隊列是否為空的判斷，入隊和出隊等功能。 通過此次實驗，加深了對隊列的存儲結(jié)構(gòu)的了解，同時也對程序設(shè)計能力有了提高，加深了對隊列先進先出性質(zhì)的理解，它允許在表的一端進行插入，在另一端刪除元素，這和我們?nèi)粘Ｉ钪械呐抨犑且恢碌模钤邕M入隊列的元素最早離開。我們往往寫不出程序，這其中的原因我覺得是對程序的結(jié)構(gòu)不是很了解，對實驗的內(nèi)容也不熟練的結(jié)果，數(shù)據(jù)結(jié)構(gòu)給我們許多程序的算法和模型，對我們寫程序的思維有很大的鍛煉，我們應(yīng)珍惜每次上機實驗的機會去實踐課堂上所學(xué)的東西并從中發(fā)現(xiàn)問題，從而達到提升寫程序的能力。 數(shù)據(jù)結(jié)構(gòu)上機實驗報告一﹑實驗名稱： 實驗三—二叉樹的遍歷 二﹑實驗?zāi)康模?/p> 1、熟悉二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法； 2、掌握二叉樹的生成，掌握二叉樹的定義和存儲表示，學(xué)會建立一棵特定二叉樹的方法； 3、理解二叉樹的三種遍歷方法：先序遍歷、中序遍歷和后序遍歷； 4、學(xué)會編寫實現(xiàn)樹的各種操作的算法。 二、實驗內(nèi)容： 1、使用類定義實現(xiàn)二叉樹，補充完整所缺的函數(shù)，并實現(xiàn)創(chuàng)建和遍歷二叉樹的基本操作； 2、編程實現(xiàn)在二叉鏈表這種存儲方式下，實現(xiàn)二叉的遍歷，可采用遞歸或者非遞歸實現(xiàn)，遍歷算法為在先序、中序和后序遍歷算法。 三、實驗步驟與程序： #include void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函數(shù) { printf(“------------二叉樹的遍歷-------------n”);printf(“請輸入要遍歷的數(shù)：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍歷:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍歷:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍歷:”);printf(“n”);PostOrder(Ta);} 五﹑實驗結(jié)果 六﹑實驗心得體會： 實驗的程序設(shè)計規(guī)劃（實現(xiàn)的功能、分幾個模塊、子函數(shù)）（1）先序遍歷遞歸算法函數(shù)：void PreOrder(BiTree T)（2）中序遍歷遞歸算法函數(shù)：void InOrder(BiTree T)（3）后續(xù)遍歷遞歸算法函數(shù)：void PostOrder(BiTree T)（4）主函數(shù)的實現(xiàn)：void main() 在實驗前我認真閱讀關(guān)于二叉樹的實現(xiàn)的內(nèi)容，為編程實現(xiàn)第一步，本次實驗通過按上述的實驗步驟一步步實現(xiàn)的，實驗過程中出現(xiàn)了一些錯誤，經(jīng)過一步步的調(diào)試，修改錯誤，得到了二叉樹的遍歷用遞歸運算的方法的程序。通過這個實驗，我體會到了理解數(shù)據(jù)結(jié)構(gòu)的重要性，這有真正理解了定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。二叉樹的先序，中序與后序的輸出都用了遞歸的算法，而且用起來不是很復(fù)雜，這使我更進一步理解了函數(shù)遞歸調(diào)用并得到靈活運用；在實現(xiàn)算法上，從算法的效率看，遞歸方法書寫形式較為簡潔，更為直觀，一般具有較好的空間效率。 總之，不管做什么實驗，我們在做實驗前都要先預(yù)習(xí)，對所做的實驗有較深的理解，在做實驗的時候需要很嚴謹，仔細的查找錯誤，從而能在實驗中收獲知識，提升自己。 數(shù)據(jù)結(jié)構(gòu)上機實驗報告4 一﹑實驗名稱： 實驗四—查找 二﹑實驗?zāi)康模?/p> 1、熟悉掌握順序表的查找方法； 2、熟練掌握二叉排序樹的構(gòu)造方法和查找算法 3、掌握描述查找過程的判定樹的構(gòu)造方法，以及按照定義計算各種查找方法在等概率情況下查找成功時的平均查找長度； 4、學(xué)會定義線性表的儲存類型，實現(xiàn)C++程序的基本結(jié)構(gòu)對線性表的一些基本操作和具體的函數(shù)定義； 5、掌握順序表的基本操作，實現(xiàn)順序表的查找的等基本運算； 6、掌握對于多函數(shù)程序的輸入，編輯，調(diào)試和運算過程。 二、實驗內(nèi)容： 1、實現(xiàn)順序表的查找算法 2、關(guān)于衡量查找的主要操作—查找的查找平均效率的平均長度的討論。 三、實驗步驟與程序： #include element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num);int main(){ int i,num,searchnum,k; printf(“---------------數(shù)據(jù)結(jié)構(gòu)查找實驗-------------n”);printf(“請輸入數(shù)據(jù)元素的個數(shù)：”);scanf(“%d”,&num);printf(“請輸入數(shù)據(jù)的元素：n”);for(i=0;i printf(“請輸入要查詢的數(shù)據(jù)元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查詢元素的下標為：”);printf(“%dn”,k);} else printf(“查詢元素不存在。n”);} return 0;} int seqsearch(element list[],int searchnum,int num){ int j; list[num].key=searchnum; for(j=0;list[j].key!=searchnum;j++);return j 六﹑實驗心得體會： 實驗的程序設(shè)計規(guī)劃為先寫一個主函數(shù)int main()，再寫一個查找的子函數(shù)int seqsearch(element list[],int searchnum,int num)，主函數(shù)通過調(diào)用子函數(shù)的方法實現(xiàn)程序的設(shè)計。 所謂“查找”即為在一個眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個“特定的”數(shù)據(jù)元素（或記錄），通過本次實驗，我更進一步的了解數(shù)據(jù)結(jié)構(gòu)程序?qū)嶒炘O(shè)計實現(xiàn)算法的基本模型，和算法實現(xiàn)等基本內(nèi)容，學(xué)會了順序表的查找方法。 數(shù)據(jù)結(jié)構(gòu)上機實驗報告5 一﹑實驗名稱： 實驗五—內(nèi)部排序 二﹑實驗?zāi)康模?/p> 1、通過實現(xiàn)下述實驗內(nèi)容，學(xué)習(xí)、實現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況，并加以靈活應(yīng)用。 2、掌握各種排序時間復(fù)雜度的分析方法。 二、實驗內(nèi)容： 1、插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。 2、快速排序：首先選擇一個基準，將記錄分割為兩部分，左支小于或等于基準，右支則大于基準，然后對兩部分重復(fù)上述過程，直至整個序列排序完成。 3、討論各種內(nèi)部排序方法的基本思路，算法特點，排序過程及它們的時間復(fù)雜度的分析。 三、實驗步驟與程序： #include } int x;void charu();void kuaisu();printf(“----------內(nèi)部排序---------n”);printf(“ 1、插入排序：n”);printf(“ 2、選擇排序：n”);printf(“請根據(jù)序號選擇：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m; printf(“插入排序n”); printf(“請輸入個您想排序的數(shù)據(jù):n”); for(i=0;i<7;i++)scanf(“%d”,&a[i]); for(j=1;j<7;j++) { m=a[j]; for(i=j-1;i>=0;i--) { if(a[i] break; else a[i+1]=a[i]; } a[i+1]=m; } printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key; key=L[first]; while(left { while((left right--; if(left L[left++]=L[right]; while((left left++; if(left L[left]=key; return left; } quick_sort(int L[],int first,int end) { int split; if(end>first) { split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); } } void kuaisu(){ int a[7],i; printf(“快速排序n”); printf(“請輸入個您想排序的數(shù)據(jù):n”); for(i=0;i<7;i++) scanf(“%d”,&a[i]); quick_sort(a,0,9); printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} 五﹑實驗結(jié)果： 六﹑實驗心得體會： 排序的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，從新排成按關(guān)鍵字有序的序列；直接插入排序的穩(wěn)定性比快速排序高，且算法較簡單。本次實驗運用到的是插入排序和快速排序。 實習(xí)報告 題 目 : 實現(xiàn)一個約瑟夫環(huán)程序 班級：031021姓名：王帥學(xué)號：03102076 一、需求分析 1． 本演示程序中，利用單向循環(huán)鏈表存儲結(jié)構(gòu)存儲約瑟夫環(huán)數(shù)據(jù)（即n個人的編號和密碼）。 2． 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數(shù)據(jù)，運算結(jié)果顯示在其后。 3． 程序執(zhí)行的命令包括： 1)構(gòu)造單向循環(huán)鏈表；2）進行數(shù)值的輸入，并作判斷分析；3）約瑟夫算法的實現(xiàn)與結(jié)果輸出；4）結(jié)束。 4． 測試數(shù)據(jù) m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，（正確的出列順序為6，1，4，7，2，1，3，5）。 二、概要設(shè)計 1．單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為： ADT List｛ 數(shù)據(jù)對象：D=｛ai | ai?正整數(shù)，I=1，2，......，n,n≥0｝數(shù)據(jù)關(guān)系：R1=｛< ai-1，ai > |，ai-1，ai?D,I=1，2，......，n｝基本操作： Init List(&L) 操作結(jié)果：構(gòu)造一個空的線性表L。 List Insert(&L,i,e) 初始條件：線性表L已存在，1≤i≤List Length(L)+1.操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L長度加1。List Delete(&L,i,&e) 初始條件：線性表L存在非空，1≤i≤List Length(L).操作結(jié)果：刪除L的第i個元素，并用e返回其值，L長度減1。 2． 程序包含四個模塊： 1）主程序模塊： void main() { 初始化； for（;;） {} while（命令=開始） { 接受命令； 處理命令； } for（;;） { } } 2）有序表單元模塊——實現(xiàn)有序表的抽象數(shù)據(jù)類型； 3）節(jié)點結(jié)構(gòu)單元模塊——定義有序表的節(jié)點結(jié)構(gòu)； 4）數(shù)據(jù)輸入分析模塊——判斷輸入數(shù)據(jù)正確有效； 各模塊之間的調(diào)用關(guān)系如下： 主程序模塊 ↓ 有序表結(jié)構(gòu)模塊 ↓ 節(jié)點結(jié)構(gòu)單元模塊 ↓ 數(shù)據(jù)輸入分析模塊 三、詳細設(shè)計 1、結(jié)點類型，指針類型 TypedefstructLNode{ int code,date;//code 為人所在位置 date為人持有的密碼 struct LNode *next; };// 結(jié)點類型，指針類型 2、構(gòu)造單向循環(huán)鏈表 struct LNode *p,*head,*q;//定義頭節(jié)點，和指針 for(i=2;i<=n;i++) { struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配 新結(jié)點空間 s->code=i; input(s->date); p->next=s; p=p->next; } p->next=head;//根據(jù)輸入的人數(shù)，進行單項循環(huán)鏈表的創(chuàng)建，p指向最后一個結(jié)點，并與頭節(jié)點鏈接，形成單項循環(huán)鏈表 3、約瑟夫環(huán)的程序?qū)崿F(xiàn)部分 while(n!=1)//判斷輸入人數(shù)，如為1則直接輸出結(jié)果，不循環(huán) { for(i=1，m=m%n;i { p=p->next; } q=p->next;//找到要刪除節(jié)點 p->next=q->next;//找到要刪除節(jié)點的后繼，并連接新環(huán)m=q->date;//找到下一個密碼 printf(“%d”,q->code); free(q);//釋放已刪除節(jié)點空間 n--;//鏈表長度減一 } printf(“%d”,p->code);//約瑟夫環(huán)的結(jié)果輸出 4、其他函數(shù)代碼 數(shù)值的輸入限制 int input() { int y,k,z=0; char c;//元素類型 char a[4];//數(shù)組初始化 if(!z)//輸入判斷，確定位數(shù)字或控制字符且位置和密碼不為零 { for(y=0;y<4;y++) { c=getch(); if(c>=48&&c<=57)//確定為輸入數(shù)字 {a[y]=c; putch(c); } else { y--; if(c=='r')//確定輸入為控制字符 即回車或者刪除 break; else if(c==8) {a[y]='n'; y--;} continue; } } k=atoi(a);//確定最終輸入數(shù)字的值 printf(“n”); z=k; if(z==0) printf(“ERROR!The number couldn't be 0!n”);// 輸入為零，重新輸入 } return(k);//數(shù)值的返回 5、函數(shù)的調(diào)用關(guān)系圖反映程序?qū)哟谓Y(jié)構(gòu) Main→input 四、調(diào)試分析 1、早期程序只寫了約瑟夫環(huán)的實現(xiàn)部分，沒有對輸入數(shù)據(jù)進行篩選，調(diào)試的時候會經(jīng)常出錯。比如是輸入字母，或者輸入0，大于32767溢出； 2、早期的循環(huán)過程中沒有進行優(yōu)化，導(dǎo)致循環(huán)次數(shù)過多，浪費時間； 3、為了輸出時美觀，分別在input和main函數(shù)主體內(nèi)做了兩次，輸入非零的判斷，浪費了資源； 4、算法的時空分析 為了限制在輸入過程中不會上溢，只在輸入中限定為四個不全為零的數(shù)字，但是做的是do……while循環(huán)，復(fù)雜度為o（1）; 當(dāng)n大于1時： 在數(shù)據(jù)輸入中，鏈表的創(chuàng)建是for循環(huán)，時間復(fù)雜度為o（n-1） 在約瑟夫環(huán)實現(xiàn)程序中，為for循環(huán)。時間復(fù)雜度為o（m%n-1） 當(dāng)n=1時，復(fù)雜度為o（1）。 五、用戶手冊 用戶根據(jù)提示，先輸入起始密碼m，然后輸入人數(shù)n，再根據(jù)人數(shù)，分別輸入每個人的密碼date，數(shù)值均不能為0，否則會提示重新輸入，輸入為字母則自動丟棄，輸入錯誤可用刪除鍵進行修改，輸入完成后按回車鍵確定本次輸入完畢（若輸入數(shù)字大于9999，則第五位自動轉(zhuǎn)換為下一個數(shù)字的起始位，依此類推）。 當(dāng)n個數(shù)字全部輸入完畢，則自動顯示結(jié)果，按任意鍵則退出本程序。 六、測試結(jié)果 第一組：m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，出列順序為6，1，4，7，2，1，3，5。 第二組： m 的初值為30；n=8，7個人的密碼依次為：5，1，6，9，4，7，2，3，出列順序為6，5，2，3，7，1，4，8。 第三組 : m 的初值為15；n=6，7個人的密碼依次為：5，3，4，7，6，9，出列順序為3，1，2，6，4，5。 七、附錄 源程序頭文件名清單： #include “malloc.h”//內(nèi)存空間分配頭文件 #include “stdio.h”//輸入輸出函數(shù)頭文件 #include “stdlib.h”//input函數(shù)中字符串轉(zhuǎn)短整形函數(shù)的頭文件 #include “conio.h”//最后顯示結(jié)果、清屏函數(shù)頭文件 北京郵電大學(xué) 數(shù)據(jù)結(jié)構(gòu)試驗報告 實驗名稱： 實驗一 線性表 學(xué)生姓名： 班 級： 班內(nèi)序號： 學(xué) 號： 日 期： 2014年1月3日 實驗?zāi)康?/p> ? 熟悉C++語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法 ? 學(xué)習(xí)指針、模板類、異常處理的使用 ? 掌握線性表的操作的實現(xiàn)方法 ? 學(xué)習(xí)使用線性表解決實際問題的能力 實驗內(nèi)容 2.1題目1 根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈式結(jié)構(gòu)實現(xiàn)線性表，并完成線性表的基本功能。 線性表存儲結(jié)構(gòu)（五選一）： 1、帶頭結(jié)點的單鏈表 2、不帶頭結(jié)點的單鏈表 3、循環(huán)鏈表 4、雙鏈表 5、靜態(tài)鏈表 線性表的基本功能： 1、構(gòu)造：使用頭插法、尾插法兩種方法 2、插入：要求建立的鏈表按照關(guān)鍵字從小到大有序 3、刪除 4、查找 5、獲取鏈表長度 6、銷毀 7、其他：可自行定義 編寫測試main()函數(shù)測試線性表的正確性。程序分析 3.1 存儲結(jié)構(gòu) 單鏈表的存儲結(jié)構(gòu)： 3.2 關(guān)鍵算法分析 一、關(guān)鍵算法 1.頭插法 自然語言描述：a.在堆中建立新結(jié)點 b.將a[i]寫入到新結(jié)點的數(shù)據(jù)域 c.修改新結(jié)點的指針域 d.修改頭結(jié)點的指針域,將新結(jié)點加入鏈表中 代碼描述： template front = new Node } } s->next = front->next;front->next = s;時間復(fù)雜度：O(n) 2.尾插法 自然語言描述：a.在堆中建立新結(jié)點 b.將a[i]寫入到新結(jié)點的數(shù)據(jù)域 c.將新結(jié)點加入到鏈表中 d.修改修改尾指針 代碼描述: template front = new Node } } s->data = a[i];s->next = r->next;r->next= s;r=s;時間復(fù)雜度：O(n) 3.析構(gòu)函數(shù) 自然語言描述：a.新建立一個指針，指向頭結(jié)點 b.移動a中建立的指針 c.逐個釋放指針 代碼描述: template Node } } delete front;4.按位查找函數(shù) 自然語言描述: a.初始化工作指針p和計數(shù)器j，p指向第一個結(jié)點，j=1 b.循環(huán)以下操作，直到p為空或者j等于1 b1：p指向下一個結(jié)點 b2：j加1 c.若p為空，說明第i個元素不存在，拋出異常 d.否則，說明p指向的元素就是所查找的元素，返回元素地址 代碼描述: template Node if(j } else break;p = p->next;j++; } if(!p)throw“查找位置非法”;else return p;} 時間復(fù)雜度：O(n) 5.按值查找函數(shù) 自然語言描述：a.初始化工作指針p和計數(shù)器j，p指向第一個結(jié)點，j=1 b.循環(huán)以下操作，找到這個元素或者p指向最后一個結(jié)點 b1.判斷p指向的結(jié)點是不是要查找的值，如果是，返回j; b2.否則p指向下一個結(jié)點,并且j的值加一 c.如果找到最后一個結(jié)點還沒有找到要查找的元素，返回查找失敗信息 代碼描述: template Node } return-1;if(p->data == x)return j;else { p = p->next; j++;} } 時間復(fù)雜度：O(n)6.插入函數(shù) 自然語言描述： a.在堆中建立新結(jié)點 b.將要插入的結(jié)點的數(shù)據(jù)寫入到新結(jié)點的數(shù)據(jù)域 c.修改新結(jié)點的指針域 d.修改前一個指針的指針域，使其指向新插入的結(jié)點的位置 代碼描述: template Node } else throw“插入位置非法”;Node 自然語言描述：a.從第一個結(jié)點開始，查找要刪除的位數(shù)i前一個位置i-1的結(jié)點 b.設(shè)q指向第i個元素 c.將q元素從鏈表中刪除 d.保存q元素的數(shù)據(jù) e.釋放q元素 代碼描述: template T x=q->data; } p->next = q->next;delete q;return x; 8.遍歷打印函數(shù) 自然語言描述: a.判斷該鏈表是否為空鏈表，如果是，報錯 b.如果不是空鏈表，新建立一個temp指針 c.將temp指針指向頭結(jié)點 d.打印temp指針的data域 e.逐個往后移動temp指針，直到temp指針的指向的指針的next域為空 代碼描述: template } Node } cout< 自然語言描述： a.判斷該鏈表是否為空鏈表，如果是，輸出長度0 b.如果不是空鏈表，新建立一個temp指針，初始化整形數(shù)n為0 c.將temp指針指向頭結(jié)點 d.判斷temp指針指向的結(jié)點的next域是否為空，如果不是，n加一，否則return n e.使temp指針逐個后移，重復(fù)d操作，直到temp指針指向的結(jié)點的next域為0，返回n 代碼描述: template } Node } return i-1;p = p->next;i++;4 程序運行結(jié)果 4.1主函數(shù)流程圖 4.2程序運行框圖 實驗心得 1.調(diào)試時出現(xiàn)的問題及解決的方法 在編寫按值查找函數(shù)時，由于沒有處理好指針類型的原因，導(dǎo)致指針無法正常返回，屢屢報錯。最后意識到c++沒有指針強制類型的轉(zhuǎn)換機制，經(jīng)過細致檢查后才改正錯誤使得程序正常運行。2.心得體會 了解了單鏈表的基本的操作函數(shù)實現(xiàn)，對鏈式存儲結(jié)構(gòu)有了較好的認識 3.下一步的改進 可以增加完善報錯機制，增強程序的健壯性 完整源代碼 #include template }; template }; //template Node template } template } template } front = p;p = p->next;delete front;front = new Node } Node } Node } Node } cout< template } template } Node } return-1;if(p->data == x)return j;else { } p = p->next; j++;Node } if(!p)throw“查找位置非法”;else return p;if(j } else break;p = p->next;j++; template } template } template } void main(){ Node } return i-1;p = p->next;i++;Node } else throw“插入位置非法”;Node T x=q->data; } int n;cout<<“將要輸入的鏈表長度為：”;cin>>n;int *b=new int[n];cout<<“輸入鏈表中的元素：”;for(int k=0;k “計算機軟件技術(shù)基礎(chǔ)”課程實驗報告 （六）實驗名稱：數(shù)據(jù)庫及SQL語言 班級_______ 姓名__________ 學(xué)號______實驗日期： 實驗機時：3 學(xué)時實驗成績： ----------------- 一.實驗?zāi)康模?/p> 1、學(xué)習(xí)數(shù)據(jù)庫設(shè)計的一般過程及相關(guān)技術(shù)； 2、學(xué)習(xí)access數(shù)據(jù)庫管理系統(tǒng)； 3、掌握數(shù)據(jù)庫的輸入、查詢、更新操作。 二.實驗內(nèi)容： 1、需求陳述：某校圖書館要建立一個圖書數(shù)據(jù)管理系統(tǒng)。該圖書館的圖書（書名、分類號、作者、出版社）存放在不同的借閱室（室名），讀者（姓名、系名、類別）在書架上找到所需圖書后，可以到服務(wù)臺辦理借閱（借閱時間）。 設(shè)計要求： ? 分析需求，建立數(shù)據(jù)庫的概念模型； ? 將概念模型轉(zhuǎn)換為關(guān)系模型（注意：是否需要作規(guī)范化處理）； ? 寫出創(chuàng)建基本表的SQL語句； ? 寫出以下查詢要求的SQL語句： （1）所有“高等數(shù)學(xué)習(xí)題集”書的信息； （2）讀者“李林”借了什么書？ （3）“社會學(xué)原理”在哪個借閱室？ 2、在access數(shù)據(jù)庫管理系統(tǒng)中建立所設(shè)計的關(guān)系表； 3、向各表中輸入一組實驗數(shù)據(jù)（元組）（注意：關(guān)系完整性）； 4、對數(shù)據(jù)庫進行查詢。 三.實驗結(jié)果： 1、實體-關(guān)系圖； 2、數(shù)據(jù)庫表； 3、創(chuàng)建基本表的語句； 4、查詢語句。第二篇：數(shù)據(jù)結(jié)構(gòu)上機實驗報告
第三篇：數(shù)據(jù)結(jié)構(gòu)上機實驗報告
第四篇：北郵數(shù)據(jù)結(jié)構(gòu)實驗報告 單鏈表
第五篇：《數(shù)據(jù)結(jié)構(gòu)》上機作業(yè)——實驗報告(六)
![下載2012《數(shù)據(jù)結(jié)構(gòu)》上機實驗報告 鏈表[★]word格式文檔](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
點擊咨詢 