数据结构ch02

课程设计任务书

学生姓名： 专业班级：

指导教师： 工作单位:

题 目： 学生成绩管理系统

已知技术参数和设计要求：

现有学生成绩信息文件1（cj1。txt),内容如下

姓名 学号 语文 数学 英语

张明明 01 67 78 82

李成友 02 78 91 88

张辉灿 03 68 82 56

王露 04 56 45 77

陈东明 05 67 38 47

…. 。. 。。 。。 …

学生成绩信息文件2（cj2.txt），内容如下:

姓名 学号 语文 数学 英语

陈果 31 57 68 82

李华明 32 88 90 68

张明东 33 48 42 56

李明国 34 50 45 87

陈道亮 35 47 58 77

…. 。。 .. .. …

试编写一管理系统, 其基本功能要求:

实现对两个文件数据进行合并,生成新文件cj3.txt

抽取出三科成绩中有补考的学生并保存在一个新文件cj4.txt

对合并后的文件3。txt中的数据按总分降序排序(至少采用两种排序方法实现)

输入一个学生姓名后，能查找到此学生的信息并输出结果(至少采用两种查找方法实现)

要求使用结构体，链或数组等实现上述要求。

采用多种方法且算法正确者,可适当加分。

要求完成的主要任务: (包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）

数据结构课程设计说明书

第３７卷　Ｖ０１．３７　第９期　ＮＯ．９　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１１年５月　Ｍａｖ　２０１１　

・软件技术与数据库・　文章编号：１ｏｏｏｌ＿＿３４２８（２ｏ１１）ｏ９＿＿＿ｏ１ｏ４＿－＿ｏ３　文献标识码：Ａ　中图分类号：ＴＰ３１１・１２　

基于关联规则的决策树算法　

、　汪海锐　，李伟　

ｆ１河海大学计算机与信息学院，江棼常州２１３０２２；２海军蚌埠上官学校，安徽蚌埠２３３０１２）　

摘要：通过将关联规则与决策树算法相结合，形成一种基于关联规则的决策树算法。该算法对不同时期同一事务的异种数据结构进行处　

理，得到一种可扩展的多分支分类决策树，使得改进后的决策树算法具有良好的可扩展性。该算法解决了传统分类算法在数据集维度发生　变化时分类过程无法持续进行的问题。　关健诃：决策树；关联规则；分类算法；扩展性；组合算法　

Ｄｅｃｉｓｉｏｎ　Ｔｒｅｅ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　０ｎ　Ａｓｓｏｃｉａｔｉｏｎ　Ｒｕｌｅｓ　

ＷＡＮＧ　Ｈａｉ．ｒｕｉ　．一．ＬＩ　Ｗｅｉ　

（１　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ＆Ｉｎｆｏｒｍａｔｉｏｎ，Ｈｏｈａｉ　Ｕｎｉｖｅｒｓｉｔｙ．Ｃｈａｎｇｚｈｏｕ　２１３０２２，Ｃｈｉｎａ：２．Ｎａｖｙ　Ｐｅｔｔｙ　Ｏｆｆｉｃｅｒ　Ａｃａｄｅｍｙ．Ｂｅｎｇｂｕ　２３３０１２，Ｃｈｉｎａ）　

［Ａｂｓｔｒａｃｔ］Ｔｈｉｓ　ｐａｐｅｒ　ｃｏｍｂｉｎｅｓ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ａｎｄ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｐｒｏｐｏｓｅｓ　ａ　ｎｅ，ａ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ．Ｔｈｅ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｈａｎｄｌｅ　ｄｉｓｓｉｍｉｌａｒ　ｔｒａｎｓａｃｔｉｏｎ　ｄａｔａ　ｓｅｔ　ｒｅｃｏｉｄ　ｂｌｏｃｋｓ　ｗｈｉｃｈ　ａｒｅ　ｓａｌｎｃ　ｉｎｖｅｓｔｉｇａｔｉｏｎｓ　ｃｏｎｄｎｃｔｅｄ　ｉｎ　ｄｉｆｆｅｒｅｎｔ　ｔｉｍｅｓ　

第四章 串 4.10 void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r { StrAssign(r,''); //初始化r为空串 for(i=Strlen(s);i;i--) { StrAssign(c,SubString(s,i,1)); StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中 } }//String_Reverse 4.11 void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r { StrAssign(r,''); for(i=1;i<=Strlen(s);i++) { StrAssign(c,SubString(s,i,1)); for(j=1;jStrlen(t)) StrAssign(r,Concat(r,c)); } }//for }//String_Subtract 4.12 int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数 { for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围 if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串 { //分别把T的前面和后面部分保存为head和tail StrAssign(head,SubString(S,1,i-1)); StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V)); StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串 i+=Strlen(V); //当前指针跳到插入串以后 n++; }//if return n; }//Replace 分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果? 4.13 int Delete_SubString(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数 { for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++) if(!StrCompare(SubString(s,i,Strlen(t)),t)) { StrAssign(head,SubString(S,1,i-1)); StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1)); StrAssign(S,Concat(head,tail)); //把head,tail连接为新串 n++; }//if return n, }//Delete_SubString 4.14 Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new { Initstack(s); //s的元素为Stringtype类型 for(i=1;i<=Strlen(str);i++) { r=SubString(str,i,1); if(r为字母) push(s,r); else { if(StackEmpty(s)) return ERROR; pop(s,a); if(StackEmpty(s)) return ERROR; pop(s,b); StrAssign(t,Concat(r,b)); StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b连接为新子前缀表达式c push(s,c); } }//for pop(s,new); if(!StackEmpty(s)) return ERROR; return OK; }//NiBoLan_to_BoLan 分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序. 4.15 void StrAssign(Stringtype &T,char chars&#;)//用字符数组chars给串T赋值,Stringtype的定义见课本 { for(i=0,T[0]=0;chars[i];T[0]++,i++) T[i+1]=chars[i]; }//StrAssign 4.16 char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,ss[0]&&i>t[0]) return 0; else if(i>s[0]) return -t[i]; else if(i>t[0]) return s[i]; else return s[i]-t[i]; }//StrCompare 4.17 int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数 { for(n=0,i=1;i<=S[0]-T[0]+1;i++) { for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++); if(k>T[0]) //找到了与T匹配的子串:分三种情况处理 { if(T[0]==V[0]) for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换 S[i+l-1]=V[l]; else if(T[0]=i+T[0];l--) S[l+V[0]-T[0]]=S[l]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } else //新子串长度小于原子串时:先将后部左移 { for(l=i+V[0];l<=S[0]+V[0]-T[0];l++) S[l]=S[l-V[0]+T[0]]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } S[0]=S[0]-T[0]+V[0]; i+=V[0];n++; }//if }//for return n; }//String_Replace 4.18 typedef struct { char ch; int num; } mytype; void StrAnalyze(Stringtype S)//统计串S中字符的种类和个数 { mytype T[MAXSIZE]; //用结构数组T存储统计结果 for(i=1;i<=S[0];i++) { c=S[i];j=0; while(T[j].ch&&T[j].ch!=c) j++; //查找当前字符c是否已记录过 if(T[j].ch) T[j].num++; else T[j]={c,1}; }//for for(j=0;T[j].ch;j++) printf("%c: %d\n",T[j].ch,T[j].num); }//StrAnalyze 4.19 void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r { r[0]=0; for(i=1;i<=s[0];i++) { c=s[i]; for(j=1;jt[0]) r[++r[0]]=c; } }//for }//Subtract_String 4.20 int SubString_Delete(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数 { for(n=0,i=1;i<=s[0]-t[0]+1;i++) { for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++); if(j>m) //找到了与t匹配的子串 { for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]]; //左移删除 s[0]-=t[0];n++; } }//for return n; }//Delete_SubString 4.21 typedef struct{ char ch; LStrNode *next; } LStrNode,*LString; //链串结构 void StringAssign(LString &s,LString t)//把串t赋值给串s { s=malloc(sizeof(LStrNode)); for(q=s,p=t->next;p;p=p->next) { r=(LStrNode*)malloc(sizeof(LStrNode)); r->ch=p->ch; q->next=r;q=r; } q->next=NULL; }//StringAssign void StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在. { for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next) { p->ch=q->ch;pre=p; } while(q) { p=(LStrNode*)malloc(sizeof(LStrNode)); p->ch=q->ch; pre->next=p;pre=p; } p->next=NULL; }//StringCopy char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,snext,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next); if(!p&&!q) return 0; else if(!p) return -(q->ch); else if(!q) return p->ch; else return p->ch-q->ch; }//StringCompare int StringLen(LString s)//求串s的长度(元素个数) { for(i=0,p=s->next;p;p=p->next,i++); return i; }//StringLen LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针 { p=malloc(sizeof(LStrNode)); for(q=p,r=s->next;r;r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for //复制串s for(r=t->next;r;r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for //复制串t q->next=NULL; return p; }//Concat LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串 { p=malloc(sizeof(LStrNode));q=p; for(r=s;start;start--,r=r->next); //找到start所对应的结点指针r for(i=1;i<=len;i++,r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; } //复制串t q->next=NULL; return p;

2005年－2006学年第二学期“数据结构”考试试题(A)

姓名 学号（序号）_ 答案隐藏 班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号.

一、单项选择题(每小题2分,共20分）

1．数据的运算a 。

A.效率与采用何种存储结构有关 B.是根据存储结构来定义的

C。有算术运算和关系运算两大类 D.必须用程序设计语言来描述

答：A。

2. 链表不具备的特点是 a .

A.可随机访问任一结点 B。插入删除不需要移动元素

C。不必事先估计存储空间 D。所需空间与其长度成正比

答：参见本节要点3。本题答案为：A。

3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O（1) B.O（log2n)

C。O(n） D.O(n2)

答：C。

4．以下线性表的存储结构中具有随机存取功能的是 d 。

A。 不带头结点的单链表 B. 带头结点的单链表

C. 循环双链表 D。 顺序表

解 D。

5。 一个栈的进栈序列是a，b，c,d，e，则栈的不可能的输出序列是 c .

A.edcba B.decba