实验三 实现顺序栈的插入和删除算法

数据结构与算法分析实验报告一、实验目的本次实验旨在通过实际操作和分析，深入理解数据结构和算法的基本概念、原理和应用，提高解决实际问题的能力，培养逻辑思维和编程技巧。

二、实验环境本次实验使用的编程语言为 Python，使用的开发工具为 PyCharm。

操作系统为 Windows 10。

三、实验内容（一）线性表的实现与操作1、顺序表的实现使用数组实现顺序表，包括插入、删除、查找等基本操作。

通过实验，理解了顺序表在内存中的存储方式以及其操作的时间复杂度。

2、链表的实现实现了单向链表和双向链表，对链表的节点插入、删除和遍历进行了实践。

体会到链表在动态内存管理和灵活操作方面的优势。

（二）栈和队列的应用1、栈的实现与应用用数组和链表分别实现栈，并通过表达式求值的例子，展示了栈在计算中的作用。

2、队列的实现与应用实现了顺序队列和循环队列，通过模拟银行排队的场景，理解了队列的先进先出特性。

（三）树和二叉树1、二叉树的遍历实现了先序、中序和后序遍历算法，并对不同遍历方式的结果进行了分析和比较。

2、二叉搜索树的操作构建了二叉搜索树，实现了插入、删除和查找操作，了解了其在数据快速查找和排序中的应用。

（四）图的表示与遍历1、邻接矩阵和邻接表表示图分别用邻接矩阵和邻接表来表示图，并比较了它们在存储空间和操作效率上的差异。

2、图的深度优先遍历和广度优先遍历实现了两种遍历算法，并通过对实际图结构的遍历，理解了它们的应用场景和特点。

（五）排序算法的性能比较1、常见排序算法的实现实现了冒泡排序、插入排序、选择排序、快速排序和归并排序等常见的排序算法。

2、算法性能分析通过对不同规模的数据进行排序实验，比较了各种排序算法的时间复杂度和空间复杂度。

四、实验过程及结果（一）线性表1、顺序表在顺序表的插入操作中，如果在表头插入元素，需要将后面的元素依次向后移动一位，时间复杂度为 O(n)。

删除操作同理，在表头删除元素时，时间复杂度也为 O(n)。

一、实验目的1．掌握单链表的基本操作：插入、删除、查找以及表的合并等运算。

2．掌握运用C语言上机调试单链表的基本方法。

二、实验任务1．试编写在单链表上实现插入和删除的算法。

三、程序流程图四、测试过程及结果五、总结1．程序特点：最小化、模块化、for循环。

2．单链表特点：动态分配内存、必须从已知指针逐一查找数据、通过改变数据间的链接改变顺序。

附录程序清单#include <stdio.h>#include <stdlib.h>struct NODE{int data;NODE *next;};NODE *creatlink(){NODE *head,*p,*s;int i,n;head=(NODE *)malloc(sizeof(NODE));p=head;scanf("%d",&n);for(i=0;i<n;i++){s=(NODE *)malloc(sizeof(NODE));scanf("%d",&s->data);p->next=s;p=s;}p->next=0;return head;}void print(NODE *p){for(p=p->next;p!=0;p=p->next)printf("%d ",p->data);printf("\n");}void insert(NODE *p,int i,int x){NODE *s;int j;for(j=1;j<i;j++)p=p->next;s=(NODE *)malloc(sizeof(NODE));s->data=x;s->next=p->next;p->next=s;}void Delete(NODE *p,int i){NODE *s;int j;for(j=1;j<i;j++)p=p->next;s=p->next;p->next=s->next;free(s);}void main(){int i,x;NODE A=*creatlink();scanf("%d%d",&i,&x);insert(&A,i,x);print(&A);scanf("%d",&i);Delete(&A,i);print(&A);}。

栈和队列的操作实验小结一、实验目的本次实验旨在深入理解和掌握栈和队列这两种基本数据结构的基本操作，包括插入、删除、查找等操作，并通过实际操作加深对这两种数据结构特性的理解。

二、实验原理栈（Stack）：栈是一种后进先出（Last In First Out，LIFO）的数据结构，即最后一个进入栈的元素总是第一个出栈。

在计算机程序中，栈常常被用来实现函数调用和递归等操作。

队列（Queue）：队列是一种先进先出（First In First Out，FIFO）的数据结构，即第一个进入队列的元素总是第一个出队。

在计算机程序中，队列常常被用来实现任务的调度和缓冲等操作。

