第一篇：北京科技大学数据结构试验报告(附录含代码)
一、1)功能描述
输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。2)详细设计
遵循链表建立的基本思想，建立一个新的链表，H为表头，r为新节点，p为表尾节点指针，没存入一个新的数据则申请一个新的节点，知道没有数据输入，利用循环和打擂台法，比较和的大小，并输出。3)测试分析
程序调试完成后，选取两组数据进行测试，都得出了正确结果（数据以0为结束符，若有相同和，则取第一组）结果截图
4)心得体会
通过做第一题，学习到链表的建立以及链表里指针的使用，并且复习了比较法里面的打擂台法。
二、1)功能描述
实现算术表达式求值程序（栈的运用），输入中缀表达式，可将其转换成后缀表达式 2)详细设计
本题目的程序是根据课本上的程序改进之后得出的，课本上有完整的程序，但是有bug，按照课本上的程序，结果会出现“烫烫烫烫烫”，原因是对于优先级的比较没有处理好，因此加了两行代码，将优先级的比较处理好，即现在的程序。3)测试分析
程序调试完成后，选取题目所给的式子进行测试，得出了正确后缀表达式结果 结果截图
4)心得体会
通过做第二题，对于课本上的知识表示得出“实践出真知”的真理，即使书上的东西也不一定就是正确的，尤其是代码，最好是个人自己真正实践一下。
三、1)功能描述
实现链式队列运算程序（队列的运用）2)详细设计
本题目是队列相关应用，队列和栈是相反的，队列是先进的先出，因此输入12345，先出的是1，本着队列的这一特性，根据课本所学的队列的算法，设计了如下程序。3)测试分析
程序调试完成后，选取12345进行测试，后缀加0，则一个字符出队，只输入0，则继续出队，输入@，则打印剩余全部元素。结果截图
4)心得体会
通过做第三题，对于队列的特点有了更加深刻的认识，尤其区分队列与栈的不同点，需要特别注意。
四、1)功能描述
①构造关于F的Huffman树；
②求出并打印D总各字符的Huffman编码。2)详细设计
本题目是Huffman树的应用以及Huffman编码的应用，参照课本上关于Huffman树的建立以及Huffman编码的应用的实现，将所给数据依权值最小原则建立Huffman树，并实现Huffman编码。3)测试分析
程序调试完成后，给出数据abcdefgh，相应频率为12345678，运行代码得出结果如图。同时选取另一组数据测试也得出了正确结论
结果截图
4)心得体会
通过做第四题，对于Huffman树有了更加深刻的体会，同时练习也使得对课本知识进行实践，有助于更好的理解Huffman树的算法。
五、1)功能描述
设英文句子：“everyone round you can hear you when you speak.”（1）依次读入句中各单词，构造一棵二叉排序树；（2）按LDR遍历此二叉排序树。
LDR： can everyone hear round speak when you（有序）
2)详细设计
本题目是有关二叉树的建立和中序遍历的，二叉树作为数据存储一个很重要的结构，它的建立也是很重要的。本题目代码设计上采用课本上的对于二叉树建立的方法，将所给单词以二叉树形式建立并存储，然后中序遍历的到字典顺序。3)测试分析
程序调试完成后，给出单词串everyone round you can hear you when you speak，运行代码得出中序遍历结果如图。结果截图
4)心得体会
通过做第五题，练习运用二叉树模型解决了一些实际问题如现实中字典的编排问题，在熟悉算法的基础上，同时得出结论，好的算法可以应用与实际生活生产，使之更为便捷。
附录 程序代码 实验一：
#include“stdio.h” #include“malloc.h” typedef struct node {
int data;
struct node *next;}list,*List;List Creatlist()
//建立链表函数 { List H,p,r;
//H为表头，r为新节点，p为表尾节点指针
H=(List)malloc(sizeof(list));
//建立头节点
r=H;
p=(List)malloc(sizeof(list));
//申请新节点
while(scanf(“%d”,p)&&p->data!=0)//输入数据，直到为零（结束标志）
{
r->next=p;//新节点链入表尾
r=p;
p=(List)malloc(sizeof(list));
} r->next=NULL;//将尾节点的指针域置空
return H;
//返回已创建的头节点 } List Adjmax(List H)//比较相邻两数之和
{
//返回相邻两数之和最大的第一个数指针
List p,r,q;int sum=0;p=H->next;if(H->next ==NULL)//判断是否为空
{
printf(“Empty List!”);
q=(List)malloc(sizeof(list));
q->data =0;}
while(p!=NULL)//比较相邻两数之和
{
r=p->next;
if(p&&r)
if(r->data+p->data>sum)
{
q=p;
sum=r->data +p->data;}//不断赋给sum新的最大值
else;
p=p->next;} return q;} int main(){ char ch;printf(“/// 请输入整形数据，以空格隔开，0结束。/// n”);printf(“Ready? nY/N(enter 'y' or 'Y' to continue)n”);while(scanf(“%c”,&ch)&&(ch=='Y'||ch=='y'))
{
List H,pmax;
H=Creatlist();
pmax=Adjmax(H);
printf(“相邻两数之和最大的第一个数为：%dnContinue?
Y/N
free(H);
scanf(”%c“,&ch);} return 0;}
”,pmax->data);实验二：
#include
struct node *next;//后继指针 }snode,*slink;int Emptystack(slink S)//检测栈空 { if(S==NULL)return(1);else return(0);} char Pop(slink*top)//出栈 { char e;slink p;if(Emptystack(*top))return(-1);//栈空返回
else {
e=(*top)->data;//取栈顶元素
p=*top;*top=(*top)->next;//重置栈顶指针
free(p);return(e);} } void Push(slink*top,char e)//进栈 { slink p;p=(slink)malloc(sizeof(snode));//生成进栈p节点
p->data=e;//存入元素e p->next=*top;//p节点作为新的栈顶链入
*top=p;} void Clearstack(slink*top)//置空栈 { slink p;while(*top!=NULL){
p=(*top)->next;
Pop(top);//依次弹出节点直到栈空
*top=p;} *top=NULL;} char Getstop(slink S)//取栈顶 { if(S!=NULL)return(S->data);return(0);} //符号优先级比较
int Precede(char x,char y)//比较x是否“大于”y { switch(x){
case '(':x=0;break;case '+': case '-':x=1;break;case '*': case '/':x=2;break;default: x=-1;} switch(y){ case '+': case '-':y=1;break;case '*': case '/':y=2;break;case '(':y=3;break;default: y=100;} if(x>=y)return(1);else return(0);} //中后序转换
void mid_post(char post[],char mid[])//中缀表达式mid到后缀表达式post的转换的算法 { int i=0,j=0;char x;
slink S=NULL;//置空栈 Push(&S,'#');//结束符入栈 do { x=mid[i++];//扫描当前表达式分量x switch(x){ case '#':
{ while(!Emptystack(S))
post[j++]=Pop(&S);
}
}break;case ')':
{ while(Getstop(S)!='(')
post[j++]=Pop(&S);//反复出栈直至遇到'（'
Pop(&S);//退掉'（'
}break;case '+': case '-': case '*': case '/': case '(':
{ while(Precede(Getstop(S),x))//栈顶运算符（Q1）与x比较
post[j++]=Pop(&S);//Q1>=x时，输出栈顶符并退栈
Push(&S,x);//Q1 }break;default:post[j++]=x;//操作数直接输出 } }while(x!='#');post[j]=' ';//后缀表达式求值 int postcount(char post[])//后缀表达式post求值的算法 { int i=0;char x;float z,a,b;slink S=NULL;//置栈空 while(post[i]!='#'){ x=post[i];//扫描每一个字符送x switch(x) {case '+':b=Pop(&S);a=Pop(&S);z=a+b;Push(&S,z);break; case '-':b=Pop(&S);a=Pop(&S);z=a-b;Push(&S,z);break; case '*':b=Pop(&S);a=Pop(&S);z=a*b;Push(&S,z);break; case '/':b=Pop(&S);a=Pop(&S);z=a/b;Push(&S,z);break;//执行相应运算结果进栈 default:x=post[i]-'0';Push(&S,x);//操作数直接进栈 } i++;} if(!Emptystack(S))return(Getstop(S));//返回结果 } void main(){ char post[255],mid[255]=“";printf(”请输入要处理的中缀表达式：n“); } scanf(”%s“,mid);printf(”相应的后缀表达式为：n“);mid_post(post,mid);printf(”%sn“,post);printf(”表达式的值为：%dn“,postcount(post));getch();实验三： #include”stdio.h“ #include”malloc.h“ #define max 1000 typedef struct node { char ch[max];int front,rear;}squeue,*sq;void Clearqueue(sq Q){ Q->front=Q->rear;} int Emptyqueue(sq Q){ if(Q->rear==Q->front) return 1;else return 0;} void Enqueue(sq Q,char ch){ if(Q->rear>=max){ printf(”FULL QUEUE!“);} else { Q->ch [Q->rear]=ch; Q->rear ++;}} void Dequeue(sq Q){ if(Emptyqueue(Q)){ printf(”Empty QUEUE!n“);} else { printf(”出队：%cn“,Q->ch[Q->front]); Q->front ++;} } void Printqueue(sq Q){ if(Emptyqueue(Q)) ; else { printf(”队列中全部元素：n“); while(Q->front!=Q->rear-1) { printf(”%c“,Q->ch[Q->front]); Q->front++; } printf(”n“);} } int main(){ sq Queue; char f; printf(”*******************************************n“); printf(”请输入字符XnX ≠'@'并且 X ≠'@'字符入队；n“); printf(”X='0',字符出队；n“); printf(”X='@',打印队列中各元素。n“); printf(”*******************************************n“); Queue=(sq)malloc(sizeof(squeue)); Queue->front =Queue->rear=0; while(scanf(”%c“,&f)&&f!='@') { if(f!='0') Enqueue(Queue,f); else Dequeue(Queue); } if(f=='@') Printqueue(Queue); else;return 0;} 实验四： #include”stdio.h“ #include”malloc.h“ #define N 8 #define MAX 100 #define M 2*N-1 typedef struct { char letter;int w;int parent,lchild,rchild;}Huffm;typedef struct { char bits[N+1];int start;char ch;}ctype;void inputHT(Huffm HT[M+1]){ int i; for(i=1;i<=M;i++){ HT[i].w=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0;} printf(”请输入电文字符集：“);for(i=1;i<=N;i++){ scanf(”%c“,&HT[i].letter); } printf(”请输入字符出现的频率：“);for(i=1;i<=N;i++){ scanf(”%d“,&HT[i].w);} } void CreatHT(Huffm HT[M+1]){ int i,j,min1,min2;int tag1,tag2; //权值最小两个点标号； for(i=N+1;i<=M;i++){ tag1=tag2=0; min1=min2=MAX; for(j=1;j<=i-1;j++) { if(HT[j].parent ==0) if(HT[j].w { min2=min1; min1=HT[j].w; tag2=tag1; tag1=j; } else if(HT[j].w { min2=HT[j].w; tag2=j; } } HT[tag1].parent =HT[tag2].parent =i; HT[i].lchild =tag1; HT[i].rchild =tag2; HT[i].w =HT[tag1].w +HT[tag2].w; } } void Huffmcode(Huffm HT[M+1])// Huffm编码函数 { int i,j,p,tag; ctype mcode,code[N+1];for(i=1;i<=N;i++){ code[i].ch=HT[i].letter; } for(i=1;i<=N;i++){ mcode.ch =code[i].ch; mcode.start=N+1; tag=i; p=HT[i].parent; for(j=0;j<=N;j++) mcode.bits [j]=' '; while(p!=0) { mcode.start--; if(HT[p].lchild ==tag) mcode.bits[mcode.start ]='0'; else mcode.bits [mcode.start ]='1'; tag=p;p=HT[p].parent; } code[i]=mcode; } for(i=1;i<=N;i++){ printf(” '%c'的Huffm编码为：“,code[i].ch); for(j=0;j<=N;j++) printf(”%c“,code[i].bits [j]); printf(”n“);} } int main(){ char ch; printf(”******************************************************n“);printf(”电文字符集含8个字符，连续输入，不同频率之间以空格隔开 n“); printf(”******************************************************n“); ch='y';while(ch=='y'){ Huffm HT[M+1]; inputHT(HT); CreatHT(HT); Huffmcode(HT); printf(”Continue? Y/N “); fflush(stdin); scanf(”%c“,&ch); fflush(stdin);} } 实验五： #include”stdio.h“ #include”malloc.h“ #include”string.h“ typedef struct bsnode { char word[20];struct bsnode *lchild,*rchild;}BStree,*BST;BST BSTinsert(BST T,BST s){ BST f,p;if(T==NULL) return s;p=T;f=NULL;while(p){ f=p; if(strcmp(s->word,p->word)==0) { free(s); return T; } if(strcmp(s->word,p->word)<0) p=p->lchild; else p=p->rchild;} if(strcmp(s->word ,f->word)<0) f->lchild=s;else f->rchild=s;return T;} BST CreatBst(){ BST T,s;char keyword[20];T=NULL;gets(keyword);while(keyword[0]!='0'){ s=(BST)malloc(sizeof(BStree)); strcpy(s->word,keyword); s->lchild=s->rchild=NULL; T=BSTinsert(T,s); gets(keyword);} return T;} void Inorder(BST T){ if(T){ Inorder(T->lchild); printf(”%s “,T->word); Inorder(T->rchild);} } int main(){ char ch;BST T;printf(”************************************************************n“);printf(”请输入英文句子，每输入一个单词以回车结束，句子结束以'0'结束。n“); printf(”************************************************************n“);ch='y';while(ch=='Y'||ch=='y'){ T=CreatBst(); printf(”按LDR遍历此二叉排序树(字典顺序):n“);Inorder(T);free(T);printf(”nContinue? Y/N “);scanf(”%c",&ch);}} 实验一：ADT的类C描述向C程序的转换实验(2学时) 实验目的： (1)复习C语言的基本用法； (2)学会用类C的语言对算法进行描述的方法，将类C算法转换成C源程序的方法和过程； (3)抽象数据类型的定义和表示、实现； (4)加深对数据的逻辑结构和物理结构之间关系的理解；(5)初步建立起时间复杂度和空间复杂度的概念。实验内容：(类C算法的程序实现)(1)输入一组数据存入数组中，并将数据元素的个数动态地由输入函数完成。求输入数据的最大值、最小值，并通过函数参数返回所求结果； 实验准备： 1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤： 1.安装TC并设置好环境，如果已安装好，可以跳过此步； 2.录入程序代码并进行调试和算法分析； 对实验内容(1)的操作步骤：1)用类C语言描述算法过程；2)用C语言环境实现该算法。 对实验内容(2)的操作步骤：1)完成算法的C实现；2)分析其时间复杂度和空间复杂度。 3.编写实验报告。 实验结果：// 动态分配数组空间 #include int size,i;int *pArray;int *p;void malloc_size(){ pArray=(int *)malloc(size*(sizeof(int)));} int input_size(){ printf(“please input the size:n”);printf(“size= ”);scanf(“%d”,&size);return 0;} int input_data(){ printf(“please input the value:n”);for(i=0;i printf(“pArray[%d]= ”,i); scanf(“%d”,&pArray[i]);} return *pArray;} int Compare(){ int x,y,i;x=y=p[0];for(i=0;i if(x>=p[i])x=p[i]; if(y<=p[i])y=p[i];} printf(“min= %dt max=%dn”,x,y);return 0;} int Output_data(){ p=pArray;printf(“before ofpaixu :n”);for(i=0;i printf(“%dt”,*pArray); pArray++;} printf(“n”);return *pArray;} void paixu(){ int x=0;int i,j;printf(“later of paixu:n”);for(i=0;i for(j=i+1;j { if(p[i]>=p[j]) { x=p[i];p[i]=p[j];p[j]=x; } } printf(“%dt”,p[i]);} printf(“n”);} void main(){ clrscr();input_size();malloc_size();input_data();Output_data();Compare();paixu();} 实验结果： 实验二 线性表及其基本操作实验(2学时)实验目的： (1)熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2)以线性表的基本操作为基础实现相应的程序； (3)掌握线性表的顺序存储结构和动态存储结构之区分。 实验内容：(类C算法的程序实现，任选其一。具体要求参见教学实验大纲)(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2)有序表的合并；(3)集合的并、交、补运算； 实验准备： 1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤： 1.录入程序代码并进行调试和算法分析； 2.编写实验报告。实验结果：//线性链表 #include typedef struct node { int data;struct node *next;}*Sqlist; void Initlialize(Sqlist &L){ L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;} int Getlength(Sqlist L){ int i=0;Sqlist p=L->next;while(p!=NULL){ i++; p=p->next;} return i;} int Getelem(Sqlist L,int i){ int j=1,e;Sqlist p=L->next;while(j p=p->next; j++;} e=p->data;printf(“第 %d 个元素是：%dn”,i,e);return 1;} int Locatelem(Sqlist L,int x){ int i=0;Sqlist p=L->next;while(p!=NULL&&p->data!=x){ p=p->next; i++;} if(p==NULL) return 0;else { printf(“%d 是第 %d 个元素n”,x,i);return i;} } void CreatlistF(Sqlist &L,int a[ ],int n){ Sqlist s;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;for(i=0;i s=(Sqlist)malloc(sizeof(Sqlist)); } } void CreatlistR(Sqlist &L,int a[],int n){ Sqlist s,r;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;r=L;for(i=0;i s=(Sqlist)malloc(sizeof(Sqlist)); s->data =a[i]; s->next=NULL; r->next =s;r =s;} } int Inselem(Sqlist &L,int i,int x){ int j=1;Sqlist s,p=L->next;s=(Sqlist)malloc(sizeof(Sqlist));s->data =x;s->next =NULL;if(i<1||i>Getlength(L)) return 0;while(j p=p->next;j++;} printf(“在第 %d 个位置插入数据：%dn”,i,x);s->next =p->next; p->next =s;return 1;} int Delelem(Sqlist &L,int i){ int j=1; Sqlist p,q; p=L; if(i<1||i>Getlength(L)) return 0;s->data =a[i]; s->next =L->next;L->next =s; while(j { p=p->next; j++; } q=p->next; p->next =q->next; free(q); return 1;} void Displist(Sqlist L){ Sqlist p=L->next; while(p!=NULL) { printf(“%dt”,p->data); p=p->next; } printf(“n”);} void input(int *pArray,int n){ printf(“请输入数组数据(共含 %d 个元):n”,n); for(int i=0;i Scanf(“%d”,&pArray[i]); } int main(int argc, char* argv[]){ Sqlist L; int Array[M],Select;initlialize(L);do{ printf(“请输入选择方法（1表示头插法，2表示尾插法,0表示结束）：n”); scanf(“%d”,&Select); switch(Select) { case 1: printf(“按头插法建立线性表:n”); input(Array,M); creatlistF(L,Array,M); break;case 2: printf(“按尾插法建立线性表:n”); input(Array,M); creatlistR(L,Array,M); break; } printf(“原线性表数据为:n”);Displist(L); Getelem(L,3); Locatelem(L,2); Inselem(L,5,5); printf(“修改后的线性表数据为:n”); Delelem(L,4); Displist(L);}while(Select!=0);return 0;} 运行结果: 实验三 栈和队列实验(6学时)实验目的： (1)熟练掌握栈和队列的抽象数据类型及其结构特点；(2)实现基本的栈和队列的基本操作算法程序。实验内容：(类C算法的程序实现，任选其一)(1)设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP等操作）(必做)； (2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计与实现（选做）； 实验准备： 1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤： 1.录入程序代码并进行调试和算法分析； 2.编写实验报告。实验结果：//队列存储 #include typedef struct sqqueue { char data[QueueSize];int front,rear;}SqQueue; void InitQueue(SqQueue &qu){ qu.front =qu.rear =0;} status EnQueue(SqQueue &qu,char x){ if((qu.rear +1)%QueueSize==qu.front) return 0;qu.rear =(qu.rear+1)%QueueSize;qu.data[qu.rear]=x;return 1;} status DeQueue(SqQueue &qu,char &x){ if(qu.rear==qu.front) return 0;qu.front =(qu.front +1)%QueueSize;x=qu.data[qu.front];return 1;} status GetHead(SqQueue qu,char &x){ if(qu.rear ==qu.front) return 0;x=qu.data[(qu.front+1)%QueueSize];return 1;} status QueueEmpty(SqQueue qu){ if(qu.rear==qu.front) return 1;else return 0;} void main(){ SqQueue qu;char e;InitQueue(qu);printf(“Queue %sn”,(QueueEmpty(qu)==1?“Empty”:“Not Empty”)); printf(“inser an”); EnQueue(qu,'a'); printf(“inser bn”); EnQueue(qu,'b'); printf(“inser cn”); EnQueue(qu,'c'); printf(“inser dn”); EnQueue(qu,'d'); printf(“Queue %sn”,(QueueEmpty(qu)==1?“Empty”:“Not Empty”)); GetHead(qu,e); printf(“Queue of top elem is: %cn”,e); printf(“show of Queue:n”); while(!QueueEmpty(qu)){ DeQueue(qu,e); printf(“%ct”,e);} printf(“n”);} 实验结果： （2）//用栈实现对表达式的求值运算 #include #define TRUE 1 #define FALSE 0 #define OK #define ERROR 0 #define INFEASIBLE-1 #define OVERFLOW-2 #define STACK_INIT_SIZE #define STACKINCREMENT 10 typedef int Status;typedef char ElemType; typedef ElemType OperandType; typedef char OperatorType; typedef struct { ElemType *base; ElemType *top; int stacksize;}SqStack; Status InitStack(SqStack &S){ S.base =(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!S.base)exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;} Status GetTop(SqStack S){ ElemType e; if(S.top == S.base)return ERROR; e = *(S.top-1); return e;} Status Push(SqStack &S,ElemType e) { if(S.top1 < n){ merge(r, r1, i, i+length-1, i + 2*length1 < n-1) merge(r, r1, i, i+length-1, n-1); else for(j = i;j < n;j++)r1[j] = r[j];} void MergeSort(SortObject * pvector){ RecordNode record[MAXNUM]; int length = 1; while(length < pvector->n){ mergePass(pvector->record, record, pvector->n, length); length *= 2; mergePass(record, pvector->record, pvector->n, length); length *= 2; } } SortObject vector = {8, 49,38,65,97,76,13,27,49}; int main(){ int i;printf(“排序前序列为：”); for(i = 0;i < 8;i++) printf(“%d ”, vector.record[i]);printf(“n”); MergeSort(&vector);printf(“采用归并排序为：”); for(i = 0;i < 8;i++) printf(“%d ”, vector.record[i]); getchar(); return 0;} 实验结果： 实验十 查找实验(2学时)* 实验目的： (1)熟练掌握各种静态查找表方法(顺序查找、折半查找、索引顺序表等)；(2)熟练掌握二叉排序树的构造方法和查找算法； (3)了解和掌握其它查找方法。 实验内容：(类C算法的程序实现，除顺序查找算法之外，任选一个)(1)顺序查找算法的实现(必做)；(2)折半查找算法的实现(选做)； 实验结果：//查找实验 1、顺序查找： #include void SequenceSearch(int *fp,int Length){ int data; printf(“开始使用顺序查询.请输入你想要查找的数据: ”); scanf(“%d”,&data); for(int i=0;i if(fp[i]==data) { printf(“数据%d 是第 %d 个数据n”,data,i+1); return; } printf(“未能查找到数据%d.n”,i,data);} void main(){ int count; int arr[LENGTH]; printf(“请输入你的数据的个数:”); scanf(“%d”,&count); printf(“请输入 %d 个数据:”,count); for(int i=0;i scanf(“%d”,&arr[i]); SequenceSearch(arr,count);} 实验结果： 2、折半查找： #include typedef struct { char *elem; int length; }SStable; void Create(char **t) { int i;static char a[M+1];*t=a;for(i=1;i<=M;i++){ printf(“A[%d] is:”,i); scanf(“%c”,&a[i]); if(a[i]!= 'n')getchar();} } int Searth(char *t,char k){ int i;for(i=M;i>=0 && t[i]!=k;i--); Return i;} void output(char *t){ int i;for(i=1;i<=M;i++) printf(“n A[%d] is %c”,i,t[i]);} void px(char *t) { char s;int i,j;for(i=1;i<=M;i++) for(j=i+1;j<=M;j++) { if(t[i]>t[j]){s=t[i];t[i]=t[j];t[j]=s;} } } int Search_bin(char *t,char k){ int low=1,high=M,mid;while(low<=high){ mid=(low+high)/2; if(k==t[mid])return mid; else if(k else low=mid+1;} return 0;} void main(){ char *t,k;int s;Create(&t);output(t);printf(“nplease input you search char:”);k=getchar();s=Searth(t,k);if(s>=0)printf(“1: use search find is A[%d]n”,s);else printf(“1:can not find itn”);px(t);output(t);s=Search_bin(t,k);if(s==0)printf(“n1:can not find it n”);else printf(“n2:use Search_bin find is A[%d]n”,s);getchar();} 实验结果： 线性表上机实习 1、实验目的 （1）熟悉将算法转换为程序代码的过程。 （2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。 （3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。 2、实验要求 （1）熟悉顺序表的插入、删除和查找。（2）熟悉单链表的插入、删除和查找。 3、实验内容: ① 顺序表 （1）抽象数据类型定义 typedef struct { TypeData data[maxsize]; //容量为maxsize的静态顺手表 int n; //顺序表中的实际元素个数 }SeqList; //静态顺序表的定义 在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单选择界面，通过不同的数字输入，实现对顺序表，删除，插入，查找，显示等操作。 （2）存储结构定义及算法思想 在顺序表结构体的定义中，typedef int TypeData 为整型，存储结构如下： for(n=0;n cout<<“请输入线性表数据”< cin>>L.data[n]; //顺序将数据存入顺序表 } //其他存储与此类似，都是直接赋值与数组的某一位 插入版块子函数： void insert(SeqList &L) //插入数据 { int a,b,c,k; cout<<“请输入插入的数及其插入的位置”< cin>>a>>b; if(b<=0||b>(L.n+1)){cout<<“不能在该位置插入”< k=L.data[b-1];L.data[b-1]=a;c=L.n;L.n=L.n+1; while(c>b){ L.data[c]=L.data[c-1];c--; //通过循环，实现插入位置后的数据挨个往后移动一位 } L.data[b]=k;} 顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。显示操作是通过循环实现表中第一个元素到最后一个元素的输出，查找操作是直接取数组中的查找位输出。 （3）实验结果与分析 ② 单链表 （1）抽象数据类型定义 typedef struct node{ DataType data; //链表的数据类型 struct node *link; //链表的结点指针 }linknode,*linklist; //定义了结构体linklode和结构体指针linklist 在本次实验中，首先程序自己建立一个空的头结点，通过菜单的功能选择“添加链表数据”可自由添加链表的节点数及元素值。在菜单选择中，有“添加链数据”，“插入链表数据”，“删除链表数据”，“查找链表数据”和“显示链表数据”功能，选择不能的功能选择就能实现不同的操作。其中“添加链表数据”可反复批量输入链表数据。 （2）存储结构定义及算法思想 在单链表中，typedef int DataType;DataType data;定义链表存储数据位整型。存储结构如下： while(p->link!=NULL){ p=p->link; k++; //首先找到单链表的最后结点（如果是只有头结点 } 的单链表则直接跳过），以便后面接着输入数据 for(int i=0;i { cout<<“请输入数据”< //开辟新的结点空间并转化为linklist指针型 cin>>q->data; q->link=p->link; //将前面一个结点的指向(及NULL)赋给新开辟的结点的指向 p->link=q; //将插入点前面一个结点指向新开辟的的结点 p=q; //将指明的最后一个一个结点向后移1位到最后一位，以便后面接着输入 } 删除结点子函数： void delate(linklist &l){ //删除单链表数据 linklist p;int m,n,i=0; cout<<“请输入想要删除的结点位置”< cin>>m; p=l; //将头结点赋给转移指针p while(p&&i //查找删除结点的位置 p=p->link; //当在单链表中间已查到删除结点或p=NULL时跳出循环 i++; } if(p==NULL){ //当p=NULL跳出循环时，表明链表中没有该结点 cout<<“该结点不存在，删除错误”< } n=p->link->data;//找到删除接结点将数据取出并显示出来（找结点时是找的前一个结点） cout<<“被删除的结点元素为: ”< p->link=p->link->link; //将删除结点的前后结点链接起来 } 链表的删除，插入操作是类似的，要考虑到加入或减少一个结点后，前后结点的链接关系，以及删除或插入的是最后一个结点时，新空间的开辟与结点收尾等问题。其中删除功能的一部分就是查找功能，显示功能也是从链表的头结点遍历至最后一个，依次输出。 （4）实验结果与分析 ③ 心得体会 本次数据结构实习我收获颇丰，以前学过c语言与c++也有经常上机，但以往都是偏向于程序整体的算法设计，没有像这次的实习这样是着重在线性表，链表结构的算法设计上面。这次上机实习，让我更加熟练了结构体及结构体指针的用法，线性表的设计等等，同时在这次实习中，引用，指针，地址这三个的用法曾一度让我混淆，在查阅书籍后才得以解决，也希望老师在课堂上有时间时给我们详细讲解一下，指针，地址，引用三者的使用。 附录： 顺序表源代码: #include void makeSeq(SeqList &L)// 据 { int m,n,k;cout<<“请输入线性表长度”< 输入线性表数输出线性表数据 void insert(SeqList &L)//插入数据 { int a,b,c,k;cout<<“请输入插入的数及其插入的位置”< cout<<“删除 2”< 单链表源代码： #include linklist chushihua(){ linklist L;L=(linklist)malloc(sizeof(linknode));L->link=NULL;cout<<“开辟空间成功，头结点建立”< p=l;while(p->link!=NULL){ p=p->link;k++;} for(int i=0;i data<<“ ”;p=p->link;} cout< { linklist p,q;int m,n,i=0; cout<<“请输入您要插入的结点位置及插入的数据”< q=(linklist)malloc(sizeof(linknode));q->data=n;q->link=p->link;p->link=q;} void delate(linklist &l){ linklist p;int m,n,i=0;cout<<“请输入想要删除的结点位置”< L=chushihua(); while(1){ cout<<“请选择功能”< case 1: shuru(L);break;case 2: insert(L);break;case 3: delate(L);break;case 4: find(L);break;case 5: show(L);break;default :break;} } } #include typedef struct LNode { //数据域 int cipher; //密码 int number; //编号 struct LNode *next; //指针域 }LNode,*LinkList; void InitList(LinkList &L) //创建一个只有头结点链表 { L =(LinkList)malloc(sizeof(LNode));if(!L){ exit(1); printf(“/n/nError!/n/n”);} L->next = L;} void CreateList(int n,LinkList &L)//初始化循环单链表 { LinkList p,q;q = L;printf(“分别输入每个人的密码：”);for(int i = 1;i <= n;i++){ int k; scanf(“%d”,&k); if(k <= 0) { printf(“nn密码有误!nn”); exit(1); } p =(LinkList)malloc(sizeof(LNode)); if(!p) { exit(1); printf(“/n/nError!/n/n”); } p->cipher = k; p->number = i; L->next = p; L = p;} L->next = q->next;free(q);} void PrintList(int x,int n,LinkList L)//输出出列顺序 { LinkList p,q;p = L;for(int i = 1;i <= n;i++){ for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf(“%d ”,q->number); p->next = q->next; free(q);} } int main(){ printf(“=============约瑟夫环==============nnn”); int n,x;LinkList L;L = NULL;InitList(L); //构造空链表 printf(“输入初始密码：”);scanf(“%d”,&x); //初始密码为x printf(“n”);printf(“输入参与总人数：”);scanf(“%d”,&n); //总共的人数n printf(“n”);CreateList(n,L); //建立好一个约瑟夫环 printf(“nnn===================================nn”); printf(“出列编号为：”);PrintList(x,n,L); //输出出列顺序 printf(“nn”);return 0;} 《数据结构》课程设计题目(程序实现采用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第二篇：数据结构试验报告
第三篇：数据结构线性表试验报告
第四篇：数据结构课程设计——约瑟夫环报告(含代码)
第五篇：数据结构经典题目及c语言代码总结
点击咨询 