数据结构实验指导书

温州大学瓯江学院

WENZHOU UNIVERSITY OUJIANG COLLEGE

实 验 指 导 书

专 业 课 程

计算机科学与技术

数据结构

数据结构实验指导书

温州大学瓯江学院信息与电子工程分院 谢胜利编

第1部分 上机实验要求及规范

数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。在上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体实习步骤如下：

1．1问题分析与系统结构设计

充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？）。然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。

1．2详细设计和编码

详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。

编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。

1．3上机准备

熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。

1．4上机调试程序

调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。

1．5整理实习报告

在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析。写出实验报告。

一、实验报告的基本要求：

一般性、较小规模的上机实验题，必须遵循下列要求。养成良好的习惯。

（1） 实验名称

（2） 实验内容和目的

（3） 数据结构和算法设计思想 （4） 测试数据，运行结果，体会 （5） 程序清单（带有必要的注释）

实验者必须重视这一环节，否则等同于没有完成实验任务。这里可以体现个人特色、或创造性思维。具体内容包括：测试数据与运行记录；调试中遇到的主要问题，自己是如何解决的；经验和体会等。

二、实验报告的提高要求：

阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。

（1）实验名称 （2）实验内容目的 （3）概要设计

说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系。 （4）详细设计

a. 设计思想：存储结构（题目中限定的要描述）；主要算法基本思想。

b. 设计表示：每个函数的头和规格说明；列出每个函数所调用和被调用的函数，也

可以通过调用关系图表达。

c. 实现注释：各项功能的实现程度、在完成基本要求的基础上还有什么功能。 （5）用户手册：即使用说明。

（6）调试报告：调试过程中遇到的主要问题是如何解决的；设计的回顾、讨论和分析；

时间复杂度、空间复杂度分析；改进设想；经验和体会等。 （7）程序清单（带有必要的注释）

第2部分 数据结构实验

实验一 复数ADT及其实现 一、实验目的

1. 了解抽象数据类型（ADT）的基本概念，及描述方法。

2. 通过对复数抽象数据类型ADT的实现，熟悉C语言语法及程序设计。为以后章节的学习打下基础。

二、实验内容和要求：

1、定义一个表示复数的抽象数据类型； 2、编写函数，输入实部和虚部建立一个复数； 3、编写函数，求两个复数的和； 4、编写函数，求两个复数的积；

5、编写两个函数，分别求复数的实部和虚部。

三、实验分析

1. 复数抽象数据类型ADT的描述及实现。 [复数ADT的描述] ADT complex{

数据对象：D={ c1,c2 | c1,c2∈FloatSet } 数据关系：R={ | c1 c2 }

基本操作：创建一个复数 create_complex();

求两个复数相加之和 add_complex(com1, com2); 求两个复数相减之差 sub_complex(com1, com2); 求两个复数相乘之积 mul_complex(com1, com2); 等等; } ADT complex; 2. 复数结构定义

typedef struct /*定义数据结构*/ {

float real; float image; }complex;

3. 几个复数的基本操作

