数据结构实验答案

第1章习题答案1. 填空题（1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示）数据元素的表示元素之间关系的表示数据元素。

（2）已经实现是一个概念分离分离（3）时、空效率指人对算法阅读理解的难易程度对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。

（4）软硬件环境问题规模的（5）最坏（6）O（n4）O（n2）（7）时间复杂度（8）n 2)1(nn+O（n2）2. 判断题（1）×（2）×（3）√（4）√（5）√（6）√（7）×（8）×（9）×（10）×3. 简答题（1）略（见教材第3页的1.2数据结构的基本概念）（2）（a）n-1，O（n）（b）n-1 , O（n）（c）11* n+1, O（n）（n为初始值100）（d）⎣⎦n, O（n）（e）n , O（n）第2章习题及答案1、填空题（1）address+m*i（2）顺序顺序顺序链式存储链式存储（3）亦相邻不一定（4）n-i+1（5）0≤i≤la的长度-1≤j≤lb的长度-1 0≤k≤lc的长度-1（6）2)1(nn+插入的位置，节点数n（顺序表长度n）（7）其前驱O(n) O（1）（8）其前驱O(n) O（1）（9）p→next=p→next →next（10）head→next==Null head==Null head→next==head head==Null （11）head→next=head→next→next head=head→next（12）x=p→prior→data; p→prior→data=p→next→data; p→next→data=x; （13）p==head→prior(或p→next==head)2．判断题（1）×（2）√（3）×（4）×（5）×（6）×（7）√（8）×（9）×（10）×3．简答题(1)（2）在带头结点的单链表上，查找指针p所指结点的前驱。

数据结构实验报告答案数据结构实验报告答案引言：数据结构是计算机科学中的重要概念，它涉及组织和管理数据的方法和技术。

在本次实验中，我们将研究和实践几种常见的数据结构，包括数组、链表、栈和队列。

通过这些实验，我们将深入理解数据结构的原理和应用。

一、数组数组是一种线性数据结构，它由一系列相同类型的元素组成。

数组的特点是可以通过索引来访问和修改元素，具有随机访问的能力。

在本次实验中，我们将实现一个简单的数组类，并进行一些基本操作，如插入、删除和查找。

首先，我们定义一个数组类，包含以下成员变量和方法：- size：数组的大小- elements：存储元素的数组- insert(index, element)：在指定位置插入元素- remove(index)：删除指定位置的元素- get(index)：获取指定位置的元素- search(element)：查找元素在数组中的位置通过实现上述方法，我们可以对数组进行各种操作。

例如，我们可以在数组的末尾插入一个元素，然后在指定位置删除一个元素。

我们还可以通过元素的值来查找其在数组中的位置。

二、链表链表是另一种常见的线性数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

链表的特点是插入和删除操作的效率较高，但随机访问的效率较低。

在本次实验中，我们将实现一个简单的单向链表，并进行一些基本操作。

首先，我们定义一个节点类，包含以下成员变量和方法：- data：节点的数据元素- next：指向下一个节点的指针然后，我们定义一个链表类，包含以下成员变量和方法：- head：链表的头节点- insert(element)：在链表的末尾插入一个节点- remove(element)：删除链表中指定的节点- search(element)：查找链表中指定元素的节点通过实现上述方法，我们可以对链表进行各种操作。

例如，我们可以在链表的末尾插入一个节点，然后删除链表中指定的节点。

数据结构实验报告-答案数据结构(C语言版)实验报告专业班级学号姓名实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。

实验主要步骤：1、分析、理解给出的示例程序。

2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。

3、修改程序：（1）增加插入结点的功能。

（2）将建立链表的方法改为头插入法。

程序代码:#include“stdio.h“#include“string.h“#include“stdlib.h“#include“ctype. h“typedefstructnode//定义结点{chardata[10];//结点的数据域为字符串structnode*next;//结点的指针域}ListNode;typedefListNode*LinkList;//自定义LinkList单链表类型LinkListCreatListR1();//函数，用尾插入法建立带头结点的单链表LinkListCreatList(void);//函数，用头插入法建立带头结点的单链表ListNode*LocateNode();//函数，按值查找结点voidDeleteList();//函数，删除指定值的结点voidprintlist();//函数，打印链表中的所有值voidDeleteAll();//函数，删除所有结点，释放内存ListNode*AddNode();//修改程序：增加节点。

用头插法，返回头指针//==========主函数==============voidmain(){charch[10],num[5];LinkListhead;head=C reatList();//用头插入法建立单链表，返回头指针printlist(head);//遍历链表输出其值printf(“Deletenode(y/n):“);//输入“y“或“n“去选择是否删除结点scanf(“%s“,num);if(strcmp(num,“y“)==0||strcmp(num,“Y“)==0){printf(“PleaseinputDelete_data:“);scanf(“%s“,ch);//输入要删除的字符串DeleteList(head,ch);printlist(head);}printf(“Addnode?(y/n):“);//输入“y“或“n“去选择是否增加结点scanf(“%s“,num);if(strcmp(num,“y“)==0||strcmp(num,“Y“)==0){head=A ddNode(head);}printlist(head);DeleteAll(head);//删除所有结点，释放内存}//==========用尾插入法建立带头结点的单链表===========LinkListCreatListR1(void){charch[10];LinkListhead=(Li nkList)malloc(sizeof(ListNode));//生成头结点ListNode*s,*r,*pp;r=head;r->next=NULL;printf(“Input#toend“);//输入“#“代表输入结束printf(“\nPleaseinputN ode_data:“);scanf(“%s“,ch);//输入各结点的字符串while(strcmp(ch,“#“)!=0){pp=LocateNode(head,ch);//按值查找结点，返回结点指针if(pp==NULL){//没有重复的字符串，插入到链表中s=(ListNode*)malloc(sizeof(ListNode));strcpy(s->data,ch);r->next=s;r=s; r->next=NULL;}printf(“Input#toend“);printf(“PleaseinputNode_data:“);scanf(“%s“,ch);}returnhead;//返回头指针}//==========用头插入法建立带头结点的单链表===========LinkListCreatList(void){charch[100];LinkListhead,p;head =(LinkList)malloc(sizeof(ListNode));head->next=NULL;while(1){printf(“Input#toend“);printf(“PleaseinputNode_data:“);scanf(“%s“,ch);if(strcmp (ch,“#“)){if(LocateNode(head,ch)==NULL){strcpy(head->data,ch);p=(Li nkList)malloc(sizeof(ListNode));p->next=head;head=p;}}elsebreak;}retu rnhead;}//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========ListNode*LocateNode(LinkListhead,char*key){List Node*p=head->next;//从开始结点比较while(p!=NULL//扫描下一个结点returnp;//若p=NULL则查找失败，否则p指向找到的值为key的结点}//==========修改程序：增加节点=======ListNode*AddNode(LinkListhead){charch[10];ListNode*s,*pp ;printf(“\nPleaseinputaNewNode_data:“);scanf(“%s“,ch);//输入各结点的字符串pp=LocateNode(head,ch);//按值查找结点，返回结点指针printf(“ok2\n“);if(pp==NULL){//没有重复的字符串，插入到链表中s=(ListNode*)malloc(sizeof(ListNode));strcpy(s->data,ch);printf(“ok3\n“);s->next=head->next;head->next=s;}returnhead;}//==========删除带头结点的单链表中的指定结点=======voidDeleteList(LinkListhead,char*key){ListNode*p,*r,*q=hea d;p=LocateNode(head,key);//按key值查找结点的if(p==NULL){//若没有找到结点，退出printf(“positionerror”);exit(0);}while(q->next!=p)//p 为要删除的结点，q为p的前结点q=q->next;r=q->next;q->next=r->next;free(r);//释放结点}//===========打印链表=======voidprintlist(LinkListhead){ListNode*p=head->next;//从开始结点打印while(p){printf(“%s,“,p->data);p=p->next;}printf(“\n“);}//==========删除所有结点，释放空间===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while( p->next){r=p->next;free(p);p=r;}free(p);}实验结果：Input#toendPleaseinputNode_data:batInput#toendPleaseinputNode_data: catInput#toendPleaseinputNode_data:eatInput#toendPleaseinputNode_da ta:fatInput#toendPleaseinputNode_data:hatInput#toendPleaseinputNode_ data:jatInput#toendPleaseinputNode_data:latInput#toendPleaseinputNode _data:matInput#toendPleaseinputNode_data:#mat,lat,jat,hat,fat,eat,cat,bat ,Deletenode(y/n):yPleaseinputDelete_data:hatmat,lat,jat,fat,eat,cat,bat,Ins ertnode(y/n):yPleaseinputInsert_data:putposition:5mat,lat,jat,fat,eat,put,c at,bat,请按任意键继续...示意图：latjathatfateatcatbatmatNULLheadlatjathatfateatcatbatmatheadlatjatfateat putcatbatmatheadNULLNULL心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。

数据结构（第4版）习题及实验参考答案数据结构复习资料完整版（c语言版）数据结构基础及深入及考试习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。

即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。

它依赖于计算机。

存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。

它由基本的数据类型构成，并包括一组相关的服务（或称操作）。

它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。

4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。

2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。

A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。

”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p->ne某t==NULLB、p==NULLC、p->ne某t==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)数据结构(第4版）习题及实验参考答案9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p->ne某t=p->ne某t->ne某t;B、p=p->ne某t;p->ne某t=p->ne某t->ne某t;C、p->ne某t=p->ne某t;D、p=p->ne某t->ne某t;10、在一个单链表中，若在p所指结点之后插入所指结点，则执行（B）A、->ne某t=p;p->ne某t=;B、->ne某t=p->ne某t;p->ne某t=;C、->ne某t=p->ne某t;p=;D、p->ne某t=;->ne某t=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点，则执行（C）A、->ne某t=p->ne某t;p->ne某t=;B、p->ne某t=->ne某t;->ne某t=p;C、q->ne某t=;->ne某t=p;D、p->ne某t=;->ne某t=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1个前趋结点。

【实验题】1．狐狸逮兔子围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到１号洞找，第二次隔１个洞（即3号洞）找，第三次隔２个洞（即6号洞）找，以后如此类推，次数不限。

”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。

问兔子究竟藏在哪个洞里？（提示：这实际上是一个反复查找线性表的过程。

）【数据描述】定义一个顺序表，用具有10个元素顺序表来表示这10个洞。

每个元素分别表示围着山顶的一个洞，下标为洞的编号。

#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量typedef struct {ElemType *elem; //存储空间基址int length; //当前长度int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）}SqList;【算法描述】status InitList_Sq(SqList &L) {//构造一个线性表LL.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem) return OVERFLOW; //存储分配失败L.length=0; //空表长度为0L.listsize=LIST_INIT_SIZE; //初始存储容量return OK;} //InitList_Sqstatus Rabbit(SqList &L){ //构造狐狸逮兔子函数int current=0; //定义一个当前洞口号的记数器，初始位置为第一个洞口for(i=0;i<LIST_INIT_SIZE;i++)L.elem[i]=1; //给每个洞作标记为1，表示狐狸未进之洞L.elem[LIST_INIT_SIZE-1]=L.elem[0]=0;//首先进入第一个洞，标记进过的洞为0。

数据结构实验报告答案一、实验目的本次数据结构实验的主要目的是通过实际编程和操作，深入理解和掌握常见的数据结构，如数组、链表、栈、队列、树和图等，并能够运用这些数据结构解决实际问题，提高编程能力和算法设计能力。

二、实验环境操作系统：Windows 10编程语言：C+＋开发工具：Visual Studio 2019三、实验内容1、数组操作定义一个整数数组，实现数组元素的输入、输出和查找功能。

对数组进行排序（选择排序、冒泡排序等），并输出排序后的数组。

2、链表操作构建一个单向链表，实现链表节点的插入、删除和遍历操作。

反转链表，并输出反转后的链表。

3、栈和队列操作用数组实现栈和队列的数据结构，实现入栈、出栈、入队、出队等基本操作。

利用栈实现表达式求值（中缀表达式转后缀表达式，然后计算后缀表达式的值）。

4、树的操作构建二叉树（可以采用顺序存储或链式存储），实现二叉树的前序、中序和后序遍历。

实现二叉树的查找、插入和删除节点操作。

5、图的操作用邻接矩阵或邻接表表示图，实现图的深度优先遍历和广度优先遍历。

求解图的最短路径（Dijkstra 算法或 Floyd 算法）。

四、实验步骤及代码实现1、数组操作｀｀｀cppinclude ＜iostream>using namespace std;／／数组输入函数void inputArray(int arr, int size) ｛cout ＜＜＂请输入＂＜＜ size ＜＜＂个整数：＂＜＜ endl; for （int i ＝ 0; i ＜ size; i+＋）｛cin ＞＞ arri;｝｝／／数组输出函数void outputArray(int arr, int size) ｛cout ＜＜＂数组元素为：＂＜＜ endl;for （int i ＝ 0; i ＜ size; i+＋）｛cout ＜＜ arri ＜＜＂＂；｝cout ＜＜ endl;｝／／数组查找函数int searchArray(int arr, int size, int target) ｛for （int i ＝ 0; i ＜ size; i+＋）｛if （arri ＝＝ target) ｛return i;｝｝return －1;｝／／选择排序函数void selectionSort(int arr, int size) ｛for （int i ＝ 0; i ＜ size 1; i+＋）｛int minIndex ＝ i;for （int j ＝ i ＋ 1; j ＜ size; j+＋）｛if （arrj ＜ arrminIndex) ｛minIndex ＝ j;｝｝if （minIndex!＝ i) ｛int temp ＝ arri;arri ＝ arrminIndex;arrminIndex ＝ temp;｝｝｝／／冒泡排序函数void bubbleSort(int arr, int size) ｛for （int i ＝ 0; i ＜ size 1; i+＋）｛for （int j ＝ 0; j ＜ size i 1; j+＋）｛if （arrj ＞ arrj ＋ 1) ｛int temp ＝ arrj;arrj ＝ arrj ＋ 1;arrj ＋ 1 ＝ temp;｝｝｝｝int main(）｛int size ＝ 10;inputArray(arr, size)；outputArray(arr, size)；int target ＝ 5;int result ＝ searchArray(arr, size, target)；if （result!＝－1) ｛cout ＜＜＂找到目标元素＂＜＜ target ＜＜＂，在数组中的索引为＂＜＜ result ＜＜ endl;｝ else ｛cout ＜＜＂未找到目标元素＂＜＜ target ＜＜ endl;｝selectionSort(arr, size)；outputArray(arr, size)；bubbleSort(arr, size)；outputArray(arr, size)；return 0;｝2、链表操作｀｀｀cppinclude ＜iostream>using namespace std;／／链表节点结构体struct ListNode ｛int data;ListNode next;ListNode(int x) ： data(x)， next(NULL) ｛｝｝；／／链表插入函数void insertNode(ListNode& head, int val) ｛ListNode newNode ＝ new ListNode(val)；if （head ＝＝ NULL) ｛head ＝ newNode;return;｝ListNode curr ＝ head;while （curr>next!＝ NULL) ｛curr ＝ curr>next;｝curr>next ＝ newNode;｝／／链表删除函数void deleteNode(ListNode& head, int val) ｛if （head ＝＝ NULL) ｛return;｝if （head>data ＝＝ val) ｛ListNode temp ＝ head;head ＝ head>next;delete temp;return;｝ListNode curr ＝ head;while （curr>next!＝ NULL ＆＆ curr>next>data!＝ val) ｛curr ＝ curr>next;｝if （curr>next!＝ NULL) ｛ListNode temp ＝ curr>next;curr>next ＝ curr>next>next;delete temp;｝｝／／链表遍历函数void traverseList(ListNode head) ｛ListNode curr ＝ head;while （curr!＝ NULL) ｛cout ＜＜ curr>data ＜＜＂＂；curr ＝ curr>next;｝cout ＜＜ endl;｝／／链表反转函数ListNode reverseList(ListNode head) ｛ListNode prev ＝ NULL;ListNode curr ＝ head;while （curr!＝ NULL) ｛ListNode nextTemp ＝ curr>next; curr>next ＝ prev;prev ＝ curr;curr ＝ nextTemp;｝return prev;｝int main(）｛ListNode head ＝ NULL;insertNode(head, 1)；insertNode(head, 2)；insertNode(head, 3)；insertNode(head, 4)；insertNode(head, 5)；traverseList(head)；deleteNode(head, 3)；traverseList(head)；ListNode reversedHead ＝ reverseList(head)；traverseList(reversedHead)；return 0;｝｀｀｀3、栈和队列操作｀｀｀cppinclude ＜iostream>using namespace std;／／用数组实现栈const int MAX_SIZE ＝ 100;class Stack ｛private:int arrMAX_SIZE;int top;public:Stack(）｛top ＝－1;｝／／入栈void push(int val) ｛if （top ＝＝ MAX_SIZE 1) ｛cout ＜＜＂栈已满，无法入栈" ＜＜ endl; return;｝arr+＋top ＝ val;｝／／出栈int pop(）｛if （top ＝＝－1) ｛cout ＜＜＂栈为空，无法出栈" ＜＜ endl; return －1;｝int val ＝ arrtop;top;return val;｝／／查看栈顶元素int peek(）｛if （top ＝＝－1) ｛cout ＜＜＂栈为空" ＜＜ endl;return －1;｝return arrtop;｝／／判断栈是否为空bool isEmpty(）｛return top ＝＝－1;｝｝；／／用数组实现队列class Queue ｛private:int arrMAX_SIZE;int front, rear;public:Queue(）｛front ＝ rear ＝－1;｝／／入队void enqueue(int val) ｛if （（rear ＋ 1) ％ MAX_SIZE ＝＝ front) ｛cout ＜＜＂队列已满，无法入队" ＜＜ endl; return;｝if （front ＝＝－1) ｛front ＝ 0;｝rear ＝（rear ＋ 1) ％ MAX_SIZE;arrrear ＝ val;｝／／出队int dequeue(）｛if （front ＝＝－1) ｛cout ＜＜＂队列为空，无法出队" ＜＜ endl; return －1;｝int val ＝ arrfront;if （front ＝＝ rear) ｛front ＝ rear ＝－1;｝ else ｛front ＝（front ＋ 1) ％ MAX_SIZE;｝return val;｝／／查看队头元素int peek(）｛if （front ＝＝－1) ｛cout ＜＜＂队列为空" ＜＜ endl;return －1;｝return arrfront;｝／／判断队列是否为空bool isEmpty(）｛return front ＝＝－1;｝｝；／／表达式求值函数int evaluateExpression(string expression) ｛Stack operandStack;Stack operatorStack;for （int i ＝ 0; i ＜ expressionlength(）； i+＋）｛char c ＝ expressioni;if （isdigit(c)）｛int operand ＝ 0;while （i ＜ expressionlength(）＆＆ isdigit(expressioni)）｛operand ＝ operand 10 ＋（expressioni+＋＇0'）；｝i;operandStackpush(operand)；｝ else if （c ＝＝＇＋＇｜｜ c ＝＝＇＇｜｜ c ＝＝＇＇｜｜ c ＝＝＇／＇）｛while （！operatorStackisEmpty(）＆＆precedence(operatorStackpeek(））＞＝ precedence(c)）｛int operand2 ＝ operandStackpop(）；int operand1 ＝ operandStackpop(）；char op ＝ operatorStackpop(）；int result ＝ performOperation(operand1, operand2, op)；operandStackpush(result)；｝operatorStackpush(c)；｝ else if （c ＝＝＇（＇）｛operatorStackpush(c)；｝ else if （c ＝＝＇）＇）｛while （operatorStackpeek(）！＝＇（＇）｛int operand2 ＝ operandStackpop(）；int operand1 ＝ operandStackpop(）；char op ＝ operatorStackpop(）；int result ＝ performOperation(operand1, operand2, op)；operandStackpush(result)；｝operatorStackpop(）；｝｝while （！operatorStackisEmpty(））｛int operand2 ＝ operandStackpop(）；int operand1 ＝ operandStackpop(）；char op ＝ operatorStackpop(）；int result ＝ performOperation(operand1, operand2, op)；operandStackpush(result)；｝return operandStackpop(）；｝／／运算符优先级函数int precedence(char op) ｛if （op ＝＝＇＋＇｜｜ op ＝＝＇＇）｛return 1;｝ else if （op ＝＝＇＇｜｜ op ＝＝＇／＇）｛return 2;｝return 0;｝／／运算函数int performOperation(int operand1, int operand2, char op) ｛switch （op) ｛case ＇＋＇：return operand1 ＋ operand2;case ＇＇：return operand1 operand2;case ＇＇：return operand1 operand2;case ＇／＇：if （operand2!＝ 0) ｛return operand1 ／ operand2;｝ else ｛cout ＜＜＂除数不能为 0" ＜＜ endl;return －1;｝｝return －1;｝int main(）｛Stack stack;stackpush(1)；stackpush(2)；stackpush(3)；cout ＜＜＂栈顶元素：＂＜＜ stackpeek(）＜＜ endl;cout ＜＜＂出栈元素：＂＜＜ stackpop(）＜＜ endl;cout ＜＜＂栈是否为空：＂＜＜（stackisEmpty(）？＂是" ：＂否"）＜＜ endl;Queue queue;queueenqueue(1)；queueenqueue(2)；queueenqueue(3)；cout ＜＜＂队头元素：＂＜＜ queuepeek(）＜＜ endl;cout ＜＜＂出队元素：＂＜＜ queuedequeue(）＜＜ endl;cout ＜＜＂队列是否为空：＂＜＜（queueisEmpty(）？＂是" ：＂否"）＜＜ endl;string expression ＝＂2+34"；int result ＝ evaluateExpression(expression)；cout ＜＜ expression ＜＜＂＝＂＜＜ result ＜＜ endl; return 0;｝｀｀｀4、树的操作｀｀｀cppinclude ＜iostream>using namespace std;／／二叉树节点结构体struct TreeNode ｛int val;TreeNode left;TreeNode right;TreeNode(int x) ： val(x)， left(NULL)， right(NULL) ｛｝｝；／／前序遍历函数void preOrderTraversal(TreeNode root) ｛return;｝cout ＜＜ root>val ＜＜＂＂；preOrderTraversal(root>left)；preOrderTraversal(root>right)；｝／／中序遍历函数void inOrderTraversal(TreeNode root) ｛if （root ＝＝ NULL) ｛return;｝inOrderTraversal(root>left)；cout ＜＜ root>val ＜＜＂＂；inOrderTraversal(root>right)；｝／／后序遍历函数void postOrderTraversal(TreeNode root) ｛return;｝postOrderTraversal(root>left)；postOrderTraversal(root>right)；cout ＜＜ root>val ＜＜＂＂；｝／／查找函数TreeNode searchBST(TreeNode root, int val) ｛if （root ＝＝ NULL ｜｜ root>val ＝＝ val) ｛return root;｝if （val ＜ root>val) ｛return searchBST(root>left, val)；｝ else ｛return searchBST(root>right, val)；｝｝／／插入函数TreeNode insertBST(TreeNode root, int val) ｛if （root ＝＝ NULL) ｛return new TreeNode(val)；｝if （val ＜ root>val) ｛root>left ＝ insertBST(root>left, val)；｝ else if （val ＞ root>val) ｛root>right ＝ insertBST(root>right, val)；｝return root;｝／／删除函数TreeNode deleteNodeBST(TreeNode root, int key) ｛if （root ＝＝ NULL) ｛return root;｝if （key ＜ root>val) ｛root>left ＝ deleteNodeBST(root>left, key)；｝ else if （key ＞ root>val) ｛root>right ＝ deleteNodeBST(root>right, key)；｝ else ｛if （root>left ＝＝ NULL) ｛TreeNode temp ＝ root>right;delete root;return temp;｝ else if （root>right ＝＝ NULL) ｛TreeNode temp ＝ root>left;delete root;return temp;｝TreeNode minNode ＝ root>right;while （minNode>left!＝ NULL) ｛minNode ＝ minNode>left;｝root>val ＝ minNode>val;root>right ＝ deleteNodeBST(root>right, minNode>val)；｝return root;｝int main(）｛TreeNode root ＝ new TreeNode(4)；root>left ＝ new TreeNode(2)；root>right ＝ new TreeNode(6)；root>left>left ＝ new TreeNode(1)；root>left>right ＝ new TreeNode(3)；root>right>left ＝ new TreeNode(5)；root>right>right ＝ new TreeNode(7)；cout ＜＜＂前序遍历：＂＜＜ endl; preOrderTraversal(root)；cout ＜＜ endl;cout ＜＜＂中序遍历：＂＜＜ endl; inOrderTraversal(root)；cout ＜＜ endl;cout ＜＜＂后序遍历：＂＜＜ endl; postOrderTraversal(root)；cout ＜＜ endl;int target ＝ 3;TreeNode foundNode ＝ searchBST(root, target)；if （foundNode!＝ NULL) ｛cout ＜＜＂找到目标节点＂＜＜ target ＜＜ endl;｝ else ｛cout ＜＜＂未找到目标节点＂＜＜ target ＜＜ endl;｝root ＝ insertBST(root, 8)；cout ＜＜＂插入节点 8 后的中序遍历：＂＜＜ endl; inOrderTraversal(root)；cout ＜＜ endl;root ＝ deleteNodeBST(root, 2)；cout ＜＜＂删除节点 2 后的中序遍历：。

重庆邮电学院软件学院《数据结构》实验参考资料<适用于软件学院13104级>重庆邮电学院软件学院实验中心目录一、课程编号 (2)二、课程类型 (2)三、本课程的地位、作用与任务 (2)四、课程基本要求 (2)五、实验安排 (2)1、数据结构实验机器与环境 (2)（一）计算机的硬件配置 (2)（二）计算机的软件配置 (2)2、VisualC++6.0开发C语言程序 (2)（一）进入C++工作环境 (2)（二）编译、运行C程序 (3)3、上机实验 (6)实验1：线性表操作 (6)实验2：单链表操作 (11)实验3：表达式计算 (17)实验4：二叉树操作 (24)实验5：二叉搜索树操作 (30)实验6：图的运算 (36)实验7：散列表操作 (43)实验8：外存文件的排序操作 (49)实验9：二叉搜索树与文件操作 (53)六、教材 (60)七、成绩考核办法 (60)数据结构（C语言版）实验一、课程编号130101（本科）二、课程类型课程类型：必修课。

适用专业：计算机系各专业实验学时：10学时三、本课程的地位、作用与任务《数据结构》在计算机科学中是一门综合性的专业基础课。

数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有密切的关系，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。

在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础，它的主要任务是讨论各种数据结构的逻辑结构，存储结构及有关操作的算法。

目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。

另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

从而为提高学生的实际分析问题和解决问题的编程能力打下基础。