数据结构课程设计航班信息的查询与检索
目录
第1章概述 (1)
第2章设计要求与分析 (2)
2.1设计要求 (2)
2.2设计分析 (2)
2.2.1定义数据类型 (2)
2.2.2实现排序的个函数说明 (3)
第3章算法实现 (4)
3.1 一趟分配算法 (4)
3.2 一趟收集算法 (4)
3.3 链式基数排序算法 (11)
3.4 二分查找的函数定义 (12)
第4章程序代码 (12)
第5章运行与测试 (20)
第6章实验反思 (23)
参考文献 (23)
第1章概述
排序和查找是在数据信息处理中使用频度极高的操作。为了加快查找的速度，需要先对数据记录按关键字排序。当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、
时间、价格及机型等信息。在这个飞机航班数据的信息模型中，航班号是关键字，而且是具有结构特点的一类关键字。因为航班号是字母数字混变的，例如CZ3869，这种记录集合是一个适合与多关键字排序的例子。
第2章设计要求与分析
2.1设计要求
该设计要求对飞机航班信息进行排序和查找.可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。
对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他词关键字的查找可采用最简单的顺序查找方法进行，因为他们用的较少。
每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表如下表所示：
其中k0和k14位为航班表号，这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串型即可。
2.2设计分析
2.2.1定义数据类型
根据设计要求，我们知道设计中所用到的数据记录只有航班信息，因此要定义行管的数据类型：
Typedef struct{
Char start[7];
Char end[7];
Char sche[12];
Char time1[5];
Char time2[5];
Char model[4];
Int price;
}InfoType;
Typedef struct{
KeyType keys[keylen];
InfoType others;
Int next;
}SLNode;
Typedef struct{
SLNode s1[MaxSpace];
Int keylen;
Int length;
}SLList;
为了进行基数排列，需要定义在分配和手机操作使用到的指针数组：
Typedef int ArrType_n[10];
Typedef int ArrType_.c[26];
2.2.2实现排序的个函数说明
（1）一趟分配函数：
Void Distribute(SLNode *s1,int I,ArrType f,ArrType e);
//本算法是按关键字keys[i]建立RADIX个子集，是同一个子集中记录的keys[i]相同，//f[0..RADIX]和e[0..RADIX]分别指向各自表中的第一个和最后一个记录
（2）一趟搜集函数：
Void Collect(SLNode *s1,int i,ArrType f,ArrType e);
//本算法是按关键字keys[i]从小到大将[0..RADIX]所指的各子表一次连接成一个链表
（3）链式基数排序函数：
Void RadixSort(SLList &L);
//本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两端实现
（4）二分查找函数：
Int BinSerach(SLList L,KeyType key[]);
//L为待查找的表，key[]为待查找的关键字，按二分查找的思想实现查找
（5）主控函数：
Void main()
{
初始化；
数据输入；
排序处理；
接受查找要求及查找关键字；
查找处理；
输出查找结果；
}
第3章算法实现
3.1 一趟分配算法
Void Distribute(SLNode *s1,int I,ArrType f,ArrType e) {
Int j,p;
For(j=0;j {//分子表初始化为空表 F[j]=0; E[j]=0; } For(p=s1[0].next;p;p=s1[p].next) { J=s1[p].keys[i]%48; If(!f[j]) F[j]=p; Else S1[e[j]].next=p; E[j]=p; } } 3.2 一趟收集算法 Void Colect(SLNode *s1,int I,ARRType f,ArrType e) { Int j,t; For(j=0;!f[j];j++); S1[0].next=f[j];t=e[j]; While(j { For(j=j+1;j If(f[j]){s1[t].next=f[j];t=e[j];} } S1[t].next=0; } //主函数程序 #include #include #define MaxSpace 100 #define keylen 6 #define RADIX_n 10 #define RADIX_c 26 #define SHOW_MSG_ERROR "\n错误信息：航班号须由2位大写字母和4位数字组成。\n 输入数据错误，程序终止执行！\n" typedef char KeyType; typedef struct { char start[6]; char end[6]; char sche[6]; char time1[6]; char time2[6]; char model[3]; int price; }InfoType; typedef struct { KeyType keys[keylen]; InfoType others; int next; }SLNode; typedef struct { SLNode sl[MaxSpace]; int keynum; int length; }SLList; typedef int ArrType_n[RADIX_n]; typedef int ArrType_c[RADIX_c]; KeyType key[keylen],kl[4]; void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e); void Collect(SLNode *sl, int i, ArrType_n f, ArrType_n e); void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e); void Collect_c(SLNode *sl, int i, ArrType_c f, ArrType_c e); void RadixSort(SLList &L); void Arrange(SLList &L); int BinSearch(SLList L, KeyType key[]); void SeqSearch(SLList L, KeyType key[],int i); void DisplayStyle(int i, char *s); void Display(SLList L, int i); void searchcon(SLList L); void Prompt( ); bool InputData(SLList &L); bool Check_HangBanHao(char *HangBanHao); void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e) { int j,p; for(j=0;j f[j]=0; for(p=sl[0].next; p; p=sl[p].next) { j=sl[p].keys[i]%48; if(!f[j]) f[j]=p; else sl[e[j]].next=p; e[j]=p; } } void Collect(SLNode *sl, ArrType_n f, ArrType_n e) { int j,t; for(j=0;!f[j];j++); sl[0].next=f[j]; t=e[j]; while(j { for(j=j+1;j if(f[j]) { sl[t].next=f[j];t=e[j]; } } sl[t].next=0; } void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e) { int j,p; for(j=0;j f[j]=0; for(p=sl[0].next; p!=0; p=sl[p].next) { j=sl[p].keys[i]%65; if(!f[j]) f[j]=p; else sl[e[j]].next=p; e[j]=p; } } void Collect_c(SLNode *sl, ArrType_c f, ArrType_c e) { int j,t; for(j=0;!f[j]; j++); sl[0].next=f[j];t=e[j]; while(j { for(j=j+1;j if(f[j]) { sl[t].next=f[j];t=e[j]; } } sl[t].next=0; } void RadixSort(SLList &L) { int i; ArrType_n fn,en; ArrType_c fc,ec; for(i=0; i L.sl[i].next=i+1; L.sl[L.length].next=0; for(i=L.keynum-1;i>=2;i--) { Distribute(L.sl,i,fn,en); Collect(L.sl,fn,en); } for(i=1;i>=0;i--) { Distribute_c(L.sl,i,fc,ec); Collect_c(L.sl,fc,ec); } } void Arrange(SLList &L) { int p,q,i; SLNode temp; p=L.sl[0].next; for(i=1;i { while(p p=L.sl[p].next; q=L.sl[p].next; if(p!=i) { temp=L.sl[p];L.sl[p]=L.sl[i];L.sl[i]=temp; L.sl[i].next=p; } p=q; } } int BinSearch(SLList L, KeyType key[]) { int low,high,mid; low=1; high=L.length; while(low<=high){ mid=(low+high)/2; if(strcmp(key,L.sl[mid].keys)==0) return mid; else if(strcmp(key,L.sl[mid].keys)<0) high=mid-1; else low=mid+1; } return 0; } void SeqSearch(SLList L, KeyType key[],int i) { int j,k,m=0; for(j=1;j<=L.length;j++) { switch(i){ case 2:k=strcmp(key,L.sl[j].others.start);break; case 3:k=strcmp(key,L.sl[j].others.end); break; case 4:k=strcmp(key,L.sl[j].others.time1);break; case 5:k=strcmp(key,L.sl[j].others.time2);break; } if(k==0) { m=1; Display(L,j); } } if(m==0) printf("很抱歉，无此航班信息。\n"); } void Display(SLList L, int i) { printf("航班号起点站终点站航班期起飞时间到达时间机型票价\n"); DisplayStyle(6, L.sl[i].keys);DisplayStyle(7, L.sl[i].others.start); DisplayStyle(7, L.sl[i].others.end);DisplayStyle(7, L.sl[i].others.sche); DisplayStyle(9, L.sl[i].others.time1);DisplayStyle(9, L.sl[i].others.time2); DisplayStyle(5, L.sl[i].others.model);printf("%6d\n",L.sl[i].others.price); printf("\n"); } void DisplayStyle(int i, char *s) { int j; i -= strlen(s); for(j=0; j printf(" "); printf("%s,", s); } void searchcon(SLList L) { int i=1,k; while(i>=1 && i<=5){ printf("\n请选择命令代号(0----5): "); scanf("%d", &i); switch(i){ case 1: printf("输入要查询的航班号(字母要大写): "); scanf(" %s", key);k=BinSearch(L, key); if(k) Display(L,k); else printf("很抱歉，无此航班信息。\n"); break; case 2: printf("输入要查询的航班起点站名: "); scanf(" %s", key); SeqSearch(L, key, i); break; case 3: printf("输入要查询的航班终点站名: "); scanf("%s", key); SeqSearch(L, key, i); break; case 4: printf("输入要查询的航班起飞时间: "); scanf("%s", kl); SeqSearch(L, kl, i); break; case 5: printf("输入要查询的航班到达时间: "); scanf("%s", kl); SeqSearch(L, kl, i); break; case 0: printf("再见!\n"); return; } Prompt( ); } } void Prompt( ) { printf("***************************************************\n"); printf(" * 航班信息查询与检索系统*\n"); printf("***************************************************\n"); printf(" * 1.按航班号查询*\n"); printf(" * 2.按起点站查询*\n"); printf(" * 3.按终点站查询*\n"); printf(" * 4.按起飞时间查询*\n"); printf(" * 5.按到达时间查询*\n"); printf(" * 0.退出系统*\n"); printf("***************************************************\n"); } bool InputData(SLList &L) { int i=++L.length; char yn='y'; printf("\n请依次录入航班信息数据（航班号由2位大写字母和4位数字组成）:"); do { printf("\n航班号起点站终点站航班期起飞时间到达时间机型票价\n"); scanf("%s%s%s%s%s%s%s%d", L.sl[i].keys, L.sl[i].others.start, L.sl[i].others.end, L.sl[i].others.sche, L.sl[i].others.time1, L.sl[i].others.time2, L.sl[i].others.model, &L.sl[i].others.price); fflush(stdin); if(!Check_HangBanHao(L.sl[i].keys)) return false; ++i; printf("继续输入吗? y/n:"); scanf("%c",yn); } while(yn=='y' || yn=='Y'); printf("\n"); L.length = i-1; RadixSort(L); Arrange(L); return true; } bool Check_HangBanHao(char *HangBanHao) { if (strlen(HangBanHao) != 6) return false; else if (HangBanHao[0]<'A' || HangBanHao[0]>'Z' || HangBanHao[1]<'A' || HangBanHao[1]>'Z') return false; for(int i=2; i<=5; i++) { if (HangBanHao[i]<'0' || HangBanHao[i]>'9') return false; } return true; } int main( ) { SLList L; L.keynum=6;L.length=0; Prompt( ); if(!InputData(L)) { printf(SHOW_MSG_ERROR); return 1; } searchcon(L); return 0; } 3.3 链式基数排序算法 Void RadixSort(SLList &L) { ArrType_n fn,en; ArrType_c fc,en; For(i=0;k L.s1[i].next=i+1; L.s1[L.lsength].next=0; For(i=L.keynum-1;i>=2;i--) {//需分为两段完成，因为自负的那个分关键字要单独做Distribute_n(L.s1,i,fn,en); Collect_n(L.s1,i,fn,en); } For(i=1;i>=0;i--) { Distribute_c(L.s1,i,fc,ec); Collect_c(L.s1,i,fc,ec); } }//RadixSort //按指针链整理链表 Void Arrange(SLList &L) { p=L.s1[0].next; For(i=1;i { While(p //找到第i个记录，并用p指示其在L中的当前位置 Q=L.s1[p].next; If(p!=i) { Temp=L.s1[p];L.s1[p]=L.s1[i];L.s1[i]=temp; L.s1[i].next=p; } P=q; } }//AArrange 3.4 二分查找的函数定义 Int BinSearch(SLList L,KeysType key[]) { While(low<=high){ Mid=(low+high)/2; If(strcmp(key,L.s1[mid].keys)==0) Return mid; Else low=mid+1; } Return 0; }//BinSearch 第4章程序代码 #include #include /* 宏定义*/ #define MaxSpace 100 #define keylen 6 #define RADIX_n 10 #define RADIX_c 26 #define SHOW_MSG_ERROR "\n错误信息：航班号须由2位大写字母和4位数字组成。\n 输入数据错误，程序终止执行！\n" typedef char KeyType; /* 航班记录数据结构描述*/ typedef struct { char start[6]; //起点char end[6]; //终点char sche[6]; //班期char time1[6]; //起飞时间char time2[6]; //到达时间char model[3]; //机型int price; //票价 }InfoType; /* 静态链表结点类型*/ typedef struct { KeyType keys[keylen]; //关键字（航班号）InfoType others; int next; }SLNode; /* 静态链表类型*/ typedef struct { SLNode sl[MaxSpace]; //静态链表int keynum; //关键字字符数int length; //表长}SLList; typedef int ArrType_n[RADIX_n]; //数字字符typedef int ArrType_c[RADIX_c]; //字母字符KeyType key[keylen],kl[4]; /* 功能函数声明*/ void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e); void Collect(SLNode *sl, int i, ArrType_n f, ArrType_n e); void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e); void Collect_c(SLNode *sl, int i, ArrType_c f, ArrType_c e); void RadixSort(SLList &L); void Arrange(SLList &L); int BinSearch(SLList L, KeyType key[]); void SeqSearch(SLList L, KeyType key[],int i); void DisplayStyle(int i, char *s); void Display(SLList L, int i); void searchcon(SLList L); void Prompt( ); bool InputData(SLList &L); bool Check_HangBanHao(char *HangBanHao); /* 1. 数字字符分配函数*/ void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e) { int j,p; for(j=0;j f[j]=0; for(p=sl[0].next; p; p=sl[p].next) { j=sl[p].keys[i]%48; //将数字字符映射为十进制数字 if(!f[j]) f[j]=p; else //将p指向的结点插入到第j个子表中sl[e[j]].next=p; e[j]=p; } } /* 2. 数字字符收集函数*/ void Collect(SLNode *sl, ArrType_n f, ArrType_n e) { int j,t; for(j=0;!f[j];j++); //找第一个非空子表sl[0].next=f[j]; //将sl[0].next指向第一个非空子表的第一个结点t=e[j]; while(j { for(j=j+1;j if(f[j]) { sl[t].next=f[j];t=e[j]; //链接到主链表} } sl[t].next=0; } /* 3. 字母字符分配函数*/ void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e) { int j,p; for(j=0;j f[j]=0; for(p=sl[0].next; p!=0; p=sl[p].next) { j=sl[p].keys[i]%65; //将字母字符映射为字母集中的相应序号 if(!f[j]) f[j]=p; else //将p指向的结点插入到第j个子表中sl[e[j]].next=p; e[j]=p; } } /* 4. 字母字符收集函数*/ void Collect_c(SLNode *sl, ArrType_c f, ArrType_c e) { int j,t; for(j=0;!f[j]; j++); //找第一个非空子表sl[0].next=f[j];t=e[j]; //将sl[0].next指向第一个非空子表的第一个结点while(j { for(j=j+1;j if(f[j]) { sl[t].next=f[j];t=e[j]; //链接到主链表} } sl[t].next=0; } /* 5. 链式基数排序函数*/ void RadixSort(SLList &L) { int i; ArrType_n fn,en; ArrType_c fc,ec; for(i=0; i L.sl[L.length].next=0; //"0"表示空指针 //按最低位优先依次对各关键字进行分配和收集for(i=L.keynum-1;i>=2;i--) //对低四位数字部分进行分配和收集{ Distribute(L.sl,i,fn,en); Collect(L.sl,fn,en); for(i=1;i>=0;i--) //对高位的2位字母进行分配和收集{ Distribute_c(L.sl,i,fc,ec); Collect_c(L.sl,fc,ec); } } /* 6. 按指针链整理线性表*/ void Arrange(SLList &L) { int p,q,i; SLNode temp; p=L.sl[0].next; //p指向第一个结点for(i=1;i { while(p q=L.sl[p].next; if(p!=i) //若第i个结点不在当前位置，交换结点数据 { temp=L.sl[p];L.sl[p]=L.sl[i];L.sl[i]=temp; L.sl[i].next=p; } p=q; //p指向下一个未调整结点} } /* 7. 二分查找函数*/ int BinSearch(SLList L, KeyType key[]) { int low,high,mid; low=1; high=L.length; while(low<=high){ mid=(low+high)/2; if(strcmp(key,L.sl[mid].keys)==0) return mid; else if(strcmp(key,L.sl[mid].keys)<0) high=mid-1; else low=mid+1; } return 0; } /* 8.顺序查找函数*/ void SeqSearch(SLList L, KeyType key[],int i) { int j,k,m=0; for(j=1;j<=L.length;j++) switch(i){ case 2:k=strcmp(key,L.sl[j].others.start);break; case 3:k=strcmp(key,L.sl[j].others.end); break; case 4:k=strcmp(key,L.sl[j].others.time1);break; case 5:k=strcmp(key,L.sl[j].others.time2);break; } if(k==0) { m=1; Display(L,j); } } if(m==0) printf("很抱歉，无此航班信息。\n"); } /* 9. 打印班次信息函数*/ void Display(SLList L, int i) { printf("航班号起点站终点站航班期起飞时间到达时间机型票价\n"); DisplayStyle(6, L.sl[i].keys);DisplayStyle(7, L.sl[i].others.start); DisplayStyle(7, L.sl[i].others.end);DisplayStyle(7, L.sl[i].others.sche); DisplayStyle(9, L.sl[i].others.time1);DisplayStyle(9, L.sl[i].others.time2); DisplayStyle(5, L.sl[i].others.model);printf("%6d\n",L.sl[i].others.price); printf("\n"); } /* 10. 调整对齐格式函数*/ void DisplayStyle(int i, char *s) { int j; i -= strlen(s); for(j=0; j printf(" "); printf("%s,", s); } /* 11. 交互界面函数*/ void searchcon(SLList L) { int i=1,k; while(i>=1 && i<=5){ printf("\n请选择命令代号(0----5): "); scanf("%d", &i); switch(i){ case 1: printf("输入要查询的航班号(字母要大写): "); scanf(" %s", key);k=BinSearch(L, key); if(k) Display(L,k); else printf("很抱歉，无此航班信息。\n"); break; case 2: printf("输入要查询的航班起点站名: "); scanf(" %s", key); SeqSearch(L, key, i); break; case 3: printf("输入要查询的航班终点站名: "); scanf("%s", key); SeqSearch(L, key, i); break; case 4: printf("输入要查询的航班起飞时间: "); scanf("%s", kl); SeqSearch(L, kl, i); break; case 5: printf("输入要查询的航班到达时间: "); scanf("%s", kl); SeqSearch(L, kl, i); break; case 0: printf("再见！\n"); return; } Prompt( ); //循环显示主菜单 } } /* 12. 显示主菜单*/ void Prompt( ) { printf("***************************************************\n"); printf(" * 航班信息查询与检索系统*\n"); printf("***************************************************\n"); printf(" * 1.按航班号查询*\n"); printf(" * 2.按起点站查询*\n"); printf(" * 3.按终点站查询*\n"); printf(" * 4.按起飞时间查询*\n"); printf(" * 5.按到达时间查询*\n"); printf(" * 0.退出系统*\n"); printf("***************************************************\n"); } /* 13. 输入航班记录函数*/ bool InputData(SLList &L) { int i=++L.length; char yn='y'; printf("\n请依次录入航班信息数据（航班号由2位大写字母和4位数字组成）:"); do { printf("\n航班号起点站终点站航班期起飞时间到达时间机型票价\n"); scanf("%s%s%s%s%s%s%s%d", L.sl[i].keys, L.sl[i].others.start, L.sl[i].others.end, L.sl[i].others.sche, L.sl[i].others.time1, L.sl[i].others.time2, L.sl[i].others.model, &L.sl[i].others.price); fflush(stdin); //清空输入缓冲区 if(!Check_HangBanHao(L.sl[i].keys)) return false; ++i; printf("继续输入吗? y/n:"); scanf("%c",&yn); } while(yn=='y' || yn=='Y'); printf("\n"); L.length = i-1; RadixSort(L); Arrange(L); return (true); } /* 14. 航班号输入效验*/ bool Check_HangBanHao(char *HangBanHao) { //必须为6位 if (strlen(HangBanHao) != 6) return false; //1-2位须为大写字母 else if (HangBanHao[0]<'A' || HangBanHao[0]>'Z' || HangBanHao[1]<'A' || HangBanHao[1]>'Z') return false; //3-6位须为数字 for(int i=2; i<=5; i++) { if (HangBanHao[i]<'0' || HangBanHao[i]>'9') return false; } return true; } /* 15. 主函数*/ int main( ) { SLList L; L.keynum=6;L.length=0; //初始化 Prompt( ); //显示界面if(!InputData(L)) //信息录入，并作输入效验{ printf(SHOW_MSG_ERROR); return 1; } searchcon(L); //执行相关查询 return 0; } 第5章运行与测试 按要求依次输入要查询的信息： （1）先输入航班信息 输入1，查询航班号 输入2，查询起点站 输入3，查询终点站 输入4，查询起飞时间 输入5，查询到达时间 输入0，退出系 算法与数据结构实验报告航班查询与检索 题目：航班查询与检索 指导老师： 组长： 成员： 一：航班信息的查询与检索 初始化信息 进行排序 主菜单显示输入查询序号判断序号是否合法 按航班号查询按时间 查询 按地点 查询 按票价 查询 输出航班信息 结束 开始 按时间查询： 按站点查询： 开始 输入票价范围 判断有无符合条件票价 输出相应信息 返回查询信息 按票价范围查询 输入查询时间 Time=1 按抵达时间查询 按起飞时间查询 返回查询信息 开始 是 否 二分法查询： 开始 返回查询信息 输入起点终点及AD AD=1? 按目的站查询 按起点站查询 否 是 二： 算法分析：程序主要采用结构体 链表 顺序表 队列 主要算法：/*航班信息的查询与检索*/ 三：/*航班信息的查询与检索*/ #include #include 《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月 三级项目报告注意事项 1. 按照项目要求书写项目报告，条理清晰，数据准确； 2. 项目报告严禁抄袭，如发现抄袭的情况，则抄袭者与被抄袭者均 以0分计； 3. 课程结束后报告上交教师，并进行考核与存档。 三级项目报告格式规范 1. 正文：宋体，小四号，首行缩进2字符，1.5倍行距，段前段后 各0行； 2. 图表：居中，图名用五号字，中文用宋体，英文用“Times New Roman”，位于图表下方，须全文统一。 目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一：项目成员 (6) 附录二：相关代码、电路图等 (6) 一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能： 1）利用数据结构的知识独立完成一个应用系统设计 2）程序正常运行，能够实现基本的数据增加、删除、修改、查询等功能3）体现程序实现算法复杂度优化 4）体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能： （结合本系统预期具体实现，描述出对应基本要求(增、删、改、查等)的具体功能） 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 （基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现） 模块一： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 数据结构实验总结报告 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件， 会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 （3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。 三、调研常用的压缩算法，对这些算法进行比较分析 （一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。 变体1：重复次数+字符 文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。 学院名称 《数据结构》课程设计报告题目——航班信息查询与检索 班级： 姓名： 时间：2012/12/29---2013/1/5 二○一二年十二月二十九日 课程设计任务书及成绩评定 航班信息查询与检索 课题 名称 Ⅰ、题目的目的和要求： 1、设计目的 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。 （1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。 （2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。 2、设计题目要求： 问题描述:该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。 任务要求:对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等， 这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。 Ⅱ、设计进度及完成情况 Ⅲ、主要参考文献及资料 [1] 严蔚敏数据结构（C语言版）清华大学出版社 1999 [2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999 [3] 谭浩强 C语言程序设计清华大学出版社 [4] 与所用编程环境相配套的C语言或C++相关的资料 Ⅳ、成绩评定： 设计成绩：（教师填写） 指导老师：（签字） 二○一三年一月五日 《数据结构与算法》课程设计报告 学号： 班级序号： 姓名： 指导教师： 成绩： 中国地质大学信息工程学院地理信息系统系 2011年12 月 1．需求规格说明 【问题描述】 利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。 【基本要求】 一个完整的系统应具有以下功能： （1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。 （2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件(*.Haf)。 （3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。 （4）程序使用命令行方式运行 压缩命令：SZip A Test.Haf 1.doc 解压缩命令：SZip X Test.Haf 2.doc或SZip X Test.Haf 用户输入的命令不正确时，给出提示。 （5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。 2．总体分析与设计 （1）设计思想： 1、压缩准备：1> 读文件，逐个读取字符，统计频率 2> 建立哈夫曼树 3> 获得哈弗曼编码 2、压缩过程： 1> 建立一个新文件，将储存权值和字符的对象数组取存储在文件头 数据结构课程设计题目 说明： （1）选用语言：C或Java语言； （2）需要注明3人（可少于3人）小组各自承担和完成的任务（据此给予成绩）； （3）如下带“*”的题目，“*”越多，难度越大一些，分值权重更高---要得到更高分数，推荐选择。 要求： (1) 用中文给出设计说明书（含重要子函数的流程图）； (2) 给出测试通过、能实现相应功能的源代码； (3) 测试报告。 0、小学数学四则混合运算试题出题、评价、题库自动生成与组卷系统（****）---已经有2组选择 任务： （1）将随机给出的四则混合运算表达式显示在计算机显示器上，要求应试者给出答案；并且使用堆栈对该表达式求值，同给出的答案进行比较，判断 正确和错误。给出鼓励信息和嘉奖信息； （2）保存多人在不同时间应试的题目与他（或她）给出的答案，评价所出题目的难易程度（通过多人回答正确与否的情况给出），形成题库； （3）按照用户给出的题目难易程度指标（例如让50人的得分满足怎样的正态分布，如90分以上10%，80分以上30%，70分以上30%，60分以上20%，60分 以下10%），从题库中抽取不同的题目，组成试卷。 要求：随机产生的题目中，参加运算的数据随机、运算符随机。题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。 1、集合的并、交和差运算---已经有1组选择 任务：编制一个能演示执行集合的并、交和差运算的程序。 要求: (1) 集合的元素限定为小写字母字符[…a?..?z?] 。 (2) 演示程序以用户和计算机的对话方式执行。 实现提示:以链表表示集合。 选作内容: (1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。 (3) 集合的混合运算表达式求值。 (4) 集合的元素类型推广到其他类型，甚至任意类型。 2、停车场管理------已经有2组选择 任务：设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 要求：以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。栈以顺序存储结构实现，队列以链表结构实现。 3、哈夫曼码的编/译码系统（**）---已经有1组选择 课程设计报告 课程设计名称：数据结构课程设计 题目：设计并实现一个航班信息查询与检索系统 院系：计算机学院 专业： 班级： 学号： 姓名： 指导教师： 学术诚信声明 本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。 本人签名: 日期：年月日 目录 1 题目介绍 (5) 2 课程设计要求 (5) 2.1课程设计内容 (5) 2.2课程设计目标 (5) 3 概要设计 (5) 3.1设计思路 (5) 3.2流程图 (5) 4 算法概述 (6) 4.1定义数据类型 (6) 4.2函数描述 (7) 5 测试数据 (10) 附录（关键部分程序清单） (12) 1、题目介绍 设计一个航班信息查询与检索系统。可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进行查询。 2、课程设计要求 1、每个航班记录包括八项：航班号、起始站、终点站、班期、起飞时间、到达时间、飞机型号、票价。如下表所示： 2、对航班信息进行排序与查找。 3、概要设计 3.1、设计思路 根据题目所要求，程序必须实现航班信息的录入和查询。程序首先定义了一个储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数据进行排序，最后执行数据查询和检索。在查询设计中，使用折半查找法对排好序的航班号数据实现快速查找，按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。 3.2、流程图 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计 实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 。 武汉轻工大学数计学院《数据结构》课程设计报告 名称:航班查询系统 班级:信息与计算科学1301 姓名:王杰 学号:1312010027 指导教师:王防修 学年学期:2014 ~ 2015 学年第一学期 2014 年12 月26 日 一、需求分析 1. 问题描述： 本任务要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。本设计主要是对排序以及查找等概念进行综合练习。以链式基数排序为主线，用到二分查找和顺序查找等知识，还有建立静态链表等相关概念. 2. 基本要求： 进入系统后，首先提示输入航班的信息，包括：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号及票价等，票价为整型，其他为字符型。当输入完一个信息后会提示是否继续输入，重复以上步骤输入全部的信息。进入主菜单后会给出用户操作的界面，根据提示进行航班信息的查询。 二、概要设计 1.系统的功能： 本任务要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。本设计主要是对排序以及查找等概念进行综合练习。以链式基数排序为主线，用到二分查找和顺序查找等知识，还有建立静态链表等相关概念。 2.系统模块分析： （1）航班排序对输入系统内的航班首先要进行排序，我们采用的基数排序，从低位到高位依次对关键字进行分配和收集，分两段实现其算法流程图。 （2)时间查找根据航班的起飞时间（到达时间）查找航班的信息。 （3)二分法查找功能 （4）显示功能显示功能是将所求单词的所有行列信息依次显示在屏幕上。 航班查询系统 程序源代码： # include 编号 课程设计 题目 1、一元稀疏多项式计算器 2、模拟浏览器操作程序 3、背包问题的求解 4、八皇后问题 二级学院计算机科学与工程学院 专业计算机科学与技术 班级 2011级 37-3班 学生姓名 XX 学号 XXXXXXXXXX 指导教师 XXXXX 评阅教师 时间 1、一元稀疏多项式计算器 【实验内容】 一元稀疏多项式计算器。 【问题描述】 设计一个一元稀疏多项式简单计算器。 【需求分析】 其基本功能包括： （1）输入并建立多项式； （2）输出多项式，输出形式为整数序列为：n,c1,e1,c2,e2,……,cn,en,其中n 是多项式的项数，ci，ei分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相减，建立多项a+b； （4）多项式a和b相减，建立多项式a-b； （5）计算多项式在x处的值； （6）计算器的仿真界面（选做）； 【概要设计】 -=ADT=- { void input(Jd *ha,Jd *hb)； void sort(dnode *h) dnode *operate(dnode *a,dnode *b) float qiuzhi(int x,dnode *h) f",sum); printf("\n"); } 【运行结果及分析】 （1）输入多项式： （2）输出多项式（多项式格式为：c1x^e1+c2x^e2+…+cnx^en）： （3）实现多项式a和b相加： （4）实现多项式a和b相减： （5）计算多项式在x处的值： 2、模拟浏览器操作程序 【实验内容】 模拟浏览器操作程序 【问题描述】 标准Web浏览器具有在最近访问的网页间后退和前进的功能。实现这些功能的一个方法是：使用两个栈，追踪可以后退和前进而能够到达的网页。在本题中，要求模拟实现这一功能。 【需求分析】 需要支持以下指令： BACK：将当前页推到“前进栈”的顶部。取出“后退栈”中顶端的页面，使它成为当前页。若“后退栈”是空的，忽略该命令。 FORWARD：将当前页推到“后退栈”的顶部。取出“前进栈”中顶部的页面，使它成为当前页。如果“前进栈”是空的，忽略该命令。 VISIT 数据结构课程设计 设计说明书 TSP 问题 起止日期：2016 年 6 月27 日至2016 年7 月 1 日 学生姓名 班级 学号 成绩 指导教师( 签字) 2016 年7 月 1 日 目录 第1 章需求分析.................................................................................1... 1.1 简介 (1) 1.2 系统的开发背景 (1) 1.3 研究现状 (1) 第2 章概要设计.................................................................................2... 2.1 系统开发环境和技术介绍 (2) 2.2 系统需求分析 (2) 2.2.1 总体功能分析 (2) 2.2.2 核心功能分析 (3) 第3 章详细设计...................................................................................4... 3.1 系统开发流程 (4) 3.2 系统模块设计 (4) 3.3 系统结构 (6) 3.2 系统流程图 (6) 第4 章调试分析...................................................................................7... 4.1 程序逻辑调试 (7) 4.2 系统界面调试 (8) 第5 章测试结果...................................................................................9... 5.1 测试环境 (9) 5.2 输入输出测试项目 (9) 5.3 测试结果 (10) 结论.....................................................................................................1..1.. 参考文献................................................................................................1..1. 附录.......................................................................................................1..2.. 关于数据结构课程设计心得体会范文 心得体会是指一种读书、实践后所写的感受性文字。是指将学习的东西运用到实践中去，通过实践反思学习内容并记录下来的文字，近似于经验总结。下面是小编搜集的关于数据结构课程设计心得体会范文，希望对你有所帮助。 关于数据结构课程设计心得体会(1) 这学期开始两周时间是我们自己选题上机的时间，这学期开始两周时间是我们自己选题上机的时间，虽然上机时间只有短短两个星期但从中确实学到了不少知识。上机时间只有短短两个星期但从中确实学到了不少知识。 数据结构可以说是计算机里一门基础课程，据结构可以说是计算机里一门基础课程，但我觉得我们一低计算机里一门基础课程定要把基础学扎实，定要把基础学扎实，然而这次短短的上机帮我又重新巩固了 c 语言知识，让我的水平又一部的提高。数据结构这是一门语言知识让我的水平又一部的提高。数据结构这是一门知识，纯属于设计的科目，它需用把理论变为上机调试。 纯属于设计的科目，它需用把理论变为上机调试。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。来说具有一定的难度。它是其它编程语言的一门基本学科。我选的上机题目是交叉合并两个链表，对这个题目，我选的上机题目是交叉合并两个链表，对这个题目，我觉得很基础。刚开始调试代码的时候有时就是一个很小的错觉得很基础。 刚开始调试代码的时候有时就是一个很小的错调试代码的时候误，导致整个程序不能运行，然而开始的我还没从暑假的状导致整个程序不能运行，态转到学习上，每当程序错误时我都非常焦躁，态转到学习上，每当程序错误时我都非常焦躁，甚至想到了放弃，但我最终找到了状态，一步一步慢慢来，放弃，但我最终找到了状态，一步一步慢慢来，经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然具备的条件! 同时，通过此次课程设计使我了解到，必然具备的条件! 同时，通过此次课程设计使我了解到，硬件语言必不可缺少，要想成为一个有能力的人，必须懂得件语言必不可缺少，要想成为一个有能力的人，硬件 武汉理工大学华夏学院课程设计报告书 课程名称：数据结构课程设计 题目：用C语言实现成绩统计程序的设计系名：信息工程系 专业班级：计算机1121 姓名：吴涛 学号：10210412104 指导教师:司晓梅 2016年3 月20日 武汉理工大学华夏学院信息工程系 课程设计任务书 课程名称：数据结构课程设计指导教师：司晓梅班级名称：计算机1121 开课系、教研室：信息系计算机 一、课程设计目的与任务 《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程。目的：学习数据结构课程，旨在使学生学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据的逻辑结构和存储结构以及相应操作，把现实世界中的问题转换为计算机内部的表示和处理，这就是一个良好的程序设计技能训练的过程。提高学生的程序设计能力、掌握基本知识、基本技能，提高算法设计质量与程序设计素质的培养就是本门课程的课程设计的目的。 任务：根据题目要求，完成算法设计与程序实现，并按规定写出课程设计报告。 二、课程设计的内容与基本要求 设计题目：用C语言实现成绩统计程序的设计 〔问题描述〕给出n个学生的m门课程的考试成绩信息，每条信息由姓名、课程代号与分数组成，要求设计算法： （1）输入每个人的各门课程的成绩，计算每人的平均成绩； （2）按平均成绩的高低次序，打印出个人的名次，平均成绩相同的为同一名次； （3）按名次列出每个学生的姓名和各科成绩； 〔基本要求〕学生的考试成绩必须通过键盘输入，且需对输出进行格式控制； 〔算法提示〕可以用选择排序、冒泡排序等多种排序算法求解； 具体要完成的任务是： A. 编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B. 写出规范的课程设计报告书； 三、课程设计步骤及时间进度和场地安排 时间：1周地点：现代教育中心 具体时间安排如下： 第一天：布置题目，确定任务、查找相关资料 第二天～第四天：功能分析，编写程序，调试程序、运行系统； 第五天上午：撰写设计报告； 第五天下午：程序验收、答辩。 四、课程设计考核及评分标准 排序算法： (1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序(6) 堆排序 (7) 归并排序 【算法分析】 （1）直接插入排序；它是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的序的有序表中，从而得到一个新的、记录数增加1的有序表。 （2）折半插入排序：插入排序的基本操作是在一个有序表中进行查找和插入，我们知道这个查找操作可以利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。 （3）冒泡排序：比较相邻关键字，若为逆序（非递增），则交换，最终将最大的记录放到最后一个记录的位置上，此为第一趟冒泡排序；对前n-1记录重复上操作，确定倒数第二个位置记录；……以此类推，直至的到一个递增的表。 (4)简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。 (5)快速排序:它是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 (6)堆排序: 使记录序列按关键字非递减有序排列，在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 (7)归并排序:归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2-路归并排序。 【算法实现】 （1）直接插入排序： void InsertSort(SqList &L){ for(i=2;i<=L.length ;i++) if(L.elem[i] 《数据结构课程设计》报告 题目：课程设计题目2教学计划编制 班级：700 学号：09070026 姓名：尹煜 完成日期：2011年11月7日 一．需求分析 本课设的任务是根据课程之间的先后的顺序，利用拓扑排序算法，设计出教学计划，在七个学期中合理安排所需修的所有课程。 （一）输入形式：文件 文件中存储课程信息，包括课程名称、课程属性、课程学分以及课程之间先修关系。 格式：第一行给出课程数量。大于等于0的整形，无上限。 之后每行按如下格式“高等数学公共基础必修6.0”将每门课程的具体信息存入文件。 课程基本信息存储完毕后，接着给出各门课程之间的关系，把每门课程看成顶点，则关系即为边。 先给出边的数量。大于等于0的整形。 默认课程编号从0开始依次增加。之后每行按如下格式“1 3”存储。此例即为编号为1的课程与编号为3的课程之间有一条边，而1为3的前驱，即修完1课程才能修3课程。 例： （二）输出形式：1.以图形方式显示有向无环图 2.以文本文件形式存储课程安排 （三）课设的功能 1.根据文本文件中存储的课程信息（课程名称、课程属性、课程学分、课程之间关系） 以图形方式输出课程的有向无环图。 拓展：其显示的有向无环图可进行拖拽、拉伸、修改课程名称等操作。 2.对课程进行拓扑排序。 3.根据拓扑排序结果以及课程的学分安排七个学期的课程。 4.安排好的教学计划可以按图形方式显示也可存储在文本文件里供用户查看。 5.点击信息菜单项可显示本人的学好及姓名“09070026 尹煜” （四）测试数据（见六测设结果） 二．概要设计 数据类型的定义： 1.Class Graph即图类采用邻接矩阵的存储结构。类中定义两个二维数组int[][] matrix 和Object[][] adjMat。第一个用来标记两个顶点之间是否有边，为画图服务。第二个 是为了实现核心算法拓扑排序。 2.ArrayList 数据结构课程设计心得体会数据结构课程设计心得体会怎么写，以下是XX精心整理的相关内容，希望对大家有所帮助! 数据结构课程设计心得体会这学期开始两周时间是我们自己选题上机的时间，这学期开始两周时间是我们自己选题上机的时间，虽然上机时间只有短短两个星期但从中确实学到了不少知识。上机时间只有短短两个星期但从中确实学到了不少知识。数据结构可以说是计算机里一门基础课程，据结构可以说是计算机里一门基础课程，但我觉得我们一低计算机里一门基础课程定要把基础学扎实，定要把基础学扎实，然而这次短短的上机帮我又重新巩固了C 语言知识，让我的水平又一部的提高。数据结构这是一门语言知识让我的水平又一部的提高。数据结构这是一门知识，纯属于设计的科目，它需用把理论变为上机调试。纯属于设计的科目，它需用把理论变为上机调试。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。来说具有一定的难度。它是其它编程语言的一门基本学科。我选的上机题目是交叉合并两个链表，对这个题目，我选的上机题目是交叉合并两个链表，对这个题目，我觉得很基础。刚开始调试代码的时候有时就是一个很小的错觉得很基础。刚开始调试代码的时候有时就是一个很小的错调试代码的时候误，导致整个程序不能运行，然而开始的我还 没从暑假的状导致整个程序不能运行，态转到学习上，每当程序错误时我都非常焦躁，态转到学习上，每当程序错误时我都非常焦躁，甚至想到了放弃，但我最终找到了状态，一步一步慢慢来，放弃，但我最终找到了状态，一步一步慢慢来，经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然具备的条件! 同时，通过此次课程设计使我了解到，必然具备的条件! 同时，通过此次课程设计使我了解到，硬件语言必不可缺少，要想成为一个有能力的人，必须懂得件语言必不可缺少，要想成为一个有能力的人，硬件基础语言。在这次课程设计中，硬件基础语言。在这次课程设计中，虽然不会成功的编写一个完整的程序，但是在看程序的过程中，个完整的程序，但是在看程序的过程中，不断的上网查资料以及翻阅相关书籍，通过不断的模索，测试，发现问题，以及翻阅相关书籍，通过不断的模索，测试，发现问题，解 决问题和在老师的帮助下一步一步慢慢的正确运行程序，决问题和在老师的帮助下一步一步慢慢的正确运行程序，终于完成了这次课程设计，于完成了这次课程设计，虽然这次课程设计结束了但是总觉得自已懂得的知识很是不足，学无止境，得自已懂得的知识很是不足，学无止境，以后还会更加的努力深入的学习。力深入的学习。 数据结构课程设计心得体会本次课程设计，使我对《数 目录 (2) 1 概述 (2) 1.1 课程设计名称 (2) 1.2 课程设计目的 (2) 1.3 课程设计内容 (2) 2 系统分析 (2) 2.1 设计要求 (2) 2.2 设计分析 (2) 3 概要设计 (3) 3.1 系统总流程图 (3) 3.2 定义数据类型 (3) 3.3 实现排序的各函数的说明 (4) 4 详细设计 (4) 4.1 数据类型的定义 (4) 4.2 链式基数排序 (5) 4.2.1 一趟数字字符分配函数 .................... 错误！未定义书签。 4.2.2 一趟数字字符的收集函数................. 错误！未定义书签。 4.2.3 一趟字母字符分配函数 .................... 错误！未定义书签。 4.2.4 一趟字母字符收集 ........................... 错误！未定义书签。 4.2.6 链式基数排序函数 ........................... 错误！未定义书签。 4.3 重新整理静态链表 (6) 4.4 查找算法实现 (6) 4.4.1 二分查找函数 (6) 4.4.2 顺序查找函数 (7) 4.5 输入输出函数 (7) 5 运行与测试 (8) 6 总结与心得 (11) 7 参考文献 (11) 8 附录（程序源代码） (11) 目录 1 概述 1.1 课程设计名称 航班信息的查询与检索 1.2 课程设计目的 通过本次实验，掌握数据结构中的几种排序算法和查找算法，了解静态链表的运用，利用上述的算法完成航班信息的查询与检索。 2 系统分析 2.1 课程设计内容 本课程设计主要是对排序及查找等进行练习，以链式基数排序为主线，利用二分查找和顺序查找等知识，并建立静态链表，完成对航班信息的查询与检索。我们可以利用航班的这些信息，通过其中的任意一个信息，找出我们所需要的查找的航班的所有信息，所以，我们可以采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排序好的航班记录按航班号实现快速查找，并按其他关键字的查找可以采用最简单的顺序查找方法进行。 2.2 设计要求 1) 提供对航班信息的排序功能 2 提供对航班信息的输入输出记录功能找出我们所需要的查找的航班的所有信息 3）提供按关键字（航班号）快速查询或顺序查询功能 2.3 设计分析 对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用得比较少。 每个航班记录包括八项，分别是：航班号，起点站，终点站，班期，起飞时间，到达时间，飞机型号以及票价等。其中航班号一项的格式为： K0 k1 k2 k3 k4 k5 C Z 3 8 6 9 航班关键字可分为两段，即字母和数字。其中k0和k1是航空公司的别称，用两个大写字母表数据结构课程设计-航班查询与检索(含代码、流程图、输出结果)
数据结构课程设计报告模板
数据结构实验总结报告
数据结构课程设计航班信息查询与检索
数据结构课程设计报告
数据结构课程设计题目选择
航班信息查询与检索系统
数据结构课程设计报告模板
数据结构课程设计题目及要求
航班查询系统
数据结构课程设计报告
数据结构课程设计报告
关于数据结构课程设计心得体会范文
数据结构课程设计报告-学生成绩管理系统[]
数据结构课程设计排序算法总结
数据结构课程设计报告
数据结构课程设计心得体会
航班信息的查询与检索
- 航班信息查询与检索系统课程设计报告
- 数据结构课程设计报告航班信息查询与检索
- 20141204060 航班信息的查询与检索(排序应用)
- 航班有关信息的查询与检索讲解--实用.doc
- 航班信息的查询与及检索
- 航班信息的查询与检索的程序设计模版
- 航班信息的查询与检索
- 航班信息的查询与检索讲解
- 数据结构课程设计航班信息查询与检索
- 航班信息的查询和检索.
- 航班信息查询与检索系统
- 数据结构课程设计航班信息的查询与检索汇编
- 数据结构课程设计航班信息的查询与检索
- 数据结构与算法课程设计报告——航班信息查询系统(C++)
- 项目一航班信息查询
- 航班信息查询与检索系统
- 数据结构课程设计航班信息查询与检索
- 数据结构课程设计航班信息的查询与检索
- 航班信息的查询与检索
- 数据结构课程设计--航班信息查询与检索系统