complex create_complex() /*创建一个复数 */ {

complex com; /*定义一个复数 */

printf(\输出提示信息：输入实部和虚部 */ scanf(\输入复数的实虚部 */ return com; }

complex add_complex(complex com1,complex com2) /*函数定义：两个复数相加*/ {

complex addcom; /*定义一个两复数为相加后的复数 */ addcom.real=com1.real+com2.real; addcom.image=com1.image+com2.image; return addcom; }

complex mul_complex(complex com1,complex com2) /*函数定义：两个复数相乘 */ {

complex mulcom; /*定义一个两复数为乘积后的复数 */ mulcom.real=com1.real*com2.real-com1.image*com2.image; mulcom.image=com1.real*com2.image+com1.image*com2.real; return mulcom; }

complex div_complex(complex com1,complex com2) /*函数定义：两个复数相除 */ {

complex divcom; /*定义一个两复数相除后的复数*/

divcom.real=(com1.real*com2.real+com1.image*com2.image)/(com2.real*com2.real+ com2.image*com2.image);

divcom.image=(com1.image*com2.real-com1.real*com2.image)/(com2.real*com2.real +com2.image*com2.image);/*由公式可知 */ return divcom; }

float real_complex(complex com) /*对复数求实部 */ {

return com.real; }

float image_complex(complex com) /*对复数求虚部 */ {

return com.image; }

main() {

complex com1,com2,addcom,mulcom,divcom;

com1=create_complex(); /*调用创建复数函数 */

printf(\ com2=create_complex();/*调用创建复数函数 */

printf(\ addcom=add_complex(com1,com2);/*调用复数相加函数*/

printf(\ mulcom=mul_complex(com1,com2);/*调用复数相乘函数 */

printf(\ divcom=div_complex(com1,com2);/*调用复数相除函数 */

printf(\

printf(\输出实部 */ printf(\输出虚部 */ }

四、思考题

2n编写算法，一元多项式Pn(x)?a0?a1x?a2x?...?anx的值。请分析算法的时间复

杂度，要求时间复杂度尽可能小。

实验二 顺序表的基本操作

一、实验目的

1、掌握线性表的基本运算；

2、掌握顺序存储的概念，学会对顺序存储数据结构进行操作；

3、加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能力。

二、实验内容和要求：

1、编写函数，创建一个顺序表（数据自拟）；

2、编写函数，在顺序表的指定位置插入一个元素； 3、编写函数，在顺序表的指定位置删除一个元素；

4、编写函数，将两个有序顺序表合并成一个新的有序顺序表；

三、实验分析

1. 线性表的顺序存储表示（结构）及实现。

阅读下列程序请注意几个问题：

（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含‘静态’一维数组和线性表长的结构体： typedef int ElemType;

typedef struct{

ElemType elem[MAXSIZE]; int length;

}SqList; /* 顺序存储的结构体类型 */

（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段，并不强要求学生一定使用“菜单设计”技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复数处理程序中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。 [源程序]

#include \#include \#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType; typedef struct{

ElemType elem[MAXSIZE]; int length; }SqList;

Status InitList_Sq(SqList *L){ L->length=0; return OK; } /*InitList_Sq */

Status ListEmpty(SqList L)

{ if(L.length ==0) /*可以用一句语句代替 return (L.lenght==0);*/ return TRUE; else

return FALSE; }

int ListLength(SqList L) { return L.length; }

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

if (i<1 || i>L.length ) return ERROR; *e=L.elem[i-1]; return OK; }

int LocateElem(SqList L,ElemType e ) { int i;

for (i=1;i<=L.length;i++)

if(L.elem[i-1]==e) return (i); return 0; }

Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e) { int pos=0,i;

for(i=1;i

if(L.elem[i-1]== cur_e ) { pos=i-1;break;} if(pos<=0 ) return ERROR;

/*如果pos==-1表示找不到，如果pos==0表示处于第１个位置，所以没有前驱 )*/ *pre_e=L.elem[pos-1]; /*请思考如果没有变量pos怎么办*/ return 1; }

Status ListInsert(SqList *L,int i,ElemType e) /*插入 在ai和ai-1间插入 */

/* 原表 （a1,a2,??，ai-1,ai,ai+1,??,an） */ /* 新表 （a1,a2,??，ai-1,b,ai,ai+1,??,an） */ /* 长度+1 */ { int j;

if(i<1 || i>L->length+1 || L->length==MAXSIZE )return ERROR; for(j=L->length;j>=i;j--) L->elem[j]=L->elem[j-1]; L->elem[i-1]=e;

L->length=L->length+1; return OK; }

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

/*删除第i 个元素ai */ { int j;

if (i<1 ||i>L->length ) return ERROR; *e=L->elem[i-1];

for(j=i;jlength;j++) L->elem[j-1]=L->elem[j];

L->length=L->length-1; return OK; }

Status MergeList_Sq(SqList La,SqList Lb,SqList *Lc ) { /*两个有序表的合并 */ int i,j,k;

ElemType ai,bj; int la_len,lb_len;

if(La.length+Lb.length>LIST_INIT_SIZE ) return ERROR; i=j=1;k=1;

la_len=La.length;lb_len=Lb.length; while(i<=la_len && j<=lb_len ) {

GetElem(La,i,&ai); GetElem(Lb,j,&bj) ; if( ai<=bj )

{ ListInsert(Lc,k,ai );i++;} else

{ListInsert(Lc,k,bj);j++; } k++; }

while(i<=la_len)

{ GetElem(La,i++,&ai);ListInsert(Lc,k++,ai);} while(j<=lb_len)

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

Status CreateList_Sq(SqList *pL,int n) { ElemType x; int i;

for(i=1;i<=n;i++) { scanf(\ListInsert(pL,i,x); } }

void ListTraverse_Sq(SqList L) {int i;

for( i=1;i<=L.length;i++) printf(\printf(\}

main()

{SqList la,lb,lc; int na=3,nb=5;

InitList_Sq(&la);InitList_Sq(&lb);InitList_Sq(&lc); int i,k,loc; ElemType e,x; char ch; do { printf(\

printf(\建立线性表 \

printf(\在i位置插入元素e\

printf(\删除第i个元素，返回其值\ printf(\查找值为 e 的元素\ printf(\两个有序表的合并\ printf(\结束程序运行\

printf(\ printf(\请输入您的选择（1，2，3，4，5，6）\ scanf(\ switch(k)

{ case 1:{ CreateList_Sq(&la,na); /*建立na个结点的顺序表 */ ListTraverse_Sq(la); } break;

case 2:{ printf(\ ListInsert(&la,i,e); ListTraverse_Sq(la); } break;

case 3:{ printf(\

ListDelete(&la,i,&x); ListTraverse_Sq(la); printf(\ } break;

case 4:{ printf(\ loc=LocateElem(la,e);

if (loc==0) printf(\未找到 %d\

else printf(\已找到，元素位置是 %d\ } break;

case 5:{CreateList_Sq(&la,na); /*建立na个结点的顺序表 */

ListTraverse_Sq(la);/*编历顺序表，打印输出 */ CreateList_Sq(&lb,nb);/*建立nb个结点的顺序表 */ ListTraverse_Sq(lb);/*打印输出 */ MergeList_Sq(la,lb,&lc);/*全并到lc */ ListTraverse_Sq(lc);/*打印输出lc */ }break; } /* switch */ }while(k!=6);

printf(\再见！\

printf(\打回车键，返回。\ }

四、思考题

1. 用有序顺序表来表示集合，分别编写算法求两个集合的交集和并集。

2. 用顺序存储表示（数组）实现约瑟夫环问题。

实验三 链表的基本操作及其应用

一、实习目的

1、掌握链表的概念，学会对链表进行操作；

2、加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力；

二、实验内容与要求

1. 2. 3. 4. 5.

编写函数，创建一个带头结点的单链表（数据自拟）； 编写函数，在单链表的指定位置插入一个元素； 编写函数，在单链表的指定位置删除一个元素；

编写函数，将两个有序链表合并成一个新的有序链表； 编写程序，完成约瑟夫环的求解。

三、实验分析

1. 线性表的链表存储表示（结构）及实现。 阅读下列程序请注意几个问题：

（1）关于线性表的链表存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中可以不相邻,既地址不连续。不同的教材的表示基本是一致的。 typedef struct LNode

{ ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */

}LNode，LinkList; /* 结点结构类型 和指针类型 */

（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供关于链表操作的资料，供学生参考。可以看到本程序的main()与前一程序的main()函数的结构十分相似。稍加改动还可为其他题目的源程序所用。 [源程序]

#include \#include \#include \#define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType; struct LNode {

ElemType data;

struct LNode *next; };

Status InitList(struct LNode **L) {

struct LNode *p;

p=(struct LNode *)malloc(sizeof(struct LNode)); if(!p) return ERROR; p->data=0; L p->next=NULL; ∧ *L=p;

return OK;

} /*InitList_Link */

Status ListEmpty(struct LNode *L) { if(L->next==NULL) return OK; else

return ERROR; }

int ListLength(struct LNode *L) { int len=0;

struct LNode *p; p=L;

while(!p->next) {

len++; p=p->next; }

return len;

}

Status GetElem(struct LNode *L,int i,ElemType *e) {

struct LNode *p; int j; p=L->next;

j=1; /*p指向第一个结点,j为计数器*/ while(p && j

p=p->next; ++j; }

if (!p|| j>i ) return ERROR; *e=p->data; return OK; }

int LocateElem(struct LNode *L,ElemType e ) { int i=1;

struct LNode *p; p=L->next;

while(p && p->data!=e) {

i++;

p=p->next; }

if(!p)

return(0); else

return(i); }

Status ListInsert(struct LNode **L,int i,ElemType e) { /*在带表头的单链表中在第i个位置插入元素e*/ struct LNode * p,*s; int j;

p=*L;j=0; /*注意与前面的区别这里j=0;p=*L;*/ while( p && j

{ /*找i-1位置的元素*/ p=p->next; j++;

}

if(!p || j>i-1) return ERROR;/*找不到*/

s=(struct LNode *) malloc(sizeof(struct LNode));/*找到*/ s->data=e;

s->next=p->next;/*插入元素*/ p->next=s; return OK; }/*ListLink_L;*/

Status ListDelete(struct LNode **L,int i,ElemType *e )

{ /*在带表头的单链表中在第i个位删除结点,并由pe指针返回其值*/ int j;

struct LNode * p,*q;

p=*L;j=0; /*注意与前面的区别这里j=0;p=*L;*/ while(p->next && j

p=p->next; j++; }

if( !(p->next) || j>i-1 ) return ERROR; q=p->next;

p->next=q->next; *e=q->data; free(q); return OK; }/*ListDelete*/

L 11 22 Status CreateList(struct LNode **L,int n)

建成后的链表L {

ElemType x; int i;

for(i=1;i<=n;i++) {

scanf(\ ListInsert(L,i,x); } }

void ListPrint(struct LNode *L) { struct LNode * p; p=L->next; while(p) {

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

printf(\}

struct LNode *MergeList(struct LNode *La,struct LNode *Lb) { /*已知单链线性表La,Lb的元素按值非递减排列 */

/*归合La和Lb得到新的单链表Lc，Lc的元素也按非递减排列 */ struct LNode *pa,*pb,*pc,*Lc,*ptr; ListPrint(La); ListPrint(Lb); pa=La->next; pb=Lb->next ;

Lc=(struct LNode *)malloc(sizeof(struct LNode)); Lc->data=0; Lc->next=NULL;

pc=Lc; /*Lc的头结点 */ printf(\ while(pa && pb ) {

if( pa->data <=pb->data ) {

ptr=(struct LNode *)malloc(sizeof(struct LNode)); ptr->data=pa->data; ptr->next=NULL; pc->next =ptr; pc=ptr;

pa=pa->next ; } else {

ptr=(struct LNode *)malloc(sizeof(struct LNode)); ptr->data=pb->data; ptr->next=NULL; pc->next =ptr; pc=ptr;

pb=pb->next ; } }

if(pa)

while(pa) {

ptr=(struct LNode *)malloc(sizeof(struct LNode));

ptr->data=pa->data; ptr->next=NULL; pc->next =ptr; pc=ptr;

pa=pa->next ; } else

while(pb) {

ptr=(struct LNode *)malloc(sizeof(struct LNode)); ptr->data=pb->data; ptr->next=NULL; pc->next =ptr; pc=ptr;

pb=pb->next ; }

ListPrint(Lc);

return Lc; }

main()

{ struct LNode * la,*lb,*lc; ElemType e; int i;

int na=3,nb=4;

/*改变na,nb的值 */ InitList(&la);

InitList(&lb); /*初始化la,lb */ ListPrint(la); ListPrint(lb);

printf(\CreateList(&la,na); /*建立na个结点的顺序表 */ ListPrint(la);/*打印输出 */

printf(\CreateList(&lb,nb);/*建立nb个结点的顺序表 */ ListPrint(lb);/*打印输出 */

lc=MergeList(la,lb);/*合并到lc */ printf(\

ListPrint(lc);/*打印输出lc */ printf(\下面对链表la进行插入和删除操作\\n\

printf(\下面分别有两次输入输入测试数据，请自拟数据一次为成功，一次为不成功\\n\printf(\请输入插入位置:\scanf(\

printf(\请输入插入的元素值\scanf(\

if(ListInsert(&la,i,e))

{ printf(\插入成功,la为：\\n\ ListPrint(la);/*打印输出 */ } else

printf(\插入不成功\\n\

printf(\请输入插入位置:\scanf(\

printf(\请输入插入的元素值\scanf(\

if(ListInsert(&la,i,e))

{ printf(\插入成功,la为：\\n\

ListPrint(la);/*打印输出 */ } else

printf(\插入不成功\\n\

printf(\请输入删除的位置： \scanf(\

if(ListDelete(&la,i,&e))

{ printf(\删除成功,la为：\\n\

ListPrint(la);/*打印输出 */ printf(\删除的元素值为%d\\n\ } else

printf(\删除不成功\\n\

printf(\请输入删除的位置： \scanf(\

if(ListDelete(&la,8,&e))

{ printf(\删除成功,la为：\\n\

ListPrint(la);/*打印输出 */ printf(\删除的元素值为%d\\n\ }

else

printf(\删除不成功\\n\printf(\}

2.约瑟夫问题的一种描述：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数。

方法1．报m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。

方法2. 报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。 [方法1的程序清单] #include #include

typedef struct node /* 结点的结构定义 */ { int num; /* 编号子域 */ int sm; /* 密码子域 */ struct node *next; /* 指针域 */ }JOS;

/* 函数声明 */ JOS *creat();

void outs(JOS *h, int m); /* 主函数 */ main()

{ int m; JOS *h; h=creat();

printf(“\\n enter the begin secret code, m=（m>1）”); scanf(“%d”,&m); outs(h, m); } /* main */

/* 生成约瑟夫环 */ JOS *creat() h { int i=0, mi;

JOS *new, *pre, *h;

h=(JOS *)malloc(sizeof(JOS)); /* 为头结点申请空间 */ h->link=h; /* 头结点h形成环 */

pre=h;

printf(“\\n 个人密码 =?”); scanf(“%d”,&mi);

while( mi != -111) /* 密码为-111，结束循环 */ { new=(JOS *)malloc(sizeof(JOS)); /* 申请数据元素结点空间 */ i++; new->num=i; new->sm=mi; /* 结点送值 */ new->link=h; pre->link=new;

pre=new; /* 形成循环链表 */ printf(“\\n 个人密码 =?”); scanf(“%d”,&mi); /* 读入下一个密码 */

} /* while */

pre->link= h->link; free(h); /* 删除头结点h */ h=pre->link; return(h); /* 头指针指向第一个数据元素结点 */ } /* JOS *creat , 该约瑟夫环无附加头结点 */ /* 按m被叫出列的顺序，输出结点信息 */ void outs(JOS *h, int m) { int i; JOS *q=h, p; printf(“\\n “); while (q->link!=q)

{ for(i=1;ilink;} /* 报数到第m个人 */

printf(“m m ”,q->num,q->sm); /* 输出第m个人的编号和密码 */ p->link=q->link; free(q); /* 第m个人出列 */ q=p->link; }

printf(“m m \\n”,q->num,q->sm); /* 输出最后一个结点的编号值 */ free(q);

} /* outs */

本程序用了不带头结点的循环链表，也可以加上头结点，对于本题有头结点会使操作麻烦，（同学们可以试一试，加进头结点如何实现？）并不是任何时候有头结点都能使程序操作简化，要根据实际情况，决定用是否使用头结点。

感兴趣的同学可以设计一个程序实现约瑟夫环的方法2。

在一般情况下默认使用头结点。不论是单向链表还是循环链表，头指针不能丢。

四、思考题

1. 用顺序存储表示（数组）实现约瑟夫环问题。

2. 一个线性表有n个元素（n

[提示] 可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为‘工作结点’，需从链表的首结点开始比较，如果‘工作结点’的数据比链中的‘当前结点’的数据小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。[建立一条有序链表]

5．两个稀疏多项式的加法（稀疏多项式可采用顺序表或链表来存储）。 6. 超长正整数的加法，设计一个程序实现两个任意长的整数求和运算

[提示] 可采用一个带有头结点的循环链表来表示一个非负的超大整数。从低位 开始每四位组成的数字，依次放在链表的第一个、第二个、……结点中，不足四位的最高位存放在链表的最后一个结点中，表头结点值规定位-1。

例如：大整数“567890987654321”可用如下的头结点的链表表示： head -1 4321 8765 8909 0567

按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其代入下一个结点进行运算。

实验四 栈的基本操作及其应用

一、实验目的

1、熟悉栈的定义和栈的基本操作；

2、掌握顺序存储栈和链接存储栈的基本运算；

3、加深对栈结构的理解，逐步培养解决实际问题的编程能力。

二、实验内容和要求

1、编写函数，实现顺序栈的各种基本操作； 2、编写程序，利用栈实现算术表达式的求解。

三、实验分析

1. 栈(stack)的定义

栈(stack)是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶（top），另一个固定端称为栈底。当表中没有元素时称为空栈。下图表示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为后进先出的线

3. 邻接表的构造算法

ALGraph CreateALGraph(void) { ALGraph* p; int i,countvex,countarc; int start,end; VexType ch; p=(ALGraph*)malloc(sizeof(ALGraph)); printf(\请输入顶点个数(不超过%d):\ scanf(\ p->vexnum=countvex; printf(\下面输入%d个顶点的信息:\\n\ for(i=0;i<=countvex;i++){ scanf(\ p->vertices[i].data=ch; p->vertices[i].firstarc=NULL; } printf(\下面输入边的信息(以始点,终点形式输入,输入-1,-1结束)\\n\ printf(\ scanf(\ printf(\ scanf(\ countarc=0; while(start!=-1 && end!=-1) { insert(p,start,end);countarc++; printf(\ scanf(\ printf(\ scanf(\ } p->arcnum=countarc; return *p; }

4. 深度优先遍历（DFS）

所谓的深度优先遍历（Depth_First Search）是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。

深度优先搜索的基本思想是：

（1） 从图中某个顶点v0出发，首先访问v0。

（2） 找出刚访问过的顶点的第一个未被访问的邻接点，然后访问该顶点。重复此步

骤，直到刚访问过的顶点没有未被访问的邻接点。

（3） 返回前一个访问过的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶

点。转2。

如果用递归的形式说明，则深度优先搜索的基本思想是： （1） 访问出发点v0。

（2） 依次以v0的未被访问的邻接点为出发点，深度优先搜索图。

若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。

void DFS(ALGraph G, int v) {

/* 从顶点v出发，深度优先搜索遍历连通图 G*/ int w;

visited[v] = TRUE; printf(\ for(w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w);

/* 对v的尚未访问的邻接顶点w*/ /* 递归调用DFS*/ } /* DFS*/

void DFSTraverse(ALGraph G) { /* 对图 G 作深度优先遍历*/ int v;

for (v=0; v

visited[v] = FALSE; /* 访问标志数组初始化*/ for (v=0; v

if (!visited[v]) DFS(G, v);

/* 对尚未访问的顶点调用DFS*/ }

5. 广度优先遍历(BFS)

所谓的广度优先遍历（Breadth_First Search）是指按照广度方向搜索，它类似于树的按层次遍历，是树的按层次遍历的推广。

广度优先搜索的基本思想是：

（1） 从图中某个顶点v0出发，首先访问v0。 （2） 依次访问v0的各个未被访问的邻接点。

（3） 分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新

的端结点）。访问时应保证：如果Vi和Vk为当前端结点，且Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问。重复（3），直到所有端结点均没有未被访问的邻接点为止。 若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。

void BFSTraverse(ALGraph G){

int v,u,w; SqQueue Q;

for (v=0; v

if ( !visited[v]) { /* v 尚未访问*/ visited[v] = TRUE; printf(\ \.vertices[v].data); /* 访问v*/ EnQueue(&Q, v); /*v入队列*/ while (!QueueEmpty(Q)) { DeQueue(&Q, &u); /* 队头元素出队并置为u*/ for(w=FirstAdjVex(G, u); w!=-1;w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]=TRUE; printf(\ \.vertices[w].data); /* 访问w*/

EnQueue(&Q, w); /* 访问的顶点w入队列*/ } } /* while*/ }

} /* BFSTraverse*/

6.算法

在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树。 普利姆（prim）算法:

假设N=(V,{E})是连通网，TE为最小生成树中边的集合 （1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U, v∈V-U的边中选一条代价最小的边（u0，v0）并入集合TE，同时将v0并入U；

（3）重复（2），直到U=V为止。

此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。 可以看出，普利姆算法逐步增加U的中顶点，可称为“加点法”。

注意：选择最小边时，可能有多条同样权值的边可选，此时任选其一。

为了实现这个算法需要设置一个辅助数组closedge[ ]，以纪录从U到V-U具有最小代价的边。对每个顶点v∈V-U，在辅助数组中存在一个分量closedge[v]，它包括两个域vex和lowcost，其中lowcost存储该边上的权，显然有 closedge[v].lowcoast=Min({cost(u,v) | u∈U}) 辅助数组closedge[ ]的定义： struct {

VertexData adjvex; int lowcost;

} closedge[MAX_VERTEX_NUM]; /* 求最小生成树时的辅助数组*/

普里姆算法可描述如下：

void Prim(MGraph G, VexType u)

{ /*用普里姆算法从顶点u出发构造网G的最小生成树*/ CLOSEDGE closedge; int k,j,i;

k = LocateVex ( G, u );

for ( j=0; j

/* 求出加入生成树的下一个顶点(k)*/ printf(\ end_vex=%c\\n\.vexs[k]); /* 输出生成树上一条边*/ closedge[k].lowcost = 0; /* 第k顶点并入U集*/ for (j=0; j

7. 求最短路径的Dijkstra算法

迪杰斯特拉（Dijkstra）算法的基本思想是：按路径长度递增的顺序，逐个产生各最短路径。

迪杰斯特拉算法的主要步骤如下： ⑴ g为用邻接矩阵表示的带权图。 S←—{v0} ，dist[i]= g.arcs[v0][vi]；

将v0到其余顶点的路径长度初始化为权值； ⑵ 选择vk，使得

dist[vk]=min(dist[i] | vi∈V－S)

vk为目前求得的下一条从v0出发的最短路径的终点。

⑶ 修改从v0出发到集合V－S上任一顶点vi的最短路径的长度。如果

dist[k]+ g.arcs[k][i]

则将dist[i]修改为

dist[k]+ g.arcs[k][i]

⑷ 重复(2)、(3) n-1次，即可按最短路径长度的递增顺序，逐个求出v0到图中其它每个顶点的最短路径。

首先引进辅助向量dist[ ]，它的每一个分量dist[i]表示已经找到的且从开始点v0到每一个终点vi的当前最短路径的长度。它的初态为：如果从v0到vi有弧，则dist[i]为弧的权值；否则dist[i]为∞。其中，长度为

dist[j]=Min{dist[i] | vi∈V}

的路径是从v0出发的长度最短的一条最短路径，此路径为（v0，vj）。 typedef struct {

VexType vertex; /* 顶点信息 */

AdjType length; /* 最短路径长度 */

int prevex; /* 从v0到达vi(i=1,2,?n-1)的最短路径上vi的前趋顶点 */

}DIST;

DIST dist[MAXVEX];

void Dijkstra(MGraph graph, int v0) { int i,j,v,minvex; AdjType min; int finish[MAXVEX]; for(v=0;v