《数据结构》课程实验指导书

数据结构课程实验指导书线性表的插入和删除实验一实验目的（1）熟练掌握线性表的逻辑特征。（2）熟练掌握顺序表的表示方法，存储结构及其基本操作的实现。实验要求（1）顺序表的插入和删除操作，掌握数据元素前移、后移的操作技巧。（2）单链表的插入和删除操作，包括有序（递减或递增）单链表的插入和删除操作。插入操作要求表中不允许有关键字相同的数据元素。实验内容（1）设计一个顺序表，实现下列基本运算：①初始化线性表：②在第1个元素前插入一个元素e：③删除第1个元素；（2）设计一个单链表，实现下列基本运算：①生成一个带头结点的单链表：②在第1个元素前插入一个元素e；③删除第1个元素。算法实现程序（源程序代码）（1）顺序表的基本操作#include <iostream.h>#define MAX151/顺序表的定义typedef struct(int elem[MAX];int length;}Sqlist,void Initlist sq(Sqlist &L),void Listlnsert_sq(Sqlist &L,int i, int e);void ListDel _sq(Sqlist &L,int i, int &e),void print_sq(Sqlist L);II函数的定义void Initlist_sq(Sqlist &L)L.length =0;1void Listlnsert_sq(Sqlist &L,int i, int e)(int *p,*q,if(i<1li>L.length +1)return,q=&L.elem[i-1]；1插入位置for(p=&L.elem[L.length -1];p>=q;-p )*(p+1)=*p;*q=e,++L.length ;return,1void ListDel sq(Sqlist &L,inti, int &e)1

1 数据结构课程实验指导书 实验一 线性表的插入和删除 实验目的 （1）熟练掌握线性表的逻辑特征。 （2）熟练掌握顺序表的表示方法，存储结构及其基本操作的实现。 实验要求 （1）顺序表的插入和删除操作，掌握数据元素前移、后移的操作技巧。 （2）单链表的插入和删除操作，包括有序（递减或递增）单链表的插入和删除操作。插入操作要 求表中不允许有关键字相同的数据元素。 实验内容 （1）设计一个顺序表，实现下列基本运算：①初始化线性表；②在第 1 个元素前插入一个元素 e； ③删除第 1 个元素； （2）设计一个单链表，实现下列基本运算：①生成一个带头结点的单链表；②在第 1 个元素前插 入一个元素 e；③删除第 1 个元素。 算法实现程序（源程序代码） （1）顺序表的基本操作 #include <iostream.h> #define MAX 15 //顺序表的定义 typedef struct{ int elem[MAX]; int length; }Sqlist; void Initlist_sq(Sqlist &L); void ListInsert_sq(Sqlist &L,int i, int e); void ListDel_sq(Sqlist &L,int i, int &e); void print_sq(Sqlist L); // 函数的定义 void Initlist_sq(Sqlist &L){ L.length =0; } void ListInsert_sq(Sqlist &L,int i, int e){ int *p,*q; if(i<1||i>L.length +1) return; q=&L.elem[i-1]; //插入位置 for(p=&L.elem[L.length -1];p>=q;-p ) *(p+1)=*p; *q=e; ++L.length ; return; } void ListDel_sq(Sqlist &L,int i, int &e){

if(i<1li>L.length )return,e=L.elem[i-1];for(int j=i.j<L.length j++)L.elem[j-1]-L.elem[i];L.length ;1void print_sq(Sqlist L)int *p,*q-L.elem+L.length-1 ;for(p=L.elem,p<=q,p++)printf(*p);printf("n");void mainOinta[11]=(10,20,30,40,50,60,70,80,90,100);Sqlist L;Initlist_sq(L)，//初始化顺序表printf("现在的表长：",L.length),1/插入10个数据元素for( int i=1;i<=10;++i)Listlnsert_ sq(L, i, a[i-1]),printf("插入10个元素后的线性表：");print_sq(L)，//遍历printf("现在的表长：",L.length)1/删除第5个元素int x,ListDel_sq(L,5, x);printf("删除的元素值是：",x);printf("删除第5个元素后的表：");print_sq( L);printf("现在的表长：",L.length);/（2）单链表的操作#include<iostream.h>structNODEint data,NODE *next;;voidprint(NODE*&head)；I/遍历int data[6]=(25,41,17,98,5,6);voidSetup_L(NODE*&head,intn);I/生成单链表voidInsertL(NODE*&head, intI, int e),//插入void Delete_L(NODE *&head, int I,int&e),I删除void mainOtNODE *L;Setup_ L(L,6),2