三、实验步骤与结果创建一个空栈和一个空队列。

对栈进行入栈（push）和出栈（pop）操作，观察并记录结果。

可以发现，栈的出栈顺序与入栈顺序相反，体现了后进先出的特性。

对队列进行入队（enqueue）和出队（dequeue）操作，观察并记录结果。

可以发现，队列的出队顺序与入队顺序相同，体现了先进先出的特性。

尝试在栈和队列中查找元素，记录查找效率和准确性。

由于栈和队列的特性，查找操作并不像在其他数据结构（如二叉搜索树或哈希表）中那样高效。

四、实验总结与讨论通过本次实验，我更深入地理解了栈和队列这两种数据结构的基本特性和操作。

在实际编程中，我可以根据需求选择合适的数据结构来提高程序的效率。

我注意到，虽然栈和队列在某些操作上可能不如其他数据结构高效（如查找），但它们在某些特定场景下具有无可替代的优势。

例如，在实现函数调用和递归时，栈的特性使得它成为最自然的选择；在实现任务调度和缓冲时，队列的特性使得它成为最佳选择。

我也认识到，不同的数据结构适用于解决不同的问题。

在选择数据结构时，我需要考虑数据的特性、操作的频率以及对时间和空间复杂度的需求等因素。

通过实际操作，我对栈和队列的实现方式有了更深入的理解。

例如，我了解到栈可以通过数组或链表来实现，而队列则可以通过链表或循环数组来实现。

算法与及数据结构实验报告算法与数据结构实验报告一、实验目的本次算法与数据结构实验的主要目的是通过实际操作和编程实现，深入理解和掌握常见算法和数据结构的基本原理、特性和应用，提高我们解决实际问题的能力和编程技巧。

二、实验环境本次实验使用的编程语言为 Python，开发环境为 PyCharm。

同时，为了进行算法性能的分析和比较，使用了 Python 的 time 模块来计算程序的运行时间。

三、实验内容1、线性表的实现与操作顺序表的实现：使用数组来实现顺序表，并实现了插入、删除、查找等基本操作。

链表的实现：通过创建节点类来实现链表，包括单向链表和双向链表，并完成了相应的操作。

2、栈和队列的应用栈的实现与应用：用数组或链表实现栈结构，解决了表达式求值、括号匹配等问题。

队列的实现与应用：实现了顺序队列和循环队列，用于模拟排队系统等场景。

3、树结构的探索二叉树的创建与遍历：实现了二叉树的先序、中序和后序遍历算法，并对其时间复杂度进行了分析。

二叉搜索树的操作：构建二叉搜索树，实现了插入、删除、查找等操作。

4、图的表示与遍历邻接矩阵和邻接表表示图：分别用邻接矩阵和邻接表来存储图的结构，并对两种表示方法的优缺点进行了比较。

图的深度优先遍历和广度优先遍历：实现了两种遍历算法，并应用于解决路径查找等问题。

5、排序算法的比较插入排序、冒泡排序、选择排序：实现了这三种简单排序算法，并对不同规模的数据进行排序，比较它们的性能。

快速排序、归并排序：深入理解并实现了这两种高效的排序算法，通过实验分析其在不同情况下的表现。

6、查找算法的实践顺序查找、二分查找：实现了这两种基本的查找算法，并比较它们在有序和无序数据中的查找效率。

四、实验步骤及结果分析1、线性表的实现与操作顺序表：在实现顺序表的插入操作时，如果插入位置在表的末尾或中间，需要移动后续元素以腾出空间。

删除操作同理，需要移动被删除元素后面的元素。

在查找操作中，通过遍历数组即可完成。

实验报告一------顺序表的插入和删除1.实验目的1、输入一批整型数据，建立顺序表；2、实现顺序表的插入（输入插入位置i,插入元素）3、实现顺序表的删除（输入删除元素位置i）4、实现顺序表中数据的显示；5、实现顺序表中数据的查找和定位；6、编写主函数，调试上述算法。

