数据结构实验手册修订版

1、第一部分c语言基本知识数据结构是计算机专业及相关专业的核心基础课。上机实验是对学生的一种全面 综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题 中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生 学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的动手能力；另一方面, 能使书上的知识变“活”，起到深化理解和灵活常握教学内容的目的。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语 法细节。多年的教学实践表明，学生的程序设计基础并不一致，相当一部分人基础较为薄弱, 对上机实验感到非常困难。存在的主要

2、问题是：不能正确的输入数据，结构体概念陌生，函 数的传址调用概念不清，有关指针的内容理解不深。因此，有必要将数据结构所必须使用的 c语言语法在此做简单介绍。如果学生基础好，可以跳过这一部分内容不看。一、基本输入和输出看起来简单的输入/输出，往往是上机实验最容易出错的地方，尤其是输入。对于一个 算法程序，如果数据不能正确输入，算法设计得再好也无法正常运行。i输入c语言的输入是由系统提供的scanf()等函数实现，在程序的首部一般要求写入：# include <stdio.h>因为标准输入/输出函数都存在于头文件stdio.h之中，现将其包含进来方可使用这些常用的输入/输出函数。有的系

3、统允许不使用上述包含语句，可以直接使用标准输入/输出函数。函数scanfo的功能很丰富，输入格式也是多种多样，这是大家较为熟悉的知识，这里不 做详细介绍。在使用中需要注意以下儿个问题。(1) 一条scanf()语句有多个变量、并且都是数值型(int, float, double)时，在输入数 据时应该在一行之内键入多个数据，数据之i'可空格分隔。例如：int n; float x; scanf (“d %f " , &n, &x);正确的输入应是：整数 空格 实数回车。例如：100 u34 ?就是在两个数据之间使用空格键为分隔符，最后打冋车键。如果语句中在d和

4、彳之间有一个逗号：scanf ("%d , %f", &n, &x);正确的输入应是：整数逗号实数回车。例如：100, 3.14 ?(2) 在需要字符型变量或字符串输入时，要单独写一条输入语句，这样不易出错。 如杲在同一条scanf()语句中将字符型和数值型混合输入常常会出错。因为键盘输入时在数 值型数据之间'空格键起'分隔符作用，但是在字符或字符串之间，'空格'会被当做 一个字符，而不能起到'分隔符'的作用。所以将它们混在一起容易出错。(3) 在scanf()语句屮变暈写法应该是该变暈的地址，这一点常被忽视。

