下载文档原格式
苏州科技学院数据结构（C语言版）实验报告专业班级测绘1011学号10201151姓名XX实习地点C1 机房指导教师史守正目录封面 (1)目录 (2)实验一线性表 (3)一、程序设计的基本思想，原理和算法描述 (3)二、源程序及注释（打包上传） (3)三、运行输出结果 (4)四、调试和运行程序过程中产生的问题及采取的措施 (6)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (6)实验二栈和队列 (7)一、程序设计的基本思想，原理和算法描述 (8)二、源程序及注释（打包上传） (8)三、运行输出结果 (8)四、调试和运行程序过程中产生的问题及采取的措施 (10)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (10)实验三树和二叉树 (11)一、程序设计的基本思想，原理和算法描述 (11)二、源程序及注释（打包上传） (12)三、运行输出结果 (12)四、调试和运行程序过程中产生的问题及采取的措施 (12)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (12)实验四图 (13)一、程序设计的基本思想，原理和算法描述 (13)二、源程序及注释（打包上传） (14)三、运行输出结果 (14)四、调试和运行程序过程中产生的问题及采取的措施 (15)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (16)实验五查找 (17)一、程序设计的基本思想，原理和算法描述 (17)二、源程序及注释（打包上传） (18)三、运行输出结果 (18)四、调试和运行程序过程中产生的问题及采取的措施 (19)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (19)实验六排序 (20)一、程序设计的基本思想，原理和算法描述 (20)二、源程序及注释（打包上传） (21)三、运行输出结果 (21)四、调试和运行程序过程中产生的问题及采取的措施 (24)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (24)实验一线性表一、程序设计的基本思想，原理和算法描述：程序的主要分为自定义函数、主函数。
目录1问题描述 (2)2基本要求 (2)2.1问题分析及解决法案框架确定 (2)2.2程序设计 (2)2.3详细设计和编码 (2)3算法思想 (2)4模块划分 (3)4.1对各个模块进行功能的描述 (3)4.2模块之间关系及其相互调用 (3)5数据结构 (5)5.1定义栈 (5)5.2定义队列 (5)5.3栈的基本操作 (5)5.4队列的基本操作 (6)6测试数据 (6)7测试情况 (6)8总结 (9)1 问题描述试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。
其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。
例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
栈和队列是一种常见的数据结构，是两种非常重要的线性结构，也都是线性表，它们是操作受限的的线性表，有顺序栈、链式栈、链式队列和循环队列等形式。
它们广泛应用在各种软件系统中。
本题就是要用这些线性结构先完成基本的应用，如回文，逆置。
2 基本要求2.1问题分析及解决法案框架确定充分地分析和理解问题本身，使程序结构清晰合理简单和易于调试，并确定每个函数的简单功能，以及函数之间的调用关系。
2.2程序设计1、选择顺序栈和链队列，完成回文判断、字符串的逆置；2、选择链栈和循环队列，完成回文判断、字符串的逆置；3、运用掌握C语言编写程序，实现所编程序的各个模块功能。
2.3详细设计和编码给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。
3 算法思想运用栈和队列算法，在序列依次输入时将序列分别入栈和入队列，利用栈FILO 和队列FIFO的特点，通过出栈和出队列实现序列顺序和逆序的比较，根据题目描述的回文序列判断并输出结果。
定义顺序栈和链队列及关于它们的基本操作，如定义栈和队列、求栈和队列的长度、入栈出栈、入队列出队列等。
栈的定义和特点栈（stack）是⼀个特殊的线性表，是限定仅在⼀端（通常是表尾）进⾏插⼊和删除操作的线性表。
⼜称为后进先出（Last In First Out）的线性表，简称 LIFO 结构。
栈的相関概念：栈是仅在表尾进⾏插⼊、删除操作的线性表。
表尾（即an端）称为栈顶 Top；表头（即a1端）称为栈底 Base例如：栈 s = (a1,a2,a3.....an-1,an) a1被称为栈底元素，an被称为栈顶元素插⼊元素到栈顶（即表尾）的操作，称为⼊栈。
从栈顶（即表尾）删除最后⼀个元素的操作，称为出栈。
栈的⽰意图：操作⽰意图-⼊栈：操作⽰意图-出栈：【思考】假设有3个元素a,b,c，⼊栈顺序是a,b,c 则他们的出栈顺序有⼏种可能⼊栈顺序：a进⼊后，b进⼊，最后c进⼊出栈顺序：（先进后出）所以得到，c,b,a这种出栈顺序也可以：a⼊栈，接着a出栈；b⼊栈，接着b出栈；c⼊栈，接着c出栈。
还可以：a⼊栈，接着a出栈；b⼊栈，c⼊栈，接着c出栈，b出栈。
还可以：a⼊栈，b⼊栈，b出栈，a出栈，c⼊栈，c出栈总结⼀下：栈的定义：限定只能在表的⼀端进⾏插⼊和删除运算的线性表（只能在栈顶操作）逻辑结构：与同线性表相同，仍为⼀对⼀关系。
存储结构：⽤顺序栈（⽤顺序存储的话，就叫顺序栈）或链栈（⽤链式存储的话，就叫链栈）存储均可，但以顺序栈更常见运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则实现⽅式：关键是编写⼊栈和出栈函数，具体实现依顺序栈和链栈的不同⽽不同栈与⼀般线性表的区别：仅在于运算规则不同。
，⼀般线性表逻辑结构：⼀对⼀存储结构：顺序表、链表栈逻辑结构：⼀对⼀存储结构：顺序栈、链栈。
第三次作业第三章栈和队列一、选择题1. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。
A. i-j-1B. i-jC. j-i+1D. 不确定的2. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ AD ）。
A. |top[2]-top[1]|=0B. top[1]+1=top[2]C. top[1]+top[2]=mD.top[1]=top[2]3. 栈在（ D ）中应用。
A. 递归调用B. 子程序调用C. 表达式求值D. A，Ｂ，Ｃ4. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ D ），其中^为乘幂。
A. 3,2,4,1,1；(*^(+*-B. 3,2,8；(*^-C. 3,2,4,2,2；(*^(-D. 3,2,8；(*^(-5. 用链接方式存储的队列，在进行删除运算时（ D ）。
A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改D. 头、尾指针可能都要修改6. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m7. 栈和队列的共同点是（ C ）。
A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。
A． 6 B. 4 C. 3 D. 2二、判断题1.消除递归不一定需要使用栈，此说法（√）2. 栈是实现过程和函数等子程序所必需的结构。
2015-2016学年第二学期《算法与数据结构》课程实验报告专业软件工程学生姓名成晓伟班级软件141学号1410075094实验学时16实验教师徐秀芳信息工程学院实验一单链表的基本操作一、实验目的1.熟悉C语言上机环境，进一步掌握C语言的基本结构及特点。
2.掌握线性表的各种物理存储表示和C语言实现。
3.掌握单链表的各种主要操作的C语言实现。
4.通过实验理解线性表中的单链表存储表示与实现。
二、主要仪器及耗材普通计算机三、实验内容与要求1、用C语言编写一个单链表基本操作测试程序。
（1）初始化单链表（2）创建单链表（3）求单链表长度（4）输出单链表中每一个结点元素（5）指定位置插入某个元素（6）查找第i个结点元素的值（7）查找值为e 的结点，并返回该结点指针（8）删除第i个结点（9）销毁单链表2、实验要求（1）程序中用户可以选择上述基本操作。
程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。
（2）要求用线性表的顺序存储结构，带头结点的单链表存储结构分别实现。
（3）主函数实现对基本操作功能的调用。
3、主要代码（1）初始化单链表LinkList *InitList(){ //创建一个空链表,初始化线性表LinkList *L;L=(LinkList *)malloc(sizeof(LinkList));L->next=NULL;return L;}（2）创建单链表//头插法void CreateListF(LinkList *L){LinkList *s;int i=1,a=0;while(1){printf("输入第%d个元素(0表示终止)",i++);scanf("%d",&a);if(a==0)break;s=(LinkList *)malloc(sizeof(LinkList));s->data=a;s->next=L->next;L->next=s;}}（3）求链表长度int ListLength(LinkList *L){ //求链表长度int n=0;LinkList *p=L;while(p->next!=NULL){p=p->next;n++;}return(n);}（4）在指定位置插入元素int InsertList(LinkList *L,int i,ElemType e){LinkList *p=L,*s;int j=0;while(p!=NULL&&j<i-1){p=p->next;j++;} //找出要插入的位置的前一个位置if(p==NULL){return 0;}else{s=(LinkList *)malloc(sizeof(LinkList));s->data=e;s->next=p->next;p->next=s;return 1;}}（5）输出链表void DispList(LinkList *L){ //输出链表LinkList *p=L->next;while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}（6）查找链表中指定元素int GetElem(LinkList *L,int i){ //查找链表中指定元素LinkList *p=L;int j=0;while(j<i&&p!=NULL){j++;p=p->next;}if(p==NULL){return 0;}else{return p->data;}}（7）查找值是e的结点并返回该指针LinkList *LocateElem(LinkList *L,ElemType e){ //查找值是e的结点并返回该指针int i=1;LinkList *p=L;while(p!=NULL)if(p->data==e) return p;}if(p==NULL){return NULL;}}（8）删除元素int ListDelete(LinkList *L,int i,ElemType *e){ //删除元素LinkList *p=L,*q;int j=0;while(p!=NULL&&j<i-1){p=p->next;j++;} //找到要删除元素地址的前一个地址if(p==NULL){ return 0;} //不能删除else{q=p->next;*e=q->data;p->next=q->next;free(q); //删除成功return 1;}}（9）销毁链表void DestroyList(LinkList *L){//销毁链表LinkList *pre=L,*p=L->next;while(p!=NULL){free(pre);pre=p;p=pre->next;}free(pre);}main函数：int main(){LinkList *L;ElemType e;int i;L=InitList();CreateListF(L);DispList(L);printf("输入要查找的元素位置:\n");scanf("%d",&i);e=GetElem(L,i);printf("%d\n",e);printf("单链表长度为:%d\n",ListLength(L));printf("输入要删除元素的位置:");scanf("%d",&i);if (i>ListLength(L)){printf("超出范围重新输入");scanf("%d",&i);}if(ListDelete(L,i,&e)==0){printf("未找到元素\n");}else DispList(L);printf("输入插入元素的位置和值:");scanf("%d%d",&i,&e);InsertList(L,i,e);DispList(L);return 0;}4、测试数据及测试结果输入：23 56 12 28 45输出：四、注意事项1、存储结构定义和基本操作尽可能用头文件实现。
. 教育范文 第五次实验报告—— 顺序栈、链栈的插入和删除 一 需求分析 1、在演示程序中，出现的元素以数字出现定义为int型， 2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上 3、顺序栈的程序执行的命令包括如下： （1） 定义结构体 （2） 顺序栈的初始化及创建 （3） 元素的插入 （4） 元素的删除 （5） 顺序栈的打印结果 3、链栈的程序执行的命令包括如下： （1） 定义结构体 （2） 链栈的初始化及创建 （3） 元素的插入 （4） 元素的删除 （5）链栈的打印结果 .
教育范文 二 概要设计 1、顺序栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作： InitStack(SqStack &S) 操作结果：构造一个空栈 Push(L,e) 操作结果：插入元素e为新的栈顶元素 Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作： LinkStack(SqStack &S) 操作结果：构造一个空栈 Status Push(L,e) 操作结果：插入元素e为新的栈顶元素 . 教育范文 Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List；
3、顺序栈程序包含的主要模块： (1) 已给定的函数库： （2）顺序栈结构体： （3）顺序栈初始化及创建: (4)元素插入 (5)元素删除 （6）主程序：
4、链栈程序包含的主要模块： (1) 已给定的函数库： （2）链栈结构体： （3）链栈初始化及创建: (4)元素插入 (5)元素删除 (6)主程序：
三 详细设计 线性栈： . 教育范文 结构体 #define STACK_INIT_SIZE 100//存储空间初始分配量 #define STACKINCREMENT 10//存储空间分配增量 typedef struct { int *base;//在构造栈之前和销毁之后，base的值为NULL int *top;//栈顶指针 int stacksize;//当前已分配的存储空间，以元素为单位 }SqStack#include"Base.h" 主函数 #include"construction.h" #include"stack_operation.c" int main() { SqStack S; int choice,e; S=InitStack(); S=Input_Sq(S); printf("请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice="); scanf("%d",&choice); switch(choice) . 教育范文 { case 1: { printf("请输入插入元素的值e="); scanf("%d",&e); S=Push(S,e); printf("执行入栈操作后的线性栈为"); Print_Stack(S); };break; case 2: {S=Pop(S); printf("执行出栈操作后的线性栈为"); Print_Stack(S); };break; default : printf("您输入的值不合法"); } } 线性栈的创建 SqStack InitStack()//线性栈的创建 { SqStack S; S.base=(int*)malloc(STACK_INIT_SIZE * sizeof(int));//分配 . 教育范文 存储空间 if(!S.base) exit(OVERFLOW);//存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return S; } 输入函数 SqStack Input_Sq(SqStack S)//输入函数 { int n,i; printf("请输入元素个数n="); scanf("%d",&n); printf("请输入%d个元素",n); for(i=0;i{
scanf("%d",S.top); S.top++; } return S; } . 教育范文 进栈函数 SqStack Push(SqStack S,int e)//进栈函数 { if(S.top-S.base>=S.stacksize)//判断栈是否为满，追加存储空间 {
S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) exit(OVERFLOW);//存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e;//插入元素 return S; } 出栈函数 SqStack Pop(SqStack S)//删除函数 { int e; if(S.top==S.base) . 教育范文 printf("线性栈为空"); e=*--S.top; return S; } 输出函数 void Print_Stack(SqStack S)//打印函数 { int i; while(S.base!=S.top) { for(i=0;i{ S.top--; printf("%5d",*S.top); } printf("\n"); } 库函数 * Base.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,故去掉此行 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSEl 链栈程序： 结构体 typedef struct SNode//建立链表结构体 . 教育范文 { int data; struct SNode *next; }SNode,*LinkStack; 主函数 #include"Base.h" #include"construction.h" #include"LinkStack_operation.c" int main() { LinkStack S; int choice,e; S=Creatlist_Stack(); printf("请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice="); scanf("%d",&choice); switch(choice) { case 1: { printf("请输入插入元素的值e="); scanf("%d",&e); . 教育范文 S=Push(S,e); printf("执行操作入栈后的线性栈为"); Print_Stack(S); };break; case 2: { S=Pop(S); printf("执行出栈操作后的线性栈为"); Print_Stack(S); };break; default : printf("您输入的值不合法\n"); } } 创建链栈函数 LinkStack Creatlist_Stack()//创建一个链栈 { LinkStack S; LinkStack P; int i,n; S=(LinkStack)malloc(sizeof(SNode)); S->next=NULL;/* 先建立一个链栈 */ printf("请输入元素个数n=");