2.实验源代码#include<stdio.h>#define max 100void sequenlist(int s[],int n) //建立一个顺序表{for(int i=0;i<n;i++){printf("顺序表第%d个元素是：\n",i+1);scanf("%d",&s[i]);}printf("所以该顺序表输出为：\n");for(int j=0;j<n;j++){printf("%d\t",s[j]);}putchar('\n');}void insert(int s[],int &n,int i,int x) //顺序表的插入{if(n==max||i<1||i>n+1)printf("插入失败!!!\n");elsefor(int k=n-1;k>=i-1;k--){s[k+1]=s[k];}s[i-1]=x;n++;}void dele(int s[],int &n,int i) //删除元素位置i {if(i<1||i>n+1)printf("无法删除!!!\n");elsefor(int j=i-1;j<n;j++){s[j]=s[j+1];}n--;}void disp(int s[],int n) //输出顺序表数据{printf("该顺序表输出为：\n");for(int j=0;j<n;j++){printf("%d\t",s[j]);}putchar('\n');}void locate(int s[],int &n,int x) //查找和定位{int k;for(int j=0;j<n;j++){if(s[j]==x)k=j+1;}printf("您要查找的数据位于第%d位!\n",k);}int main(){int s[max];int n;int i,x;int num;printf("请输入顺序表的数据元素个数：\n");scanf("%d",&n);sequenlist(s,n); //顺序表的建立printf("******************************************************\n" );printf("*************1.插入***********************************\n");printf("*************2.删除***********************************\n");printf("*************3.输出***********************************\n");printf("*************4.查找***********************************\n");printf("******************************************************\n" );while(1){printf("请选择：\n");scanf("%d",&num);switch(num){case 1:printf("请选择要插入的位置：\n");scanf("%d",&i);printf("请选择要插入的数据：\n");scanf("%d",&x);insert(s,n,i,x);break;case 2:printf("请选择您要删除的元素位置：\n");scanf("%d",&i);dele(s,n,i);break;case 3:disp(s,n);break;case 4:printf("请选择您要查询的元素：\n");scanf("%d",&x);locate(s,n,x);break;default:goto l;break;}}l:return 0;}3．实验结果见下图！。

#include<stdio.h>#include<string.h>#include<ctype.h>//作用的函数？？？？？？？？？？#include<malloc.h> // malloc()等#include<limits.h> // INT_MAX等#include<stdio.h> // EOF(=^Z或F6),NULL#include<stdlib.h> // atoi()#include<io.h> // eof()#include<math.h> // floor(),ceil(),abs()#include<process.h> // exit( )#include<iostream.h> // cout,cin#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int SElemType;typedef int Status;#define STACK_INIT_SIZE 100// 存储空间初始分配量#define STACKINCREMENT 10 // 存储空间分配增量typedef struct {SElemType *base; // base的初值为NULLSElemType *top; // 栈顶指针int stacksize; // 当前已分配的存储空间，以元素为单位}SqStack;Status InitStack(SqStack &S){// 构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base) exit(OVERFLOW);S.top =S.base;S.stacksize= STACK_INIT_SIZE;return OK;}// STACK_INIT_SIZEStatus StackEmpty (SqStack S){// 若栈S为空栈，则返回TRUE，否则返回FALSEif(S.top-S.base)return FALSE;return TRUE;}Status Push(SqStack &S, SElemType e){// 插入元素e为新的栈顶元素int *Newbase;if(S.top-S.base>=S.stacksize){//栈满，追加存储Newbase=(SElemType*)realloc(S.base,(S.stacksize+ STACKINCREMENT)*sizeof(SElemType));if(!Newbase)exit(OVERFLOW);//存储分配失败S.base=Newbase;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}//pushStatus Pop (SqStack &S,SElemType &e){// 若栈不空，则删除S的栈顶元素，用e返回其值，// 并返回OK；否则返回ERRORif(S.top==S.base)return ERROR;e=*--S.top;return OK;}//PopStatus ClearStack (SqStack &S){// 把S置为空栈S.top=S.base;return OK;}// ClearStack//正序输出void PrintL(SqStack &S){int *p,n;p=S.base;for(n=S.top-S.base;n>0;n--){printf("%d\t",*p);p++;}//逆序输出/*void PrintL(SqStack &S){int *p,n;p=S.top;for(n=0;n<S.top-S.base;n++){printf("%d\t",*--p);//为啥不可以替换--p？？？}}*/void main(){int k,e;//为了区别下边变量的用法不同这里用k区别开n的作用//int n,e;SqStack S;InitStack (S);printf("空栈已经为您创建成功啦！*_* \n");printf("请您输入入栈的元素：^_^ \n"); //$$while(e!=0) //这里的0是输入入栈元素结束的标志{scanf("%d",&e); //输入栈中元素Push(S,e); //进栈操作if(e==0){ //$$Pop (S, e); //$$在打印出来之前删掉栈尾部元素^_^PrintL(S); //$$输出栈break; //$$结束}}// PrintL(S);这里会出现反复输出的现象printf("\n1.插入\t\n2.删除\t\n3.清空\t\n0.退出\t\n请选择您需要的操作序号~_~ \n");while(k){//主函数中定义的k可以用了int n;scanf("%d",&n);switch(n){ //switch(k){case 1:printf("请输入您要插入的数字@_@ --->\t");scanf("%d",&e);printf("\n");//添加Push (S,e);printf("插入栈顶元素后栈的情况如下所示~_~\n");//要清楚地告诉PrintL(S);printf("\n请选择您还需要的操作序号*_*\n");//可删除break;case 2:printf("删除栈尾元素后栈的情况如下所示#_#\n");Pop (S, e);// printf("删除栈顶元素%d \t",e);//输出不好看不用PrintL(S);printf("\n");printf("\n请选择您还需要的操作序号*_*\n");//可删除break;case 3:ClearStack(S);printf("栈已清空!_! !_!");printf("\n请选择您还需要的操作序号*_*\n");//可删除break;case 0:exit(0);break;default: exit(0);}}}总结：这是关于栈的基本操作的程序，我自己调试了一个晚上。

