第一篇：數據結構上機作業
實驗一 線性表
一、實驗題
線性表的應用———多項式計算
二、程序設計思路
包括每個函數的功能說明，及一些重要函數的算法實現思路一鏈式存儲：
1.void InitPoly(LNode *&p)初始化多項式 2.void TraversePoly(LNode *&p)遍歷多項式 3.void ClearPoly(LNode *&p)清除多項式
4.void InsertPoly(LNode *&p, double a, int e)插入一項 5.void DeletetPoly(LNode *&p,int pos)
刪除一項
6.double PolySum(LNode *&p, double x)
多項式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2)
多項式相加 順序存儲：
1.void InitPoly1(SeqList &L)初始化多項式 2.void ClearPoly1(SeqList &L)清除多項式 3.void TraversePoly1(SeqList L)
遍歷多項式
4.bool InsertPoly1(SeqList &L, ElemType item)插入一項 5.double PolySum1(SeqList L,double x)
多項式求值 6.bool DeleteList1(SeqList &L,int pos)
刪除一項
7.SeqList PolyAdd1(SeqList &L1,SeqList& L2)
多項式相加
三、源程序代碼
#include
{ if(pos>1||pos<-1)return false;NodeType *cp=p->next;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){
刪除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多項式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;i<=cp->exp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多項式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->exp 輸出多項式 } void ClearPoly1(ListType &p)//清除多項式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//項 { p.list[e]=a;if(p.size { int i,n;if(p.size==0){ cout<<“多項式為空,刪除無效!”< 插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值 { double sum=0,item;int i,j;for(i=0;i<=p.size;i++){ item=1;for(j=1;j<=i;j++)item=item*x;sum=sum+item*p.list[i];} return sum;} ListType PolyAdd1(ListType p1, ListType p2)//項式相加 { ListType p;InitPoly1(p);float coef; 多項式求多int i,j;for(i=0;i<=p1.size;i++){ coef=p1.list[i]+p2.list[i];InsertPoly1(p, coef, i);} if(i<=p1.size)for(j=i;j<=p1.size;j++)InsertPoly1(p, p1.list[j], j);if(i<=p2.size)for(j=i;j<=p2.size;j++)InsertPoly1(p, p2.list[j], j);return p;四實驗結果分析 五.心得體會 對于結構體的認識增加了，對于動態存儲也有了更多的認識，也是在不知不覺中提高了。 實驗二 字符串的操作 一、實驗題目——字符串的操作 二、程序設計思路 采用定長順序存儲表示，由用戶創建串s和串t，實現在串s中下標為pos的字符之前插入串t。 三、源程序代碼 #define MAXLEN 10 typedef struct { /*串結構定義*/ char ch[MAXLEN]; int len;}SString;void createstring(SString *s) /*創建串s*/ { int i,j;char c;printf(“input the length of the string:”); scanf(“%d”,&j); for(i=0;i { printf(“input the %d:”,i+1); fflush(stdin); scanf(“%c”,&c); s->ch[i] = c; } s->len = j;} void output(SString *s) /*輸出串s*/ { int i;for(i=0;i printf(“%c ”,s->ch[i]); printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下標為pos的字符之前插入串t */ { int i;if(pos<0 || pos>s->len) /*插入位置不合法*/ return(0); if(s->len + t->len<=MAXLEN) /*插入后串長≤MAXLEN*/ { for(i=s->len + t->len-1;i>=t->len + pos;i--) s->ch[i]=s->ch[i-t->len];/*將下標為pos的字符后的元素往后移動t->len個長度*/ for(i=0;i s->ch[i+pos]=t->ch[i]; /*將串t從下標為pos位置開始插入到串s*/ s->len=s->len+t->len;} else { if(pos+t->len<=MAXLEN)/*插入后串長>MAXLEN,但串t的字符序列可以全部插入*/ { for(i=MAXLEN-1;i>t->len+pos-1;i--) s->ch[i]=s->ch[i-t->len]; for(i=0;i s->ch[i+pos]=t->ch[i]; /*將串t從下標為pos位置開始插入到串s*/ s->len=MAXLEN; } else /*插入后串長>MAXLEN,并且串t的部分字符也要舍棄*/ { for(i=0;i s->ch[i+pos]=t->ch[i]; /*直接從下標為pos的位置按順序插入串t*/ s->len=MAXLEN; } return(1);} } void main(){ SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0) printf(“insert error!”);else { printf(“after insert:n”); output(str1);} } 四、實驗結果 五、實驗體會 通過本次實驗，我加深了對串數據結構的理解。在串的定長順序存儲結構中，按照預定義的大小，為每個定義的串變量分配一個固定長度的存儲區。在存儲方式中，結點大小的選擇和順序存儲方式的格式選擇一樣都很重要，它直接影響著串處理的效率。 實驗三 一、實驗題目——非遞歸算法對二叉樹進行中前序遍歷 二、程序設計思路 創建一棵10個節點構造的完全二叉樹，并對其進行前、中、后序遍歷。 三、源程序代碼 #define STUDENT EType #define SType SType #define HeadEType int #include //定義數據結構類型 struct STUDENT { char name[8];int age;char number[15];char address[20];}; struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree; typedef struct { BinaryTreeNode *ptr;bool status;}SType; typedef struct { SType *element;int top;int MaxSize;}Stack; void CreatStack(Stack &S, int MaxStackSize){// 構造一個最大容量為MaxStackSize 的堆棧 S.MaxSize = MaxStackSize; S.element = new SType[S.MaxSize]; S.top =-1;} bool IsEmpty(Stack &S){// 判斷堆棧S是否為空 if(S.top ==-1) return true; return false;} bool IsFull(Stack &S){// 判斷堆棧S是否為空 if(S.top == MaxSize-1) return true; return false;} bool Push(Stack &S , SType &x){// x進s棧，返回進棧后的狀態值 if(IsFull(S)) return false; S.top++; S.element[S.top] = x; return true;} bool Pop(Stack &S , SType &x){// 將s棧頂的值取至x中，返回出棧后的狀態值 if(IsEmpty(S)) return false; x = S.element[S.top]; S.top--; return true;} BinaryTreeNode *MakeNode(EType &x) {//構造結點 BinaryTreeNode *ptr; ptr = new BinaryTreeNode; if(!ptr)return NULL; ptr->data = x; ptr-> LChild = NULL; ptr-> RChild = NULL; return ptr;} void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 聯接root，left, right所指的結點指針為二叉樹 root->LChild=left; root->RChild=right;} void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉樹前序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q||!IsEmpty(S)){ if(q) { cout< ele.ptr=q; Push(S,ele);//節點指針進棧，以后回溯時在退棧 q=q->LChild;//指針指向剛剛被訪問的“根”節點的左子樹 } else //當左子樹為空時，利用堆棧回溯 if(!IsEmpty(S)) { Pop(S,ele);//退棧回溯 q=ele.ptr;//指針重新指向剛剛被訪問的“根”節點 q=q->RChild;//指針指向該回溯節點的右子樹 } } } void InOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的中序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q ||!IsEmpty(S)){ while(q)//找到最左邊的子樹 { ele.ptr=q; Push(S,ele);//指針非空時，將當前的“根”節點指針進棧，用于以后回溯 q=q->LChild;//指針繼續指向該“根”節點的左子樹 } if(!IsEmpty(S))//當左子樹為空時，進行退棧回溯 { Pop(S,ele);//從堆棧中回溯節點指針（節點還未訪問） q=ele.ptr; cout< q=q->RChild;//指針向回溯的節點右子樹推進 } } } void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的后序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q ||!IsEmpty(S)){ if(q)//找最左邊的子樹 { ele.ptr=q; ele.status=false;//進棧前標記為第一次進棧 Push(S,ele); q=q->LChild;//指針繼續向左推進 } else if(!IsEmpty(S))//直到左子樹為空時，退棧回溯 { Pop(S,ele);//從堆棧中彈出回溯節點（還未訪問） q=ele.ptr;//q指向當前回溯節點 if(ele.status)//判斷節點進棧標志，是否對其進行訪問 { cout< q=NULL;//將q設為空，為了繼續退棧 } else { ele.status=true;//改變回溯節點的進棧標記，以便再次進棧 Push(S,ele); q=q->RChild;//指針向該回溯節點的右孩子推進 } } } } //主函數 void main(){ BinaryTreeNode *ptr[11]; char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i<11;i++){ strcpy(x[11-i].name,Name[11-i]); ptr[11-i]=MakeNode(x[11-i]);//構造10個二叉樹節點 } //將節點鏈接域填值，構造一個二叉樹 //這里構造的是一棵有10個節點的完全二叉樹 for(int j=1;j<5;j++){ MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//該完全二叉樹構造完畢 //***********對已構造的完全二叉樹進行前序非遞歸遍歷************// cout<<“對該二叉樹進行前序遍歷結果：”< //***********對已構造的完全二叉樹進行中序非遞歸遍歷************// cout< //***********對已構造的完全二叉樹進行中序非遞歸遍歷************// cout< 四、實驗結果分析 五、實驗總結 二叉樹是一種非常重要的數據結構，很多其它數據結構都是基于二叉樹的基礎演變而來的。對于二叉樹，有前序、中序以及后序三種遍歷方法。因為樹的定義本身就是遞歸定義，因此采用遞歸的方法去實現樹的三種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實現。在三種遍歷中，前序和中序遍歷的非遞歸算法都很容易實現，非遞歸后序遍歷實現起來相對來說要難一點。 實驗四 一、實驗題目——深度優先算法實現圖的遍歷 二、程序設計思路 以鄰接矩陣或鄰接表為存儲結構，以用戶指定的頂點為起始點，實現無向連通圖的深度優先，并輸出遍歷的結點序列。首先，根據用戶輸入的頂點總數和邊數，構造無向圖，然后以用戶輸入的頂點為起始點，進行深度優先，并輸出遍歷的結果。 三、源程序代碼 #include };struct vexnode { char vertex;edgenode* edgelink;};struct Graph { vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//隊列的定義及相關函數的實現 struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL) return;if(Q->rear==NULL) Q->front=Q->rear=q;else { Q->rear->next=q; Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL) return;if(Q->front==Q->rear){ *e=Q->front->nData; Q->front=Q->rear=NULL;} else { *e=Q->front->nData; Q->front=Q->front->next;} } //創建圖 void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“請輸入頂點數和邊數:”< cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL;} cout<<“開始輸入邊表信息:”< cout<<“請輸入邊 cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink; G->adjlists[i].edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=G->adjlists[j].edgelink; G->adjlists[j].edgelink=p2; //因為是無向圖，所以有兩次建立邊表的過程 } } //------------------------------深度優先遍歷 void DFS(Graph *G,int i,int visit[]){ cout< DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度優先遍歷 { cout<<“該圖的深度優先遍歷結果為:”< visit[i]=0;//全部初始化為0，即未訪問狀態 } int m;for(i=0;i if(G->adjlists[i].vertex==c)//根據字符查找序號 { m=i; DFS(G,i,visit); break; } } //繼續訪問未被訪問的結點 for(i=0;i if(visit[i]==0) DFS(G,i,visit);} cout< int e=0; DeQueue(Q,&e); cout< visit[e]=1; edgenode* p=new edgenode; p=G->adjlists[e].edgelink; if(p) { int m=p->endver; if(m==0) { EnQueue(Q,m); while(visit[m]==0) { p=p->edgenext; if(p==NULL) break; m=p->endver; EnQueue(Q,m); } } } } } void BFStraversal(Graph *G,char c){ cout<<“該圖的廣度優先遍歷結果為:”< visited[i]=0;} int m;for(i=0;i if(G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } } //繼續訪問未被訪問的結點 for(i=0;i if(visited[i]==0) BFS(G,i,visited);} cout< 四、實驗結果及分析 五、實驗總結 本次試驗采用的是鄰接表的方式實現圖的深度優先遍歷和。對于深度優先遍歷，主要是采用遞歸的方式。試驗本身問題不是太大，但要注意輸入的問題，什么時候用空格，什么時候用回車，這一點是需要注意的，因為一旦數據的輸入有問題，結果當然也就不可能正確了。只有正確的輸入數據，建立圖，才能得出正確的遍歷結果。 “計算機軟件技術基礎”課程實驗報告 （六）實驗名稱：數據庫及SQL語言 班級_______ 姓名__________ 學號______實驗日期： 實驗機時：3 學時實驗成績： ----------------- 一.實驗目的： 1、學習數據庫設計的一般過程及相關技術； 2、學習access數據庫管理系統； 3、掌握數據庫的輸入、查詢、更新操作。 二.實驗內容： 1、需求陳述：某校圖書館要建立一個圖書數據管理系統。該圖書館的圖書（書名、分類號、作者、出版社）存放在不同的借閱室（室名），讀者（姓名、系名、類別）在書架上找到所需圖書后，可以到服務臺辦理借閱（借閱時間）。 設計要求： ? 分析需求，建立數據庫的概念模型； ? 將概念模型轉換為關系模型（注意：是否需要作規范化處理）； ? 寫出創建基本表的SQL語句； ? 寫出以下查詢要求的SQL語句： （1）所有“高等數學習題集”書的信息； （2）讀者“李林”借了什么書？ （3）“社會學原理”在哪個借閱室？ 2、在access數據庫管理系統中建立所設計的關系表； 3、向各表中輸入一組實驗數據（元組）（注意：關系完整性）； 4、對數據庫進行查詢。 三.實驗結果： 1、實體-關系圖； 2、數據庫表； 3、創建基本表的語句； 4、查詢語句。 “計算機軟件技術基礎”課程實驗報告 （五）實驗名稱：排序算法 班級_______ 姓名__________ 學號______實驗日期： 實驗機時：3 學時實驗成績： ----------------- 一.實驗目的： 1、掌握主要排序算法的思想和實現技術。 二.實驗內容： 1、設計一程序，要求：輸入學生“軟件技術基礎”課的成績（學 號、姓名、平均成績、總學分）；按總學分對學生數據進行排序。（要求：實現任選3種排序算法） 三.程序： 1、程序規范（輸入數據、功能、輸出數據） 2、設計分析（數據表示、算法） 3、C源代碼（電子版） 四.程序調試： 數據結構實驗報告 課程 數據結構 _ 院 系 專業班級 實驗地點 姓 名 學 號 實驗時間 指導老師 數據結構上機實驗報告1 一﹑實驗名稱： 實驗一——鏈表 二﹑實驗目的： 1.了解線性表的邏輯結構特性； 2.熟悉鏈表的基本運算在順序存儲結構上的實現，熟練掌握鏈式存儲結構的描述方法； 3.掌握鏈表的基本操作（建表、插入、刪除等）4.掌握循環鏈表的概念，加深對鏈表的本質的理解。5.掌握運用上機調試鏈表的基本方法 三﹑實驗內容： （1）（2）（3）（4）創建一個鏈表 在鏈表中插入元素 在鏈表中刪除一個元素 銷毀鏈表 四﹑實驗步驟與程序 #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的數據元素 LinkList p; } void LinkListLengh(LinkList &L){//計算鏈表L的數據元素個數。int i=0;p=L->next;if(L->next==NULL){ } cout<<“鏈表的數據元素為:”;while(p) { cout< data<<“ ”; p=p->next;} cout<<“鏈表沒有元素!”< } LinkList p;p=L->next;while(p){ i++; p=p->next; } cout<<“鏈表的數據元素個數為:”< 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個數據元素。 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<<“鏈表已經被銷毀!”< LinkList L; int i,j,x;cout<<“第一次數據結構上機實驗—鏈表”< 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);} 五﹑實驗結果 六﹑實驗心得體會： 鏈表是一種常見的重要的數據結構。它是動態地進行存儲分配的一種結構。它可以根據需要開辟內存單元。鏈表中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為用戶需要用的實際數據，二為下一個結點的地址。 實驗的程序設計規劃（實現的功能、分幾個模塊、子函數）（1）編寫鏈表創建子函數void CreatLinkList(L,j)（2）編寫鏈表插入子函數 int InsertLinkList(LinkList &L, int i, int x)（3）鏈表的打印int PrintLinkList(LinkList &L)（4）編寫鏈表刪除子函數 int DeleteLinkList(LinkList &L,int i)（5）編寫鏈表銷毀子函數void DestroyLinkList(LinkList &L)（6）編寫主函數Main()，通過功能菜單調用子函數（7）編譯調試程序 經過多次的調試，修改，實驗結果終于正確了，在這個過程中，經歷了不知道怎么進行聲明區的編寫如包含文件，宏定義，函數聲明，全局變量聲明，結構體等的定義等的結合，到學會了使用先把程序主要規劃為四個部分來寫就簡單多了，第一，定義；第二，寫所要調用的子函數；第三，寫主函數，調用子函數；第四就是程序的編譯與調試，修改。數據結構實驗需要我們對每個程序的算法有深刻的理解，才能應用到實際中去，因此我們需要在做實驗之前要熟悉實驗的內容，且先把所要實驗的程序寫出來，在實驗中就可以查找錯誤并加以改正，這是一個成長的過程。 數據結構上機實驗報告一﹑實驗名稱： 實驗二—隊列 二﹑實驗目的： 1.掌握隊列這種抽象數據類型的特點, 掌握棧與隊列在實際問題中的應用和基本編程技巧,并能在相應的問題中選用它;2.熟練掌握循環隊列和鏈隊列的基本操作實現算法，特別是隊滿和隊空的描述方法； 3．掌握棧與隊列的數據類型描述及特點； 4.掌握棧的順序和鏈式存儲存表示與基本算法的實現； 5.掌握隊列的鏈式存儲表示與基本操作算法實現;6.按照實驗題目要求，獨立完成實際程序的編寫編寫、調試和運行，并通過用例數據的運行過程抓獲相關屏面驗證程序設計的正確性； 7.認真書寫實驗報告，并按時提交。 三﹑實驗內容： 對順序循環隊列，常規的設計方法是使用対尾指針和對頭指針，對尾指針用于指示當前的対尾位置下標，對頭指針用于指示當前的対頭位置下標。現要求： （1）掌握棧和隊列的特點，即后進先出和先進先出的原則。（2）設計一個使用對頭指針和計數器的順序循環隊列抽象數據類型，其中操作包括：初始化，入隊列，出隊列，取對頭元素和判斷隊列是否為空； （3）編寫主函數進行測試。 四﹑實驗步驟與程序 #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:結束程序，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; } } 五﹑實驗結果 六﹑實驗心得體會： 程序主要構造了主函數main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等調用函數，實現了隊列的創立，隊列是否為空的判斷，入隊和出隊等功能。 通過此次實驗，加深了對隊列的存儲結構的了解，同時也對程序設計能力有了提高，加深了對隊列先進先出性質的理解，它允許在表的一端進行插入，在另一端刪除元素，這和我們日常生活中的排隊是一致的，最早進入隊列的元素最早離開。我們往往寫不出程序，這其中的原因我覺得是對程序的結構不是很了解，對實驗的內容也不熟練的結果，數據結構給我們許多程序的算法和模型，對我們寫程序的思維有很大的鍛煉，我們應珍惜每次上機實驗的機會去實踐課堂上所學的東西并從中發現問題，從而達到提升寫程序的能力。 數據結構上機實驗報告一﹑實驗名稱： 實驗三—二叉樹的遍歷 二﹑實驗目的： 1、熟悉二叉樹的結構特性，了解相應的證明方法； 2、掌握二叉樹的生成，掌握二叉樹的定義和存儲表示，學會建立一棵特定二叉樹的方法； 3、理解二叉樹的三種遍歷方法：先序遍歷、中序遍歷和后序遍歷； 4、學會編寫實現樹的各種操作的算法。 二、實驗內容： 1、使用類定義實現二叉樹，補充完整所缺的函數，并實現創建和遍歷二叉樹的基本操作； 2、編程實現在二叉鏈表這種存儲方式下，實現二叉的遍歷，可采用遞歸或者非遞歸實現，遍歷算法為在先序、中序和后序遍歷算法。 三、實驗步驟與程序： #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()//主函數 { printf(“------------二叉樹的遍歷-------------n”);printf(“請輸入要遍歷的數：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍歷:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍歷:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍歷:”);printf(“n”);PostOrder(Ta);} 五﹑實驗結果 六﹑實驗心得體會： 實驗的程序設計規劃（實現的功能、分幾個模塊、子函數）（1）先序遍歷遞歸算法函數：void PreOrder(BiTree T)（2）中序遍歷遞歸算法函數：void InOrder(BiTree T)（3）后續遍歷遞歸算法函數：void PostOrder(BiTree T)（4）主函數的實現：void main() 在實驗前我認真閱讀關于二叉樹的實現的內容，為編程實現第一步，本次實驗通過按上述的實驗步驟一步步實現的，實驗過程中出現了一些錯誤，經過一步步的調試，修改錯誤，得到了二叉樹的遍歷用遞歸運算的方法的程序。通過這個實驗，我體會到了理解數據結構的重要性，這有真正理解了定義數據類型的好處，才能用好這樣一種數據結構。二叉樹的先序，中序與后序的輸出都用了遞歸的算法，而且用起來不是很復雜，這使我更進一步理解了函數遞歸調用并得到靈活運用；在實現算法上，從算法的效率看，遞歸方法書寫形式較為簡潔，更為直觀，一般具有較好的空間效率。 總之，不管做什么實驗，我們在做實驗前都要先預習，對所做的實驗有較深的理解，在做實驗的時候需要很嚴謹，仔細的查找錯誤，從而能在實驗中收獲知識，提升自己。 數據結構上機實驗報告4 一﹑實驗名稱： 實驗四—查找 二﹑實驗目的： 1、熟悉掌握順序表的查找方法； 2、熟練掌握二叉排序樹的構造方法和查找算法 3、掌握描述查找過程的判定樹的構造方法，以及按照定義計算各種查找方法在等概率情況下查找成功時的平均查找長度； 4、學會定義線性表的儲存類型，實現C++程序的基本結構對線性表的一些基本操作和具體的函數定義； 5、掌握順序表的基本操作，實現順序表的查找的等基本運算； 6、掌握對于多函數程序的輸入，編輯，調試和運算過程。 二、實驗內容： 1、實現順序表的查找算法 2、關于衡量查找的主要操作—查找的查找平均效率的平均長度的討論。 三、實驗步驟與程序： #include element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num);int main(){ int i,num,searchnum,k; printf(“---------------數據結構查找實驗-------------n”);printf(“請輸入數據元素的個數：”);scanf(“%d”,&num);printf(“請輸入數據的元素：n”);for(i=0;i printf(“請輸入要查詢的數據元素:”);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 六﹑實驗心得體會： 實驗的程序設計規劃為先寫一個主函數int main()，再寫一個查找的子函數int seqsearch(element list[],int searchnum,int num)，主函數通過調用子函數的方法實現程序的設計。 所謂“查找”即為在一個眾多的數據元素（或記錄）的查找表中找出某個“特定的”數據元素（或記錄），通過本次實驗，我更進一步的了解數據結構程序實驗設計實現算法的基本模型，和算法實現等基本內容，學會了順序表的查找方法。 數據結構上機實驗報告5 一﹑實驗名稱： 實驗五—內部排序 二﹑實驗目的： 1、通過實現下述實驗內容，學習、實現、對比各種排序算法，掌握各種排序算法的優劣，以及各種算法使用的情況，并加以靈活應用。 2、掌握各種排序時間復雜度的分析方法。 二、實驗內容： 1、插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。 2、快速排序：首先選擇一個基準，將記錄分割為兩部分，左支小于或等于基準，右支則大于基準，然后對兩部分重復上述過程，直至整個序列排序完成。 3、討論各種內部排序方法的基本思路，算法特點，排序過程及它們的時間復雜度的分析。 三、實驗步驟與程序： #include } int x;void charu();void kuaisu();printf(“----------內部排序---------n”);printf(“ 1、插入排序：n”);printf(“ 2、選擇排序：n”);printf(“請根據序號選擇：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m; printf(“插入排序n”); printf(“請輸入個您想排序的數據: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(“請輸入個您想排序的數據: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”);} 五﹑實驗結果： 六﹑實驗心得體會： 排序的功能是將一個數據元素（或記錄）的任意序列，從新排成按關鍵字有序的序列；直接插入排序的穩定性比快速排序高，且算法較簡單。本次實驗運用到的是插入排序和快速排序。 實習報告 題 目 : 實現一個約瑟夫環程序 班級：031021姓名：王帥學號：03102076 一、需求分析 1． 本演示程序中，利用單向循環鏈表存儲結構存儲約瑟夫環數據（即n個人的編號和密碼）。 2． 演示程序以用戶和計算機的對話方式執行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數據，運算結果顯示在其后。 3． 程序執行的命令包括： 1)構造單向循環鏈表；2）進行數值的輸入，并作判斷分析；3）約瑟夫算法的實現與結果輸出；4）結束。 4． 測試數據 m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，（正確的出列順序為6，1，4，7，2，1，3，5）。 二、概要設計 1．單向循環鏈表的抽象數據類型定義為： ADT List｛ 數據對象：D=｛ai | ai?正整數，I=1，2，......，n,n≥0｝數據關系：R1=｛< ai-1，ai > |，ai-1，ai?D,I=1，2，......，n｝基本操作： Init List(&L) 操作結果：構造一個空的線性表L。 List Insert(&L,i,e) 初始條件：線性表L已存在，1≤i≤List Length(L)+1.操作結果：在L中第i個位置之前插入新的數據元素e，L長度加1。List Delete(&L,i,&e) 初始條件：線性表L存在非空，1≤i≤List Length(L).操作結果：刪除L的第i個元素，并用e返回其值，L長度減1。 2． 程序包含四個模塊： 1）主程序模塊： void main() { 初始化； for（;;） {} while（命令=開始） { 接受命令； 處理命令； } for（;;） { } } 2）有序表單元模塊——實現有序表的抽象數據類型； 3）節點結構單元模塊——定義有序表的節點結構； 4）數據輸入分析模塊——判斷輸入數據正確有效； 各模塊之間的調用關系如下： 主程序模塊 ↓ 有序表結構模塊 ↓ 節點結構單元模塊 ↓ 數據輸入分析模塊 三、詳細設計 1、結點類型，指針類型 TypedefstructLNode{ int code,date;//code 為人所在位置 date為人持有的密碼 struct LNode *next; };// 結點類型，指針類型 2、構造單向循環鏈表 struct LNode *p,*head,*q;//定義頭節點，和指針 for(i=2;i<=n;i++) { struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配 新結點空間 s->code=i; input(s->date); p->next=s; p=p->next; } p->next=head;//根據輸入的人數，進行單項循環鏈表的創建，p指向最后一個結點，并與頭節點鏈接，形成單項循環鏈表 3、約瑟夫環的程序實現部分 while(n!=1)//判斷輸入人數，如為1則直接輸出結果，不循環 { for(i=1，m=m%n;i { p=p->next; } q=p->next;//找到要刪除節點 p->next=q->next;//找到要刪除節點的后繼，并連接新環m=q->date;//找到下一個密碼 printf(“%d”,q->code); free(q);//釋放已刪除節點空間 n--;//鏈表長度減一 } printf(“%d”,p->code);//約瑟夫環的結果輸出 4、其他函數代碼 數值的輸入限制 int input() { int y,k,z=0; char c;//元素類型 char a[4];//數組初始化 if(!z)//輸入判斷，確定位數字或控制字符且位置和密碼不為零 { for(y=0;y<4;y++) { c=getch(); if(c>=48&&c<=57)//確定為輸入數字 {a[y]=c; putch(c); } else { y--; if(c=='r')//確定輸入為控制字符 即回車或者刪除 break; else if(c==8) {a[y]='n'; y--;} continue; } } k=atoi(a);//確定最終輸入數字的值 printf(“n”); z=k; if(z==0) printf(“ERROR!The number couldn't be 0!n”);// 輸入為零，重新輸入 } return(k);//數值的返回 5、函數的調用關系圖反映程序層次結構 Main→input 四、調試分析 1、早期程序只寫了約瑟夫環的實現部分，沒有對輸入數據進行篩選，調試的時候會經常出錯。比如是輸入字母，或者輸入0，大于32767溢出； 2、早期的循環過程中沒有進行優化，導致循環次數過多，浪費時間； 3、為了輸出時美觀，分別在input和main函數主體內做了兩次，輸入非零的判斷，浪費了資源； 4、算法的時空分析 為了限制在輸入過程中不會上溢，只在輸入中限定為四個不全為零的數字，但是做的是do……while循環，復雜度為o（1）; 當n大于1時： 在數據輸入中，鏈表的創建是for循環，時間復雜度為o（n-1） 在約瑟夫環實現程序中，為for循環。時間復雜度為o（m%n-1） 當n=1時，復雜度為o（1）。 五、用戶手冊 用戶根據提示，先輸入起始密碼m，然后輸入人數n，再根據人數，分別輸入每個人的密碼date，數值均不能為0，否則會提示重新輸入，輸入為字母則自動丟棄，輸入錯誤可用刪除鍵進行修改，輸入完成后按回車鍵確定本次輸入完畢（若輸入數字大于9999，則第五位自動轉換為下一個數字的起始位，依此類推）。 當n個數字全部輸入完畢，則自動顯示結果，按任意鍵則退出本程序。 六、測試結果 第一組：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”//內存空間分配頭文件 #include “stdio.h”//輸入輸出函數頭文件 #include “stdlib.h”//input函數中字符串轉短整形函數的頭文件 #include “conio.h”//最后顯示結果、清屏函數頭文件第二篇：《數據結構》上機作業——實驗報告(六)
第三篇：《數據結構》上機作業——實驗報告(五)[推薦]
第四篇：數據結構上機實驗報告
第五篇：數據結構上機實驗報告
點擊咨詢 