2020年國(guó)家開(kāi)放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)形成性考核冊(cè)實(shí)驗(yàn)名稱：實(shí)驗(yàn)一線性表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)【問(wèn)題描述】某項(xiàng)比賽中，評(píng)委們給某參賽者的評(píng)分信息存儲(chǔ)在一個(gè)帶頭結(jié)點(diǎn)的單向鏈表中，編寫(xiě)程序：顯示在評(píng)分中給出最高分和最低分的評(píng)委的有關(guān)信息（姓名、年齡、所給分?jǐn)?shù)等）。在鏈表中刪除一個(gè)最高分和一個(gè)最低分的結(jié)點(diǎn)。計(jì)算該參賽者去掉一個(gè)最高分和一個(gè)最低分后的平均成績(jī)?！净疽蟆拷⒁粋€(gè)評(píng)委打分的單向鏈表；顯示刪除相關(guān)結(jié)點(diǎn)后的鏈表信息。顯示要求的結(jié)果?！緦?shí)驗(yàn)步驟】運(yùn)行PC中的MicrosoftVisualC++6.0程序，點(diǎn)擊“文件”→“新建”→對(duì)話窗口中“文件”→“c++SourceFile”→在“文件名”中輸入“X1.cpp”→在“位置”中選擇儲(chǔ)存路徑為“桌面”→“確定”，輸入程序代碼，程序代碼如下:#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<iostream.h>#include<conio.h>#defineNULL0#definePWRS5//定義評(píng)委人數(shù)structpw//定義評(píng)委信息{charname[6];floatscore;intage;};typedefstructpwPW;structnode//定義鏈表結(jié)點(diǎn){structpwdata;structnode*next;};typedefstructnodeNODE;NODE*create(intm);//創(chuàng)建單鏈表intcalc(NODE*h);//計(jì)算、數(shù)據(jù)處理voidprint(NODE*h);//輸出所有評(píng)委打分?jǐn)?shù)據(jù)voidinput(NODE*s);//輸入評(píng)委打分?jǐn)?shù)據(jù)voidoutput(NODE*s);//輸出評(píng)委打分?jǐn)?shù)據(jù)voidmain(){NODE*head;floatave=0;floatsum=0;head=create(PWRS);printf("所有評(píng)委打分信息如下:\n");print(head);//顯示當(dāng)前評(píng)委打分calc(head);//計(jì)算成績(jī)printf("該選手去掉1最高分和1最低分后的有效評(píng)委成績(jī):\n");print(head);//顯示去掉極限分后的評(píng)委打分}voidinput(NODE*s){printf("請(qǐng)輸入評(píng)委的姓名:");scanf("%S",&s->);printf("年齡:");scanf("%d",&s->data.age);printf("打分:");scanf("%f",&s->data.score);printf("\n");}voidoutput(NODE*s){printf("評(píng)委姓名:%8s,年齡:%d,打分:%2.2f\n",s->,s->data.age,s->data.score);}NODE*create(intm){NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;i<=m;i++){p=(NODE*)malloc(sizeof(NODE));input(p);p->next=NULL;q->next=p;q=p;}return(head);}voidprint(NODE*h){for(inti=1;((i<=PWRS)&&(h->next!=NULL));i++){h=h->next;output(h);}printf("\n");}intcalc(NODE*h){NODE*q,*p,*pmin,*pmax;floatsum=0;floatave=0;p=h->next;//指向首元結(jié)點(diǎn)pmin=pmax=p;//設(shè)置初始值sum+=p->data.score;p=p->next;for(;p!=NULL;p=p->next){if(p->data.score>pmax->data.score)pmax=p;if(p->data.score<pmin->data.score)pmin=p;sum+=p->data.score;}cout<<"給出最高分的評(píng)委姓名："<<pmax-><<"年齡："<<pmax->data.age<<"分值："<<pmax->data.score<<endl;cout<<"給出最低分的評(píng)委姓名："<<pmin-><<"年齡："<<pmin->data.age<<"分值："<<pmin->data.score<<endl;printf("\n");sum-=pmin->data.score;sum-=pmax->data.score;for(q=h,p=h->next;p!=NULL;q=p,p=p->next){if(p==pmin){q->next=p->next;p=q;}//刪除最低分結(jié)點(diǎn)if(p==pmax){q->next=p->next;p=q;}//刪除最高分結(jié)點(diǎn)}ave=sum/(PWRS-2);cout<<"該選手的最后得分是："<<ave<<endl;return1;}程序運(yùn)行結(jié)果如下:線性表的順序存儲(chǔ)結(jié)構(gòu)【問(wèn)題描述】用順序表A記錄學(xué)生的信息，編寫(xiě)程序：（1）將A表分解成兩個(gè)順序表B和C，使C表中含原A表中性別為男性的學(xué)生，B表中含原表中性別為女性的學(xué)生，要求學(xué)生的次序與原A表中相同。（2）分別求男生和女生的平均年齡【基本要求】建立學(xué)生信息的順序表A。顯示B表和C表中的相關(guān)信息。顯示計(jì)算結(jié)果?！緦?shí)驗(yàn)步驟;】（1）運(yùn)行PC中的MicrosoftVisualC++6.0程序，（2）點(diǎn)擊“文件”→“新建”→對(duì)話窗口中“文件”→“c++SourceFile”→在“文件名”中輸入“X1.cpp”→在“位置”中選擇儲(chǔ)存路徑為“桌面”→“確定”，(3)輸入程序代碼，程序代碼如下:#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<iostream.h>#include<conio.h>#include<string.h>//包含庫(kù)函數(shù)strcpy的頭文件#defineNULL0structstudent//定義學(xué)生信息{charname[8];intsex;//0女:1:男intage;};typedefstructstudentSTD;intcreate(STD*m);//創(chuàng)建順序表intcalc(STD*m,STD*n,STD*r,float&Fage,float&Mage);//計(jì)算、數(shù)據(jù)處理voidprint(STD*m);constintMAX=100;//定義人數(shù)voidmain(){STDA[MAX];STDB[MAX];STDC[MAX];floatage1=0,age2=0;//age1男age2女create(A);printf("學(xué)生總表A記錄如下:\n");print(A);calc(A,B,C,age1,age2);printf("女生名冊(cè)B記錄如下:\n");print(B);printf("男生名冊(cè)C記錄如下:\n");print(C);}intcreate(STD*m){ intn; printf("請(qǐng)輸入班級(jí)總?cè)藬?shù):\n"); scanf("%d",&n); m[0].age=n;//置順序表長(zhǎng)度 printf("請(qǐng)輸入學(xué)生信息：\n");for(inti=1;i<=n;i++){ printf("姓名:"); scanf("%s",&m[i].name); printf("性別0女1男:"); scanf("%d",&m[i].sex); printf("年齡:"); scanf("%d",&m[i].age); printf("\n");} return1;}intcalc(STD*m,STD*n,STD*r,float&Fage,float&Mage){inti,j=1,k=1;n[0].age=r[0].age=0;for(i=1;i<=m[0].age;i++){if(m[i].sex==0){strcpy(n[j].name,m[i].name);n[j].sex=m[i].sex;n[j].age=m[i].age;n[0].age++;Mage+=m[i].age;j++;}else{strcpy(r[k].name,m[i].name); r[k].sex=m[i].sex;r[k].age=m[i].age;r[0].age++;Fage+=m[i].age;k++;}}Mage=Mage/n[0].age;Fage=Fage/r[0].age;cout<<"女生的平均年齡是："<<Mage<<"男生的平均年齡是："<<Fage<<endl;return1;}voidprint(STD*m){for(inti=1;i<=m[0].age;i++){ printf("姓名:%3s,性別(0女1男):%d,年齡:%d\n",m[i].name,m[i].sex,m[i].age); }} 程序運(yùn)行結(jié)果如下:實(shí)驗(yàn)結(jié)束。實(shí)驗(yàn)結(jié)論：線性表采用鏈?zhǔn)酱鎯?chǔ)（鏈表）時(shí)：以結(jié)構(gòu)變量存儲(chǔ)結(jié)點(diǎn)，動(dòng)態(tài)生成結(jié)點(diǎn)，以指針鏈接結(jié)點(diǎn)，能有效利用存儲(chǔ)空間，插入刪除方便，但不能隨機(jī)訪問(wèn).單向鏈表可從某結(jié)點(diǎn)訪問(wèn)到后繼結(jié)點(diǎn)。單向鏈表操作的關(guān)鍵步驟：建立鏈表的頭插法：指針變量p開(kāi)辟單元，生成結(jié)點(diǎn)，指針變量q始終指向頭結(jié)點(diǎn)，操作為：p->next=q->next;q->next=p;尾插法：指針變量q始終指向尾結(jié)點(diǎn)，p指針開(kāi)辟單元，生成結(jié)點(diǎn)：q->next=p;q=p;?插入：p所指向結(jié)點(diǎn)的后面插入新結(jié)點(diǎn)s所指結(jié)點(diǎn)s->next=p->next;p->next=s;?刪除：p，q指向相鄰結(jié)點(diǎn)，q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的后繼，刪除q所指結(jié)點(diǎn)，p->next=q->next;?遍歷：p=p->next;實(shí)驗(yàn)名稱：實(shí)驗(yàn)二棧、列隊(duì)、遞歸程序設(shè)計(jì)2.1棧和隊(duì)列的基本操作【問(wèn)題描述】編寫(xiě)一個(gè)算法，輸出指定棧中的棧底元素，并使得原棧中的元素倒置。【基本要求】（1）正確理解棧的先進(jìn)后出的操作特點(diǎn),建立初始棧，通過(guò)相關(guān)操作顯示棧底元素。（2）程序中要體現(xiàn)出建棧過(guò)程和取出棧底元素后恢復(fù)棧的入棧過(guò)程，按堆棧的操作規(guī)則打印結(jié)果棧中的元素?！緦?shí)驗(yàn)步驟;】運(yùn)行PC中的MicrosoftVisualC++6.0程序，點(diǎn)擊“文件”→“新建”→對(duì)話窗口中“文件”→“c++SourceFile”→在“文件名”中輸入“X1.cpp”→在“位置”中選擇儲(chǔ)存路徑為“桌面”→“確定”，輸入程序代碼，程序代碼如下:#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstruct{ ElemTypedata[MaxSize]; inttop; //棧頂指針}SeqStack;//定義棧typedefstruct{ ElemTypeelem[MaxSize]; intfront,rear; //隊(duì)首和隊(duì)尾指針}SqQueue;//定義隊(duì)列//---初始棧函數(shù)voidInitStack(SeqStack*&s){ s=(SeqStack*)malloc(sizeof(SeqStack)); s->top=-1;}//----進(jìn)棧函數(shù)intPush(SeqStack*&s,ElemTypee){ if(s->top==MaxSize-1) return0; s->top++; s->data[s->top]=e; return1;}//---顯示棧函數(shù)voidDispStack(SeqStack*s){ inti; for(i=s->top;i>=0;i--) printf("%c",s->data[i]); printf("\n");}//---顯示棧底元素voidDispBottomStack(SeqStack*s){ printf("%c",s->data[0]);//先進(jìn)后出,棧底元素為第一個(gè)元素,即data[0] printf("\n");}//---判空棧函數(shù)intStackEmpty(SeqStack*s){ return(s->top==-1);}//---出棧函數(shù)intPop(SeqStack*&s,ElemType&e){ if(s->top==-1) return0; e=s->data[s->top]; s->top--; return1;}//---初始隊(duì)列函數(shù)voidInitQueue(SqQueue*&q){ q=(SqQueue*)malloc(sizeof(SqQueue)); q->front=q->rear=0;}//---入隊(duì)列函數(shù)intInQueue(SqQueue*&q,ElemTypee){ if((q->rear+1)%MaxSize==q->front)//隊(duì)滿 return0; q->rear=(q->rear+1)%MaxSize; q->elem[q->rear]=e; return1;}//---出隊(duì)列函數(shù)intOutQueue(SqQueue*&q,ElemType&e){ if(q->front==q->rear)//隊(duì)空 return0; q->front=(q->front+1)%MaxSize; e=q->elem[q->front]; return1;}//---判空隊(duì)列函數(shù)intQueueEmpty(SqQueue*q){ return(q->front==q->rear);}//-----主程序voidmain(){ ElemTypee; SeqStack*s; printf("(1)初始化棧s\n"); InitStack(s); printf("(2)棧為%s\n",(StackEmpty(s)?"空":"非空")); printf("(3)依次進(jìn)棧元素a,b,c,d,e\n"); Push(s,'a');//入棧元素1 Push(s,'b');//入棧元素2 Push(s,'c');//入棧元素3 Push(s,'d');//入棧元素4 Push(s,'e');//入棧元素5 printf("(4)棧為%s\n",(StackEmpty(s)?"空":"非空")); printf("(5)從棧頂?shù)綏５自?");DispStack(s); printf("(6)棧底元素為:");DispBottomStack(s); printf("(7)出棧/入隊(duì)列序列:"); SqQueue*q; InitQueue(q); while(!StackEmpty(s)) { Pop(s,e);//出棧 printf("%c",e); InQueue(q,e);//入隊(duì) } printf("\n"); printf("(8)棧為%s,",(StackEmpty(s)?"空":"非空")); printf("隊(duì)列為%s\n",(QueueEmpty(q)?"空":"非空")); printf("(9)出隊(duì)列/入棧序列:"); while(!QueueEmpty(q)) { OutQueue(q,e);//出隊(duì) Push(s,e);//入棧 printf("%c",e); } printf("\n"); printf("(10)棧為%s,",(StackEmpty(s)?"空":"非空")); printf("隊(duì)列為%s\n",(QueueEmpty(q)?"空":"非空")); free(q);//釋放隊(duì)列 printf("(11)從棧頂?shù)綏５自?");DispStack(s); free(s);//釋放棧 }程序運(yùn)行結(jié)果如下:2.2遞歸程序設(shè)計(jì)【問(wèn)題描述】給定一個(gè)5位的十進(jìn)制正整數(shù)，用遞歸法分別編制程序：（1）要求從低位到高位逐次輸出各位數(shù)字。（2）要求從高位到低位逐次輸出各位數(shù)字?！净疽蟆勘容^題中兩種不同要求的遞歸程序設(shè)計(jì)和執(zhí)行過(guò)程差別。正確理解遞歸程序的執(zhí)行過(guò)程。顯示計(jì)算結(jié)果?！緦?shí)驗(yàn)步驟】（1）運(yùn)行PC中的MicrosoftVisualC++6.0程序，點(diǎn)擊“文件”→“新建”→對(duì)話窗口中“文件”→“c++SourceFile”→在“文件名”中（2）輸入“X1.cpp”→在“位置”中選擇儲(chǔ)存路徑為“桌面”→“確定”，(3)輸入程序代碼程序代碼如下:#include<stdio.h>#include<math.h>voidout(intn,inti)//從高位到低位輸出函數(shù){intx,y;y=int(pow(10,i));if(n!=0){x=n/y;n=n-x*y;printf("%d",x);}elseprintf("0");i--;if(i>=0)out(n,i);}voidout1(intm,intj)//從低位到高位輸出函數(shù){intx,z;if(m!=0){x=int(m/10);z=m-x*10;m=x;printf("%d",z);}elseprintf("0");j--;if(j>=0)out1(m,j);}voidmain(){intm,n,o,x,i,j;printf("輸入需要排列的數(shù)字:\n");scanf("%d",&o);m=n=o;x=n;i=-1;while(x!=0){x=x/10;i++;}//求出i為十進(jìn)制正整數(shù)位數(shù)j=i;printf("\n");printf("從高位到低位逐次輸出各位數(shù)字:");out(n,i);printf("\n");printf("從低位到高位逐次輸出各位數(shù)字:");out1(m,j);printf("\n");} 程序運(yùn)行結(jié)果如下:實(shí)驗(yàn)結(jié)論:棧和隊(duì)列是運(yùn)算受限制的線性表 棧：后進(jìn)先出（LIFO） 例:進(jìn)棧b,c,d,e,f出?？赡転閒,e,d,c,b;b,c,d,e,f;c,b,e,d,f???但不可能是e,d,f,b,c 隊(duì)列：先進(jìn)先出（FIFO） 例：入隊(duì)1,2,3,4,5出隊(duì)1,2,3,4,5實(shí)驗(yàn)名稱：實(shí)驗(yàn)三二叉樹(shù)3.1二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)【問(wèn)題描述】設(shè)一棵完全二叉樹(shù)用順序存儲(chǔ)方法存儲(chǔ)于數(shù)組tree中，編寫(xiě)程序：根據(jù)數(shù)組tree，建立與該二叉樹(shù)對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)該二叉樹(shù)采用中序遍歷法顯示遍歷結(jié)果?！净疽蟆吭谥骱瘮?shù)中，通過(guò)鍵盤輸入建立設(shè)定的完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)子函數(shù)，其功能為將順序結(jié)構(gòu)的二叉樹(shù)轉(zhuǎn)化為鏈?zhǔn)浇Y(jié)構(gòu)。設(shè)計(jì)子函數(shù)，其功能為對(duì)給定二叉樹(shù)進(jìn)行中序遍歷，顯示遍歷結(jié)果。通過(guò)實(shí)例判斷算法和相應(yīng)程序的正確性?！緦?shí)驗(yàn)步驟】運(yùn)行PC中的MicrosoftVisualC++6.0程序，點(diǎn)擊“文件”→“新建”→對(duì)話窗口中“文件”→“c++SourceFile”→在“文件名”中輸入“X1.cpp”→在“位置”中選擇儲(chǔ)存路徑為“桌面”→“確定”，輸入程序代碼，程序代碼如下:#include<stdio.h>#include<malloc.h>#include<string.h>#include<stdlib.h>#include<memory.h>#defineMaxSize10typedefstructnode{ chardata; structnode*left,*right;}NODE;voidCreab(char*tree,intn,inti,NODE*p);voidInorder(NODE*p);voidmain(){ NODE*p; chartree[MaxSize]; intn=1; inti=1; printf("請(qǐng)輸入完全二叉數(shù)的節(jié)點(diǎn)值（連續(xù)輸入字符，以回車結(jié)束輸入。）:"); while((tree[n]=getchar())!='\n')n++; tree[n]='\n'; p=NULL; Creab(tree,n,i,p); Inorder(p);}voidCreab(char*tree,intn,inti,NODE*p){ if(i>=n)p=NULL; else { p=(NODE*)malloc(sizeof(NODE)); p->data=tree[i]; printf("%c",p->data); Creab(tree,n,2*i,p->left); Creab(tree,n,2*i+1,p->right); }}/*中序遍歷樹(shù)*/voidInorder(NODE*p){ if(p!=NULL){ Inorder(p->left); printf("%c",p->data); Inorder(p->right);}}程序運(yùn)行結(jié)果如下:3.1二叉樹(shù)的遍歷【問(wèn)題描述】設(shè)一棵二叉樹(shù)采用鏈?zhǔn)椒绞酱鎯?chǔ)，編寫(xiě)一個(gè)前序遍歷該二叉樹(shù)的非遞歸算法。【基本要求】掌握前序遍歷二叉樹(shù)的步驟，針對(duì)任意一棵二叉樹(shù)能人工完成對(duì)二叉樹(shù)的前序遍歷。能掌握棧的工作特點(diǎn)，并能正確應(yīng)用這一特點(diǎn)實(shí)現(xiàn)對(duì)二叉樹(shù)的遍歷?！緦?shí)驗(yàn)步驟】（1）運(yùn)行PC中的MicrosoftVisualC++6.0程序，點(diǎn)擊“文件”→“新建”→對(duì)話窗口中“文件”→“c++SourceFile”→在“文件名”中（2）輸入“X1.cpp”→在“位置”中選擇儲(chǔ)存路徑為“桌面”→“確定”，(3)輸入程序代碼程序代碼如下:voidFirstOrderAccess1(BTree*header)