内蒙古科技大学信息工程学院计算机系《数据结构与算法》实验报告
add(a,b,c);
nodeprint(c);
return 0;
}
实验过程及结果线性表的顺序存储和删除：线性表的链式存储和删除：
顺序栈：
链队列：
实验三：
实验总结
【实验1】
这次实验了解了线性表的顺序存储结构和线性表的链式存储结构的插入和删除的操作，了解了线性表这两种存储方式的不同以及这两种线性表的优缺点，顺序存储结构的效率较低而链式存储结构的插入和删除效率高一些，操作更容易一些。

【实验2】
这次实验初步掌握了栈和队列的简单应用，学会的创建栈和队列，向栈和队列中传入参数，销毁栈和队列。

【实验3】
这次实验掌握了数组的压缩存储和应用，用三元组实现了矩阵之间的相加
1、每个实验项目填写一份实验报告，电子版命名方式为：学号姓名项目号.doc。

例如：1167111182张三3.doc表示张三做的第3个项目的实验报告。

2、实验报告电子版应该在实验后一周内由学习委员收齐后存放在一个文件夹下，文件夹命
名方式为：软件12-1班3，表示软件12-1班第3个项目的实验报告，压缩。

第一时间发送
给任课教师。

必须以班级为单位上交。

顺序栈的实现代码顺序栈是一种基于数组实现的栈结构，它具有后进先出（LIFO）的特点。

在顺序栈中，元素的插入和删除操作只能在栈顶进行，即只能在栈顶进行入栈和出栈操作。

下面我们将介绍顺序栈的实现代码。

我们需要定义一个顺序栈的结构体，包含两个主要的成员变量：一个数组用于存储栈中的元素，一个整数用于记录栈顶的位置。

```#include <stdio.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;} SeqStack;```在顺序栈的初始化函数中，我们将栈顶位置初始化为-1，表示栈为空。

```void init(SeqStack *stack) {stack->top = -1;}```接下来，我们实现入栈操作。

入栈操作是将一个元素插入到栈顶的过程。

首先，我们需要判断栈是否已满，如果栈已满则无法插入元素；如果栈未满，则将栈顶位置加1，并将要插入的元素放入栈顶位置。

```void push(SeqStack *stack, int element) {if (stack->top == MAX_SIZE - 1) {printf("Stack is full, cannot push element.\n");return;}stack->top++;stack->data[stack->top] = element;}```然后，我们实现出栈操作。

出栈操作是将栈顶元素删除的过程。

首先，我们需要判断栈是否为空，如果栈为空则无法删除元素；如果栈不为空，则将栈顶位置减1，并返回栈顶元素的值。

```int pop(SeqStack *stack) {if (stack->top == -1) {printf("Stack is empty, cannot pop element.\n");return -1;}int element = stack->data[stack->top];stack->top--;return element;}```接下来，我们实现获取栈顶元素的操作。

数据结构实验-顺序表的基本操作顺序表是一种线性数据结构，它的元素在内存中是连续存储的。

顺序表具有随机访问的特点，可以通过下标直接访问元素，因此在访问元素时具有较高的效率。

顺序表的基本操作包括插入、删除、查找等，下面将对这些基本操作进行详细介绍。

1. 初始化：初始化顺序表需要为其分配一定的内存空间，以存储元素。

