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

班级：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即

班级：041132 学号：04113*** 姓名：

可完成结点的交换。

（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大的数据前。

第五题： 方法一： 基本思想：将字符存入数组，然后对数组进行首尾两端的元素进行比较，若相等，则将前标号后移一位，同时后标号前移一位。

班级：041132 学号：04113*** 姓名：

方法二：

基本思想：采用堆栈的思想：先将数据存入链表，然后计算链表长度，将链表的前一半压入堆栈，若长度为则需 先将链表当前指向后移一个，在将堆栈数据弹出，与链表后半部分数据进行比较；若长度为偶数，则直接将链堆、

栈中数据弹出与链表中的后半部分进行比较。

第六题：

（1）树的建立：树的建立是借用队列先入先出的原则，队尾指向当前输入的结点，对头指向当前在这个结点的双亲结点，当尾结点是偶数时，当前结点作为左孩子与双亲结点链接，当尾结点为奇数时，当前结点作为右孩子与双亲结点进行链接，若当前结点为虚结点（即为?@?）时，则无须链接。 （2）结点的查找：只要当前的结点不是虚结点即为有效结点。 （3）叶子结点的查找：只要当前结点没有左右孩子即可认为该结点是叶子结点。

四、 调试分析

在编写程序中使用的集成开发工具：Code：：blocks 12.11 使用的编译器：GNU GCC compile

遇见的问题：

（1）Mian函数返回类型在使用void时编译器提示返回类型不正确，在缺省时，main函数默认返回值类型为int,会出现warning信息。

解决办法：使main函数的返回int类型，然后在最后加上“return 1”语句。 （2）在有时括号的配对不正确，导致程序编译时不通过。 解决办法：养成好的编程习惯，规范的格式有助于查找错误。

（3）在设计算法时经常忽略了特殊元素的处理：比如在第四题插入新的数据，

查找插入位置时，当p指向第一个元素是要进行特殊处理。在第五题中当字符串的长度是奇数时，将前一半元素压入堆栈以后，要先将p后移一次，在逐个出栈进行比较。

解决办法：在设计算法之前，应该先将算法进行合理的推演，将所有的情况都要考虑进去，养成严谨的好习惯。

改进之处：在第一题中，如果链表中的最小值有多个时，只能找到第一个，

针对第一个进行处理。

经验与体会：

通过这几次上机，觉得将一个算法设计出来并不是难事，但是能否在计算机上正确运行是最关键的问题，有时编译时并不会报错，但是程序就是不能按照预期的结果运行，这时就需要进行调试，单步调试来观察能够判断算法正误的变量的值，然后对算法进行改进，最终使算法按照预期模式运行。

觉得调试完一个程序之后对算法有了新的认识和更深刻的了解，收获远比编写

班级：041132 学号：04113*** 姓名：

出一个算法大得多。

五、 测试结果

第一题：

当最小值是偶数时：

当最小值是奇数时：

班级：041132 学号：04113*** 姓名：

第二题：

班级：041132 学号：04113*** 姓名：

第三题：

班级：041132 学号：04113*** 姓名：

第四题：

班级：041132 学号：04113*** 姓名：

第五题：

方法一：

班级：041132 学号：04113*** 姓名：

方法二:

班级：041132 学号：04113*** 姓名：

第六题：

当输入为ABCDEFG# 时

班级：041132 学号：04113*** 姓名：

当输入为ABCD@E@#

班级：041132 学号：04113*** 姓名：

六、 带注释的源程序

第一题：

/******************************************************************** 设有一个由正整数组成的无序单链表，编写完成下列功能的算法： ① 找出最小值结点，且打印该数值；

② 若该数值是奇数，则将其与直接后继结点的数值交换； ③ 若该数值是偶数，则将其直接后继结点删除。

********************************************************************/ #include #include #include

