第一篇:数据结构经典题目及c语言代码总结
《数据结构》课程设计题目(程序实现采用C语言)
题目1:猴子选王(学时:3)
一堆猴子都有编号,编号是1,2,3...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。
要求:m及n要求从键盘输入,存储方式采用向量及链表两种方式实现该问题求解。
//链表
#include
typedef struct _RingNode
{
int pos;
struct _RingNode *next;}RingNode, *RingNodePtr;
// 创建约瑟夫环,pHead:链表头指针,count:链表元素个数 void CreateRing(RingNodePtr pHead, int count){
RingNodePtr pCurr = NULL, pPrev = NULL;
int i = 1;
pPrev = pHead;
while(--count > 0)
{
pCurr =(RingNodePtr)malloc(sizeof(RingNode));
i++;
pCurr->pos = i;
pPrev->next = pCurr;
pPrev = pCurr;
}
pCurr->next = pHead;// 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n){
RingNodePtr pCurr, pPrev;
int i = 1;
// 计数
pCurr = pPrev = pHead;
while(pCurr!= NULL)
{
if(i == n)
{
// 踢出环
printf(“n%d”, pCurr->pos);
// 显示出圈循序
pPrev->next = pCurr->next;
free(pCurr);
pCurr = pPrev->next;
i = 1;
}
pPrev = pCurr;
pCurr = pCurr->next;
if(pPrev == pCurr)
{
// 最后一个
printf(“nKing is %d”, pCurr->pos);
// 显示出圈循序
free(pCurr);
break;
}
i++;
} }
int main(){
int n = 0, m = 0;
RingNodePtr pHead = NULL;
printf(“M(person count)= ”);
scanf(“%d”, &m);
printf(“N(out number)= ”);
scanf(“%d”, &n);
if(m <= 0 || n <= 0)
{
printf(“Input Errorn”);
return 0;
}
// 建立链表
pHead =(RingNodePtr)malloc(sizeof(RingNode));
pHead->pos = 1;
pHead->next = NULL;
CreateRing(pHead, m);// 开始出圈
printf(“nKick Order: ”);
KickFromRing(pHead, n);
printf(“n”);
system(“pause”);
return 0;}
//数组做:
#include
void SelectKing(int MonkeyNum, int CallNum);
void main(){
int MonkeyNum;
int CallNum;
/* 输入猴子的个数 */
printf(“Monkey Num = ”);
scanf(“%d”, &MonkeyNum);
/* 输入M的值 */
printf(“Call Num = ”);
scanf(“%d”, &CallNum);
SelectKing(MonkeyNum, CallNum);
}
void SelectKing(int MonkeyNum, int CallNum){
int *Monkeys;// 申请一个数组,表示所有的猴子;
int counter = 0;//计数,当计数为猴子个数时表示选到最后一个猴子了;
int position = 0;// 位置,数组的下标,轮流遍历数组进行报数;
int token = 0;// 令牌,将报数时数到M的猴子砍掉;
// 申请猴子个数大小的数组,把桌子摆上。
Monkeys =(int *)malloc(sizeof(int)* MonkeyNum);
if(NULL == Monkeys)
{
printf(“So many monkeys, system error.n”);
return;
}
// 将数组的所有内容初始化为0,被砍掉的猴子设置为1
memset(Monkeys, 0, sizeof(int)*MonkeyNum);
// 循环,直到选中大王
while(counter!= MonkeyNum)
{
// 如果这个位置的猴子之前没有砍掉,那么报数有效
if(Monkeys[position] == 0)
{
token++;// 成功报数一个,令牌+1,继续报数直到等于M
// 如果报数到M,那么将这个猴子砍去
if(token == CallNum)
{
Monkeys[position] = 1;// 设置为1,表示砍去
counter++;// 计数增加
token = 0;// 设置为0,下次重新报数
// 如果是最后一个猴子,把它的位置打印,这个就是大王了
if(counter == MonkeyNum)
{
printf(“The king is the %d monkey.n”, position+1);
}
}
}
// 下一个猴子报数
position =(position + 1)%MonkeyNum;
}
// 释放内存,开头为所有猴子创建的桌子
free(Monkeys);
return;}
题目2 :字符逆转(学时:3)
从键盘读入一个字符串,把它存入一个链表(每个结点存储1个字符),并按相反的次序将字符串输出到显示屏。
#include
struct node {
struct node *prev;
char c;
struct node *next;};struct node *input(struct node *top);int main(void){ struct node T,*top=&T,*bottom=&T,*p=NULL;T.prev=NULL;T.next=NULL;T.c=' ';bottom=input(top);p=bottom->prev;while(p!=NULL){
printf(“%c”,p->c);
p=p->prev;} return 0;}
struct node *input(struct node *top){
struct node *t;char x;while((x=getchar())!='n'){ top->c=x;t=(struct node *)malloc(sizeof(struct node));top->next=t;t->prev=top;t->next=NULL;t->c=' ';top=top->next;
} }
return top;题目3 :工资核算(学时:3)
设有一个单位的人员工资有如下信息:name、department、base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中;再从paydata取出工资数据并给每个人的base pay增加100元,增加后将工资数据显示于屏幕(每行1人)。
#include
char name[100];char department[100];
int basepay;
int allowance;
int total;}stuff[SIZE];main(){ FILE *fp;
int i;
printf(“Please enter name department basepay allowance:n”);
for(i=0;i scanf(“%s %s %f %f”,&stuff[i].name,&stuff[i].department,&stuff[i].basepay,&stuff[i].allowance); if((fp=fopen(“paydata.dat”,“wb”))==NULL) { printf(“Can't open filen”); return 0;} for(i=0;i if(fwrite(&stuff[i],LENTH,1,fp)!=1) printf(“文件写入出错n”); fclose(fp); if((fp=fopen(“paydata.dat”,“rb”))==NULL) { } printf(“Can't open filen”); printf(“修改过后的结果:n”); for(i=0;i { fread(&stuff[i],LENTH,1,fp); stuff[i].total=stuff[i].basepay+100+stuff[i].allowance; printf(“%-10s%-10s %f %f %fn”,stuff[i].name,stuff[i].department,stuff[i].basepay+100,stuff[i].allowance,stuff[i].total); } fclose(fp);return 0;} 题目4:满足条件的有序表生成(学时:3) 已知三个有序表A、B、C,它们皆由同一类元素构成,现要求对于表A作以下运算而获得有序表D:排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。 #include int a[7],b[5],c[6],d[7]; int i,j,k,t,m;printf(“nPlease enter 7 numbers of A:”);for(i=0;i<7;i++)scanf(“%d”,&a[i]);for(j=0;j<6;j++) for(i=0;i<6-j;i++) if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i<7;i++)printf(“%5d”,a[i]); printf(“nPlease enter 5 numbers of B:”); for(i=0;i<5;i++)scanf(“%d”,&b[i]);printf(“n”);for(j=0;j<4;j++)for(i=0;i<4-j;i++) if(b[i]>b[i+1]){t=b[i];b[i]=b[i+1];b[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i<5;i++)printf(“%5d”,b[i]); printf(“nPlease enter 6 numbers of C:”); for(i=0;i<6;i++)scanf(“%d”,&c[i]); for(j=0;j<5;j++) for(i=0;i<5-j;i++) if(c[i]>c[i+1]){t=c[i];c[i]=c[i+1];c[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i<6;i++)printf(“%5d”,c[i]);printf(“n”); for(i=0;i<5;i++){ for(j=0;j<6;j++){ if(b[i]==c[j]){ for(k=0;k<7;k++){ if(b[i]==a[k]) } } } } a[k]=m; printf(“n”);k=0;for(i=0;i<7;i++) if(a[i]!=m){ } printf(“生成的有序表d为 ”);for(i=0;i printf(“%4d”,d[i]);d[k]=a[i];k++;printf(“n”);} 题目5:一元 多项式的减法(学时:6) 设有两个一元多项式A(x),B(x),请完成运算A(x)+B(x)、A(x)-B(x),要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。 #include struct Polynode { int coef;int exp;Polynode *next;}Polynode,*Polylist;void Polycreate(Polylist head){ } void Polyadd(Polylist polya,Polylist polyb){ Polynode *p,*q,*tail,*temp;int sum;p=polya->next;Polynode *rear,*s;int c,e;rear=head;printf(“请输入多项式的系数项和指数项”);scanf(“%d,%d”,&c,&e);while(c!=0){ } rear->next=NULL;s=(Polynode*)malloc(sizeof(Polynode));s->coef=c;s->exp=e;rear->next=s;rear=s;scanf(“%d,%d”,&c,&e); q=polyb->next;tail=polya;while(p!=NULL&&q!=NULL){ if(p->exp sum=p->coef+q->coef;if(sum!=0){ } else { temp=p;p->coef=sum;tail->next=p;tail=p;p=p->next;temp=q;q=q->next;free(temp); } } } } p=p->next;free(temp);q=q->next;free(temp);else { } tail->next=q;tail=q;q=q->next;if(p!=NULL)tail->next=p;else tail->next=q;void Polysubstract(Polylist polya,Polylist polyb){ Polylist h=polyb;Polylist p=pb->next;Polylist pd;while(p){p->coef*=-1;p=p->next;} pd=Polyadd(pa,h);for(p=h->next;p;p=p->next)p->coef*=-1;return pd; } void PrintPolyn(Polyn P) void printfPolyn(Polynode *head){ Polynode *p=head->next;while(p){printf(“%dx^%d”,p->coef,p->exp);if(p->next)printf(“+”);p=p->next;} } int main(){ Polynode *La,Lb;La=Polycreate();Lb=Polycreate();PrintPolyn(La);printf(“/n”);PrintPolyn(Lb); } printf(“/n”);Polyadd(polya,polyb);printPolyn(polya);return 0; 题目6:床位分配(学时:6) 某客店有N个等级的房间,第k级客房有A(k)个,每个房间有B(k)个单人床,以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时,印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号;分配不成功时,允许更改房间等级,若不更改等级,印出“满客”提示。 #include typedef struct Room { int roomlevel;int roomnum;int bednum;int peoplenum;int bed[N];int sex;char name[10];struct Room *next;}Room;Room *creat(int roomlevel,int room[],int bed[]){ Room *head,*p,*q; int i=1,j,h,num=1; head=(Room *)malloc(sizeof(Room));head->peoplenum=0;q=head;while(i<=roomlevel) { for(j=1;j<=room[i];j++) { p=(Room *)malloc(sizeof(Room)); p->roomlevel=i;p->roomnum=num++; p->sex=-1; for(h=0;h q->next=p; q=p;} i++;} p->next=NULL; p->peoplenum=0; return(head);} void Init(Room *head){ Room *p;int i;p=head;while(p!=NULL){ p->peoplenum=0; p->sex=-1; for(i=0;i p->bed[i]=0; p=p->next;} printf(“nn 操作成功} void Getin(Room *head){ Room *p;n”); int i,s,lev,age;char name[10];int number=0;int bednumber=0;printf(“nn 欢迎使用订房系统 nn”); printf(“请输入性别(1为男,2为女):”); scanf(“%d”,&s);printf(“nn 请输入想入住的房间等级:”);scanf(“%d”,&lev);p=head->next;while(p!=NULL){ if((p->roomlevel==lev)&&((p->sex==s)||(p->sex==-1))){ } for(i=0;i if(p->bed[i]==0){ } if(number!=0)break;number=p->roomnum;bednumber=i+1;p->bed[i]=1;p->sex=s;p->peoplenum++;break; } p=p->next;if(number==0&&bednumber==0) else { head->peoplenum++; printf(“n订单已下,请输入客人信息: n”);printf(“n 满客 n”); printf(“名字:n”);scanf(“%s”,name); printf(“年龄 :n”);scanf(“%d”,&age); printf(“您的订单3:n”); printf(“名字 年龄 性别 到达时间 房间等级 房间号 床位号n”); if(s==1) printf(“%s %d male 11-19 %d %d %dn”,name,age,p->roomlevel,p->roomnum,bednumber); else printf(“%s %d formale 11-19 %d %d %d n”,name,age,p->roomlevel,p->roomnum,bednumber); } printf(“n”); } void Checkout(Room *head){ Room *p;int number,bednumber,i,s;printf(“欢迎使用退房系统:”);printf(“nn 请输入房间号:”);scanf(“%d”,&number);printf(“nn 请输入性别(1为男,0为女):”);scanf(“%d”,&s);printf(“请输入床位号:”);scanf(“%d”,&bednumber);p=head->next;while(p!=NULL){ if(p->roomnum==number) for(i=0;i roomlevel;i++) if(i+1==bednumber){ p->bed[i]=0;p->peoplenum--;if(p->peoplenum<0) p->peoplenum=0; } } } if(p->peoplenum==0) p->sex=-1; printf(“您已退房,欢迎下次光临”);break;p=p->next;void Display(Room *head){ Room *p;int i=0;p=head->next;printf(“nn已订房间查询”);if(head->peoplenum==NULL){ printf(“所有等级房间空房”); return;} while(p->peoplenum!=NULL){ if(p->sex==1) printf(“n 房间号:%d,房间等级:%d,已住人数:%d,住房人性别:男”,p->roomnum,p->roomlevel,p->peoplenum); else printf(“n 房间号:%d,房间等级:%d,已住人数:%d,住房人性别:女”,p->roomnum,p->roomlevel,p->peoplenum); } void main(){ int n,k=1,i,roomlevel,room[10],bed[10],sum=0; Room *head; printf(“请输入房间等级数:n”);printf(“Roomlevel:”);scanf(“%d”,&roomlevel);for(i=1;i<=roomlevel;i++) { printf(“n %d等级房间数:”,i); } printf(“n”);p=p->next; while(i peoplenum) if(p->bed[i]==1) { printf(“,已住床位号:%d”,i+1); i++; } } scanf(“%d”,&room[i]);printf(“n %d房间内床位数:”,i); scanf(“%d”,&bed[i]);sum+=room[i]*bed[i];head=creat(roomlevel,room,bed); while(k==1) { printf(“ n欢迎光临 :n”); printf(“1:订房n2:退房n3:查询n4:退出系统n”); printf(“请输入您的选择:n”); scanf(“%d”,&n); switch(n) { case 1: Getin(head);break; case 2: Checkout(head);break; case 3: Display(head);break; case 4: k=0;break; default : printf(“Error!please input again:”);break; } } } 题目7:文本文件单词的检索及计数(学时:6) 要求编程建立一个文本文件,每个单词不包括空格及跨行,单词由字符序列构成且区分大小写,完成以下功能:统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。 #include }SW; void CreatTextFile(){ char filename[10],ch; FILE*fp; printf(“请输入所用的文件名:”);scanf(“n%s”,filename);fp=fopen(filename,“w”); printf(“请输入一段文字,以$号结束:n”);scanf(“%s”,&ch); while(ch!='$'){ fwrite(&ch,sizeof(ch),1,fp); } scanf(“%c”,&ch); } fclose(fp);void CountWord(){ FILE *fp;SW S,T;char ch;char filename[10]; int i=0,number=0; printf(“输入文本文件名:”); scanf(“%s”,filename);fp=fopen(filename,“r”); printf(“输入要统计计数的单词:”); scanf(“%s”,T.ch); while(!feof(fp)){ ch= fgetc(fp); if(ch==' ') { if(i!=0){ S.ch[i]=' ';i=0; } } } if(strcmp(S.ch,T.ch)==0)number++;else if(ch=='n'){ if(i!=0) } else { } S.ch[i]=ch;i++;{ S.ch[i]=' '; i=0; } if(strcmp(S.ch,T.ch)==0)number++;if(number==0)printf(“单词不在文本中 n”);else printf(“单词%s在文件%s中共出现了%d次:”,T.ch,filename,number); fclose(fp);} void SearchWord(){ FILE*fp;SW S,T;char filename[10]; int i,i_r,line,flag=0;char ch;printf(“n输入文本文件名:”); scanf(“%s”,filename);fp=fopen(filename,“r”);printf(“输入要统计计数的单词:”); scanf(“%s”,T.ch); i=i_r=0;line=1;while(!feof(fp)){ ch=fgetc(fp); if(ch==' ') { if(i!=0) { i_r++;S.ch[i]=' '; i=0; if(strcmp(T.ch,S.ch)==0){ printf(“%s单词第一次出现是在n”,T.ch,line,i_r); %d 行,%d列 flag=1; break; } } } else if(ch=='n') { if(i!=0) { i_r++;S.ch[i]=' '; if(strcmp(T.ch,S.ch)==0){ printf(“%s单词第一次出现是在n”,T.ch,line,i_r); flag=1; break; } i=0;i_r=0;line++; } else { line++;i_r=0; } } else { %d 行,%d列 S.ch[i]=ch;i++;} } if(flag==0) printf(“%s单词不在文本中n”,T.ch); fclose(fp);} int main(){ } CreatTextFile();CountWord();SearchWord(); 题目8:二叉树的遍历(学时:6) 二叉树以lson-rson链接方式存储,以菜单方式设计并完成功能任务:建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度,其中对于中序、后序的遍历运算要求采用非递归方式。 #include b=NULL;else { b=(BTNode *)malloc(sizeof(BTNode)); b->data=ch; b->lchild=CreatBTree();//递归先序建立左子树 b->rchild=CreatBTree();//递归先序建立右子树 } return b;} void PreOrder(BTNode *b)//递归先序遍历二叉树函数 { if(b!=NULL) { printf(“%c ”,b->data); PreOrder(b->lchild); PreOrder(b->rchild); } } void InOrder(BTNode *b)//非递归中序遍历二叉树函数 { BTNode *stack[M],*p;int top=-1;if(b!=NULL){ p=b; while(top>-1||p!=NULL) { while(p!=NULL)//扫描p的所有左结点并入栈 { top++; stack[top]=p; } p=p->lchild;if(top>-1){ p=stack[top];//出栈访问结点 top--;printf(“%c ”,p->data); p=p->rchild;//扫描p的右结点 } } printf(“n”);} } void PostOrder(BTNode *b)//非递归后序遍历二叉树函数 { BTNode *stack[M],*p;int sign,top=-1;if(b!=NULL){ do { while(b!=NULL)// b所有左结点入栈 { top++; stack[top]=b; b=b->lchild; } p=NULL;// p指向栈顶前一个已访问结点 sign=1; //置b为已访问 while(top!=-1 && sign){ b=stack[top];//取出栈顶结点 if(b->rchild==p)//右孩子不存在或右孩子已访问则访问b { printf(“%c ”,b->data); top--;p=b;//p指向被访问的结点 } else { b=b->rchild;//b指向右孩子结点 sign=0;//置未访问标记 } } }while(top!=-1); printf(“n”);} } void change(BTNode *b) //左右子树交换(递归){ BTNode *r;r=(BTNode *)malloc(sizeof(BTNode));int f1=0,f2=0;if(b==0)return; //树为空时,跳出 if(b->lchild){ change(b->lchild); r->lchild=b->lchild; f1++; //有左子树,符号位不为空 } if(b->rchild){ change(b->rchild); r->rchild=b->rchild; f2++; //有右子树,符号位不为空 } if(f1==0)r->lchild=NULL; //否则,给中间变量赋空值 if(f2==0)r->rchild=NULL;if(f1||f2){ b->rchild=r->lchild; //左右子树交换 b->lchild=r->rchild;} } int max(int m,int n){ } if(m>n)return m;else return n;int count(BTNode *b) //计算树高(递归){ if(b==NULL) return 0;else return(1+max(count(b->lchild),count(b->rchild)));} int main() { BTNode *root = NULL; printf(“-----------------二叉树的遍历-----------------nn”); printf(“请按先序递归顺序创建二叉树(结束符 #):n”); root = CreatBTree(); printf(“n递归先序遍历结果:n”); PreOrder(root); printf(“n非递归中序遍历结果:n”); InOrder(root); printf(“非递归后序遍历结果:n”); PostOrder(root); printf(“n树高: %dn”,count(root));printf(“n左右子树交换位置:”); change(root); printf(“n递归先序遍历结果:n”); PreOrder(root); printf(“n非递归中序遍历结果:n”); InOrder(root); printf(“非递归后序遍历结果:n”); PostOrder(root); return 0; 题目9:创建二叉排序树(学时:3) 二叉排序树以lson-rson链接方式存储,编写能够通过键盘输入建立二叉排序树,并在建立完立即在屏幕显示中序遍历结果的程序。 #include typedef struct node { int data;struct node *lchild ,*rchild;}BSTNode,*BSTTree; //二叉排序树的插入(递归算法)void InsertBST(BSTTree *BST , int key){ } if((*BST)==NULL){ } else if((*BST)->data>key)//如果待插入的元素比根结点元素值小 InsertBST(&((*BST)->lchild),key);//插入在根结点的左子树(*BST)=(BSTNode*)malloc(sizeof(BSTNode));(*BST)->data=key;(*BST)->lchild=NULL;(*BST)->rchild=NULL;else InsertBST(&((*BST)->rchild),key);//插入在根结点的右子树上 //创建一棵二叉排序树 BSTTree CreateBSTTree(){ } //中序遍历 void InOrder(BSTTree BST){ if(BST!=NULL){ } InOrder(BST->lchild);printf(“%5d”,BST->data);InOrder(BST->rchild);BSTTree bst=NULL;int x;while(1){ } return bst; scanf(“%d”,&x);if(x==00)break;InsertBST(&bst,x);} void main(){ BSTTree BST; printf(“建立二叉排序树,请输入序列:n”); BST=CreateBSTTree(); printf(“中序遍历后输出的该序列为:”);InOrder(BST); printf(“n”); } 题目10:霍夫曼编码应用(学时:3) 假设一串由大写字母构成的电文,采用霍夫曼规则对其进行编码,以菜单方式设计并完成功能任务:建立霍夫曼树、霍夫曼编码生成、编码文件译码。 #include char ch; int parent,lchild,rchild;}HTNode; typedef struct{ char ch; char bits[n+1]; }CodeNode; typedef struct { char cha;int number;}COUNTER; int Init(HTNode ht[])//初始化函数,为每一个字母信息赋权值 { int i,s=1;COUNTER counter[27];char ch;printf(“请输入字符:n”);scanf(“%c”,&ch);counter[1].cha='A';counter[2].cha='B';counter[3].cha='C';counter[4].cha='D'; counter[5].cha='E';counter[6].cha='F';counter[7].cha='G';counter[8].cha='H';counter[9].cha='I';counter[10].cha='J';counter[11].cha='K';counter[12].cha='L';counter[13].cha='M';counter[14].cha='N';counter[15].cha='O';counter[16].cha='P';counter[17].cha='Q'; counter[18].cha='R'; counter[19].cha='S';counter[20].cha='T';counter[21].cha='U';counter[22].cha='V';counter[23].cha='W';counter[24].cha='X';counter[25].cha='Y';counter[26].cha='Z';for(i=1;i<=26;i++)counter[i].number=0;while(ch!=' '){ switch(ch){ case 'A':counter[1].number++;break;case 'B':counter[2].number++;break;case 'C':counter[3].number++;break;case 'D':counter[4].number++;break;case 'E':counter[5].number++;break;case 'F':counter[6].number++;break;case 'G':counter[7].number++;break;case 'H':counter[8].number++;break;case 'I':counter[9].number++;break;case 'J':counter[10].number++;break;case 'K':counter[11].number++;break;case 'L':counter[12].number++;break;case 'M':counter[13].number++;break;case 'N':counter[14].number++;break;case 'O':counter[15].number++;break; case 'P':counter[16].number++;break; case 'Q':counter[17].number++;break;case 'R':counter[18].number++;break;case 'S':counter[19].number++;break;case 'T':counter[20].number++;break;case 'U':counter[21].number++;break;case 'V':counter[22].number++;break;case 'W':counter[23].number++;break;case 'X':counter[24].number++;break; } } case 'Y':counter[25].number++;break;case 'Z':counter[26].number++;break;} scanf(“%c”,&ch);for(i=1;i<=26;i++){ } s=s-1;return s;if(counter[i].number!=0){ } ht[s].weight=counter[i].number;ht[s].ch=counter[i].cha;s++; void select(HTNode ht[],int q,int *p1,int *p2)//select函数 { int i,j,x=0,y=0;for(j=1;j<=q;++j){ } if(ht[j].parent==0){ } x=j;break;for(i=j+1;i<=q;++i){ } for(j=1;j<=q;++j){ } for(i=j+1;i<=q;++i){ if(ht[i].weight //选出第二小结点 if(ht[j].parent==0&&x!=j){ } y=j;break;if(ht[i].weight //选出最小结点 } } } if(x>y){ } else { } *p1=x;*p2=y;*p1=y;*p2=x;void huffman_setup(HTNode ht[],int s){ int i,a;int p1,p2;a=2*s-1;for(i=1;i<=a;i++){ if(i<=s){ } else { ht[i].weight=ht[i].weight; } } } ht[i].weight=0;ht[i].parent=ht[i].lchild=ht[i].rchild=0;for(i=s+1;i<=a;++i) //建立赫夫曼树 { } select(ht,i-1,&p1,&p2);ht[p1].parent=i;ht[p2].parent=i;ht[i].lchild=p1;ht[i].rchild=p2;ht[i].weight=ht[p1].weight+ht[p2].weight;void huffman_show(CodeNode hc[],HTNode ht[],int s)//给字符编码 { char q[n];int i,p,c,f;q[s-1]=' ';for(i=1;i<=s;i++) { p=s-1;for(c=i,f=ht[i].parent;f;c=f,f=ht[f].parent){ } } if(ht[f].lchild==c){ } else { } q[--p]='1';q[--p]='0';strcpy(hc[i].bits,&q[p]);} hc[i].ch=ht[i].ch;//-----------------编码 void huffman_code(CodeNode hc[]){ int i=1;char ch,ah;printf(“请输入编码的信息:n”);scanf(“%c”,&ch);printf(“编码是:n”);while(ch!=' '){ ah=hc[i].ch;while(ch!=ah){ } i++;ah=hc[i].ch;printf(“%s”,hc[i].bits);scanf(“%c”,&ch);i=1; } } //-----------------解码 void huffman_read(HTNode ht[],int s)//根据编码来返回字母信息 { int i,j,t;char b;t=2*s-1;i=t;printf(“进行解码n”);fflush(stdin);scanf(“%c”,&b);printf(“解码后的信息是:n”);while(b!=' '){ if(b=='0')i=ht[i].lchild;else i=ht[i].rchild;if(ht[i].lchild==0){ } } } printf(“%c”,ht[i].ch);j=i;i=t;scanf(“%c”,&b);int main(){ int flag=1,choice;int s,i;HTNode ht[m];CodeNode hc[n];printf(“霍夫曼树:n”);s=Init(ht);huffman_setup(ht,s);huffman_show(hc,ht,s);for(i=1;i<=s;i++){ } while(flag){ printf(“%c---> %sn”,hc[i].ch,hc[i].bits); } } printf(“请输入您想要进行的操作:n 1 编码n 2 解码n 3 退出n”);fflush(stdin);scanf(“%d”,&choice);switch(choice){ case 1: huffman_code(hc);printf(“n”);break; case 2: } huffman_read(ht,s);printf(“n”);break; case 3: flag=0;return 0;题目11:关键路径寻找(学时:6) 对于给定的一个工程施工图,该图以边为单位从键盘输入,编写能够找出该图的关键路径的程序。 #include #include “stdio.h” #include void main(){ int n=0;struct course *head=NULL;void insert(struct course **head,struct course *cou);void Print(struct course **head,int *n);void Modify(struct course **head,int *n);void Require(struct course **head);void Creat(struct course **head,int *n);void Delete(struct course **head,int *n);void Fun(struct course **head,int *n); Fun(&head,&n);} void insert(struct course **head,struct course *cou){ struct course *p0,*p1,*p2;p2=p1=*head;p0=cou;if(*head){ while((p0->semester>p1->semester)&&(p1->next)) { p2=p1; p1=p1->next; } if(p0->semester semester) { if(*head==p1)*head=p0; else p2->next=p0; p0->next=p1;} else { if(p0->semester==p1->semester){ while((p0->cID>p1->cID)&&(p1->next)&&(p0->semester==p1->semester)) { } if(p0->semester!=p1->semester){ } else { if(p0->cID<=p1->cID){ if(*head==p1)*head=p0;else p2->next=p0;p2=p1;p1=p1->next;p2->next=p0;p0->next=p1; p0->next=p1; } else {p1->next=p0;p0->next=NULL;} } } else {p1->next=p0;p0->next=NULL;} } } else { *head=p0; p0->next=NULL;} } void Print(struct course **head,int *n){ struct course *p;p=*head;if(*head){ if(*n==1)printf(“nThis %d record is:n”,*n); else printf(“nThese %d records are:n”,*n); printf(“semester cID name creditn”); do { printf(“%-10d%-10d%-18s%-12.1f n”,p->semester,p->cID,p->name,p->credit); p=p->next; }while(p!=NULL);} else printf(“nList null!n”);} void Modify(struct course **head,int *n){ struct course *p,*p2;int cID;if(*head){ Print(head,n);while(1){ printf(“nPlease input the cID which you want to modify:”); scanf(“%d”,&cID);p2=p=*head;while(p->next&&(cID!=p->cID)){ p2=p; p=p->next;} if(cID==p->cID){ printf(“Please input the new cID(1~60):”); scanf(“%d”,&p->cID); while(p->cID<0||p->cID>60) { printf(“nError!”); printf(“nPlease input the new cID(1~60):”); scanf(“%d”,&p->cID); } printf(“Please input the new semester(1~8):”); scanf(“%d”,&p->semester);while(p->semester<0||p->semester>8) { printf(“nError!”); printf(“nPlease input the new semester(1~8):”); scanf(“%d”,&p->semester); } printf(“Please input the new credit:”); scanf(“%f”,&p->credit); printf(“Please input the new name:”); scanf(“%s”,p->name); if(p==*head)*head=p->next; else p2->next=p->next; insert(head,p); break; } else printf(“%d not been found!n”,cID); } } else {printf(“nList null!n”);} } void Require(struct course **head){ struct course *p;float sum=0;int sem,i=0;printf(“nPlease input the semester which is required:”); scanf(“%d”,&sem);p=*head;while(p){ if(sem==p->semester) { i++;if(i==1)printf(“nsemester cID name creditn”);printf(“%-10d%-10d%-18s%-12.1f n”,p->semester,p->cID,p->name,p->credit); sum=sum+p->credit; } p=p->next;} printf(“The sum of credit in this term is:%.1fn”,sum);} void Creat(struct course **head,int *n){ struct course *p1;while(1){ p1=(struct course *)malloc(LEN); printf(“Please input the cID(1~60):”); scanf(“%d”,&p1->cID); while(p1->cID<0||p1->cID>60) { printf(“nError!”); printf(“nPlease input the cID(1~60):”); scanf(“%d”,&p1->cID); } if(p1->cID==0)break; printf(“Please input the semester(1~8):”); scanf(“%d”,&p1->semester); while(p1->semester<0||p1->semester>8) { printf(“nError!”); printf(“nPlease input the semester(1~8):”);scanf(“%d”,&p1->semester); } } } printf(“Please input the credit:”);scanf(“%f”,&p1->credit);printf(“Please input the name:”);scanf(“%s”,p1->name);insert(head,p1);*n=*n+1;printf(“nYou can continue until the cID is ”0“!n”);Print(head,n);void Delete(struct course **head,int *n){ struct course *p1,*p2;int cID;Print(head,n);if(*head){ printf(“Please input the cID of the course which you want to delete:”);scanf(“%d”,&cID);p1=*head; while(cID!=p1->cID&&p1->next!=NULL) { p2=p1; p1=p1->next; } if(cID==p1->cID) { if(p1==*head)*head=p1->next; else p2->next=p1->next; printf(“Have delete cID:%dn”,cID); *n=*n-1; } else printf(“%d not been found!n”,cID);} } void Fun(struct course **head,int *n){ char num; while(1) { system(“cls”); puts(“**************** Main Menu ******************”); puts(“* 1.Add Records 2.Print Records *”); puts(“* 3.Delete Records 4.Modify Records *”); puts(“* 5.Require Records 6.Exit *”); printf(“Please input your choice: ”); scanf(“%d”,&num); switch(num) { case 1:Creat(head,n);break; case 2:Print(head,n);break; case 3:Delete(head,n);break; case 4:Modify(head,n);break; case 5:Require(head);break;case 6:exit(0);break; default: break; } printf(“nPress ”Enter“ to continue!”);getchar();getchar(); } } 求两个数之和。在两种情况下完成: ①数据在程序内部定义变量时赋初值,或者通过赋值语句赋值。②数据通过scanf()函数输入。静态输入: #include #include 设圆半径r=1.5,圆柱高h=3,求圆周长、圆面积、圆柱表面积、圆柱体积。要求用scanf 输入数据,输出计算结果。#include l=%6.2fn”,l);printf(“圆的面积为 s=%6.2fn”,s);printf(“圆柱的表面积为 sq=%6.2fn”,sq);printf(“圆柱的体积为 vz=%6.2fn”,vz);} 输入a、b、c三个整数,求出其中最大者,并连同三个源数据一起输出。#include if(x>z) max=x; else max=z;} else { if(y>z) max=y; else max=z;} return(max);} void main(){ int max(int x,int y,int z); int a,b,c,w; printf(“请您输入三个整数:”); scanf(“%d,%d,%d”,&a,&b,&c); printf(“您输入的三个数是:%d,%d,%dn”,a,b,c); w=max(a,b,c); printf(“这三个数中最大的是:%dn”,w);} 给出一个百分制成绩,要求输出成绩等级A、B、C、D、E。90分以上为A,80-89分为B,70-79分为C,60-69分为D,60分以下为E。要求输入一个成绩并打印出对应的等级制成绩。要求用switch语句完成。#include printf(“您输入了一个错误的成绩!请重新输入n”); scanf(“%d”,&grade);} c=grade/10;switch(c){ case 10: case 9: grade='A';break;case 8: grade='B';break;case 7: grade='C';break;case 6: grade='D';break;default: grade='E';} printf(“您输入的成绩的等级为:%Cn”,grade);} 计算当n为何值时,不等式sum=1 + 1/2 + 1/3 +… + 1/n >limit成立,输出n对应的sum(limit从键盘输入,要求用while、或do...while 语句,limit=10)。#include n++; sum=sum+1/n;} printf(“此时sum的值是:%fn”,sum);printf(“此时n的值为%fn”,n);} 计算M=11+ 22+ 33+…+ NN,直到N等于15为止,输出N和对应的M。(要求用for语句做) #include M=M+(n+10*n);} for(n=10;n<=15;n++){ M=M+(n+100*n);} n--;printf(“当n是%d时,M的值为%fn”,n,M);} 100匹马驮100担货,大马一匹驮3担,中马一匹驮2担,小马一匹驮0.5担,计算大、中、小马数目并输出。#include for(small=0;small<100;small+=2) for(mid=0;mid<50;mid++) { if(3*big+2*mid+small/2==100&&big+mid+small==100) { printf(“big:%dt,mid:%dt,small:%dn”,big,mid,small); sum++; } } printf(“一共有%d种组合方式n”,sum);} 求 sum=1!+2!+3!+...+10!,并输出结果。#include t=t*n; s=s+t;} printf(“1!+2!+3!+...+10!的和是:%en”,s);} 注意该程序的结果为:1!+2!+3!+...+10!的和是:4.037913e+006 是以科学计数法表示的结果,因为int的定义范围只能以此表示,如果用long int来输出,则可以得到正常表示的结果 #include t=t*n; s=s+t;} printf(“1!+2!+3!+...+10!的和是:%ldn”,s);} 1!+2!+3!+...+10!的和是:4037913 设数列为1,3,5,7,9,11,13,15,17,19,动态输入在数组array中,然后顺序打印输出该数列,再逆序打印输出该数列。#include scanf(“%d”,&array[i]);printf(“您输入的10个整数的顺序排列是:n”);for(i=0;i printf(“%-4d”,array[i]);printf(“n”);printf(“您输入的10个整数的逆序排列是:n”);for(i=N-1;i>=0;i--) printf(“%-4d”,array[i]);printf(“n”);} 将3x3阶二维数组的关于主对角线对称的元素互换。二维数组的第1至3行元素分别为1、2、3、4、5、6、7、8、9。用矩阵形式分别输出互换前、后的数组元素值。#include for(j=0;j<3;j++) printf(“%5d”,array[i][j]); printf(“n”);} for(i=1;i<3;i++) for(j=0;j { t=array[i][j]; array[i][j]=array[j][i]; array[j][i]=t; } printf(“After Exchanged:n”); for(i=0;i<3;i++) { for(j=0;j<3;j++) printf(“%5d”,array[i][j]); printf(“n”); } } 定义两个字符数组s1、s2,并用赋初值的方法把两个字符串“Computer”和“Language” 分别存放到s1、s2中,要求不用库函数strcat(),把s2连接到s1的尾部,然后以%s格式输出连接后的字符串s1。#include char s1[80],s2[40]; int i=0,j=0; printf(”input string1:“); scanf(”%s“,&s1); printf(”input string2:“); scanf(”%s“,&s2); while(s1[i]!=' ') i++; s1[i]=' '; i++; while(s2[j]!=' ') s1[i++]=s2[j++]; s1[i] = ' '; printf(”The new string is:%sn“,s1);} 用赋初值的方法把字符串”C is a general purpose, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system.“存放到字符数组s中,编程统计其中的大写字母、小写字母、数字、空格、逗号的个数。#include char s[512] = ”C is a general purpose, procedural, imperative “ ”computer programming language developed in 1972 by Dennis“ ”Ritchie at the Bell Telephone Laboratories for use with “ ”the Unix operating system.“;int upper=0,lower=0,digit=0,space=0,comma=0;int i=0;while(s[i]) { if(s[i]>='A'&&s[i]<='Z')upper++; if(s[i]>='a'&&s[i]<='z')lower++; if(s[i]>='0'&&s[i]<='9')digit++; if(s[i]==' ')space++; if(s[i]==',')comma++; i++; } printf(”这串字符串有大写字母%d个,小写字母%d个,数字%d个,空格%d个,逗号%d个n“,upper,lower,digit,space,comma);} 试从主函数输入10个数据到数组中,编写对偶数项求和的子函数,它将计算结果返回给主函数,由主函数输出。#include int i,s;s=0; for(i=1;i s=s+a[i]; return(s);} void main(){ int a[10];int i,s;printf(”请您在数组内输入10个数:“);for(i=0;i<10;i++) scanf(”%d“,&a[i]);s=oqh(a,10);printf(”这个数组的偶数项的和是:%dn“,s);} 注意:oqh并无其他含义,是本人定义的一个函数名,偶数项求和的缩写。编写一个判断素数的程序,其中主函数用于完成输入一个整数并给出判断结果,单独编写一个函数用于判断其参数是否为素数,其返回值为1表示为素数,为0表示为非素数。#include if(n%i==0) { m=0; break; } if(i>t) m=1; else continue;} return(m);} void main(){ int n;int i;printf(”请输入你要判断的数:n“);scanf(”%d“,&n);while(n<=1){ printf(”您输入了一个错误的数据,请重新输入:n“); scanf(”%d“,&n);} if(prime(n)) printf(”您输入的是一个素数n“);else printf(”您输入的不是一个素数n“); } 输入三个整数,按由小到大的顺序输出。(要求使用指针来排序输出)#include t=*a; *a=*b; *b=t;} if(*a>*c){ t=*a; *a=*c; *c=t;} if(*b>*c){ t=*b; *b=*c; *c=t;} } void main(){ int a,b,c;printf(”请您输入三个整数:“);scanf(”%d %d %d“,&a,&b,&c);sort(&a,&b,&c);printf(”它们由小到大的排列顺序是:%d %d %dn“,a,b,c);} 或者是 #include void swap(int *p1,int *p2); int a,b,c; int *p1,*p2,*p3; printf(”请您输入三个整数:“); scanf(”%d %d %d“,&a,&b,&c); p1=&a; p2=&b; p3=&c; if(a>b)swap(p1,p2); if(a>c)swap(p1,p3); if(b>c)swap(p2,p3); printf(”它们由小到大的排列顺序是:%d %d %dn“,a,b,c);} void swap(int *p1,int *p2){ int p; p=*p1; *p1=*p2; *p2=p;} 输入十个整数,放在数组list中,然后用指针法从后向前输出该数组中的整数。#include int list[10],i,*p=list; printf(”请您输入10个整数:n“); for(i=0;i<10;i++) scanf(”%d“,&list[i]); printf(”这10个整数的逆序序列是:n“); for(i=9;i>=0;i--) printf(”%-4d“,*(p+i));} 如果输入的数字个数不定的情况,下面的代码可行 #include scanf(”%d“,&list[i]);p=&list[0];sort(p,n);printf(”这%d个整数的逆序序列是:n“,n);for(i=0;i printf(”%-4d“,list[i]);printf(”n“);} void sort(char *p,int m){ int i;char t,*p1,*p2;for(i=0;i p1=p+i; p2=p+(m-1-i); t=*p1; *p1=*p2; *p2=t;} } 编写一个函数,它能对一个字符串(“I am a student”)测出长度,要求函数的形参是一个指针变量,函数返回值是字符串的长度。#include n++; p++;} //*p=' ';//n++;return(n);} 若要统计结果包含结束符,则启用*p=' ';n++;两条语句 编一个函数cstrcmp实现两个字符串的比较,具体为: int cstrcmp(char *p1, char *p2)p1,p2分别指向字符串s1,s2;若s1=s2则函数返回0;若s1>s2,则函数返回1;若s1 return 0;} if(strcmp(p1,p2)>0){ return 1;} if(strcmp(p1,p2)<0){ return-1;} } void main(){ char *a;char *b;input();printf(”这两个字符串比较的结果是:%dn“,cstrcmp(a,b));} 如果要求返回的是不相同字母的ASCII码值: #include if(*(p1+i++)==' ')return(0); return(*(p1+i)-*(p2+i));} 有5个学生,每个学生的数据包括学号、姓名、3门课的成绩,用赋初值的方法输入5个学生的数据到结构体数组中,输出每个学生3门课的平均成绩。#include { char num[6]; char name[8];int score[3];float avr;}stu[5]={{”101“,”Zhou“,93,89,87},{”102“,”Yang“,85,80,78},{”103“,”Chen“, 77,70,83},{”104“,”Qian“,70,67,60},{”105“,”Li“,72,70,69}};void main(){ int i,j,sum;for(i=0;i<5;i++) { sum=0; for(j=0;j<3;j++) sum+=stu[i].score[j]; stu[i].avr=sum/3.0;} printf(”number name score1 score2 score3 averagen“);for(i=0;i<5;i++){ printf(”%3s%10s“,stu[i].num,stu[i].name); for(j=0;j<3;j++) printf(”%7d“,stu[i].score[j]); printf(”%10.2fn“,stu[i].avr);} } 如果按平均成绩由高到低排序后,输出每个学生的成绩 #include { char num[6]; char name[8]; int score[3];float avr; }stu[5]={{”101“,”Zhou“,93,89,87},{”102“,”Yang“,85,80,78},{”103“,”Chen“, 77,70,83},{”104“,”Qian“,70,67,60},{”105“,”Li“,72,70,69}},temp;void main(){ int i,j,sum; for(i=0;i<5;i++){ sum=0; for(j=0;j<3;j++) sum+=stu[i].score[j]; stu[i].avr=sum/3.0;} for(i=0;i<4;i++) for(j=i;j<4;j++) if(stu[j].avr { temp=stu[j]; stu[j]=stu[j+1]; stu[j+1]=temp; } printf(”number name score1 score2 score3 averagen“); for(i=0;i<5;i++) { printf(”%3s%10s“,stu[i].num,stu[i].name); for(j=0;j<3;j++) printf(”%7d“,stu[i].score[j]); printf(”%10.2fn",stu[i].avr); } } C语言课程设计参考题目 一、矩阵运算 矩阵的加法、减法、转置、数乘矩阵、交换矩阵行或列、两个矩阵作乘法、求矩阵的秩、求可逆矩阵的逆矩阵、特殊矩阵(如对称矩阵、反对称矩阵、三角形矩阵)的运算。 二、级数和数列运算 求无穷级数的和(①从第一项累加到给定的项数时为止,②当一般项的值变化到满足某一条件时为止,③当累加的级数的和满足某一条件时为止。对于正项级数和交错级数,都能计算。);求无穷级数的某一项的值(①按给定项数求值;②按给定满足的条件求值)。 求数列的前n项之和(①等差数列前n项之和;②等比数列前n项之和);计算并显示数列各项的值(①截止到第n项为止;②截止到满足给定的条件为止);求等差中项和等比中项。 三、统计与计算 求N个整数的和、平均值、最大公约数、最小公倍数、方差、标准差等。求N个数中的最大值、最小值、出现次数最多的值、出现次数最少的值。 对一组整数进行分类统计(自行设定分类统计标准。例如,对于一组在0到100之间的数,可以这样分类统计:小于或等于100且大于等于90的有多少,小于90且大于等于80的有多少,小于80且大于等于70的有多少,小于70且大于等于60的有多少,小于60的有多少)。给定N个数,计算并显示这N个数的各种排列和组合。 判断某整数是否是素数,求某范围内的所有素数。将某整数分解成若干素数乘积的形式。 四、排序和查找运算 将给定的N个数排序(①升序;②降序,分别用选择法和冒泡法)。 将给定的N个单词排序(①升序;②降序,分别用选择法和冒泡法)。将给定的N个英文句子排序(①升序;②降序,分别用选择法和冒泡法)。 运用顺序查找法,在一组数中查找给定的数。运用两分查找法,在一组数中查找给定的数。在一组数中查找到给定的数之后,用另一个数将其替换或删除。在一组有序数中,插入某个数,使插入后仍是一组有序数。 将一组数以中间对称的形式交换位置,然后输出。 五、求方程近似根和积分运算 求一元二次方程的根。用牛顿法求某个一元高次方程的近似根。用二分法求某个一元高次方程的近似根。用弦截法求某个一元高次方程的近似根。 求线性方程组的解。 用矩形法求某个函数定级分。用梯形法求某个函数定级分。 六、对英文单词和句子运算 分别统计一个英文句子中大写字母、小写字母、数字、空格的个数。求某个字母在一个英文句子中出现的位置。统计一个英文句子中所包含单词的个数。统计一个英文句子中最长的单词所含字母个数。统计某个单词在一个英文句子中出现的次数。将一个单词从英文句子中删除,显示删除单词后的英文句子。将一个单词插入到英文句子的指定位置,显示插入单词后的英文句子。用一个单词替换英文句子中的另一个单词。比较两个英文句子的不同点,输出不同点的位置。 七、画图案 画各种三角形图案。画各种菱形图案。画各种平行四边形图案。画各种梯形图案。画各种正多边形图案。(以上图案包括空心的或实心的两种。要采用两种方法画一种图案:①用二维数组;②只用循环不用二维数组。不能全用二维数组画!) 用以上几种基本图案组合成一个新图案。 八、商品信息管理系统 每件商品信息包括编号、商品名、类型、生产厂家、生产日期、单价、库存量等项内容,本系统可以实现如下功能:往系统里添加新商品的各项信息;修改现有商品的各项信息;查找并显示满足某条件的商品的信息;按某个给定的条件将商品排序并显示排序结果;统计满足某条件的商品的库存量;计算某种商品的总价值(单价乘库存量),以及某几种商品的总价值。 九、优秀歌手比赛评分系统 比赛共有M个歌手参赛,共有N个评委为歌手打分。每次评分,由N个评委每人给歌手一个分数,然后去掉一个最高分,去掉一个最低分,求出其余N-2个分数的平均分,作为歌手的得分。本系统可以实现如下功能:按评委给分顺序显示某个参赛歌手的得分;显示某个参赛歌手所得的最高分和最低分;求出每个参赛歌手的得分;按参赛歌手的得分从高到低排序并显示排序结果;显示某个评委打出的M个分数;计算某个评委打分的平均值;查找满足给定得分范围的歌手。 十、工资管理系统 某单位有N个,职工工资信息包括基本工资、岗位津贴、地方津贴、奖金、扣公积金、扣税、实发工资等项内容,将N个职工的这些内容存入本系统。可以利用本系统实现如下功能:往系统里添加新的职工工资信息内容;根据给定的条件修改现有的职工工资内容;删除某个职工工资内容;根据给定的条件查找并显示某个职工工资内容;显示符合某个条件的所有职工工资内容;统计某项工资内容的总和;计算某个职工的实发工资(基本工资+岗位津贴+地方津贴+奖金-扣公积金-扣税);计算符合某个条件的所有职工的实发工资总和。 十一、学生成绩管理系统 该班共有N个学生,共开M门课,将已经结束的每门课的成绩存入本系统,将学生的学号和姓名存入本系统。可以利用本系统实现如下功能:往系统里添加新的课程成绩;根据给定的条件修改现有的课程成绩;删除某个学生的学号、姓名和各门课的成绩;根据给定的学生的学号和姓名,查找并显示该学生各门课的成绩;计算所有学生某门课的平均分;计算某个学生各门课的平均分;按每个学生得总分从高到低排序并显示排序结果。 十二、职工档案管理系统 某单位有N个职工,每个职工有编号、姓名、性别、出生日期、毕业学校、电话号码、职务等项内容,将N个职工的这些内容存入本系统。可以利用本系统实现如下功能:往系统里添加新的职工档案内容;根据给定的条件修改现有的职工档案内容;删除某个职工档案内容;根据给定的条件查找并显示某个职工档案内容;显示符合某个条件的所有职工档案内容;统计满足某个条件的职工人数;按某个给定的条件将职工排序并显示排序结果。 十三、图书信息管理系统 每本图书信息包括编号、书名、作者、出版社、出版日期、单价、册数等项内容,本系统可以实现如下功能:往系统里添加新图书的各项信息;修改现有图书的各项信息;查找并显示满足某条件的图书的信息;按某个给定的条件将图书排序;统计满足某条件的图书的册数;计算某种图书的总价值(单价乘册数),以及某几种图书的总价值。 十四、运动会分数统计系统 共有M个运动代表队,每个代表队参加N项比赛。每项比赛的第1名得10分、第2名得8分、第3名得5分,其它名次不得分。输入每项比赛的代表队排名。本系统可以实现如下功能:统计各代表队所得的总分;将各代表队按总分值从高到低排序,然后显示输出;查找某个代表队参加某项比赛的成绩并显示;查找某个代表队的总分和各项比赛的得分并显示;查找某项比赛取得某个名次得代表队名称。 第一章 绪论 数据结构:数据结构就是数据的组织形式,也可看成是包含数据结构的数据表,说明数据之间存在着一定的相互关系或约束。数据结构被形式地定义为(D,R),其中D是数据元素的有限集合,R是D上的关系有限集合.数据类型:一个值的集合和定义在这个值集上的一组操作的总称;数据运算:对数据施加的一种操作;数据结构和数据类型两个概念之间区别:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了一组操作。 逻辑结构:我们把只表现元素之间逻辑关系,而不涉及它们在计算机中的表示,只是理论的、反映在纸面上的东西,这种抽象的数据结构称为逻辑结构。 物理结构:抽象的数据结构在计算机内的表示,也就是映射在存储空间上的、具体的数据结构在计算机内表示,也就是映射在存储空间上的、具体的数据结构。 数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称;数据元素:数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是数据的最小单位。 数据对象:性质相同的数据元素的集合,是数据的一个子集。 数据结构:是相互之间一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性。数据结构包括逻辑结构(线性结构,如线性表,栈,队,串,数组 和非线性结构如 树结构、图结构)、物理(存储)结构(集合、线性结构、树形结构和图状结构或网状结构)和数据运算如插入、删除、修改、排序、查找。数据结构中,与所使用的计算机无关的数据叫逻辑结构,数据结构在计算机内存中的表示是指数据的存储结构 四大类存储结构:顺序存储、链式存储、索引存储和散列存储。顺序存储包括数据存储(把逻辑上相邻的元素存储在地址连续的存储单位)和数据关系存储(通过连续的物理地址体现关系);链式存储包括数据存储(把逻辑上相邻的元素存放在物理地址随意的存储单元)和数据关系存储(不仅存放数据本身还存放数据元素的物理地址) 抽象数据类型ADT:一个数学模型以及定义在该模型上的一组操作,包括_数据和操作_两个部分 算法的特性:有穷性(执行有穷步结束)、确定性(确切含义,不会产生二义性)、可行性、输入(零个或多个输入)和输出(一个或多个输出) 算法设计的要求:正确性、可读写、健壮性、效率与低存储量需求。 2、数据的逻辑结构是指图形结构_三种类型,树形结构和图形结构合称为非线性结构_。数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构4种。 17_称为存储结构.1821、算法的执行时间是 371、某算法的时间复杂度为O(n2),表明该算法的_____.2.算法分析的目的是问题规模之间的关系;算法分析的两个主要方面是空间复杂度和时间复杂度 5.在决定选取何种存储结构时,一般不考虑 A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.编程语言实现这种结构是否方便。 10.程序段i = 0;while(i<=n){i = i * 3 12数据项的个数要相同,而且对应的数据项的类型要一致 1.数据结构是一门研究非数值计算的程序设计问题中计算机的系和运算等的学科。数据结构式相互之间存在一种或多种特定关系的数据元素的集合。10.数据的运算最常用的有5-1- 第二章 线性表 1.线性表:一个线性表是n个类型相同的数据元素的有限序列。线性表的顺序表示:用一组地址连 续的存储单元依次存储线性表的数据元素。顺序存储结构的特点:优,可随机存取表中任一元素,方便快捷;缺,再插入或删除时,需移动大量元素,数组的静态空间分配。 2.线性结构与非线性结构的不同点:线性结构反映结点间的逻辑关系是 一对一的,非线性结构反 映结点间的逻辑关系是多对多的。 3.从一个具有n个节点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较个结点,4.在一个单链表中,已知*q结点是*p结点的前驱结点,若在*q和*p之间插入*s结点,则执行 5.对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的,删除一个 元素时大约要移动表中的(n-1)/2两种情况下求平均个元素。 6.设单链表中指针p指着结点m,指针f指着将要插入的新结点x,当x插在链表中最后一个结点 m之后时,只要先修改后修改p->link=f即可。 7.在一个长度为n的顺序存储的线性表中,删除第i个元素(1<=i<=n)时,需要从前向后依次前移i个元素前插入元素需移动 存储结构需要分配较大空间,插入和删除不需要移动元素的线性表 9、在双向链表存储结构中,删除p所指的结点时需修改指针p所指的结点的前趋结点(若存在)时需修改指针 1.在循环双链表的p所指结点之前插入s所指结点的操作是12.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用_结点的双循环链表__存储方式最节省运算时间;某线性表最常用的操作是在最后一个结点之后插 入一个结点或删除第一个结点,故采用_仅有尾指针的单循环链表存储方式最节省运算时间;对 于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为用尾指针表示的循环单链表 14.15.16.17、不带头结点的单链表head为空的判定条件是 带头结点的~是 19、带头结点的双循环表L为空表的条件是。 20、非空的循环单链表head的尾结点(由p所指向)满足21.在一个长度为n(n>1)操作与链表的长度有关;与单链表相比,双链表的优点之一是顺序访问相邻结点更灵活 23线性表的链接存储中,元素之间的逻辑关系是通过链接指针决定的。 24、从顺序表中删除第i个元素时,首先把第i个元素赋给_针开始向后的所有元素均前移一个位置,最后使线性表的长度减1。 25,26、循环单链表L为空的条件是 27、在以HL为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件分别为。 28、在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为,若p为一个数组a中的下标,则其后继结点的下标的a[p].next。 29、在由数组a中元素结点构成的单链表中,在下标为i的结点的后面插入一个下标为j的结点 时,需要进行的操作为a[j].next=a[i].next和a[i].next=j语句。 第三章 栈和队列 1.栈:是限定仅在表尾进行插入或删除操作的线性表。栈又称为先进后出LIFO的线性表。 2.判定一个栈ST(最多元素为m0)为空的条件是 2.栈的两种存储方法:一是顺序栈,即栈的顺序存储结构是利用一组地址连续的存储单元依次存 放自栈底到栈顶的元素;二是栈的链式表示。 3.队列:队列是一种先进先出FIFO的线性表。允许插入的一端叫做队尾rear,允许删除的一段则 称为队头front 4.链队的出队入队操作:s入队,rear->next=s;rear=s;p出队:front->next=p->next 5.顺序队:插入元素:front不变,rear加1;删除元素:rear不变,front加1。判定一个顺序栈 st(最多元素为MaxSize)为空的条件是6.循环队列:空队满队都是rea=r=front为区分,规定循环队列中剩一个元素即为满队,front=rear+1 7.8.9.向一个栈项指针为hs的链栈中插入一个*s结点时,则执行。 10.在一个链队列中,假定front和rear分别为队首指针和队尾指针,则进行插入*s结点的操作时 应执行rear->next=s;rear=s; 11.若己知一个栈的进栈序列是1,2,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi(1 23、判定一个环形队列qu(最多元素为MaxSize)为空的条件是是(qu->rear+1)%MaxSize==qu->front 列的元素个数是(rear-front+MaxSize)%MaxSize。 24.从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行5.栈顶指针 7.在链表qu中,判定只有一个结点的条件是设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为3。 9.设计一个判别表达式中左、右括号是否配对出现的算法,采用数据结构最佳 例:设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆 列车开出车站的所有可能的顺序。 答:至少有14种①全进之后再出情况,只有1种:4,3,2,1②进3个之后再出的情况,有 3种,3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况,有5种,2,4,3,12,3,4,12,1, 3,4 2,1,4,32,1,3,4④进1个之后再出的情况,有5种,1,4,3,21,3,2,41,3,4,21, 2,3,41,2,4,3 第四章 串 1.串:由零个或多个字符组成的有限序列;串中字符的数目n称为串的长度,零个字符的串称为 空串。包含子串的串相应的称为主串,通常称字符在序列中的序号为该字符在串中的位置。 2.空串是,其长度等于度等于其包含的空格个数。组成串的数据元素只能是 单个字符。 4.一个字符串中称为该串的子串。 5.若串S= ‘software’,其子串的数目是字符串长度为n的字串的个数计算公式 :[n+(n-1)+...+ 1+1]) 60.串是一种特殊的线性表,其特殊性体现在61.设有两个串p和q,求q在p中首次出现的位置的运算称为 串:1。KMP算法,求NEXT函数值等。时间:O(n+m)。其中,模式匹配为O(n);预处理为 O(m);求两串的最长公共子串,时间为O(n)是不行的,至少要O(n2)。 第五章 数组(线性结构,元素受限,操作不限)和广义表 1.矩阵的压缩存储:是指为多个值相同的元只分配一个存储空间,对零元不分配空间。 2.树的存储结构: 一、双亲表示法:就是用一组连续空间存储树的结点,同时在每个结点中附设 一个指示器指示其双亲的结点在数组中位置。特点:找双亲容易,找孩子难; 二、孩子兄弟表示 法(又称二叉树和二叉链表表示法)链表结构中的两个链域分别指向该结点的的第一个孩子结点 和下一个兄弟结点。操作容易,破坏了树的层次 第六章 树和二叉树 1.树:树是由n个类型相同的元素构成的有限集。 2.二叉树的性质:在二叉树的第i层上至多有2i-1个结点;深度为k的二叉树最多有2k-1个结点; 叶子结点比度为2的结点个数多1。 3.遍历二叉树:先序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)。前后序遍历确定 跟,中序遍历确定左右子树,依次判断,方法是:由前序先确定root,由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合,可继 续确定root的左右孩子。将他们分别作为新的root,不断递归,则所有元素都将被唯一确定.第七章图 一、图的定义和术语: 1、图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中:V(G)是顶点的非空有限集 E(G)是边的有限集合,边是顶点的无序对或有序对 2、有向图—有向图G是由两个集合V(G)和E(G)组成的其中:V(G)是顶点的非空有限集E(G)是有 向边(也称弧)的有限集合,弧是顶点的有序对,记为 3、无向图——无向图G是由两个集合V(G)和E(G)组成的其中:V(G)是顶点的非空有限集 E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v) 4、n个顶点的有向图最大边数是n(n-1); n个顶点的无向图最大边数是n(n-1)/26、权——与图的边或弧相关的数叫~;简单路径——序列中顶点不重复出现的路径叫~ 14、简单回路——除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路叫~ 16、连通图——图中任意两个顶点都是连通的叫~;连通分量——非连通图的每一个连通部分叫~ 18、强连通图——有向图中,如果对每一对Vi,VjÎV, Vi¹Vj,从Vi到Vj 和从Vj到 Vi都存在路径 1、深度优先搜索----从图的某一顶点V0出发,访问此顶点;然后依次从V0的未被访问的邻接点 出发,深度优先遍历图,直至图中所有和V0相通的顶点都被访问到;若此时图中尚有顶点未被 访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止 深度遍历:V1-> V2->V4-> V8->V5->V3->V6->V72、广度优先遍历(BFS)——方法:从图的某一顶点V0出发,访问此顶点后,依次访问V0的各个 未曾访问过的邻接点;然后分别从这些邻接点出发,广度优先遍历图,直至图 中所有已被访问的顶点的邻接点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作 起点,重复上述过程,直至图中所有顶点都被访问为止 第九章 查找 1.静态查找——拆半查找:确定待查记录所在的范围,然后逐步缩小范围知道找到或找不到该记 录为止。假设low和high分别为待查元素所在范围的上下界,指针mid指示区域中间的位置,mid=[low+high]/2.此处low和high分别为位置而非数值。比较时与mid做比较,比mid大,low=mid+1,反之high=mid-1,mid重新计算。查找成功或失败最多比较关键字个数不超过[log2n]+1 例:折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它 将依次与表中20,70,30,50 比较大小,查找结果是失败。 2.静态查找——顺序查找:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,相等则查找成功,反之失败。平均查找长度:ASL=(n+1)/2 3.二叉排列树:或是一棵空树;或者是具有以下性质的二叉树:1.若它的左子树不空,则左子树 上所有结点的值均小于它的根结点的的值;2.若它的右子树不空,则右子树上所有借点得知均大 于它的根节点的值;3.它的左右子树上也分别为二叉排列树。第二篇:C语言课程设计代码
第三篇:C语言实验题目
第四篇:C语言课程设计参考题目
第五篇:数据结构C章节总结