5、viod main() char name10, ch ; int num;printf(unprintf(unpi*intf(“ii1:2:3:4:5:6:例1请看下列程序:float x;请输入姓名：”)；scanf(“s”，name);请输入性别：j; scanf(“c", &ch);请输入学号和成绩：j； scanfc %d%f', &n, &x);为了方便说明问题程序屮加了行号，运行时当然不允许行号。一般情况下在scanf() 语句中的变量名之前要加上求地址符&，上述程序第5, 6行之中就是这样。为什么第4行的 mime前面不加&am

6、p;呢？因为name代表字符串，即是一维字符数组，一维数组名本身就是一个 地址，是该数组的首地址，所以name前面不加&。在本程序中把字符串、字符、数值型变量分别写入不同的scanf()语句，输入数据的具 体形式如下：请输入姓名：zhanghua请输入性别：v请输入学号和成绩:101 90.5请考虑如果姓名输入成：zhang hua,会出现什么现象？那样只会读入zhang做姓名，而hua 被忽略，还会影响后面的输入语句无法正确读入数据。因此，应该充分重视数据的输入技术。2输出c语言的输出是由系统提供的printf()等函数來实现，在程序的首部一般要求写入：# include <s

7、tdio.h>因为标准输入/输出函数都存在于头文件stdio.h z中，现将其包含进来方可使用这些常 用的输入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/输出函数。输出函数printf()的语法一般容易掌握，这里强调的是怎样合理巧妙的使用它。(1) 在连续输出多个数据时，数据之间一定要有间隔，不能连在一起。int n= 10, m=20, p=30;printf(4tn %d%d%d",n,m,p);printf(4tn %6d%6d%6<t,n,m,p);提倡使用的语句第一行输出是：102030第二行输出是：102030(2) 在输入语句scanf

8、( )2前先使用printf()输出提示信息，但是在printf()最后不 能使用换行符。int x;printf(4tn x二厂)；句尾不应使用换行符scanf( “d",&x);这样使光标与提示信息出现在同一行上，光标停在问号后边：x二?口。(3) 在该换行的地方，要及时换行。inti;printf(4澈据输出如下：e);/需要换行for (i=0; i<8; i+) printf(4t%6d, i);/儿个数据在同一行输出，不能换行(4) 在调试程序时多加儿个输出语句，以便监视中间运行状况。程序调式成功后，再 去掉这些辅助输出语句。二、函数与参数传递c语言的源程序

9、是由一个主函数和若干(或零个)子函数构成，函数是组成c语言程 序的基本单位。函数具有相刈独立的功能，可以被其他函数调用，也可调用其他函数。当函 数直接或间接的调用自身时，这样的函数称为递归函数。是否能够熟练的设计和使用函数，是体现一个人程序设计能力高低的基本条件。因此有 必要回顾和复习c语言函数的基本概念。1函数的设计函数设计的一般格式是：类型名 函数名(形参表) 函数体；函数设计一般是处理一些数据获得某个结果，因此函数可以具有返回值，上面的类型名 就是函数返冋值的类型，可以是int, float.等。例如：float funx(形参表)函数体；.函数也可无返回值，此时类型是voido例如：v

10、oid funy(形参表)函数体；而函数体内所需处理的数据往往通过形参表传送，函数也可以不设形参表，此吋写为： 类型名 函数名() 函数体；例2设计一个函数计算三个整数之和，再设计一个函数仅输出一条线。设计主函数调 用两个函数。# include <stdio.h>int sumx (int a, int b, int c)/*计算三个整数之和的函数*/ int s;s 二 a+b+c;return s;void display( )/*输出一条线的函数*/ printf(n“)；void main() int x,y, z ,sa;x=y=z=2;display();/* 画一条

11、线 */printf(4tn sum=%d,sumx(x,y,z); /* 在输出语句中直接调用两数 sumx() */ printf(4tn %6d%6d%6d'',x,y,z);printf(4tnh);display();x=15; y=16; z=17;sa二sumx(x, y, z);/*在赋值语句中调用函数sumx()*/printf(4tn “ sum=%(f',sa);printf(4tn %6d%6d%6dn,x,y,z);displayo;/* 程序结束 */运行结果:sum= 6222sum=481516172.关于函数的参数传递函数在被调用时，由

12、主调程序提供实参，将信息传递给形参。在调用结束后，有时形参 可以返回新的数据给主调程序。这就是所谓参数传递。各种算法语言实现参数传递的方法通 常分为传值和传址两大类。在上例中函数sumx()的设计和主函数对它的调用，就是传值调用。第一、第二次调 用，带入的实参均是三个整型变量。调用函数返冋后，在主程序屮输出实参的值仍与调用z 前相同。传值调用的主要特点是数据的单向传递，由实参通过形参将数据代入被调用函数， 不论在调用期间形参值是否改变，调用结束返回主调函数之后，实参值都不会改变。在不同的算法语言屮，传址调用的语法有所不同。在pascal语言中用变参实现传址。 在c语言中采用指针变量做形参来实现

13、传址。传址调用的主要特点是可以实现数据双向传 递，在调用时实参将地址传给形参，该地址中的数据代入被调用函数。如果在调用期间形参 值被改变，也即该地址中的数据发牛变化，调用结朿返冋主调函数之后，实参地址仍然不变, 但是该地址中的数据发生相应改变。这就是数据的双向传递。现看一例题：例3 设计一个函数实现两个数据的交换，在主程序屮调用。#include <stdio.h>viod swap( int *a, int *b) ；/* 函数原型声明 */void main() int x=100, y=800;printtvan %6d%6ct, x, y);/* 输岀原始数据 */swap

14、(&x, &y);/*调用交换数据的函数swap() */printf(44n %6d%6d", x ,y);/* 输出交换后的数据 */viod swap( int *a, int *b) int c;c=*a; *a = *b;*b=c;运行结果：100 800800 100实践证明x,y的数据在调用函数前后发生了交换变化。形参是指向整形的指针变量a 和b,在函数体内需要交换的是指针所指的存储单元的内容，因此使用切=6;这样的写法。 在调用时，要求实参个数、类型位置与形参一致。因为实参应该是指针地址，所以调用语句 swap(&x, &y)中，实参&

15、amp;x,和& y代入的是整型变暈x,y的地址。在函数体内交换的是实参地 址中的内容，而作为主函数变量x,y的地址仍然没有改变。从整数交换的角度看，本例题实 现了双向数据传递。若从指针地址角度看，调用前后指针地址不变。在数据结构教材中，很多函数的形参前带有“&”，如顺序表的初始化函数的声明： status lnitlist_sq( sqlist &l)其中，形参前带有“&”，说明形参t是引用类型的。引用类型是c+语言特有的。引用类 型的变量，其值若在函数中发生变化，则变化的值会带冋主调函数小。下面的例子说明了函 数中引用类型的变量和非引用类型的变量的区别：例4

16、# include<stdio.h>void fa(int a)函数屮改变a,将不会带回主调函数(主调函数屮的a仍是原值) a+;printf(”在函数 fa 中：a=%dn",a);void fb(int &a) rfl于a为引用类型，在函数屮改变a,其值将带回主调函数 a+;printf(h在函数 fb 中：a=%dnh,a);void fc(int *a) a为指针类型，数据双向传递，在函数屮改变恤的值，其结果将带回 主调函数 (*a)+;printf("在函数 fc 中：*a=%dn'*,*a);void main() int n=l,*

17、p;p二&n;printf(”在主程中，调用函数fa之前：n=%dnu,n);fa(n);prinlf(”在主程中，调用函数fa z后，调用函数fb z前:n=%dn",n); fb(n);printf("在主程中，调用函数fb之后，调用函数fc之m： n=%dn'n); fc(p)；printf(”在主程屮，调用函数fc z后：n=%dnu,n);运行结果：在主程屮，调用函数fa之前：n=l在函数fa中：a=2在主程屮，调用函数faz后，调用函数fbz前:n=l在函数fb中:a=2在主程中，调用函数fb之后，调用函数fa之前:口二2在函数fc中：*a=3在

18、主程屮，调用函数fcz后，1尸3需要进-步说明的是，c语言的传址调用比较复杂，不如c卄的引用调用方便。因此建 议大家采用visual c+作为编译环境，在此环境下可以兼容c程序，并且可以直接使用引用 参数，算法变为程序的过程就会容易很多。三、结构体及运用数据结构课程所研允的问题均运用到“结构体”。在c语言中结构体的定义、输入/输出 是数据结构程序设计的重要语法基础。定义结构体的一般格式：struct结构体类型名类型名1类型名2类型名n变量名1;数据子域变量名2；变量名n；其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结 构体类型的变量，声明创建一个结构体变量的

19、方法是：struct结构体类型名结构体变量名；例如：struct elemtype /*定义结构体*/ int num; char nameflo;； struct elemtype x； /* 声明结构体变量x */另外有一种方法使用typedef语句定义结构体，在声明结构体变量时町以不写struct, 使得书写更加简便。例如：typedef struct int num;char name10; elemtype；elemtype就是一个新的类型名，并且是结构体类型名。声明变量x的语句是： elemtype x;一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型(int

20、char等)，也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数 组。它们也可以称为结构体的数据成员。通过“结构体变量名数据子域”可以访问数据子域。例5 设计student结构体，在主程序屮运用。#include <stdio.h>#include <string.h>typedef struct> long num;佯定义结构体student */ 严 学号 */int x;/*成绩*/char name10; student;void main() student si;/*姓名 */*声明创建一个结构体变量s1 */si.num-1001

21、 ;/*为s1的数据子域提供数据*/si. x=83;strcpy( , * 李 明”)；printf( t4n 姓名：); /* 输11!结构体变量si的内容*/printf( mn 学号： %d", sl.num);printf( *n 成绩：d”, sl.x);或者使用键盘输入： scanf(“<t, sl.num);scanf(“d”, sl.x); scanf(“s”，);还可以通过“结构体指针->数据子域”来访问数据域。在实际问题中还会使用到指向 结构体的指针，通过以下语句段可以说明结构体指针的一般用法。 studen

22、t *p;/* 声明指针变量p*/p=( student *)malloczeof( student); /*分配存储单元，首地址赋给p指针*/ p->num=101;p->x=83; strcpy( p>name, “李 明 ")；printf("n % 10s%6d%6d,p->name,p->num,p->x);设计一个一维数组，每个数组元素是student结构体类型，通过以下语句段可以说明结 构体数组的一般用法。可以通过“结构体数组名下标.数据子域”访问数据域。 student a5;/*声明创建一个结构体数组aint i;for

23、( i=0, i<5, i+)printf(un学号：d” ,ai.num);printf(t4n姓名：s” ,)；1printf(4<n1成绩：d” ,ai-x)；四动态分配函数以数组为例，在我们声明一个数组时，必须用一个常量指定数组的长度，但是常常这个 数组的长度是未知的。一般采用的方法是声明一个较大的数组，内存利用率有可能不高且仍 可能溢出。采用动态分配函数就可以较好地解决这个问题。在数据结构实验屮，很多顺序存 储结构都采用的动态分配内存的方式。不同的c编译系统提供的动态存储分配函数不同。有的编译系统放在malloc.h中，有 的编译系统放在stdlib.h中

24、。常用的有如下儿种：(1) malloc()函数其函数原型为：void *malloc(unsigned int size);其功能是：分配一块长度为size字节的连续空间，并将该空间的首地址作为函数的返 回值。如果函数没有成功执行，返回值为空指针(null或0)。由于返回的指针的基类型 为void,应该通过强制类型转换后才能存入其他基类型的指针变量屮，否则会有警告提示。例如：p=(int *)malloc(sizeof(int);sizeof运算符返回某类型所需的内存字节数或某变量所分配的字节数，该处返回一个整 型变量所需要的字节数2,它即为动态分配内存空间的大小。返回的指针先要通过(int

25、*) 转换成整型指针，然后才赋值给整型指针变量p。(2) realloc ()函数其函数原型为：void * realloc(void * ptr, unsigned int size)；其功能是：用来改变已分配的内存空间的大小，如果重新分配成功，则该函数返回指 向被分配内存的指针，否则返回空指针null。其中，realloc是该函数的名字，ptr是指 向已分配的内存空间的指针，即为所要改变大小的内存空i'可，size是改变后的内存空间大小。 既可以将原来空间变大，也可以将原来空间变小。如果用于扩大一个内存块，那么这块内存 原先的内容依然保留，新增的内存添加到原先内存块的后面。相反如果

26、用于缩小一个内存块, 那么这个内存原来尾部的内存便被删除，但是剩余部分内存的原先内容依然保留。如果原先内存块的大小是无法改变的那么realloc将重新分配另一块指定大小的内存块, 并把原先那块内存的内容复制到新的内存块上面。所以在使用了 realloc z后便不可以再使 用原来指向那块旧内存的指针了，而应该使用realloc所返回的新指针。否者很容易出错！例如：p=(int *)malloc(p, 20*sizeof(int);作用是将原来分配给指针p的内存变更为20个整型变量所需内存空间。(3) free()函数其函数原型为：void free(void *p);其功能是：释放以前分配给指针

27、变量p的动态空间(由函数malloc或realloc等分配的 地址)。例如：free(p);作用就是将上例屮malloc或realloc分配的空间释放掉。第二部分上机实验上机实验要求及规范一、实验步骤数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。上机实验是 一个重要的教学环节。一般情况下学生对于编写程序上机练习具有一定的积极性，但容易忽 略实验的总结，忽略实验报告的撰写。正确的实验步骤如下：1 问题分析与系统结构设计充分分析和理解问题，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数 据结构为屮心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据

28、的存储结构（是顺序结构还是链表结构？）然后设计有关操作的函数。在每个函数模块中， 要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法 头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。2. 详细设计和编码详细设计是对函数（模块）的进一步求精，用伪高级语言（如类c语言）或自然语言写 出算法框架，这时不必确定很多结构和变量。编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如c/c+语 言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错 矫正，在程序成功后再删去它们。3. 上机准备熟悉高级语言用法

29、，如c语言。熟悉机器（即操作系统和编译系统），基本的常用命令。 静态检查主要有两条路径，i是用i组测试数据手工执行程序（或分模块进行）；二是通过 阅读或给别人讲解口己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和 断言。如果程序中逻辑概念清楚，后者将比前者有效。4. 上机调试程序调试最好分块进行，自底向上，即先调试底层函数，表而上的麻烦工作可以大大降低调 试时所面临的复杂性，提高工作效率。5. 整理实习报告在上机实开始之前耍充分准备实验数据，在上机实践过程中要及时记录实验数据，在上 机实践完成之后必须及时总结分析。写出实验报告。二、实验报告的基本要求：一般性、较小规模的上机实验题

30、，必须遵循下列要求，养成良好的习惯：（1）题目：内容叙述（2）程序清单（带有必要的注释）（3）调试报告：实验者必须重视这一环节，否则等同于没有完成实验任务。这里可以 体现个人特色、或创造性思维。具体内容包括：测试数据与运行记录；调试中遇到的主要问 题，自己是如何解决的；经验和体会等。三、实验习报告的提高要求：阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。（1）需求和规格说明描述问题，简述题目要解决的问题是什么，规定软件做什么，原题条件不足时补全。（2）设计a. 设计思想：存储结构（题目中限定的要描述）；主要算法基本思想。b. 设计表示：每个函数的头和规格说明；列出每个函数所调

31、用和被调用的函数，也 可以通过调用关系图表达。c. 实现注释：各项功能的实现程度、在完成基本要求的基础上还有什么功能。（3）用户手册：使用说明。（4）调试报告：调试过程屮遇到的主要问题是如何解决的；设计的回顾、讨论和分析; 时间复杂度、空间复杂度分析；改进设想；经验和体会等。四、关于实验题目本实验手册共分七个大实验，每个实验中又有几个小题目。学生可以根据实际情况选做 其中2个或全做。有的实验只有一个题目，要求必做。实验一线性表一. 实验目的1. 掌握线性表的逻辑结构特性以及在计算机内的两种存储结构。2. 掌握线性表的基本操作在两种存储结构上的实现；英屮以链表的操作为侧重点；会灵 活运用线性表结

32、构解决某些实际问题。二、实例：线性表的顺序表示(顺序表)及操作实现。阅读下列程序请注意几个问题：(1)关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai,在 存储地址屮也是相邻的，既地址连续。不同的教材有不同的表示，我们采用含'动态分配 一维数组的结构体：typedef struct elemtype *elem;int length; int listsize;jsqlist; 定义顺序表的存储结构(2)本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序 存储表示的资料，供学生参考。【源程序】include <stdio.h>#incl

33、ude <malloc.h>#include <process.h>#define ok 1#define error 0#define overflow-1#define initsize 100#define increment 10预定义常量typedef int status; 定义状态结果类型 typedef int elemtype; 定义数据元素类型 typedef struct elemtype *elem;int length;int listsize;isqlist; 定义顺序表的存储结构status initlist(sqlist &l)/

34、构造一个空的顺序表l.l.elem=(elemtype*)malloc(initsize*sizeof(elemtype); if(!l.elem)exit(overflow);l.length=0;l.listsize=initsize;retum(ok);void assign(sqlist &l)为顺序表l的各元素赋值.int i, n;printf("please input the number of the sqlist:"); scanf(” d“,&n);printf("please in put the elements:*);f

35、or(i=0;i<n;i+) scanf(“d”,&l.elemi);l.l ength+;void listtraverse(sqlist l)/遍历顺序表l.int i;for(i=0;i<=l.length-l ;i+)printf(n%d n,l.elemi);printf(” n”);printf("the length is:%dn",l.length);void print(elemtype g) void listtraverse2(sqlist l,void (*vi)(elemtype) /遍历顺序表l的另一种方法.int i;ele

36、mtype *p;p=l.elem;for (i=o;i<=l.length-l ;i+)vi(*p+);printf(uthe length is:%dn'l.length);status getelem(sqlist l, int i, elemtype &e) /取顺序表l的笫i个元素的值，用e返冋.e=l.elemi-l;return ok;int listlength(sqlist l)求顺序表的长度return(l length);status listinsert(sqlist &l, int i, elemtype e) 在顺序表l的第i个元素前插

37、入元素e.elemtype *p,*q卢newbase;if(i< l|i>l.length+1 )return error;if(l.le ngth=listsize)newbase=(elemtype*)realloc(l.elem,(initsize+increment)*sizeof(elemtype);i f(! newbase)exit(overflow);l.elem=newbase;l.listsize+=increment;q二&l.elemfi-1;for(p 二&l.eleml.iength-l ;p>=q;-p)*(p+l)=*p;*q

38、=e;+l.length;return ok;void mergelist(sqlist lasqlist lb, sqlist &lc) 己知顺序表la和lb的元素按值非递减排列，归并la和lb得到新的顺序表lc,lc的元素也按值非递减排列.elemtype *pa,*pb,*pc,*pa_last,*pbast;pa=la.elem;pb=lb.elem;lc.listsize=lc.length=la.length+lb.length;pc=lc.elem=(elemtype*)malloc(lc.listsize*sizeof(elemtype);if(!lc.elem)exi

39、t(overflow);pa_last=la.elem+la.length-l;pbast=lb.elem+lb.length-1;while(pa<=pa_last&&pb<=pb_last)if(*pa<=*pb) *pc+=*pa+;else *pc+=*pb+;)while(pa<=pa_last) *pc+=*pa+;while(pb<=pb_last) *pc+=*pb+;void main()sqlist l,l1,l2;int i,j；初始化顺序表l 为l的元素赋值 遍历顺序表lelemtype e,f;if(initlist(l)

40、 printf("init successn");assign(l);listtraverse(l);/listtraverse2(l,print);printf(nplsese input the location i:h); scanf(”d“,&i);getelem(l,i,e);printf(uthe ith elem is: %dn",e);printf(hplease input the inserted elem's no. and the value:11); scanf("%d %d",&j,&

41、f);listinsert(l,j,f)；listtraverse(l);initlist(ll);assign(ll);listtraverse(ll);mergelist(l,l 1 ,l2);listtraverse(l2);三. 实验内容1. 线性表链式存储结构下基本操作的实现（初始化、赋值、取值、插入、删除、归并等）。2. 线性表合并运算两个数据元素按值非递减有序排列的线性表，要求将二者归并为一个新表，新表中的数 据元素仍按值非递减有序排列。要求分别采用顺序和链式两种存储结构3. 约瑟夫环问题【问题描述】设有n个人围坐一圈，现从某个人开始报数，数到m的人出列，接着从 11!列的下一个

42、人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。 试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺 序打印出各人的编号。【测试数据】n二#include "malloc.h"#include "stdio.h"#define max 100#define error 0#define ok 0 typedef int elemtype;typedef struct lnodeint num;elemtype data;struct ln ode *next;lnode;lnode *head,*this,

43、*new;int strmax;new_code(int a); delete_code(int a,int b); main()int m,n,i; printf("enter the first code (m):u); scanf(u%d",&m);printf("nenter the people number (n):"); scanf(”d”,&n);getchar(); printf(hnh); new_code(n); if(head!=null)delete_code(n,m);elseprintf("list

44、 is emptyn”)； exit(); for(i=0;ivn；i+) printf(h%-3dm,stri); printf(hnh);new_code(int a)int i=l;char numstr10;new=(lnode *)malloc(sizeof(lnode); if(new=null)return error;if(head=null)head 二 new; this=head;while(a!=0)this->num=i;printf(henter the %d code(data):'i);gets(numstr); this->data=ato

45、i(numstr);new=(lnode *)malloc(sizeof(lnode);this->next=new;this=new;i+；this->num=i;printf("enter the %d code(data):",i);gets(numstr);this->data=atoi(numstr);this->next=head;return ok;delete_code(int a,int b)int i;intj=o;lnode *p;while(a)!=1)fbr(i=l;i<=b;i+)p=this;this=this-&

46、gt;next;b=this->data;strj=this->num;p> next 二 this > next;free(this);j+；strj =this->next->num;return ok;测试结果当输入m=6, n=7,每个人所持密码一次为：3, 1, 7, 2, 4, 8, 4吋，则输出正 确的出列顺序为：6, 1, 4, 7, 2, 3, 5。实验二栈和队列一. 实验目的1. 深入了解栈和队列的定义和特性。2. 掌握栈和队列的数组表示、链表表示以及相应操作的实现，巩固对这两种结构的构造 方法的掌握。二、实例：队列的顺序存储结构（循环队

47、列）及操作实现。阅读下列程序请注意：该例程是标准c语言的程序。算法屮函数的引用参数全部转化 为指针来实现，这将有助同学们掌握在turbo c环境下将算法转化为程序的方法。【源程序】#include <stdio.h>include <stdlib. h>#define maxsi ze 20typedef int elemtype;typedef struct elemtype amaxsize;int front, rear;sqqueue;sqqueue qi;/*函数声明*/void init_q(sqqueue *q);void out q(sqqueue q)

48、;void enqueue(sqqueue *q, elemtypeelemtype dequeue(sqqueue *q);/*主函数*/maino int k; elemtype e, x; char ch;init_q( &q1) ;/*初始化一个空循环队列*/do printf("nnn");printf("nnprintf (，znnprintf("nnprintf ("n=printf (/zn 请输入您的选择(1,2,3)");scanf&k);switch(k) case 1: printf (z/n

49、进队 e二?”); scanf ("%d", &e);enqueue (sqqueue &q1, e); out_q(ql); break;case 2: x= dequeue(&q1);printf (z，n 出队元素:%d", x); out_q(ql ); break;case 3: exit(0); /* switch */*/*/*数组最人界限 数据元素类型*/*/一维数组子域/*头、尾指针子域/*循环队列的结构体类型1. 数据元素e进队列）；2. 出队一个元素，返回其值3. 结束程序运行“）；*/*/*/“);)；printf

50、(z/nwhile(k>=l && k<3);printf (n printf (''n /* main */再见！ “)；打冋车键，返回。;ch=getch();/*初始化空队列* / void init q(sqqueue *q) q->front=0; q->rear=0; /* init_q */*输出队列的内容*/void out_q(sqqueue q)(char ch; int i;/*不能修改队列头、尾指针*/if (q->front=q->rear) printf (''n queue is

51、null. ''); else i=(q->front+l)% maxsize;whi 1 e ( i! =q->rear) printf (''n data=%d,z, q->ai); i=(i+l)%maxsize; printf (''n data=%d, q->ai);printf (''n 打回车键，继续。;ch=getch(); /* out_q */ *进队函数*/voi d enqueue(sqqueue *q,elemtype e) if (q->rear+l)%maxstze=q-

52、>front) printf (''n queue is overflow!z,); else q->rear=(q->rear+l)% maxsize ;q->aq->rear=e;/* enqueue/*出队函数*/elemtype dequeue (sqqueue *q) elemtype x;if (q->frontq->rear) printf (''n queue is null!z,); x=-l;else q->front=（q->fronbh）% maxsize ;x=q->aq-&g

53、t;front;return（x）; /* dequeue */三、实验内容1. 栈的基本操作的实现（初始化、赋值、収值、插入、删除等），要求分别采用顺序和 链式存储结构。2. 写一个程序，将输入的十进制数据m转换为八进制数据m8,将其调试通过。在此 基础上修改程序，实现十进制数据m向n进制（2或8或16）的转换。（1）采用顺序存储结构实现栈。（2）采用链表结构实现栈。3. 括号匹配的检验【问题描述】假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（）或（ ）等为正确格式，（）或（均为不正确的格式。读入含圆括号和方括号的符号序 列，输出“匹配”或“此串括号匹配不合法"

54、。【测试数据】输入（）,结果“匹配”输入（），结果“此串括号匹配不合法"【选作内容】考虑增加大括号的情况。x实验目的1. 了解算术表达式的不同表示形式及相应算法实现的不同。2. 深入了解栈的特性，并在实际问题背景下灵活运用。3. 掌握字符串解释为表达式的意义和数字的转化。二、实验内容1算术表达式求值【问题描述】表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型的例子，设 计一个程序，演示用算符优先法对算术表达式求值的过程。【基本要求】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1 给出的算符优先关系，实现对算术四则混合运算表达式的求值。【测试数据】3*（7-1）； 1+2+3+4； 88-1*5； 1024/4*8； （20+2）*（6/2）； （6+2*（3+6）,【实现提示】（1）设置运算符栈和运算数栈辅助分析算符优先关系。（2）在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以 及相应的运算。（3）识别出运算数的同时，要将其字符序列形式转换成整数形式。（4）在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。【选做内容】（1）在实现整数四则运算的基础上，能够实现正浮点小数的四则运算，进而扩大到实 数范