数据结构实验报告全集实验一线性表基本操作和简单程序1．实验目的（1）掌握使用Visual C++ 上机调试程序的基本方法；（2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。
2．实验要求（1）认真阅读和掌握和本实验相关的教材内容。
（2）认真阅读和掌握本章相关内容的程序。
（3）上机运行程序。
（4）保存和打印出程序的运行结果，并结合程序进行分析。
（5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果实验代码：1）头文件模块#include >验目的掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。
2.实验要求（1）认真阅读和掌握和本实验相关的教材内容。
（2）分析问题的要求，编写和调试完成程序。
（3）保存和打印出程序的运行结果，并分析程序的运行结果。
3.实验内容利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。
具体完成如下：（1）定义栈的顺序存取结构。
（2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。
（3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。
其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。
（4）设计一个测试主函数进行测试。
（5）对程序的运行结果进行分析。
实验代码：#include < >#define MaxSize 100typedef struct{??? int data[MaxSize];??? int top;}SqStack;void InitStack(SqStack *st) 验目的（1）进一步掌握指针变量的用途和程序设计方法。
（2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。
（3）掌握构造二叉树的基本方法。
（4）掌握二叉树遍历算法的设计方法。
3．实验要求（1）认真阅读和掌握和本实验相关的教材内容。
（2）掌握一个实际二叉树的创建方法。
（3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。
4．实验内容（1）定义二叉链存储结构。
（2）设计二叉树的基本操作（初始化一棵带头结点的二叉树、左结点插入、右结点插入、中序遍历二叉树等）。
（3）按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。
（4）编写测试主函数并上机运行。
打印出运行结果，并结合程序运行结果进行分析。
实验代码：#include<>typedef struct bitnode{char data;struct bitnode *lchild,*rchild;}binode,*bitree;void createbitree(bitree *T){char ch;cin>>ch;if(ch=='0')(*T)=NULL;else{(*T)=new bitnode;(*T)->data=ch;createbitree(&(*T)->lchild);createbitree(&(*T)->rchild);}void inorderout(bitree T){if(T){inorderout(T->lchild);cout<<T->data<<endl;inorderout(T->rchild);}}void postorder(bitree T){if(T){postorder(T->lchild);postorder(T->rchild);cout<<T->data<<endl;}}int countleaf(bitree bt){if(!bt)return 0;if(bt->lchild==NULL&&bt->rchild==NULL) return 1;return(countleaf(bt->lchild)+countleaf(bt->rchild));void main(){bitree bt;createbitree(&bt);inorderout(bt);cout<<" "<<endl;postorder(bt);countleaf(bt);}实验五建立有序表并进行折半查找1. 实验目的掌握递归算法求解问题的基本思想和程序实现方法。
2．实验要求（1）认真阅读和掌握本实验的算法思想。
（2）编写和调试完成程序。
（3）保存和打印程序的运行结果，并对运行结果进行分析。
3.实验内容（1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。
（2）编写程序实现：在保存于数组的1000个有序数据元素中查找数据元素x是否存在。
数据元素x要包含两种情况：一种是数据元素x包含在数组中；另一种是数据元素x不包含在数组中（3）数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。
（4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。
实验代码：#include<>#include<>#define MAX_LENGTH 100typedef int KeyType;typedef struct{int key;}ElemType;typedef struct{ElemType elem[MAX_LENGTH]; SSTable STey) return mid;elseif(key<[mid].key)high = mid-1;elselow=mid+1;}return 0;}void main(){int i,result;SSTable ST;KeyType key;printf("please input length:");scanf("%d",&;for(i=1;i<=;i++){printf("please input :");scanf("%d",&[i]);}printf("please input keyword:");scanf("%d",&key);result=Search_Bin(ST,key);if(result==0)printf("Don't find\n");elseprintf("Find the key,the position is %d\n",result);}实验结果：实验六建立一组记录并进行插入排序1. 实验目的（1）掌握插入排序算法的思想。
（2）掌握顺序队列下插入排序算法的程序设计方法。
2. 实验要求（1）认真阅读和掌握教材中插入排序算法的思想。
（3）编写基于顺序队列的插入排序排序算法并上机实现。
3. 实验内容（1）编写基于顺序队列的插入排序函数。
（2）设计一个测试主函数，实现对基于顺序队列结构的插入排序算法的测试。
（3）分析程序的运行结果。
实验代码：#include<>#include<>#define MAXSIZE 100typedef struct{int key;}sortkey;typedef struct{sortkey elem[MAXSIZE];int length;}sortelem;void InsertSort(sortelem *p){int i,j;for(i=2;i<=p->length;i++){if(p->elem[i].key<p->elem[i-1].key)/*小于时，需将elem[i]插入有序表*/ {p->elem[0].key=p->elem[i].key; /*为统一算法设置监测*/for(j=i-1;p->elem[0].key<p->elem[j].key;j--)p->elem[j+1].key=p->elem[j].key;/*记录后移*/p->elem[j+1].key=p->elem[0].key; /*插入到正确位置*/}}}void main(){sortelem *p;int i;int b[6]={45,23,54,6,4,46};p=(sortelem *)malloc(sizeof(sortelem));p->length=0;for(i=1;i<7;i++){p->elem[i].key=b[i-1];p->length++;}InsertSort(p);for(i=1;i<7;i++){printf("%d ",p->elem[i].key);}system("pause");}实验结果：实验七? 建立一组记录并进行快速排序1. 实验目的（1）掌握快速排序算法的思想。
（2）掌握顺序队列下快速排序算法的程序设计方法。
2. 实验要求（1）认真阅读和掌握教材中快速排序算法的思想。
（3）编写基于顺序队列的快速排序排序算法并上机实现。
3. 实验内容（1）编写基于顺序队列的快速排序函数。
（2）设计一个测试主函数，实现对基于顺序队列结构的快速排序算法的测试。
（3）分析程序的运行结果。
实验代码：#include<>void quick_sort(int a[],int low, int high){int i,j,pivot;if (low < high){pivot = a[low];i = low;j = high;while (i < j){//从顶端开始比较值，如果小于标准值，停止while (i < j && a[j] >= pivot){j--;}//将比pivot小的元素移到低端，下标加加if (i < j)a[i++] = a[j];//从底端开始比较值，如果大于标准值，停止while (i < j && a[i] <= pivot){i++;}//将比pivot大的元素移到顶端，下标减减 if (i < j)a[j--] = a[i];}//pivot移动到最终位置a[i] = pivot;//对左区间进行递归排序quick_sort(a, low, i-1);//对右区间进行递归排序quick_sort(a, i+1, high);}}void print_array(int a[], int n){for(int i = 0; i < n; i++){cout << a[i] << ",";}}int main(){int data[9] = {54,38,96,23,15,72,60,45,83}; quick_sort(data, 0, 8);print_array(data,9); return 0;}实验结果：。