《数据结构实验指导》

第１章 上机实验内容及指导

上机实验是对学生的一种全面综合训练，是与课堂讲授的内容相辅相成的必不可少的一个教学环节。通过上机实验，既可以加深对讲授内容的理解、深化，也可以培养学生的思维能力和创造精神。在上机实验时，千万不要在已给出的源程序通过运行后就认为完成任务了，而要在所给的例子的基础上，完成每章的课后习题。

上机实验一般包括以下几个步骤：

（1）准备好上机所需的程序。为提高上机效率，上机前应认真检查手编程序，以减少错误率。

（2）上机输入和调试自己所编的程序。上机过程中，应该善于分析判断，尽量独立去处理出现的问题，这是提高调试程序能力的良好机会。

（3）程序调试通过后，要记录程序在不同条件下的运行结果，为实验报告作准备。

（4）上机结束后，要及时整理出实验报告。实验报告除了在开头写上班级、姓名、学号和完成日期外，还应该包括以下内容：

①实验题目 ②实验内容 ③程序构思 ④程序清单 ⑤运行结果

最后，在每次上机后，自己应该对程序的运行情况作一下分析，总结本次上机调试程序所取得的经验。若程序未能通过，应分析其原因。

- 1 -

第2章 线性表

实验一 线性表的顺序存储结构

一、实验目的

通过本次实验，掌握线性表的顺序存储结构的基本操作及线性表存储结构所适用的范围。

二、实验内容与要求

(一)认真复习线性表顺序存储结构方面的知识，完成本实验的内容。 (二)实验内容为教材例2-1：假设利用两个线性表LA和LB分别表示两个集合A和B（即线性中的数据元素即为集合中的成员），现要求一个新的集合A=A∪B。

三、程序构思

从题意的要求可知，对线性表应作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中进行查访，若不存在，则插入之。

四、程序源代码

/* c1.h (程序名) */ #include #include

#include /* malloc()等 */ #include /* INT_MAX等 */

#include /* EOF(=^Z或F6),NULL */ #include /* atoi() */ #include /* eof() */

#include /* floor(),ceil(),abs() */ #include /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1

/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故

- 2 -

去掉此行 */

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

/* c2-1.h 线性表的动态分配顺序存储结构 */

#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */ typedef struct {

ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */

int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList;

/* bo2-1.c 顺序表示的线性表(存储结构由c2-1.h定义)的基本操作(12个) */

Status InitList(SqList *L) /* 算法2.3 */ { /* 操作结果：构造一个空的顺序线性表 */

(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!(*L).elem)

exit(OVERFLOW); /* 存储分配失败 */ (*L).length=0; /* 空表长度为0 */

(*L).listsize=LIST_INIT_SIZE; /* 初始存储容量 */ return OK; }

Status DestroyList(SqList *L)

{ /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */ free((*L).elem); (*L).elem=NULL; (*L).length=0; (*L).listsize=0; return OK; }

- 3 -

Status ClearList(SqList *L)

{ /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */ (*L).length=0; return OK; }

Status ListEmpty(SqList L)

{ /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */ if(L.length==0) return TRUE; else

return FALSE; }

int ListLength(SqList L)

{ /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */

return L.length; }

Status GetElem(SqList L,int i,ElemType *e)

{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值 */ if(i<1||i>L.length) exit(ERROR); *e=*(L.elem+i-1); return OK; }

int LocateElem(SqList L,ElemType e,Status(*compare)

(ElemType,ElemType))

{ /* 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1,否则为0) */

/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */

/*若这样的数据元素不存在，则返回值为0。算法2.6 */

- 4 -

ElemType *p;

int i=1; /* i的初值为第1个元素的位序 */ p=L.elem; /* p的初值为第1个元素的存储位置 */ while(i<=L.length&&!compare(*p++,e)) ++i;

if(i<=L.length) return i; else

return 0; }

Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e) { /* 初始条件：顺序线性表L已存在 */

/* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */

/* 否则操作失败，pre_e无定义 */ int i=2;

ElemType *p=L.elem+1;

while(i<=L.length&&*p!=cur_e) {

p++; i++; }

if(i>L.length)

return INFEASIBLE; else {

*pre_e=*--p; return OK; } }

