数据库原理与应用实训教程

数据库原理与应用实训教程 崔海源 主 编 大连理工大学出版社数据库原理与应用实训教程 崔海源 主 编 李 橙 李 霞 编 著大连理工大学出版社内容简介本书共分七章，包含七个完整实训项目，分别涉及到数据结构中线性表、栈、串、树、查找和排序六个知识点。每个章节都详细介绍一个实训项目得开发过程，并以“问题描述”、“输入与输出”、“需求分析”、“开发工具与环境”、“概要设计”、“详细设计”、“调试结果”为纲安排过程，使得读者能够清楚每一个项目实施的具体步骤，便于分析和解决问题。这七个实训项目分成A、B两个等级。B级项目在原有书本知识的基础之上进行拓展，是各知识的高级应用。例如第三章的项目“基于栈结构的中缀表达式求职”，是应用栈结构的高级应用。学生首先要会掌握与栈相关的各种基本运算，在此基础之上，应用栈的知识对输入的任意中缀表达式进行转换与求值。A级难度最大，涉及到得内容是课本以外的，因此增加了“知识准备”，对于涉及到的知识进行简单讲解。A级项目对学生的自学能力和创新能力有很高的要求，适合于学有余力和程序发烧友完成。本书项目实例以C作为开发平台。可以使用TURBO C或VC进行程序的编写。C语言是目前世界上流行、使用最广泛的高级程序设计语言。C语言对操作系统和系统使用程序以及需要对硬件进行操作的场合，用C语言明显优于其它高级语言，许多大型应用软件都是用C语言编写的。而C语言是数据结构的先修课程，我们的学生在学数据结构之前都系统的学习过了C语言，因此对于编写C语言都有一定的基础。本书可作为本、专科、高职层次数据库技术与应用的实训教材。本书中出现的所有C语言或程序模块都在VC6.0系统环境下调试并通过，其正确性得到了实际的验证，从而增强了教材的实用性和科学性。本书所有的源程序代码可通过以下地址下载（/drill）;也可以通过Email和李憕老师联系（）。本书由南京师范大学泰州学院李橙老师（编写1、2、3、5章）和李霞老师（编写4、6、7章），另外彭程和苏戴也参与了程序的编写和调试。由于编者的水平有限，本书肯定会有不少缺点和不足，热切期望得到专家和读者的批评指正。 编者 2009年12月主编寄语一本好的教材，基本上奠定了一半的教学效果。好的教学效果，就是满足市场对人才的需求。但长期以来，高校批量培养出的计算机软件专业的学生，不能满足公司的用人标准，在技术基础、职业素养、独立工作能力等方面都有欠缺；同时，应用型本科高校既不是理论研究型也不是高级技工型，如何找到准确的定位，让毕业的学生能够高层次就业、“即插即用”，这一直是我们思考的问题。鉴于我系承担的全国高等学校教学研究中心的国家级课题：“我国高校应用型人才培养模式研究”的计算机类子课题-“基于软件工厂的软件开发人才培养模式”，在推动应用型教学改革的深入开展，启动优质教学资源的建设思想指导下，以提高学生的业务水平、动手能力，进而提高学生就业竞争力为目标，我们在软件人才培养的教学计划、教学大纲、教材建设等方面都有所研究和创新，并将“实训教学”作为实现应用型人才培养的重要模式和主要手段。实训课程，也称大作业或小毕设，是不同于仅为验证的实验。我们以此编写的实训教材以项目驱动为主导，模拟企业来运作。每本教材有该门课程的总体概述、实用够用的内容介绍、还有68个不同层次的实训项目，分为A、B、C三个难易等级：C级为入门级，学生可自主完成；B级为中等层次，学生可根据上下文完成全部项目；A级为高级层次，学生可根据教材提示，实现一定程度的项目独创。实训时间可选择期末或伴随课程进行。实训模式可采用“分组考核，自主学习”相结合的组织模式。学生可选择其中一个项目作为实训成果参加考核答辩，检验学习成果，每个项目可安排15课时左右。所以本系列教材源于实践，可以满足不同层次学生的需求，由浅入深，循序渐进，难易随选。本套丛书教材是“人才培养模式研究”课题结项成果的一部分，该项目得到南京师范大学泰州学院的资助，在此表示感谢；同时也感谢大连理工大学出版社给予的鼎力相助。参加丛书数据库原理与应用实训教程、数据结构实训教程、J2EE实训教程、软件工程实训教程、Internet编程实训教程、C#程序设计实训教程等六本教材编写的有南京师范大学泰州学院的史永、张国华、李橙、卫星、吉晓香、周巧扣、叶苗、李霞、陆霞、郭依正、孙秋凤、王自然等多年在一线教学的教师。本教材既可以作为各门课程的配套实训教材、也可作为参考书、课后练习项目。通过本系列实训教材的出版，我们希望能够得到广大读者更大范围的关注并取得合作，从而共同推进我国高校、特别是应用型本科计算机软件方向专业人才的培养建设。计算机学科知识日新月异，加之编者水平有限，书中不当之处，希望读者、专家和同行勿吝指正。 2009-12目 录实训一 基于链表结构的学生记录管理程序51.1问题描述51.2输入与输出51.3 需求分析61.4 开发工具与环境61.5 概要设计61.7调试结果10实训二 基于链表结构的一元多项式相乘142.1问题描述142.2输入与输出142.3需求分析142.4开发工具与环境142.5概要设计142.6详细设计152.7调试结果18实训三 基于栈结构的中缀表达式求值203.1问题描述203.2输入与输出203.3需求分析203.4开发工具与环境203.5概要设计203.6详细设计223.7调试结果26实训四 文学研究助手264.1 问题描述264.2 输入与输出264.3 需求分析264.4 开发工具与环境264.5 概要设计264.6 详细设计274.7 调试结果30实训五：压缩与解压缩系统325.1 问题描述325.2 输入与输出325.3 需求分析325.4 开发工具与环境325.5 概要设计325.6 详细设计335.7 调试结果37实训六：hash技术统计词频376.1 问题描述376.2 输入与输出376.3 需求分析376.4 开发工具与环境376.5 概要设计376.6 详细设计386.7调试结果43实训七：内部排序算法比较457.1 问题描述457.2 输入与输出457.3 需求分析457.4 开发工具与环境457.5 概要设计457.6 详细设计467.7 调试结果50实训八：校园交通咨询系统设计（最短路径）528.1 问题描述528.2 输入与输出528.3 需求分析528.4 开发工具与环境528.5 概要设计528.6 详细设计538.7调试结果57实训一 基于链表结构的学生记录管理程序1.1问题描述学生信息的管理是一项很大的工程。设每个学生记录包含学号，姓名，成绩。使用链表结构来存储学生信息，实现链表的创建，以及在其中插入，删除，遍历记录，对记录按关键字（学号）进行排序并实现文件读写。1.2输入与输出输入：从键盘输入学生记录创建链表 从文件读学生记录创建链表 待插入学生记录，待删除记录的关键字输出：将处理完的记录内容输出到屏幕或文件中1.3 需求分析1.定义链表结构； 2.编写主函数、菜单函数，确定函数之间的接口； 3.编写简单创建链表函数、遍历函数、插入结点函数、创建链表函数、删除结点函数，排序函数；使用多套数据，进行系统调试。4.编写文件读写函数，实现从文件读数据创建链表，以及将链表中的记录保存到文件中去。1.4 开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具VC6.0或TC2.01.5 概要设计数据结构定义 typedef struct student int code; /学号 char name10; /姓名 int score; /分数 struct student *next; /指向下一个学生记录的指针域stu;2各函数模块void show_menu();操作结果：显示菜单void scan(stu *p,stu*head);操作结果：从键盘输入学生记录void create(stu *head);操作结果：根据学生记录，创建链表void print(stu *head);操作结果：在屏幕上打印学生记录void printfile(stu *head);操作结果：将学生记录写到文件中void insert(stu *head);操作结果：插入学生记录void del(stu *head);操作结果：根据学号删除学生记录void sort(stu *head);操作结果：根据学号对学生记录进行排序void search(stu *head); 操作结果：根据学号对学生记录进行查找1.6详细设计void main() int no; stu *head; head=(stu *)malloc(sizeof(stu); do show_menu(); scanf(%d,&no); switch(no) case 1: create(head);break; case 2: print(head);break; case 3: insert(head);break; case 4: del(head);break; case 5: sort(head); printf(排序成功！结果为：n); print(head); break; case 6: search(head);break; case 0: break; default: printf(输入错误！n); break; while(no!=0); printfile(head);void show_menu() printf(n*主菜单*n); printf(*1.新建学生数据 *n); printf(*2.输出学生数据 *n); printf(*3.添加一个学生 *n); printf(*4.删除一个学生 *n); printf(*5.排序 *n); printf(*6.查找 *n); printf(*0.退出 *n); printf(*n); printf(请选择序号：n);void scan(stu *p,stu *head) do printf(n请输入学号（大于0，退出循环请输0：）n); scanf(%d,&p-code); if(p-codecode); if(p-code=0) return; while(p-codename); printf(请输入分数：n); scanf(%d,&p-score);void create(stu *head) stu *p,*tail; tail=head; p=(stu *)malloc(sizeof(stu); scan(p,head); while(p-code!=0) tail-next=p; tail=p; p=(stu *)malloc(sizeof(stu); scan(p,head); tail-next=NULL;void print(stu *head) stu *p; sort(head); printf(n学号t姓名tt成绩n); for(p=head-next;p!=NULL;p=p-next) printf(%-8d%-16s%-8dn,p-code,p-name,p-score);void insert(stu *head)/插入学生记录 void del(stu *head) int code; stu *p,*q; printf(请输入要删除学生的学号：n); scanf(%d,&code); p=head; while(p-next!=NULL & p-next-code!=code) p=p-next; if(p-next!=NULL & p-next-code=code) q=p-next; p-next=q-next; printf(学号为%d的学生已被删除！n,code); else printf(学号为%d的学生不存在！n,code);void sort(stu *head)/按照学号对学生记录进行排序void search(stu *head)int code;stu *p;printf(请输入要查找的学号：n);scanf(%d,&code);p=head-next;while(p!=NULL & p-codenext;if(p!=NULL & p-code=code)printf(n学号t姓名t成绩n);printf(%dt%st%dtn,p-code,p-name,p-score);elseprintf(学号为%d的学生不存在!n,code); void printfile(stu *head) FILE *fp; stu *p; fp=fopen(D:student.dat,w+); if(fp!=NULL) fprintf(fp,学号t姓名tt成绩n); for(p=head-next;p!=NULL;p=p-next) fprintf(fp,%-8d%-16s%-8dn,p-code,p-name,p-score); fclose(fp); else printf(文件没有打开！n); 1.7调试结果在循环菜单提示下选择新建学生数据见图11： 图11在屏幕上输出学生记录见图12： 图12添加学生记录见图13： 图13按照学号删除学生记录（学号不存在，删除不成功）见图14：图14根据学号删除学生记录（删除成功）见图15： 图15按照学号对学生记录进行排序见图16：图16根据学号查找学生记录见图17：图17实训二 基于链表结构的一元多项式相乘2.1问题描述实现将一元多项式从文件读入并以链表结构存储到计算机中，将读入的两个一元多项式相乘，并将相乘结果保存到文件中。2.2输入与输出输入：从键盘读入两个一元多项式输出：将两个一元多项式相乘的结果保存到文件中2.3需求分析1.思考一元多项式在文件中的存放形式 2.编写主函数，确定函数之间的接口； 3.编写读文件创建链表程序，写文件程序，编写链表相乘计算的程序，使用多套数据，进行系统调试。2.4开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具VC6.0或TC2.02.5概要设计数据结构定义 typedef struct node int coef; /多项式的系数 int index; /指数 struct node *next;NODE;2各函数模块NODE *createfile(char filename );操作结果：读文件，创建一元多项式链表NODE *createinput();操作结果：从键盘读数据，创建一元多项式链表void show_menu();操作结果：显示菜单void cover(NODE *head);操作结果：将链表表示的一元多项式，表示一般形式显示void insert(NODE *head,NODE *new1);操作结果：将new1指向的某项，按照指数降序插入到head指向的一元多项式链表中去void plus(NODE *L1, NODE *L2,NODE *L3);操作结果：将L1和L2指向的多项式相乘，结果保存在L3中void print(NODE *head);操作结果：将head指向的一元多项式打印在屏幕上void printfile(NODE *L);操作结果：将L指向的一元多项式写到文件中。2.6详细设计void main()NODE *L1,*L2,*L3;int no; L3=(NODE*)malloc(sizeof(NODE);do show_menu(); scanf(%d,&no); switch(no) case 1: L1=createfile(D:/in1.dat); printf(多项式一：); print(L1); printf(多项式一：); cover(L1); L2=createfile(D:/in2.dat); printf(n多项式二：); print(L2); printf(多项式二：); cover(L2); L3-coef=0; L3-next=L3; plus(L1,L2,L3); / L1*L2=L3 printf(n多项式相乘得：n); print(L3); printf(多项式相乘得：); cover(L3); printfile(L3); break; case 2: printf(多项式一：n); L1=createinput(); printf(多项式一:); cover(L1); printf(n多项式二：n); L2=createinput(); printf(多项式二:); cover(L2); L3-coef=0; L3-next=L3; plus(L1,L2,L3); / L1*L2=L3 printf(n多项式相乘得：n); print(L3); printf(多项式相乘得：); cover(L3); printfile(L3); break; case 0: break; default: printf(输入错误！n); break; while(no!=0); void show_menu() printf(n*主菜单*n); printf(*1.从文件读入数据 *n); printf(*2.从键盘输入数据 *n); printf(*0.退出 *n); printf(*n); printf(请选择序号：);NODE *createfile(char filename) /从文件中读入数据 FILE *fp; int i,count; NODE *head,*p; fp=fopen(filename,r); fscanf(fp,count=%dn,&count); head=(NODE *)malloc(sizeof(NODE); head-coef=0; head-next=head; for(i=0; icoef,&p-index); insert(head,p); fclose(fp); return(head);NODE *createinput() /通过键盘输入数据 int i,count; NODE *head,*p; printf(请输入多项式的项数：);scanf(%d,&count); head=(NODE *)malloc(sizeof(NODE); head-coef=0; head-next=head; for(i=1; icoef); printf(index=);scanf(%d,&p-index); insert(head,p);return(head);void insert(NODE *head,NODE *new1) /将new1指向的某项，按照指数降序插入到head指向的一元多项式链表中去void cover(NODE *head) /转化成式子 NODE *p;int a,b; for(p=head-next; p-index=0; p=p-next) a=p-coef; b=p-index; if(p-next-index=0) printf(%dX%d+,a,b); else printf(%dX%d,a,b);printf(n); / L1*L2=L3 void plus(NODE *L1, NODE *L2,NODE *L3) / 将L1和L2指向的多项式相乘，结果保存在L3中 void print(NODE *head) NODE *p; printf(count=%dn,head-coef); for(p=head-next; p-index=0; p=p-next) printf(coef=%d,index=%dn,p-coef, p-index);void printfile(NODE *L) FILE *fp;NODE *p; fp=fopen(D:in3.dat,w+); if(fp!=NULL)fprintf(fp,count=%dn,L-coef);for(p=L-next; p-index=0; p=p-next) fprintf(fp,coef=%d,index=%dn,p-coef, p-index);2.7调试结果从文件读入数据见图21：图21从键盘读入数据见图22： 图22文件中存放的多项式见图23：实训三 基于栈结构的中缀表达式求值3.1问题描述从键盘输入一中缀表达式字符串，读字符串，利用栈结构实现表达式求值。3.2输入与输出输入：从键盘中缀表达式eg. 325（64）输出：计算结果423.3需求分析1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算2.在读数的时候考虑多位运算 3.实现表达式求值3.4开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具VC6.0或TC2.03.5概要设计结构定义 typedef struct /* 运算符栈 */ char *base,*top; int stacksize; SqStack; typedef struct /* 运算数栈 */ int *base,*top; int stacksize; SqStack1;int priority77=, , , , , , / + , , , , , , / - , , , , , , / * , , , , , , / / , , , , , , , , , , , / ) , , , , , , = / #; /*用于比较符号优先级的全局二维数组*/2各函数模块void InitStack(SqStack *s);操作结果：初始化运算符栈char GetTop(SqStack *s);操作结果：得到运算符栈的栈顶元素void Push(SqStack *s,char e);操作结果：对运算符栈进行压栈操作char Pop(SqStack *s);操作结果：对运算符栈进行出栈操作void InitStack1(SqStack1 *s);操作结果：初始化运算数栈int GetTop1(SqStack1 *s);操作结果：得到运算数栈的栈顶元素void Push1(SqStack1 *s,int e);操作结果：对运算数栈进行压栈操作int Pop1(SqStack1 *s);操作结果：对运算数栈进行出栈操作int OpID(char op1);操作结果：得到符号的排列位置char Precede(char op1,char op2);操作结果：利用二维数组比较两个符号的优先级int IsNumber(char c);操作结果：判断一个字符是否是数字int MidExpression_Eval(char Express);操作结果：计算中缀表达式的值int Operate (int a,char x,int b);操作结果：计算表达式axb，并返回结果3.6详细设计void main() char Express20;int s;printf(请输入表达式:n);scanf(%s,Express);s=MidExpression_Eval(Express);printf(运算结果为:%dn,s);int MidExpression_Eval(char Express) int i=0,x,sign; int a,b;char c,fore_op;SqStack *OPTR;SqStack1 *OPND; OPTR=(SqStack *)malloc(sizeof(SqStack);OPND=(SqStack1 *)malloc(sizeof(SqStack1); InitStack(OPTR); /* 运算符栈 */Push(OPTR,#); InitStack1(OPND); /* 运算数栈 */ c=Expressi+; sign=0; while(c!=# | GetTop(OPTR)!=#) if(IsNumber(c) /是数字 else/是运算符，则进行优先级的比较 fore_op=GetTop(OPTR); switch(Precede(fore_op,c)/根据Precede(fore_op,c)函数的值确定操作 case : / fore_op : / fore_op c 执行fore_op sign=0; return(GetTop1(OPND);void InitStack(SqStack *s) s-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s-base) printf(Overlow); return; s-top=s-base; s-stacksize=STACK_INIT_SIZE;void Push(SqStack *s,char e) if(s-top=s-base+s-stacksize) s-base=(char*)realloc(s-base,(s-stacksize+STACK_INCREMENT)*sizeof(char); if(!s-base) printf(Overlow); return; s-top=s-base+s-stacksize; s-stacksize+=STACK_INCREMENT; *s-top=e; s-top+;char GetTop(SqStack *s)char e;if(s-top=s-base) printf(Error!); e=*(s-top-1);return e;char Pop(SqStack *s) char e;if(s-top=s-base) printf(Underlow); s-top-; e=*s-top; return e;void InitStack1(SqStack1 *s) s-base=(int*)malloc(STACK_INIT_SIZE*sizeof(int); if(!s-base) printf(Overlow); return; s-top=s-base; s-stacksize=STACK_INIT_SIZE;void Push1(SqStack1 *s,int e) if(s-top=s-base+s-stacksize) s-base=(int *)realloc(s-base,(s-stacksize+STACK_INCREMENT)*sizeof(int); if(!s-base) printf(Overlow); return; s-top=s-base+s-stacksize; s-stacksize+=STACK_INCREMENT; *s-top=e; s-top+;int GetTop1(SqStack1 *s)int e;if(s-top=s-base) printf(Error!); e=*(s-top-1);return e;int Pop1(SqStack1 *s) int e;if(s-top=s-base) printf(Underlow); s-top-; e=*s-top; return e;int OpID(char op1) switch (op1) case + : return 0; case - : return 1; case * : return 2; case / : return 3; case ( : return 4; case ) : return 5; case # : return 6; char Precede(char op1, char op2) return(priorityOpID(op1)OpID(op2); int Operate (int a,char k,int b)int c;switch(k) case +: c=a+b; break; case -: c=a-b; break; case *: c=a*b; break; case /: c=a/b; break;return(c);int IsNumber(char c)if(c=0 & c=9)return 1;elsereturn 0;3.7调试结果 见图31：图31：实训四 文学研究助手4.1 问题描述要求建立一个文本文件，每个单词子串不包含空格且不跨行，单词子串由字符序列构成，且区分大小写；统计给定单词子串在文本文件中出现的总次数；检索输出某个单词子串出现在文本中的行号、在该行中出现的次数以及位置。4.2 输入与输出输入：从键盘循环输入字符串，创建到文本文件中从键盘输入要计数的单词子串以及要定位的单词子串输出：将统计结果以及