西电软计技术上机

西安电子科技大学机电工程学院 软件技术大作业

任课老师 许威 上机报告

一、 上机目的

1． 熟悉线性表，链表，队列，二叉树等数据结构

2． 学习利用C语言实现多种数据结构的建立和多种操作（插入，删除等） 3． 在编程过程中学习程序的调试方式

二、 上机内容

一共完成5题——1,2,4,5,6

1题：

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

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

③ 若该数值是偶数，则将其直接后继结点删除。 2题：

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

4题：

某百货公司仓库中有一批电视机，试按价格从高到底的次序建立一个循环链表，每个结点有价格、数量和指针三个域。现新到10台价格为4000元的电视机，修改原链表并输出修改后链表的所有内容。

5题：

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

6题：

试设计一个程序，求二叉树的结点数目和叶子结点数目。

三、 设计说明

1题

1）用带头结点的单链表是实现 2）结点声明

typedef struct node {

int data;

struct node *next; }linklist

3）共定义了5个函数

CREAT——建立单链表函数 DELETE——删除结点函数

SEARCH——查找数据域最小的结点函数

基本思想：定义两个指针，其中s指针始终记录值较小的结点，并与p

所指结点比较，直到将整个链表比较完毕。 EXCHANGE ——交换结点值函数

PRINT——打印单链表，显示结点数据值函数

4）输入说明：以为单链表由正整数组成，所以以输入0为输入结束标志。

2题

1） 用带头结点的单链表实现 2） 共定义了3个函数

CREAT——建立单链表 REVERSE——将单链表逆置

基本思想：有3个指针r，s。r指向单链表尾部，s指向单链表头部，

s为用于交换结点数据值的中间量。将s和r所指结点交换，然后r向前移动一个位置，s向后移动一个位置，再换，直到r=s（即r，s重合——当结点数为奇数时）或者s=r->next（即s跑到r的后面——当结点个数为偶数时）。这时说明整个链表交换完毕，即逆置。（因为r是前移，所以该过程中要记录r的前驱p） PRINT——打印单链表

3） 输入说明：输入结点数据域为1~10，所以以大于10的数的输入为输入结

束标志。

说明：单链表建立为头插法，所以链表打印出的顺序与实际输入相反。实现逆置后就与实际输入顺序一致。

4题

1） 用带头结点的循环链表实现 2） 结点声明

typedef struct node {

int con; ——数量 float pri;——价格 struct node *next;

} tvnode; 3） 共定义5个函数

CREAT——建立带头结点的循环链表 EXCHANGE——交换两个结点的数据域 ARRANGE——按价格从高到低的排序函数

基本思想：定义两个指针s，p。p指向头结点后一个结点，s指针寻

找比p大的结点并与p交换，内循环一次即实现将最大值结点置于链表头。之后p向后移动一个位置，与上面相似循环地找出次大的结点与p交换，即实现将次大值结点置于第二的位置。以此类推，直到p移动到链表尾就完成排序。这样实现了按价格从高到低排列结点。 PRINT——打印单链表函数，显示数量和价格

INSERT——将新结点s按价格插入到已排好序的链表中

基本思想：定义指针p，r。r用以寻找第一个比新插入结点值小的

结点，p始终指向r的前驱。找到后，p指向该结点，s后移一个结点，将新结点s插入p，r之间。

4） 输入说明：先输入台数，再输入价格，当台数为0时认为输入结束。（如

果要统计台数为0的记录，可修该结束条件）

5题

1）用一维数组实现。（当然可以参考用课件中的队列的方法，但就算法繁简来说，用数组实现更为简单高效）

2）基本思想：设数组长度为n。分别将a[0]与a[n-1]，a[1]与a[n-2]，a[2]与a[n-3]……比较，判断是否相等，相等则计数变量k加1，否则退出循环。最后判断k值。若是回文，则k应该等于[n/2],否则就不是回文。 3）输入说明：以$输入为结束标志

6题

1） 用课本P152二叉链表的方式建立二叉树 2） 结点声明

typedef struct node {char data;

struct node *lchild,*rchild; }bitree; 3） 共定义3个函数

CREAT——建立二叉链表 COUNT1——统计结点个数

基本思想：利用课本P153的先序遍历法，遍历二叉树。若结点数据

域值不为虚结点@，则n加1 COUNT2——统计叶子数

基本思想：利用课本P153的先序遍历法，遍历二叉树。若结点左子

树，右子树均为空，则该结点为叶子，m加1

说明：因为二叉树遍历由递归算法实现，所以为了使在递归时，n，m能继续累加，所以将n，m定义为全局变量。 PRINT——打印二叉树