可以使用静态分配或动态分配两种方式来初始化顺序表。

静态分配是在编译时为顺序表分配固定大小的内存空间，而动态分配是在运行时根据需要动态地为顺序表分配内存空间。

2. 插入操作：插入操作是将一个元素插入到顺序表的指定位置上。

在插入元素之前，需要判断顺序表是否已满，如果已满则需要进行扩容操作。

插入元素时，需要将插入位置以及其后的元素向后移动一位，为插入元素腾出位置。

插入操作的时间复杂度为O(n)，其中n为顺序表的长度。

3. 删除操作：删除操作是将顺序表中的一个元素删除。

在删除元素之前，需要判断顺序表是否为空，如果为空则无法进行删除操作。

删除元素时，需要将删除位置后面的元素向前移动一位，覆盖删除位置上的元素。

删除操作的时间复杂度为O(n)，其中n为顺序表的长度。

4. 查找操作：查找操作是根据给定的关键字，在顺序表中查找满足条件的元素。

可以使用顺序查找或二分查找两种方式进行查找。

顺序查找是从顺序表的第一个元素开始，逐个比较关键字，直到找到满足条件的元素或遍历完整个顺序表。

二分查找是在有序顺序表中进行查找，每次将待查找区间缩小一半，直到找到满足条件的元素或待查找区间为空。

查找操作的时间复杂度为O(n)，其中n为顺序表的长度。

5. 修改操作：修改操作是将顺序表中的一个元素修改为新的值。

修改操作需要先进行查找操作，找到待修改的元素，然后将其值修改为新的值。

修改操作的时间复杂度为O(n)，其中n为顺序表的长度。

6. 遍历操作：遍历操作是依次访问顺序表中的每个元素。

可以使用for循环或while循环进行遍历，从第一个元素开始，依次访问每个元素，直到遍历完整个顺序表。

《数据结构》课程上机实验指导书实验一【实验名称】顺序表的基本算法【实验目的】创建一个顺序表，掌握线性表顺序存储的特点。

设计和验证顺序表的查找、插入、删除算法。

【实验要求】（1）从键盘读入一组整数，按输入顺序形成顺序表。

并将创建好的顺序表元素依次打印在屏幕上。

（2）设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素的功能。

（3）当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。

（4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。

【实验步骤】1、实验前先写好算法。

2、上机编写程序。

3、编译。

4、调试。

例程：书上参考算法2-1，2-4，2-5，2-6，2-8！带菜单的主函数参考书上2.5综合实例！注意：顺序表的结构体！typedef struct{datatype items[listsize];int length;}SpList;实验二【实验名称】单链表的基本算法【实验目的】创建一个单链表，掌握线性表链式存储的特点。

设计和验证链表的查找、插入、删除、求表长的算法。

【实验要求】（1）从键盘读入一组整数，按输入顺序形成单链表。

并将创建好的单链表元素依次打印在屏幕上。

（注意：选择头插法或者尾插法！）（2）设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找数据元素，和求单链表表长等几项功能。

（3）当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。

（4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。

【实验步骤】1、实验前先写好算法。

国开数据结构(本)数据结构课程实验报告1. 实验目的本次实验的主要目的是通过实际操作，掌握数据结构的基本概念、操作和应用。

通过对实验内容的了解和实际操作，达到对数据结构相关知识的深入理解和掌握。

2. 实验工具与环境本次实验主要使用C++语言进行编程，需要搭建相应的开发环境。

实验所需的工具和环境包括：C++编译器、集成开发环境(IDE)等。

