第一篇：數(shù)據(jù)結(jié)構實訓報告
北京聯(lián)合大學
實訓報告
課程（項目）名稱： 數(shù)據(jù)結(jié)構 學 院： 專 業(yè)： 班 級： 學 號：
姓 名： 成 績：
2012年 6 月 21 日
數(shù)據(jù)結(jié)構實訓任務一
一、任務與目的：
1、用順序表表示兩個無序集合A、B，實現(xiàn)集合的如下操作，求兩個集合的并集、交集、差集。
2、用順序表表示兩個集合A、B（集合A、B都是有序遞增的情況）實現(xiàn)集合的如下操作，求兩個集合的并集、交集、差集。
3、用帶頭單鏈表存儲結(jié)構表示兩個無序集合A、B，實現(xiàn)集合的如下操作，求兩個集合的并集、交集、差集。
4、用帶頭單鏈表存儲結(jié)構表示兩個集合A、B（集合A、B都是有序遞增的情況），實現(xiàn)集合的如下操作，求兩個集合的并集、交集、差集。
5、殺人游戲 N個人坐成一圈玩殺人游戲，按順時針編號
N。從1號開始順時針開始數(shù)到第m號就殺掉第一個人，被殺掉的人要退出游戲。
如果數(shù)到了編號的末尾，接著數(shù)開頭的編號。
重復，直至殺掉一半人時，游戲結(jié)束，聰明的你能告訴我活到最后的幸存者最初的編號是多少嗎？ 輸入數(shù)據(jù)：N、M ；輸出數(shù)據(jù)：幸存者的編號
分析該程序，如果N=20，M=2，……10。聰明的你應選擇的編號是多少，（提示，計算出M分別等于1到10的情況下，那些編號生存概率較大）。給出實驗結(jié)果
6、作業(yè)抽查問題：有35個學生的班級，由于某種原因不能夠做到全部檢查作業(yè)，現(xiàn)在希望每次抽查10名學生，希望能夠隨機抽查，并能夠有記憶，即希望抽查過的學生，下次抽查的概率有所減小，但避免不被抽查。設計一個算法實現(xiàn)該功能，給出你的解釋。1.void BingSet(SqList A, SqList B,SqList &C){//求并集
int i,j;int flag=0;C.length=0;for(i=0;i if(flag==0) {C.elem[i]=B.elem[j];i++;} } C.length=i;} void JiaoSet(SqList A, SqList B,SqList &C){//求交集 int i,j;int flag=0;C.length=0;i=0;for(j=0;j if(flag!=0) {C.elem[i]=B.elem[j];i++;} } C.length=i;} void ChaSet(SqList A, SqList B,SqList &C){//求差集 int i,j,k;int flag=0;C.length=0;k=0;for(i=0;i if(flag==0) {C.elem[k]=A.elem[i];k++;} } C.length=k;} 運行結(jié)果： 2.void BingSet(SqList A, SqList B,SqList &C){//求并集 int i,j,k;k=0;C.length=0;for(i=0,j=0;(i {C.elem[k]=A.elem[i];k++;i++; } else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {C.elem[k]=B.elem[j];k++;j++;} } } if(i {C.elem[k]=A.elem[i];k++;i++; } } if(j {C.elem[k]=B.elem[j];k++;j++;} } C.length=k;} void JiaoSet(SqList A, SqList B,SqList &C){//求交集 int i,j,k;k=0;C.length=0;for(i=0,j=0;(i {i++;} else {if(A.elem[i]==B.elem[j]) {C.elem[k]=A.elem[i];k++;i++;j++; } else {j++;} } } C.length=k;} void ChaSet(SqList A, SqList B,SqList &C){//求差集 int i,j,k;int flag=0;k=0;C.length=0;for(i=0,j=0;(i {C.elem[k]=A.elem[i];i++;k++; } else {if(A.elem[i]==B.elem[j]) {i++;j++;} else {j++; } } } if(i {C.elem[k]=A.elem[i];k++;i++;} } C.length=k;} void InserOrder_Sq(SqList &L,ElemType e){int i,j;for(i=0;i L.elem[j+1]=L.elem[j];L.elem[i]=e;L.length++;} 運行結(jié)果： 3.void bing(link &p,link &h,link &q) {//求并集 link l,s,m;int j=0,i=0;q=new LNode;q->date=NULL;q->next=NULL;s=p->next;m=q;while(s){l=new LNode; l->date=s->date; l->next=NULL; s=s->next; m->next=l; m=l; s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==0){l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l; } s=s->next;} } void jiao(link &p,link &h,link &q) { //求交集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q; s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==1) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l; } s=s->next;} } void cha(link &p,link &h,link &q) {//求差集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=p->next;while(s){i=s->date; j=Locate(h,i); if(j==0){l=new LNode; l->date=s->date; l->next=NULL; m->next=l;m=l;} s=s->next;} } void shengcheng(link &p,link &h,link &q) { int i,j=0;Elem e;for(i=0;i<11;){if(i==0){p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=rand()%50+1; j=Locate(p,e); if(j==0) {LInsert(p,e);i++;}}}} 運行結(jié)果： 4.void bing(link &p,link &h,link &q) { //并集 link l,s,m;int j=0,i=0;q=new LNode;q->date=NULL;q->next=NULL;s=p->next;m=q;while(s){l=new LNode; l->date=s->date; l->next=NULL; s=s->next; m->next=l; m=l;} s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==0) {LInsert(q,i);} s=s->next;} } void jiao(link &p,link &h,link &q) {//交集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=h->next;while(s){i=s->date; j=Locate(p,i); if(j==1) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l;} s=s->next;} } void cha(link &p,link &h,link &q) {//差集 link l,s,t,m;int j=0;Elem i=0;q=new LNode;q->date=NULL;q->next=NULL;m=q;s=p->next;while(s){i=s->date; j=Locate(h,i); if(j==0) {l=new LNode; l->date=s->date; l->next=NULL; m->next=l; m=l;} s=s->next;} } void shengcheng(link &p,link &h,link &q) {int i,j=0;Elem e;for(i=0;i<11;){if(i==0) {p=new LNode; p->date=NULL; p->next=NULL; h=p;q=p;i++;} else {e=rand()%50+1; j=Locate(p,e); if(j==0) {LInsert(p,e);i++;}}}} 運行結(jié)果： 5.#include struct kill { int num; struct kill *next;}; struct kill *create(int m) {struct kill *head,*p1,*p2;int i;p1=p2=(struct kill*)malloc(LEN);head=p1; head->num=1; for(i=1,p1->num=1;i p2->next=p1;p2=p1;} p2->next=head;return head;} struct kill *findout(struct kill *start,int n){int i; struct kill *p;i=n;p=start; for(i=1;i struct kill *letout(struct kill *last){struct kill *out,*next;out=last->next; last->next=out->next;next=out->next;free(out);return next;} void main() { int m,n,i,servive;struct kill *p1,*p2; cout<<“請輸入?yún)⒓託⑷擞螒蚩側(cè)藬?shù)m:”< cout<<“要殺掉的人的序號n:”< { p1=p2=create(m);for(i=1;i p2=letout(p1);p1=p2;} servive=p2->num;free(p2);} cout<<“幸存者是：”< 6.#include //學生id int times; //定義學生抽查數(shù)};Student stu[35];//35個學生 int cho[10]; //抽查的10個學生 int top; //已抽查學生數(shù) int choose(){int n=rand()%35;//隨機抽取 for(int i=0;i int n2=rand()%stu[n].times;//否則幾率按抽取的次數(shù)減小,具體為(1/抽取次數(shù))if(n2==0)return n;else return choose();} void main(){char a='Y';srand(time(0));//隨機數(shù)初始化 int i;for(i=0;i<35;i++)//學生初始化 {stu[i].id=i+1;stu[i].times=0;} while(a=='Y'||a=='y'){int tmp;top=0;for(i=0;i<10;i++)//抽取10個學生 {tmp=choose();//抽取學生 cho[top++]=tmp;stu[tmp].times++;cout<<“第”< 數(shù)據(jù)結(jié)構實訓任務二 一、任務與目的：主要考察的是棧與隊列的邏輯結(jié)構和存儲結(jié)構。 1、用棧，判斷一個算數(shù)表達式中的圓括弧、方括弧和花括弧是否匹配。 2、用棧，把十進制的整數(shù)轉(zhuǎn)換為二至九之間的任一進制 3、設計一個算法，檢測一個字符串數(shù)組是否是回文，回文是指這個字符串是否關于中心對稱。int Check（char a[]，int n） 4、采用SPT規(guī)則的單機生產(chǎn)計劃問題。問題描述如下，存在一臺機器，要加工n個工件，每個工件i都有一個確定的加工時間，采用按照 遞增的順序，進行加工，計算每個工件的完成時間（初始加工時間為0）。設計一個算法，輸入工件數(shù)量n，隨機在[1，30]的區(qū)間內(nèi)產(chǎn)生每個工件的加工時間。按照SPT規(guī)則進行加工，輸出每個工件的完成時間。 5、采用EDD規(guī)則的單機生產(chǎn)計劃問題。問題描述如下，存在一臺機器，要加工n個工件，每個工件i都有一個確定的加工時間，同時每個工件都有一個確定的交貨期，采用按照 遞增的順序，進行加工，計算每個工件的完成時間（初始加工時間為0）。設計一個算法，輸入工件數(shù)量n，隨機在[1，30]的區(qū)間內(nèi)產(chǎn)生每個工件的加工時間，在區(qū)間[2，20*n]內(nèi)隨機產(chǎn)生每個工件的交貨期。按照EDD規(guī)則進行加工，輸出每個工件的完成時間，計算每個工件i完成時間和 的差值。1.void Ininstack(stack &s) {//初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) {//擴容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) { //入棧 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} stype Pop(stack &s) {//出棧 stype e;e=s.elem[s.top];s.top--;return e;} stype GetTop(stack s) {//取棧頂 stype e;e=s.elem[s.top ];return e;} void main(){stype e,t,ch;stack s;char a[20];int i=0,n;Ininstack(s);cout<<“請輸入算術表達式(以$結(jié)尾):”;while(ch!='$'){cin>>ch; a[i]=ch;i++;} n=i;for(i=0;i {e=a[i];Push(s,e);} if(a[i]=='}'||a[i]==']'||a[i==')']) {t=GetTop(s); if(a[i]=='}' && t=='{')Pop(s); else if(a[i]==']' && t=='[') Pop(s);else if(a[i]==')' && t=='(') Pop(s);}} if(s.top==-1) cout<<“括號匹配!”< cout<<“括號不匹配!”< 2.void Ininstack(stack &s) { //初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) { //擴容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) {//入棧 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} stype Pop(stack &s) { //出棧 stype e;e=s.elem[s.top];s.top--;return e;} void main(){stack s;int a,b;Ininstack(s);cout<<“請輸入任意非負十進制數(shù):”;cin>>a;cout<<“請輸入需要轉(zhuǎn)換的進制數(shù)(進制數(shù)為二至九):”;cin>>b;while(a){Push(s,a%b);a=a/b;} while(!(s.top==-1))cout< 運行結(jié)果： 3.void Ininstack(stack &s) { //初始化 s.elem=new stype[SIZE];s.top=-1;s.size=SIZE;s.insize=IN;} void INsize(stack &s) { //擴容 stype *a;int i;a=new stype[s.size+s.insize];for(i=0;i<=s.top;i++)a[i]=s.elem[i];delete []s.elem;s.elem=a;s.size+=s.insize;} void Push(stack &s,stype e) {//入棧 if(s.top==(s.size-1))INsize(s);s.top++;s.elem[s.top]=e;} void Error(char *a) { cout< stype Pop(stack &s) { stype e;e=s.elem[s.top];s.top--;return e;} int Check(char a[],int n,stack &s) {//判斷 int i;char e;Pop(s);for(i=0;i urn 0;} void main(){stack s; r ch,a[50];t i=0,n,t;instack(s);cout<<“請輸入字符串(以$結(jié)尾):”;while(ch!='$'){cin>>ch;[i]=ch;ush(s,ch);+;} n=i;Check(a,n,s);if(t==1)cout<<“是回文!”< 運行結(jié)果： 4.void chushihua(sqlist &a) //初始化 {a.elem=new elemtype[SIZE]; a.num=new elemtype[SIZE]; a.welem=new elemtype[SIZE]; a.length=0; a.listsize=SIZE; a.incrementsize=INCREMENT;} void paixu(sqlist a) //排序 { int i,j,t,m;for(i=0;i 5.typedef struct {elemtype *elem; //加工時間 elemtype *num; //序號 elemtype *welem; //完成時間 elemtype *jelem; //交貨期 elemtype *celem; //差值 int length; //長度 int listsize; //分配量 int incrementsize;//增補量 }sqlist;void chushihua(sqlist &a) //初始化 {a.elem=new elemtype[SIZE]; a.num=new elemtype[SIZE]; a.welem=new elemtype[SIZE]; a.celem=new elemtype[SIZE]; a.jelem=new elemtype[SIZE]; a.length=0; a.listsize=SIZE; a.incrementsize=INCREMENT;} void paixu(sqlist a) //排序 {int i,j,t,m,p;for(i=0;i a.welem[i]=a.elem[i];else {a.welem[i]=a.elem[i]+a.welem[i-1];} a.celem[i]=a.jelem[i]-a.welem[i];cout< 數(shù)據(jù)結(jié)構實訓任務書三：二叉樹鏈式存儲的基本操作 1、創(chuàng)建二叉樹 a)熟悉使用教材的先序創(chuàng)建二叉樹的方法 b)編寫一個算法，實現(xiàn)在已知二叉樹的先序序列和中序序列的情況下創(chuàng)建二叉樹。 c)如果已知二叉樹的順序表示形式，將其轉(zhuǎn)換為二叉樹的鏈式存儲方式。 2、二叉樹的遍歷 a)先序、中序和后序三種形式的鏈式存儲遞歸式算法 b)先序、中序和后序三種形式的鏈式存儲非遞歸式算法 c)層次遍歷的算法。 3、二叉樹一些基本操作 a)計算二叉樹的深度； b)計算二叉樹的葉子節(jié)點個數(shù) c)計算二叉樹的單支節(jié)點的個數(shù) d)計算二叉樹的雙支節(jié)點的個數(shù) 4、編寫一個主函數(shù)能夠測試你所設計的算法。 主函數(shù)調(diào)用教材創(chuàng)建二叉樹的創(chuàng)建教材圖7-10的二叉樹鏈式存儲方式。 {p=st.a[st.top]; st.top--; cout< data; while(p->right!=NULL) {st.top++; st.a[st.top]=p->right; q=p->right; while(q->left!=NULL) {st.top++; st.a[st.top]=q->left; q=q->left; } 代碼：#include //二叉樹結(jié)點的結(jié)構體表示形式 {char data;struct node* left,*right;}BTree;typedef BTree *Tree;typedef struct stackelem //棧的結(jié)構體表示形式 {BTree* a[MAXSIZE];int top;}Stack;void CreateBiTree_Rec(Tree &T)//先序創(chuàng)建二叉樹的方法 {char ch;cin>>ch;if(ch=='#') T=NULL;else {T= new BTree; T->data=ch; CreateBiTree_Rec(T->left); CreateBiTree_Rec(T->right);}} void Preorder(Tree t)//前序遍歷，遞歸的方法 {if(NULL!=t){cout< Preorder(t->left); Preorder(t->right);}} void Preorder2(Tree t)//前序遍歷的非遞歸實現(xiàn) {Tree p;Stack st;st.top=-1;if(NULL==t){return;} else {st.top++; st.a[st.top]=t; while(st.top!=-1) {p=st.a[st.top]; st.top--; cout< data; if(p->right!=NULL) {st.top++; st.a[st.top]=p->right;} if(p->left!=NULL) {st.top++; st.a[st.top]=p->left;} void Inorder(Tree t)//中序遍歷，遞歸實現(xiàn) {if(NULL!=t){Inorder(t->left); cout< Inorder(t->right);}} void Inorder2(Tree t)//中序遍歷，非遞歸實現(xiàn) {Tree p,q;Stack st;st.top=-1;if(NULL==t){return;} else {while(t!=NULL) {st.top++; st.a[st.top]=t; t=t->left; }}} 20 } while(st.top!=-1)break; } }}} void Postorder(Tree t)//后序遍歷，遞歸實現(xiàn) {if(t!=NULL){Postorder(t->left); Postorder(t->right); cout< {st.top++; st.a[st.top]=t; t=t->left; } m=NULL; flag=1; while(st.top!=-1 && flag) {t=st.a[st.top]; if(t->right==m) {cout< st.top--; m=t;} else {t=t->right; flag=0; }}} while(st.top!=-1);} int Height(Tree t)//求二叉樹的高度，遞歸實現(xiàn){int depth1,depth2;if(!t){ return 0;} else {depth1=Height(t->left); depth2=Height(t->right); if(depth1>depth2) {return(depth1+1); } else {return(depth2+1); }}} int leafs_rec(Tree t) //葉子結(jié)點 {int l,r;if(t==NULL) return 0;else if((t->left==NULL)&&(t->right==NULL)) return 1;else {l=leafs_rec(t->left); r=leafs_rec(t->right); return(l+r);}} int danzhi(Tree t)//單只 {if(t==NULL) return 0;else if((t->left==NULL)&&(t->right!=NULL)) d++;else if((t->left!=NULL)&&(t->right==NULL)) d++;danzhi(t->left);danzhi(t->right);return(d);} int shuangzhi(Tree t) //雙只 {if(t==NULL) return 0;else if((t->left!=NULL)&&(t->right!=NULL)) l++;shuangzhi(t->left);shuangzhi(t->right);return(l);} void TraversalOfLevel(Tree t)//層次遍歷二叉樹 { Tree p,q[100];int f=0,r=0;if(t!=NULL) {p=t; q[r]=t; r++;} while(f!=r){p=q[f];f++; cout< data; if(p->left!=NULL) {q[r]=p->left; r++; } if(p->right!=NULL) {q[r]=p->right; r++;} }} void CreateBiTree_XZ(Tree &T,char a[],int la,int ra,char b[],int lb,int rb)//知先序、中序求二叉樹 {int i,lla,lra,llb,lrb,rla,rra,rlb,rrb;if(la>ra) T=NULL;else {T=new BTree; T->data=a[la]; for(i=lb;i<=rb;i++) {if(b[i]==a[la]) break;} lla=la+1; lra=lla+i-lb-1; rla=lra+1; rra=ra;llb=lb; lrb=i-1; rlb=i+1; rrb=rb; CreateBiTree_XZ(T->left,a,lla,lra,b,llb,lrb); CreateBiTree_XZ(T->right,a,rla,rra,b,rlb,rrb);}} void CreateBiTree_SX(Tree &T,char S[],int pos,int n)//二叉樹的順序表示形式，將其轉(zhuǎn)換為二叉樹的鏈式存儲方式 {int i;if(S[pos]=='#') T=NULL;else {T=new BTree; T->data=S[pos]; if((i=2*pos+1)<=n) CreateBiTree_SX(T->left,S,i,n); else T->left=NULL; if((i=2*pos+2)<=n) CreateBiTree_SX(T->right,S,i,n); else T->right=NULL;}} void main(){int n,i;char a[30],b[30],c[30];Tree s;Tree m;cout<<“請輸入先序:”;CreateBiTree_Rec(m);cout< 數(shù)據(jù)結(jié)構實訓任務書四：圖的操作 1、建立圖的存儲結(jié)構 a)創(chuàng)建圖的鄰接矩陣表示方式 b)創(chuàng)建圖的鄰接表表示方式 c)實現(xiàn)兩種方式的互換 2、圖的遍歷 a)基于鄰接矩陣的深度和廣度遍歷 b)基于鄰接表的深度和廣度遍歷 3、最小生成樹，使用Prim算法實現(xiàn)從某一節(jié)點出發(fā)的圖的最小生成樹25 4、單源最短路徑，算法8-10 5、關鍵路徑算法。 1．代碼： typedef enum{DG,DN,UDG,UDN}GKind;typedef enum{FALSE,TRUE}Boolean;Boolean visited[max_v];typedef int VType;typedef int EType;typedef int qtype;typedef struct { qtype *elem;int front;int rear;int qsize;int insize;}squeue;typedef struct { VType vexs[max_v];EType edges[max_v][max_v];int vnum,ednum;GKind kind;}MGraph;typedef struct ENode { int advex;struct ENode *next;int weight;}ENode;typedef struct VNode { VType vex;ENode *first;}VNode,List[max_v];typedef struct { List ver;int vnum,ednum;int kind;}AGraph;int LocatV(MGraph g,VType x){ int k;k=-1;for(k=0;(k //鄰接矩陣 { int i,j,k,v1,v2,w;cout<<“請輸入頂點數(shù):”;cin>>g.vnum;cout<<“請輸入邊數(shù):”;cin>>g.ednum;cout<<“請輸入構造頂點數(shù)組頂點值:”< g.edges[i][j]=infinity;cout<<“請輸入構造鄰接矩陣:”< cin>>v1; cout<<“請輸入頂點V2:”; cin>>v2; cout<<“請輸入權值:”; cin>>w; i=LocatV(g,v1); j=LocatV(g,v2); while((i<0)||(i>(g.vnum-1))||(j<0)||(j>(g.vnum-1))) { cout<<“編號超出范圍，請重新輸入頂點及權值:”< cin>>v1; cin>>v2; cin>>w; i=LocatV(g,v1); j=LocatV(g,v2); g.edges[i][j]=w; g.edges[j][i]=g.edges[i][j];}} int LocatVA(AGraph g,VType x){ int k;k=-1;for(k=0;(k cout<<“編號超出范圍，請重新輸入:”< cin>>v1; cin>>v2; i=LocatVA(g,v1); j=LocatVA(g,v2);} p=new ENode;p->advex=j;p->next=g.ver[i].first;g.ver[i].first=p;}} void DFS(AGraph g,VType i){ ENode *p;VType w;visited[i]=TRUE;cout< DFS(g,w);}} void Draverse(AGraph g) //鄰接表深度遍歷 { int i;for(i=0;i DFS(g,i);} void MDFS(MGraph g,VType i){ VType p;visited[i]=TRUE;cout< MDFS(g,p);}} void Mraverse(MGraph g) //鄰接矩陣深度遍歷 { int i;for(i=0;i MDFS(g,i);} void InQueue(squeue &q) { q.elem=new qtype[SIZE];q.front=q.rear=0;q.qsize=SIZE;q.insize=IN;} void INsize(squeue &q) { qtype *a;int i;a=new qtype[q.qsize+q.insize];for(i=0;i { if(((q.rear+1)%q.qsize)==q.front)INsize(q);q.elem[q.rear]=e;q.rear=(q.rear+1)%q.qsize;} void Error(char *a) //錯 { cout< { qtype e;if(q.front==q.rear)Error(“循環(huán)隊列空!”);e=q.elem[q.front];q.front=(q.front+1)%q.qsize;return e;} void BFS(MGraph g) { int i,w,u;squeue q; //初始化 //擴容 //入隊 //出隊 //鄰接矩陣廣度遍歷29 for(i=0;i cout< EnQueue(q,i); while(q.front!=q.rear) { u=DeQueue(q); for(w=0;w if(g.edges[u][w]&&(!visited[w])) { visited[w]=TRUE; cout< EnQueue(q,w);}}}} void MBFS(AGraph g) //鄰接表廣度遍歷 { int i,w,u;squeue q;ENode *p;for(i=0;i EnQueue(q,i); while(q.front!=q.rear) {u=DeQueue(q); cout< p=g.ver[u].first; while(p) {w=p->advex; if(visited[w]!=TRUE) { visited[w]=TRUE; EnQueue(q,w);} p=p->next;}}}}} void MatToList(MGraph l,AGraph &g)//此函數(shù)用于實現(xiàn)將鄰接矩陣轉(zhuǎn)換成鄰接表{ int i,j;ENode *p;g.vnum = l.vnum;for(i = 0;i g.ver[i].first = NULL; g.ver[i].vex=l.vexs[i];} for(i=0;i for(j = l.vnum-1;j>=0;j--) { if((l.edges[i][j]!= 0)&&(l.edges[i][j]!=100)){ p =(ENode*)malloc(sizeof(ENode)); p->advex = j; p->next= g.ver[i].first; g.ver[i].first= p;}}} void ListToMat(MGraph &g, AGraph l)//表轉(zhuǎn)矩陣 { int i,j;ENode *p;g.vnum=l.vnum;g.ednum=l.ednum;for(i = 0;i g.edges[i][j] = 0;for(i=0;i while(p){g.edges[i][p->advex] = 1; p=p->next;} }} void main(){ int j=0,i;MGraph g;AGraph h;ENode *p;CreatUDN_MG(g);cout<<“n此無向圖共有”< for(j=0;j cout< ”; cout< { p=h.ver[i].first; while(p!=NULL) { cout<<“<”< p=p->next; } } cout< Draverse(h);cout< MatToList(g,h);cout<<“n此無向圖共有”< for(j=0;j cout< ”; cout< { p=h.ver[i].first; while(p!=NULL) {cout<<“<”< p=p->next;} }} 2.代碼：#include struct edgeNode *link;//與之相連的端點 }; //存儲節(jié)點信息 vexNode adjlist[MAX];//訪問標志 bool visited[MAX];//lowcost[j]存儲從開始節(jié)點到節(jié)點j的最小花費 WeiType lowcost[MAX];//parent[j]表示節(jié)點j的前驅(qū)節(jié)點 int parent[MAX];//建立鄰接表存儲 void createGraph(vexNode *adjlist,const int n,const int e,const int v0){ edgeNode *p1,*p2;int i,v1,v2;WeiType weight;for(i=1;i<=n;i++){ cout<<“請輸入節(jié)點”< visited[i] = false;lowcost[i] = Infinity;parent[i] = v0;} for(i=1;i<=e;i++){ cout<<“請輸入邊”< p1->weight = weight;p1->info = adjlist[v1].info;p1->next = adjlist[v2].link;adjlist[v2].link = p1;p2->no = v2;p2->weight = weight;p2->info = adjlist[v2].info;p2->next = adjlist[v1].link;adjlist[v1].link = p2;}} void f(int n,int e,int v){ int i,j,k;edgeNode *p,*q;WeiType sum = 0,minCost;createGraph(adjlist,n,e,v);p = adjlist[v].link; visited[v] = true;while(p!=NULL){ lowcost[p->no] = p->weight;p = p->next;} for(i=1;i minCost = Infinity; int k; for(j=1;j<=n;j++) { if(minCost>lowcost[j]&&!visited[j]) { minCost = lowcost[j]; k = j; } } sum += minCost; visited[k] = true; q = adjlist[k].link; while(q!= NULL) { if(!visited[q->no]&&q->weight { lowcost[q->no] = q->weight; parent[q->no] = k; } q = q->next;} } cout<<“最小生成樹的邊集為：”< cout<<“(”< } } 7、評語 工作態(tài)度（認真、一般、較差），工作量（飽滿、一般、不夠），每個任務能夠獨立（完成、基本完成、在輔導下完成），程序運行結(jié)果（正確、基本正確、部分正確），實訓報告格式（標準、一般）。創(chuàng)新意識（較強、一般、沒有），運行所學知識解決實際問題的能力（強、一般、較差）。 ? 優(yōu)(100~90)：能夠熟練運用開發(fā)工具，編程解決實際問題，創(chuàng)意新穎，功能實現(xiàn)完善。 ? 良(89~80)：能夠熟練運用開發(fā)工具，編程解決實際問題，有一定創(chuàng)新，功能實現(xiàn)較好。 ? 中(79~70)：能夠較熟練使用開發(fā)工具，編程解決實際問題，獨立完成實訓，功能實現(xiàn)一般。 ? 及格(69~60)：能夠運用開發(fā)工具，在教師輔導下完成實訓，實現(xiàn)部分功能。? 不及格(59~0)：編程解決實際問題的能力差，功能實現(xiàn)較差。 實訓成績?yōu)椋?分 教師簽字： 題目：在火車貨場車皮編解場，2條軌道連接到2條側(cè)軌道，形成2個鐵路轉(zhuǎn)軌棧，其中左邊軌道為車皮入口，編號為A；右邊軌道為出口，編號為D；2個鐵路轉(zhuǎn)軌棧分別編號為C和D如下圖所示。編號為a, b, c, ┅, n的各車皮依序停放在車皮的入口處，調(diào)度室要安排個車皮進出棧次序，使得在出口處各車皮按照預先制定的順序依次出站。車皮移動時只能按照從左到右的方向移動。組織與指導老師： 組長：* 成員：*** 指導教師：* 完成時間、地點： 時間：第16周（6月6日～6月10日） 地點：南校區(qū)東教學樓2樓機房。 一、需求分析 1、問題描述 掌握隊列、棧、樹的結(jié)構以及基本操作，熟悉for循環(huán)語句，if條件語句的嵌套，結(jié)構體函數(shù)等，從而實現(xiàn)程序的功能。 例如： typedef struct Stack { Data *data; Data *end; }Stack; …… 2、實現(xiàn)功能 （1）對于給定的車皮數(shù)n，以及各車皮的出站順序，編程計算最優(yōu)調(diào)度方案，使得移動車皮的次數(shù)最少。 （2）數(shù)據(jù)輸入：由文件input.txt給出數(shù)據(jù)。第一行有1個正整數(shù)n，表示車皮數(shù)；接下來的1行是一個字符串，表示預先確定的車皮的出站順序。 （3）數(shù)據(jù)輸出：將計算得到的最優(yōu)調(diào)度方案輸出到文件output.txt，文件的第一行使最少移動次數(shù)m，接下來的m行使對于最優(yōu)方案的m次移動。每次移動用“cXY”的3個字符表示，其中c表示車皮編號，X表示其時棧號，Y表示目標棧號。如果無法調(diào)度則輸出“No Solution!” 二、概要設計 1、抽象數(shù)據(jù)類型 void ReadData(void) { int i; FILE *fp; fp = fopen(“input.txt”, “r”); if(fp == NULL) exit(__COUNTER__); fscanf(fp, “%d”, &total); if(total < 1) { fclose(fp); exit(__COUNTER__); } ……、void Show(Stack a, char *s) { char *tmp, *pc; char *p =(char*)a.data; pc = tmp =(char*)malloc(total + 1); while(p <= a.end) *pc++ = *p++; *pc = 0; printf(“%s%s”, tmp, s); } …… if(d == end) { if(min > count) { min = count; strcpy(res, tmp); return; } } count++; if(A.end >= A.data) a = *A.end; else a = EOD; …… 2、程序中包含功能模塊及模塊間的調(diào)用關系 各個基本操作都通過公有成員函數(shù)實現(xiàn)，然后通過主程序調(diào)用來實現(xiàn)程序的功能。 例如： void Init(Stack *a, int len) { a->data =(Data*)malloc(len * sizeof(Data)); memset(a->data, 0, len * sizeof(Data)); a->end = a->data-1; } …… void main(void) { ReadData(); Calc(head); End(); } 三、調(diào)試分析 完成情況說明： 編譯程序的過程中發(fā)現(xiàn)了許多漏洞，調(diào)試起來很不方便，經(jīng)過我和同學的共同努力，終于有了突破性的進展，程序按照預定的時間調(diào)試出來了，雖然當中還存在不少的漏洞，但不會影響程序的正常運行。 程序的性能分析：各個操作都是通過公有函數(shù)的調(diào)用來實現(xiàn)的，其中用到結(jié)構體函數(shù)，for循環(huán)，If語句的嵌套等，通過測試可以實現(xiàn)其預定的功能。出現(xiàn)的問題及解決方案： 缺失頭文件導致的定義無效錯誤，通過添加頭文件即可解決問題；定義字符類型錯誤，使用正確的函數(shù)類型定義即可，for循環(huán)的循環(huán)語句語法使用不當，導致函數(shù)無法實現(xiàn)循環(huán)，if條件語句的應用還存在問題，以上所述的編譯錯誤都通過我很同學的認真分析后糾正了。 四、用戶使用說明 了解程序的執(zhí)行過程，輸入合法的數(shù)值是程序正常運行的關鍵，輸入的數(shù)值和開始需要的字符的長度要符合五、心得體會： 通過多次編寫程序，我總結(jié)出來一條心得，程序不能寫完才調(diào)試，而是應該寫一個函數(shù)調(diào)試一個函數(shù)，這樣才能縮小調(diào)試的范圍，提高編程的效率，程序編完后在進行一次綜合調(diào)試，將不完善的函數(shù)和功能處理好，才能將程序做到最好！而且，很多時候，一個大的工程并不是一個人就能完成，這就要求我們有團隊精神。讓我感受最深的是在我調(diào)試程序的時候，一個很細微的錯誤就可能導致程序的出錯，正所謂的“細節(jié)決定成敗”，不管是在學習中，生活中，我們都要有一顆善于發(fā)現(xiàn)問題，解決問題的新，除此之外，還要有樂于助人的精神。 （數(shù)據(jù)結(jié)構實訓報告） 目錄 一、實訓目的...........................................................1 二、實訓題目...........................................................1 三、實訓步驟...........................................................2 四、實訓內(nèi)容...........................................................2 五、實訓心得..........................................................19 六、參考文獻..........................................................19 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 一、實訓目的 通過實訓，對所學數(shù)據(jù)結(jié)構和程序設計的基本知識和基本理論有更進一步的了解和認識，將理論和實際相結(jié)合，能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來。主要是培養(yǎng)學生綜合利用C語言進行程序設計的能力和創(chuàng)新能力以及綜合解決問題的能力。運用算法分析與程序設計的一般方法進行實際項目的開發(fā)。本次實訓盡量選取與實際結(jié)合緊密或?qū)W生比較感興趣的項目，本次實訓學生需要具備熟練的程序設計基礎、數(shù)據(jù)結(jié)構和計算機應用基礎知識，具備程序編寫、調(diào)試的基本能力，具有一定的文字表達和報告撰寫能力，具備辦公軟件使用能力。 通過實訓，考查語言基本概述掌握是否牢固，并考查與后續(xù)課程較為密切的結(jié)構體，鏈表，文件的運用熟練程度，加強對基本概念的理解和復習，最重要的是了解基本軟件的設計步驟，還有對軟件調(diào)試的掌握。能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設計技能。 二、實訓題目 （一）單項題目 1、二叉樹遍歷 【問題描述】建立二叉樹，實現(xiàn)二叉樹的先序遍歷、中序、后序和層序遍歷（用遞歸或非遞歸的方法都可以）。 【要 求】編寫菜單程序。能夠輸入二叉樹的各個結(jié)點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲結(jié)構的輸入函數(shù)、輸出先序遍歷序列的函數(shù)；輸出中序遍歷序列的函數(shù)；輸出后序遍歷序列的函數(shù)；輸出層序遍歷序列的函數(shù)。 （二）綜合題目 1、圖書管理系統(tǒng) 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 【問題描述】建立一個圖書信息文件，包括書號（num）、書名（bookname）、作者（name）、出版社（publish）、價格（price）等。 【要 求】建立一個圖書信息文件，包括書號（num）、書名（bookname）、作者（name）、出版社（publish）、價格（price）等。 三、實訓步驟 1、問題分析 正確理解問題，分析問題究竟“做什么”，分析問題已知的信息及其作用，分析在解決中對信息處理的規(guī)則、要求、限制條件，分析問題解決后應該輸出什么樣的結(jié)果（輸出形式、格式、內(nèi)容）。并分析得出判定結(jié)果是否正確的標準。 2、設計分析 得出解決問題的思路、主要流程、采用的數(shù)據(jù)結(jié)構類型的說明、主要算法的思想。 3、設計方案 采用的數(shù)據(jù)結(jié)構類型的定義、主要算法的描述及說明。 4、詳細設計 根據(jù)問題要求和已得到的算法編寫程序。 5、調(diào)試程序 發(fā)現(xiàn)程序中存在的語法錯誤和一些邏輯錯誤，并修改，使程序能夠運行。 6、運行程序 選擇若干具有代表性的輸入數(shù)據(jù)（包括合理數(shù)據(jù)和不合理數(shù)據(jù)），進行測試，盡量使程序的各語句和分支都被檢查到，以便發(fā)現(xiàn)程序中的錯誤和漏洞，以便改進算法和程序。 7、使用說明 包括程序源代碼、算法（程序）流程圖、開發(fā)過程中各階段的有關記錄、算法的正確性證明、程序的測試結(jié)果、對輸入輸出要求及格式的詳細描述。 四、實訓內(nèi)容 （一）個人題目 1、二叉樹遍歷 【問題描述】建立二叉樹，實現(xiàn)二叉樹的先序遍歷、中序、后序和層序遍歷（用遞歸或非遞歸的方法都可以）。吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 【要 求】編寫菜單程序。能夠輸入二叉樹的各個結(jié)點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲結(jié)構的輸入函數(shù)、輸出先序遍歷序列的函數(shù)；輸出中序遍歷序列的函數(shù)；輸出后序遍歷序列的函數(shù)；輸出層序遍歷序列的函數(shù)。 【設計分析】 1、總體設計(基本概念)樹的概念 樹（Tree）是n（n>=0）個結(jié)點的有限集。在任意一棵非空樹中： 1)有且僅有一個特定的稱為根的結(jié)點； 2)當n>1時，其余結(jié)點可分為m（m>0）個互不相交的有限集T1，T2......Tm，其中每一個集合又是一棵樹，并且稱為根的子樹（SubTree）。 【例】如圖1所示： 圖1 圖1是有8個結(jié)點的樹，其中A是根，其余結(jié)點分成2個互不相交的子集：T1={B，D}，T2={C，E，F(xiàn)，G，H}；T1和T2都是根A的子樹，且本身也是一棵樹。 【設計方案】1．創(chuàng)建二叉樹（可從鍵盤輸入各結(jié)點的值）2．按某種方式對二叉樹進行遍歷 3．樹型結(jié)構是一種非常重要的非線性結(jié)構。樹在客觀世界是廣泛存在的，在計算 機領域里也得到了廣泛的應用。在編譯程序里，也可用樹來表示源程序的語法結(jié)構，在數(shù)據(jù)庫系統(tǒng)中，數(shù)形結(jié)構也是信息的重要組織形式。 4．節(jié)點的有限集合（N大于等于0）。在一棵非空數(shù)里：（1）、有且僅有 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 一個特定的根節(jié)點；（2）、當N大于1時，其余結(jié)點可分為M（M大于0）個互不相交的子集，其中每一個集合又是一棵樹，并且稱為根的子樹。樹的定義是以遞歸形式給出的。 5．二叉樹是另一種樹形結(jié)構。它的特點是每個結(jié)點最多有兩棵子樹，并且，二叉 樹的子樹有左右之分，其次序不能顛倒。 從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點及左、右子樹這三個基本部分組成。因此，在任一給定結(jié)點上，可以按某種次序執(zhí)行三個操作：（1）訪問結(jié)點本身(N)，（2）遍歷該結(jié)點的左子樹(L)，（3）遍歷該結(jié)點的右子樹(R)。以上三種操作有六種執(zhí)行次序： NLR、LNR、LRN、NRL、RNL、RLN。【詳細設計】本程序源代碼如下： /*源程序*/ /* Note:Your choice is C IDE */ #include “stdio.h” #include typedef char DataType;#define MaxStackSize 50 using namespace std; typedef struct Node { DataType data; struct Node *leftChild; struct Node *rightChild; }BiTreeNode;typedef BiTreeNode* DataType2;typedef struct { DataType2 stack[MaxStackSize];吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 int top;} SeqStack;typedef struct { DataType2 quene[MaxStackSize]; int front; int rear;}Quene;void StackInitiate(SeqStack *S) { S->top = 0;} int StackNotEmpty(SeqStack S){ if(S.top <= 0)return 0; else return 1;} int StackPush(SeqStack *S, DataType2 x){ if(S->top >= MaxStackSize) { printf(“堆棧已滿無法插入!n”); return 0; } else { S->stack[S->top] = x; S->top ++; return 1; } } int StackPop(SeqStack *S, DataType2 *d){ if(S->top <= 0) { printf(“堆棧已空無數(shù)據(jù)元素出棧!n”); return 0; } else { S->top--; *d = S->stack[S->top]; return 1;吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 } } int StackTop(SeqStack S, DataType2 *d){ if(S.top <= 0) { printf(“堆棧已空!n”); return 0; } else { *d = S.stack[S.top-1]; return 1; } } typedef struct node{ char data;struct node *lchild;struct node *rchild;}BTNode; typedef BTNode *BTree; int NodeNum,leaf; BTree CreatBTree(void){BTree T;char ch;if((ch=getchar())=='*')return(NULL); else{ T=(BTNode *)malloc(sizeof(BTNode));T->data=ch;T->lchild=CreatBTree();T->rchild=CreatBTree();return(T);} } void Preorder(BTree T)吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 { if(T){ printf(“%c”,T->data); Preorder(T->lchild); Preorder(T->rchild);} } void Inorder(BTree T){ if(T){ Inorder(T->lchild); printf(“%c”,T->data); Inorder(T->rchild);} } void Postorder(BTree T){ if(T){ Postorder(T->lchild); Postorder(T->rchild); printf(“%c”,T->data);} } int TreeDepth(BTree T){ int hl,hr,max;if(T){ hl=TreeDepth(T->lchild); hr=TreeDepth(T->rchild); max=hl>hr?hl:hr; NodeNum=NodeNum+1; if(hl==0&&hr==0) leaf=leaf+1; return(max+1);} 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 else return(0);} void Levelorder(BTree T){ int front=0,rear=1;BTNode *cq[Max],*p;cq[1]=T;while(front!=rear){ front=(front+1)%NodeNum; p=cq[front]; printf(“%c”,p->data); if(p->lchild!=NULL) { rear=(rear+1)%NodeNum; cq[front]=p->lchild; cq[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%NodeNum; cq[front]=p->rchild; cq[rear]=p->rchild; } } } void main(){ BTree root;int i,depth;printf(“n”);printf(“創(chuàng)建二叉樹，請輸入完全二叉樹的先序序列，用*代表虛結(jié)點:”);root=CreatBTree();//返回根結(jié)點 do{ 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 printf(“t1:先序遍歷n”);printf(“t2:中序遍歷n”);printf(“t3:后序遍歷n”);printf(“t4:深度、結(jié)點數(shù)、葉子數(shù)n”);printf(“t5:層次遍歷n”);printf(“備注：選擇層次遍歷之前，需要先選擇4，求出該樹的結(jié)點數(shù)?！?; printf(“t0:Exitn”); scanf(“%d”,&i);//輸入菜單序號 switch(i) { case 1:printf(“先序遍歷結(jié)果為:”); Preorder(root); break; case 2:printf(“中序遍歷結(jié)果為:”); Inorder(root); break; case 3:printf(“后序遍歷結(jié)果為:”); Postorder(root); break; case 4:depth=TreeDepth(root); printf(“深度=%d 結(jié)點數(shù)=%d”,depth,NodeNum); printf(“葉子數(shù)=%d”,leaf); break; case 5:printf(“層次遍歷為:”); Levelorder(root); break; default:exit(1); } printf(“n”);} while(i!=0);} 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 【使用說明】本程序在turboc 2.0環(huán)境下運行，迷宮大小為20×20，需要修改迷宮大小時，可以修改程序中N值的大小。迷宮圖由系統(tǒng)自動隨機生成，每次生成的迷宮圖是不同的。按enter健顯示最終搜索結(jié)果。按Q健退出程序。 【運行調(diào)試】 圖（1）二叉樹遍歷主界面 圖（2） （二）綜合題目 1、圖書管理系統(tǒng) 【問題描述】建立一個圖書信息文件，包括書號（num）、書名（bookname）、作者（name）、出版社（publish）、價格（price）等。 【要 求】編寫菜單程序，功能包括：建立圖書信息、插入記錄，刪除記錄、修改記錄、按照書號或書名查詢記錄、顯示記錄、根據(jù)圖書價格進行排序。定義圖書信息結(jié)構體名稱為book。書號（num）、書名（bookname）、作者（name）、出版社（publish）均為字符型數(shù)組。價格（price）為單精度型數(shù)據(jù)。 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 【設計分析】系統(tǒng)目標分析 每個學校都有圖書館，最初由于圖書數(shù)量和種類較少，人工手動管理比較方便和靈活。隨著社會的發(fā)展，圖書的數(shù)量和種類越來越多，人工手動管理會降低工作的效率，希望建立一個圖書館圖書信息管理系統(tǒng)，是為了解決了人工手動管理圖書信息在實踐的問題，從而達到系統(tǒng)化、規(guī)范化、標準化的水平。該系統(tǒng)的建立不但給管理者帶來了方便，也節(jié)省了工作時間從而提高了工作效率。 在構造系統(tǒng)時，首先從需求出發(fā)構造數(shù)據(jù)庫表，然后再由數(shù)據(jù)庫表結(jié)合需求劃分系統(tǒng)功能模塊。這樣，就把一個大的系統(tǒng)分解成了幾個小系統(tǒng)。這里把系統(tǒng)的層次劃分為了三個部分：一個自由態(tài)：即面向任何用戶的界面，提供登錄功能，以便不同身份的用戶登錄子系統(tǒng)；一個是一般用戶態(tài)：即圖書有服務子系統(tǒng)；還有一個是管理員界面：提供圖書的管理和維護功能。對于不同子系統(tǒng)之間的功換，采用了登錄功能和用戶注銷功能。系統(tǒng)劃分了子系統(tǒng)后，下一步的工作是繼續(xù)劃分子系統(tǒng)的小模塊。先考慮在進入子系統(tǒng)時應該做什么，進入系統(tǒng)之后又應該做什么，提供那些服務等。例如，對于圖書信息服務子系統(tǒng)，在用戶進入時首先得調(diào)用相關數(shù)據(jù)庫表，找出用戶的圖書借閱情況；進入系統(tǒng)后，子系統(tǒng)得提供圖書查詢、圖書借閱和還書功能。另外，針對本系統(tǒng)的特殊情況，同時也考慮系統(tǒng)的可移植性，在系統(tǒng)中增加了數(shù)據(jù)庫路徑的維護部分。最后，考慮到系統(tǒng)的安全性，還在系統(tǒng)中特別增加了“加密界面”的功能。 【設計方案】本數(shù)據(jù)庫管理系統(tǒng)主要由圖書檢索、圖書管理、數(shù)據(jù)維護、圖書統(tǒng)計、打印輸出、系統(tǒng)維護六大模塊組成, 如圖1 所示。各模塊功能如下： 1、主控模塊主控模塊的功能是控制各個分支模塊,它是實現(xiàn)各模塊功能的總控制臺 2、圖書檢索模塊是圖書管理系統(tǒng)的重要模塊之一,是讀者快速查詢圖書的途徑 本模塊的功能是按書名、書號、作者、出版社、圖書分類查詢 數(shù)據(jù)維護模塊是由圖書管理員控制的模塊,它由增加、修改和刪除讀者,增加、修改刪除圖書,瀏覽修改讀者、瀏覽修改圖書等程序組成。在軟件設計時考慮到讀者編號、書名、書號是唯一的,因此,在修改讀者或圖書中,讀者記錄或圖書記錄一經(jīng)登記“讀者編號”和“姓名”便不能修改,在刪除讀者或圖書時只要讀者有借出圖書未還或庫存圖書原有數(shù)量與現(xiàn)有庫存量不符便不能刪除。 5、數(shù)據(jù)統(tǒng)計模塊由讀者統(tǒng)計、圖書統(tǒng)計、借出圖書分類統(tǒng)計、到期未歸還圖書讀者統(tǒng)計幾部分組成 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 我們小組的信息系統(tǒng)開發(fā)課程設計題目是：圖書管理系統(tǒng)開發(fā)。系統(tǒng)開發(fā)的總的設計目標是實現(xiàn)圖書管理的系統(tǒng)化、規(guī)范化和自動化，實現(xiàn)對圖書資料的集中統(tǒng)一的管理。 本系統(tǒng)主要實現(xiàn)對圖書館信息的管理，主要功能為管理有關讀者，書籍，借閱和管理者的信息等。本系統(tǒng)結(jié)構分為讀者信息管理模塊，書籍信息管理模塊，借閱信息管理模塊，管理者信息管理模塊。讀者信息管理部分有兩方面的功能，可以瀏覽讀者的信息，可以對讀者信息進行維護。書籍信息管理可以瀏覽書籍的信息，可以對書籍信息進行維護。借閱信息管理可以顯示當前數(shù)據(jù)庫中書籍借閱情況，可以對借閱信息進行維護。管理者信息管理可以顯示數(shù)據(jù)庫中管理者的情況，可以對管理者信息進行維護。可見，本系統(tǒng)并不復雜，主要解決的問題是利用關鍵字對數(shù)據(jù)庫進行查詢。 【詳細設計】本程序源代碼如下： /*源程序*/ /* Note:Your choice is C IDE */ /* Note:Your choice is C IDE */ #include struct books_list { char author[20]; /*作者名*/ char bookname[20]; /*書名*/ char publisher[20]; /*出版單位*/ char pbtime[15]; /*出版時間*/ char loginnum[10]; /*登陸號*/ float price; /*價格*/ char classfy[10]; /*分類號*/ struct books_list * next;/*鏈表的指針域*/ };吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 struct books_list * Create_Books_Doc(); /*新建鏈表*/ void InsertDoc(struct books_list * head);/*插入*/ void DeleteDoc(struct books_list * head , int num);/*刪除*/ void Print_Book_Doc(struct books_list * head);/*瀏覽*/ void search_book(struct books_list * head);/*查詢*/ void info_change(struct books_list * head);/*修改*/ void save(struct books_list * head);/*保存數(shù)據(jù)至文件*/ /*瀏覽操作*/ void Print_Book_Doc(struct books_list * head){ struct books_list * p;if(head==NULL || head->next==NULL)/*判斷數(shù)據(jù)庫是否為空*/ { printf(“n ━━━━ 沒有圖書記錄!━━━━nn”); return;} p=head;printf(“┏━━━┳━━━┳━━━┳━━━┳━━━━┳━━━┳━━━┓n”);printf(“┃登錄號┃書名 ┃ 作者 ┃出版單位┃出版時間┃分類號┃價格┃n”); printf(“┣━━━╋━━━╋━━━╋━━━╋━━━━╋━━━╋━━━┫n”);/*指針從頭節(jié)點開始移動，遍歷至尾結(jié)點，依次輸出圖書信息*/ while(p->next!= NULL){ p=p->next; printf(“┃%-6.6s┃%-10.10s┃%-10.10s┃%-10.10s┃%-12.12s┃%-6.6s┃%.2f ┃n”,p->loginnum,p->bookname,p->author,p->publisher,p->pbtime,p->classfy,p->price);/*循環(huán)輸出表格*/ } printf(“┗━━━┻━━━┻━━━┻━━━┻━━━━┻━━━┻━━━┛n”);printf(“n”);吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 } /*刪除操作*/ void DeleteDoc(struct books_list * head){ struct books_list *s,*p; /*s為中間變量，p為遍歷時使用的指針*/ char temp[20];int panduan;/*此變量用于判斷是否找到了書目*/ panduan=0;p=s=head;printf(“ [請輸入您要刪除的書名]:”);scanf(“%s”,temp);/*遍歷到尾結(jié)點*/ while(p!= NULL) { if(strcmp(p->bookname,temp)==0) { panduan++; break; } p=p->next;} if(panduan==1){ for(;s->next!=p;) /*找到所需刪除卡號結(jié)點的上一個結(jié)點*/ { s=s->next; } s->next=p->next;/*將后一節(jié)點地址賦值給前一節(jié)點的指針域*/ free(p); printf(“n ━━━━ 刪除成功!━━━━n”);} else /*未找到相應書目*/ 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 { printf(“ 您輸入的書目不存在，請確認后輸入!n”);} return;} int main(void){ struct books_list * head; char choice;head=NULL;for(;;)/*實現(xiàn)反復輸入選擇*/ { printf(“ ┏━━━━━━━━━━━━━━━━━━━┏━┓n”); printf(“ ┃ ┃ socat 圖書管理系統(tǒng) ┃ ┃n”); printf(“ ┃ ┗━━━━━━━━━━━━━━━━━━━┛ ┃n”); printf(“ ┃ ●[1]圖書信息錄入 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[2]圖書信息瀏覽 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[3]圖書信息查詢 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[4]圖書信息修改 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[5]圖書信息刪除 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[6]退出系統(tǒng) ┃n”); printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━┛ 15 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 n”); printf(“ 請選擇:”); fflush(stdin); scanf(“%c”,&choice); if(choice=='1') { if(head==NULL) { head=Create_Books_Doc(); } InsertDoc(head); } else if(choice=='2') { Print_Book_Doc(head); } else if(choice=='3') { search_book(head); } else if(choice=='4') { info_change(head); } else if(choice=='5') { struct books_list *s,*p; /*s為中間變量，p為遍歷時使用的指針*/ char temp[20];int panduan;/*此變量用于判斷是否找到了書目*/ panduan=0;p=s=head;printf(“ [請輸入您要刪除的書名]:”);吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 scanf(“%s”,temp);/*遍歷到尾結(jié)點*/ while(p!= NULL) { if(strcmp(p->bookname,temp)==0) { panduan++; break; } p=p->next;} if(panduan==1){ for(;s->next!=p;) /*找到所需刪除卡號結(jié)點的上一個結(jié)點*/ { s=s->next; } s->next=p->next;/*將后一節(jié)點地址賦值給前一節(jié)點的指針域*/ free(p); printf(“n ━━━━ 刪除成功!━━━━n”);} else /*未找到相應書目*/ { printf(“ 您輸入的書目不存在，請確認后輸入!n”);} return; } else if(choice=='6') { printf(“n”); printf(“ ━━━━━━━━ 感謝使用圖書管理系統(tǒng) ━━━━━━━━n”);吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 break; } else { printf(“ ━━━━ 輸入錯誤，請重新輸入！━━━━”); break; } } } 【使用說明】本程序在turboc 2.0環(huán)境下運行，迷宮大小為20×20，需要修改迷宮大小時，可以修改程序中N值的大小。迷宮圖由系統(tǒng)自動隨機生成，每次生成的迷宮圖是不同的。按enter健顯示最終搜索結(jié)果。按Q健退出程序。 【運行調(diào)試】 圖（3）圖書管理系統(tǒng)主界面 吉林工業(yè)職業(yè)技術學院 數(shù)據(jù)結(jié)構實訓 圖（4）圖書信息瀏覽 五、實訓心得 六、參考文獻 實驗一 線性表 1.實驗要求 1.1 掌握數(shù)據(jù)結(jié)構中線性表的基本概念。 1.2 熟練掌握線性表的基本操作：創(chuàng)建、插入、刪除、查找、輸出、求長度及合并并運算在順序存儲結(jié)構上的實驗。1.3 熟練掌握鏈表的各種操作和應用。2.實驗內(nèi)容 2.1 編寫一個函數(shù)，從一個給定的順序表A中刪除元素值在x到y(tǒng)之間的所有元素，要求以較高效率來實現(xiàn)。 2.2 試寫一個算法，在無頭結(jié)點的動態(tài)單鏈表上實現(xiàn)線性表插入操作 2.3 設計一個統(tǒng)計選票的算法，輸出每個候選人的得票結(jié)果。 3.實驗代碼 2.1代碼： #include A[i-k]=A[i];i++;} return(n-k);} void main(){ int i,j;int a[maxsize];printf(“輸入%d個數(shù):n”,maxsize);for(i=0;i scanf(“%d,”,&a[i]); 數(shù)據(jù)結(jié)構實驗報告 j=del(a,maxsize,1,3); printf(“輸出刪除后剩下的數(shù):n”); for(i=0;i ”n,a[i]);} 2.2代碼： INSERT(L,i,b)。 void Insert(Linklist &L,int i,elemtype x){ if(!L){ L=(Linklist)malloc(sizeof(Lnode)); (*L).data=x;(*L).next=NULL;} else { if(i==1) { s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=L;L=s; } else { p=L;j=1; while(p&&j {j++;p=p->next;} if(p||j>i-1) return error; s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=p->next;p->next=s; } } } 2.3代碼： typedef int elemtype typedef struct linknode { elemtype data;struct linknode *next;}nodetype; 數(shù)據(jù)結(jié)構實驗報告 nodetype *create(){ elemtype d;nodetype h=NULL,*s,*t;int i=1;printf(“建立單鏈表:n”);while(1){ printf(“輸入第%d個結(jié)點數(shù)據(jù)域”,i); scanf(“%d”,&d); if(d==0)break; if(i==1) { h=(nodetype *)malloc(sizeof(nodetype)); h->data=d;h->next=NULL;t=h; } else { s=(nodetype *)malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s; } i++;} return h;} void sat(nodetype *h,int a[]){ nodetype *p=h;while(p!=NULL){ a[p->data]++; p=p->next;} } void main(){ int a[N+1],i;for(i=0;i a[i]=0;nodetype *head;head=create();sat(head,a); 數(shù)據(jù)結(jié)構實驗報告 } printf(“候選人:”);for(i=1;i<=N;i++)printf(“%3d”,i);printf(“n得票數(shù)n”);for(i=1;i<=N;i++)printf(“%3d”,a[i]);printf(“n”);4.實驗小結(jié) 線性表是最簡單的、最常用的一種數(shù)據(jù)結(jié)構，是實現(xiàn)其他數(shù)據(jù)結(jié)構的基礎。 實驗二 棧與隊列 1.實驗要求 1.1 了解棧和隊列的特性，以便靈活運用。1.2 熟練掌握棧和有關隊列的各種操作和應用。 2.實驗內(nèi)容 2.1 設一個算術表達式包括圓括號，方括號和花括號三種括號，編寫一個算法判斷其中的括號是否匹配。 3.實驗代碼 2.1代碼： #include 數(shù)據(jù)結(jié)構實驗報告 gets(str);deal(str);printf(“正確!”);getchar();return 0;} void deal(char *str){ list *L;L=(list *)malloc(sizeof(list));if(!L){ printf(“錯誤!”);exit(-2);} L->next=NULL;while(*str){ if(*str=='('||*str=='['||*str=='{') push(*str,L);else if(*str==')'||*str==']'||*str=='}') if(pop(*str,L)) {puts(“錯誤,請檢查!”); puts(“按回車鍵退出”); getchar();exit(-2); } str++;} if(L->next){ puts(“錯誤,請檢查!”);puts(“按任意鍵退出”);getchar();exit(-2);} } void push(char c,list *L){ list *p;p=(list *)malloc(sizeof(list));if(!p){ printf(“錯誤!”);exit(-2); 數(shù)據(jù)結(jié)構實驗報告 } p->str=c;p->next=L->next;L->next=p;} #define check(s)if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);} int pop(char c,list *L){ list *p;if(L->next==NULL)return 1;switch(c){ case')':check('(')break;case']':check('[')break;case'}':check('{')break;} return 1; 4.實驗小結(jié) 棧和隊列是最基礎的一種數(shù)據(jù)結(jié)構之一，為實現(xiàn)其他數(shù)據(jù)結(jié)構的奠定基石。 實驗三 樹 1.實驗要求 1.1 掌握二叉樹，二叉樹排序數(shù)的概念和存儲方法。1.2 掌握二叉樹的遍歷算法。 1.3 熟練掌握編寫實現(xiàn)樹的各種運算的算法。 2.實驗內(nèi)容 2.1 編寫程序，求二叉樹的結(jié)點數(shù)和葉子數(shù)。 2.2 編寫遞歸算法，求二叉樹中以元素值為X的結(jié)點為根的子數(shù)的深度。2.3 編寫程序，實現(xiàn)二叉樹的先序，中序，后序遍歷，并求其深度。 數(shù)據(jù)結(jié)構實驗報告 3.實驗代碼 2.1代碼： #include bt=(struct node *)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat();} return bt;} int n=0,n1=0;void preorder(blink bt){ if(bt){ n++; if(bt->lchild==NULL&&bt->rchild==NULL) n1++; preorder(bt->lchild); preorder(bt->rchild);} } void main(){ blink root;root=creat();preorder(root);printf(“此二叉數(shù)的接點數(shù)有:%dn”,n);printf(“此二叉數(shù)的葉子數(shù)有:%dn”,n1);} 數(shù)據(jù)結(jié)構實驗報告 2.2代碼： int get_deep(bitree T,int x){ if(T->data==x){ printf(“%dn”,get_deep(T));exit 1;} else { if(T->lchild)get_deep(T->lchild,x);if(T->rchild)get_deep(T->rchild,x);} int get_depth(bitree T){ if(!T)return 0;else { m=get_depth(T->lchild);n=get_depth(T->rchild);return(m>n?m:n)+1;} } 2.3代碼： #include 數(shù)據(jù)結(jié)構實驗報告 bt->lchild=creat();bt->rchild=creat();} return bt;} void preorder(blink bt){ if(bt){ printf(“%c”,bt->data);preorder(bt->lchild);preorder(bt->rchild);} } void inorder(blink bt){ if(bt){ inorder(bt->lchild);printf(“%c”,bt->data);inorder(bt->rchild);} } void postorder(blink bt){ if(bt){ postorder(bt->lchild);postorder(bt->rchild);printf(“%c”,bt->data);} } int max(int x,int y){ if(x>y)return x;else return y;} int depth(blink bt){ if(bt)return 1+max(depth(bt->lchild),depth(bt->rchild));else 數(shù)據(jù)結(jié)構實驗報告 } { return 0;void main()blink root; root=creat();printf(“n”);printf(“按先序排列:”); preorder(root);printf(“n”); printf(“按中序排列:”);inorder(root);printf(“n”);printf(“按后序排列:”); postorder(root);printf(“n”); } printf(“此二叉數(shù)的深度是:”);printf(“depth=%dn”,depth(root));4.實驗小結(jié) 通過本章學習實驗，對樹有了初步的認識。樹就是一種非線性的數(shù)據(jù)結(jié)構，描述了客觀世界中事物之間的層次關系。這種結(jié)構有著廣泛的應用，一切具有層次關系的問題都可以用樹來表示。 實驗四 圖 1.實驗要求 1.1 熟悉圖的各種存儲方法。 1.2 掌握遍歷圖的遞歸和非遞歸的算法。1.3 理解圖的有關算法。 2.實驗內(nèi)容 2.1 寫出將一個無向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。 數(shù)據(jù)結(jié)構實驗報告 2.2 以鄰接表作存儲結(jié)構，給出拓撲排序算法的實現(xiàn)。 3.實驗代碼 2.1代碼： void mattolist(int a[][],adjlist b[],int n)/*n為圖的結(jié)點個數(shù)*/ { for(i=0;i /*鄰接表置空*/ for(i=0;i /*逐行進行*/ } 2.2代碼： typedef struct vexnode { VertexType vertex;int in;/*增加一個入度域*/ ArecNodeTp * fristarc;for(j=n-1;j>=0;j--) if(a[i][j]!=0){p=(arcnodetp *)malloc(sizeof(arcnodetp));/*產(chǎn)生鄰接點*/ p->adjvex=j; p->nextare=b[i].firstare;b[i].firstarc=p;} }AdjList[vnum];typedef struct graph { AdjList adjlist;int vexnum,arcnum;}GraphTp;Top_Sort(GraphTp g) 數(shù)據(jù)結(jié)構實驗報告 { LstackTp *p;/*建立入度為0的頂點棧S*/ int m,i,v; initStack(S); } for(i=0;i } if(m 通過本章學習實驗，對圖有了具體的認識。圖也是一種非線性的數(shù)據(jù)結(jié)構，這種結(jié)構有著廣泛的應用，一切具有關系的問題都可以用圖來表示。 數(shù)據(jù)結(jié)構實驗報告 實驗五 查找 1.實驗要求 1.1 掌握順序查找、二分法查找、分塊查找和哈希表查找的算法。1.2 能運用線性表的查找方法解決實際問題。2.實驗內(nèi)容 2.1 編寫一個算法，利用二分查找算法在一個有序表中插入一個元素X，并保持表的有序性。 2.2 根據(jù)給定的數(shù)據(jù)表，先建立索引表，然后進行分塊查找。3.實驗代碼 2.1代碼： #include int data[MAXNUM],m;int insert=1;m=input(data);printf(“Input the insert num:”);scanf(“%d”,data);insert=search(data,1,m);/*返回插入位置*/ plug(data,insert,m);for(insert=1;insert<=m+1;insert++)/*顯示數(shù)據(jù)*/ printf(“%3d”,*(data+insert)); 數(shù)據(jù)結(jié)構實驗報告 getch();} int input(int *data){ int i,m; printf(“nInput the max num:”);scanf(“%d”,&m);printf(“input datan”);for(i=1;i<=m;i++)scanf(“%d”,data+i);return m;} int search(int *data,int low,int high)/*遞歸查找插入位置*/ { int mid;if(low>high)return low;/*沒有找到插入數(shù)據(jù)，返回low*/ else{ } search(data,low,high);} void plug(int *data,int insert,int m) { int i;for(i=m;i>insert;i--)*(data+i+1)=*(data+i);mid=(low+high)/2;if(*(data+mid)==*data)retun mid;/*找到插入數(shù)據(jù)，返回mid*/ else if(*(data+mid)<*data)else if(*()data+mid)>*data)*(data+insert)=*data 數(shù)據(jù)結(jié)構實驗報告 } 2.2代碼： #include /*元素個數(shù)*/ #definr Blocknum 3 /*分塊數(shù)*/ typedef struct indexterm { int key;/*最大關鍵字*/ int addr;/*塊的起始地址*/ }index;/*索引表數(shù)據(jù)類型*/ index * CreateList(int data[],int n)/*建索引表*/ { index *p;int m,j,k;m=n/BlockNum;/*分為BlockNum塊，每塊有m個元素*/ p=(index *)malloc(BlockNum *sizeof(index));for(k=0;k } return p;} int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分塊查找*/ { int low=0,high=m-1,mid,i;(p+k)->key=dat a[m*k];(p+k)->addr=m*k;for(j=m*k;j 數(shù)據(jù)結(jié)構實驗報告 int b=n/m;/*每塊有b個元素*/ while(low<=high){/*塊間折半查找*/ } if(low } return-1;} void main(){ int record[N]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};int key;index *list;printf(“please input key:n”);scanf(“%d”,&key);list=CreateList(record,N);printf(“data postion id %dn”,BlockSearch(list,record,N,BlockNum,key));} if(i<=(list+low)->addr+b-1)return i;mid=(low+high)/2;if((list+mid)->key>=k)high=mid+1;else low=mid+1;else return-1;4.實驗小結(jié) 通過本章的學習，對排序有較高層次的理解與認識，從平時的練習中可以看出排序是數(shù)據(jù)處理中經(jīng)常用到的重要運算。有序的順序表可以采用查找效率較高的折半查找法，而無序的順序表只能用效率較低的順序查找法。 這次課程設計的心得體會通過實習我的收獲如下 1、鞏固和加深了對數(shù)據(jù)結(jié)構的理解，提高綜合運用本課程所學知識的能力。 2、培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。 3、通過實際編譯系統(tǒng)的分析設計、編程調(diào)試，掌握應用軟件的分析方法和工程設計方法。 4、通過課程設計，培養(yǎng)了我嚴肅認真的工作作風，逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。從剛開始得覺得很難，到最后把這個做出來，付出了很多，也得到了很多，以前總以為自己對編程的地方還不行，現(xiàn)在，才發(fā)現(xiàn)只要認真做，沒有什么不可能。編程時要認真仔細，出現(xiàn)錯誤要及時找出并改正，（其中對英語的要求也體現(xiàn)出來了，因為它說明錯誤的時候都是英語）遇到問題要去查相關的資料。反復的調(diào)試程序，最好是多找?guī)讉€同學來對你的程序進行調(diào)試并聽其對你的程序的建議，在他們不知道程序怎么寫的時候完全以一個用戶的身份來用對你的用戶界面做一些建議，正所謂當局者迷旁觀者清，把各個注意的問題要想到；同時要形成自己的編寫程序與調(diào)試程序的風格，從每個細節(jié)出發(fā)，不放過每個知識點，注意與理論的聯(lián)系和理論與實踐的差別。另外，要注意符號的使用，注意對字符處理，特別是對指針的使用很容易出錯且調(diào)試過程是不會報錯的，那么我們要始終注意指針的初始化不管它怎么用以免不必要麻煩。通過近兩周的學習與實踐，體驗了一下離開課堂的學習，也可以理解為一次實踐與理論的很好的連接。特別是本組所做的題目都是課堂上所講的例子，在實行之的過程中并不是那么容易事讓人有一種紙上談兵的體會，正所謂紙上得來終覺淺絕知此事要躬行。實訓過程中讓我們對懂得的知識做了進一步深入了解，讓我們的理解與記憶更深刻，對不懂的知識與不清楚的東西也做了一定的了解，也形成了一定的個人做事風格。 通過這次課程設計，讓我對一個程序的數(shù)據(jù)結(jié)構有更全面更進一步的認識，根據(jù)不同的需求，采用不同的數(shù)據(jù)存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數(shù)組，只要運用得當，也能達到相同的效果，甚至更佳，就如這次的課程設計，通過用for的多重循環(huán)，舍棄多余的循環(huán)，提高了程序的運行效率。在編寫這個程序的過程中，我復習了之前學的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應用范圍，程序結(jié)構算法等一系列的問題它使我對數(shù)據(jù)結(jié)構改變了看法。在這次設計過程中，體現(xiàn)出自己單獨設計模具的能力以及綜合運用知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，也從中發(fā)現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。篇二：數(shù)據(jù)結(jié)構試驗心得 數(shù)據(jù)結(jié)構課程設計心得體會（專業(yè)：計算機科學與技術 姓名：朱文 學號：2011220137） 通訊錄管理系統(tǒng)是基于雙向循環(huán)鏈表設計而成的信息管理系統(tǒng)。該系統(tǒng)通過對程序進行模塊化，建立添加、顯示、查找和刪除功能的函數(shù)，各函數(shù)中運用雙向循環(huán)鏈表存儲數(shù)據(jù)。為存儲通訊錄信息，需定義一個結(jié)構體類型，成員包括姓名、街道、城市、郵編、國家等，并建立雙向循環(huán)鏈表，定義該結(jié)構體類型的指針，用于指向各結(jié)點。分別建立具有添加、刪除、修改、查詢等功能的子函數(shù)，完成相應功能，對程序?qū)崿F(xiàn)模塊化。這其中要用到對鏈表的刪除、插入等知識。為實現(xiàn)存儲功能，需用到文件的相關函數(shù) 開發(fā)一個通訊錄管理系統(tǒng)，借助計算機可以方便、快捷、靈活的管理個人的朋友及相關人員的通訊信息，了解友人相關信息，幫助與友人保持聯(lián)絡。所以設計一個通訊錄管理系統(tǒng)管理各人的通訊信息是非常必要的，同時，通過用循環(huán)雙向鏈表設計通訊錄管理系統(tǒng)可以讓我們更好的去理解循環(huán)雙向鏈表，更好的學好數(shù)據(jù)結(jié)構這門課程。本次實驗中，我們使用分工合作的方式，首先定義了函數(shù)的結(jié)構體部分，剩下的根據(jù)函數(shù)所要實現(xiàn)的功能進行分工合作，我實現(xiàn)的是通訊錄中刪除功能的子函數(shù)，刪除信息（void delete(dnode *head)）的功能是按照用戶輸入的姓名首先進行按姓名查詢功能，查找成功，則執(zhí)行刪除信息的功能，查詢不成功，則提示錯誤信息。定義結(jié)點p，輸入要刪除的信息的姓名，按姓名查找結(jié)點，如果找到匹配的結(jié)點p，就進行相關的刪除操作，否則就是沒找到要刪除的數(shù)據(jù)，最后返回到主函數(shù)。 這次實驗中我深刻認識到合作的重要性。例如：我所編寫的按名刪除功能的實現(xiàn)中，應用了章林霞同學所編寫寫的按名搜索查詢功能的那部分函數(shù)，在這次實驗中，我學到很多東西，加強了我的動手能力，并且培養(yǎng)了我的獨立思考能力。我們堅持理論聯(lián)系實際的思想，以實踐證實理論，從實踐中加深對理論知識的理解和掌握。實驗是我們快速認識和掌握理論知識的一條重要途徑。通過這次課程設計，我們對c語言以及數(shù)據(jù)結(jié)構有了更深刻的了解，增強了程序的編寫能力，鞏固了專業(yè)知識，對程序的模塊化觀念也又模糊逐漸變的清晰了。在程序的運行與調(diào)試過程中出現(xiàn)了很多錯誤，通過反復地復習課本上的相關知識，不停地修改與調(diào)試，我們終于完成了這段程序。在調(diào)試過程中，我們認識到了數(shù)據(jù)結(jié)構的靈活性與嚴謹性，同一個功能可以由不同的語句來實現(xiàn)，但編寫程序時要特別注意細節(jié)方面的問題，因為一個小小的疏忽就能導致整個程序不能運行。我們也認識到了自己的薄弱之處，如對鏈表相關知識的欠缺，文件運用的不熟練，在以后的學習中我們要集中精力、端正態(tài)度，爭取把知識學得更扎實、更全面。 經(jīng)過這次的實驗，我們整體對各個方面都得到了不少的提高，希望以后學校和系里能夠開設更多類似的實驗，能夠讓我們得到更好的鍛煉。也讓我們深深感受到討論交流很重要，遇到困難時，大家一起討論，加強我們的團隊合作精神，同時通過這次的課程設計，我們對 數(shù)據(jù)結(jié)構中雙向鏈表結(jié)構有了更深刻的理解。篇三：數(shù)據(jù)結(jié)構綜合實驗心得體會 心得體會： 做了一個星期的程序設計終于做完了，在這次程序設計課中，真是讓我獲益匪淺。對大一學習的c語言和這學期開的數(shù)據(jù)結(jié)構，并沒有掌握，很多知識都不太懂，突然讓自己獨立完成一個程序讓我手忙腳亂，起碼在我認為那真的特別難，看了老師給的題目以及上網(wǎng)查找了一些相關的知識，簡單的編了幾行就告一段落了，第一天等于只完成了老師要求寫的需求分析和概要設計，后來查找了關于哈希表的相關知識，了解了如何創(chuàng)建哈希表，如何合適的構建哈希函數(shù)，（選取合適的表長，合適的余數(shù)，使得查找時間以及平均查找長度最短）以及什么是除留余數(shù)法，和怎樣用除留余數(shù)法創(chuàng)建哈希表，看懂了之后，我又看了處理沖突的方法，有三種線性探測再散列法法，二次探測再散列法，偽隨機數(shù)序列法三種，而我所要做的是第一種線性探測再散列的方法，相較后兩種要簡單很多，在遇到?jīng)_突的時候地址加一，知道沖突解決。 在了解這些概念以后，我就開始著手編程序了，在遇到問題的時候請教我們班擅長的同學，慢慢把不能不會不理解的地方給弄明白了，在經(jīng)過很多次調(diào)試以后，一些基本功能已經(jīng)可以實現(xiàn)了，為了使平均查找長度越小越好，我不斷嘗試新的表長以及除數(shù)，在沒有出現(xiàn)錯誤的基礎上，將功能實現(xiàn)，最后，終于在周四的時候?qū)⑺械某绦蛘{(diào)試完全。這次的綜合性實驗使我了解到，平時對知識的積累相當重要，同時也要注重課上老師的講解，老師在課上的延伸是課本上所沒有的，這些知識對于我們對程序的編寫有很大的作用，同時，編程也要求我們有足夠的耐心，細細推敲。越著急可能就越無法得到我們想要的結(jié)果，遇到不會的問題要多多請教，知識是在實踐與向別人請教的過程中積累的，所以問是至關重要的，只要肯下功夫很多東西都是可以完成的。篇四：數(shù)據(jù)結(jié)構實驗報告及心得體會 2011~2012第一學期數(shù)據(jù)結(jié)構實驗報告 班級：信管一班 學號：201051018 姓名：史孟晨 實驗報告題目及要求 一、實驗題目 設某班級有m（6）名學生，本學期共開設n（3）門課程，要求實現(xiàn)并修改如下程 序（算法）。 1.輸入學生的學號、姓名和 n 門課程的成績（輸入提示和輸出顯示使用漢字系統(tǒng)），輸出實驗結(jié)果。（15分） 2.計算每個學生本學期 n 門課程的總分，輸出總分和n門課程成績排在前 3 名學 生的學號、姓名和成績。 3.按學生總分和 n 門課程成績關鍵字升序排列名次，總分相同者同名次。 二、實驗要求 1．修改算法。將奇偶排序算法升序改為降序。（15分）2．用選擇排序、冒泡排序、插入排序分別替換奇偶排序算法,并將升序算法修改為 降序算法。（45分））3．編譯、鏈接以上算法，按要求寫出實驗報告（25）。4.修改后算法的所有語句必須加下劃線，沒做修改語句保持按原樣不動。5．用a4紙打印輸出實驗報告。 三、實驗報告說明 實驗數(shù)據(jù)可自定義，每種排序算法數(shù)據(jù)要求均不重復。(1)實驗題目：《n門課程學生成績名次排序算法實現(xiàn)》；(2)實驗目的：掌握各種排序算法的基本思想、實驗方法和驗證算法的準確性；(3)實驗要求：對算法進行上機編譯、鏈接、運行；(4)實驗環(huán)境（windows xp-sp3,visual c++)；(5)實驗算法（給出四種排序算法修改后的全部清單）；(6)實驗結(jié)果（四種排序算法模擬運行后的實驗結(jié)果）；(7)實驗體會（文字說明本實驗成功或不足之處）。 三、實驗源程序（算法）score.c #include stdio.h #include string.h #define m 6 #define n 3 struct student { char name[10];int number;int score[n+1]; /*score[n]為總分,score[0]-score[2]為學科成績*/ }stu[m];void changesort(struct student a[],int n,int j){int flag=1,i;struct student temp;while(flag){ flag=0;for(i=1;i /*對所有奇數(shù)項進行一遍比較*/ if(a[i].score[j]>a[i+1].score[j]) { temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;} for(i=0;i a[i]=a[i+1]; a[i+1]=temp;flag=1;} } } void print_score(struct student a[],int n,int j){ int i,k;printf(“ 奇偶交換 成績 %d 排序表,j+1);printf(n);printf(名 次 學 號 姓 名 分 數(shù)n);k=1;for(i=0;k printf(%4d,a[i].number);printf（%s,a[i].name); printf(%6d,a[i].score[j]);printf(n);} } main(){ int i,j,k;for(i=0;i 名:);scanf(%s,stu[i].name);printf(編 號:);scanf(%4d,&stu[i].number);printf(數(shù)據(jù)結(jié)構:);scanf(%4d,&stu[i].score[0]);printf(離散數(shù)學:);scanf(%4d,&stu[i].score[1]);printf(大學英語:);scanf(%4d,&stu[i].score[2]);} for(i=0;i { stu[i].score[n]=0;for(j=0;j 山東科技大學泰山科技學院 課程實訓說明書 課程： 數(shù)據(jù)結(jié)構項目實訓 題目： 院 系： 信息工程系 2014年 5月 25日 專業(yè)班級： 學 號： 學生姓名： 指導教師： 目 錄 一、設計題目..........................................................3 1.1 順序表操作.........................................................3 1.2 鏈表操作..........................................................3 1.3 二叉樹的基本操作..................................................3 二、運行環(huán)境（軟、硬件環(huán)境）.......................................3 2.1 軟件環(huán)境..........................................................3 2.2 硬件環(huán)境..........................................................3 三、數(shù)據(jù)結(jié)構及算法設計的思想.......................................3 3.1 順序表設計構思.....................................................3 3.2 鏈表設計構思......................................................4 3.3 二叉樹設計構思....................................................4 四、源代碼............................................................5 5.1 順序表源代碼......................................................5 5.2 鏈表源代碼........................................................6 5.3 二叉樹源代碼......................................................8 五、運行結(jié)果分析.....................................................11 6.1 順序表運行結(jié)果...................................................11 6.2 鏈表運行結(jié)果.....................................................13 6.3 二叉樹運行結(jié)果...................................................15 七、實習總結(jié)........................................................18 一、設計題目 1.1鏈表操作 1.1.1 設計目的 ? 掌握線性表的在順序結(jié)構和鏈式結(jié)構實現(xiàn)。? 掌握線性表在順序結(jié)構和鏈式結(jié)構上的基本操作。1.1.2 設計內(nèi)容和要求 利用順序表鏈表的插入運算建立線性鏈表，然后實現(xiàn)鏈表的查找、插入、刪除、計數(shù)、輸出、排序、逆置等運算（查找、插入、刪除、查找、計數(shù)、輸出、排序、逆置要單獨寫成函數(shù)），并能在屏幕上輸出操作前后的結(jié)果。1.2二叉樹的基本操作 1.2.1 設計目的 ? 掌握二叉樹的概念和性質(zhì) ? 掌握任意二叉樹存儲結(jié)構。? 掌握任意二叉樹的基本操作。 1.2.2 設計內(nèi)容和要求(1)對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存儲結(jié)構，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判棧空）實現(xiàn)二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結(jié)果。(2)求二叉樹高度、結(jié)點數(shù)、度為1的結(jié)點數(shù)和葉子結(jié)點數(shù)。第二篇：數(shù)據(jù)結(jié)構實訓報告
第三篇：數(shù)據(jù)結(jié)構實訓報告樣本
第四篇：《數(shù)據(jù)結(jié)構》實訓報告
第五篇：數(shù)據(jù)結(jié)構實訓心得體會范文
點擊咨詢 