第一篇：數據結構實訓報告
北京聯合大學
實訓報告
課程（項目）名稱： 數據結構 學 院： 專 業： 班 級： 學 號：
姓 名： 成 績：
2012年 6 月 21 日
數據結構實訓任務一
一、任務與目的：
1、用順序表表示兩個無序集合A、B，實現集合的如下操作，求兩個集合的并集、交集、差集。
2、用順序表表示兩個集合A、B（集合A、B都是有序遞增的情況）實現集合的如下操作，求兩個集合的并集、交集、差集。
3、用帶頭單鏈表存儲結構表示兩個無序集合A、B，實現集合的如下操作，求兩個集合的并集、交集、差集。
4、用帶頭單鏈表存儲結構表示兩個集合A、B（集合A、B都是有序遞增的情況），實現集合的如下操作，求兩個集合的并集、交集、差集。
5、殺人游戲 N個人坐成一圈玩殺人游戲，按順時針編號
N。從1號開始順時針開始數到第m號就殺掉第一個人，被殺掉的人要退出游戲。
如果數到了編號的末尾，接著數開頭的編號。
重復，直至殺掉一半人時，游戲結束，聰明的你能告訴我活到最后的幸存者最初的編號是多少嗎？ 輸入數據：N、M ；輸出數據：幸存者的編號
分析該程序，如果N=20，M=2，……10。聰明的你應選擇的編號是多少，（提示，計算出M分別等于1到10的情況下，那些編號生存概率較大）。給出實驗結果
6、作業抽查問題：有35個學生的班級，由于某種原因不能夠做到全部檢查作業，現在希望每次抽查10名學生，希望能夠隨機抽查，并能夠有記憶，即希望抽查過的學生，下次抽查的概率有所減小，但避免不被抽查。設計一個算法實現該功能，給出你的解釋。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;} 運行結果： 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++;} 運行結果： 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++;}}}} 運行結果： 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++;}}}} 運行結果： 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<<“請輸入參加殺人游戲總人數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; //定義學生抽查數};Student stu[35];//35個學生 int cho[10]; //抽查的10個學生 int top; //已抽查學生數 int choose(){int n=rand()%35;//隨機抽取 for(int i=0;i int n2=rand()%stu[n].times;//否則幾率按抽取的次數減小,具體為(1/抽取次數)if(n2==0)return n;else return choose();} void main(){char a='Y';srand(time(0));//隨機數初始化 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<<“第”< 數據結構實訓任務二 一、任務與目的：主要考察的是棧與隊列的邏輯結構和存儲結構。 1、用棧，判斷一個算數表達式中的圓括弧、方括弧和花括弧是否匹配。 2、用棧，把十進制的整數轉換為二至九之間的任一進制 3、設計一個算法，檢測一個字符串數組是否是回文，回文是指這個字符串是否關于中心對稱。int Check（char a[]，int n） 4、采用SPT規則的單機生產計劃問題。問題描述如下，存在一臺機器，要加工n個工件，每個工件i都有一個確定的加工時間，采用按照 遞增的順序，進行加工，計算每個工件的完成時間（初始加工時間為0）。設計一個算法，輸入工件數量n，隨機在[1，30]的區間內產生每個工件的加工時間。按照SPT規則進行加工，輸出每個工件的完成時間。 5、采用EDD規則的單機生產計劃問題。問題描述如下，存在一臺機器，要加工n個工件，每個工件i都有一個確定的加工時間，同時每個工件都有一個確定的交貨期，采用按照 遞增的順序，進行加工，計算每個工件的完成時間（初始加工時間為0）。設計一個算法，輸入工件數量n，隨機在[1，30]的區間內產生每個工件的加工時間，在區間[2，20*n]內隨機產生每個工件的交貨期。按照EDD規則進行加工，輸出每個工件的完成時間，計算每個工件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<<“請輸入算術表達式(以$結尾):”;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<<“請輸入任意非負十進制數:”;cin>>a;cout<<“請輸入需要轉換的進制數(進制數為二至九):”;cin>>b;while(a){Push(s,a%b);a=a/b;} while(!(s.top==-1))cout< 運行結果： 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<<“請輸入字符串(以$結尾):”;while(ch!='$'){cin>>ch;[i]=ch;ush(s,ch);+;} n=i;Check(a,n,s);if(t==1)cout<<“是回文!”< 運行結果： 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< 數據結構實訓任務書三：二叉樹鏈式存儲的基本操作 1、創建二叉樹 a)熟悉使用教材的先序創建二叉樹的方法 b)編寫一個算法，實現在已知二叉樹的先序序列和中序序列的情況下創建二叉樹。 c)如果已知二叉樹的順序表示形式，將其轉換為二叉樹的鏈式存儲方式。 2、二叉樹的遍歷 a)先序、中序和后序三種形式的鏈式存儲遞歸式算法 b)先序、中序和后序三種形式的鏈式存儲非遞歸式算法 c)層次遍歷的算法。 3、二叉樹一些基本操作 a)計算二叉樹的深度； b)計算二叉樹的葉子節點個數 c)計算二叉樹的單支節點的個數 d)計算二叉樹的雙支節點的個數 4、編寫一個主函數能夠測試你所設計的算法。 主函數調用教材創建二叉樹的創建教材圖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 //二叉樹結點的結構體表示形式 {char data;struct node* left,*right;}BTree;typedef BTree *Tree;typedef struct stackelem //棧的結構體表示形式 {BTree* a[MAXSIZE];int top;}Stack;void CreateBiTree_Rec(Tree &T)//先序創建二叉樹的方法 {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)//前序遍歷的非遞歸實現 {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)//中序遍歷，遞歸實現 {if(NULL!=t){Inorder(t->left); cout< Inorder(t->right);}} void Inorder2(Tree t)//中序遍歷，非遞歸實現 {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)//后序遍歷，遞歸實現 {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)//求二叉樹的高度，遞歸實現{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) //葉子結點 {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)//二叉樹的順序表示形式，將其轉換為二叉樹的鏈式存儲方式 {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< 數據結構實訓任務書四：圖的操作 1、建立圖的存儲結構 a)創建圖的鄰接矩陣表示方式 b)創建圖的鄰接表表示方式 c)實現兩種方式的互換 2、圖的遍歷 a)基于鄰接矩陣的深度和廣度遍歷 b)基于鄰接表的深度和廣度遍歷 3、最小生成樹，使用Prim算法實現從某一節點出發的圖的最小生成樹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<<“請輸入頂點數:”;cin>>g.vnum;cout<<“請輸入邊數:”;cin>>g.ednum;cout<<“請輸入構造頂點數組頂點值:”< 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(“循環隊列空!”);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)//此函數用于實現將鄰接矩陣轉換成鄰接表{ 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)//表轉矩陣 { 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;//與之相連的端點 }; //存儲節點信息 vexNode adjlist[MAX];//訪問標志 bool visited[MAX];//lowcost[j]存儲從開始節點到節點j的最小花費 WeiType lowcost[MAX];//parent[j]表示節點j的前驅節點 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<<“請輸入節點”< 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、評語 工作態度（認真、一般、較差），工作量（飽滿、一般、不夠），每個任務能夠獨立（完成、基本完成、在輔導下完成），程序運行結果（正確、基本正確、部分正確），實訓報告格式（標準、一般）。創新意識（較強、一般、沒有），運行所學知識解決實際問題的能力（強、一般、較差）。 ? 優(100~90)：能夠熟練運用開發工具，編程解決實際問題，創意新穎，功能實現完善。 ? 良(89~80)：能夠熟練運用開發工具，編程解決實際問題，有一定創新，功能實現較好。 ? 中(79~70)：能夠較熟練使用開發工具，編程解決實際問題，獨立完成實訓，功能實現一般。 ? 及格(69~60)：能夠運用開發工具，在教師輔導下完成實訓，實現部分功能。? 不及格(59~0)：編程解決實際問題的能力差，功能實現較差。 實訓成績為： 分 教師簽字： 題目：在火車貨場車皮編解場，2條軌道連接到2條側軌道，形成2個鐵路轉軌棧，其中左邊軌道為車皮入口，編號為A；右邊軌道為出口，編號為D；2個鐵路轉軌棧分別編號為C和D如下圖所示。編號為a, b, c, ┅, n的各車皮依序停放在車皮的入口處，調度室要安排個車皮進出棧次序，使得在出口處各車皮按照預先制定的順序依次出站。車皮移動時只能按照從左到右的方向移動。組織與指導老師： 組長：* 成員：*** 指導教師：* 完成時間、地點： 時間：第16周（6月6日～6月10日） 地點：南校區東教學樓2樓機房。 一、需求分析 1、問題描述 掌握隊列、棧、樹的結構以及基本操作，熟悉for循環語句，if條件語句的嵌套，結構體函數等，從而實現程序的功能。 例如： typedef struct Stack { Data *data; Data *end; }Stack; …… 2、實現功能 （1）對于給定的車皮數n，以及各車皮的出站順序，編程計算最優調度方案，使得移動車皮的次數最少。 （2）數據輸入：由文件input.txt給出數據。第一行有1個正整數n，表示車皮數；接下來的1行是一個字符串，表示預先確定的車皮的出站順序。 （3）數據輸出：將計算得到的最優調度方案輸出到文件output.txt，文件的第一行使最少移動次數m，接下來的m行使對于最優方案的m次移動。每次移動用“cXY”的3個字符表示，其中c表示車皮編號，X表示其時棧號，Y表示目標棧號。如果無法調度則輸出“No Solution!” 二、概要設計 1、抽象數據類型 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、程序中包含功能模塊及模塊間的調用關系 各個基本操作都通過公有成員函數實現，然后通過主程序調用來實現程序的功能。 例如： 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(); } 三、調試分析 完成情況說明： 編譯程序的過程中發現了許多漏洞，調試起來很不方便，經過我和同學的共同努力，終于有了突破性的進展，程序按照預定的時間調試出來了，雖然當中還存在不少的漏洞，但不會影響程序的正常運行。 程序的性能分析：各個操作都是通過公有函數的調用來實現的，其中用到結構體函數，for循環，If語句的嵌套等，通過測試可以實現其預定的功能。出現的問題及解決方案： 缺失頭文件導致的定義無效錯誤，通過添加頭文件即可解決問題；定義字符類型錯誤，使用正確的函數類型定義即可，for循環的循環語句語法使用不當，導致函數無法實現循環，if條件語句的應用還存在問題，以上所述的編譯錯誤都通過我很同學的認真分析后糾正了。 四、用戶使用說明 了解程序的執行過程，輸入合法的數值是程序正常運行的關鍵，輸入的數值和開始需要的字符的長度要符合五、心得體會： 通過多次編寫程序，我總結出來一條心得，程序不能寫完才調試，而是應該寫一個函數調試一個函數，這樣才能縮小調試的范圍，提高編程的效率，程序編完后在進行一次綜合調試，將不完善的函數和功能處理好，才能將程序做到最好！而且，很多時候，一個大的工程并不是一個人就能完成，這就要求我們有團隊精神。讓我感受最深的是在我調試程序的時候，一個很細微的錯誤就可能導致程序的出錯，正所謂的“細節決定成敗”，不管是在學習中，生活中，我們都要有一顆善于發現問題，解決問題的新，除此之外，還要有樂于助人的精神。 （數據結構實訓報告） 目錄 一、實訓目的...........................................................1 二、實訓題目...........................................................1 三、實訓步驟...........................................................2 四、實訓內容...........................................................2 五、實訓心得..........................................................19 六、參考文獻..........................................................19 吉林工業職業技術學院 數據結構實訓 一、實訓目的 通過實訓，對所學數據結構和程序設計的基本知識和基本理論有更進一步的了解和認識，將理論和實際相結合，能夠根據數據對象的特性，學會數據組織的方法，能把現實世界中的實際問題在計算機內部表示出來。主要是培養學生綜合利用C語言進行程序設計的能力和創新能力以及綜合解決問題的能力。運用算法分析與程序設計的一般方法進行實際項目的開發。本次實訓盡量選取與實際結合緊密或學生比較感興趣的項目，本次實訓學生需要具備熟練的程序設計基礎、數據結構和計算機應用基礎知識，具備程序編寫、調試的基本能力，具有一定的文字表達和報告撰寫能力，具備辦公軟件使用能力。 通過實訓，考查語言基本概述掌握是否牢固，并考查與后續課程較為密切的結構體，鏈表，文件的運用熟練程度，加強對基本概念的理解和復習，最重要的是了解基本軟件的設計步驟，還有對軟件調試的掌握。能夠根據數據對象的特性，學會數據組織的方法，能把現實世界中的實際問題在計算機內部表示出來，并培養基本的、良好的程序設計技能。 二、實訓題目 （一）單項題目 1、二叉樹遍歷 【問題描述】建立二叉樹，實現二叉樹的先序遍歷、中序、后序和層序遍歷（用遞歸或非遞歸的方法都可以）。 【要 求】編寫菜單程序。能夠輸入二叉樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲結構的輸入函數、輸出先序遍歷序列的函數；輸出中序遍歷序列的函數；輸出后序遍歷序列的函數；輸出層序遍歷序列的函數。 （二）綜合題目 1、圖書管理系統 吉林工業職業技術學院 數據結構實訓 【問題描述】建立一個圖書信息文件，包括書號（num）、書名（bookname）、作者（name）、出版社（publish）、價格（price）等。 【要 求】建立一個圖書信息文件，包括書號（num）、書名（bookname）、作者（name）、出版社（publish）、價格（price）等。 三、實訓步驟 1、問題分析 正確理解問題，分析問題究竟“做什么”，分析問題已知的信息及其作用，分析在解決中對信息處理的規則、要求、限制條件，分析問題解決后應該輸出什么樣的結果（輸出形式、格式、內容）。并分析得出判定結果是否正確的標準。 2、設計分析 得出解決問題的思路、主要流程、采用的數據結構類型的說明、主要算法的思想。 3、設計方案 采用的數據結構類型的定義、主要算法的描述及說明。 4、詳細設計 根據問題要求和已得到的算法編寫程序。 5、調試程序 發現程序中存在的語法錯誤和一些邏輯錯誤，并修改，使程序能夠運行。 6、運行程序 選擇若干具有代表性的輸入數據（包括合理數據和不合理數據），進行測試，盡量使程序的各語句和分支都被檢查到，以便發現程序中的錯誤和漏洞，以便改進算法和程序。 7、使用說明 包括程序源代碼、算法（程序）流程圖、開發過程中各階段的有關記錄、算法的正確性證明、程序的測試結果、對輸入輸出要求及格式的詳細描述。 四、實訓內容 （一）個人題目 1、二叉樹遍歷 【問題描述】建立二叉樹，實現二叉樹的先序遍歷、中序、后序和層序遍歷（用遞歸或非遞歸的方法都可以）。吉林工業職業技術學院 數據結構實訓 【要 求】編寫菜單程序。能夠輸入二叉樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立二叉樹存儲結構的輸入函數、輸出先序遍歷序列的函數；輸出中序遍歷序列的函數；輸出后序遍歷序列的函數；輸出層序遍歷序列的函數。 【設計分析】 1、總體設計(基本概念)樹的概念 樹（Tree）是n（n>=0）個結點的有限集。在任意一棵非空樹中： 1)有且僅有一個特定的稱為根的結點； 2)當n>1時，其余結點可分為m（m>0）個互不相交的有限集T1，T2......Tm，其中每一個集合又是一棵樹，并且稱為根的子樹（SubTree）。 【例】如圖1所示： 圖1 圖1是有8個結點的樹，其中A是根，其余結點分成2個互不相交的子集：T1={B，D}，T2={C，E，F，G，H}；T1和T2都是根A的子樹，且本身也是一棵樹。 【設計方案】1．創建二叉樹（可從鍵盤輸入各結點的值）2．按某種方式對二叉樹進行遍歷 3．樹型結構是一種非常重要的非線性結構。樹在客觀世界是廣泛存在的，在計算 機領域里也得到了廣泛的應用。在編譯程序里，也可用樹來表示源程序的語法結構，在數據庫系統中，數形結構也是信息的重要組織形式。 4．節點的有限集合（N大于等于0）。在一棵非空數里：（1）、有且僅有 吉林工業職業技術學院 數據結構實訓 一個特定的根節點；（2）、當N大于1時，其余結點可分為M（M大于0）個互不相交的子集，其中每一個集合又是一棵樹，并且稱為根的子樹。樹的定義是以遞歸形式給出的。 5．二叉樹是另一種樹形結構。它的特點是每個結點最多有兩棵子樹，并且，二叉 樹的子樹有左右之分，其次序不能顛倒。 從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：（1）訪問結點本身(N)，（2）遍歷該結點的左子樹(L)，（3）遍歷該結點的右子樹(R)。以上三種操作有六種執行次序： NLR、LNR、LRN、NRL、RNL、RLN?！驹敿氃O計】本程序源代碼如下： /*源程序*/ /* 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];吉林工業職業技術學院 數據結構實訓 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(“堆棧已空無數據元素出棧!n”); return 0; } else { S->top--; *d = S->stack[S->top]; return 1;吉林工業職業技術學院 數據結構實訓 } } 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)吉林工業職業技術學院 數據結構實訓 { 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);} 吉林工業職業技術學院 數據結構實訓 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(“創建二叉樹，請輸入完全二叉樹的先序序列，用*代表虛結點:”);root=CreatBTree();//返回根結點 do{ 吉林工業職業技術學院 數據結構實訓 printf(“t1:先序遍歷n”);printf(“t2:中序遍歷n”);printf(“t3:后序遍歷n”);printf(“t4:深度、結點數、葉子數n”);printf(“t5:層次遍歷n”);printf(“備注：選擇層次遍歷之前，需要先選擇4，求出該樹的結點數。”); printf(“t0:Exitn”); scanf(“%d”,&i);//輸入菜單序號 switch(i) { case 1:printf(“先序遍歷結果為:”); Preorder(root); break; case 2:printf(“中序遍歷結果為:”); Inorder(root); break; case 3:printf(“后序遍歷結果為:”); Postorder(root); break; case 4:depth=TreeDepth(root); printf(“深度=%d 結點數=%d”,depth,NodeNum); printf(“葉子數=%d”,leaf); break; case 5:printf(“層次遍歷為:”); Levelorder(root); break; default:exit(1); } printf(“n”);} while(i!=0);} 吉林工業職業技術學院 數據結構實訓 【使用說明】本程序在turboc 2.0環境下運行，迷宮大小為20×20，需要修改迷宮大小時，可以修改程序中N值的大小。迷宮圖由系統自動隨機生成，每次生成的迷宮圖是不同的。按enter健顯示最終搜索結果。按Q健退出程序。 【運行調試】 圖（1）二叉樹遍歷主界面 圖（2） （二）綜合題目 1、圖書管理系統 【問題描述】建立一個圖書信息文件，包括書號（num）、書名（bookname）、作者（name）、出版社（publish）、價格（price）等。 【要 求】編寫菜單程序，功能包括：建立圖書信息、插入記錄，刪除記錄、修改記錄、按照書號或書名查詢記錄、顯示記錄、根據圖書價格進行排序。定義圖書信息結構體名稱為book。書號（num）、書名（bookname）、作者（name）、出版社（publish）均為字符型數組。價格（price）為單精度型數據。 吉林工業職業技術學院 數據結構實訓 【設計分析】系統目標分析 每個學校都有圖書館，最初由于圖書數量和種類較少，人工手動管理比較方便和靈活。隨著社會的發展，圖書的數量和種類越來越多，人工手動管理會降低工作的效率，希望建立一個圖書館圖書信息管理系統，是為了解決了人工手動管理圖書信息在實踐的問題，從而達到系統化、規范化、標準化的水平。該系統的建立不但給管理者帶來了方便，也節省了工作時間從而提高了工作效率。 在構造系統時，首先從需求出發構造數據庫表，然后再由數據庫表結合需求劃分系統功能模塊。這樣，就把一個大的系統分解成了幾個小系統。這里把系統的層次劃分為了三個部分：一個自由態：即面向任何用戶的界面，提供登錄功能，以便不同身份的用戶登錄子系統；一個是一般用戶態：即圖書有服務子系統；還有一個是管理員界面：提供圖書的管理和維護功能。對于不同子系統之間的功換，采用了登錄功能和用戶注銷功能。系統劃分了子系統后，下一步的工作是繼續劃分子系統的小模塊。先考慮在進入子系統時應該做什么，進入系統之后又應該做什么，提供那些服務等。例如，對于圖書信息服務子系統，在用戶進入時首先得調用相關數據庫表，找出用戶的圖書借閱情況；進入系統后，子系統得提供圖書查詢、圖書借閱和還書功能。另外，針對本系統的特殊情況，同時也考慮系統的可移植性，在系統中增加了數據庫路徑的維護部分。最后，考慮到系統的安全性，還在系統中特別增加了“加密界面”的功能。 【設計方案】本數據庫管理系統主要由圖書檢索、圖書管理、數據維護、圖書統計、打印輸出、系統維護六大模塊組成, 如圖1 所示。各模塊功能如下： 1、主控模塊主控模塊的功能是控制各個分支模塊,它是實現各模塊功能的總控制臺 2、圖書檢索模塊是圖書管理系統的重要模塊之一,是讀者快速查詢圖書的途徑 本模塊的功能是按書名、書號、作者、出版社、圖書分類查詢 數據維護模塊是由圖書管理員控制的模塊,它由增加、修改和刪除讀者,增加、修改刪除圖書,瀏覽修改讀者、瀏覽修改圖書等程序組成。在軟件設計時考慮到讀者編號、書名、書號是唯一的,因此,在修改讀者或圖書中,讀者記錄或圖書記錄一經登記“讀者編號”和“姓名”便不能修改,在刪除讀者或圖書時只要讀者有借出圖書未還或庫存圖書原有數量與現有庫存量不符便不能刪除。 5、數據統計模塊由讀者統計、圖書統計、借出圖書分類統計、到期未歸還圖書讀者統計幾部分組成 吉林工業職業技術學院 數據結構實訓 我們小組的信息系統開發課程設計題目是：圖書管理系統開發。系統開發的總的設計目標是實現圖書管理的系統化、規范化和自動化，實現對圖書資料的集中統一的管理。 本系統主要實現對圖書館信息的管理，主要功能為管理有關讀者，書籍，借閱和管理者的信息等。本系統結構分為讀者信息管理模塊，書籍信息管理模塊，借閱信息管理模塊，管理者信息管理模塊。讀者信息管理部分有兩方面的功能，可以瀏覽讀者的信息，可以對讀者信息進行維護。書籍信息管理可以瀏覽書籍的信息，可以對書籍信息進行維護。借閱信息管理可以顯示當前數據庫中書籍借閱情況，可以對借閱信息進行維護。管理者信息管理可以顯示數據庫中管理者的情況，可以對管理者信息進行維護?？梢?，本系統并不復雜，主要解決的問題是利用關鍵字對數據庫進行查詢。 【詳細設計】本程序源代碼如下： /*源程序*/ /* 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;/*鏈表的指針域*/ };吉林工業職業技術學院 數據結構實訓 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);/*保存數據至文件*/ /*瀏覽操作*/ void Print_Book_Doc(struct books_list * head){ struct books_list * p;if(head==NULL || head->next==NULL)/*判斷數據庫是否為空*/ { printf(“n ━━━━ 沒有圖書記錄!━━━━nn”); return;} p=head;printf(“┏━━━┳━━━┳━━━┳━━━┳━━━━┳━━━┳━━━┓n”);printf(“┃登錄號┃書名 ┃ 作者 ┃出版單位┃出版時間┃分類號┃價格┃n”); printf(“┣━━━╋━━━╋━━━╋━━━╋━━━━╋━━━╋━━━┫n”);/*指針從頭節點開始移動，遍歷至尾結點，依次輸出圖書信息*/ 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);/*循環輸出表格*/ } printf(“┗━━━┻━━━┻━━━┻━━━┻━━━━┻━━━┻━━━┛n”);printf(“n”);吉林工業職業技術學院 數據結構實訓 } /*刪除操作*/ 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);/*遍歷到尾結點*/ while(p!= NULL) { if(strcmp(p->bookname,temp)==0) { panduan++; break; } p=p->next;} if(panduan==1){ for(;s->next!=p;) /*找到所需刪除卡號結點的上一個結點*/ { s=s->next; } s->next=p->next;/*將后一節點地址賦值給前一節點的指針域*/ free(p); printf(“n ━━━━ 刪除成功!━━━━n”);} else /*未找到相應書目*/ 吉林工業職業技術學院 數據結構實訓 { printf(“ 您輸入的書目不存在，請確認后輸入!n”);} return;} int main(void){ struct books_list * head; char choice;head=NULL;for(;;)/*實現反復輸入選擇*/ { printf(“ ┏━━━━━━━━━━━━━━━━━━━┏━┓n”); printf(“ ┃ ┃ socat 圖書管理系統 ┃ ┃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]退出系統 ┃n”); printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━┛ 15 吉林工業職業技術學院 數據結構實訓 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(“ [請輸入您要刪除的書名]:”);吉林工業職業技術學院 數據結構實訓 scanf(“%s”,temp);/*遍歷到尾結點*/ while(p!= NULL) { if(strcmp(p->bookname,temp)==0) { panduan++; break; } p=p->next;} if(panduan==1){ for(;s->next!=p;) /*找到所需刪除卡號結點的上一個結點*/ { s=s->next; } s->next=p->next;/*將后一節點地址賦值給前一節點的指針域*/ free(p); printf(“n ━━━━ 刪除成功!━━━━n”);} else /*未找到相應書目*/ { printf(“ 您輸入的書目不存在，請確認后輸入!n”);} return; } else if(choice=='6') { printf(“n”); printf(“ ━━━━━━━━ 感謝使用圖書管理系統 ━━━━━━━━n”);吉林工業職業技術學院 數據結構實訓 break; } else { printf(“ ━━━━ 輸入錯誤，請重新輸入！━━━━”); break; } } } 【使用說明】本程序在turboc 2.0環境下運行，迷宮大小為20×20，需要修改迷宮大小時，可以修改程序中N值的大小。迷宮圖由系統自動隨機生成，每次生成的迷宮圖是不同的。按enter健顯示最終搜索結果。按Q健退出程序。 【運行調試】 圖（3）圖書管理系統主界面 吉林工業職業技術學院 數據結構實訓 圖（4）圖書信息瀏覽 五、實訓心得 六、參考文獻 實驗一 線性表 1.實驗要求 1.1 掌握數據結構中線性表的基本概念。 1.2 熟練掌握線性表的基本操作：創建、插入、刪除、查找、輸出、求長度及合并并運算在順序存儲結構上的實驗。1.3 熟練掌握鏈表的各種操作和應用。2.實驗內容 2.1 編寫一個函數，從一個給定的順序表A中刪除元素值在x到y之間的所有元素，要求以較高效率來實現。 2.2 試寫一個算法，在無頭結點的動態單鏈表上實現線性表插入操作 2.3 設計一個統計選票的算法，輸出每個候選人的得票結果。 3.實驗代碼 2.1代碼： #include A[i-k]=A[i];i++;} return(n-k);} void main(){ int i,j;int a[maxsize];printf(“輸入%d個數:n”,maxsize);for(i=0;i scanf(“%d,”,&a[i]); 數據結構實驗報告 j=del(a,maxsize,1,3); printf(“輸出刪除后剩下的數: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; 數據結構實驗報告 nodetype *create(){ elemtype d;nodetype h=NULL,*s,*t;int i=1;printf(“建立單鏈表:n”);while(1){ printf(“輸入第%d個結點數據域”,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); 數據結構實驗報告 } printf(“候選人:”);for(i=1;i<=N;i++)printf(“%3d”,i);printf(“n得票數n”);for(i=1;i<=N;i++)printf(“%3d”,a[i]);printf(“n”);4.實驗小結 線性表是最簡單的、最常用的一種數據結構，是實現其他數據結構的基礎。 實驗二 棧與隊列 1.實驗要求 1.1 了解棧和隊列的特性，以便靈活運用。1.2 熟練掌握棧和有關隊列的各種操作和應用。 2.實驗內容 2.1 設一個算術表達式包括圓括號，方括號和花括號三種括號，編寫一個算法判斷其中的括號是否匹配。 3.實驗代碼 2.1代碼： #include 數據結構實驗報告 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); 數據結構實驗報告 } 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.實驗小結 棧和隊列是最基礎的一種數據結構之一，為實現其他數據結構的奠定基石。 實驗三 樹 1.實驗要求 1.1 掌握二叉樹，二叉樹排序數的概念和存儲方法。1.2 掌握二叉樹的遍歷算法。 1.3 熟練掌握編寫實現樹的各種運算的算法。 2.實驗內容 2.1 編寫程序，求二叉樹的結點數和葉子數。 2.2 編寫遞歸算法，求二叉樹中以元素值為X的結點為根的子數的深度。2.3 編寫程序，實現二叉樹的先序，中序，后序遍歷，并求其深度。 數據結構實驗報告 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(“此二叉數的接點數有:%dn”,n);printf(“此二叉數的葉子數有:%dn”,n1);} 數據結構實驗報告 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 數據結構實驗報告 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 數據結構實驗報告 } { 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(“此二叉數的深度是:”);printf(“depth=%dn”,depth(root));4.實驗小結 通過本章學習實驗，對樹有了初步的認識。樹就是一種非線性的數據結構，描述了客觀世界中事物之間的層次關系。這種結構有著廣泛的應用，一切具有層次關系的問題都可以用樹來表示。 實驗四 圖 1.實驗要求 1.1 熟悉圖的各種存儲方法。 1.2 掌握遍歷圖的遞歸和非遞歸的算法。1.3 理解圖的有關算法。 2.實驗內容 2.1 寫出將一個無向圖的鄰接矩陣轉換成鄰接表的算法。 數據結構實驗報告 2.2 以鄰接表作存儲結構，給出拓撲排序算法的實現。 3.實驗代碼 2.1代碼： void mattolist(int a[][],adjlist b[],int n)/*n為圖的結點個數*/ { 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));/*產生鄰接點*/ 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) 數據結構實驗報告 { LstackTp *p;/*建立入度為0的頂點棧S*/ int m,i,v; initStack(S); } for(i=0;i } if(m 通過本章學習實驗，對圖有了具體的認識。圖也是一種非線性的數據結構，這種結構有著廣泛的應用，一切具有關系的問題都可以用圖來表示。 數據結構實驗報告 實驗五 查找 1.實驗要求 1.1 掌握順序查找、二分法查找、分塊查找和哈希表查找的算法。1.2 能運用線性表的查找方法解決實際問題。2.實驗內容 2.1 編寫一個算法，利用二分查找算法在一個有序表中插入一個元素X，并保持表的有序性。 2.2 根據給定的數據表，先建立索引表，然后進行分塊查找。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++)/*顯示數據*/ printf(“%3d”,*(data+insert)); 數據結構實驗報告 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;/*沒有找到插入數據，返回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;/*找到插入數據，返回mid*/ else if(*(data+mid)<*data)else if(*()data+mid)>*data)*(data+insert)=*data 數據結構實驗報告 } 2.2代碼： #include /*元素個數*/ #definr Blocknum 3 /*分塊數*/ typedef struct indexterm { int key;/*最大關鍵字*/ int addr;/*塊的起始地址*/ }index;/*索引表數據類型*/ 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 數據結構實驗報告 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.實驗小結 通過本章的學習，對排序有較高層次的理解與認識，從平時的練習中可以看出排序是數據處理中經常用到的重要運算。有序的順序表可以采用查找效率較高的折半查找法，而無序的順序表只能用效率較低的順序查找法。 這次課程設計的心得體會通過實習我的收獲如下 1、鞏固和加深了對數據結構的理解，提高綜合運用本課程所學知識的能力。 2、培養了我選用參考書，查閱手冊及文獻資料的能力。培養獨立思考，深入研究，分析問題、解決問題的能力。 3、通過實際編譯系統的分析設計、編程調試，掌握應用軟件的分析方法和工程設計方法。 4、通過課程設計，培養了我嚴肅認真的工作作風，逐步建立正確的生產觀念、經濟觀念和全局觀念。從剛開始得覺得很難，到最后把這個做出來，付出了很多，也得到了很多，以前總以為自己對編程的地方還不行，現在，才發現只要認真做，沒有什么不可能。編程時要認真仔細，出現錯誤要及時找出并改正，（其中對英語的要求也體現出來了，因為它說明錯誤的時候都是英語）遇到問題要去查相關的資料。反復的調試程序，最好是多找幾個同學來對你的程序進行調試并聽其對你的程序的建議，在他們不知道程序怎么寫的時候完全以一個用戶的身份來用對你的用戶界面做一些建議，正所謂當局者迷旁觀者清，把各個注意的問題要想到；同時要形成自己的編寫程序與調試程序的風格，從每個細節出發，不放過每個知識點，注意與理論的聯系和理論與實踐的差別。另外，要注意符號的使用，注意對字符處理，特別是對指針的使用很容易出錯且調試過程是不會報錯的，那么我們要始終注意指針的初始化不管它怎么用以免不必要麻煩。通過近兩周的學習與實踐，體驗了一下離開課堂的學習，也可以理解為一次實踐與理論的很好的連接。特別是本組所做的題目都是課堂上所講的例子，在實行之的過程中并不是那么容易事讓人有一種紙上談兵的體會，正所謂紙上得來終覺淺絕知此事要躬行。實訓過程中讓我們對懂得的知識做了進一步深入了解，讓我們的理解與記憶更深刻，對不懂的知識與不清楚的東西也做了一定的了解，也形成了一定的個人做事風格。 通過這次課程設計，讓我對一個程序的數據結構有更全面更進一步的認識，根據不同的需求，采用不同的數據存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數組，只要運用得當，也能達到相同的效果，甚至更佳，就如這次的課程設計，通過用for的多重循環，舍棄多余的循環，提高了程序的運行效率。在編寫這個程序的過程中，我復習了之前學的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應用范圍，程序結構算法等一系列的問題它使我對數據結構改變了看法。在這次設計過程中，體現出自己單獨設計模具的能力以及綜合運用知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，也從中發現自己平時學習的不足和薄弱環節，從而加以彌補。篇二：數據結構試驗心得 數據結構課程設計心得體會（專業：計算機科學與技術 姓名：朱文 學號：2011220137） 通訊錄管理系統是基于雙向循環鏈表設計而成的信息管理系統。該系統通過對程序進行模塊化，建立添加、顯示、查找和刪除功能的函數，各函數中運用雙向循環鏈表存儲數據。為存儲通訊錄信息，需定義一個結構體類型，成員包括姓名、街道、城市、郵編、國家等，并建立雙向循環鏈表，定義該結構體類型的指針，用于指向各結點。分別建立具有添加、刪除、修改、查詢等功能的子函數，完成相應功能，對程序實現模塊化。這其中要用到對鏈表的刪除、插入等知識。為實現存儲功能，需用到文件的相關函數 開發一個通訊錄管理系統，借助計算機可以方便、快捷、靈活的管理個人的朋友及相關人員的通訊信息，了解友人相關信息，幫助與友人保持聯絡。所以設計一個通訊錄管理系統管理各人的通訊信息是非常必要的，同時，通過用循環雙向鏈表設計通訊錄管理系統可以讓我們更好的去理解循環雙向鏈表，更好的學好數據結構這門課程。本次實驗中，我們使用分工合作的方式，首先定義了函數的結構體部分，剩下的根據函數所要實現的功能進行分工合作，我實現的是通訊錄中刪除功能的子函數，刪除信息（void delete(dnode *head)）的功能是按照用戶輸入的姓名首先進行按姓名查詢功能，查找成功，則執行刪除信息的功能，查詢不成功，則提示錯誤信息。定義結點p，輸入要刪除的信息的姓名，按姓名查找結點，如果找到匹配的結點p，就進行相關的刪除操作，否則就是沒找到要刪除的數據，最后返回到主函數。 這次實驗中我深刻認識到合作的重要性。例如：我所編寫的按名刪除功能的實現中，應用了章林霞同學所編寫寫的按名搜索查詢功能的那部分函數，在這次實驗中，我學到很多東西，加強了我的動手能力，并且培養了我的獨立思考能力。我們堅持理論聯系實際的思想，以實踐證實理論，從實踐中加深對理論知識的理解和掌握。實驗是我們快速認識和掌握理論知識的一條重要途徑。通過這次課程設計，我們對c語言以及數據結構有了更深刻的了解，增強了程序的編寫能力，鞏固了專業知識，對程序的模塊化觀念也又模糊逐漸變的清晰了。在程序的運行與調試過程中出現了很多錯誤，通過反復地復習課本上的相關知識，不停地修改與調試，我們終于完成了這段程序。在調試過程中，我們認識到了數據結構的靈活性與嚴謹性，同一個功能可以由不同的語句來實現，但編寫程序時要特別注意細節方面的問題，因為一個小小的疏忽就能導致整個程序不能運行。我們也認識到了自己的薄弱之處，如對鏈表相關知識的欠缺，文件運用的不熟練，在以后的學習中我們要集中精力、端正態度，爭取把知識學得更扎實、更全面。 經過這次的實驗，我們整體對各個方面都得到了不少的提高，希望以后學校和系里能夠開設更多類似的實驗，能夠讓我們得到更好的鍛煉。也讓我們深深感受到討論交流很重要，遇到困難時，大家一起討論，加強我們的團隊合作精神，同時通過這次的課程設計，我們對 數據結構中雙向鏈表結構有了更深刻的理解。篇三：數據結構綜合實驗心得體會 心得體會： 做了一個星期的程序設計終于做完了，在這次程序設計課中，真是讓我獲益匪淺。對大一學習的c語言和這學期開的數據結構，并沒有掌握，很多知識都不太懂，突然讓自己獨立完成一個程序讓我手忙腳亂，起碼在我認為那真的特別難，看了老師給的題目以及上網查找了一些相關的知識，簡單的編了幾行就告一段落了，第一天等于只完成了老師要求寫的需求分析和概要設計，后來查找了關于哈希表的相關知識，了解了如何創建哈希表，如何合適的構建哈希函數，（選取合適的表長，合適的余數，使得查找時間以及平均查找長度最短）以及什么是除留余數法，和怎樣用除留余數法創建哈希表，看懂了之后，我又看了處理沖突的方法，有三種線性探測再散列法法，二次探測再散列法，偽隨機數序列法三種，而我所要做的是第一種線性探測再散列的方法，相較后兩種要簡單很多，在遇到沖突的時候地址加一，知道沖突解決。 在了解這些概念以后，我就開始著手編程序了，在遇到問題的時候請教我們班擅長的同學，慢慢把不能不會不理解的地方給弄明白了，在經過很多次調試以后，一些基本功能已經可以實現了，為了使平均查找長度越小越好，我不斷嘗試新的表長以及除數，在沒有出現錯誤的基礎上，將功能實現，最后，終于在周四的時候將所有的程序調試完全。這次的綜合性實驗使我了解到，平時對知識的積累相當重要，同時也要注重課上老師的講解，老師在課上的延伸是課本上所沒有的，這些知識對于我們對程序的編寫有很大的作用，同時，編程也要求我們有足夠的耐心，細細推敲。越著急可能就越無法得到我們想要的結果，遇到不會的問題要多多請教，知識是在實踐與向別人請教的過程中積累的，所以問是至關重要的，只要肯下功夫很多東西都是可以完成的。篇四：數據結構實驗報告及心得體會 2011~2012第一學期數據結構實驗報告 班級：信管一班 學號：201051018 姓名：史孟晨 實驗報告題目及要求 一、實驗題目 設某班級有m（6）名學生，本學期共開設n（3）門課程，要求實現并修改如下程 序（算法）。 1.輸入學生的學號、姓名和 n 門課程的成績（輸入提示和輸出顯示使用漢字系統），輸出實驗結果。（15分） 2.計算每個學生本學期 n 門課程的總分，輸出總分和n門課程成績排在前 3 名學 生的學號、姓名和成績。 3.按學生總分和 n 門課程成績關鍵字升序排列名次，總分相同者同名次。 二、實驗要求 1．修改算法。將奇偶排序算法升序改為降序。（15分）2．用選擇排序、冒泡排序、插入排序分別替換奇偶排序算法,并將升序算法修改為 降序算法。（45分））3．編譯、鏈接以上算法，按要求寫出實驗報告（25）。4.修改后算法的所有語句必須加下劃線，沒做修改語句保持按原樣不動。5．用a4紙打印輸出實驗報告。 三、實驗報告說明 實驗數據可自定義，每種排序算法數據要求均不重復。(1)實驗題目：《n門課程學生成績名次排序算法實現》；(2)實驗目的：掌握各種排序算法的基本思想、實驗方法和驗證算法的準確性；(3)實驗要求：對算法進行上機編譯、鏈接、運行；(4)實驗環境（windows xp-sp3,visual c++)；(5)實驗算法（給出四種排序算法修改后的全部清單）；(6)實驗結果（四種排序算法模擬運行后的實驗結果）；(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 /*對所有奇數項進行一遍比較*/ 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(名 次 學 號 姓 名 分 數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(數據結構:);scanf(%4d,&stu[i].score[0]);printf(離散數學:);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 山東科技大學泰山科技學院 課程實訓說明書 課程： 數據結構項目實訓 題目： 院 系： 信息工程系 2014年 5月 25日 專業班級： 學 號： 學生姓名： 指導教師： 目 錄 一、設計題目..........................................................3 1.1 順序表操作.........................................................3 1.2 鏈表操作..........................................................3 1.3 二叉樹的基本操作..................................................3 二、運行環境（軟、硬件環境）.......................................3 2.1 軟件環境..........................................................3 2.2 硬件環境..........................................................3 三、數據結構及算法設計的思想.......................................3 3.1 順序表設計構思.....................................................3 3.2 鏈表設計構思......................................................4 3.3 二叉樹設計構思....................................................4 四、源代碼............................................................5 5.1 順序表源代碼......................................................5 5.2 鏈表源代碼........................................................6 5.3 二叉樹源代碼......................................................8 五、運行結果分析.....................................................11 6.1 順序表運行結果...................................................11 6.2 鏈表運行結果.....................................................13 6.3 二叉樹運行結果...................................................15 七、實習總結........................................................18 一、設計題目 1.1鏈表操作 1.1.1 設計目的 ? 掌握線性表的在順序結構和鏈式結構實現。? 掌握線性表在順序結構和鏈式結構上的基本操作。1.1.2 設計內容和要求 利用順序表鏈表的插入運算建立線性鏈表，然后實現鏈表的查找、插入、刪除、計數、輸出、排序、逆置等運算（查找、插入、刪除、查找、計數、輸出、排序、逆置要單獨寫成函數），并能在屏幕上輸出操作前后的結果。1.2二叉樹的基本操作 1.2.1 設計目的 ? 掌握二叉樹的概念和性質 ? 掌握任意二叉樹存儲結構。? 掌握任意二叉樹的基本操作。 1.2.2 設計內容和要求(1)對任意給定的二叉樹（頂點數自定）建立它的二叉鏈表存儲結構，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判?？眨崿F二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結果。(2)求二叉樹高度、結點數、度為1的結點數和葉子結點數。第二篇：數據結構實訓報告
第三篇：數據結構實訓報告樣本
第四篇：《數據結構》實訓報告
第五篇：數據結構實訓心得體會范文
點擊咨詢 