3. 实验内容本次实验主要包括以下内容：3.1. 实现顺序存储结构的线性表3.2. 实现链式存储结构的线性表3.3. 实现栈和队列的顺序存储结构和链式存储结构3.4. 实现二叉树的顺序存储结构和链式存储结构3.5. 实现图的邻接矩阵和邻接表表示4. 实验步骤实验进行的具体步骤如下：4.1. 实现顺序存储结构的线性表- 定义数据结构- 实现插入、删除、查找等操作4.2. 实现链式存储结构的线性表- 定义数据结构- 实现插入、删除、查找等操作4.3. 实现栈和队列的顺序存储结构和链式存储结构- 定义数据结构- 实现入栈、出栈、入队、出队操作4.4. 实现二叉树的顺序存储结构和链式存储结构- 定义数据结构- 实现插入、删除、查找等操作4.5. 实现图的邻接矩阵和邻接表表示- 定义数据结构- 实现插入、删除、查找等操作5. 实验结果与分析通过对以上实验内容的实现和操作，得到了以下实验结果与分析： 5.1. 顺序存储结构的线性表- 实现了线性表的插入、删除、查找等操作- 通过实验数据进行性能分析，得出了相应的性能指标5.2. 链式存储结构的线性表- 实现了线性表的插入、删除、查找等操作- 通过实验数据进行性能分析，得出了相应的性能指标5.3. 栈和队列的顺序存储结构和链式存储结构- 实现了栈和队列的入栈、出栈、入队、出队操作- 通过实验数据进行性能分析，得出了相应的性能指标5.4. 二叉树的顺序存储结构和链式存储结构- 实现了二叉树的插入、删除、查找等操作- 通过实验数据进行性能分析，得出了相应的性能指标5.5. 图的邻接矩阵和邻接表表示- 实现了图的插入、删除、查找等操作- 通过实验数据进行性能分析，得出了相应的性能指标6. 总结与展望通过本次数据结构课程的实验，我们深入了解并掌握了数据结构的基本概念、操作和应用。

实验四顺序栈的操作一.实验目的掌握顺序栈的基本操作：初始化栈、判栈空、入栈、出栈、取栈顶数据元素等运算及程序实现方法。

二.实验内容（1）定义栈的顺序存取结构。

（2）分别定义顺序栈的基本操作（初始化栈、判栈空、入栈、出栈等）。

（3）设计一个测试主函数进行测试。

三.实验要求（1）根据实验内容编写程序，上机调试并获得运行结果（2）撰写实验报告四.准备工作本次实验将会建立下图所示顺序栈，并会根据此顺序栈进行新增，删除等操作五.关键操作思路与算法(1)定义顺序栈利用顺序存储方式实现的栈称为顺序栈。

栈中的数据元素可用一个预设的足够长度的一维数组来实现:datatype data［MAXNUM］，栈底位置一般设置在数组的低端处，在整个进栈和出栈的过程中不改变，而栈顶位置将随着数据元素进栈和出栈而变化，为了指明当前栈顶在数组中的位置，一般用top作为栈顶指针，算法如下；1.#define MAXNUM 1002.typedef int datatype;3.4.typedef struct{5. datatype data[MAXNUM];6.int top;7.}SeqStack;(2)置空栈算法思路；(1)向系统申请栈空间(2)初始化栈顶指针top，置空栈标志top=-1算法如下；1.void StackSetNull(SeqStack *s)2.{3. s->top=-1;4.}（3）判断是否为空栈算法如下；1.//判断栈是否为空2.int StackIsEmpty(SeqStack *s)3.{4.if(s->top == -1)5.return TRUE;6.else7.return FALSE;8.}9.}（4）入栈算法思路；（1）判断当前栈空间是否已满，若已满，则返回0，未满则转第（2步）（2）栈顶指针top++（3）将元素赋值到top所指位置作为新的栈顶元素，成功返回值1.算法如下；1.//进栈2.int StackPush(SeqStack *s,datatype x)3.{4.if(s->top==MAXNUM-1)5. {6. printf("栈上溢出!\n");7.return FALSE;8. }9.else10. {11. s->top=s->top+1;12. s->data[s->top]=x;13.return TRUE;14. }15.}（五）出栈算法思路；（1）判断当前栈空间是否为空，若为空，则返回0，不为空则转第（2步）（2）将top指针所指位置元素值取出（3）栈顶指针top--指向新的栈顶元素，成功返回值1.算法如下；1.//出栈2.int StackPop(SeqStack *s,datatype *x)3.{4.if(s->top==-1)5. {6. printf("栈下溢出!\n");7.return FALSE;8. }9.else10. {11. * x=s->data[s->top];12.//s->top=s->top-1;13. s->top --;14.return TRUE;15. }16.}（六）读栈顶元素算法如下；1.//读栈顶2.datatype StackGetTop(SeqStack *s)3.{4.if(s->top==-1)5. {6. printf("栈下溢出!\n");7.return FALSE;8. }9.else10.return (s->data[s->top]);11.}六.注意事项（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>|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>|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<n;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-S.base;i++){S.top--;printf("%5d",*S.top);}printf("\n");}库函数* Base.h (程序名) */#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等 */#include<limits.h> /* INT_MAX等 */#include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */ #include<process.h> /* 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=");scanf("%d",&n);printf("请输入%d个数据\n",n);i=0;scanf("%d",&S->data);for(i=1;i<n;++i){P=(LinkStack)malloc(sizeof(SNode)); /* 生成新结点 */P->next=S;S=P;scanf("%d",&S->data); /* 输入元素值 */}return S;}入栈函数LinkStack Push(LinkStack S,int e){LinkStack P;if(S==NULL)return ERROR;P=(LinkStack)malloc(sizeof(SNode));P->data=e;P->next=S;S=P;return S;}出栈函数LinkStack Pop(LinkStack S){LinkStack P,Q;P=S;S=S->next;free(P);return S;}输出函数void Print_Stack(LinkStack S){while(S){printf("%5d",S->data);S=S->next;}printf("\n");}库函数* Base.h (程序名) */#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等 */#include<limits.h> /* INT_MAX等 */#include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */#include<process.h> /* 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四调试分析:输出函数用了语句S->next!=NULL改正：语句S！=NULL五用户手册:看提示内容六测试结果线性栈：1）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=1，请输入插入元素的值e=6，执行入栈操作后的线性栈为6 4 3 2 1 2）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=2,执行出栈操作后的线性栈为3 2 1链栈：1）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=1，请输入插入元素的值e=6，执行入栈操作后的线性栈为6 4 3 2 1 2）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=2,执行出栈操作后的线性栈为3 2 1。

