实验报告
实 验 名 称：数据结构 实 验 地 点： 实 验 日 期： 指 导 教 师： 学 生 班 级： 学 生 姓 名： 学 生 学 号： 提 交 日 期：
2015年12月信息网络安全学院
目 录
实验一 学生成绩分析程序............................................4
1.1 上机实验的问题和要求（需求分析）： .....................................4 1.2 程序设计的基本思想，原理和算法描述： ..................................4 1.3 调试和运行程序过程中产生的问题及采取的措施：...........................4 1.4 运行输出结果：.........................................................4 1.5 源程序及注释： ........................................................5
实验二 线性表的基本操作............................................8
2.1 上机实验的问题和要求（需求分析）：......................................8 2.2 程序设计的基本思想，原理和算法描述： ..................................8 2.3 调试和运行程序过程中产生的问题及采取的措施：...........................8 2.4 运行输出结果：.........................................................8 2.5 源程序及注释： ........................................................8
实验三 链表的基本操作..............................................11
3.1 上机实验的问题和要求（需求分析）：.....................................11 3.2 程序设计的基本思想，原理和算法描述： .................................11 3.3 调试和运行程序过程中产生的问题及采取的措施：..........................11 3.4 运行输出结果：........................................................11 3.5 源程序及注释： .......................................................11
实验四 单链表综合实验 .........................................14
4.1 上机实验的问题和要求（需求分析）：....................................14 4.2 程序设计的基本思想，原理和算法描述： ................................14 4.3 调试和运行程序过程中产生的问题及采取的措施：.........................14 4.4 运行输出结果：.......................................................14
1
4.5 源程序及注释： .....................................................14
实验五 串.........................................................19
5.1 上机实验的问题和要求（需求分析）：...................................19 5.2 程序设计的基本思想，原理和算法描述： ...............................19 5.3 调试和运行程序过程中产生的问题及采取的措施：........................19 5.4 运行输出结果：......................................................19 5.5 源程序及注释： .....................................................21
实验六 循环队列的实现与运算.................................22
6.1 上机实验的问题和要求（需求分析）：...................................22 6.2 程序设计的基本思想，原理和算法描述： ...............................22 6.3 调试和运行程序过程中产生的问题及采取的措施：........................22 6.4 运行输出结果：......................................................22 6.5 源程序及注释： .....................................................23
实验七 栈子系统..................................................26
7.1 上机实验的问题和要求（需求分析）：...................................26 7.2 程序设计的基本思想，原理和算法描述： ...............................26 7.3 调试和运行程序过程中产生的问题及采取的措施：........................26 7.4 运行输出结果：......................................................26 7.5 源程序及注释： .....................................................28
实验八 树...........................................................36
8.1 上机实验的问题和要求（需求分析）：..................................36 8.2 程序设计的基本思想，原理和算法描述： ..............................39 8.3 调试和运行程序过程中产生的问题及采取的措施：.......................39 8.4 运行输出结果：.....................................................39
2
8.5 源程序及注释： .....................................................41
实验九 建立哈夫曼树与哈夫曼树与码...........................50
9.1 上机实验的问题和要求（需求分析）：..................................50 9.2 程序设计的基本思想，原理和算法描述： ..............................50 9.3 调试和运行程序过程中产生的问题及采取的措施：.......................50 9.4 运行输出结果：.....................................................50 9.5 源程序及注释： ....................................................50
实验十 图…………………………….............................53
10.1 上机实验的问题和要求（需求分析）：.................................53 10.2 程序设计的基本思想，原理和算法描述： .............................53 10.3 调试和运行程序过程中产生的问题及采取的措施：......................53 10.4 运行输出结果：....................................................53 10.5 源程序及注释： ...................................................53
3
实验一 学生成绩分析程序
一、 上机实验的问题和要求（需求分析）：
【题目】设一个班有10个学生，每个学生有学号，以及数学、物理、英语、语文、体育 5 门课的成绩信息。分别编写3个函数以实现以下3个要求： （1） 求数学的平均成绩。
（2） 对于有两门以上课程不及格的学生，输出他们的学号、各门课成绩及平均成绩。 （3） 输出成绩优良的学生（平均成绩在85分以上或全部成绩都在80分以上）的学号、
各门课成绩和平均成绩。
二、 程序设计的基本思想，原理和算法描述：
【算法描述】（1）用数组id[3],name[10],score[5]来记录是个学生的各门课程的成绩.将数学科目的成绩相加再求出平均成绩。
（2）取一个未知数A来求学生的不及格数，a>=2时输出学生的名字学号和成绩。 （3）求出所有的成绩的平均分并输出各门成绩和平均成绩。
三、调试和运行程序过程中产生的问题及采取的措施：
基本上是输入时的细节如大括号的位置等。
四、运行输出结果
4
五、源程序及注释：
输入学生的学号姓名和成绩： #include\"stdio.h\" struct STUDENT {
char id[3]; char name[10]; int score[5]; double ave; }stu[10]; void main() {
int num=10,i,j,all=0;; for(i=0;i scanf(\"%s\ j=0; printf(\"\语文课的成绩\"); scanf(\"%d\ j++; printf(\"\数学课的成绩\"); scanf(\"%d\ j++; printf(\"\物理课的成绩\"); scanf(\"%d\ j++; printf(\"\英语课的成绩\"); scanf(\"%d\ j++; printf(\"\体育课的成绩\"); scanf(\"%d\ } pj (); bjg(); yx(); } 输出数学平均成绩： void pj(stu[10]) { 5 int a,b,i; for(i=0;i<10;i++); { a=a+stu[i].score[2]; } b=a/10; printf(\"\the everage score is:%d\} 求出不及格人数： void bjg() { int i,j=0,c=0; for(i=0;i<10;i++); { for(j=0;j<5;i++); { if(stu[i].score[j]<60) {c=c++;} } if(\"c>=2\"); printf(\"两门课以上不及格的同学：\"); printf(\"%d\%d\%d\%d\\ } } 输出优秀学生： void yx() { int i,j=0,c=0; for(i=0;i<10;i++); { for(j=0;j<5;i++); { if(stu[i].score[j]>=80) {c=c++;} } if(\"c==5\"); printf(\"优秀学生为：\"); printf(\"%d\%d\%d\%d\\ } } 6 实验二 线性表的基本操作 一、 上机实验的问题和要求（需求分析）： 【题目】线性表的插入，删除。 二、 程序设计的基本思想，原理和算法描述： 【算法描述】当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。 三、调试和运行程序过程中产生的问题及采取的措施： 四、运行输出结果： 五、源程序及注释： #include typedef struct linknode { char data; struct linknode *next; }linnode; linnode *head; int n; 创建线性表： void Createlist() { n=0; linknode *p,*s; char x; int z=1; head=new linknode; p=head; printf(\"\\n\\ 请逐个输入结点，以“X”为结素标记！\\n\"); while(z) { printf(\"\\输入一个字符数据，并按回车：\"); scanf(\"%c\ getchar(); 7 if(x!='x') { s=new linknode; n++; s->data=x; p->next=s; s->next=NULL; p=s; } else z=0; } } 线性表的插入： void InsList(int i,char x) { linknode *s,*p; p=head; int j=0; while(p!=NULL&&j p=p->next; } if(p!=NULL) { s=new linknode; s->data=x; s->next=p->next; p->next=s; n++; } else printf(\"\\n\\线性表为空或插入位置超出！\\n\"); } 线性表的删除： void DelList(char x) { linknode *p,*q; if(head->next==NULL) { printf(\"\\n\\线性表下溢！\"); return; } if(head->next==NULL) 8 { printf(\"\\n\\线性表已经为空！\"); return; } q=head; p=head->next; while(p!=NULL&&p->data!=x) { q=p; p=p->next; } if(p!=NULL) { q->next=p->next; delete p; n--; printf(\"\\n\\结点已经被删除！\"); scanf(\"\\n\抱歉！没有找到您要删除的节点.\"); } } 9 实验三 链表的基本操作 一、 上机实验的问题和要求（需求分析）： 【题目】建立线性链表，链表的插入、删除，查找。 二、 程序设计的基本思想，原理和算法描述： 【算法描述】线性链表不需要用地址连续的存储空间来实现，链式存储的线性表对于插入、删除操作不再需要移动数据元素。 三、调试和运行程序过程中产生的问题及采取的措施： 四、运行输出结果： 五、源程序及注释： 建立线性链表： #include typedef struct linknode { char data; struct linknode *next; }linnode; linnode *head; int n; void CreateList() { n=0; linnode *p,*s; char x; int z=1; head=new linnode; p=head; printf(\"\\n\\建立一个线性表\"); printf(\"\\n\\说明：请逐个输入字符，结素标记为\"x\"!\\n\"); while(z) { printf(\"\\ put in: \"); scanf(\"%c\ getchar(); if(x!='x') { 10 s=new node; n++; s->data=x; s->next=s; } else z=0; } } 链表的插入： void InsList(int i,char x) { linnode *s,*p; p=head; int j=0; while(p!=NULL&&j p=p->next; } if(p!=NULL) { s=new linnode; s->data=x; s->next=p->next; p->next=s; n++; } else printf(\"\\n\\线性表为空或插入位置出错！\\n\"); } 链表的删除： void DelList(char x) { node *p,*q; if(head==NULL) { printf(\"\\链表下溢!\\n\"); return; } if(head->next==NULL) { printf(\"\\线性表已经为空！\"); return; } 11 q=head; p=head->next; while(p!=NULL&&p->data!=x) { q=p; p=p->next; } if(p!=NULL) { q->next=p->next; delete p; n--; printf(\"\\已经被删除！\\n\"); } else printf(\"\\未找到！\\n\"); } 链表的查找： 12 实验四 单链表综合实验 一、 上机实验的问题和要求（需求分析）： 【题目】 （1）、建立自己的有关单链表的头文件 （2）、单链表基本操作的实现 [问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。 二、 程序设计的基本思想，原理和算法描述： 【算法描述】链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。 三、调试和运行程序过程中产生的问题及采取的措施： 四、运行输出结果： 五、源程序及注释： # include 建立数组： typedef struct node { DataType data; struct node *next; }ListNode; 产生头结点： void Init_List(ListNode **L) { (*L)=(ListNode *)malloc(sizeof(ListNode)); (*L)->next=NULL; 13 } 测量单链表长度： int List_Length(ListNode *L ) { int n=0; ListNode *p=L->next; while(p!=NULL) { n++; p=p->next; } return n; } 单链表的查找第i个节点： ListNode* GetNode(ListNode *L,int i) { int j; ListNode *p; p=L;j=0; /*从头结点开始扫描*/ while(p->next&&j!=i) /*顺指针向后扫描,直到p->next为NULL或i=j为止*/ { p=p->next; j++; } if(i==j) return p; /*找到了第i个结点*/ else return NULL; /*当i<0或i>j时,找不到第i个结点*/ } 单链表在第i个节点插入： void InsertList(ListNode *L,DataType x,int i) { ListNode *p,*s; p=GetNode(L,i-1); /*寻找第i-1个结点*/ if (p==NULL) /*i<1或i>n+1时插入位置i有错*/ { printf(\"error!\"); return ; } s=(ListNode *)malloc(sizeof(ListNode)); /*建立一个新的节点*/ s->data=x;s->next=p->next;p->next=s; /*将节点插入单链表*/ 14 } 删除单链表第i个节点： void DeleteList(ListNode *L ,int i) { ListNode *p,*r; p=GetNode(L,i-1); /*找到第i-1个结点*/ if (p==NULL||p->next==NULL) { printf(\"error!\"); return ; } r=p->next; /*使r指向被删除的结点a*/ p->next=r->next; /*将ai从链上删除*/ free(r); } 使用头插法建立带头结点链表算法: ListNode * CreatListF(void) { char ch; ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/ ListNode *s; /*工作指针*/ head->next=NULL; ch=getchar(); /*读入第1个字符*/ while(ch!='\\n') { s=(ListNode *)malloc(sizeof(ListNode)); /*生成新结点*/ s->data=ch; /*将读入的数据放入新结点的数据域中*/ s->next=head->next; head->next=s; ch=getchar(); /*读入下一字符*/ } return head; } 使用尾插法建立带头结点链表算法: ListNode * CreatListR1(void) { char ch; ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/ ListNode *s,*r; /*工作指针*/ r=head; /*尾指针初值也指向头结点*/ while((ch=getchar())!='\\n') 15 { s=(ListNode *)malloc(sizeof(ListNode)); s->data=ch; r->next=s; r=s; } r->next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/ return head; } /*复制链表A中的内容到表B中*/ void copy(ListNode *a, ListNode *b) { ListNode *pa=a->next; ListNode *u; ListNode *rb=b; while(pa!=NULL) { u=( ListNode *)malloc(sizeof(ListNode)); u->data=pa->data; rb->next=u; rb=u; pa=pa->next; } rb->next=NULL; } /*输出带头结点的单链表*/ void DisplaySL(ListNode *la, char *comment) { ListNode *p ; p=la->next ; if(p) printf(\"\\n%s\\n\" , comment) ; while(p) { printf(\"%4c\ p=p->next; } printf(\"\\n\") ; } /*主函数*/ main( ) { 16 ListNode *la ,*lb,*lc, *p ; int n,x,i; printf(\"\\n用头插法建立链表la，请输入节点内容:\"); la=CreatListF(); DisplaySL(la,\"新生成链la节点内容:\"); printf(\"\\n链表la的长度: %2d\printf(\"\\n请输入要插入的元素: \"); scanf(\"%c\ printf(\"\\n请输入要插入的位置：\"); scanf(\"%d\InsertList(la,x,i); DisplaySL(la,\"插入后链la节点内容\"); printf(\"\\n请输入要删除元素的位置：\"); scanf(\"%d\DeleteList(la,i); DisplaySL(la, \"删除后链la节点内容\"); printf(\"\\n用尾插法建立链表lb，请输入节点内容:\"); fflush(stdin); lb=CreatListR1(); DisplaySL(lb,\"新生成链lb节点内容:\"); Init_List(&lc); copy(la,lc); DisplaySL(lc,\"复制生成的链lc节点内容:\"); } 17 实验五 串 一、 上机实验的问题和要求（需求分析）： 串的基本运算：创建一个串；串的复制；求串的长度；求子串；输入一个自串；删 除一个子串；连接两个串；输出串。 【题目】1、下列是一个置换函数，采用顺序存储方式存储串，将串s1中的第I个字符开始的j个字符（包括第I个字符）构成的子串用s2串进行替换，函数名为replace(s1,I,j,s2)。例如：replace（“abcd”,1,3,’xyz”）返回”xyzd”。（填空） 二、程序设计的基本思想，原理和算法描述： 先提取s1中位置I之前的所有字符构成的子串str1,再提取位置I+j-1及之后的所有字符构成的子串 str2，最后将str1,s2,str2连接起来便构成了结果串 三、 调试和运行程序过程中产生的问题及采取的措施： 四、 运行输出结果： 【题目】1、下列是一个置换函数，采用顺序存储方式存储串，将串s1中的第I个字 符开始的j个字符（包括第I个字符）构成的子串用s2串进行替换，函数名为 replace(s1,I,j,s2)。例如：replace（“abcd”,1,3,’xyz”）返回”xyzd”。（填空） # include char ch [MaxLen]； int len； } strtype； void create (strtype *s, char str[]) { strcpy (s->ch, str)； s->len=strlen (str)； 18 } void disp(strtype *s) { if (s->len= =0) printf( “空串\\n”）； else printf（“%c\\n”,s->ch)； } strtype replace(strtype *sl, int I, int j, strtype *s2) { strtype s； int n, k； if (I+j-1<=s1->len) { for (n=0；n for (n=s.len, k=I+j-1；k s.ch[0]=’\\0’； s.len=0； 19 } return(s)； } void main() { strtype s,s1,s2； int pos, n； char str[maxlen]； printf（“字符串：”）； gets(str)； create (&s1, str)； printf( “位置：”)； scanf（“%d”,& create (strtype *s, char str[]) )；printf( “长度：”)； scanf（“%d”,& disp(strtype *s) )； printf（“子串：”）； gets( *s2 )； create(&s2, str)； s=replace(&s1, pos, n, &s2)； disp(&s)； } 输出： 字符串：12345678 位置： 3 长度： 4 子串：abcdefgh 五、 源程序及注释： 20 实验六、循环队列的实现与运算 一、 上机实验的问题和要求（需求分析）： 1．掌握队列“先进先出”的特点； 2.复习队列的入队、出队、插入、删除等基本运算； 3.掌握循环队列的特点，以及循环队列的应用。 二、 程序设计的基本思想，原理和算法描述 1.在顺序存储结构上实现输出受限制的双端循环队列的入队和出队（只允许队头输出）算法； 2.设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。 3.循环队列数据类型： #define MAXLEN 10 Typedef struct { Int data[MAXLEN]; Int front,rear; }csequeue; 4.入队作业处理的预计执行时间可以用随机数函数rand()产生，也可以从键盘输入。 三、 调试和运行程序过程中产生的问题及采取的措施： 四、 运行输出结果： 21 五、 源程序及注释： #include { int data[MAXLEN]; // 定义数据的类型 int front,rear; // 定义队头、队尾指针 }csequeue; csequeue q; void IniQueue() // 初始化队列 { q.front=q.rear=MAXLEN-1; } void InQueue() // 入队函数 { int x ; printf(\"\\n\\ 输入一个入队的整数数据：\"); scanf(\"%d\ if (q.front==(q.rear+1) % MAXLEN ) { printf(\"\\n\\ 队满，不能入队! \\n\"); return; } q.rear=(q.rear+1) % MAXLEN; 22 q.data[q.rear]=x; printf(\"\\n\\ 入队成功! \\n\"); } void Outsequeue() // 出队函数 { if (q.front==q.rear) { printf (\"\\n\\ 此队列为空! \"); return ;} // 队空不能出队 else { q.front=(q.front+1) % MAXLEN; printf(\"\\n\\ 出队元素为：%d\\n\// 输出队头元素 return; } } void ShowQueue() // 显示函数 { int k=q.front; if (k==q.rear) { printf(\"\\n\\ 此队列为空! \\n\"); return;} printf(\"\\n\\ 此队列元素为：\"); do { k=(k+1)%MAXLEN; printf(\"%4d\ } while(k!=q.rear); printf(\"\\n\"); } int length() { int k; k=(q.rear-q.front+MAXLEN)% MAXLEN; return k; } void main() // 主函数 { int i=1; int choice; IniQueue(); while (i) { printf(\"\\n\\ 循 环 队 列\\n\"); printf(\"\\n\\***********************************************\"); printf(\"\\n\\* 1----------进 队 *\"); printf(\"\\n\\* 2----------出 队 *\"); printf(\"\\n\\* 3----------显 示 *\"); printf(\"\\n\\* 4----------求 队 列 长 度 *\"); printf(\"\\n\\* 0----------返 回 *\"); printf(\"\\n\\***********************************************\"); printf(\"\\n\\n\\ 请选择菜单号: \"); scanf(\"%d\ 23 switch(choice) { case 1: InQueue(); break; case 2: Outsequeue(); break; case 3: ShowQueue(); break; case 4: printf(\"\\n\\ 队列长度为: %d \\n\ case 0: i=0; break; } } } 24 实验七、栈子系统 一、 上机实验的问题和要求（需求分析）： 【题目】 （1）设计一个字符型的链栈。 （2）编写进栈、出栈、显示栈中全部元素的程序。 （3）编写一个把十进制整数转换成二进制数的应用程序。 （4）编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序。（5）设计一个选择式菜单，以菜单方式选择上诉操作。 二、 程序设计的基本思想，原理和算法描述： 利用栈“后进先出”的特点做成一个存储数据的系统。 三、 调试和运行程序过程中产生的问题及采取的措施： 四、 运行输出结果： 25 26 五、 源程序及注释： #include typedef struct stacknode { int data; struct stacknode *next; }stacknode; 27 typedef struct { stacknode *top;/*指向栈顶的指针*/ }linkstack; /*进栈*/ void Push(linkstack *s,int x) { stacknode *p=new stacknode;/*建立一个新的结点*/ p->data=x; p->next=s->top; s->top=p; } /*出栈*/ int Pop(linkstack *s) { int x; stacknode *p=s->top; x=p->data; s->top=p->next; delete p; return x; } /*显示栈的内容*/ void ShowStack(linkstack *s) { stacknode *p=s->top; if(p==NULL) printf(\"\\n\\栈为空.\"); else { printf(\"\\n\\栈元素为：\"); while(p!=NULL) { printf(\"%6d\ p=p->next; } printf(\"\\n\"); } } /*十进制转二进制*/ void ConversionB(int n) { linkstack s; int x; 28 s.top=NULL;/*置栈空*/ do { x=n%2;/*取余数*/ n=n/2;/*取新的商*/ stacknode *p=new stacknode;/*申请新的结点*/ p->next=s.top; s.top=p; s.top->data=x; }while(n); printf(\"\\n\\转换后的二进制数值为：\"); while(s.top) { printf(\"%d\ stacknode *p=s.top; s.top=s.top->next; delete p; } printf(\"\\n\"); getchar(); } //十进制转十六进制（1） void ConversionX1(int n) { linkstack s; int x; s.top=NULL; do { x=n%16; n=n/16; stacknode *p=new stacknode; p->next=s.top; s.top=p; s.top->data=x; }while(n); printf(\"\\n\\转换后的十六进制数值为：\"); while(s.top) { if(s.top->data==10) printf(\"A\"); else if(s.top->data==11) printf(\"B\"); 29 else if(s.top->data==12) printf(\"C\"); else if(s.top->data==13) printf(\"D\"); else if(s.top->data==14) printf(\"E\"); else if(s.top->data==15) printf(\"F\"); else printf(\"%d\ stacknode *p=s.top; s.top=s.top->next; delete p; } printf(\"\\n\"); getchar(); } //十进制转十六进制（2） void ConversionX2(int n) { linkstack s; int x; s.top=NULL; do { x=n%16; n=n/16; stacknode *p=new stacknode; p->next=s.top; s.top=p; s.top->data=x; }while(n); printf(\"\\n\\转换后的十六进制数值为：\"); while(s.top) { if(s.top->data<10) printf(\"%d\ else printf(\"%c\ stacknode *p=s.top; s.top=s.top->next; delete p; } printf(\"\\n\"); getchar(); 30 } //求逆波兰式 void Suffix() { char str[STACKMAX]; char stack[STACKMAX]; char exp[STACKMAX]; char ch; int sum,i,j,t,top=0; printf(\"\\n\\输入算术表达式(运算符只能包含+,-,*,/),以#结束。\\n\"); printf(\"\\n\\算术表达式：\"); i=0; do{ i++;scanf(\"%c\ }while(str[i]!='#' && i!=STACKMAX); sum=i; t=1; i=1; ch=str[i]; i++; while(ch!='#') { switch(ch) { case'(': top++; stack[top]=ch; break; case')': while(stack[top]!='(') { exp[t++]=stack[top--]; exp[t++]=','; } top--; break; case'+': case'-': while(top!=0 && stack[top]!='(') { exp[t++]=stack[top--]; exp[t++]=','; } 31 case'*': case'/': while(stack[top]=='*' || stack[top]=='/') { exp[t++]=stack[top--]; exp[t++]=','; } stack[++top]=ch; break; case' ': break; default: while(ch>='0' && ch<='z') { exp[t++]=ch; ch=str[i++]; } i--; exp[t++]=','; } ch=str[i++]; } while(top!=0) exp[t++]=stack[top--]; printf(\"\\n\\原来表达式：\"); for(j=1;j /*主函数*/ void main() { linkstack *s=new linkstack; int i=1,j=1,choice,val,n; char a; s->top=NULL; while(i) { printf(\"\\n\"); printf(\"\\n\\ 栈子系统 \"); 32 printf(\"\\n\\╔═════════════════╗\"); printf(\"\\n\\║ 1------进 栈 ║\"); printf(\"\\n\\║ 2------出 栈 ║\"); printf(\"\\n\\║ 3------显 示 ║\"); printf(\"\\n\\║ 4------十进制转二进制 ║\"); printf(\"\\n\\║ 5------十进制转十六进制1 ║\"); printf(\"\\n\\║ 6------十进制转十六进制2 ║\"); printf(\"\\n\\║ 7------逆波兰式 ║\"); printf(\"\\n\\║ 0------返 回 ║\"); printf(\"\\n\\╠═════════════════╝\"); printf(\"\\n\\╚请选择菜单号（0--7）：\"); choice=getchar(); getchar(); switch (choice) { case '1': while(j) { printf(\"\\n\\键入一个整数（'0'表示结束）并按回车：\"); scanf(\"%d\ if(val!=0) Push(s,val); else j=0; }; break; case '2': if(s->top!=NULL) printf(\"\\n\\出栈元素为：%d\\n\ break; case '3': ShowStack(s); break; case '4': printf(\"\\n\\请输入一个十进制正整数：\"); scanf(\"%d\ ConversionB(n); break; case '5': printf(\"\\n\\请输入一个十进制正整数：\"); scanf(\"%d\ ConversionX1(n); break; case '6': 33 printf(\"\\n\\请输入一个十进制正整数：\"); scanf(\"%d\ ConversionX2(n); break; case '7': Suffix(); break; default: i=0; } if(choice=='1'||choice=='2'||choice=='3'||choice=='4'||choice=='5') { printf(\"\\n\\按回车键返回主菜单,按任意键后回车退出.\\n\"); a=getchar(); if(a!='\\xA') i=0; } } } 34 实验八 树 一、 上机实验的问题和要求（需求分析）： 1.掌握二叉树，二叉树排序数的概念及存储方法。 2.掌握二叉树的遍历算法。 3.熟练掌握编写实现树的各种运算的算法。 【题目】1、建立一棵二叉树并中序遍历。（填空） #include “ stdio.h” #include “malloc.h” struct node{ char data； struct node *lchild , *rchild； } bnode； typedef struct node * blink； blink add(blink bt,char ch) { if(bt==NULL) { bt=nalloc(sizeof(bnode))； bt->data = ch； bt->lchild = bt->rchild =NULL； } else if ( ch < bt->data) bt->lchild = add(bt->lchid ,ch)； else bt->rchild = add(bt->rchild,ch)； return bt； } 35 void inorder(blink bt) { if(bt) { inorder(bt-> bt->lchild )； printf（“%c”, bt->data ）； inorder(bt-> bt->rchild )； } } main() { blink root = null； int i,n； char x； scanf（“%c”,&n)； for(i=1；i<=n；i++) { x=getchar()； root=add(root,x)； } inorder(root)； printf（“\\n”）； } 【题目】2、求二叉树的结点数和叶子数(填空) #include “stdio.h” #include “alloc.h” struct node{ char data； struct node *lchild , *rchild； } bnode； 36 typedef struct node *blink； int n=0,no=0； /*先序遍历*/ void preorder(blink bt) { if(bt) { n++； if(bt->lchild ==NULL&&bt->rchild==NULL) no++； preorder(bt-> lchild ；) preorder(bt-> rchild ；) } } blink creat() { blink bt； char ch； ch = getchar()； if (ch!=’#’) { bt= nalloc(sizeof(bnode))； bt->data= ch； bt->lchild = ch->lchild ； bt->rchild= ch->rchild ； } else bt=NULL； return bt； } 37 main() { blink root； root = creat()； preorder(root)； printf（“number of node： %d number of leaf： %d \\n” , n , no)； } 【题目】3、编写程序，实现按层次遍历二叉树。 二、 程序设计的基本思想，原理和算法描述： 树的基本运算：创建树；输出树；遍历树；求二叉树的深度；创建二叉排序树；二 叉排序树的查找；二叉排序树的删除；创造哈夫曼树；输出哈夫曼树； 三、调试和运行程序过程中产生的问题及采取的措施： 四、运行输出结果： 38 39 五、源程序及注释： 【题目】3、编写程序，实现按层次遍历二叉树。 #include char data; BT* lchild; BT* rchild; 40 }BT; BT*CreateTree(); void ShowTree(BT *T); void Preorder(BT *T); void Postorder(BT *T); void Levelorder(BT *T); void Inorder(BT *T); void Leafnum(BT *T); void Nodenum(BT *T); int TreeDepth(BT *t); int count=0; void main() { BT *T=NULL; char ch1,ch2,a; ch1='y'; while(ch1=='y'||ch1=='Y') { printf(\"\\n\"); printf(\"\\n\\ 二叉树子系统\"); printf(\"\\n\\*************************************\"); printf(\"\\n\\* 1------建 二 叉 树 *\"); printf(\"\\n\\* 2------凹 入 显 示 *\"); printf(\"\\n\\* 3------先 序 遍 历 *\"); printf(\"\\n\\* 4------中 序 遍 历 *\"); printf(\"\\n\\* 5------后 序 遍 历 *\"); printf(\"\\n\\* 6------层 次 遍 历 *\"); printf(\"\\n\\* 7------求 叶 子 树 *\"); printf(\"\\n\\* 8------求 结 点 数 *\"); 41 printf(\"\\n\\* 9------求 树 深 度 *\"); printf(\"\\n\\* 0------返 回 *\"); printf(\"\\n\\*************************************\"); printf(\"\\n\\请选择菜单号（0--9）：\"); scanf(\"%c\getchar(); printf(\"\\n\"); switch(ch2) { case'1': printf(\"\\n\\请按先序序列输入二叉树的结点：\\n\"); printf(\"\\n\\说明：输入结点（'0'表示后继结点为空）后按回车。 \\n\"); printf(\"\\n\\请输入跟结点：\"); T=CreateTree(); printf(\"\\n\\二叉树成功建立！\\n\"); break; case'2': ShowTree(T); break; case'3': printf(\"\\n\\该二叉树的先序遍历序列为：\"); Preorder(T); break; case'4': printf(\"\\n\\该二叉树的中序遍历序列为：\"); Inorder(T); break; case'5': printf(\"\\n\\该二叉树的后序遍历序列为：\"); 42 Postorder(T); break; case'6': printf(\"\\n\\该二叉树的层次遍历序列为：\"); Levelorder(T); break; case'7': count=0;Leafnum(T); printf(\"\\n\\该二叉树有%d个叶子。\\n\ break; case'8': count=0;Nodenum(T); printf(\"\\n\\该二叉树共有%d个结点。\\n\ break; case'9': printf(\"\\n\\该树的深度是：%d\ break; case'0': ch1='n';break; default: printf(\"\\n\\***请注意：输入有误！***\"); } if (ch2!='0') { printf(\"\\n\\n\\按回车键返回主菜单，按任意键退出！\\n\"); a=getchar(); if(a!='\\xA') { getchar();ch1='n'; } 43 } } } BT *CreateTree() { BT *t; char x; scanf(\"%c\ getchar(); if(x=='0') t=NULL; else { t=new BT; t->data=x; printf(\"\\n\\请输入%c结点的左子结点：\ t->lchild=CreateTree(); printf(\"\\n\\请输入%c结点的右子节点：\ t->rchild=CreateTree(); } return t; } void Preorder(BT *T) { if(T) { printf(\"%3c\ Preorder(T->lchild); 44 Preorder(T->rchild); } } void Inorder(BT *T) { if(T) { Inorder(T->lchild); printf(\"%3c\ Inorder(T->rchild); } } void Postorder(BT *T) { if(T) { Postorder(T->lchild); Postorder(T->rchild); printf(\"%3c\ } } void Levelorder(BT *T) { int i,j; BT *q[100],*p; p=T; if(p!=NULL) 45 { i=1;q[i]=p;j=2; } while(i!=j) { p=q[i];printf(\"%3c\ if(p->lchild!=NULL) { q[j]=p->lchild;j++; } if(p->rchild!=NULL) { q[j]=p->rchild;j++; } i++; } } void Leafnum(BT *T) { if(T) { if(T->lchild==NULL&&T->rchild==NULL) count++; Leafnum(T->lchild); Leafnum(T->rchild); } } void Nodenum(BT *T) 46 { if(T) { count++; Nodenum(T->lchild); Nodenum(T->rchild); } } int TreeDepth(BT *T) { int ldep,rdep; if(T==NULL) return 0; else { ldep=TreeDepth(T->lchild); rdep=TreeDepth(T->rchild); if(ldep>rdep) return ldep+1; else return rdep+1; } } void ShowTree(BT *T) { BT *stack[TREEMAX],*p; int level[TREEMAX] [2],top,n,i,width=4; if(T!=NULL) 47 printf(\"\\n\\凹入表示法：\\n\\\"); top=1; stack[top]=T; level[top][0]=width; while(top>0) { p=stack[top]; n=level[top][0]; for(i=1;i<=n;i++) printf(\" \"); printf(\"%c\ for(i=n+1;i<30;i+=2) printf(\"■\"); printf(\"\\n\\\"); top--; if(p->rchild!=NULL) { top++; stack[top]=p->rchild; level[top][0]=n+width; level[top][1]=2; } if(p->lchild!=NULL) { top++; stack[top]=p->lchild; level[top][0]=n+width; level[top][1]=1; } 48 { } } } 实验九 建立哈夫曼树与哈夫曼树编码 一、上机实验的问题和要求（需求分析）： 哈夫曼树的建立，够造，编码。 二、程序设计的基本思想，原理和算法描述： 利用哈夫曼树构造一个模型。 三、调试和运行程序过程中产生的问题及采取的措施： 四、运行输出结果： 五、源程序及注释： /* sy7_4.c */ #define MAXVALUE 32767 /*定义最大权值*/ #define MAXLEAF 8 /*定义哈夫曼树中叶子结点的个数*/ #define MAXNODE MAXLEAF*2-1 #include 49 }HTNode; /*定义二叉树的存储结点*/ typedef struct Code { int bits[MAXLEAF]; int start; char ch; }HCodeType; /*定义编码结构*/ HTNode Ht[MAXNODE]; HCodeType HuffCode[MAXLEAF]; void Huffman_tree() /*建立哈夫曼树*/ { int i,j,m1,m2,p1,p2; for(i=0;i } 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; } }/*Huffman_tree*/ void Huffman_code() /*哈夫曼树编码*/ { HCodeType cd; int c,p,i,j; for(i=0;i p=Ht[i].parent; while(p!=-1) { cd.start--; if(Ht[p].lchild==c) cd.bits[cd.start]=0; else cd.bits[cd.start]=1; c=p; p=Ht[p].parent; } HuffCode[i]=cd; } for(i=0;i } } void main() { Huffman_tree(); /*建立哈夫曼树*/ Huffman_code(); /*哈夫曼树编码*/ } 实验十 图 一、上机实验的问题和要求（需求分析）： 建立一个图。 二、程序设计的基本思想，原理和算法描述： 用图的邻接矩阵表示法，完成图的建立。 三、调试和运行程序过程中产生的问题及采取的措施：四、运行输出结果： 五、源程序及注释： 1、图的邻接矩阵表示法算法如下，通过如下算法，完成图的建立 #include #include #include MGRAPH create_mgraph() {/*建立图的邻接矩阵*/ int i,j,k; MGRAPH mg; mg.kind=2; printf(\"\\n\\n输入顶点数和边数(用逗号隔开) : \"); scanf(\"%d,%d\ mg.vexnum=i; mg.arcnum=j; printf(\"\\n\\n\"); 52 for(i=0;i while(i<1||i>mg.vexnum||j<1||j>mg.vexnum) { printf(\"输入错，重新输入: \"); scanf(\"%d,%d\ mg.arcs[i-1][j-1]=1; mg.arcs[j-1][i-1]=1;} return mg; } main（）{ } 2、图的邻接链表表示法算法如下，通过如下算法，完成图的建立 #include #include #include ADJGRAPH creat_adjgraph(){ EDGENODE *p; int i, s, d; ADJGRAPH adjg; adjg.kind = 2; printf(\"\\n\\n输入顶点数和边数(用逗号隔开) : \"); scanf(\"%d,%d\ adjg.vexnum = s; /*存放顶点数在adjg.vexnum中 */ adjg.arcnum = d; /*存放边点数在adjg.arcnum中*/ printf(\"\\n\\n\"); 53 for(i = 0; i < adjg.vexnum; i++) {printf(\"输入顶点 %d 的值 : \ scanf(\"%d\ /*输入顶点的值*/ fflush(stdin); adjg.adjlist[i].link = NULL;} printf(\"\\n\\n\"); for(i = 0; i < adjg.arcnum; i++) {printf(\"输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): \ scanf(\"%d,%d\ /*输入边的起始顶点和终止顶点*/ fflush(stdin); while(s < 1 || s > adjg.vexnum || d < 1 || d > adjg.vexnum) { printf(\"输入错，重新输入: \"); scanf(\"%d,%d\ } s --; d --; p = malloc(sizeof(EDGENODE)); /*建立一个和边相关的结点*/ p->adjvex = d; p->next = adjg.adjlist[s].link; /*挂到对应的单链表上*/ adjg.adjlist[s].link = p; p = malloc(sizeof(EDGENODE)); /*建立另一个和边相关的结点*/ p->adjvex = s; p->next = adjg.adjlist[d].link; /*挂到对应的单链表上*/ adjg.adjlist[d].link = p;} return adjg; } main（） ｛ ｝ 54 因篇幅问题不能全部显示，请点此查看更多更全内容