Status NextElem(SqList L,ElemType cur_e,ElemType *next_e) { /* 初始条件：顺序线性表L已存在 */ /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */

/* 否则操作失败，next_e无定义 */

- 5 -

int i=1;

ElemType *p=L.elem;

while(i

i++; p++; }

if(i==L.length)

return INFEASIBLE; else {

*next_e=*++p; return OK; } }

Status ListInsert(SqList *L,int i,ElemType e) /* 算法2.4 */ { /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 */ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */

ElemType *newbase,*q,*p;

if(i<1||i>(*L).length+1) /* i值不合法 */ return ERROR;

if((*L).length>=(*L).listsize) /* 当前存储空间已满,增加分配 */ {

newbase=(ElemType

*)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)

exit(OVERFLOW); /* 存储分配失败 */ (*L).elem=newbase; /* 新基址 */

(*L).listsize+=LISTINCREMENT; /* 增加存储容量 */ }

q=(*L).elem+i-1; /* q为插入位置 */

for(p=(*L).elem+(*L).length-1;p>=q;--p) /* 插入位置及之后的元素右移 */

- 6 -

*(p+1)=*p;

*q=e; /* 插入e */ ++(*L).length; /* 表长增1 */ return OK; }

Status ListDelete(SqList *L,int i,ElemType *e) /* 算法2.5 */ { /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */

/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */

ElemType *p,*q;

if(i<1||i>(*L).length) /* i值不合法 */ return ERROR;

p=(*L).elem+i-1; /* p为被删除元素的位置 */ *e=*p; /* 被删除元素的值赋给e */ q=(*L).elem+(*L).length-1; /* 表尾元素的位置 */

for(++p;p<=q;++p) /* 被删除元素之后的元素左移 */ *(p-1)=*p;

(*L).length--; /* 表长减1 */ return OK; }