实验一顺序表基本操作的实现与应用顺序表的运算·create(sqlist A)：创建顺序表A，并返回其中的元素个数。

·disp(sqlist A,int n)：输出一个具有n个元素的顺序表A。

·ins(sqlist A,int n, int i,elemtype x)：在顺序表A的第i个元素前插入一个元素x。

若i=0，则新元素作为第1个元素；若i=n，则插入在顺序表的最后。

·del(sqlist A, int n, int i)：在顺序表A中删除第i个元素。

·find(sqlist A, int n, elemtype x)：在一个有n个元素的顺序表A中查找元素值为x 的元素。

一、【实验目的】掌握线性表在顺序存储下的插入与删除等基本运算二、【实验内容】1、设计顺序表的基本运算算法。

2、编写一个算法实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储（假设这两个有序顺序表中没有相同的元素）。

3、请编写26个字母按特定字母值插入或删除的完整程序。

三、【源程序及运行结果】实验二单链表基本操作的实现与应用单链表单链表节点的类型定义如下：typedef int elemtype; //定义数据域的类型typedef struct linknode{ //定义节点类型elemtype data;struct linknode *next;} linknode;单链表的运算·create()：创建单链表，由用户输入各节点data 域的值，以0表示输入结束，最后返回建立的单链表的头指针。

·disp(nodetype *h)：输出单链表h的所有节点的data 域的值。

·len(nodetype *h)：返回单链表h的长度。

·find(nodetype *h,int i)：返回单链表h中第i个节点的指针。

数据结构实验报告报告名称栈的应用专业网络工程班级1001学号************姓名张剑指导教师陈淑红李珍辉黄哲2012 年5 月4日一、实验目的：熟练掌握栈的基本操作，进一步理解栈的应用。

二、实验内容与基本要求：实验内容：设计一个程序，用算符优先法对算术表达式求值基本要求：以字符序列的形式从终端输入语法正确的、不含变量的算术表达式，利用算符优先关系，实现对算术四则混合运算表达式求值。

三、实现提示：1．利用栈辅助分析算符优先关系；2．在读入表达式字符序列的同时，完成运算符和操作数的识别处理，以及相应的运算；3．在识别出操作数的同时，要将其字符序列形式转换成相应的浮点数形式。

四．概要设计：1.顺序栈的定义：typedef struct{SElemType *base;SElemType *top;int stacksize;} SqStack;2.栈的基本操作：InitStack(&S)操作结果：构造一个空栈S。

DestoryStack（&S）初始条件：栈S存在。

、操作结果：栈S被销毁。

ClearStack(&S)初始条件：栈S存在。

、操作结果：将S清为空栈。

StackEmpty（&S）初始条件：栈S存在。

、操作结果：若S为空栈，则返回TUUE，否则FALSE.StackLength(&S)初始条件：栈S存在。

、操作结果：返回S的元素个数，即栈的长度。

GetTop（S,&e）初始条件：栈S存在且非空。

操作结果：用e 返回S的栈顶元素。

Push（&S，e）初始条件：栈S存在。

、操作结果：插入元素e为新的栈顶元素。

