第一篇：数据结构实验C语言版
南阳理工学院
数据结构(C语言版)上机实验指导书
软件学院·软件工程
目录
实验1 线性表应用
实验2 栈和队列的应用.......................................................................14 实验3 线性表应用...............................................................................27 实验4 图论及其应用...........................................................................46
实验5 查找
实验6 排序...........................................................................................64
实验1 线性表应用
一、实验目的
3，了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实 2，能够利用线性表结构对实际问题进行分析建模，利用计算机求解。
1，能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
二、实验内容及步骤
1、利用程序设计语言分别实现顺序表和链表的抽象数据类型。
2、掌握程序分文件（头文件和实现文件）书写的方式。
3、分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。
三、实验步骤与调试过程
以线性表来描述一元多项式，储存结构采用单链表，每个结点储存的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。
四、实验结果
五、疑难小结
当线性表的长度变化较大，难以估计其存储规模，另外对线性表频繁进行插入和删除操作时，则采用链表作为存储结构可能会更好一些。在实际应用中应该考虑以下因素：(1)应有利于运算的实现；(2)应有利于数据的特性；(3)应有利于软件环境。
六、主要算法和程序清单 顺序表的非递减数列合并 #include
/*包含输入输出头文件*/ #define ListSize 100 typedef int DataType;typedef struct { DataType list[ListSize];int length;}SeqList;
void InitList(SeqList *L)
/*将线性表初始化为空的线性表只需要把线性表的长度length置为0*/ { L->length=0;/*把线性表的长度置为0*/ } int ListEmpty(SeqList L)
/*判断线性表是否为空，线性表为空返回1，否则返回0*/ {
if(L.length==0)
/*判断线性表的长度是否为9*/
return 1;
/*当线性表为空时，返回1；否则返回0*/
else
return 0;} int GetElem(SeqList L,int i,DataType *e)
/*查找线性表中第i个元素。查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败。*/ { if(i<1||i>L.length)
/*在查找第i个元素之前，判断该序号是否合法*/
return-1;*e=L.list[i-1];/*将第i个元素的值赋值给e*/
return 1;} int LocateElem(SeqList L,DataType e)
/*查找线性表中元素值为e的元素，查找成功将对应元素的序号返回，否则返回0表示失败。*/ {
int i;for(i=0;i if(L.list[i]==e) return i+1; return 0;} int InsertList(SeqList *L,int i,DataType e) /*在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，顺序表满返回0*/ { int j;if(i<1||i>L->length+1) /*在插入元素前，判断插入位置是否合法*/ { printf(“插入位置i不合法！n”); return-1;} else if(L->length>=ListSize)/*在插入元素前，判断顺序表是否已经满，不能插入元素*/ { printf(“顺序表已满，不能插入元素。n”); return 0;} else { for(j=L->length;j>=i;j--)/*将第i个位置以后的元素依次后移*/ L->list[j]=L->list[j-1]; L->list[i-1]=e;/*插入元素到第i个位置*/ L->length=L->length+1;/*将顺序表长增1*/ return 1;} } int DeleteList(SeqList *L,int i,DataType *e){ int j; if(L->length<=0) { printf(“顺序表已空不能进行删除!n”); return 0; } else if(i<1||i>L->length) { printf(“删除位置不合适!n”); return-1; } else { *e=L->list[i-1]; for(j=i;j<=L->length-1;j++) L->list[j-1]=L->list[j]; L->length=L->length-1; return 1; } } int ListLength(SeqList L){ return L.length;} void ClearList(SeqList *L){ L->length=0;} void MergeList(SeqList A,SeqList B,SeqList *C);*/ void main(){ int i,flag;DataType a[]={6,11,11,23};DataType b[]={2,10,12,12,21};DataType e; /*合并顺序表A和B中元素的函数声明 SeqList A,B,C; /*声明顺序表A，B和C*/ InitList(&A); /*初始化顺序表A*/ InitList(&B); /*初始化顺序表B*/ InitList(&C); /*初始化顺序表C*/ for(i=1;i<=sizeof(a)/sizeof(a[0]);i++) /*将数组a中的元素插入到顺序表A中*/ { if(InsertList(&A,i,a[i-1])==0) { printf(“位置不合法”); return; } } for(i=1;i<=sizeof(b)/sizeof(b[0]);i++) /*将数组b中元素插入到顺序表B中*/ { if(InsertList(&B,i,b[i-1])==0) { printf(“位置不合法”); return; } } printf(“顺序表A中的元素：n”);for(i=1;i<=A.length;i++)/*输出顺序表A中的每个元素*/ { flag=GetElem(A,i,&e);/*返回顺序表A中的每个元素到e中*/ if(flag==1) printf(“%4d”,e);} printf(“n”);printf(“顺序表B中的元素：n”);for(i=1;i<=B.length;i++)/*输出顺序表B中的每个元素*/ { flag=GetElem(B,i,&e);/*返回顺序表B中的每个元素到e中*/ if(flag==1) printf(“%4d”,e); } printf(“n”);printf(“将在A中出现B的元素合并后C中的元素：n”);MergeList(A,B,&C); /*将在顺序表A和B中的元素合并*/ for(i=1;i<=C.length;i++) /*显示输出合并后C中所有元素*/ { flag=GetElem(C,i,&e); if(flag==1) printf(“%4d”,e); } printf(“n”);getch(); } void MergeList(SeqList A,SeqList B,SeqList *C)/*合并顺序表A和B的元素到C中，并保持元素非递减排序*/ { int i,j,k;DataType e1,e2;i=1;j=1;k=1;while(i<=A.length&&j<=B.length){ GetElem(A,i,&e1); GetElem(B,j,&e2); if(e1<=e2) { InsertList(C,k,e1); i++; k++; } else { InsertList(C,k,e2); j++; k++; } } while(i<=A.length) 素*/ { GetElem(A,i,&e1); InsertList(C,k,e1); i++; k++;} while(j<=B.length) 素*/ { GetElem(B,j,&e2); InsertList(C,k,e2); j++; /*取出顺序表A中的元素*/ /*取出顺序表B中的元素*/ /*比较顺序表A和顺序表B中的元素*/ /*将较小的一个插入到C中*/ /*往后移动一个位置，准备比较下一个元素*/ /*将较小的一个插入到C中*/ /*往后移动一个位置，准备比较下一个元素*/ /*如果A中元素还有剩余，这时B中已经没有元/*将A中剩余元素插入到C中*/ /*如果B中元素还有剩余，这时A中已经没有元/*将B中剩余元素插入到C中*/ k++;} C->length=A.length+B.length;/*C的表长等于A和B的表长的和*/ } 链式表的非递减数列合并 /*包含头文件*/ #include #include DataType data; struct Node *next;}ListNode,*LinkList;void MergeList(LinkList A,LinkList B,LinkList *C);/*将单链表A和B的元素合并到C中的函数声明*/ void InitList(LinkList *head)/*将单链表初始化为空。动态生成一个头结点，并将头结点的指 针域置为空。*/ { if((*head=(LinkList)malloc(sizeof(ListNode))) ==NULL)/*为头结点分配一个存储空间*/ exit(-1);(*head)->next=NULL; /*将单链表的头结点指针域置为空*/ } int ListEmpty(LinkList head) /*判断单链表是否为空，就是通过判断头结点的指针域是否为空 */ { if(head->next==NULL) /*判断 单链表头结点的指针域是否为空*/ return 1; /*当单链表为空时，返回1；否则返回0*/ else return 0;} ListNode *Get(LinkList head,int i) /*查找单链表中第i个结点。查找成功返回该结点的指针表示成 功；否则返回NULL表示失败。*/ { ListNode *p;int j;if(ListEmpty(head))/*在查找第i个元素之前，判断链表是否为空*/ return NULL;if(i<1) /*在查找第i个元 素之前，判断该序号是否合法*/ return NULL;j=0;p=head;while(p->next!=NULL&&j p=p->next; j++;} if(j==i) return p;/*找到第i个结点，返回指针p*/ else return NULL;/*如果没有找到第i个元 素，返回NULL*/ } ListNode *LocateElem(LinkList head,DataType e) /*查找线性表中元素值为e的元素，查找成功将对应元素的结点 指针返回，否则返回NULL表示失败。*/ { ListNode *p;p=head->next;/*指针p指向第一个结点*/ while(p){ if(p->data!=e)/*找到与e相等的元素，返 回该序号*/ p=p->next; else break;} return p;} int LocatePos(LinkList head,DataType e) /*查找线性表中元素值为e的元素，查找成功将对应元素的序号 返回，否则返回0表示失败。*/ { ListNode *p;int i; if(ListEmpty(head))/*在查找第i个元 素之前，判断链表是否为空*/ return 0; p=head->next;/*指针p指向第一 个结点*/ i=1; while(p) { if(p->data==e)/*找到与e相等的 元素，返回该序号*/ return i; else { p=p->next; i++; } } if(!p) /*如果 没有找到与e相等的元素，返回0，表示失败*/ return 0;} int InsertList(LinkList head,int i,DataType e)/*在单链表中第i个位置插入一个结点，结点的元素值为e。插入 成功返回1，失败返回0*/ { ListNode *p,*pre;/*定义指向第i个元素的前 驱结点指针pre，指针p指向新生成的结点*/ int j;pre=head; /*指针p指向头结 点*/ j=0;while(pre->next!=NULL&&j pre=pre->next; j++;} if(!pre) /*如果没找到，说明插入位置错误*/ { printf(“插入位置错”); return 0;} /*新生成一个结点，并将e赋值给该结点的数据域*/ if((p=(ListNode*)malloc(sizeof(ListNode)))==NULL) exit(-1);p->data=e;/*插入结点操作*/ p->next=pre->next;pre->next=p;return 1;} int DeleteList(LinkList head,int i,DataType *e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回 0*/ { ListNode *pre,*p;int j; pre=head; j=0; while(pre->next!=NULL&&pre->next->next! =NULL&&j { pre=pre->next; j++; } if(j!=i-1) /*如果没找到要 删除的结点位置，说明删除位置错误*/ { printf(“删除位置错误”); return 0;} /*指针p指向单链表中的第i个结点，并将该结点的数据 域值赋值给e*/ p=pre->next;*e=p->data;/*将前驱结点的指针域指向要删除结点的下一个结点，也就是将p指向的结点与单链表断开*/ pre->next=p->next; free(p); /*释放p指向的结 点*/ return 1;} int ListLength(LinkList head){ ListNode *p; int count=0; p=head; while(p->next!=NULL) { p=p->next; count++; } return count;} void DestroyList(LinkList head){ ListNode *p,*q; p=head; while(p!=NULL){ q=p; p=p->next; free(q); } } void main(){ int i;DataType a[]={6,7,9,14,37,45,65,67};DataType b[]={3,7,11,34,45,89}; LinkList A,B,C; /*声明单链表A和B*/ ListNode *p;InitList(&A); /*初始化单链表A*/ InitList(&B); /*初始化单链表B*/ for(i=1;i<=sizeof(a)/sizeof(a[0]);i++)/*将数组a中元素插入到单链表A中*/ { if(InsertList(A,i,a[i-1])==0) { printf(“位置不合法”); return; } } for(i=1;i<=sizeof(b)/sizeof(b[0]);i++)/*将数组b中元素插入单链表B中*/ { if(InsertList(B,i,b[i-1])==0) { printf(“位置不合法”); return; } } printf(“单链表A中的元素有%d个：n”,ListLength(A));for(i=1;i<=ListLength(A);i++)/*输出单链表A中的每个元素*/ { p=Get(A,i); /*返回单链表A中的每个结点的指针*/ if(p) printf(“%4d”,p->data);/*输出单链表A中的每个元素*/ } printf(“n”);printf(“单链表B中的元素有%d个：n”,ListLength(B));for(i=1;i<=ListLength(B);i++) { p=Get(B,i); /*返回单链表B中的每个每个结点的指针*/ if(p) printf(“%4d”,p->data);/*输出单链表B中的每个元素*/ } printf(“n”);MergeList(A,B,&C); /*将单链表A和B中的元素合并到C中*/ printf(“将单链表A和B的元素合并到C中后，C中的元素有%d个：n”,ListLength(C));for(i=1;i<=ListLength(C);i++) { p=Get(C,i); /*返回单链表C中每个结点的指针*/ if(p) printf(“%4d”,p->data);/*显示输出C中所有元素*/ } printf(“n”);getch();} void MergeList(LinkList A,LinkList B,LinkList *C)/*单链表A和B中的元素非递减排列，将单链表A和B中的元素合并到C中，C中的元素仍按照非递减排列*/ { ListNode *pa,*pb,*pc;/*定义指向单链表A，B,C的指针*/ pa=A->next;pb=B->next;*C=A; /*将单链表A的头结点作为C的头结点*/(*C)->next=NULL;pc=*C;/*依次将链表A和B中较小的元素存入链表C中*/ while(pa&&pb) { if(pa->data<=pb->data) { pc->next=pa;/*如果A中的元素小于或等于B中的元素，将A中的元素的结点作为C的结点*/ pc=pa; pa=pa->next; } else { pc->next=pb;/*如果A中的元素大于B中的元素，将B中的元素的结点作为C的结点*/ pc=pb; pb=pb->next; } } pc->next=pa?pa:pb;/*将剩余的结点插入C中*/ free(B); /*释放B的头结点*/ } 实验2 栈和队列的应用 一、实验目的 1、掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 2、熟练掌握栈类型的两种实现方法。 3、熟练掌握循环队列和链队列的基本操作实现算法。 二、实验内容及步骤 1、用程序设计语言实现栈和队列的抽象数据类型。 2、在第一题的基础上完成以下选择： 选择一： 1)设计并实现括号匹配算法。 2)用队列实现在屏幕上打印杨辉三角。选择二： 分别用栈和队列实现迷宫问题求解。选择三： 分别用栈和队列实现一个列车调度系统。 三、实验步骤与调试过程 首先只只置操作数栈为空，表达式起始符“#”为运算符栈的栈底元素，依次读入表达式中每个字符，直至整个表达式求值完毕。 四、实验结果 五、疑难小结 对栈的顺序存储结构用了更深刻的了解，同时也对程序设计能力有了提高，加深了对栈先进后出性质的理解，对数组的应用也十分熟练。 六、主要算法： 括号匹配算法。#include DataType data; struct node *next;}LStackNode,*LinkStack;void InitStack(LinkStack *top)/*将链栈初始化为空。动态生成头结点，并将头结点的指针域置为空。*/ { if((*top=(LinkStack)malloc(sizeof(LStackNode)))==NULL)/*为头结点分配一个存储 空间*/ exit(-1);(*top)->next=NULL; /*将链栈的头结点指针域置为空*/ } int StackEmpty(LinkStack top) /*判断链栈是否为空，就是通过判断头结点的指针域是否为空*/ { if(top->next==NULL) /*判断链栈头结点的指针域是否为空*/ return 1; /*当链栈为空时，返回1；否则返回0*/ else return 0;} int PushStack(LinkStack top, DataType e)/*进栈操作就是要在链表的第一个结点前插入一个新结点，进栈成功返回1*/ { LStackNode *p;/*定义指向第i个元素的前驱结点指针pre，指针p指向新生成的结点*/ if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL){ printf(“内存分配失败!”); exit(-1);} p->data=e; /*指针p指向头结点*/ p->next=top->next;top->next=p;return 1;} int PopStack(LinkStack top,DataType *e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/ { LStackNode *p; p=top->next; if(!p) /*判断链栈是否为空*/ { printf(“栈已空”); return 0; } top->next=p->next; /*将栈顶结点与链表断开，即出栈*/ *e=p->data; /*将出栈元素赋值给e*/ free(p); /*释放p指向的结点*/ return 1;} int StackLength(LinkStack top){ LStackNode *p; int count=0; p=top; while(p->next!=NULL) { p=p->next; count++; } return count;} void DestroyStack(LinkStack top){ LStackNode *p,*q; p=top; while(!p){ q=p; p=p->next; free(q); } } int GetTop(LinkStack top,DataType *e){ LStackNode *p; p=top->next; if(!p) /*判断链栈是否为空*/ { printf(“栈已空”); return 0; } *e=p->data; /*将出栈元素赋值给e*/ return 1;} void main(){ LinkStack S;char *p;DataType e;DataType ch[60];InitStack(&S); /*初始化链栈*/ printf(“请输入带括号的表达式('{}','[]','()').n”);gets(ch);p=ch;while(*p) { switch(*p) { case '(': case '[': case '{': PushStack(S,*p++); break; case ')': case ']': case '}': if(StackEmpty(S)) { printf(“缺少左括号.n”); return; } else { GetTop(S,&e); if(Match(e,*p)) PopStack(S,&e); else { printf(“左右括号不配对.n”); return; } } default: p++; } } if(StackEmpty(S)) printf(“括号匹配.n”);else printf(“缺少右括号.n”);} int Match(DataType e,DataType ch){ if(e=='('&&ch==')') return 1;else if(e=='['&&ch==']') return 1;else if(e=='{'&&ch=='}') return 1;else return 0;} 用队列实现在屏幕上打印杨辉三角 /*包含头文件*/ #include /*定义链式队列元素的类型为整数类型*/ #define MaxSize 100 void PrintArray(int a[],int n);void YangHuiTriangle(int N); typedef struct QNode { DataType data;struct QNode* next;}LQNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue; void InitQueue(LinkQueue *LQ) /*将带头结点的链式队列初始化为空队列需要把头结点的指针域置为0*/ { LQ->front=(LQNode*)malloc(sizeof(LQNode));if(LQ->front==NULL)exit(-1); LQ->front->next=NULL;/*把头结点的指针域置为为0*/ LQ->rear=LQ->front;} int QueueEmpty(LinkQueue LQ) /*判断链式队列是否为空，队列为空返回1，否则返回0*/ { if(LQ.front->next==NULL)/*当链式队列为空时，返回1，否则返回0*/ return 1; else return 0;} int EnterQueue(LinkQueue *LQ,DataType e)/*将元素e插入到链式队列LQ中，插入成功返回1*/ { LQNode *s;s=(LQNode*)malloc(sizeof(LQNode));/*为将要入队的元素申请一个结点的空间*/ if(!s)exit(-1); /*如果申请空间失败，则退出并返回参数-1*/ s->data=e; /*将元素值赋值给结点的数据域*/ s->next=NULL; /*将结点的指针域置为空*/ LQ->rear->next=s; /*将原来队列的队尾指针指向p*/ LQ->rear=s; /*将队尾指针指向p*/ return 1;} //int DeleteQueue(LinkQueue *LQ,DataType *e)///*删除链式队列中的队头元素，并将该元素赋值给e，删除成功返回1，否则返回0*/ //{ // LQNode *s;//if(LQ->front==LQ->rear)/*在删除元素之前，判断链式队列是否为空*/ // return 0;// else //{ // s=LQ->front->next; /*使指针p指向队头元素的指针*/ // *e=s->data; /*将要删除的队头元素赋值给e*/ // LQ->front->next=s->next; /*使头结点的指针指向指针p的下一个结点*/ // if(LQ->rear==s)LQ->rear=LQ->front;/*如果要删除的结点是队尾，则使队尾指针指向队头指针*/ // free(s); /*释放指针p指向的结点*/ // return 1;// } //} int GetHead(LinkQueue LQ,DataType *e)/*取链式队列中的队头元素，并将该元素赋值给e，取元素成功返回1，否则返回0*/ { LQNode *s;if(LQ.front==LQ.rear)/*在取队头元素之前，判断链式队列是否为空*/ return 0;else { s=LQ.front->next;/*将指针p指向队列的第一个元素即队头元素*/ *e=s->data; /*将队头元素赋值给e，取出队头元素*/ return 1;} } /*出队操作。*/ int DeleteQueue(LinkQueue *Q,DataType *x){ /* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */ LQNode * p; if(Q->front==Q->rear) return(0);p=Q->front->next;Q->front->next=p->next;/* 队头元素p出队 */ if(Q->front==NULL)/* 如果队中只有一个元素p，则p出队后成为空队 */ Q->rear=Q->front; *x=p->data;free(p); /* 释放存储空间 */ return(1);} void YangHuiTriangle(int N)/*链式队列实现打印杨辉三角*/ { int i,j,k,n;DataType e,t;int temp[MaxSize]; LinkQueue Q;k=0;InitQueue(&Q); EnterQueue(&Q,1); /*产生第中间n-2行的元素*/ for(n=2;n<=N;n++) 在临时数组中*/ { k=0; EnterQueue(&Q,1); for(i=1;i<=n-2;i++) 并入队列*/ { DeleteQueue(&Q,&t); temp[k++]=t; GetHead(Q,&e); t=t+e; EnterQueue(&Q,t); } DeleteQueue(&Q,&t); temp[k++]=t; PrintArray(temp,k,N); EnterQueue(&Q,1); } k=0; while(!QueueEmpty(Q)) { /*定义一个临时数组，用于存放每一行的元素*/ /*初始化链队列*/ /*第一行元素入队*/ /*产生第i行元素并入队，同时将第i-1行的元素保存/*第i行的第一个元素入队*/ /*利用队列中第i-1行元素产生第i行的中间i-2个元素/*将第i-1行的元素存入临时数组*/ /*取队头元素*/ /*利用队中第i-1行元素产生第i行元素*/ /*将第i-1行的最后一个元素存入临时数组*/ /*第i行的最后一个元素入队*/ /*将最后一行元素存入数组之前，要将下标k置为0*/ /*将最后一行元素存入临时数组*/ DeleteQueue(&Q,&t); temp[k++]=t; if(QueueEmpty(Q)) PrintArray(temp,k,N);} } void main(){ int n;printf(“请输入要打印的行数：n=:”);scanf(“%d”,&n); YangHuiTriangle(n);} void PrintArray(int a[],int n,int N)/*打印数组中的元素，使能够呈正确的形式输出*/ { int i;static count=0; /*记录输出的行*/ for(i=0;i /*打印空格*/ printf(“ ”);count++;for(i=0;i /*打印数组中的元素*/ printf(“%6d”,a[i]);printf(“n”);} 用栈实现迷宫问题求解 #include #define OVERFLOW-1 #define MAX 100 typedef struct { int x; int y; int d;}Data; typedef struct { int pos; Data data[MAX];}SNode,*Stack; Stack InitStack() { Stack pStack; pStack=(Stack)malloc(sizeof(SNode)); if(!pStack) exit(OVERFLOW); pStack->pos=-1; return pStack;} int IsEmpty(Stack pstack){ return pstack->pos==-1;} void Push(Stack pStack,Data x){ if(pStack->pos>=MAX-1) exit(OVERFLOW); else { pStack->pos++; pStack->data[pStack->pos]=x; } } void Pop(Stack pStack){ if(pStack->pos==-1) exit(OVERFLOW); else pStack->pos--;} Data GetTop(Stack pStack){ return pStack->data[pStack->pos];} Data SetStackElem(int x,int y,int d){ Data element; element.x=x; element.y=y; element.d=0; return element;} void DisplayPath(Stack pStack){ Data element; printf(“The path is:n”); while(!IsEmpty(pStack)) { element=GetTop(pStack); Pop(pStack); printf(“The node is:(%d,%d)n”,element.x,element.y); } } void MazePath(int maze[8][11],int direction[4][2],int x1,int y1,int x2,int y2){ int i,j,k,g,h; Stack pStack; Data element; pStack=InitStack(); maze[x1][y1]=2; Push(pStack,SetStackElem(x1,y1,0)); while(!IsEmpty(pStack)){ element=GetTop(pStack); Pop(pStack); i=element.x; j=element.y; k = element.d; while(k<=3) { g=i+direction[k][0]; h=j+direction[k][1]; if(g==x2 && h==y2 && maze[g][h]==0) { Push(pStack,SetStackElem(i,j,k)); Push(pStack,SetStackElem(x2,y2,k)); DisplayPath(pStack); return; } if(maze[g][h]==0) { maze[g][h]=2; Push(pStack,SetStackElem(i,j,k+1)); i=g; j=h; k=0; } else k++; } } printf(“The path has not been foundn”);} void main(){ int direction[4][2]={0,1,1,0,0,-1,-1,0}; int maze[8][11]= { 1,1,1,1,1,1,1,1,1,1,1，1,0,1,0,0,1,1,1,0,0,1，1,0,0,0,0,0,1,0,0,1,1，1,0,1,1,1,0,0,0,1,1,1，1,0,0,0,1,0,1,1,0,1,1，1,1,0,0,1,0,1,1,0,0,1，1,1,1,0,1,0,0,0,0,0,1，1,1,1,1,1,1,1,1,1,1,1 }; int i,j; printf(“The maze is:n”); for(i=0;i<8;i++){ for(j=0;j<11;j++) printf(“%2d”,maze[i][j]); printf(“n”);};MazePath(maze,direction,1,1,6,9);} 用队列实现迷宫问题求解 #include //行列坐标 int pre;}sqtype; sqtype sq[r];struct moved { int x, y;//坐标增量，取值-1，0，1 }move[8]; int maze[m2][n2]; int PATH(int maze[][n2])//找迷宫maze的路径 { int i,j,k,v,front,rear,x,y;int mark[m2][n2];for(i=0;i for(j=0;j mark[i ][j]=0;printf(“Please Input move arrayn”);for(i=0;i<8;i++){ scanf(“%d,%d”,&move[i ].x,&move[i ].y);sq[1].x=1;sq[1].y=1;sq[1].pre=0;front=1;rear=1;mark[1][1]=1; //标记入口以到达过 while(front<=rear){ x=sq[front].x; y=sq[front].y; //(x,y)为出发点 for(v=0;v<8;v++)//搜索(x,y)的8个相邻(i,j)是否可以到达 { i=x+move[v].x; j=y+move[v].y; if((maze[i ][j]==0)&&(mark[i ][j]==0))//(i,j)为可以到达点，将起入队 { rear++; sq[rear].pre=front; mark[i ][j]=1;//标记(i,j)已经到达过 } if((i==m)&&(j==n)) //到达出口 { printf(“THE PATH: n”); k=rear; do { printf(“(%d %d)<-”,sq[k].x,sq[k].y); k=sq[k].pre;//找前一点 }while(k!=0);//k=0是已经到达 for(i=1;i<19;i++) printf(“%3d”,i); printf(“n”); for(i=1;i<19;i++) printf(“%3d”,sq[i ].x); printf(“n”); for(i=1;i<19;i++) printf(“%3d”,sq[i ].y); printf(“n”); for(i=1;i<19;i++) printf(“%3d”,sq[i ].pre); printf(“n”); return(1); //成功返回 } } front++; //出队，front 指向新的出发点 } } //队空，循环结束 printf(“There is no path!n”);return(0); //迷宫没有路径返回 } main(){ int i,j;for(i=0;i<10;i++){ maze[0][i ]=1; maze[7][i ]=1;} for(i=0;i<8;i++){ maze[i ][0]=1; maze[i ][9]=1;} /*for(i=1;i<7;i++) for(j=1;j<9;j++) { printf(“%d %d”,i,j); scanf(“%d”,&maze[i ][j]); }*/ maze[1][1]=0;maze[1][2]=1;maze[1][3]=0;maze[1][4]=1;maze[1][5]=1;maze[1][6]=0;maze[1][7]=1;maze[1][8]=1; maze[2][1]=1;maze[2][2]=0;maze[2][3]=0;maze[2][4]=1;maze[2][5]=1;maze[2][6]=0;maze[2][7]=1;maze[2][8]=0;maze[3][1]=0;maze[3][2]=1;maze[3][3]=1;maze[3][4]=0;maze[3][5]=0;maze[3][6]=1;maze[3][7]=1;maze[3][8]=1;maze[4][1]=1;maze[4][2]=0;maze[4][3]=0;maze[4][4]=1;maze[4][5]=1;maze[4][6]=0;maze[3][7]=0;maze[4][8]=1;maze[5][1]=1;maze[5][2]=1;maze[5][3]=0;maze[5][4]=0;maze[5][5]=1;maze[5][6]=1;maze[5][7]=0;maze[5][8]=1;maze[6][1]=0;maze[6][2]=1;maze[6][3]=1;maze[6][4]=1;maze[6][5]=0;maze[6][6]=0;maze[6][7]=0;maze[6][8]=0; printf(“n”);for(i=0;i<8;i++){ for(j=0;j<10;j++) printf(“%d”,maze[i ][j]); printf(“n”);} PATH(maze);} 分别用队列实现一个列车调度系统。 实验3 树的应用 一、实验目的 1、领会并理解二叉树的类型定义。 2、熟练掌握二叉树的主要特性。 3、熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。 4、熟练掌握二叉树和树的各种存储结构及其建立的算法。 5、了递归算法的实现过程。 二、实验内容及步骤 1、实现二叉树的抽象数据类型。 2、构造一棵二叉树并用递归实现其先序、中序、后序遍历算法并验证。 3、用非递归算法实现二叉树的中序遍历。 4、给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。 三、实验步骤与调试过程 利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈，之后，左节点进栈；接着，弹出栈顶元素,此结点的右结点进栈，之后左节点进栈，弹出栈顶元素，直到栈为空。 从根节点开始，循环，只要有左子节点则进栈，直到左子节点为空。接着弹出栈顶输出，判断该结点是否有右子节点，若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，有则进栈，直到左子节点为空；若该右子节点没有左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；接着又要判断刚进栈的这个节点，是否有左子节点，有则进栈，没有则继续弹栈。 从根结点开始，只要左子节点非空，则进栈，直到左子节点为空为止。取出栈顶元素，判断取出的栈顶元素是否有右子节点，或者右子节点是否被访问过，若满足条件，则输出该结点，同时弹栈，并且记录下该访问的节点。取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点。 四、实验结果 五、疑难小结 用图形显示遍历能够是人更好的明白二叉树的遍历，更好的理解二叉树的链式结构的存储，理解二叉树遍历的过程，能够针对递归结构的二叉树进行查询、修改、删除的操作。 六、主要算法和程序清单 二叉树递归实现其先序、中序、后序遍历算法并验证。/*包含头文件及宏定义*/ #include /*定义栈的最大容量*/ /*函数的声明*/ void CreateBitTree2(BiTree *T,char str[]);/*利用括号嵌套的字符串建立二叉树的函数声明*/ void LevelPrint(BiTree T); /*按层次输出二叉树的结点*/ void TreePrint(BiTree T,int nLayer);/*按树状打印二叉树*/ typedef struct Node /*二叉链表存储结构类型定义*/ { DataType data; /*数据域*/ struct Node *lchild; /*指向左孩子结点*/ struct Node *rchild; /*指向右孩子结点*/ }*BiTree,BitNode; void InitBitTree(BiTree *T)/*二叉树的初始化操作*/ { *T=NULL;} void DestroyBitTree(BiTree *T)/*销毁二叉树操作*/ { if(*T) /*如果是非空二叉树*/ { if((*T)->lchild) DestroyBitTree(&((*T)->lchild)); if((*T)->rchild) DestroyBitTree(&((*T)->rchild)); free(*T); *T=NULL;} } void CreateBitTree(BiTree *T)/*递归创建二叉树*/ { DataType ch; scanf(“%c”,&ch); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode));/*生成根结点*/ if(!(*T)) exit(-1); (*T)->data=ch; CreateBitTree(&((*T)->lchild)); /*构造左子树*/ CreateBitTree(&((*T)->rchild)); /*构造右子树*/ } } int InsertLeftChild(BiTree p,BiTree c)/*二叉树的左插入操作*/ { if(p) /*如果指针p不空*/ { c->rchild=p->lchild; /*p的原来的左子树成为c的右子树*/ p->lchild=c; /*子树c作为p的左子树*/ return 1; } return 0;} int InsertRightChild(BiTree p,BiTree c)/*二叉树的右插入操作*/ { if(p) /*如果指针p不空*/ { c->rchild=p->rchild; /*p的原来的右子树作为c的右子树*/ p->rchild=c; /*子树c作为p的右子树*/ return 1; } return 0;} BiTree Point(BiTree T,DataType e)/*查找元素值为e的结点的指针*/ { BiTree Q[MaxSize]; /*定义一个队列，用于存放二叉树中结点的指针*/ int front=0,rear=0; /*初始化队列*/ BitNode *p; if(T) /*如果二叉树非空*/ { Q[rear]=T; rear++; while(front!=rear)/*如果队列非空*/ { p=Q[front]; /*取出队头指针*/ front++; /*将队头指针出队*/ if(p->data==e) return p; if(p->lchild) /*如果左孩子结点存在，将左孩子指针入队*/ { Q[rear]=p->lchild;/*左孩子结点的指针入队*/ rear++; } if(p->rchild) /*如果右孩子结点存在，将右孩子指针入队*/ { Q[rear]=p->rchild;/*右孩子结点的指针入队*/ rear++; } } } return NULL;} DataType LeftChild(BiTree T,DataType e)/*返回二叉树的左孩子结点元素值操作*/ { BiTree p; if(T) { p=Point(T,e); if(p&&p->lchild) 在*/ return p->lchild->data; } return;} DataType RightChild(BiTree T,DataType e)/*返回二叉树的右孩子结点元素值操作*/ { BiTree p; if(T) { p=Point(T,e); if(p&&p->rchild) 在*/ return p->rchild->data; } return;} int DeleteLeftChild(BiTree p)/*二叉树的左删除操作*/ { if(p) { DestroyBitTree(&(p->lchild)); return 1; } return 0;} int DeleteRightChild(BiTree p)/*二叉树的左删除操作*/ { if(p) { DestroyBitTree(&(p->rchild)); return 1; } return 0;} void main() /*如果二叉树不空*/ /*p是元素值e的结点的指针*/ /*如果p不为空且p的左孩子结点存 /*返回p的左孩子结点的元素值*/ /*如果二叉树不空*/ /*p是元素值e的结点的指针*/ /*如果p不为空且p的右孩子结点存/*返回p的右孩子结点的元素值*/ /*如果p不空*/ /*删除左子树*/ /*如果p不空*/ /*删除右子树*/ { BiTree T,root;printf(“根据括号嵌套(a(b(c,d),e(f(,g),h(i)))建立二叉树:n”);CreateBitTree2(&T,“(a(b(c,d),e(f(,g),h(i)))”);printf(“按层次输出二叉树的序列：n”);LevelPrint(T);printf(“n”);printf(“按树状打印二叉树：n”);TreePrint(T,1);printf(“根据括号嵌套(A(B(D(,H),E(,I)),C(F,G)))建立二叉树:n”);CreateBitTree2(&root,“(A(B(D(,H),E(,I)),C(F,G)))”);printf(“按层次输出二叉树的序列：n”);LevelPrint(root);printf(“n”);printf(“按树状打印二叉树：n”);TreePrint(root,1);DestroyBitTree(&T);DestroyBitTree(&root);} void LevelPrint(BiTree T)/*按层次打印二叉树中的结点*/ { BiTree queue[MaxSize]; /*定义一个队列，用于存放结点的指针*/ BitNode *p; int front,rear; /*定义队列的队头指针和队尾指针*/ front=rear=-1; /*队列初始化为空*/ rear++; /*队尾指针加1*/ queue[rear]=T; /*将根结点指针入队*/ while(front!=rear) /*如果队列不为空*/ { front=(front+1)%MaxSize; p=queue[front]; /*取出队头元素*/ printf(“%c ”,p->data); /*输出根结点*/ if(p->lchild!=NULL) /*如果左孩子不为空，将左孩子结点指针入队*/ { rear=(rear+1)%MaxSize; queue[rear]=p->lchild; } if(p->rchild!=NULL) /*如果右孩子不为空，将右孩子结点指针入队*/ { rear=(rear+1)%MaxSize; queue[rear]=p->rchild; } } } void TreePrint(BiTree T,int level)/*按树状打印的二叉树*/ { int i;if(T==NULL) /*如果指针为空，返回上一层*/ return;TreePrint(T->rchild,level+1); /*打印右子树，并将层次加1*/ for(i=0;i /*按照递归的层次打印空格*/ printf(“ ”);printf(“%cn”,T->data); /*输出根结点*/ TreePrint(T->lchild,level+1); /*打印左子树，并将层次加1*/ } void CreateBitTree2(BiTree *T,char str[])/*利用括号嵌套的字符串建立二叉链表*/ { char ch;BiTree stack[MaxSize]; /*定义栈，用于存放指向二叉树中结点的指针*/ int top=-1; /*初始化栈顶指针*/ int flag,k;BitNode *p;*T=NULL,k=0;ch=str[k];while(ch!=' ') /*如果字符串没有结束*/ { switch(ch) { case '(': stack[++top]=p; flag=1; break; case ')': top--; break; case ',': flag=2; break; default: p=(BiTree)malloc(sizeof(BitNode)); p->data=ch; p->lchild=NULL; p->rchild=NULL; if(*T==NULL)/*如果是第一个结点，表示是根结点*/ *T=p; else { switch(flag) { case 1: stack[top]->lchild=p; break; case 2: stack[top]->rchild=p; break; } } } ch=str[++k];} } void PreOrderTraverse(BiTree T)/*先序遍历二叉树的递归实现*/ { if(T) /*如果二叉树不为空*/ { printf(“%2c”,T->data); /*访问根结点*/ PreOrderTraverse(T->lchild);/*先序遍历左子树*/ PreOrderTraverse(T->rchild); /*先序遍历右子树*/ } } void InOrderTraverse(BiTree T)/*中序遍历二叉树的递归实现*/ { if(T) /*如果二叉树不为空*/ { InOrderTraverse(T->lchild); /*中序遍历左子树*/ printf(“%2c”,T->data); /*访问根结点*/ InOrderTraverse(T->rchild);/*中序遍历右子树*/ } } void PostOrderTraverse(BiTree T)/*后序遍历二叉树的递归实现*/ { if(T) /*如果二叉树不为空*/ { PostOrderTraverse(T->lchild);/*后序遍历左子树*/ PostOrderTraverse(T->rchild); /*后序遍历右子树*/ printf(“%2c”,T->data); /*访问根结点*/ } } 用非递归算法实现二叉树的中序遍历 /*包含头文件及宏定义*/ #include /*定义栈的最大容量*/ /*函数的声明*/ void InOrderTraverse2(BiTree T);/*二叉树的中序遍历的非递归函数声明*/ void CreateBitTree2(BiTree *T,char str[]);/*利用括号嵌套的字符串建立二叉树的函数声明*/ typedef struct Node /*二叉链表存储结构类型定义*/ { DataType data; /*数据域*/ struct Node *lchild; /*指向左孩子结点*/ struct Node *rchild; /*指向右孩子结点*/ }*BiTree,BitNode; void InitBitTree(BiTree *T)/*二叉树的初始化操作*/ { *T=NULL;} //BiTree CreateBitTree()//{ // char ch;// BiTree b;// ch = getchar();// // if(ch == '@') //表示该结点为空结点 // { // b = NULL;// } // else // { // b =(BiTree)malloc(sizeof(BitNode));// b->data = ch;// b->lchild = CreateBitTree();// b->rchild = CreateBitTree();// } // // return b;//} void DestroyBitTree(BiTree *T)/*销毁二叉树操作*/ { if(*T) /*如果是非空二叉树*/ { if((*T)->lchild) DestroyBitTree(&((*T)->lchild)); if((*T)->rchild) DestroyBitTree(&((*T)->rchild)); free(*T); *T=NULL;} } void CreateBitTree(BiTree *T)/*递归创建二叉树*/ { DataType ch; scanf(“%c”,&ch); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode));/*生成根结点*/ if(!(*T)) exit(-1); (*T)->data=ch; CreateBitTree(&((*T)->lchild)); /*构造左子树*/ CreateBitTree(&((*T)->rchild)); /*构造右子树*/ } } int InsertLeftChild(BiTree p,BiTree c)/*二叉树的左插入操作*/ { if(p) /*如果指针p不空*/ { c->rchild=p->lchild; /*p的原来的左子树成为c的右子树*/ p->lchild=c; /*子树c作为p的左子树*/ return 1; } return 0;} int InsertRightChild(BiTree p,BiTree c)/*二叉树的右插入操作*/ { if(p) /*如果指针p不空*/ { c->rchild=p->rchild; /*p的原来的右子树作为c的右子树*/ p->rchild=c; /*子树c作为p的右子树*/ return 1; } return 0;} BiTree Point(BiTree T,DataType e)/*查找元素值为e的结点的指针*/ { BiTree Q[MaxSize]; /*定义一个队列，用于存放二叉树中结点的指针*/ int front=0,rear=0; /*初始化队列*/ BitNode *p; if(T) /*如果二叉树非空*/ { Q[rear]=T; rear++; while(front!=rear)/*如果队列非空*/ { p=Q[front]; /*取出队头指针*/ front++; /*将队头指针出队*/ if(p->data==e) return p; if(p->lchild) /*如果左孩子结点存在，将左孩子指针入队*/ { Q[rear]=p->lchild;/*左孩子结点的指针入队*/ rear++; } if(p->rchild) /*如果右孩子结点存在，将右孩子指针入队*/ { Q[rear]=p->rchild;/*右孩子结点的指针入队*/ rear++; } } } return NULL;} DataType LeftChild(BiTree T,DataType e)/*返回二叉树的左孩子结点元素值操作*/ { BiTree p; if(T) { p=Point(T,e); if(p&&p->lchild) 在*/ return p->lchild->data; } return;} DataType RightChild(BiTree T,DataType e)/*返回二叉树的右孩子结点元素值操作*/ { BiTree p; if(T) { p=Point(T,e); if(p&&p->rchild) 在*/ return p->rchild->data; } return;} int DeleteLeftChild(BiTree p)/*二叉树的左删除操作*/ { if(p) { DestroyBitTree(&(p->lchild)); return 1; } return 0;} int DeleteRightChild(BiTree p)/*二叉树的左删除操作*/ /*如果二叉树不空*/ /*p是元素值e的结点的指针*/ /*如果p不为空且p的左孩子结点存 /*返回p的左孩子结点的元素值*/ /*如果二叉树不空*/ /*p是元素值e的结点的指针*/ /*如果p不为空且p的右孩子结点存/*返回p的右孩子结点的元素值*/ /*如果p不空*/ /*删除左子树*/ { if(p) /*如果p不空*/ { DestroyBitTree(&(p->rchild)); /*删除右子树*/ return 1; } return 0;} void main(){ BiTree T,root;InitBitTree(&T);printf(“根据输入二叉树的先序序列创建二叉树('#'表示结束)：n”);CreateBitTree(&T);printf(“二叉树的中序序列：n”);printf(“递归：t”);InOrderTraverse(T);printf(“n”);printf(“非递归：”);InOrderTraverse2(T);printf(“n”);printf(“根据括号嵌套的字符串建立二叉树:n”);CreateBitTree2(&root,“(a(b(c,d),e(f(,g),h(i)))”);printf(“二叉树的中序序列：n”);InOrderTraverse(root);printf(“n”);DestroyBitTree(&T);DestroyBitTree(&root);} void CreateBitTree2(BiTree *T,char str[])/*利用括号嵌套的字符串建立二叉链表*/ { char ch;BiTree stack[MaxSize]; /*定义栈，用于存放指向二叉树中结点的指针*/ int top=-1; /*初始化栈顶指针*/ int flag,k;BitNode *p;*T=NULL,k=0;ch=str[k];while(ch!=' ') /*如果字符串没有结束*/ { switch(ch) { case '(': stack[++top]=p; flag=1; break; case ')': top--; break; case ',': flag=2; break; default: p=(BiTree)malloc(sizeof(BitNode)); p->data=ch; p->lchild=NULL; p->rchild=NULL; if(*T==NULL)/*如果是第一个结点，表示是根结点*/ *T=p; else { switch(flag) { case 1: stack[top]->lchild=p; break; case 2: stack[top]->rchild=p; break; } } } ch=str[++k];} } void InOrderTraverse2(BiTree T)/*中序遍历二叉树的非递归实现*/ { BiTree stack[MaxSize]; /*定义一个栈，用于存放结点的指针*/ int top; /*定义栈顶指针*/ BitNode *p; /*定义一个结点的指针*/ top=0; /*初始化栈*/ p=T; while(p!=NULL||top>0){ while(p!=NULL) /*如果p不空，访问根结点，遍历左子树*/ { stack[top++]=p; /*将p入栈*/ p=p->lchild; /*遍历左子树*/ } if(top>0) /*如果栈不空*/ { p=stack[--top]; /*栈顶元素出栈*/ printf(“%2c”,p->data); /*访问根结点*/ p=p->rchild; /*遍历右子树*/ } } } 给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。#include /*定义一个无限大的值*/ /*哈夫曼树类型定义*/ typedef struct { unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree; typedef char **HuffmanCode;/*存放哈夫曼编码*/ int Min(HuffmanTree t,int n);void Select(HuffmanTree *t,int n,int *s1,int *s2);void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n);void HuffmanCoding2(HuffmanTree *HT,HuffmanCode *HC,int *w,int n);int Min(HuffmanTree t,int n)/*返回树中n个结点中权值最小的结点序号*/ { int i,flag;int f=infinity; /*f为一个无限大的值*/ for(i=1;i<=n;i++) if(t[i].weight f=t[i].weight,flag=i; t[flag].parent=1; /*给选中的结点的双亲结点赋值1，避免再次查找该结点*/ return flag;} void Select(HuffmanTree *t,int n,int *s1,int *s2)/*在n个结点中选择两个权值最小的结点序号，其中s1最小，s2次小*/ { int x;*s1=Min(*t,n);*s2=Min(*t,n);if((*t)[*s1].weight>(*t)[*s2].weight)/*如果序号s1的权值大于序号s2的权值，将两者交换，使s1最小，s2次小*/ { x=*s1; *s1=*s2; *s2=x;} } void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)/*构造哈夫曼树HT，哈夫曼树的编码存放在HC中，w为n个字符的权值*/ { int m,i,s1,s2,start;unsigned int c,f;HuffmanTree p;char *cd;if(n<=1) return;m=2*n-1;*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));/*第零个单元未用*/ for(p=*HT+1,i=1;i<=n;++i,++p,++w) /*初始化n个叶子结点*/ { (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0;} for(;i<=m;++i,++p) /*将n-1个非叶子结点的双亲结点初始化化为0*/ (*p).parent=0;for(i=n+1;i<=m;++i) /*构造哈夫曼树*/ { Select(HT,i-1,&s1,&s2);/*查找树中权值最小的两个结点*/ (*HT)[s1].parent=(*HT)[s2].parent=i; (*HT)[i].lchild=s1; (*HT)[i].rchild=s2; (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;} /*从叶子结点到根结点求每个字符的哈夫曼编码*/ *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));/*为哈夫曼编码动态分配空间*/ cd[n-1]=' '; /*求n个叶子结点的哈夫曼编码*/ for(i=1;i<=n;i++){ start=n-1; /*编码结束符位置*/ for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)/*从叶子结点到根结点求编码*/ if((*HT)[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; (*HC)[i]=(char*)malloc((n-start)*sizeof(char));/*为第i个字符编码分配空间*/ strcpy((*HC)[i],&cd[start]); /*将当前求出结点的哈夫曼编码复制到HC*/ } free(cd);} void main(){ HuffmanTree HT;HuffmanCode HC;int *w,n,i;printf(“请输入叶子结点的个数: ”);scanf(“%d”,&n);w=(int*)malloc(n*sizeof(int));/*为n个结点的权值分配内存空间*/ for(i=0;i printf(“请输入第%d个结点的权值:”,i+1); scanf(“%d”,w+i);} HuffmanCoding(&HT,&HC,w,n);for(i=1;i<=n;i++){ printf(“哈夫曼编码:”); puts(HC[i]);} HuffmanCoding2(&HT,&HC,w,n);for(i=1;i<=n;i++){ printf(“哈夫曼编码:”); puts(HC[i]);} /*释放内存空间*/ for(i=1;i<=n;i++) free(HC[i]);free(HC);free(HT);} void HuffmanCoding2(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /*构造哈夫曼树HT，并从根结点到叶子结点求赫夫曼编码并保存在HC中*/ { int s1,s2,i,m; unsigned int r,cdlen; char *cd;HuffmanTree p; if(n<=1) return;m=2*n-1;*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=*HT+1,i=1;i<=n;i++,p++,w++){ (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0;} for(;i<=m;++i,++p) (*p).parent=0;/*构造哈夫曼树HT*/ for(i=n+1;i<=m;i++) { Select(HT,i-1,&s1,&s2); (*HT)[s1].parent=(*HT)[s2].parent=i; (*HT)[i].lchild=s1; (*HT)[i].rchild=s2; (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;} /*从根结点到叶子结点求赫夫曼编码并保存在HC中*/ *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char)); r=m; /*从根结点开始*/ cdlen=0; /*编码长度初始化为0*/ for(i=1;i<=m;i++) (*HT)[i].weight=0;/*将weight域作为状态标志*/ while(r){ if((*HT)[r].weight==0)/*如果weight域等于零，说明左孩子结点没有遍历*/ { (*HT)[r].weight=1;/*修改标志*/ if((*HT)[r].lchild!=0)/*如果存在左孩子结点，则将编码置为0*/ { r=(*HT)[r].lchild; cd[cdlen++]='0'; } else if((*HT)[r].rchild==0)/*如果是叶子结点，则将当前求出的编码保存到HC中*/ { (*HC)[r]=(char *)malloc((cdlen+1)*sizeof(char)); cd[cdlen]=' '; strcpy((*HC)[r],cd); } } else if((*HT)[r].weight==1)/*如果已经访问过左孩子结点，则访问右孩子结点*/ { (*HT)[r].weight=2;/*修改标志*/ if((*HT)[r].rchild!=0) { r=(*HT)[r].rchild; cd[cdlen++]='1'; } } else /*如果左孩子结点和右孩子结点都已经访问过，则退回到双亲结点*/ { (*HT)[r].weight=0; r=(*HT)[r].parent; --cdlen; /*编码长度减1*/ } } free(cd);} 实验4 图论及其应用 一、实验目的 1、了解图的基本概念及术语,并能够熟练掌握图的两种存储结构(邻接矩阵和邻接表)。 2、理解最小生成树的概念，能按Prim算法构造最小生成树。 3、掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)、拓扑排序、关键路径、最短路径的算法思想。 二、实验内容及步骤 1、实现网（有权图）的存储结构。 2、利用prim算法构造它的最小生成树。 3、选择一个源点，寻找从原点出发到达其它顶点的最短路径。 三、实验步骤与调试过程 在程序编辑的过程中，有许多地方出现不能顺序运行的，还有代码出现遗漏出错，图的遍历是重点但因为知识的残缺不能完整的编译出来，又或者编译的程序不能得到正确的结果，再通过多人的合作共同讨论后得到了满意的解决。 四、实验结果 五、疑难小结 经过这次这么复杂而程序实验，我终于发现了调用函数的巨大优越性，以前遇到倒是很短的程序，感觉调用有点多余，但复杂的程序如果不采用调用的话，会使程序非常乱，改程序是不知道从哪改，调用函数能够更好使程序简洁化，层次化，更加让人看懂，这次试验的逻辑性给我们很大启发，本次试验让我对图有了更深的认识，再通过多次的更改后终于将实验做出来，在实验中也出现了许多问题，又不出结果，又不能运行的，但最终只要努力都会搞定的。 六、主要算法和程序清单 实现网（有权图）的存储结构。 邻接矩阵存储结构 #include /*定义一个无限大的值*/ #define MaxSize 50 /*最大顶点个数*/ typedef enum{DG,DN,UG,UN}GraphKind;/*图的类型：有向图、有向网、无向图和无向网*/ typedef struct { VRType adj; /*对于无权图，用1表示相邻，0表示不相邻；对于带权图，存储权值*/ InfoPtr *info; /*与弧或边的相关信息*/ }ArcNode,AdjMatrix[MaxSize][MaxSize]; typedef struct /*图的类型定义*/ { VertexType vex[MaxSize];/*用于存储顶点*/ AdjMatrix arc; /*邻接矩阵，存储边或弧的信息*/ int vexnum,arcnum; /*顶点数和边（弧）的数目*/ GraphKind kind; /*图的类型*/ }MGraph;void CreateGraph(MGraph *N);int LocateVertex(MGraph N,VertexType v);void DestroyGraph(MGraph *N);void DisplayGraph(MGraph N); void CreateGraph(MGraph *N)/*采用邻接矩阵表示法创建有向网N*/ { int i,j,k,w,InfoFlag,len;char s[MaxSize];VertexType v1,v2;printf(“请输入有向网N的顶点数,弧数,弧的信息(是:1,否:0): ”);scanf(“%d,%d,%d”,&(*N).vexnum,&(*N).arcnum,&InfoFlag);printf(“请输入%d个顶点的值(<%d个字符):n”,N->vexnum,MaxSize);for(i=0;i scanf(“%s”,N->vex[i]);for(i=0;i for(j=0;j { N->arc[i][j].adj=INFINITY; N->arc[i][j].info=NULL;/*弧的信息初始化为空*/ } printf(“请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): n”,N->arcnum); for(k=0;k { scanf(“%s%s%d”,v1,v2,&w);/*输入两个顶点和弧的权值*/ i=LocateVertex(*N,v1); j=LocateVertex(*N,v2); N->arc[i][j].adj=w; if(InfoFlag) /*如果弧包含其它信息*/ { printf(“请输入弧的相关信息: ”); gets(s); len=strlen(s); if(len) { N->arc[i][j].info=(char*)malloc((len+1)*sizeof(char));/* 有向 */ strcpy(N->arc[i][j].info,s); } } } N->kind=DN; /*图的类型为有向网*/ } int LocateVertex(MGraph N,VertexType v)/*在顶点向量中查找顶点v，找到返回在向量的序号，否则返回-1*/ { int i;for(i=0;i if(strcmp(N.vex[i],v)==0) return i; return-1;} void DestroyGraph(MGraph *N)/*销毁网N*/ { int i,j;for(i=0;i /*释放弧的相关信息*/ for(j=0;j if(N->arc[i][j].adj!=INFINITY)/*如果存在弧*/ if(N->arc[i][j].info!=NULL)/*如果弧有相关信息，释放该信息所占用空间*/ { free(N->arc[i][j].info); N->arc[i][j].info=NULL; } N->vexnum=0;/*将网的顶点数置为0*/ N->arcnum=0;/*将网的弧的数目置为0*/ } void DisplayGraph(MGraph N)/*输出邻接矩阵存储表示的图G*/ { int i,j;printf(“有向网具有%d个顶点%d条弧，顶点依次是: ”,N.vexnum,N.arcnum);for(i=0;i /*输出网的顶点*/ printf(“%s ”,N.vex[i]);printf(“n有向网N的:n”); /*输出网N的弧*/ printf(“序号i=”);for(i=0;i printf(“%8d”,i); printf(“n”);for(i=0;i printf(“%8d”,i); for(j=0;j printf(“%8d”,N.arc[i][j].adj); printf(“n”); } } void main(){ MGraph N;printf(“创建一个网：n”);CreateGraph(&N);printf(“输出网的顶点和弧：n”);DisplayGraph(N);printf(“销毁网：n”);DestroyGraph(&N);} 利用prim算法构造它的最小生成树。#include /*定义一个无限大的值*/ #define MaxSize 50 /*最大顶点个数*/ typedef enum{DG,DN,UG,UN}GraphKind;/*图的类型：有向图、有向网、无向图和无向网*/ typedef struct { VRType adj; /*对于无权图，用1表示相邻，0表示不相邻；对于带权图，存储权值*/ InfoPtr *info; /*与弧或边的相关信息*/ }ArcNode,AdjMatrix[MaxSize][MaxSize];typedef struct /*图的类型定义*/ { VertexType vex[MaxSize];/*用于存储顶点*/ AdjMatrix arc; /*邻接矩阵，存储边或弧的信息*/ int vexnum,arcnum; /*顶点数和边（弧）的数目*/ GraphKind kind; /*图的类型*/ }MGraph; /*记录从顶点集合U到V-U的代价最小的边的数组定义*/ typedef struct { VertexType adjvex;VRType lowcost;}closeedge[MaxSize];void CreateGraph(MGraph *N);int LocateVertex(MGraph N,VertexType v);void DestroyGraph(MGraph *N);void DisplayGraph(MGraph N); void Prim(MGraph G,VertexType u);int MiniNum(closeedge SZ,MGraph G); void main(){ MGraph N;printf(“创建一个无向网：n”);CreateGraph(&N);DisplayGraph(N);Prim(N,“A”); DestroyGraph(&N);} void Prim(MGraph G,VertexType u)/*利用普里姆算法求从第u个顶点出发构造网G的最小生成树T*/ { int i,j,k;closeedge closedge;k=LocateVertex(G,u);/*k为顶点u对应的序号*/ for(j=0;j strcpy(closedge[j].adjvex,u); closedge[j].lowcost=G.arc[k][j].adj;} closedge[k].lowcost=0;/*初始时集合U只包括顶点u*/ printf(“无向网的最小生成树的各条边分别是:n”);for(i=1;i k=MiniNum(closedge,G);/*k为与U中顶点相邻接的下一个顶点的序号*/ printf(“(%s-%s)n”,closedge[k].adjvex,G.vex[k]);/*输出生成树的边*/ closedge[k].lowcost=0;/*第k顶点并入U集*/ for(j=0;j if(G.arc[k][j].adj C语言实验 实验一：C语言程序调试基础 一、实验目的 1.掌握C语言源程序的编写方法和调试方法 2.学会使用VC6开发工具及调试过程的查错纠错能力。 二、任务 调试课本例子：例2.19、例3.5、例5.9 三、实验过程及结果 1.鼠标左键双击ＶＣ，打开程序；单击打开的Ｎｅｗ的页面中，单击 键，选择键，选择，在新，最后单击键，就可以建立一个新的页面。 ２．在界面中输入例２．１９的内容，单击 键进行调试，底下的对话框出现 一句话时，说明我们编写的程序无错，就可以单击键，来运行程序。运行结果及编写程序内容如图： ４．关闭这两个窗口，再单击 实验二：顺序程序设计 一、实验目的： 1.掌握顺序程序的设计方法； 键，选择 ； 2.掌握输入输出控制语句。 二、实验任务与要求 1.第3章课后习题T2 2.第3章课后习题T7 三、实验过程及结果 实验三：分支程序设计 一、目的 1.掌握分支程序控制语句的语法格式及纷争程序设计方法。2.了解分支程序的条件表达式及运算规则； 3.掌握分支程序控制语句的嵌套使用方法。 二、任务 1.第4章课后习题T6 2.第4章课后习题T8 3.第4章课后习题T12 三、实验过程及结果 实验四：循环程序设计 一、目的 1.掌握循环程序的控制语句的语法规则； 2.掌握循环程序的编写方法； 3.掌握循环程序的嵌套与退出控制方法。 二、任务 1.求100~200间的全部素数。2.第5章课后习题T8 3.第5章课后习题T10 三、实验过程及结果 实验五：数组 一、目的 1.掌握数组的定义及使用方法 2.掌握字符数组的相关操作函数。 二、任务 1.用数组求Fibonacci数列的钱40项，每5个一行。2.将一个3行8列的数组A转置为数组B。3.已知字符串str1=”abcde”,str2=”hijklm”，比阿尼写程序分别实现str1与str2的连接、求长度、比较等操作。 三、实验过程及结果 实验六：函数 一、目的 1.掌握函数的定义与调用方法。2.掌握函数参数的专递方式。 3.掌握函数的嵌套调用和递归调用方法。 二、任务 1.编写一函数，用冒泡排序法实现对数组A的排序。2.编写一函数，用选择排序法实现对数组A的排序。3.编写一函数，实现对给定年year是不是闰年。4.编写一函数，实现对给定整数m是不是素数。 5.利用递归算法，编写一函数，求Fibonacci数列的第n项。 三、实验过程及结果 实验七：变量作用域 一、目的 1.了解变量的存储类型及生命周期、作用域的性质。2.准确使用局部变量和全局变量。 二、任务 1.根据变量作用域知识，分析下列程序的运行效果。2.调试程序，分析个变量的作用范围和生命期。 #include Printf(“i=%dn”,i); int i=40; printf(“i=%dn”,i); fun1(); fun1();} 三、实验过程及结果 实验八：结构体 一、目的 1.掌握结构体的定义方法和使用。 二、任务 定义一日期（年、月、日）结构体，编程实现日期的输入、日期的输出、日期加上一个整型天数、两个日期数据相减等功能。 三、实验过程及结果 数据结构【第四次】实验报告 学院： 班级： 学号： 姓名： 实验四 （一）实验名称：C语言数据结构与指针 （二）实验目的：巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。 （三）实验内容： 1)学生信息的显示，具体要求如下： 定义一个结构体描述学生信息(学号，姓名，性别，年龄，住址)； 设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型； 设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于5人）。 2)输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如 输入：10 2 30 4 5，逆置后显示为：5 4 30 2 10。 （四）源代码： #define MAXSIZE 100 #include ElemType data[MAXSIZE];int length; } SqList;SqList l; void InitList(SqList &L) { L.length = 0;} void CreatSqlist(SqList &L,int n) { printf(“请输入节点”);int i;for(i=0;i } void Output(SqList &L) { int i;for(i=0;i printf(“n”);} int chazhao(SqList &L,int x){ int i,k;printf(“n请输入你要查找的元素 x=?”);scanf(“%d”,&x);for(i=0;i<=(L.length+1);i++){ if(x==L.data[i]) {printf(“要查找的元素%d位于线性表第%d位上nn”,x,i+1); k=0; break; } } if(k!=0)printf(“所要查找的元素%d不在线性表中”,x);return 0;} int GET(SqList &L,int i){ int m;if((i<0)||(i>L.length)){printf(“所查找范围超出线性表长度”);return 1;} else if((i>=1)&&(i<=L.length)){ m=L.data[i-1];}printf(“%d ”,m);return 0;} int DELETE(SqList &L,int i){ int j;if(i<1||i>L.length){printf(“删除错误”);return 0;} else { for(j=i;j L.data[j-1]=L.data[j]; L.length--; } return 1;} int INSERT(SqList &L,int x,int i){ int j;if(L.length>=MAXSIZE-1){printf(“over flow”);return 1;} else if((i<1)||(i>L.length+1)){printf(“插入错误”);return 1;} else {for(j=L.length;j>=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=x;L.length=L.length+1;} return 0;} int main(){int n,i,k,x;InitList(l);printf(“请输入线性表的长度 ”);scanf(“%d”,&n);CreatSqlist(l,n);Output(l); printf(“请输入你要查找的数所在的节点位置”);scanf(“%d”,&i);GET(l,i);chazhao(l,x);printf(“请输入你要删除元素的位置=?”);scanf(“%d”,&k);DELETE(l,k);Output(l);printf(“请输入你要插入的数和位置x,i=?”);scanf(“%d,%d”,&x,&i);INSERT(l,x,i);Output(l);return 0;} （五）代码运行结果： （六）需求分析 1、输入的形式和输出值的范围：1）输入10个整数。2）输出整个顺序线性表。 2、输出的形式：完成各种功能后的线性表。 3、程序所能达到的功能：1）所存储顺序线性表的显示、元素的查找、删除和插入。 （七）所用到的函数： void CreatSqlist void Output Int chazhao int GET int INSERT int DELETE （八）心得体会： 此次实验的过程中还是遇到了很多意想不到的问题，让我再一次深刻的体会到了理论和实践的差距。使我清楚的知道技术上的东西，细节更显得尤为重要和值得重视。困难虽有，但在我的努力下，最后还是成功完成了实验。总而言之，这次实验又增长了我不好知识。 《数据结构》课程设计题目(程序实现采用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 目录 前言..................................................................................................................2 概要设计..................................................................................................................3 1.1 数据结构设计...........................................................................................3 2.1 算法设计...................................................................................................3 2.1.1 建立链表的算法..............................................................................3 2.1.2 链表插入一个元素的算法..............................................................3 2.1.3 链表删除一个元素的算法..............................................................3 3.1 ADT描述..................................................................................................4 4.1 详细设计…………………………………………… ……………………………… 4 4.1.1 数据存储结构……………………………… ……………………………… 4.4.1.2 主要伪代码…… …………………… ……………………………………… 4 软件测试..................................................................................................................7 心得体会................................................................................................................11 源代码...................................................................................................................12 参考文献………………………………………………………………………...21 前言 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。 随着计算机科学的技术和发展，计算机的功能和运算速度不断地提高，其应用于信息处理的范围日益扩大。与之相应的，计算机的加工处理对象也从简单的数据发展到一般的符号，进而发展到更复杂的数据结构。数据结构是计算机程序设计的重要理论技术基础，数据结构的表示和操作都涉及到算法，如何描述数据的结构和讨论有关的算法，又涉及到程序设计语言。因此，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。我们通过对这门基础课程的学习，要学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适合的逻辑结构，储存结构及其相应的算法，并初步掌握算法时间分析和空间分析的技术。通过实际操作去了解数据结构原理，练习编写代码的能力，以及抽象能力。 从课程性质上讲，“数据结构”是一门专业技术基础课。它的要求是学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读，符合软件工程的规范。 概要设计 1.1 数据结构设计 采用链式储存结构。typedef struct LNode{ ElemType data;struct LNode *next;}LNode,*LinkList;2.1 算法设计 2.1.1 建立链表的算法 （1）算法思想分析 首先从表尾到表头逆向建立单链表,然后再建立的单链表基础上进行对链表上的元素进行查询,删除,插入的操作。（2）要点描述 首先建立一个带头结点的单链表，通过申请内存，先建立一个空链表。然后结点的插入，建立一个有多个结点的链表。在进行查询等操作。（3）时间和空间复杂度分析 程序的时间复杂度为O(n)。 2.1.2 链表插入一个元素的算法 （1）算法思想分析 要生成一个新数据域为X的结点，然后插入在单链表中。（2）要点描述 在链表中插入结点只需要修改指针。若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。 （3）时间和空间复杂度分析 时间复杂度O(n)2.1.3 链表删除一个元素的算法 （1）算法思想分析 要删除一个结点，必须修改指针并且释放空间。（2）要点描述 找到线性表中第i-1个结点，修改其指向后继的指针。 （3）时间和空间复杂度分析 时间复杂度O(n) 3.1 ADT描述 ADT LinkList{ 数据对象：D={ e | e∈LNode } 数据关系：R1={ 基本操作： GreateList_L(&L, n) 操作结果：构造了一个长为n的数据链表 ListDelete_L(&L, i, &e) 初始条件：链表L已存在而且非空 操作结果：删除L的第i个数据，并且用e返回其值 ListInsert_L(&L, i, e) 初始条件：链表L已存在 操作结果： 在L的第i个位置插入数据e GetElem(L, i, e) 初始条件：链表L已存在 操作结果：用e返回L中的第i个数据 }ADT LinkList 4.1 详细设计 4.1.1数据存储结构设计 采用单链式线性表实现 4.1.2 主要伪代码 Status GetElem(LinkList L, int i, ElemType *e){ int j=0;int d;LinkList p = L;while(p&&j } if(!p || j > i)return ERROR;printf(“您要查询的元素是:n”);d=p->data;printf(“%d”,d);printf(“n”);} void InitList(LinkList *L){ *L =(LinkList)malloc(sizeof(struct LNode));if(!*L)exit(OVERFLOW);(*L)->next = NULL;} Status ListInsert(LinkList L, int i, ElemType e){ int j = 0;LinkList p = L, s;while(p && j < i-1){ p = p->next;j++;} if(!p|| j > i-1)return ERROR;s =(LinkList)malloc(sizeof(struct LNode));s->data = e;s->next = p->next;p->next = s;return OK;} Status ListDelete(LinkList L, int i, ElemType *e){ int j = 0;LinkList p = L, q;while(p->next && j < i-1){ p = p->next; j++;} if(!p->next || j > i-1)return ERROR;q = p->next;p->next = q->next;*e = q->data;free(q);return OK;} void ListTraverse(LinkList L, void(*vi)(ElemType)){ LinkList p = L->next;while(p){ vi(p->data);p = p->next;} printf(“n”);} void ListPrint(LinkList L){ LinkList p = L->next;while(p){ printf(“%d ”, p->data);p = p->next;} printf(“n”);} void printInt(int data){ printf(“%d ”, data);}.软件测试 图一(主界面) 图二(插入学生信息) 图三(显示所有学生信息) 图四(查询个人信息) 图五(统计信息) 图六(修改信息) 图七(保存数据) 图八(删除信息) 心得体会 通过本程序的设计，我对数据结构作了以下总结：要解决一道程序题必须先要认真捕捉改程序中的有用信息，找出解决方法。先规划好，程序需要什么样的数据结构，什么函数，对程序有什么要求。然后从整体把握对程序设计进行分工，相应地把程序分成若干模块，具体实现各部分实行相应的功能。一个程序要顺利地进行设计，一是要对程序的功能有全面的了解，如果漏了某些部分，都会使得这个程序调试不出来或者是令该程序没有达到预想的效果。其次，在程序的编译中，必须注重程序设计过程中的细节，像单链表的程序，就要理解链表的概念，理解链表的数据特点，要清楚知道数据域和指针域的作用，否则，很容易会浪费大量时间在检测错误上面。要说到解题的思考方向，如果要总结成规律，我认为要灵活的进行方法的设计，通过不同的方法来实现不同的功能，如通过结点的插入来实现链表的创建。同时应该注意各种语句的选择，要先预想好需要什么样的语句来实现函数定义，尽量简单快捷地完成，避免出错。 要规范面向对象程序设计师的书写协管，在这次课程设计中，我们再次感受到，规范的程序书写，可以更好的进行后期的差错补漏。还应该注意各种面向对象语言语法的运用，例如继承的方法，都要严格按照语法来进行，否则很容易就会出现错误，甚至严重影响课程设计的进度。 源代码 #include “stdio.h” #include “stdlib.h” #include “string.h” int shoudsave=0;// struct student { char num[10];//学号 char name[20]; char sex[4]; int cgrade; int mgrade; int egrade; int totle; int ave; char neartime[10];//最近更新时间 }; typedef struct node { struct student data; struct node *next;}Node,*Link; int menu(){ char m[3]; int n; printf(“ ************************欢迎进入学生成绩管理系统******************************nn”); printf(“t欢迎使用本学生管理系统，本系统将为您提供历史学生信息查询，学生成绩信息管理功能。n”); printf(“********************************************************************************”); printf(“t1输入学生资料ttttt2删除学生资料n”); printf(“t3查询学生资料ttttt4修改学生资料n”); printf(“t5显示学生资料ttttt6统计学生成绩n”); printf(“t7保存学生资料n”); printf(“ttplease choose a operation(1-7):n”); printf(“*********************************************************************** *********n”); scanf(“%s”,m); n=atoi(m); return(n);} void printstart(){ printf(“---------n”);} void Wrong(){ printf(“n=====>提示:输入错误!n”);} void Nofind(){ printf(“n=====>提示:没有找到该学生!n”);} void printc()// 本函数用于输出中文 { printf(“学号t 姓名 性别 英语成绩 数据库成绩 数据结构成绩 总分平均分n”);} void printe(Node *p)//本函数用于输出英文 { printf(“%-12s%stt%st%dtt%dt%dt%dt %dn”,p->data.num,p->data.name,p->data.sex,p->data.egrade,p->data.mgrade,p->data.cgrade,p->data.totle,p->data.ave);} Node* Locate(Link l,char findmess[],char nameornum[])//该函数用于定位连表中符合要求的接点，并返回该指针 { Node *r; if(strcmp(nameornum,“num”)==0)//按学号查询 { r=l->next; while(r!=NULL) { if(strcmp(r->data.num,findmess)==0) return r; r=r->next; } } else if(strcmp(nameornum,“name”)==0)//按姓名查询 { r=l->next; while(r!=NULL) { if(strcmp(r->data.name,findmess)==0) return r; r=r->next; } } return 0;} void Add(Link l)//增加学生 { Node *p,*r,*s; char num[10]; r=l; s=l->next; while(r->next!=NULL) r=r->next;//将指针置于最末尾 while(1) { printf(“请你输入学号(以'0'返回上一级菜单:)”); scanf(“%s”,num); if(strcmp(num,“0”)==0) break; while(s) { if(strcmp(s->data.num,num)==0) { printf(“=====>提示:学号为'%s'的学生已经存在,若要修改请你选择'4 修改'!n”,num); printstart(); printc(); printe(s); printstart(); printf(“n”); return; } s=s->next; } p=(Node *)malloc(sizeof(Node)); strcpy(p->data.num,num); printf(“请你输入姓名:”); scanf(“%s”,p->data.name); getchar(); printf(“请你输入性别:”); scanf(“%s”,p->data.sex); getchar(); printf(“请你输入数据结构成绩:”); scanf(“%d”,&p->data.cgrade); getchar(); printf(“请你输入数据库成绩:”); scanf(“%d”,&p->data.mgrade); getchar(); printf(“请你输入英语成绩:”); scanf(“%d”,&p->data.egrade); getchar(); p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade; p->data.ave=p->data.totle / 3; //信息输入已经完成p->next=NULL; r->next=p; r=p; shoudsave=1; } } void Qur(Link l)//查询学生 { char findmess[20]; Node *p; if(!l->next) { printf(“n=====>提示:没有资料可以查询!n”); return; } printf(“请你输入要查找的学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { printf(“tttt查找结果n”); printstart(); printc(); printe(p); printstart(); } else Nofind();} void Del(Link l)//删除 { Node *p,*r; char findmess[20]; if(!l->next) { printf(“n=====>提示:没有资料可以删除!n”); return; } printf(“n=====>确定进行删除操作请按 1，按其他按键退出该操作nnnn”); if(menu()==1) { printf(“请你输入要删除的学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { r=l; while(r->next!=p) r=r->next; r->next=p->next; free(p); printf(“n=====>提示:该学生已经成功删除!n”); shoudsave=1; } else Nofind(); } else exit;} void Modify(Link l)//修改函数 { Node *p; char findmess[20]; if(!l->next) { printf(“n=====>提示:没有资料可以修改!n”); return; } printf(“请你输入要修改的学生学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { printf(“请你输入新学号(原来是%s):”,p->data.num); scanf(“%s”,p->data.num); printf(“请你输入新姓名(原来是%s):”,p->data.name); scanf(“%s”,p->data.name); getchar(); printf(“请你输入新性别(原来是%s):”,p->data.sex); scanf(“%s”,p->data.sex); printf(“请你输入新的数据结构成绩(原来是%d分):”,p->data.cgrade); scanf(“%d”,&p->data.cgrade); getchar(); printf(“请你输入新的数据库成绩(原来是%d分):”,p->data.mgrade); scanf(“%d”,&p->data.mgrade); getchar(); printf(“请你输入新的英语成绩(原来是%d分):”,p->data.egrade); scanf(“%d”,&p->data.egrade); p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade; p->data.ave=p->data.totle/3; printf(“n=====>提示:资料修改成功!n”); shoudsave=1; } else Nofind(); } void Disp(Link l)//显示函数 { int count=0; Node *p; p=l->next; if(!p) { printf(“n=====>提示:没有资料可以显示!n”); return; } printf(“tttt显示结果n”); printstart(); printc(); printf(“n”); while(p) { printe(p); p=p->next; } printstart(); printf(“n”);} void Tongji(Link l)//统计函数 { Node *pm,*pe,*pc,*pt,*pa;//用于指向分数最高的接点 Node *r=l->next; if(!r) { printf(“n=====>提示:没有资料可以统计!n”); return; } pm=pe=pc=pt=pa=r; while(r!=NULL) { if(r->data.cgrade>=pc->data.cgrade) pc=r; if(r->data.mgrade>=pm->data.mgrade) pm=r; if(r->data.egrade>=pe->data.egrade) pe=r; if(r->data.totle>=pt->data.totle) pt=r; if(r->data.ave>=pa->data.ave) pa=r; r=r->next; } printf(“------------------------------统计结果-n”); printf(“总分最高者:t%s %d分n”,pt->data.name,pt->data.totle); printf(“平均分最高者:t%s %d分n”,pa->data.name,pa->data.ave); printf(“英语最高者:t%s %d分n”,pe->data.name,pe->data.egrade); printf(“数据库最高者:t%s %d分n”,pm->data.name,pm->data.mgrade); printf(“数据结构最高者:t%s %d分n”,pc->data.name,pc->data.cgrade); printstart();} void Save(Link l)//保存函数 { FILE* fp; Node *p; int flag=1,count=0; fp=fopen(“c:student”,“wb”); if(fp==NULL) { printf(“n=====>提示:重新打开文件时发生错误!n”); exit(1); } p=l->next; while(p) { if(fwrite(p,sizeof(Node),1,fp)==1) { p=p->next; count++; } else { flag=0; break; } } if(flag) { printf(“n=====>提示:文件保存成功.(有%d条记录已经保存.)n”,count); shoudsave=0; } fclose(fp);} void main(){ Link l;//连表 FILE *fp;//文件指针 char ch; char jian; int count=0; Node *p,*r; l=(Node*)malloc(sizeof(Node)); l->next=NULL; r=l; fp=fopen(“C:student”,“rb”); if(fp==NULL) { fp=fopen(“C:student”,“wb”); exit(0); } printf(“n=====>提示:文件已经打开,正在导入记录......n”); while(!feof(fp)) { p=(Node*)malloc(sizeof(Node)); if(fread(p,sizeof(Node),1,fp))//将文件的内容放入接点中 { p->next=NULL; r->next=p; r=p;//将该接点挂入连中 count++; } } fclose(fp);//关闭文件 printf(“n=====>提示:记录导入完毕,共导入%d条记录.n”,count); for(;;) { switch(menu()) { case 1:Add(l);break;//增加学生 case 2:Del(l);break;//删除学生 case 3:Qur(l);break;//查询学生 case 4:Modify(l);break;//修改学生 case 5:Disp(l);break;//显示学生 case 6:Tongji(l);break;//统计学生 case 7:Save(l);break;//保存学生 default: Wrong(); getchar(); break; } } } 参考文献 《数据结构（C语言版）》----------------清华大学出版社 严蔚敏 吴伟民 编著 《C语言程序设计》------------------------中国铁道出版社 丁峻岭 余坚 编著第二篇：C语言实验
第三篇：C语言数据结构与指针
第四篇：数据结构经典题目及c语言代码总结
第五篇：数据结构实验报告(报告+C语言源代码)
点击咨询 