typedef 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(\scanf(\while(data1!=0)

{s=(linklist*)malloc(sizeof(linklist)); s->data=data1; r->next=s; r=s;

scanf(\r->next=NULL; return head; }

/*打印当前链表的所有结点数值*/

void PRINT(linklist *head) /*打印单链表*/ {

班级：041132 学号：04113*** 姓名：

linklist *p; int j=0;

p=head->next; while(p!=NULL) { j++;

printf(\ p=p->next;} }

/*找到当期单链表中的最小值，并且将该最小值打印出来*/ linklist *SEARCH(linklist *head) {

linklist *p,*s; p=s=head->next;

while(p->next!=NULL) {

p=p->next;

if((p->data)<(s->data)) s=p; }

printf(\：%d\\n\ 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)

班级：041132 学号：04113*** 姓名：

{

int x; x=p->data;

p->data=(p->next)->data; (p->next)->data=x; }

int main() {

linklist *head,*p,*q;

head=CREAT(); //使用尾插法建立链。 printf(\打印当前链表。 PRINT(head);

p=SEARCH(head); //查找最小值结点。 q=p->next;

if(p->data%2==1)

EXCHANG(p);//如果最小值为奇数，则将最小值结点与其后继结点交换 else

DELETE(head,q); //如果最小值为偶数，则删除后继结点。 printf(\ PRINT(head); return 1; }

第二题：

/******************************************************************** 编一程序：①建立一个数据域为1至10的带头结点的链表； ②将此链表就地逆转。

********************************************************************/ #include #include #include typedef int datatype; typedef struct node {

datatype data; struct node *next;

}linklist; //定义结点结构体。 linklist *head,*p; //对结点进行声明。

班级：041132 学号：04113*** 姓名：

/*使用尾插法建立带有头结点的链表。*/ linklist *CREATLSTER() {

int a;

linklist *head,*s,*r;

head=(linklist*)malloc(sizeof(linklist)); r=head;

printf(\ scanf(\

while((a>=1)&&(a<=10)) {

s=(linklist*)malloc(sizeof(linklist)); s->data=a; r->next=s; r=s;

scanf(\ }

r->next=NULL; //最后一个结点的后续结点置空。 return head; }

/*打印链表：将元素诸葛打印直至最后一个结点.*/ void PRINT(linklist *head) {

linklist *p; int j=0;

p=head->next; while(p!=NULL) {

j++;

printf(\ p=p->next; } }

/*将当前链表逆置，并且不开辟新空间，逆置之后将当链表头结点返回*/ linklist *REVERSEL(linklist *head) {

linklist *p,*q; p=head->next;

while(p->next!=NULL)

班级：041132 学号：04113*** 姓名：

{

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(\ PRINT(head); //打印当前链表。 printf(\

REVERSEL(head); //将链表逆置。

printf(\ PRINT(head); //打印逆置以后的链表。 printf(\ return 1; }

第三题：

/****************************************************************************** 3．设有一个含有数字、英文字母和其它字符的单链表，试编写一个算法将该单链表拆分为三个单链表，使每个单链 表中只包含同一类的字符，要求利用原表中的结点空间作为这三个表的结点空间，头结点可以另辟空间。

******************************************************************************/ #include #include #include typedef char datatype; typedef struct node {

datatype data; struct node *next;

}linklist;//定义结点结构体‘

班级：041132 学号：04113*** 姓名：

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;

定义局部变量，以便班级：041132 学号：04113*** 姓名：

s_CHAR->next=NULL; s_STRING->next=NULL; while(p!=NULL) {

if((p->data>='0')&&(p->data<='9')) //将数字结点链接在s_NUM之后 {

s_NUM->next=DELETE(p,head); s_NUM=s_NUM->next; p=p->next; }

else if((p->data>='A')&&(p->data<='z')) {

s_CHAR->next=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(\ p=p->next;

班级：041132 学号：04113*** 姓名：

} }

int main() {

head=(linklist *)malloc(sizeof(linklist)); //为head结点分配空间

NUM=(linklist *)malloc(sizeof(linklist)); //为数字链表的头结点分配空间。 CHAR=(linklist *)malloc(sizeof(linklist)); //为字母链表的头结点分配空间。 STRING=(linklist *)malloc(sizeof(linklist)); //为其他字符链表的头结点分配空间。

printf(\ head=CREATLSTER(); //尾插法建立链表 printf(\

printf(\ PRINT(head); //打印当前链表 printf(\ FIND(head); //为当前链表整理分类

printf(\ PRINT(NUM); //打印数字链表 printf(\

printf(\ PRINT(CHAR); //打印字母链表 printf(\

printf(\ PRINT(STRING); //打印其他字符链表 printf(\ return(1); }

第四题：

/******************************************************************** 某百货公司仓库中有一批电视机，试按价格从高到低的次序建立一个循环链表，每个结点有价格、数量和指针三个域。

现新到10台价格为4000元的电视机，修改原链表并输出修改后链表的所有内容。 ********************************************************************/ #include #include #include typedef struct node {

int number; float price;

班级：041132 学号：04113*** 姓名：

struct node *next; }linklist;

/************************************************************* 用尾插法创建链表

**************************************************************/ linklist *CREAT() {

int number1; float price1;

linklist *head,*r,*s;

head=(linklist *)malloc(sizeof(linklist)); r=head;

printf(\ scanf(\ while((number1!=0)&&(price1!=0)) {

s=(linklist *)malloc(sizeof(linklist)); s->number=number1; s->price=price1; r->next=s; r=s;

scanf(\ }

r->next=head; return head; }

/******************************************************* 打印链表

********************************************************/ void PRINT(linklist *head) {

linklist *p; int i=0;

p=head->next; while(p!=head) { i++;

printf(\ THE NUMBER IS %d AND THE PRICE IS \ p=p->next; } }

%f

班级：041132 学号：04113*** 姓名：

/******************************************************************** 对链表进行从高到低排序

********************************************************************/ 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->price<(q->price)) {

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->price>p->price) {

s->next=p; head->next=s;

班级：041132 学号：04113*** 姓名：

}

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(\ PRINT(head);

printf(\ SORT(head);

printf(\ PRINT(head);

printf(\

s=(linklist *)malloc(sizeof(linklist));

printf(\ scanf(\ printf(\ INSERT(head,s);

printf(\ PRINT(head);

printf(\ return(1); }

第五题：

方法一：

班级：041132 学号：04113*** 姓名：

/******************************************************************* 假设称正读反读都相同的字符序列为回文。例如，‘abba’，‘abcba’都是回文， ‘ababab’不是回

文，试编写程序判别从标准输入读入的以’@’为结束符的字符序列是否是回文。 假设称正读反读都相同的字符序列为回文。例如，‘abba’，‘abcba’都是回文， ‘ababab’不是回文，

试编写程序判别从标准输入读入的以’@’为结束符的字符序列是否是回文。 编译环境：GCC

开发软件：Codeblocks

基本思想：将字符存入数组，然后对数组进行首尾两端的元素进行比较，若相等，则将前标号后移一

位，同时后标号前移一位。

********************************************************************/ #include #include #include #define maxsize 1024 int main() {

char a[maxsize]; int n=0,Flag=0; int i,j;

printf(\ a[n]=getchar(); while(a[n]!='$') { n++;

a[n]=getchar(); }

printf(\ for(i=0;i

printf(\ }

for(i=0,j=n-1;(i

{

if(a[i]==a[j]) Flag++; else break; }

if(Flag==n/2)

printf(\ else

printf(\

班级：041132 学号：04113*** 姓名：

}

return (1);

方法二:

/*****************************************************************************************************

假设称正读反读都相同的字符序列为回文。例如，‘abba’，‘abcba’都是回文， ‘ababab’不是回文，

试编写程序判别从标准输入读入的以’@’为结束符的字符序列是否是回文。 编译环境：GCC

开发软件：Codeblocks

基本思想：采用堆栈的思想：先将数据存入链表，然后计算链表长度，将链表的前一半压入堆栈，若长度为则需

先将链表当前指向后移一个，在将堆栈数据弹出，与链表后半部分数据进行比较；若长度为偶数，则直接将链堆、

栈中数据弹出与链表中的后半部分进行比较。

*****************************************************************************************************/ #include #include #include #define maxsize 1024 typedef char datatype; int con=0;

typedef struct Stack {

datatype element[maxsize]; int Top;

}Stack; //定义栈体 typedef struct node {

datatype data; struct node *next;

}linklist; //定义链表，存储待判定字符

void SETNULL(Stack *s )//将栈体置空 {

s->Top=-1; }

int EMPTY(Stack *s) // 判断栈体是否是空 {

班级：041132 学号：04113*** 姓名：

if(s->Top==-1) return (1); else return (0); }

Stack *PUSH(Stack *s,datatype E) //入栈 {

if(s->Top>=maxsize-1) {

printf(\ return (NULL); } else {

s->Top++;

s->element[s->Top]=E; }

return s; }

datatype *POPS(Stack *s) //出栈 {

datatype *temp; if(EMPTY(s)) {

printf(\ return (NULL); } else {

s->Top--;

temp=(datatype *)malloc(sizeof(datatype)); *temp=s->element[s->Top+1]; }

return temp; }

datatype *GETTOPS(Stack *s) //取栈顶元素 {

datatype *temp; if (EMPTY(s))

本文来源：https://www.bwwdw.com/article/r36g.html