下载文档原格式
数据结构实验指导书（C++）-栈、队列、串的操作实验二栈、队列、串的操作实验类型：验证性实验要求：必修实验学时： 2学时一、实验目的：参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。
二、实验要求：1、掌握栈、队列、串的特点。
掌握特殊线性表的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：1. 堆栈类测试和应用问题。
要求：(1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。
测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。
(2)定义数据元素的数据类型为如下形式的结构体：typedef struct{ char taskname[10];//任务名int taskno; //任务号｝DataType；设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。
2. 队列类测试和应用问题。
要求：设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。
3．设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S, T)。
要求比较结果有大于、等于和小于三种情况。
*4. 设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。
*5. 设计串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回０。
并要求设计主函数进行测试。
一个测试例子为：S＝”I am a student”，T=”student”，V=”teacher “。
实验一顺序表的基本操作一、实验目的掌握线性表的顺序表基本操作：建立、插入、删除、查找、合并、打印等运算。
二、实验要求包含有头文件和main函数；1.格式正确，语句采用缩进格式；2.设计子函数实现题目要求的功能；3.编译、连接通过，熟练使用命令键；4.运行结果正确，输入输出有提示，格式美观。
三、实验设备、材料和工具1.奔腾2计算机或以上机型2.turboc2,win-tc四、实验内容和步骤1. 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。
2. 往该顺序表中第i位置插入一个值为x的数据元素。
3. 从该顺序表中第j位置删除一个数据元素，由y返回。
4. 从该顺序表中查找一个值为e的数据元素，若找到则返回该数据元素的位置，否则返回“没有找到”。
五、程序#include<stdio.h>#include<stdlib.h>#define list_init_size 10#define increment 2typedef struct {int *elem;int length,listsize;}sqlist; //类型定义void initlist_sq(sqlist &L) //初始化顺序表{ }void output(sqlist L) //输出顺序表{ }void insertlist(sqlist &L,int i, int x) //顺序表中插入x{ }void deletelist(sqlist &L,int j, int y) //顺序表中删除y{ }int locateelem(sqlist &L,int e) //顺序表中查找e{ }void main(){ }【运行结果】void initlist_sq(sqlist &L) //初始化顺序表{L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem) exit (OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;}void output(sqlist L) //输出顺序表{for(int i=0;i<=L.length-1;i++)printf("%d,",L.elem[i]);return OK;}void insertlist(sqlist &L,int i, int x) //顺序表中插入x{int p,q;if(i<1||i>L.length+1)return ERROR;if(L.length>=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbasde)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1];for(p=&(L.elem[L.length-1]);p>=q;--p*(p+1)=*p;*p=x;++L.length;return ok;}void deletelist(sqlist &L,int j, int y) //顺序表中删除y{int p,q;if(i<1||I>L.length+1) return ERROR;p=&(L.elem[i-1]);y=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;return ok;}int locateelem(sqlist &L,int e) //顺序表中查找e { int p;i=1;p=L.elem;while(i<=L.length&&!(*p++,e))++i;if(i<=L.length) return i;else return 0;}void main(){int d,p,a,b;int c;initlist_sq(&L);output( L);insertlist( &L, d, a);deletelist( &L, p, b);locateelem( &L, c);}。
实验一线性表操作一、实验目的1熟悉并掌握线性表的逻辑结构、物理结构。
2熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。
3熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。
4熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。
二、实验要求1实验之前认真准备，编写好源程序。
2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。
三、实验内容基本题:1对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。
加强、提高题：2、编写一个求解Josephus问题的函数。
用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人。
然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。
最后分析所完成算法的时间复杂度。
定义JosephusCircle类，其中含完成初始化、报数出圈成员函数、输出显示等方法。
（可以选做其中之一）加强题：（1）采用数组作为求解过程中使用的数据结构。
提高题：（2）采用循环链表作为求解过程中使用的数据结构。
运行时允许指定任意n、s、m数值，直至输入n = 0退出程序。
实验二栈、队列、递归应用一、实验目的1熟悉栈、队列这种特殊线性结构的特性2熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。
二、实验要求1实验之前认真准备，编写好源程序。
2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。
三、实验内容基本题（必做）：1分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。
2、假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。
加强题：3设线性表A中有n个字符，试设计程序判断字符串是否中心对称，例如xyzyx和xyzzyx都是中心对称的字符串。
《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。
2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。
二、实验内容√ 1、单链表的表示与操作实现 ( * )2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。
2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。
3、严格按照数据结构实验报告模板和规范，及时完成实验报告。
四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode{ DataType data;struct LNode *next;}LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit( ){ // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }3、清空单链表void LinkedListClear(LinkedList L){// 每个模块或函数应加注释，说明函数功能、入口及出口参数}4、检查单链表是否为空int LinkedListEmpty(LinkedList L){ …. }5、遍历单链表void LinkedListTraverse(LinkedList L){….}6、求单链表的长度int LinkedListLength(LinkedList L){ …. }7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i){ //L是带头结点的链表的头指针，返回第 i 个元素 }8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedList LinkedListLocate(LinkedList L, DataType x){ …… }9、向单链表中插入元素void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法// 在链表中第i 个结点之前插入新的元素 x}10、从单链表中删除元素void LinkedListDel(LinkedList L,DataType x){ // 删除以 L 为头指针的单链表中第 i 个结点 }11、用尾插法建立单链表LinkedList LinkedListCreat( ){ …… }㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结五、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。
数据结构实验指导书一、实验目的数据结构是计算机科学中的重要基础课程，通过实验，旨在帮助学生更好地理解和掌握数据结构的基本概念、原理和算法，提高学生的编程能力和问题解决能力。
具体而言，实验的目的包括：1、加深对常见数据结构（如数组、链表、栈、队列、树、图等）的理解，掌握其特点和操作方法。
2、培养学生运用数据结构解决实际问题的能力，提高算法设计和程序实现的能力。
3、增强学生的逻辑思维能力和调试程序的能力，培养学生的创新意识和团队合作精神。
二、实验环境1、操作系统：Windows 或 Linux 操作系统。
2、编程语言：C、C+＋、Java 等编程语言中的一种。
3、开发工具：如 Visual Studio、Eclipse、Code:：Blocks 等集成开发环境（IDE）。
三、实验要求1、实验前，学生应认真预习实验内容，熟悉相关的数据结构和算法，编写好实验程序的代码框架。
2、实验过程中，学生应独立思考，认真调试程序，及时记录实验过程中出现的问题及解决方法。
3、实验完成后，学生应撰写实验报告，包括实验目的、实验内容、实验步骤、实验结果、问题分析与解决等。
四、实验内容（一）线性表1、顺序表的实现与操作实现顺序表的创建、插入、删除、查找等基本操作。
分析顺序表在不同操作下的时间复杂度。
2、链表的实现与操作实现单链表、双向链表的创建、插入、删除、查找等基本操作。
比较单链表和双向链表在操作上的优缺点。
（二）栈和队列1、栈的实现与应用实现顺序栈和链式栈。
利用栈解决表达式求值、括号匹配等问题。
2、队列的实现与应用实现顺序队列和链式队列。
利用队列解决排队问题、广度优先搜索等问题。
（三）树1、二叉树的实现与遍历实现二叉树的创建、插入、删除操作。
实现二叉树的前序、中序、后序遍历算法，并分析其时间复杂度。
2、二叉搜索树的实现与操作实现二叉搜索树的创建、插入、删除、查找操作。
分析二叉搜索树的性能。
（四）图1、图的存储结构实现邻接矩阵和邻接表两种图的存储结构。
《数据结构和算法》实验指导书实验及学时数分配序号实验名称学时数（小时）1 实验一线性表 42 实验二树和二叉树 23 实验三图 24 实验四查找 25 实验五内部排序 2合计12几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。
二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。
上机时签到；下机时验收签字。
三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。
实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。
若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。
1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。
南京工程学院实验报告<班级>_<学号>_<实验X>.RAR文件形式交付指导老师。
一、实验目的1.熟悉上机环境，进一步掌握语言的结构特点。
2.掌握线性表的顺序存储结构的定义及实现。
3.掌握线性表的链式存储结构——单链表的定义及实现。
4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。
5.掌握线性表在链式存储结构——单链表中的各种基本操作。
二、实验内容1.顺序线性表的建立、插入及删除。
2.链式线性表的建立、插入及删除。
三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。
2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。
3.建立一个带头结点的单链表，结点的值域为整型数据。
要求将用户输入的数据按尾插入法来建立相应单链表。
四、程序主要语句及作用程序1的主要代码(附简要注释)public struct sequenlist{public const int MAXSIZE=1024; /*最大值为1024*/public elemtype[] vec;public int len; /* 顺序表的长度 */public sequenlist( int n){vec=new elemtype[MAXSIZE ];len = n;}};class Program{static void Main(string[] args){sequenlist list1 = new sequenlist(5);for (int i = 0; i < 5; i++){list1.vec[i] = i;}for (int i = 0; i < 5; i++){Console.Write("{0}---", list1.vec[i]) ;}Console.WriteLine("\n");Console.WriteLine("表长：{0}\n",list1.len );Console.ReadKey();}}程序2的主要代码(附简要注释)public void insertlist(int i, int x){if (len >= MAXSIZE)throw new Exception("上溢"); /*长度大于最大值则抛出异常*/if (i < 1 || i > len + 1)throw new Exception("位置");/插入位置小于1或大于len+1则抛出插入位置错误的异常for (int j = len; j >= i; j--)vec[j] = vec[j - 1]; //注意第j个元素存在数组下标为j-1处vec[i - 1] = x;len++;}};class Program{static void Main(string[] args){sequenlist list2 = new sequenlist(7);list2.vec[0] = 21;list2.vec[1] = 23;list2.vec[2] = 14;list2.vec[3] = 5;list2.vec[4] = 56;list2.vec[5] = 17;list2.vec[6] = 31;Console.Write("请输入第i个位置插入元素：");int loc =Convert.ToInt32( Console.ReadLine());Console.Write("请输入第{0}个位置插入的元素：", loc);int ele = Convert.ToInt32(Console.ReadLine());Console.WriteLine("插入前的线性表：");for (int i = 0; i < list2.len ; i++){Console.Write("{0}---", list2.vec[i]);}Console.WriteLine("\n");list2.insertlist(loc, ele);Console.WriteLine("插入后的线性表：");for (int i = 0; i < list2.len ; i++){Console.Write("{0}---", list2.vec[i]);}Console.WriteLine("\n");Console.ReadKey();}}程序3的主要代码(附简要注释)class Node{private int num;public int Num{set { num = value; }/输入值get { return num; }/获得值}private Node next;public Node Next{set { next = value; }get { return next; }}}class Pp{static void Main(string[] args){Node head;Node tempNode, tempNode1;int i;head = new Node();Console.WriteLine("输入六项数据：\n");Console.Write("输入第1项数据:");head.Num = Convert.ToInt32(Console.ReadLine());head.Next = null;tempNode = head;for (i = 1; i < 6; i++){tempNode1 = new Node();Console.Write("输入第{0}项数据:",i+1);tempNode1.Num = Convert.ToInt32(Console.ReadLine());/插入项转换为整形数值 tempNode1.Next = null;tempNode.Next = tempNode1;tempNode = tempNode.Next;}Console.WriteLine("线性表:");tempNode = head;for (i = 0; i < 6; i++){Console.Write("{0}", tempNode.Num);if (i < 5){Console.Write("--");}tempNode = tempNode.Next;}Console.ReadKey();}}五、程序运行结果截图程序1程序2程序3六、收获，体会及问题(写得越详细、越个性化、越真实越好，否则我不知道你做这个实验的心路历程，也就无法充分地判断你是否是独立完成的这个实验、你是否在做这个实验时进行了认真仔细地思考、通过这个实验你是否在实践能力上得到了提高)这次试验刚开始做时完全不知道从哪下手，才刚上了几节课，对于线性表、链式表都不是理解的很透彻，不知道用哪个软件编写程序。
数据结构实验报告一、实验目的数据结构是计算机科学中重要的基础课程，通过本次实验，旨在深入理解和掌握常见数据结构的基本概念、操作方法以及在实际问题中的应用。
具体目的包括：1、熟练掌握线性表（如顺序表、链表）的基本操作，如插入、删除、查找等。
2、理解栈和队列的特性，并能够实现其基本操作。
3、掌握树（二叉树、二叉搜索树）的遍历算法和基本操作。
4、学会使用图的数据结构，并实现图的遍历和相关算法。
二、实验环境本次实验使用的编程环境为具体编程环境名称，编程语言为具体编程语言名称。
三、实验内容及步骤（一）线性表的实现与操作1、顺序表的实现定义顺序表的数据结构，包括数组和表的长度等。
实现顺序表的初始化、插入、删除和查找操作。
2、链表的实现定义链表的节点结构，包含数据域和指针域。
实现链表的创建、插入、删除和查找操作。
（二）栈和队列的实现1、栈的实现使用数组或链表实现栈的数据结构。
实现栈的入栈、出栈和栈顶元素获取操作。
2、队列的实现采用循环队列的方式实现队列的数据结构。
完成队列的入队、出队和队头队尾元素获取操作。
（三）树的实现与遍历1、二叉树的创建以递归或迭代的方式创建二叉树。
2、二叉树的遍历实现前序遍历、中序遍历和后序遍历算法。
3、二叉搜索树的操作实现二叉搜索树的插入、删除和查找操作。
（四）图的实现与遍历1、图的表示使用邻接矩阵或邻接表来表示图的数据结构。
2、图的遍历实现深度优先遍历和广度优先遍历算法。
四、实验结果与分析（一）线性表1、顺序表插入操作在表尾进行时效率较高，在表头或中间位置插入时需要移动大量元素，时间复杂度较高。
删除操作同理，在表尾删除效率高，在表头或中间删除需要移动元素。
2、链表插入和删除操作只需修改指针，时间复杂度较低，但查找操作需要遍历链表，效率相对较低。
（二）栈和队列1、栈栈的特点是先进后出，适用于函数调用、表达式求值等场景。
入栈和出栈操作的时间复杂度均为 O(1)。
2、队列队列的特点是先进先出，常用于排队、任务调度等场景。
《数据结构与算法》实验指导书实验及学时数分配几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。
二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。
上机时签到；下机时验收签字。
三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。
实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。
若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。
1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。
（从键盘接受删除元素位置i，实现删除；显示删除后的线性表）二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素。
《数据结构》实验指导及实验报告栈和队列实验四栈和队列⼀、实验⽬的1、掌握栈的结构特性及其⼊栈，出栈操作；2、掌握队列的结构特性及其⼊队、出队的操作，掌握循环队列的特点及其操作。
⼆、实验预习说明以下概念1、顺序栈：2、链栈：3、循环队列：4、链队三、实验内容和要求1、阅读下⾯程序，将函数Push和函数Pop补充完整。
要求输⼊元素序列1 2 3 4 5 e，运⾏结果如下所⽰。
#include#include#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存储空间初始分配量*/#define STACKINCREMENT 5 /*存储空间分配增量*/typedef int ElemType; /*定义元素的类型*/typedef struct{ElemType *base; /*定义栈底部指针*/ElemType *top; /*定义栈顶部指针*/int stacksize; /*当前已分配的存储空间*/}SqStack;int InitStack(SqStack *S); /*构造空栈*/int push(SqStack *S,ElemType e); /*⼊栈操作*/int Pop(SqStack *S,ElemType *e); /*出栈操作*/int CreateStack(SqStack *S); /*创建栈*/void PrintStack(SqStack *S); /*出栈并输出栈中元素*/int InitStack(SqStack *S){S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR;S->top=S->base;int Push(SqStack *S,ElemType e){if(S->top-S->base>=S->stacksize){S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType)); S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top++=e;return 1}/*Push*/int Pop(SqStack *S,ElemType *e){if(S->top!=S->base){*e=*--S->top;return 1;}elsereturn 0;}/*Pop*/int CreateStack(SqStack *S){int e;if(InitStack(S))printf("Init Success!\n");else{printf("Init Fail!\n");return ERROR;}printf("input data:(Terminated by inputing a character)\n"); while(scanf("%d",&e))Push(S,e);return OK;}/*CreateStack*/while(Pop(S,&e))printf("%3d",e);}/*Pop_and_Print*/int main(){SqStack ss;printf("\n1-createStack\n");CreateStack(&ss);printf("\n2-Pop&Print\n");PrintStack(&ss);return 0;}●算法分析：输⼊元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么特性？2、在第1题的程序中，编写⼀个⼗进制转换为⼆进制的数制转换算法函数（要求利⽤栈来实现），并验证其正确性。
顺序表的基本操作#include<iostream>using namespace std;typedef int datatype;#define maxsize 1024#define NULL -1typedef struct {datatype *data;int last;}sequenlist;void SETNULL(sequenlist &L) {L.data=new datatype[maxsize];for(int i=0;i<maxsize;i++)L.data[i]=NULL;}void INITIALIZE(sequenlist &L) {cout<<"请输入结点个数："<<endl;cin>>st;cout<<"请输入"<<st<<"个初始值："<<endl;for(int i=0;i<st;i++)cin>>L.data[i];}int LENGTH(sequenlist &L) {int i=0;while(L.data[i]!=NULL)i++;return i;}datatype GET(sequenlist &L,int i) {if(i<1||i>st) {cout<<"error1"<<endl;return NULL;}elsereturn L.data[i-1];}int LOCATE(sequenlist &L,datatype x) {int j=0;while(L.data[j]!=x)j++;if(j==st) {cout<<"所查找值不存在！"<<endl;return NULL;}elsereturn (j+1);}int INSERT(sequenlist &L,datatype x,int i) { int j;if(st>=maxsize-1) {cout<<"overflow";return NULL;}elseif(i<1||(i>st)) {cout<<"error2"<<endl;return NULL;}else{for(j=(st);j>=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=x;st++;}return 1;}int DELETE(sequenlist &L,int i) {int j;if((i<1)||(i>st+1)) {cout<<"error3"<<endl;return NULL;}else {for(j=i;j<=st;j++)L.data[j-1]=L.data[j];st--;}return 1;}int main() {sequenlist L;datatype x=5;int i=4;SETNULL(L);INITIALIZE(L);int a=LENGTH(L);cout<<"线性表中的结点个数为："<<a<<endl;datatype b=GET(L,i);cout<<"线性表中第"<<i<<"个结点为："<<b<<endl;int c=LOCATE(L,x);cout<<"值为"<<x<<"的结点位置为："<<c<<endl;int d=INSERT(L,x,i);cout<<"插入新结点后的线性表："<<endl;for(int j=0;j<st;j++)cout<<L.data[j]<<" ";cout<<endl;int e=DELETE(L,i);cout<<"删除一个结点后的线性表："<<endl;for(int j=0;j<st;j++)cout<<L.data[j]<<" ";cout<<endl;return 0;}单链表的基本操作#include<iostream>using namespace std;typedef char datatype;typedef struct node {datatype data;struct node *next;}linklist;linklist *CREATLISTF() {cout<<"请输入字符并以ENTER键结束"<<endl;char ch;linklist *head,*s;head=(linklist*)malloc(sizeof(linklist));head=NULL;ch=getchar();while(ch!='\n') {s=(linklist*)malloc(sizeof(linklist));s->data=ch;s->next=head;head=s;ch=getchar();}return head;}/*头插法建表*/linklist *CREATLISTR() {cout<<"请输入字符并以ENTER键结束"<<endl;char ch;linklist *head,*s,*r;head=NULL;r=NULL;ch=getchar();while(ch!='\n') {s=(linklist*)malloc(sizeof(linklist));s->data=ch;if(head==NULL)head=s;elser->next=s;r=s;ch=getchar();}if(r!=NULL)r->next=NULL;return head;}/*尾插法建表*/linklist *GET(linklist *head,int i) {int j;linklist *p;p=head;j=1;while((p->next!=NULL)&&(j<i)) {p=p->next;j++;}if(i==j)return p;elsereturn NULL;}/*按序号查找*/linklist *LOCATE(linklist *head,datatype key) { linklist *p;p=head;while(p!=NULL)if(p->data!=key)p=p->next;elsebreak;return p;}/*按值查找*/void INSERTAFTER(linklist *p,datatype x) { linklist *s;s=(linklist*)malloc(sizeof(linklist));s->data=x;s->next=p->next;p->next=s;}/*后插操作*/void INSERTBEFORE(linklist *p,datatype x) { linklist *s;s=(linklist*)malloc(sizeof(linklist));s->data=p->data;s->next=p->next;p->data=x;p->next=s;}/*前插操作*/void DELETEAFTER(linklist *p) {linklist *r;r=p->next;p->next=r->next;free(r);}/*删除运算*/int LENGTH(linklist *head) {int i;for(i=1;head->next!=NULL;i++)head=head->next;return i;}/*长度运算*/void SETNULL(linklist *head) {linklist *p,*q;p=head;while(p->next!=NULL) {q=p;p=p->next;free(q);}head->next=NULL;}/*置空表*/void PRINTLIST(linklist *head) {linklist *r;r=head;while((r->next)!=NULL) {putchar(r->data);r=r->next;}putchar(r->data);cout<<endl;}/*输出链表*/void main() {linklist *head1,*head21,*p,*q,*r1;int i=4;datatype key='c',x='h';head1=CREATLISTF();PRINTLIST(head1);head21=CREATLISTR();PRINTLIST(head21);r1=head1->next->next->next->next;p=GET(head1,i);cout<<"head1中第"<<i<<"个结点为："<<p->data<<endl;q=LOCATE(head1,key);cout<<"值为"<<key<<"的结点为："<<q->data<<endl;INSERTAFTER(r1,x);PRINTLIST(head1);INSERTBEFORE(r1,x);PRINTLIST(head1);DELETEAFTER(r1);PRINTLIST(head1);int j=LENGTH(head1);cout<<"单链表长度为："<<j<<endl;SETNULL(head1);j=LENGTH(head1);cout<<j<<endl;PRINTLIST(head1);}顺序队列的基本操作#include<iostream>using namespace std;typedef int datatype;#define maxsize 64#define NULL -1typedef struct {datatype *data;int front,rear;}sequeue;void SETNULL(sequeue &sq) {sq.data=new datatype[maxsize];sq.front=-1;sq.rear=-1;}/*置空队*/int EMPTY(sequeue &sq) {if(sq.rear==sq.front)return 1;elsereturn 0;}/*判队空*/datatype FRONT(sequeue &sq) {if(EMPTY(sq)) {cout<<"queue is empty"<<endl;return NULL;}elsereturn sq.data[(sq.front+1)%maxsize]; }/*取队头元素*/int ENQUEUE(sequeue &sq,datatype x) { if(sq.front==(sq.rear+1)%maxsize) {cout<<"queue is full"<<endl;return NULL;}else {sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x;return 1;}}/*入队*/datatype DEQUEUE(sequeue &sq) {if(EMPTY(sq)) {cout<<"queue is empty"<<endl;return NULL;}else {sq.front=(sq.front+1)%maxsize;return sq.data[sq.front];}}/*出队*/void PRIQUEUE(sequeue &sq) {int i;for(i=sq.front+1;i<=(sq.rear)%maxsize;i++) cout<<sq.data[i%maxsize]<<" ";cout<<endl;}/*输出队列*/int LENQUEUE(sequeue &sq) {return(sq.rear-sq.front);}/*队列长度*/int main() {sequeue sq;int lenth,i;datatype j,x;SETNULL(sq);cout<<"请输入队列元素个数："<<endl;cin>>lenth;cout<<"请输入队列初始元素："<<endl;for(i=0;i<lenth;i++) {cin>>x;j=ENQUEUE(sq,x);}PRIQUEUE(sq);j=DEQUEUE(sq);PRIQUEUE(sq);cout<<"判断队列是否为空："<<EMPTY(sq)<<endl;cout<<"队头元素为："<<FRONT(sq)<<endl;cout<<"队列长度为："<<LENQUEUE(sq)<<endl;SETNULL(sq);cout<<"队列置空后为："<<endl;PRIQUEUE(sq);return 0;}链队列的基本操作#include<iostream>using namespace std;typedef char datatype;typedef struct node {datatype data;struct node *next;}linklist;typedef struct {linklist *front,*rear;}linkqueue;void SETNULL(linkqueue* q) {q->front=(linklist*)malloc(sizeof(linklist));q->front->next=NULL;q->rear=q->front;}/*置空队*/int EMPTY(linkqueue* q) {if(q->front==q->rear)return 1;elsereturn 0;}/*判队空*/datatype FRONT(linkqueue* q) {if(EMPTY(q)) {cout<<"queue is empty"<<endl;return NULL;}elsereturn q->front->next->data;}/*取队头元素*/void ENQUEUE(linkqueue* q,datatype x) {q->rear->next=(linklist*)malloc(sizeof(linklist));q->rear=q->rear->next;q->rear->data=x;q->rear->next=NULL;}/*入队*/datatype DEQUEUE(linkqueue* q) {linklist* s;if(EMPTY(q)) {cout<<"queue is empty"<<endl;return NULL;}else {s=q->front;q->front=q->front->next;free(s);return q->front->data;}}/*出队*/void PRIQUEUE(linkqueue* q) {linklist *r;r=q->front;while(r->next!=NULL) {putchar(r->next->data);r=r->next;}cout<<endl;}/*输出链表*/int main() {linkqueue* q;q=(linkqueue*)malloc(sizeof(linkqueue));datatype x;SETNULL(q);cout<<"请输入初始元素："<<endl;x=getchar();while(x!='\n') {ENQUEUE(q,x);x=getchar();}PRIQUEUE(q);cout<<"被删除的队头元素为："<<DEQUEUE(q)<<endl;PRIQUEUE(q);cout<<"判断队列是否为空："<<EMPTY(q)<<endl;cout<<"队头结点数据为："<<FRONT(q)<<endl;SETNULL(q);cout<<"队列置空后为："<<endl;PRIQUEUE(q);return 0;}顺序栈的基本操作#include<iostream>using namespace std;typedef int datatype;#define maxsize 64#define FALSE 0#define TRUE 1#define NULL -1typedef struct {datatype *data;int top;}seqstack;void SETNULL(seqstack& s) {s.data=new datatype[maxsize];s.top=NULL;}/*置空栈*/int EMPTY(seqstack& s) {if(s.top>=0)return FALSE;elsereturn TRUE;}/*判栈空*/void PUSH(seqstack& s,datatype x) {if(s.top==maxsize-1)cout<<"overflow"<<endl;else {s.top++;s.data[s.top]=x;}}/*进栈*/datatype POP(seqstack& s) {if(EMPTY(s)) {cout<<"underflow"<<endl;return NULL;}else {s.top--;return(s.data[s.top+1]);}}/*出栈*/datatype TOP(seqstack& s) {if(EMPTY(s)) {cout<<"stack is empty"<<endl;return NULL;}elsereturn(s.data[s.top]);}/*取栈顶*/void PRINT(seqstack& s) {int i=0;for(i=s.top;i>=0;i--)cout<<s.data[i]<<" ";cout<<endl;}/*输出栈*/int STACKFULL(seqstack& s) {if(s.top==maxsize)return TRUE;elsereturn FALSE;}/*判栈满*/int main() {seqstack s;int i,LENGTH;datatype x,y,z;SETNULL(s);cout<<"请输入初始值个数："<<endl;cin>>LENGTH;cout<<"请输入初始值："<<endl;for(i=0;i<LENGTH;i++) {cin>>x;PUSH(s,x);}PRINT(s);y=POP(s);cout<<"删除的栈顶元素为："<<y<<endl;PRINT(s);z=TOP(s);cout<<"栈顶元素为："<<z<<endl;cout<<"判断栈是否满："<<STACKFULL(s)<<endl;return 0;}链栈的基本操作#include<iostream>using namespace std;typedef char datatype;#define TRUE 1#define FALSE 0typedef struct node {datatype data;struct node* next;}linkstack;void SETNULLSTACK(linkstack* top) {linkstack *p,*q;p=top;while(p->next!=NULL) {q=p;p=p->next;free(q);}top->next=NULL;}/*置空表*/int EMPTYLSTACK(linkstack* top) {if(top->next==NULL)return TRUE;elsereturn FALSE;}/*判表空*/linkstack* PUSHLSTACK(linkstack* top,datatype x) { linkstack* p;p=(linkstack*)malloc(sizeof(linkstack));p->data=x;p->next=top;return p;}/*输入函数*/linkstack* POPLSTACK(linkstack* top,linkstack* datap) { linkstack* p;if(top->next==NULL) {cout<<"underflow"<<endl;return NULL;}else {datap=top;p=top;top=top->next;free(p);return top;}}/*删除函数*/void PRINTLSTACK(linkstack* top) {linkstack* p;p=top;while(p->next!=NULL) {cout<<p->data<<" ";p=p->next;}cout<<endl;}/*输出函数*/datatype TOPLSTACK(linkstack* top) {return top->data;}/*取栈顶*/int main() {linkstack* top,*d;datatype x;d=(linkstack*)malloc(sizeof(linkstack));top=(linkstack*)malloc(sizeof(linkstack));top->next=NULL;cout<<"请输入初始值并以ENTER键结束："<<endl;x=getchar();while(x!='\n') {top=PUSHLSTACK(top,x);x=getchar();}PRINTLSTACK(top);top=POPLSTACK(top,d);cout<<"删除栈顶元素后为："<<endl;PRINTLSTACK(top);cout<<"判断栈是否为空："<<EMPTYLSTACK(top)<<endl;cout<<"栈顶元素为："<<TOPLSTACK(top)<<endl;SETNULLSTACK(top);cout<<"置空后为："<<endl;PRINTLSTACK(top);return 0;}顺序串的基本操作#include<stdio.h>#define maxsize 32typedef struct {char data[maxsize];int length;}seqstring;void StrAssign(seqstring &str,char cstr[]) {int i;for(i=0;cstr[i]!='\0';i++)str.data[i]=cstr[i];str.length=i;}/*赋值*/int StrLen(seqstring &s) {return s.length;}/*求串长*/void StrCat(seqstring &s,seqstring &t) {int i,j=StrLen(s);for(i=0;i<StrLen(t);i++)s.data[i+j]=t.data[i];s.length=s.length+t.length;}/*联接*/int StrCmp(seqstring &s,seqstring &t) { int i,j;if(s.length>t.length)i=t.length;elsei=s.length;for(j=0;j<i;j++) {if(s.data[j]>t.data[j]) {return 1;break;}if(s.data[j]<t.data[j]) {return -1;break;}}if(j==i||s.length==t.length)return 0;else {if(j==i||s.length>t.length)return 1;else if(j==i||s.length<t.length)return -1;}}/*比较串的大小*/seqstring SubStr(seqstring &s,int i,int j) { seqstring str;int k;str.length=0;if(i<=0||i>s.length||j<0||i+j-1>s.length) { printf("参数不正确\n");return str;}for(k=i-1;k<i+j-1;k++)str.data[k-i+1]=s.data[k];str.length=j;return str;}/*求子串*/seqstring InsStr(seqstring &s1,int i,seqstring &s2) { int j;seqstring str;str.length=0;if(i<=0||i>s1.length+1) {printf("参数不正确\n");return s1;}for(j=0;j<i-1;j++)str.data[j]=s1.data[j];for(j=0;j<s2.length;j++)str.data[i+j-1]=s2.data[j];for(j=i-1;j<s1.length;j++)str.data[s2.length+j]=s1.data[j];str.length=s1.length+s2.length;return str;}/*插入*/seqstring DelStr(seqstring s,int i,int j) {int k;seqstring str;str.length=0;if(i<=0||i>s.length||i+j>s.length+1) {printf("参数不正确\n");return str;}for(k=0;k<i-1;k++)str.data[k]=s.data[k];for(k=i+j-1;k<s.length;k++)str.data[k-j]=s.data[k];str.length=s.length-j;return str;}/*删除*/seqstring RepStr(seqstring &s,int i,int j,seqstring &t) { int k;seqstring str;str.length=0;if(i<=0||i>s.length||i+j-1>s.length) {printf("参数不正确\n");return str;}for(k=0;k<i-1;k++)str.data[k]=s.data[k];for(k=0;k<t.length;k++)str.data[i+k-1]=t.data[k];for(k=i+j-1;k<s.length;k++)str.data[t.length+k-j]=s.data[k];str.length=s.length-j+t.length;return str;}/*置换*/int IndStr(seqstring &s1,seqstring &s2) {int i,j,d=0;for(i=0;i<StrLen(s1)-StrLen(s2)+1;i++) {for(j=0;j<StrLen(s2);j++)if(s1.data[i+j]!=s2.data[j])break;if(j==StrLen(s2)) {d=i+1;break;}}return d;}/*子串定位*/void DispStr(seqstring &s) {int i;if(s.length>0) {for(i=0;i<s.length;i++)printf("%c",s.data[i]);printf("\n");}}void main() {seqstring s,s1,s2,s3,s4;printf("建立串s和串s1\n");StrAssign(s,"ABCDEFGHIJKLMN");StrAssign(s1,"xyz");printf("输出串s:");DispStr(s);printf("串s的长度:%d\n",StrLen(s));printf("在串的第八个字符位置插入串s1而产生串s2\n");s2=InsStr(s,8,s1);DispStr(s2);printf("删除串s第三个字符开始的三个字符而产生串s2\n");s2=DelStr(s,3,3);DispStr(s2);printf("将串s第三个字符开始的六个字符替换成串s1而产生串s2\n");s2=RepStr(s,3,6,s1);DispStr(s2);printf("提取串s的第三个字符开始的十个字符而产生串s3\n");s3=SubStr(s,3,10);DispStr(s3);printf("将串s1和串s2联接起来而产生新的串s1\n");StrCat(s1,s2);DispStr(s1);printf("将串s1和串s2比较之后得结果：%d\n",StrCmp(s1,s2));StrAssign(s4,"xyz");printf("子串s4在主串s2中的位置为：%d\n",IndStr(s2,s4));}十字链表的基本操作#include<iostream>using namespace std;#define smax 16typedef int datatype;typedef struct lnode {int i,j;struct lnode *rptr,*cptr;union {struct lnode *next;datatype v;}uval;}link;link *CREATLINKMAT() {link *p,*q,*l,*cp[smax];int i,j,m,n,t,s;datatype v;cout<<"请输入所创建矩阵的行数，列数以及非零元素个数："<<endl;cin>>m;cin>>n;cin>>t;if(m>n)s=m;elses=n;l=(link*)malloc(sizeof(link));/*建立十字链表头结点*/l->i=m;l->j=n;cp[0]=l;for(m=1;m<=s;m++) { /*建立头结点循环链表*/ p=(link*)malloc(sizeof(link));p->i=0;p->j=0;p->rptr=p;p->cptr=p;cp[m]=p;cp[m-1]->uval.next=p;}cp[s]->uval.next=l;for(n=1;n<=t;n++) {cout<<"请输入一个非零元素的三元组："<<endl;cin>>i;cin>>j;cin>>v;p=(link*)malloc(sizeof(link));p->i=i;p->j=j;p->uval.v=v;q=cp[i];/*以下是将*p结点插入第i行链表中*/while((q->rptr!=cp[i])&&(q->rptr->j<j))q=q->rptr;p->rptr=q->rptr;q->rptr=p;q=cp[j];/*以下是将*p结点插入第j列链表中*/while((q->cptr!=cp[j])&&(q->cptr->i<i))q=q->cptr;p->cptr=q->cptr;q->cptr=p;}return l;}/*创建十字链表*/void INSERT(link *head,int x,int y,datatype t) {if(x<1||x>head->i||y<1||y>head->j)cout<<"error1"<<endl;else {link *p,*q,*r,*s;int i=x,j=y;p=head->uval.next;while(--i)p=p->uval.next;q=p->rptr;s=p;while(q->j<y&&q->j!=0) {s=q;q=q->rptr;}if(q->j==y)q->uval.v=t;else if(q->j>y||q->j==0) {r=(link*)malloc(sizeof(link));r->i=x;r->j=y;r->uval.v=t;s->rptr=r;r->rptr=q;}p=head->uval.next;while(--j)p=p->uval.next;q=p->cptr;s=p;while(q->i<x&&q->i!=0) {s=q;q=q->cptr;}if(q->i>x||q->i==0) {s->cptr=r;r->cptr=q;}}}/*插入结点*/void DELETE1(link *head,int x,int y) { if(x<1||x>head->i||y<1||y>head->j)cout<<"error2"<<endl;else {link *p,*q,*r;int i=x,j=y;p=head->uval.next;while(--i)p=p->uval.next;q=p->rptr;r=p;while(q->j<y&&q->j!=0) {r=q;q=q->rptr;}if(q->j==y)r->rptr=q->rptr;p=head->uval.next;while(--j)p=p->uval.next;q=p->cptr;r=p;while(q->i<x&&q->i!=0) {r=q;q=q->cptr;}if(q->j==x) {r->cptr=q->cptr;free(q);}}}/*按行列删除结点*/void DELETE2(link *head,datatype t) { link *p,*q,*r;p=head->uval.next;while(p!=head) {q=p->rptr;r=p;while(q!=p) {if(q->uval.v==t)r->rptr=q->rptr;r=q;q=q->rptr;}p=p->uval.next;}p=head->uval.next;while(p!=head) {q=p->cptr;r=p;while(q!=p) {if(q->uval.v==t) {r->cptr=q->cptr;free(q);}elser=q;q=q->cptr;}p=p->uval.next;}}/*按值删除结点*/void PRINT(link *head) {cout<<"输出矩阵元素："<<endl;int j=1,i=head->i;link *p,*q;p=head->uval.next;while(i--) {q=p->rptr;while(j!=head->j+1) {if(q->j==j) {cout<<q->uval.v<<" ";q=q->rptr;}elsecout<<"0 ";j++;}j=1;cout<<endl;p=p->uval.next;}}/*输出十字链表*/int main() {link *head;int i,j;datatype v;head=CREATLINKMAT();PRINT(head);cout<<"请输入插入结点的行数，列数和值："<<endl;cin>>i;cin>>j;cin>>v;INSERT(head,i,j,v);PRINT(head);cout<<"请输入删除结点的行数，列数："<<endl;cin>>i;cin>>j;DELETE1(head,i,j);PRINT(head);cout<<"请输入删除结点的值："<<endl;cin>>v;DELETE2(head,v);PRINT(head);return 0;}二叉树的基本操作#include<iostream>using namespace std;typedef char datatype;#define maxsize 64typedef struct node {int ltag,rtag;datatype data;struct node *lchild,*rchild;}bithptr;bithptr *pre;bithptr *Q[maxsize];bithptr *CREATREE() {char ch;int front,rear;bithptr *root,*s;root=NULL;front=1;rear=0;ch=getchar();while(ch!='#') {s=NULL;if(ch!='@') {s=(bithptr*)malloc(sizeof(bithptr));s->data=ch;s->lchild=NULL;s->rchild=NULL;}rear++;Q[rear]=s;if(rear==1)root=s;else {if(s&&Q[front])if(rear%2==0)Q[front]->lchild=s;elseQ[front]->rchild=s;if(rear%2==1)front++;}ch=getchar();}return root;}/*建立二叉树*/void INTHREAD(bithptr *p) {if(p!=NULL) {INTHREAD(p->lchild);if(p->lchild==NULL)p->ltag=1;if(p->rchild==NULL)p->rtag=1;if(pre!=NULL) {if(pre->rtag==1)pre->rchild=p;if(p->ltag==1)p->lchild=pre;}pre=p;INTHREAD(p->rchild);}}/*二叉树线索化*/bithptr *INORDERNEXT(bithptr *p) { bithptr *q;if(p->rtag==1)return(p->rchild);else {q=p->rchild;while(q->ltag!=1)q=q->lchild;return q;}}/*中序后继*/void TRA VERSEINTHREAD(bithptr *p) { if(p!=NULL) {while(p->ltag!=1)p=p->lchild;do {cout<<" "<<p->data;p=INORDERNEXT(p);}while(p!=NULL);}}/*线索中序遍历*/void INSERTRIGHT(bithptr *p,datatype x) { bithptr *s,*q;q=(bithptr*)malloc(sizeof(bithptr));s=INORDERNEXT(p);q->data=x;q->ltag=1;q->lchild=p;q->rtag=p->rtag;q->rchild=p->rchild;p->rtag=0;p->rchild=q;if((s!=NULL)&&(s->ltag==1))s->lchild=q;}/*插入右子树*/void INORDER(bithptr *t) {if(t) {INORDER(t->lchild);cout<<" "<<t->data;INORDER(t->rchild);}}/*中序遍历*/int HEIGHT(bithptr *t) {int m,n;if(t==NULL)return 0;else {m=HEIGHT(t->lchild);n=HEIGHT(t->rchild);return (m>n)?m+1:n+1;}}/*二叉树的高度*/int COUNT(bithptr *t) {if(t==NULL)return 0;elsereturn 1+COUNT(t->lchild)+COUNT(t->rchild);}/*计算结点数*/int LEAF_COUNT(bithptr *t) {if(!t)return 0;else if(!t->lchild&&!t->rchild)return 1;elsereturn LEAF_COUNT(t->lchild)+LEAF_COUNT(t->rchild); }/*计算叶子数*/bithptr *a;void GET(bithptr *t,datatype value) {if(t) {if(t->data==value)a=t;GET(t->lchild,value);GET(t->rchild,value);}}bithptr *FIND(bithptr *ptr,datatype value,int *pos) {bithptr *previous;previous=ptr;*pos=0;GET(ptr,value);while(ptr!=NULL) {if(ptr->data==value)return previous;elseprevious=ptr;if(ptr->lchild==a) {ptr=ptr->lchild;*pos=-1;}else if(ptr->rchild==a) {ptr=ptr->rchild;*pos=1;}}return NULL;}/*二叉树查找*/bithptr *DELETE(bithptr *root,int value) { bithptr *previous;bithptr *ptr;bithptr *next;int pos;previous=FIND(root,value,&pos);cout<<pos<<endl;if(previous==NULL)return root;switch(pos){case -1:ptr=previous->lchild;break;case 1:ptr=previous->rchild;break;case 0:ptr=previous;break;}if (ptr->lchild==NULL ) {if(previous!=ptr)previous->rchild=ptr->rchild;elseroot=root->rchild;free(ptr);return root;}if(ptr->rchild==NULL) {if(previous!=ptr)previous->lchild=ptr->lchild;elseroot=root->lchild;free(ptr);return root;}previous=ptr;next=ptr->lchild;while(next->rchild!=NULL) {previous=next;next=next->rchild;}ptr->data=next->data;if(previous->lchild==next)previous->lchild=next->lchild;elseprevious->rchild=next->rchild;free(next);return root;}/*删除结点*/int main() {bithptr *root;datatype x;cout<<"请输入二叉树的值并以‘#’键结束"<<endl;root=CREATREE();INORDER(root);cout<<endl;cout<<"二叉树的高度为："<<HEIGHT(root)<<endl;cout<<"二叉树的结点数为："<<COUNT(root)<<endl;cout<<"二叉树的叶子数为："<<LEAF_COUNT(root)<<endl;cout<<"请输入删除结点的值"<<endl;cin>>x;DELETE(root,x);INORDER(root);cout<<endl;INTHREAD(root);cout<<"请输入插入结点的值："<<endl;cin>>x;INSERTRIGHT(root,x);TRA VERSEINTHREAD(root);return 0;}图的基本操作#include<iostream>using namespace std;#define n 6#define e 6#define TRUE 1typedef char vextype;typedef float adjtype;typedef struct {vextype vexs[n];adjtype arcs[n][n];}graph;typedef int datatype;#define maxsize 64typedef struct {datatype *data;int front,rear;}sequeue;int visited1[n];int visited2[n];graph g;void SETNULL(sequeue &sq) {sq.data=new datatype[maxsize];sq.front=-1;sq.rear=-1;}/*置空队*/int EMPTY(sequeue &sq) {if(sq.rear==sq.front)return 1;elsereturn 0;}/*判队空*/int ENQUEUE(sequeue &sq,datatype x) { if(sq.front==(sq.rear+1)%maxsize) { cout<<"queue is full"<<endl;return NULL;}else {sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x;return 1;}}/*入队*/datatype DEQUEUE(sequeue &sq) { if(EMPTY(sq)) {cout<<"queue is empty"<<endl;return NULL;}else {sq.front=(sq.front+1)%maxsize;return sq.data[sq.front];}}/*出队*/void CREATGRAPH() {int i,j,k;adjtype w;cout<<"请输入"<<n<<"个顶点信息："<<endl;for(i=0;i<n;i++)g.vexs[i]=getchar();for(i=0;i<n;i++)for(j=0;j<n;j++)g.arcs[i][j]=0;cout<<"请输入"<<e<<"条边的两个顶点位置以及权："<<endl;for(k=0;k<e;k++) {cin>>i;cin>>j;cin>>w;g.arcs[i][j]=w;g.arcs[j][i]=w;}}/*建立无向连通图*/void DFS(int i) {int j;cout<<"node1:"<<g.vexs[i]<<endl;visited1[i]=TRUE;for(j=0;j<n;j++)if((g.arcs[i][j]!=0)&&(!visited1[j]))DFS(j);}/*深度优先遍历*/void BFS(int k) {int i,j;sequeue Q;SETNULL(Q);cout<<"node2:"<<g.vexs[k]<<endl;visited2[k]=TRUE;ENQUEUE(Q,k);while(!EMPTY(Q)) {i=DEQUEUE(Q);for(j=0;j<n;j++)if((g.arcs[i][j]!=0)&&(!visited2[j])) {cout<<"node2:"<<g.vexs[j]<<endl;visited2[j]=TRUE;ENQUEUE(Q,j);}}}/*广度优先遍历*/void INSERT(int i,int j,adjtype w) {g.arcs[i][j]=w;}/*插入边*/void DELETE(int i,int j) {g.arcs[i][j]=0;}/*删除边*/int main() {int i,j;adjtype w;CREATGRAPH();DFS(1);for(i=0;i<n;i++)visited1[i]=0;BFS(2);for(i=0;i<n;i++)visited2[i]=0;cout<<"请输入插入边的两个顶点位置以及权："<<endl;cin>>i;cin>>j;cin>>w;INSERT(i,j,w);DFS(1);for(i=0;i<n;i++)visited1[i]=0;cout<<"请输入删除边的两个顶点位置"<<endl;cin>>i;cin>>j;DELETE(i,j);DFS(1);for(i=0;i<n;i++)visited1[i]=0;。