Status ListTraverse(SqList L,void(*vi)(ElemType*)) { /* 初始条件：顺序线性表L已存在 */ /* 操作结果：依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败 */

/* vi()的形参加'&'，表明可通过调用vi()改变元素的值 */ ElemType *p; int i; p=L.elem;

for(i=1;i<=L.length;i++) vi(p++); printf(\ return OK; }

/*algo2-1.c 实现算法2.1的程序 */

- 7 -

#include\

typedef int ElemType;

#include\采用线性表的动态分配顺序存储结构 */ #include\可以使用bo2-1.c中的基本操作 */

Status equal(ElemType c1,ElemType c2) { /* 判断是否相等的函数，Union()用到 */ if(c1==c2) return TRUE; else

return FALSE; }

void Union(SqList *La,SqList Lb) /* 算法2.1 */

{ /* 将所有在线性表Lb中但不在La中的数据元素插入到La中 */ ElemType e;

int La_len,Lb_len; int i;

La_len=ListLength(*La); /* 求线性表的长度 */ Lb_len=ListLength(Lb); for(i=1;i<=Lb_len;i++) {

GetElem(Lb,i,&e); /* 取Lb中第i个数据元素赋给e */ if(!LocateElem(*La,e,equal)) /* La中不存在和e相同的元素,则插入之 */

ListInsert(La,++La_len,e); } }

void print(ElemType *c) {

printf(\ }

void main() {

SqList La,Lb;

- 8 -

Status i; int j;

i=InitList(&La);

if(i==1) /* 创建空表La成功 */

for(j=1;j<=5;j++) /* 在表La中插入5个元素 */ i=ListInsert(&La,j,j);

printf(\输出表La的内容 */ ListTraverse(La,print);

InitList(&Lb); /* 也可不判断是否创建成功 */ for(j=1;j<=5;j++) /* 在表Lb中插入5个元素 */ i=ListInsert(&Lb,j,2*j);

printf(\输出表Lb的内容 */ ListTraverse(Lb,print); Union(&La,Lb);

printf(\输出新表La的内容 */ ListTraverse(La,print); }

程序运行结果： La=1 2 3 4 5 Lb=2 4 6 8 10

new La=1 2 3 4 5 6 8 10

实验二 线性表的链式存储结构

一、实验目的：

通过本实验，掌握线性表链式存储结构的特点及与线性表顺序存储结构的区别。

二、实验内容与要求

(一)认真复习线性表链式存储结构方面的知识，并采用链表结构完成本实验。

(二)实验内容为教材例2-2：已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减排列。例如，设LA=（3，5，8，11，LB=（2，6，8，9，11，15，20）则LC=（2，3，5，6，8，8，9，11，11，15，20）。

三、程序构思

LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。

- 9 -

四、程序源代码

/* c2-2.h 线性表的单链表存储结构 */ struct LNode {

ElemType data;

struct LNode *next; };

typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */ /* bo2-2.c 单链表线性表(存储结构由c2-2.h定义)的基本操作(12个) */ Status InitList(LinkList *L)

{ /* 操作结果：构造一个空的线性表L */

*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */

if(!*L) /* 存储分配失败 */ exit(OVERFLOW);

(*L)->next=NULL; /* 指针域为空 */ return OK; }

Status DestroyList(LinkList *L)

{ /* 初始条件：线性表L已存在。操作结果：销毁线性表L */ LinkList q; while(*L) {

q=(*L)->next; free(*L); *L=q; }

return OK; }

Status ClearList(LinkList L) /* 不改变L */

{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */ LinkList p,q;

p=L->next; /* p指向第一个结点 */ while(p) /* 没到表尾 */ {

- 10 -

}

while(i<=La_len) /* 表La非空且表Lb空 */ {

GetElem(La,i++,&ai); ListInsert(*Lc,++k,ai); }

while(j<=Lb_len) /* 表Lb非空且表La空 */ {

GetElem(Lb,j++,&bj); ListInsert(*Lc,++k,bj); } }

void print(ElemType c) {

printf(\ }

void main() {

LinkList La,Lb,Lc;

int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20}; InitList(&La); /* 创建空表La */

for(j=1;j<=4;j++) /* 在表La中插入4个元素 */ ListInsert(La,j,a[j-1]);

printf(\输出表La的内容 */ ListTraverse(La,print);

InitList(&Lb); /* 创建空表Lb */

for(j=1;j<=7;j++) /* 在表Lb中插入7个元素 */ ListInsert(Lb,j,b[j-1]);

printf(\输出表Lb的内容 */ ListTraverse(Lb,print); MergeList(La,Lb,&Lc);

printf(\输出表Lc的内容 */ ListTraverse(Lc,print); }

程序运行结果为：

- 16 -

La= 3 5 8 11

Lb= 2 6 8 9 11 15 20

Lc= 2 3 5 6 8 8 9 11 11 15 20

实验三 链表的应用——单链表的反转

一、实验目的

通过本实验，利用掌握的线性表的链式存储结构的基本操作及特点，熟练运用单链表进行程序设计。

二、实验内容与要求

利用线性表链式存储结构设计一个单链表的反转程序。 如：原链表为：

HEAD ? NULL 1 2 8 9

链表反转后为：

NULL HEAD 1 2 8 9

三、程序构思

1、 建立链表

2、 从第一个结点开始为Back结点，Back结点的下一个结点为

Pointer结点，Pointer结点的下一个结点为Next，若Back结点是首结点，则将Back结点的指针设为NULL，将Pointer结点的指针指向Back

3、 使Back,Pointer结点依次向后移，再重复第2步，直到Pointer

结点的指针为NULL为止。

四、程序源代码

#include #define Max 10

struct List /*结点结构声明*/ {

int Number; int Total;

- 17 -

struct List *Next; };

typedef struct List Node; typedef Node *Link;

int Data[2][Max]= /*输入数据*/

{1，3，5，7，2，4，6，8，9，10，

15，35，10，67，25，65，38，70，30，20};

/*反转链表*/

Link Invert_List(Link Head) {

Link Pointer; /*结点声明*/ Link Back; /*上一个结点*/ Link Next; /*下一个结点*/

Back=Head; /*Back指向首结点*/ Pointer=Back->Next; Back->Next=NULL;

Next=Pointer->Next; Pointer->Next=Back; Back=Pointer; Pointer=Next;

while(Pointer->Next!=NULL) /*当到达链表尾端时,结束循环*/ {

Next=Pointer->Next; Pointer->Next=Back; Back=Pointer; Pointer=Next; }

Pointer->Next=Back; Head=Pointer; return Head; }

/*输出链表数据*/

- 18 -

void Print_List(Link Head) {

Link Pointer; /*结点声明*/

Pointer=Head; /*Pointer指针设为首结点*/ while(Pointer!=NULL) /*当结点为NULL结束循环*/ {

printf(“[%d,%d]”,Pointer->Number,Pointer->Total); Pointer=Pointer->Next; /*往下一个结点*/ }

printf(“\\n”); }

/*释放链表*/

void Free_List(Link Head) {

Link Pointer; while(Head!=NULL) {

Pointer=Head; Head=Head->Next; free(Pointer); } }

/*建立链表*/

Link Create_List(Link Head) {

Link New; Link Pointer; int i;

Head=(Link)malloc(sizeof(Node)); /*内存分配*/ if(Head==NULL) /*分配失败*/ printf(“Memory allocate Failure!!\\n”); else {

Head->Number=Data[0][0]; /*定义首结点数据编号*/ Head->Total=Data[1][0];

- 19 -

Head->Next=NULL; Pointer=Head;

for(i=1;i

New=(Link)malloc(sizeof(Node)); New->Number=Data[0][i]; New->Total=Data[1][i]; New->Next=NULL;

Pointer->Next=New; /*将新结点串连在原链表尾端*/ Pointer=New; /*链表尾端结点为新结点*/ } }

return Head; }

/*主程序*/ void main( ) {

Link Head;

Head=Create_List(Head); if(Head!=NULL) {

printf(“Input Data:\\n”); Print_List(Head);

Head=Invert_List(Head); printf(“After Invert:\\n”); Print_List(Head); Free_List(Head); } }

程序运行结果: Input Data:

[1,15][3,35][5,10][7,67][2,25][4,65][6,38][8,70][9,30][10,20] [10,20][9,30][8,70][6,38][4,65][2,25][7,67][5,10][3,35][1,15]

- 20 -

子串s2为：CD12345

从串t的第pos个字符起，删除len个字符，请输入pos,len：4,4 删除后的串t为：ABC456

在串s2的第3个字符之前插入串t后，串s2为： CDABC45612345

s2的第3个字母起和t第一次匹配 串t为:C 串s1为：CC

用串s1取代串s2中和串t相同的不重叠的串后，串s2为：CCDABCC45612345

实验二 串的应用—字符串的比较

一、实验目的

通过本实验，熟练串结构的基本操作

二、实验内容与要求

在给定的的原始字符串中进行字符的比较，以判断某特定字符串是否存在该原始字符串中，若存在则此特定的字符串为原始字符串的子字符串。

三、程序构思

如：寻找的特定字符串为is

原始字符串为Thomas is smart

首先在原始字符串中找所要寻找的特定字符串is的第一个字符i在原始字符串中出现的第一个位置，找到后，接着将特定字符串的第2个字符s和在原始字符串中找的i字符出现的第一个位置的下一字符进行比较，如果相同，则找到，否则再在原始字符串中找i出现的第二个位置，接着找s，如此反复，直到原始字符串中所剩字符个数小于特定字符的长度。

四、程序源代码

/*计算字符串的长度*/ int strlen(char *s) {

int i;

for(i=0;s[i]!=’\\0’;) i++; return i; }

/*进行字符串的比较，判断是否存在某特定字符串*/ int strstr(char *s1,char *s2)

- 46 -

{

int i,j,endposition;

endposition=strlen(s1)-strlen(s2); if(endposition>0) {

for(i=0;i<=endposition;i++) {

for(j=i;s1[j]= =s2[j-i];j++)

{

if(s2[j-i+1]==’\\0’) return i+1; } } }

return -1; }

/*主程序*/ void main() {

char string[100]; char substring[100]; int final_result;

printf(“\\nplease input string:”); gets(string);

printf(“\\nplease input the finding substring:”); gets(substring);

final_result=strstr(string,substring); if(final_result>0)

printf(“the start position of substring ‘%s’ is[%d]\\n”,substring,final_result);

else

printf(“the substring ‘%s’ is not in the string”,substring); }

程序运行结果：

please input string:This is a good book. Please input the finding substring:good

The start position of substing ‘good’ is [11]

- 47 -

本章习题

1．编写下列算法（假定下面所用的串均采用顺序存储方式，参数ch、ch1、ch2均为字符型）：

a) 将串r中所有其值为ch1的字符换成ch2的字符。 b) 将串r中所有字符按照相反的次序仍存放在r中。 c) 从串r中删除其值等于ch的所有字符。

d) 从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。

e) 从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数和第（3）小题的删除子串的函数）。

本题的算法思想是：从头到尾扫描r串，对于值ch1的元素直接替换成ch2即可。

2．若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

本题的算法思想是：两个串相等表示对应的字符必须相同所以扫描两串，逐一比较相应位置的字符，若相同继续比较直到全部比较完毕，如果都相同则表示两串相等，否则表示两串不相等。

3．采用顺序结构存储串s，编写一个函数删除s中第i个字符开始的j个字符。

本题的算法思想是：先判定s串中要删除的内容是否存在，若存在则将第i+j-1之后的字符前移j个位置。

4．采用顺序存储方式存储串，编写一个函数将串s1中的第i个字符到第j个字符之间的字符（不包括第i个和第j个字符）用s2串替换，函数名stuff(s1,i,j,s2)。例如：stuff(?abcd?,1,3,?xyz?)返回?axyzcd?。

本题算法思想是：先提取s1的前i个字符str1,s2,str2连连接起来便构成了结果串。

5．采用顺序结构存储串，编写一个函数substring(s1,s2),用于判定s2是否是s1的子串。

本题的算法思想是：设s1=?a0a1…am?，s2=?b0b1…bn?，从s1中找与b0匹配的字符ai,若ai=b0,则判定ai+1=b1,…,ai+n=bn,若都相等，则结果是子串，否则继续比较ai之后的字符。

6．采用顺序结构存储串，编写一个函数计算一个子串在一个字符串中出现的次数，如果孩子串不出现则为0。

7．若h是采用单链表存储的串，编写一个函数将其中所有的c替换成s字符。

本题采用的算法是：逐一扫描x的每个结点，对于每个数据域c的结

- 48 -

点修改其元素值为s。

8． x和y是两个单链表存储的串，编写弄虚作假函数找出x中第一个在y中出现的字符。

本题的算法思想是：从头到尾扫描x,对于x的每个结点c,判定是否在y中，若在，则继续扫描x;若不在，则给出该c并返回。

- 49 -

第5章 数组和广义表

实验一 数组的顺序表示

一、实验目的：

通过本次实验，掌握如何实现对数组顺序表示的实现。

二、实验内容与要求

(一)了解数组的两种存储表示方法，并掌握数组的顺序存储结构及其基本操作。

(二)实验内容：数组的定长顺序存储。

三、程序构思

数组的表示法可分为：以行为主和以列为主两种。以行为主为每一行排完后再排下一行，依序将每一行排入空间中。

四、程序源代码

/* c5-1.h 数组的顺序存储表示 */ #include /*标准头文件，提供宏va_start，va_arg和va_end */

/* 用于存取变长参数表 */

#define MAX_ARRAY_DIM 8/* 假设数组维数的最大值为8 */ typedef struct {

ElemType *base; /* 数组元素基址，由InitArray分配 */ int dim; /* 数组维数 */

int *bounds; /* 数组维界基址，由InitArray分配 */ int *constants; /*数组映象函数常量基址,由InitArray分配*/ }Array;

/* bo5-1.c 顺序存储数组(存储结构由c5-1.h定义)的基本操作(5个) */ Status InitArray(Array *A,int dim,...)

{ /* 若维数dim和各维长度合法，则构造相应的数组A，并返回OK */ int elemtotal=1,i; /* elemtotal是元素总值 */ va_list ap;

if(dim<1||dim>MAX_ARRAY_DIM) return ERROR; (*A).dim=dim;

(*A).bounds=(int *)malloc(dim*sizeof(int));

- 50 -

本章习题

1.已知一个向量A，其中的元素按值非递减有序排列，编写一个函数插入一个元素X后保持该向量仍按递减有序排列。

本题的算法思想是：先找到适当的位置，然后后移元素空出一个位置，再将 X 插入，并返回向量的新长度。

2.已知一个向量中的元素按元素值非递减有序排列，编写一个函数删除向量中多余的值相同的元素。

本题的算法思想是：由于向量中的元素按元素值非递减有序排序，值同的元素必为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，最后返回向量的新长度。

3.编写一个函数将一个向量A（有n个元素且任何元素均不为0）分拆成两个向量，使A中大于0的元素存放在 B 中，小于0 的元素存放在C中。

本题的算法思想是：依次遍历 A 的元素，比较当前的元素值，大于0者赋给 B（假设p个元素），小于0者赋给 C（假设q个元素）。

4.已知在一维数组A[1，m+n]中依次存放着两个向量（a1,a2,…,am）和(b1,b2,…,bn),编写一个函数将两个向量的位置互换，即把（b1,b2,…,bn）放到(a1,a2,…,am)的前面。

本题的算法思想是：由于向量的插入与删除操作需要大量的元素移动，所用时间多，这里采用先将：

A：（a1,a2,…am,b1,b2,…,bn）

的所有元素逆置，即使之变成：

A（bn,…,b2,b1,am,…,a2,a1）

然后将（bn,…,b2,b1）逆置为（b1,b2,…,bn）,将（am,…,a2,a1）逆置为（a1,a2,…am）,这样得到最终结果：

A（b1,b2,…,bn,a1,a2,…,am）

5.有两个向量A（有m个元素）和（有n个元素），其元素均以从小到大的升序排列，编写一个函数将它们合并成一个向量C，要求C 的元素也是从小到大的升序排列。

本题的算法思想是：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个向量扫描完毕，然后将末完的一个向量的余下的所有元素赋给C即可。

- 21 -

第3章 栈和队列

实验一 堆栈数据的存取

一、实验目的：

通过本次实验，掌握栈的应用，了解栈的特点及适用范围。

二、实验内容与要求

(一)认真复习栈的基本概念与基本操作。

(二)本次实验内容：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

三、程序构思

按照十进制数和八进制数的转换方法，转换过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。

四、程序源代码

/* c3-1.h 栈的顺序存储表示 */

#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */ #define STACKINCREMENT 2 /* 存储空间分配增量 */ typedef struct SqStack {

SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针 */

int stacksize; /* 当前已分配的存储空间，以元素为单位 */ }SqStack; /* 顺序栈 */

/* bo3-1.c 顺序栈（存储结构由c3-1.h定义）的基本操作（9个） */ Status InitStack(SqStack *S) { /* 构造一个空栈S */

(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base)

exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base;

(*S).stacksize=STACK_INIT_SIZE; return OK; }

- 22 -

Status DestroyStack(SqStack *S) { /* 销毁栈S，S不再存在 */ free((*S).base); (*S).base=NULL; (*S).top=NULL; (*S).stacksize=0; return OK; }

Status ClearStack(SqStack *S) { /* 把S置为空栈 */ (*S).top=(*S).base; return OK; }

Status StackEmpty(SqStack S)

{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top==S.base) return TRUE; else

return FALSE; }

int StackLength(SqStack S)

{ /* 返回S的元素个数，即栈的长度 */ return S.top-S.base; }

Status GetTop(SqStack S,SElemType *e) { /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ if(S.top>S.base) {

*e=*(S.top-1); return OK; } else

- 23 -

return ERROR; }

Status Push(SqStack *S,SElemType e) { /* 插入元素e为新的栈顶元素 */

if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */ {

(*S).base=(SElemType*)realloc((*S).base,

((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!(*S).base)

exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; }

*((*S).top)++=e; return OK; }

Status Pop(SqStack *S,SElemType *e) { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */

if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; }

Status StackTraverse(SqStack S,Status(*visit)(SElemType)) { /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 */ /* 一旦visit()失败，则操作失败 */ while(S.top>S.base) visit(*S.base++); printf(\ return OK; }

/* algo3-1.c 调用算法3.1的程序 */

typedef int SElemType; /* 定义栈元素类型为整型 */

- 24 -

#include\

#include\采用顺序栈 */

#include\利用顺序栈的基本操作 */

void conversion() /* 算法3.1 */

{/* 对于输入的任意一个非负十进制整数，输出与其等值的八进制数*/ SqStack s;

unsigned n; /* SElemType e;

InitStack(&s); /* printf(\

scanf(\ while(n) /* {

Push(&s,n%8); /* n=n/8; }

while(!StackEmpty(s)) /* {

Pop(&s,&e); /* printf(\ }

printf(\ }

void main() {

conversion(); }

程序运行结果： n(>=0)= 95 137

非负整数 */ 初始化栈 */ 输入非负十进制整数n */ 当n不等于0 */ 入栈n除以8的余数(8进制的低位) */ 当栈不空 */ 弹出栈顶元素且赋值给e */ 输出e */

- 25 -

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