基本思想：利用课本P153的先序遍历法，遍历整个二叉树。每访问

一个节点，就打印其数据域值。

4） 输入说明：以#的输入为输入结束标志。二叉树按自上而下，从左到右的顺

序输入，虚结点以@表示。

四、 调试分析

1．调试所遇到问题

1）编译时，头文件包含不全

2） 逻辑一般没有错误，而问题多出在实际实现过程与自己想法间的差距。

例如：2题，判断条件（s!=r)&&(r->next!=s)。我想实现的是当结点数为偶数时，头尾两部分交换结束的条件是s=r；当为奇数时，结束的条件是s跑到r的后面。因此在写程序初，逻辑运算用的是||（或），即二种情况中的一种，结果运行时怎么都不正确。后来在老师帮助下才找到错误。

3） 对于算法实际运行的方式理解不到位。在做第6题时认为该题应该比

较简单，因为二叉树的建立和遍历课本上都有现成的算法，自己只需添加相应的判断条件即可。结果调试发现怎么做都不正确，后来仔细想递归算法的细节才注意到统计变量递归一次又从头开始统计，所以

结果始终是结点数1，叶子数0。改进作法是将统计量变为一个初值为0的参数，发现也是不行的。最后只能改为全局变量。

4） 输入方式不正确。在输入时没有注意输入方式，随便加空格，使得运

行结果错误。

5）改进思想

1题算法没有考虑有多个相等的最小值的情况。如果有多个相等最小值则在交换和删除时算法会不一样。

6）经验与体会

1． 体会：写出实现所需功能的程序不难，时间也不需太久。最费时费

力的还是调试部分。特别是自己认为逻辑，语法都没有错误时，最难改正。这时只能一步一步的调。 2． 经验：

调试时可以一部分一部分的进行。

2）一种简单实用的调试方法。不用编译中的单步运行去调。而是用printf函数去打印每一步变量值与理想值比较，这样来发现问题出在什么地方。

1）将实现不同功能的程序段写成函数，这样逻辑清晰而且

五、 测试结果

1题

输入单链表为：8,4,6,2,7,9,1,3,5 运行结果如下：

2题

输入数据为：3,4,6,8,0,2,5,2,10,7（头插法，所以链表实际顺序与输入顺序相反） 运行结果

4题

输入数据为：

台数 10 8 12 最后插入：10台，4000元

价格 2600 1500 5000

5题

第一次输入为12321 第二次输入为cdvf 运行结果如下：

6题

第一次输入二叉树为

D E F G B C A

第二次输入二叉树为

D E B C A

两次运行结果如下：

六、 源程序

1题

#include #include #include

typedef struct node /*结点声明*/

{

int data;

struct node *next; }linklist;

linklist *head,*p;