2 if(i<1||i>L.length ) return; e=L.elem[i-1]; for(int j=i;j<L.length ;j++) L.elem[j-1]=L.elem[j]; L.length ; } void print_sq(Sqlist L){ int *p,*q=L.elem+L.length-1 ; for(p=L.elem;p<=q;p++ ) printf(*p); printf("\n"); } void main(){ int a[11]={10,20,30,40,50,60,70,80,90,100}; Sqlist L; Initlist_sq(L); //初始化顺序表 printf("现在的表长：",L.length); //插入 10 个数据元素 for( int i=1;i<=10;++i) ListInsert_sq(L, i, a[i-1]); printf("插入 10 个元素后的线性表："); print_sq( L); //遍历 printf("现在的表长：",L.length); //删除第 5 个元素 int x; ListDel_sq(L,5, x); printf("删除的元素值是：",x); printf("删除第 5 个元素后的表："); print_sq( L); printf("现在的表长：",L.length); } （2）单链表的操作 #include <iostream.h> struct NODE{ int data; NODE *next; }; void print(NODE *&head); //遍历 int data[6]={25,41,17,98,5,6}; void Setup_L(NODE *&head,int n); //生成单链表 void Insert_L(NODE *&head, int I, int e); //插入 void Delete_L(NODE * &head, int I,int &e); //删除 void main(){ NODE *L; Setup_L(L,6);

print(L);Insert_L(L,7,50);print(L);int x,Delete L(L,0,x);printf("X=-",x,"In"),print(L),void print(NODE *&head)NODE*p;p=head->next ;while(p):printf(p->data,"，");//输出元素值p=p->next;//后移指针1print("n");/void Setup_L(NODE * &head,int n)(NODE *q,*p;head=(NODE*)newNODE;head->next=NULL;I/先建立一个带头结点的单链表q=head;for(int i=0;i<n;i++)p=(NODE*)newNODE;I/生成新结点p->data=data[i];,q->next=p;q=p;//插入到表头q->next =NULL;1void Insert_L(NODE *&L,int i, int e)(NODE *p=L,*q;int j=0;while(p&&j<i-1)p=p->next;j++;if(pli>i-1)printf("插入值超出范围！");return,1q=(NODE*)newNODE;q->data=e;q->next =p->next ;p->next =q;1n

3 print(L); Insert_L(L,7,50); print(L); int x; Delete_L(L,0,x); printf("X=",x,"\n"); print(L); } void print(NODE *&head){ NODE *p; p=head->next ; while(p){ printf(p->data,", "); //输出元素值 p=p->next; //后移指针 } print("\n"); } void Setup_L(NODE * &head,int n){ NODE *q,*p; head=(NODE*)new NODE; head->next=NULL; //先建立一个带头结点的单链表 q=head; for(int i=0;i<n;i++){ p=(NODE *)new NODE; //生成新结点 p->data=data[i]; q->next=p; q=p; //插入到表头 } q->next =NULL; } void Insert_L(NODE *&L,int i, int e){ NODE *p=L,*q; int j=0; while(p&&j<i-1){ p=p->next ; j++; } if(!p||j>i-1){ printf("插入值超出范围！"); return; } q=(NODE*)new NODE; q->data=e; q->next =p->next ; p->next =q; }

void Delete_L(NODE *&L,int i,int &e)NODE *p=L,*q;int j=0;while(p&&j<i-1)(p=p->next ;j++;1if(!plli>i-1)printf("删除值超出范围！");return,1q=p->next ;e=q->data ;p->next =q->next;delete q;上机调试情况说明（包括调试数据、调试过程中遇到的问题及解决方法）将实验程序上机调试运行。测试结果和输出数据，对结果的分析和说明实验二二叉树操作实验目的（1）掌握二叉树的非线性、递归特点，熟练掌握二叉树的存储结构。（2）熟练掌握二叉树的各种遍历操作和其它操作的实现方法。基本要求（1）要求采用二叉链存储结构，编写程序完成二叉树的建立，输出先序、中序及后序遍历二叉树的遍历序列，清楚各种递归遍历算法中递归调用语句的位置和功能。（2）求二叉树的结点总个数、叶结点个数和符合指定条件的结点个数（比如，二叉树结点的值为整数，求该树中值为偶数的结点的个数）的操作。实验内容采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。二叉树以链式结构表示，主程序以菜单方式的用户界面。算法实现程序（源程序代码）#include"stdio.h"#include"string.h"#defineMax20//结点的最大个数typedef struct nodechar data,struct node *lchild,*rchild;//自定义二叉树的结点类型BinTNode;/定义二叉树的指针typedef BinTNode *BinTree;4

4 void Delete_L(NODE *&L,int i,int &e){ NODE *p=L,*q; int j=0; while(p&&j<i-1){ p=p->next ; j++; } if(!p||j>i-1){ printf("删除值超出范围！"); return; } q=p->next ; e=q->data ; p->next =q->next; delete q; } 上机调试情况说明（包括调试数据、调试过程中遇到的问题及解决方法） 将实验程序上机调试运行。 测试结果和输出数据，对结果的分析和说明 实验二 二叉树操作 实验目的 （1）掌握二叉树的非线性、递归特点，熟练掌握二叉树的存储结构。 （2）熟练掌握二叉树的各种遍历操作和其它操作的实现方法。 基本要求 （1）要求采用二叉链存储结构，编写程序完成二叉树的建立，输出先序、中序及后序遍历二叉树 的遍历序列，清楚各种递归遍历算法中递归调用语句的位置和功能。 （2）求二叉树的结点总个数、叶结点个数和符合指定条件的结点个数（比如，二叉树结点的值为 整数，求该树中值为偶数的结点的个数）的操作。 实验内容 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求 所有叶子及结点总数的操作。 二叉树以链式结构表示，主程序以菜单方式的用户界面。 算法实现程序（源程序代码） #include"stdio.h" #include"string.h" #define Max 20 //结点的最大个数 typedef struct node{ char data; struct node *lchild,*rchild; }BinTNode; //自定义二叉树的结点类型 typedef BinTNode *BinTree; //定义二叉树的指针

I/NodeNum为结点数，leaf为叶子数intNodeNum leaf:1/基于先序遍历算法创建二叉树I/要求输入先序序列，其中加入虚结点“#”以示空指针的位置BinTree CreatBinTree(void)BinTree T,char ch,if(ch=getcharO)-#")return(NULL）；//读入#，返回空指针elselT=(BinTNode*)malloc(sizeof(BinTNode);I/生成结点T->data=ch;T->Ichild=CreatBinTreeO;1/构造左子树T->rchild=CreatBinTreeO;I/构造右子树return(T);1I先序遍历void Preorder(BinTree T)if(T)(1/访问结点printf("%c",T->data);Preorder(T->Ichild);I先序遍历左子树Preorder(T->rchild);I/先序遍历右子树111/中序遍历void Inorder(BinTree T)if(T)1/中序遍历左子树Inorder(T->lchild);1/访问结点printf("%c",T->data);1/中序遍历右子树Inorder(T->rchild),1/后序遍历void Postorder(BinTree T)if(T) Postorder(T->Ilchild);1/后序遍历左子树1/后序遍历右子树Postorder(T->rchild);//访问结点printf("%c",T->data),1结点数及叶子数的递归算法/采用后序遍历求二叉树的深度、int TreeDepth(BinTree T))int hl,hr,max;if(T)(求左深度hl-TreeDepth(T->lchild);5

5 int NodeNum,leaf; //NodeNum 为结点数，leaf 为叶子数 //基于先序遍历算法创建二叉树 //要求输入先序序列，其中加入虚结点“#”以示空指针的位置 BinTree CreatBinTree(void){ BinTree T; char ch; if((ch=getchar())=='#') return(NULL); //读入#，返回空指针 else{ T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->lchild=CreatBinTree(); //构造左子树 T->rchild=CreatBinTree(); //构造右子树 return(T); } } //先序遍历 void Preorder(BinTree T){ if(T){ printf("%c",T->data); //访问结点 Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } } //中序遍历 void Inorder(BinTree T){ if(T){ Inorder(T->lchild); //中序遍历左子树 printf("%c",T->data); //访问结点 Inorder(T->rchild); //中序遍历右子树 } } //后序遍历 void Postorder(BinTree T){ if(T){ Postorder(T->lchild); //后序遍历左子树 Postorder(T->rchild); //后序遍历右子树 printf("%c",T->data); //访问结点 } } //采用后序遍历求二叉树的深度、结点数及叶子数的递归算法 int TreeDepth(BinTree T){ int hl,hr,max; if(T){ hl=TreeDepth(T->lchild); //求左深度