pop (&s,&e)初始条件：栈S存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。

StackTravse(S,vist())初始条件:栈S存在且非空.操作结果:从栈底到栈顶依次对S的每个元素调用函数vist()，一旦vist()失败，择操作结束。

北方民族大学课程设计课程名称:数据结构与算法院(部)名称:信息与计算科学学院组长姓名学号同组人员姓名指导教师姓名:纪峰设计时间:2010.6.7----2009.6.27一、《数据结构与算法》课程设计参考题目（一）参考题目一（每位同学选作一个,同组人员不得重复）1、编写函数实现顺序表的建立、查找、插入、删除运算。

2、编写函数分别实现单链表的建立、查找、插入、删除、逆置算法。

3、编写函数实现双向链表的建立、插入、删除算法。

4、编写函数实现顺序栈的进栈、退栈、取栈顶的算法。

5、编写函数实现链栈的进栈、退栈、取栈顶的算法。

6、编写函数实现双向顺序栈的判空、进栈、出栈算法。

7、编写函数实现循环队列的判队空、取队头元素、入队、出队算法。

8、编写函数实现链环队列的判队空、取队头节点、入队、出队算法。

9、编写函数实现串的，求串长、连接、求字串、插入、删除等运算。

10、分别实现顺序串和链串的模式匹配运算。

11、实现二叉树的建立，前序递归遍历和非递归遍历算法。

12、实现二叉树的建立，中序递归遍历和非递归遍历算法。

13、实现二叉树的建立，后序递归遍历和非递归遍历算法。

14、实现二叉树的中序线索化，查找*p结点中序下的前驱和后继结点。

15、分别以临接表和邻接矩阵作为存储就够实现图的深度优先搜索和广度优先搜索算法。

16、利用线性探测处理冲突的方法实现散列表的查找和插入算法。

(二)参考题目二（每三人一组，任选三个题目完成）1.运动会分数统计（限1人完成）任务：参加运动会有n个学校，学校编号为1……n。

比赛分成m个男子项目，和w个女子项目。

项目编号为男子1……m，女子m+1……m+w。

不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。

（m<=20,n<=20）功能要求：1)可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号或名称、学校总分、男女团体总分排序输出；4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。

堆栈实验报告堆栈实验报告一、引言堆栈（Stack）是一种常见的数据结构，它遵循先进后出（Last-In-First-Out，LIFO）的原则。

在计算机科学中，堆栈常用于函数调用、表达式求值、递归算法等领域。

本实验旨在通过实际操作，深入理解堆栈的定义、特性以及应用。

二、实验目的1. 理解堆栈的概念和特性；2. 掌握堆栈的基本操作：入栈和出栈；3. 实现堆栈的数据结构，并进行相关操作；4. 分析堆栈在实际应用中的作用和意义。

三、实验方法1. 设计堆栈的数据结构：堆栈可以使用数组或链表实现，本实验选择使用数组实现；2. 实现堆栈的基本操作：包括入栈和出栈；3. 编写测试程序：验证堆栈的功能和正确性；4. 进行实验操作：通过不同的测试用例，观察堆栈的行为和变化。

四、实验步骤1. 定义堆栈的数据结构：使用数组作为底层存储结构，同时定义一个指针top 来指示栈顶元素的位置；2. 实现入栈操作：将元素插入栈顶，并更新top指针；3. 实现出栈操作：删除栈顶元素，并更新top指针；4. 编写测试程序：包括对入栈和出栈操作的测试，以及对堆栈的边界条件进行测试；5. 进行实验操作：根据测试程序的结果，观察堆栈的行为和变化。

五、实验结果与分析1. 入栈操作：通过多次入栈操作，观察栈顶元素的变化，验证入栈的正确性；2. 出栈操作：通过多次出栈操作，观察栈顶元素的变化，验证出栈的正确性；3. 边界条件测试：测试空栈的出栈操作，以及满栈的入栈操作，观察程序的响应和错误处理；4. 实验结果分析：根据实验结果，分析堆栈的特性和应用场景，如函数调用、表达式求值等。

六、实验心得通过本次实验，我深入理解了堆栈的概念和特性。

通过实际操作，我掌握了堆栈的基本操作，并成功实现了堆栈的数据结构。

在测试过程中，我发现堆栈在实际应用中具有重要作用，特别是在函数调用和表达式求值等场景下。

堆栈的先进后出特性，可以有效地管理函数调用的上下文和保存临时数据，提高程序的执行效率。