linklist *CREAT() /*建立带头结点的单链表*/ { int dat;

linklist *head,*s,*r;

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

scanf(\

while(dat!=0) /*因为是正整数组成的，所以0为结束输入标志*/ {s=(linklist*)malloc(sizeof(linklist)); s->data=dat; r->next=s; r=s;

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

void DELETE(linklist *p,linklist *head) /*删除结点p*/ {linklist *q; q=head->next;

while(q->next!=p)q=q->next; q->next=p->next; free(p); }

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; /*结点s始终指向小的结点*/ }

printf(\return s; }

void EXCHANG(linklist *p,linklist *q) /*交换两个结点的值*/ { int x; x=p->data; p->data=q->data; q->data=x; }

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

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

{printf(\ p=p->next;} } main()

{

linklist *head,*p,*q; head=CREAT();

printf(\PRINT(head); p=SEARCH(head); q=p->next; if(p->data%2==1) EXCHANG(p,q); else

DELETE(q,head); PRINT(head);}

2题

#include #include #include typedef struct node {

int data;

struct node *next;

}linklist; /*结点声明*/

linklist *CREAT() /*头插法建立单链表*/ {

int dat;

linklist *head,*s; head=NULL; scanf(\ while(dat<=10)

{s=(linklist*)malloc(sizeof(linklist)); s->data=dat; s->next=head; head=s;

scanf(\ }

return head; }

linklist *REVERSE(linklist *head) /*将单链表逆置*/ {

linklist *p,*s,*r; int temp; r=head;

s=head; /*s指向头部*/ while(r->next!=NULL)

r=r->next; /*r指向链表尾部*/ while((s!=r)&&(r->next!=s)) { p=head;

while(p->next!=r)p=p->next; /*p为r的前驱，以实现r向前移*/ temp=s->data; s->data=r->data;

r->data=temp; /*将头尾两部分互换(第一个与最后一个结点换，

第二个与倒数第二个……)*/

s=s->next;

r=p; /*交换后s向后移，r向前移*/ }

return head; }

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

linklist *s; s=head; while(s!=NULL) { }

printf(\s=s->next;

}

void main() {

linklist *head; head=CREAT();

printf(\ PRINT(head); head=REVERSE(head);

printf(\ PRINT(head); }

4题

#include #include #include typedef struct node { int con; float pri;

struct node *next;

} tvnode; /*结点声明

con-数量 pri-价格*/

tvnode *CREAT() /*建立循环链表*/ { int c; float p;

tvnode *head,*s,*r;

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

scanf(\ while(c!=0) { s=(tvnode*)malloc(sizeof(tvnode)); s->con=c; s->pri=p; r->next=s; r=s;

scanf(\

}

r->next=head; return head; }

void EXCHANGE(tvnode *s,tvnode *p) {

int tem1; float tem2; tem1=p->con; tem2=p->pri; p->con=s->con; p->pri=s->pri; s->con=tem1; s->pri=tem2; }

tvnode *ARRANGE(tvnode *head) {

tvnode *s,*p; p=head->next; s=p->next; while(p!=head)

/* 交换两个结点函数 */ /*排序函数*/ { }

return head; }

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

tvnode *s; s=head->next; while(s!=head) { } }

tvnode *INSERT(tvnode *head,tvnode *s) /*插入新节点s*/ {

tvnode *p,*r; p=head->next; r=p->next;

printf(\s=s->next; while(s!=head) { }

p=p->next;

s=p->next; /*交换后p向后移动一个(详见基本思想部分)*/

if((s->pri)>(p->pri)) EXCHANGE(s,p);

s=s->next; /*s指向最大值结点，并将其与p交换*/

else

if((p->pri)<=(s->pri)) /*将新节点s插入价格高于

它和低于它的两个结点p，r间*/

{

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

} else { {

p=r; r=r->next;

s->next=r;

while((r->pri)>(s->pri))

} /*寻找比s值小的第一个结点r，p为r的前驱*/

p->next=s;

} /*将s插入r，p之间*/ return head; }

void main() {

tvnode *head,*s; int c; float p;

printf(\ head=CREAT();

printf(\ PRINT(head); ARRANGE(head);

printf(\ PRINT(head);

printf(\ scanf(\

s=(tvnode*)malloc(sizeof(tvnode)); s->con=c;

s->pri=p; INSERT(head,s);

printf(\ PRINT(head); }

5题

#include #define maxsize 1024 void main() {

char a[maxsize]; /*定义数组*/ int n=0,k=0; int i,j;

printf(\ a[n]=getchar();

while(a[n]!='$') /*$结束输入*/ { n++;

a[n]=getchar();

} /*n为数组输入元素个数*/ printf(\ for(i=0;i

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

if(k==n/2) }

printf(\printf(\ else

if(a[i]==a[j])k++; else break; printf(\

6题

#include #include #include #define maxsize 1024 typedef struct node {char data;

struct node *lchild,*rchild;

}bitree; /*结点声明*/

bitree *CREAT() /*建立二叉树*/ {

char ch;

bitree *Q[maxsize]; int front,rear; bitree *root,*s; root=NULL; front=1; rear=0; ch=getchar(); while(ch!='#') {s=NULL; if(ch!='@')

{s=(bitree*)malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL;} rear++; Q[rear]=s; if(rear==1)root=s; else

{if(s&&Q[front])

if(rear%2==0)Q[front]->lchild=s; else

Q[front]->rchild=s; if(rear%2==1)front++;

}

ch=getchar(); }

return root; }

int n=0;

int m=0; /*为实现递归数据的有效，采用全局变量

n-结点数 m-叶子数*/

void COUNT1(bitree *p) /*统计结点数*/ {

if(p!=NULL) {

if(p->data!='@')n++; COUNT1(p->lchild); COUNT1(p->rchild); } }

void COUNT2(bitree *p) /*统计叶子数*/ {

if(p!=NULL)

{if((p->lchild==NULL)&&(p->rchild==NULL)) m++;

COUNT2(p->lchild); COUNT2(p->rchild); } }

void PRINT(bitree *p) /*打印二叉树*/ {

if(p!=NULL)

{ } return; }

void main() {

bitree *root; int n1,n2;

printf(\ root=CREAT(); PRINT(root); COUNT1(root); COUNT2(root); n1=n; n2=m;

printf(\结点数=%d，叶子数=%d\ }

printf(\PRINT(p->lchild); PRINT(p->rchild);

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