温州大学瓯江学院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={
基本操作：创建一个复数 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("input the real and image:\n"); /*输出提示信息：输入实部和虚部 */
scanf("%f,%f",&com.real,&com.image); /*输入复数的实虚部 */ 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("the complex com1 is:%f+%fi\n",com1.real,com1.image); com2=create_complex();/*调用创建复数函数 */
printf("the complex com2 is:%f+%fi\n",com2.real,com2.image); addcom=add_complex(com1,com2);/*调用复数相加函数*/
printf("the addcom is %f+%fi:\n",addcom.real,addcom.image); mulcom=mul_complex(com1,com2);/*调用复数相乘函数 */
printf("the mulcom is %f+%fi:\n",mulcom.real,mulcom.image); divcom=div_complex(com1,com2);/*调用复数相除函数 */
printf("the divcom is %f+%fi:\n",divcom.real,divcom.image);
printf("the real of divcom is %f:\n",real_complex(divcom));/*输出实部 */ printf("the image of mulcom is %f:\n",image_complex(mulcom));/*输出虚部 */ }
四、思考题
编写算法，一元多项式2012()...n
n n P x a a x a x a x =++++的值。请分析算法的时间复
杂度，要求时间复杂度尽可能小。
实验二 顺序表的基本操作
一、实验目的
1、掌握线性表的基本运算；
2、掌握顺序存储的概念，学会对顺序存储数据结构进行操作；
3、加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验内容和要求：
1、编写函数，创建一个顺序表（数据自拟）；
2、编写函数，在顺序表的指定位置插入一个元素；
3、编写函数，在顺序表的指定位置删除一个元素；
4、编写函数，将两个有序顺序表合并成一个新的有序顺序表；
三、实验分析
1. 线性表的顺序存储表示（结构）及实现。
阅读下列程序请注意几个问题：
（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素a i-1, a i，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含‘静态’一维数组和线性表长的结构体：
typedef int ElemType;
typedef struct{
ElemType elem[MAXSIZE];
int length;
}SqList; /* 顺序存储的结构体类型 */
（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段，并不强要求学生一定使用“菜单设计”技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复数处理程序中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。
[源程序]
#include "stdio.h"
#include "math.h"
#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;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("%d",&x); ListInsert(pL,i,x); } } void ListTraverse_Sq(SqList L) {int i; for( i=1;i<=L.length;i++) printf("%d ",L.elem[i-1]); printf("\n"); } 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("\n\n\n"); printf("\n 1. 建立线性表 " ); printf("\n 2. 在i位置插入元素e"); printf("\n 3. 删除第i个元素，返回其值"); printf("\n 4. 查找值为 e 的元素"); printf("\n 5. 两个有序表的合并"); printf("\n 6. 结束程序运行"); printf("\n======================================"); printf("\n 请输入您的选择（1，2，3，4，5，6）"); scanf("%d",&k); switch(k) { case 1:{ CreateList_Sq(&la,na); /*建立na个结点的顺序表 */ ListTraverse_Sq(la); } break; case 2:{ printf("\n i,e=?"); scanf("%d,%d",&i,&e); ListInsert(&la,i,e); ListTraverse_Sq(la); } break; case 3:{ printf("\n i=?"); scanf("%d",&i); ListDelete(&la,i,&x); ListTraverse_Sq(la); printf("\n x=%d",x); } break; case 4:{ printf("\n e=?"); scanf("%d",&e); loc=LocateElem(la,e); if (loc==0) printf("\n 未找到 %d",loc); else printf("\n 已找到，元素位置是 %d",loc); } 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("\n 再见！"); printf("\n 打回车键，返回。"); } 四、思考题 1. 用有序顺序表来表示集合，分别编写算法求两个集合的交集和并集。 2. 用顺序存储表示（数组）实现约瑟夫环问题。 实验三链表的基本操作及其应用 一、实习目的 1、掌握链表的概念，学会对链表进行操作； 2、加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力； 二、实验内容与要求 1.编写函数，创建一个带头结点的单链表（数据自拟）； 2.编写函数，在单链表的指定位置插入一个元素； 3.编写函数，在单链表的指定位置删除一个元素； 4.编写函数，将两个有序链表合并成一个新的有序链表； 5.编写程序，完成约瑟夫环的求解。 三、实验分析 1. 线性表的链表存储表示（结构）及实现。 阅读下列程序请注意几个问题： （1）关于线性表的链表存储结构的本质是：在逻辑上相邻的两个数据元素a i-1, a i，在存储地址中可以不相邻,既地址不连续。不同的教材的表示基本是一致的。 typedef struct LNode { ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */ }LNode，LinkList; /* 结点结构类型和指针类型 */ （2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供关于链表操作的资料，供学生参考。可以看到本程序的main()与前一程序的main()函数的结构十分相似。稍加改动还可为其他题目的源程序所用。 [源程序] #include "stdio.h" #include "stdlib.h" #include "math.h" #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; 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*/ Status CreateList(struct LNode **L,int n) { ElemType x; int i; for(i=1;i<=n;i++) { scanf("%d",&x); ListInsert(L,i,x); } } void ListPrint(struct LNode *L) { struct LNode * p; p=L->next; while(p) { 建成后的链表L printf("%d ",p->data); p=p->next; } printf("\n"); } 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("MergeList\n"); 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("please input data to struct LNode *la\n"); CreateList(&la,na); /*建立na个结点的顺序表 */ ListPrint(la);/*打印输出 */ printf("please input data to struct LNode *lb\n"); CreateList(&lb,nb);/*建立nb个结点的顺序表 */ ListPrint(lb);/*打印输出 */ lc=MergeList(la,lb);/*合并到lc */ printf("in main:print lc:\n"); ListPrint(lc);/*打印输出lc */ printf("下面对链表la进行插入和删除操作\n"); printf("下面分别有两次输入输入测试数据，请自拟数据一次为成功，一次为不成功\n"); printf("请输入插入位置:");; scanf("%d",&i); printf("请输入插入的元素值"); scanf("%d",&e); if(ListInsert(&la,i,e)) { printf("插入成功,la为：\n"); ListPrint(la);/*打印输出 */ } else printf("插入不成功\n"); printf("请输入插入位置:");; scanf("%d",&i); printf("请输入插入的元素值"); scanf("%d",&e); if(ListInsert(&la,i,e)) { printf("插入成功,la为：\n"); ListPrint(la);/*打印输出 */ } else printf("插入不成功\n"); printf("请输入删除的位置： "); scanf("%d",&i); if(ListDelete(&la,i,&e)) { printf("删除成功,la为：\n"); ListPrint(la);/*打印输出 */ printf("删除的元素值为%d\n",e); } else printf("删除不成功\n"); printf("请输入删除的位置： "); scanf("%d",&i); if(ListDelete(&la,8,&e)) { printf("删除成功,la为：\n"); ListPrint(la);/*打印输出 */ printf("删除的元素值为%d\n",e); } else printf("删除不成功\n"); printf("the end\n"); } 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() { 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;i printf(“%6d %6d ”,q->num,q->sm); /* 输出第m个人的编号和密码*/ p->link=q->link; free(q); /* 第m个人出列*/ q=p->link; } printf(“%6d %6d \n”,q->num,q->sm); /* 输出最后一个结点的编号值*/ free(q); } /* outs */ 本程序用了不带头结点的循环链表，也可以加上头结点，对于本题有头结点会使操作麻烦，（同学们可以试一试，加进头结点如何实现？）并不是任何时候有头结点都能使程序操作简化，要根据实际情况，决定用是否使用头结点。 感兴趣的同学可以设计一个程序实现约瑟夫环的方法2。 在一般情况下默认使用头结点。不论是单向链表还是循环链表，头指针不能丢。 四、思考题 1. 用顺序存储表示（数组）实现约瑟夫环问题。 2. 一个线性表有n个元素（n 3 从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求：（1）指定的值x由键盘输入；（2）程序能处理空链表的情况。 4.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。 要求：（1）通讯录是按姓名项的字母顺序排列的； （2）能查找通讯录中某人的信息； [提示] 可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为‘工作结点’，需从链表的首结点开始比较，如果‘工作结点’的数据比链中的‘当前结点’的数据小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。[建立一条有序链表] 5．两个稀疏多项式的加法（稀疏多项式可采用顺序表或链表来存储）。 6. 超长正整数的加法，设计一个程序实现两个任意长的整数求和运算 [提示] 可采用一个带有头结点的循环链表来表示一个非负的超大整数。从低位开始每四位组成的数字，依次放在链表的第一个、第二个、……结点中，不足四位的最高位存放在链表的最后一个结点中，表头结点值规定位-1。 例如：大整数“567890987654321”可用如下的头结点的链表表示： 按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其代入下一个结点进行运算。 实验四栈的基本操作及其应用 一、实验目的 1、熟悉栈的定义和栈的基本操作； 2、掌握顺序存储栈和链接存储栈的基本运算； 3、加深对栈结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容和要求 1、编写函数，实现顺序栈的各种基本操作； 2、编写程序，利用栈实现算术表达式的求解。 三、实验分析 1. 栈(stack)的定义 栈(stack)是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶（top），另一个固定端称为栈底。当表中没有元素时称为空栈。下图表示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为后进先出的线
相关主题
文本预览