{

BTree*stack[MAX_NODE];

BTree*p;

inttop;

top=0;

p=header;

do

{

while(p!=NULL)

{

printf("BTree[%d]=%c“t",p->order,p->data);

if(p->rchild!=NULL)

stack[++top]=p->rchild;

p=p->lchild;

}

if(top!=0)

p=stack[top--];

}while((top>0)||(p!=NULL));

}實(shí)驗(yàn)名稱：實(shí)驗(yàn)四圖的存儲(chǔ)方式和應(yīng)用4.1建立圖的鄰接矩陣【問(wèn)題描述】根據(jù)圖中頂點(diǎn)和邊的信息編制程序建立圖的鄰接矩陣?！净疽蟆砍绦蛞幸欢ǖ耐ㄓ眯?。直接根據(jù)圖中每個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)的關(guān)聯(lián)情況輸入相關(guān)信息，程序能自動(dòng)形成鄰接矩陣【測(cè)試用例】【實(shí)現(xiàn)提示】對(duì)圖的頂點(diǎn)編號(hào)。在上圖中，以頂點(diǎn)1為例，因?yàn)轫旤c(diǎn)2,3,4與頂點(diǎn)1關(guān)聯(lián)，可以輸入信息1234，然后設(shè)法求出與頂點(diǎn)1關(guān)聯(lián)的結(jié)點(diǎn)，從而求得鄰接矩陣中相應(yīng)與頂點(diǎn)1的矩陣元素。2211553344實(shí)驗(yàn)圖4-1設(shè)計(jì)程序代碼如下:#include<stdio.h>#defineMaxVertexNum5#defineMaxEdgeNum20#defineMaxValue1000typedefintVertexType;typedefVertexTypevexlist[MaxVertexNum];typedefintadjmatrix[MaxVertexNum][MaxVertexNum];voidCreatel(vexlistGv,adjmatrixGA,intn,inte){ inti,j,k,w; printf("輸入%d個(gè)頂點(diǎn)數(shù)據(jù)\n",n); for(i=0;i<n;i++)scanf("%d",&Gv[i]); for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i==j)GA[i][j]=0; elseGA[i][j]=MaxValue; } Printf（“輸入一條邊的兩端點(diǎn)序號(hào)i和j及邊上的權(quán)w\n”）; printf("輸入%d條無(wú)向帶權(quán)邊\n",e); for(k=1;k<=e;k++){ scanf("%d%d%d",&i,&j,&w); GA[i][j]=GA[j][i]=w; }}voidmain(){ vexlistvl; adjmatrixa; Createl(vl,a,5,8);}實(shí)驗(yàn)名稱：實(shí)驗(yàn)五查找5.1折半查找【問(wèn)題描述】某班學(xué)生成績(jī)信息表中，每個(gè)學(xué)生的記錄已按平均成績(jī)由高到低排好序，后來(lái)發(fā)現(xiàn)某個(gè)學(xué)生的成績(jī)沒(méi)有登記到信息表中，使用折半查找法把該同學(xué)的記錄插入到信息表中，使信息表中的記錄仍按平均成績(jī)有序。【基本信息】建立現(xiàn)有學(xué)生信息表，平均成績(jī)已有序。輸入插入學(xué)生的記錄信息。用折半查找找到插入位置，并插入記錄?！緶y(cè)試數(shù)據(jù)】自行設(shè)計(jì)?！緦?shí)驗(yàn)提示】用結(jié)構(gòu)數(shù)組存儲(chǔ)成績(jī)信息表。對(duì)記錄中的平均成績(jī)進(jìn)行折半查找。5.2二叉排序樹(shù)的建立【問(wèn)題描述】參閱相關(guān)資料，閱讀建立二叉排序樹(shù)的程序。【基本要求】掌握建立二叉排序樹(shù)的原理和方法。能跟蹤程序人工建立二叉排序樹(shù)。實(shí)驗(yàn)報(bào)告內(nèi)容：實(shí)驗(yàn)5.1折半查找設(shè)計(jì)程序代碼如下:#include<stdio.h>#include<string.h>#defineN5structstudent{ charname[10]; floatavg;}voidinsort(structstudents[],intn){ intlow,hight,mid,k; chary[10]; floatx; low=1; hight=n; strcpy(y,s[0].name); x=s[0].avg; while(low<=hight) { mid=(low+hight)/2; if(x>s[mid].avg) hight=mid-1; else low=mid+1; } for(k=0;k<low-1;k++){ strcpy(s[k].name,s[k+1].name); s[k].avg=s[k+1].avg; } printf("%d",low); strcpy(s[low-1].name,y); s[low-1].avg=x;}voidmain(){ Structstudenta[N]={{"caozh",96},{"cheng",95},{"zhao",93},{"wang",92},{"chen",91}}; structstudentstu[N]; inti; for(i=0;i<N;i++) stu[i+1]=a[i]; printf("初始%d位同學(xué)的信息表\n",MAX); printf("排名姓名平均分?jǐn)?shù)\n"); for(i=1;i<=N;i++) printf("%d:%6s%3.2f\n",i,stu[i].name,stu[i].avg); printf("\n"); printf("\n"); printf("請(qǐng)輸入學(xué)生的姓名："); scanf("%s",stu[0].name); printf("\n"); printf("請(qǐng)輸入平均成績(jī)："); scanf("%f",&stu[0].avg); printf("\n"); insort(stu,N); printf("折半排序后同學(xué)的信息表\n",MAX); printf("排名姓名平均分?jǐn)?shù)\n"); for(i=0;i<=N;i++) { printf("%d:%6s%3.2f\n",i+1,stu[i].name,stu[i].avg); } printf("\n");}程序運(yùn)行結(jié)果如下:實(shí)驗(yàn)5.2二叉排序樹(shù)的建立設(shè)計(jì)程序代碼如下:#include<stdio.h>#include<stdlib.h>#defineMAX5typedefstructBnode{ intkey; structBnode*left; structBnode*right;}Bnode;Bnode*btInsert(intx,Bnode*root);voidInorder(Bnode*root);voidmain(){ inti; inta[MAX]={60,40,70,20,80}; Bnode*root=NULL; printf("按關(guān)鍵字序列建立二叉排序樹(shù)\n"); for(i=0;i<MAX;i++)printf("%d",a[i]); printf("\n"); for(i=0;i<MAX;i++) root=btInsert(a[i],root); printf("中序遍歷的二叉排序樹(shù)\n"); Inorder(root); printf("\n");}Bnode*btInsert(intx,Bnode*root){ Bnode*p,*q; intflag=0; p=(Bnode*)malloc(sizeof(Bnode)); p->key=x; p->right=p->left=NULL; if(root==NULL) { root=p; returnp; } q=root; while(flag==0) { if(q->key>x) { if(q->left!=NULL) q=q->left; else { q->left=p; flag=1; } } else { if(q->right!=NULL) q=q->right; else { q->right=p; flag=1; } } } returnroot;}voidInorder(Bnode*root){if(root!=NULL){Inorder(root->left);printf("%d",root->key);Inorder(root->right);}}程序運(yùn)行結(jié)果如下:實(shí)驗(yàn)名稱：實(shí)驗(yàn)六排序6.1泡沫法排序的改進(jìn)算法【問(wèn)題描述】某班學(xué)生成績(jī)信息表中每個(gè)學(xué)生的記錄包括各門功課的成績(jī)和平均成績(jī)，以及按平均成績(jī)的排名等信息，要求從鍵盤輸入每個(gè)學(xué)生各門功課的成績(jī)，計(jì)算出平均成績(jī)，按平均成績(jī)由高到低對(duì)信息的記錄重新排序，并定出每位同學(xué)的名次，打印排序后的信息表?！净疽蟆拷W(xué)生成績(jī)信息表，計(jì)算平均成績(jī)。用泡沫法對(duì)平均成績(jī)排序，程序中要求一旦序列被排好序就結(jié)束相應(yīng)排序操作。【測(cè)試數(shù)據(jù)】自行設(shè)計(jì)【實(shí)驗(yàn)提示】用結(jié)構(gòu)數(shù)組存放學(xué)生成績(jī)信息表。在某趟泡沫中沒(méi)有發(fā)生元素間的交換則說(shuō)明已排好序6.2堆排序【問(wèn)題描述】閱讀篩選和建堆的程序，針對(duì)某一個(gè)待排序的序列，通過(guò)人工跟蹤程序的執(zhí)行，完成排序的全過(guò)程【基本要求】掌握建堆、篩選的基本原理和算法步驟。寫(xiě)出主函數(shù)，試運(yùn)行堆排序的程序。掌握堆排序的算法程序，能針對(duì)實(shí)例按步驟人工完成建堆和排序的過(guò)程?！緶y(cè)試數(shù)據(jù)】自行設(shè)計(jì)?！緦?shí)驗(yàn)提示】篩選是建堆的基本算法。把要排序序列看成一棵完全二叉樹(shù)，用循環(huán)方式從最后一個(gè)非葉結(jié)（設(shè)序號(hào)為k）開(kāi)始，逐次對(duì)序號(hào)為k,k-1,…的結(jié)點(diǎn)，直至根結(jié)點(diǎn)調(diào)用篩選算法，完成建堆。不斷通過(guò)堆頂元素與堆中最后一個(gè)元素的交換并篩選，完成排序。實(shí)驗(yàn)報(bào)告內(nèi)容：實(shí)驗(yàn)6.1冒泡法排序的改進(jìn)設(shè)計(jì)程序代碼如下:#include<stdio.h>#include<string.h>#defineMAX3structstudent{ charname[10]; floatcs; floatms; floates; floatavg;};voidsort(structstudents[],intn);voidsort(structstudents[],intn){ structstudenttemp; inti,j; for(i=1;i<n;i++)for(j=0;j<n-i;j++) if(s[j].avg<s[j+1].avg){ temp=s[j]; s[j]=s[j+1]; s[j+1]=temp; }}voidmain(){ structstudentstu[MAX]; inti; printf("請(qǐng)輸入%d位同學(xué)的姓名和各科成績(jī)\n",MAX); for(i=0;i<MAX;i++) { printf("請(qǐng)輸入第%d位學(xué)生的姓名:",i+1); scanf("%s",stu[i].name); printf("\n"); printf("語(yǔ)文分?jǐn)?shù):"); scanf("%f",&stu[i].cs); printf("\n"); printf("數(shù)學(xué)分?jǐn)?shù):"); scanf("%f",&stu[i].ms); printf("\n"); printf("英語(yǔ)分?jǐn)?shù):"); scanf("%f",&stu[i].es); printf("\n"); stu[i].avg=(stu[i].cs+stu[i].ms+stu[i].es)/3; } sort(stu,MAX); printf("排名姓名語(yǔ)文數(shù)學(xué)外語(yǔ)平均分?jǐn)?shù)\n"); for(i=0;i<MAX;i++) { printf("%d:%6s%3.2f%3.2f%3.2f%3.2f\n",i+1,stu[i].name,stu[i].cs,stu[i].ms,stu[i].es,stu[i].avg); }}程序運(yùn)行結(jié)果如下:實(shí)驗(yàn)6.2堆排序設(shè)計(jì)程序代碼如下:#include<stdio.h>#defineN8structNODE{ intdate;};voidheapshift(structNODEa[],inti,intn){ structNODEtemp; intj; temp=a[i]; j=2*i; while(j<n) { if(j+1<n&&a[j].date>a[j+1].date) j++; if(temp.date>a[j].date) { a[i]=a[j]; i=j; j=2*i; } else break; } a[i]=temp;}voidheapsort(structNODEa[],intn){ inti; structNODEtemp; for(i=n/2;i>=1;i--) heapshift(a,i,n); for(i=n;i>1;i--) { temp=a[1]; a[1]=a[i]; a[i]=temp; heapshift(a,1,i-1); }}voidmain(){ structNODEb[N]={40,80,65,100,14,30,55,50}; structNODEa[N]; inti; printf("初始數(shù)據(jù)序列："); for(i=0;i<N;i++){ a[i+1].date=b[i].date; } for(i=1;i<=N;i++){ printf("%d",a[i].date); } printf("\n"); printf("\n"); heapsort(a,N);printf("堆排序后的數(shù)據(jù)序列："); for(i=1;i<=N;i++){ printf("%d",a[i].date); } printf("\n");}程序運(yùn)行結(jié)果如下:國(guó)家開(kāi)放大學(xué)(中央廣播電視大學(xué))《國(guó)家開(kāi)放大學(xué)學(xué)習(xí)指南》課程教學(xué)大綱第一部分大綱說(shuō)明一、課程性質(zhì)與任務(wù)《國(guó)家開(kāi)放大學(xué)學(xué)習(xí)指南》是國(guó)家開(kāi)放大學(xué)（中央廣播電視大學(xué)）在本、專、一村一所有專業(yè)的一年級(jí)第一學(xué)期開(kāi)設(shè)的、起到基礎(chǔ)導(dǎo)學(xué)作用的一門統(tǒng)設(shè)必修課。課程任務(wù)是：以完成學(xué)習(xí)任務(wù)的過(guò)程為導(dǎo)向，從學(xué)習(xí)者如何完成國(guó)家開(kāi)放大學(xué)規(guī)定的專業(yè)學(xué)習(xí)任務(wù)的角度，讓學(xué)習(xí)者學(xué)會(huì)如何完成一門課程的學(xué)習(xí)、一個(gè)專業(yè)的學(xué)習(xí)，同時(shí)描述國(guó)家開(kāi)放大學(xué)基本的學(xué)習(xí)方式，說(shuō)明國(guó)家開(kāi)放大學(xué)的學(xué)習(xí)環(huán)境，解釋國(guó)家開(kāi)放大學(xué)學(xué)習(xí)平臺(tái)上基本術(shù)語(yǔ)的涵義，使學(xué)生能使用學(xué)習(xí)平臺(tái)的基本工具輔助完成學(xué)習(xí)活動(dòng)，并且了解國(guó)家開(kāi)放大學(xué)學(xué)生相關(guān)事務(wù)與管理規(guī)定。使學(xué)生初步具備利用現(xiàn)代遠(yuǎn)程技術(shù)在國(guó)家開(kāi)放大學(xué)進(jìn)行學(xué)習(xí)的能力。二、先修課要求無(wú)三、課程的教學(xué)要求理解國(guó)家開(kāi)放大學(xué)課程、專業(yè)平臺(tái)，熟練基本的遠(yuǎn)程技術(shù)學(xué)習(xí)操作技能，掌握遠(yuǎn)程學(xué)習(xí)的學(xué)習(xí)方法，較好利用國(guó)家開(kāi)放大學(xué)資源和學(xué)習(xí)支持服務(wù)。四、課程的教學(xué)方法和教學(xué)形式建議1.本課程的特點(diǎn)是：網(wǎng)絡(luò)課程完善、課程內(nèi)容新、課程形式豐富、實(shí)踐性強(qiáng)、涉及面廣，因此建議通過(guò)網(wǎng)絡(luò)，在計(jì)算機(jī)教室（或計(jì)算機(jī)多媒體教室）進(jìn)行授課、答疑和討論。講授與實(shí)踐統(tǒng)一考慮。2.為加強(qiáng)和落實(shí)動(dòng)手能力的培養(yǎng)，應(yīng)保證上機(jī)機(jī)時(shí)不少于本教學(xué)大綱規(guī)定的學(xué)時(shí)。3.對(duì)于重要概念、關(guān)鍵技能和方法等問(wèn)題可輔以網(wǎng)上答疑討論的形式。五、教學(xué)要求的層次課程的教學(xué)要求大體上分為三個(gè)層次：了解、理解和掌握。了解：能正確判別有關(guān)概念和方法。理解：能正確表達(dá)有關(guān)概念和方法的含義。掌握：在理解的基礎(chǔ)上加以靈活應(yīng)用。第二部分教學(xué)媒體與教學(xué)過(guò)程建議一、課程教學(xué)總學(xué)時(shí)數(shù)、學(xué)分?jǐn)?shù)課程教學(xué)總學(xué)時(shí)數(shù)為18學(xué)時(shí)，1學(xué)分。其中網(wǎng)絡(luò)課程為13學(xué)時(shí)，課堂練習(xí)和實(shí)驗(yàn)為5學(xué)時(shí)。二、課程呈現(xiàn)方式課程以網(wǎng)絡(luò)課程為主，這是學(xué)生學(xué)習(xí)的主要媒體形式，因此課程呈現(xiàn)方式以視頻、動(dòng)畫(huà)為主，配以必要的文字說(shuō)明，每段視頻、動(dòng)畫(huà)不超過(guò)8分鐘。視頻以學(xué)習(xí)發(fā)生的場(chǎng)景為主，也可以是學(xué)生訪談，體現(xiàn)一定交互性。課程內(nèi)容可以在手機(jī)、PAD、計(jì)算機(jī)、電視等多種終端上呈現(xiàn)。根據(jù)課程呈現(xiàn)方式，課程要做到只選取完成國(guó)家開(kāi)放大學(xué)學(xué)習(xí)的必備知識(shí)，擯棄過(guò)多的理論知識(shí)，盡可能簡(jiǎn)捷。實(shí)用、方便、模塊化設(shè)計(jì)，基于問(wèn)題、案例形式呈現(xiàn)。概念清晰、條理分明、深入淺出、便于自學(xué)。在內(nèi)容上要緊密圍繞培養(yǎng)目標(biāo)，突出重點(diǎn)、兼顧一般，反映當(dāng)代最新技術(shù)及應(yīng)用。三、主要教學(xué)媒體的使用與學(xué)時(shí)分配章節(jié)序號(hào)教學(xué)內(nèi)容網(wǎng)絡(luò)課程學(xué)時(shí)課堂練習(xí)和實(shí)驗(yàn)學(xué)時(shí)1認(rèn)識(shí)國(guó)家開(kāi)放大學(xué)312完成專業(yè)學(xué)習(xí)313完成課程學(xué)習(xí)314網(wǎng)上學(xué)習(xí)操作技能215學(xué)生事務(wù)服務(wù)21合計(jì)135四、考核本課程采用上機(jī)操作的考核方式，100%國(guó)家開(kāi)放大學(xué)考核。開(kāi)放教育的學(xué)生應(yīng)嚴(yán)格執(zhí)行該課程的有關(guān)考核文件。第三部分教學(xué)內(nèi)容和教學(xué)要求1、學(xué)習(xí)活動(dòng)一：認(rèn)識(shí)國(guó)家開(kāi)放大學(xué)（3學(xué)時(shí)）【教學(xué)內(nèi)容】：任務(wù)一走進(jìn)國(guó)家開(kāi)放大學(xué)（一）基本介紹介紹國(guó)開(kāi)的歷史，辦學(xué)模式，提供的學(xué)科門類等。（二）案例導(dǎo)入由國(guó)家開(kāi)放大學(xué)的學(xué)生講述參加國(guó)家開(kāi)放大學(xué)學(xué)習(xí)的體會(huì)與收獲（由學(xué)生講，把國(guó)家開(kāi)放大學(xué)學(xué)習(xí)的特點(diǎn)和優(yōu)勢(shì)講出來(lái)，包括學(xué)習(xí)時(shí)間、學(xué)習(xí)方式等等。）（三）國(guó)家開(kāi)放大學(xué)的學(xué)習(xí)環(huán)境1.在線學(xué)習(xí)平臺(tái)；2.教師（教師群體與角色）；3.學(xué)習(xí)者（個(gè)人角色與學(xué)習(xí)小組創(chuàng)建）；4.學(xué)習(xí)資源（文字教材、錄像、網(wǎng)絡(luò)課程、流媒體資源、全媒體數(shù)字教材、小課件等）；5.學(xué)習(xí)活動(dòng)（網(wǎng)上教學(xué)活動(dòng)、論壇討論）；6.支持服務(wù)（獲得途徑：面對(duì)面的服務(wù)、電話、短信、電子郵件、網(wǎng)上論壇、在線即時(shí)答疑系統(tǒng)）；（四）拓展內(nèi)容報(bào)名渠道，獲得學(xué)習(xí)資源，買書(shū)，有困難時(shí)候如何尋求幫助。任務(wù)二如何有效學(xué)習(xí)（一）學(xué)習(xí)策略1.紙質(zhì)學(xué)習(xí)和電子學(xué)習(xí)的認(rèn)知策略；2.制定計(jì)劃、自我監(jiān)控與調(diào)節(jié)；3.學(xué)習(xí)時(shí)間管理、學(xué)習(xí)資源與環(huán)境利用、互動(dòng)空間與手段（QQ群、課程論壇、學(xué)習(xí)空間）、學(xué)業(yè)求助策略。（二）學(xué)習(xí)方式1.自學(xué)（自己閱讀學(xué)習(xí)資源，做測(cè)試與練習(xí)）；2.聽(tīng)講（聽(tīng)看講課視頻或音頻、面授）；3.體驗(yàn)；4.探究；5.問(wèn)題解決；任務(wù)三學(xué)前準(zhǔn)備了解并完成一些學(xué)前準(zhǔn)備工作，從學(xué)習(xí)方法、知識(shí)儲(chǔ)備、計(jì)算機(jī)技能、學(xué)習(xí)環(huán)境等多方面了解自身的情況，為日后學(xué)習(xí)奠定基礎(chǔ)?！窘虒W(xué)要求】：了解：國(guó)家開(kāi)放大學(xué)的基本介紹，教學(xué)環(huán)境；掌握：國(guó)家開(kāi)放大