西电机电院自动化专业软件技术基础上机报告.doc

班级：041132 学号：04113* 姓名：上机报告一、 上机目的（1） 掌握链表的基本运算：建立，查找，删除，排序等。（2） 掌握树的基本运算。二、 上机内容 1设有一个由正整数组成的无序单链表，编写完成下列功能的算法： 找出最小值结点，且打印该数值； 若该数值是奇数，则将其与直接后继结点的数值交换； 若该数值是偶数，则将其直接后继结点删除。2编一程序：建立一个数据域为1至10的带头结点的链表； 将此链表就地逆转。3设有一个含有数字、英文字母和其它字符的单链表，试编写一个算法将该单链表拆分为三个单链表，使每个单链表中只包含同一类的字符，要求利用原表中的结点空间作为这三个表的结点空间，头结点可以另辟空间。4某百货公司仓库中有一批电视机，试按价格从高到低的次序建立一个循环链表，每个结点有价格、数量和指针三个域。现新到10台价格为4000元的电视机，修改原链表并输出修改后链表的所有内容。5假设称正读反读都相同的字符序列为回文。例如，abba，abcba都是回文， ababab不是回文，试编写程序判别从标准输入读入的以为结束符的字符序列是否是回文。6试设计一个程序，求二叉树的结点数目和叶子结点数目。三、 设计说明：写出数据结构的定义和算法流程第一题：（1）使用尾插法建立带有头结点的单链表:因为题目要求为正整数，故以数字0最为结束符。（2）查找过程中，首先定义两个结点类型的变量p、s，p指向头结点，s指向第一个结点，然后将p依次后移，并且每移动一次就将p的值与s的值进行比较，若p-datadata，则将p赋给s;否则p继续后移，直至链尾。（3）删除结点过程：删除结点就需要找到此结点的前驱结点，然后将此结点的前驱的后继指向此结点的后继结点即可。（4）结点交换过程：定义一个中间结点，先将要交换的结点中的一个A赋给中间结点保存，然后将结点B的值赋给结点A，再将中间结点的值赋给结点B即可完成结点的交换。（5）打印结点过程：首先定义局部结点变量p,并且使其指向要打印的链表的头结点，然后将p结点后移，每移动一次就打印当前p的值，直至p的后续结点为NULL。第二题：(1)使用尾插法建立带有头结点的单链表:因为题目要求数字为1到10，故当数字小于1或者大于10时就停止输入。(2)打印结点过程：首先定义局部结点变量p,并且使其指向要打印的链表的头结点，然后将p结点后移，每移动一次就打印当前p的值，直至p的后续结点为NULL。(3)逆置过程：首先定义两个结点p、q，p结点指向第一个结点，q结点始终指向p的后续结点然后将p的后续指向q的后续，并且将q的后续指向p,再将头结点指向q，因为p的位置不变，q依次后移，每次移动都将q插在head之后，故可以实现链表的逆置。第三题：(1) 使用尾插法建立带有头结点的单链表:当遇到回车符时结束字符的输入。(2) 打印结点过程：首先定义局部结点变量p,并且使其指向要打印的链表的头结点，然后将p结点后移，每移动一次就打印当前p的值，直至p的后续结点为NULL。(3)对链表的分类整理：考虑到分类之后要返回给不同的三个链表，故使用全局变量，在函数调用时直接对全局变量进行操作。在查找过程中根据ASCII码的不同依次将他们连接在相应的链表之后。通过将头结点的地址传给PRINT函数就可以将相应的链表打印出来。第四题：(1)使用尾插法建立带有头结点的单链表:当遇到price和number均为0时结束输入。(2)排序过程：首先定义两个中间结点p、q,p结点指向链表的第一个结点，q结点指向p的后续结点，将q结点的price与p结点的price进行比较，如果p-priceprice，则将两者进行交换，直至q指向链表的最后一个元素。然后将p后移，重复以上步骤执行。(3)插入过程：在执行插入过程中，要先进行查找操作，即将要插入的元素s的s-price与原来链表中的元素逐个进行比较，插入到第一个比s-price大的数据前。第五题：方法一：基本思想：将字符存入数组，然后对数组进行首尾两端的元素进行比较，若相等，则将前标号后移一位，同时后标号前移一位。方法二：基本思想：采用堆栈的思想：先将数据存入链表，然后计算链表长度，将链表的前一半压入堆栈，若长度为则需先将链表当前指向后移一个，在将堆栈数据弹出，与链表后半部分数据进行比较；若长度为偶数，则直接将链堆、栈中数据弹出与链表中的后半部分进行比较。第六题：（1）树的建立：树的建立是借用队列先入先出的原则，队尾指向当前输入的结点，对头指向当前在这个结点的双亲结点，当尾结点是偶数时，当前结点作为左孩子与双亲结点链接，当尾结点为奇数时，当前结点作为右孩子与双亲结点进行链接，若当前结点为虚结点（即为）时，则无须链接。（2）结点的查找：只要当前的结点不是虚结点即为有效结点。（3）叶子结点的查找：只要当前结点没有左右孩子即可认为该结点是叶子结点。四、 调试分析在编写程序中使用的集成开发工具：Code：blocks 12.11使用的编译器：GNU GCC compile遇见的问题：（1）Mian函数返回类型在使用void时编译器提示返回类型不正确，在缺省时，main函数默认返回值类型为int,会出现warning信息。解决办法：使main函数的返回int类型，然后在最后加上“return 1”语句。（2）在有时括号的配对不正确，导致程序编译时不通过。解决办法：养成好的编程习惯，规范的格式有助于查找错误。（3）在设计算法时经常忽略了特殊元素的处理：比如在第四题插入新的数据，查找插入位置时，当p指向第一个元素是要进行特殊处理。在第五题中当字符串的长度是奇数时，将前一半元素压入堆栈以后，要先将p后移一次，在逐个出栈进行比较。解决办法：在设计算法之前，应该先将算法进行合理的推演，将所有的情况都要考虑进去，养成严谨的好习惯。改进之处：在第一题中，如果链表中的最小值有多个时，只能找到第一个，针对第一个进行处理。经验与体会：通过这几次上机，觉得将一个算法设计出来并不是难事，但是能否在计算机上正确运行是最关键的问题，有时编译时并不会报错，但是程序就是不能按照预期的结果运行，这时就需要进行调试，单步调试来观察能够判断算法正误的变量的值，然后对算法进行改进，最终使算法按照预期模式运行。觉得调试完一个程序之后对算法有了新的认识和更深刻的了解，收获远比编写出一个算法大得多。五、 测试结果 第一题：当最小值是偶数时：当最小值是奇数时：第二题：第三题：第四题：第五题：方法一：方法二:第六题：当输入为ABCDEFG# 时当输入为ABCDE#六、 带注释的源程序第一题：/*设有一个由正整数组成的无序单链表，编写完成下列功能的算法： 找出最小值结点，且打印该数值； 若该数值是奇数，则将其与直接后继结点的数值交换； 若该数值是偶数，则将其直接后继结点删除。*/#include#include#includetypedef struct node /*结点声明*/int data;struct node *next;linklist;linklist *head,*p;/*使用尾插法建立单链表，并且以0作为结束符*/linklist *CREAT()int data1;linklist *head,*s,*r;head=(linklist*)malloc(sizeof(linklist);r=head;printf(Please input the numbers:n);scanf(%d,&data1);while(data1!=0)s=(linklist*)malloc(sizeof(linklist); s-data=data1; r-next=s; r=s; scanf(%d,&data1);r-next=NULL;return head;/*打印当前链表的所有结点数值*/void PRINT(linklist *head) /*打印单链表*/ linklist *p; int j=0; p=head-next; while(p!=NULL) j+; printf(nnumber %d=%d,j,p-data); p=p-next;/*找到当期单链表中的最小值，并且将该最小值打印出来*/linklist *SEARCH(linklist *head) linklist *p,*s; p=s=head-next; while(p-next!=NULL) p=p-next; if(p-data)data) s=p; printf(nthe minimum is：%dn,s-data); return s;/*删除当前结点*/void DELETE(linklist *head,linklist *p) /*删除结点p*/ linklist *q; q=head-next; while(q-next!=p) q=q-next; q-next=p-next;/*将当前结点和其后面的结点进行交换*/void EXCHANG(linklist *p) int x; x=p-data; p-data=(p-next)-data; (p-next)-data=x;int main() linklist *head,*p,*q; head=CREAT(); /使用尾插法建立链。 printf(The Array is:); /打印当前链表。 PRINT(head); p=SEARCH(head); /查找最小值结点。 q=p-next; if(p-data%2=1) EXCHANG(p);/如果最小值为奇数，则将最小值结点与其后继结点交换 else DELETE(head,q); /如果最小值为偶数，则删除后继结点。 printf(nnnthe final numbers are:n); PRINT(head); return 1; 第二题：/*编一程序：建立一个数据域为1至10的带头结点的链表； 将此链表就地逆转。*/#include#include#includetypedef int datatype;typedef struct node datatype data; struct node *next;linklist; /定义结点结构体。linklist *head,*p; /对结点进行声明。/*使用尾插法建立带有头结点的链表。*/linklist *CREATLSTER() int a; linklist *head,*s,*r; head=(linklist*)malloc(sizeof(linklist); r=head; printf(Please input the numbers between 1 to 10:n); scanf(%d,&a); while(a=1)&(adata=a; r-next=s; r=s; scanf(%d,&a); r-next=NULL; /最后一个结点的后续结点置空。 return head;/*打印链表：将元素诸葛打印直至最后一个结点.*/void PRINT(linklist *head) linklist *p; int j=0; p=head-next; while(p!=NULL) j+; printf(nnumber%d=%d,j,p-data); p=p-next; /*将当前链表逆置，并且不开辟新空间，逆置之后将当链表头结点返回*/linklist *REVERSEL(linklist *head) linklist *p,*q; p=head-next; while(p-next!=NULL) q=p-next; p-next=q-next; q-next=head-next; head-next=q; return head;int main() linklist *head; head=(linklist*)malloc(sizeof(linklist); head=CREATLSTER(); /尾插法建立链表。 printf(n*nthe original numbers are : n); PRINT(head); /打印当前链表。 printf(n*n); REVERSEL(head); /将链表逆置。 printf(nn*nthe numbers after reversel are : n); PRINT(head); /打印逆置以后的链表。 printf(n*n); return 1; 第三题：/*3设有一个含有数字、英文字母和其它字符的单链表，试编写一个算法将该单链表拆分为三个单链表，使每个单链表中只包含同一类的字符，要求利用原表中的结点空间作为这三个表的结点空间，头结点可以另辟空间。*/#include#include#includetypedef char datatype;typedef struct node datatype data; struct node *next;linklist;/定义结点结构体linklist *NUM,*CHAR,*STRING,*head; /定义全局变量，以便函数调用之后能够将调用结果返回linklist *CREATLSTER() /创建链表，将数据读入 datatype ch; linklist *head,*r,*s; head=(linklist *)malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=n) s=(linklist *)malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; return head;/*删除头结点为head的链表中的结点p*/linklist *DELETE(linklist *p,linklist *head) linklist *q=head; while(q-next!=p) q=q-next; q-next=p-next; return p;/*对链表数据进行查找分类*/void FIND(linklist *head) linklist *p; linklist *s_NUM=NUM,*s_CHAR=CHAR,*s_STRING=STRING; /定义局部变量，以便将结果传给全局变量 p=head-next; s_NUM-next=NULL; s_CHAR-next=NULL; s_STRING-next=NULL; while(p!=NULL) if(p-data=0)&(p-datanext=DELETE(p,head); s_NUM=s_NUM-next; p=p-next; else if(p-data=A)&(p-datanext=DELETE(p,head); /将字母结点链接在s_CHAR之后 s_CHAR=s_CHAR-next; p=p-next; else s_STRING-next=DELETE(p,head); s_STRING=s_STRING-next; /将其他字符结点链接在s_STRING之后 p=p-next; s_NUM-next=NULL; s_CHAR-next=NULL; s_STRING-next=NULL;/*打印当前链表*/void PRINT(linklist *head) linklist *p; int j=0; p=head-next; while(p!=NULL) j+; printf(nVALUE %d = %c,j,p-data); p=p-next; int main() head=(linklist *)malloc(sizeof(linklist); /为head结点分配空间 NUM=(linklist *)malloc(sizeof(linklist); /为数字链表的头结点分配空间。 CHAR=(linklist *)malloc(sizeof(linklist); /为字母链表的头结点分配空间。 STRING=(linklist *)malloc(sizeof(linklist); /为其他字符链表的头结点分配空间。 printf(n*nPlease input characters:n); head=CREATLSTER(); /尾插法建立链表 printf(n*n); printf(nn*nthe input are:n); PRINT(head); /打印当前链表 printf(n*n); FIND(head); /为当前链表整理分类 printf(nn*nthe numbers are:n); PRINT(NUM); /打印数字链表 printf(n*n); printf(nn*nthe characters are:n); PRINT(CHAR); /打印字母链表 printf(n*n); printf(nn*nthe others are:n); PRINT(STRING); /打印其他字符链表 printf(n*n); return(1);第四题：/*某百货公司仓库中有一批电视机，试按价格从高到低的次序建立一个循环链表，每个结点有价格、数量和指针三个域。现新到10台价格为4000元的电视机，修改原链表并输出修改后链表的所有内容。*/#include#include#includetypedef struct node int number; float price; struct node *next;linklist;/*用尾插法创建链表*/linklist *CREAT() int number1; float price1; linklist *head,*r,*s; head=(linklist *)malloc(sizeof(linklist); r=head; printf(Please Input the number And The Price:n); scanf(%d%f,&number1,&price1); while(number1!=0)&(price1!=0) s=(linklist *)malloc(sizeof(linklist); s-number=number1; s-price=price1; r-next=s; r=s; scanf(%d%f,&number1,&price1); r-next=head; return head;/*打印链表*/void PRINT(linklist *head) linklist *p; int i=0; p=head-next; while(p!=head) i+; printf(nNO.%d THE NUMBER IS %d AND THE PRICE IS %f ,i,p-number,p-price); p=p-next; /*对链表进行从高到低排序*/linklist *SORT(linklist *head) linklist *p,*q; int number2; float price2; p=head-next; while(p-next!=head) q=p-next; while(q!=head) if(p-priceprice) number2=p-number; price2=p-price; p-number=q-number; p-price=q-price; q-number=number2; q-price=price2; q=q-next; p=p-next; return head;/*按照由高到低的顺序先寻找插入位置，然后将节点插入链表*/linklist *INSERT(linklist *head,linklist *s) linklist *q,*p; p=head-next; q=p-next; if(s-pricep-price) s-next=p; head-next=s; if(s-priceprice) p=p-next; q=q-next; s-next=q; p-next=s; return head;/*主函数*/int main() linklist *head,*s; s=(linklist *)malloc(sizeof(linklist); head=CREAT(); printf(n*nthe old table is:n); PRINT(head); printf(n*); SORT(head); printf(n*nthe sorted table is:n); PRINT(head); printf(n*); s=(linklist *)malloc(sizeof(linklist); printf(n*nInput the node need to insert:n); scanf(%d%f,&s-number,&s-price); printf(n*); INSERT(head,s); printf(n*nthe new sorted table after insert is:n); PRINT(head); printf(n*); return(1);第五题：方法一：/*假设称正读反读都相同的字符序列为回文。例如，abba，abcba都是回文， ababab不是回文，试编写程序判别从标准输入读入的以为结束符的字符序列是否是回文。假设称正读反读都相同的字符序列为回文。例如，abba，abcba都是回文， ababab不是回文，试编写程序判别从标准输入读入的以为结束符的字符序列是否是回文。编译环境：GCC开发软件：Codeblocks基本思想：将字符存入数组，然后对数组进行首尾两端的元素进行比较，若相等，则将前标号后移一位，同时后标号前移一位。*/#include#include#include#define maxsize 1024 int main() char amaxsize;int n=0,Flag=0;int i,j;printf(Please Input The String:n);an=getchar();while(an!=$) n+;an=getchar();printf(The string is:n);for(i=0;in;i+)printf(the character %d is %c n ,i+1,ai);for(i=0,j=n-1;(ij)&(i!=j);i+,j-)if(ai=aj) Flag+;else break;if(Flag=n/2)printf(nthe string is Palindromen);elseprintf(nthe string isnt Palindromen);return (1);方法二:/*假设称正读反读都相同的字符序列为回文。例如，abba，abcba都是回文， ababab不是回文，试编写程序判别从标准输入读入的以为结束符的字符序列是否是回文。编译环境：GCC开发软件：Codeblocks基本思想：采用堆栈的思想：先将数据存入链表，然后计算链表长度，将链表的前一半压入堆栈，若长度为则需先将链表当前指向后移一个，在将堆栈数据弹出，与链表后半部分数据进行比较；若长度为偶数，则直接将链堆、栈中数据弹出与链表中的后半部分进行比较。*/#include#include#include#define maxsize 1024typedef char datatype;int con=0;typedef struct Stack datatype elementmaxsize; int Top;Stack; /定义栈体typedef struct node datatype data; struct node *next;linklist; /定义链表，存储待判定字符void SETNULL(Stack *s )/将栈体置空 s-Top=-1;int EMPTY(Stack *s) / 判断栈体是否是空 if(s-Top=-1) return (1); else return (0); Stack *PUSH(Stack *s,datatype E) /入栈 if(s-Top=maxsize-1) printf(Stack Overflow); return (NULL); else s-Top+; s-elements-Top=E; return s;datatype *POPS(Stack *s) /出栈 datatype *temp; if(EMPTY(s) printf(Stack is emptyn); return (NULL); else s-Top-; temp=(datatype *)malloc(sizeof(datatype); *temp=s-elements-Top+1; return temp;datatype *GETTOPS(Stack *s) /取栈顶元素 datatype *temp; if (EMPTY(s) printf(Stack is empty); return (NULL); else temp=(datatype *)malloc(sizeof(datatype); *temp=s-elements-Top; return (temp); linklist *CREAT() /尾插法建立链表 datatype ch; linklist *head,*r,*s; head=(linklist *)malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=$) s=(linklist *)malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; printf(n); return head;int main() int i=1; linklist *head,*p; Stack *s; s=(Stack *)malloc(sizeof(Stack); head=(linklist *)malloc(sizeof(linklist); printf(nPlease Input The Strings:n); head=CREAT(); p=head; SETNULL(s); while(p-next!=NULL) /计算待判定字符（链表）长度 con+; p=p-next; p=head-next; for(i=1;idata); p=p-next; while(con%2=1) p=p-next; while(p!=NULL) if(p-data)=*GETTOPS(s) POPS(s); p=p-next; else break; if(EMPTY(s) printf(nn$nThe string