《数据结构》实验教学大纲.docx
- 文档编号:2288581
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:42
- 大小:23.88KB
《数据结构》实验教学大纲.docx
《《数据结构》实验教学大纲.docx》由会员分享,可在线阅读,更多相关《《数据结构》实验教学大纲.docx(42页珍藏版)》请在冰点文库上搜索。
《数据结构》实验教学大纲
《数据结构》实验教学大纲
实验1线性表的基本操作
1实验目的
(1)熟练掌握线性表的逻辑特征。
(2)熟练掌握线性表的基本操作在两种存储结构上的实现。
2实验内容
(1)设计一个顺序表的基本操作的演示程序
(2)设计一个单链表的基本操作的演示程序
(3)设计一个双链表的基本操作的演示程序
【基本要求】
实现下列4种基本运算:
(1)初始化线性表;
(2)在第I个元素前插入一个元素e;(3)删除第I个元素;(4)遍历线性表;(5)将单链表逆置
【测试数据】自定
参考程序如下:
//顺序表的基本操作
#include
//顺序表的定义
#defineMAX15
typedefstruct{
intelem[MAX];
intlength;
}Sqlist;
voidInitlist_sq(Sqlist&L);
voidListInsert_sq(Sqlist&L,inti,inte);
voidListDel_sq(Sqlist&L,inti,int&e);
voidprint_sq(SqlistL);
//函数的定义
voidInitlist_sq(Sqlist&L)
{
L.length=0;
}
voidListInsert_sq(Sqlist&L,inti,inte)
{
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;
}
voidListDel_sq(Sqlist&L,inti,int&e)
{
if(i<1||i>L.length)return;
e=L.elem[i-1];
for(intj=i;j L.elem[j-1]=L.elem[j]; --L.length; } voidprint_sq(SqlistL) { int*p,*q=L.elem+L.length-1; for(p=L.elem;p<=q;p++) cout<<*p<<''; cout<<"\n"; } voidmain() { inta[11]={10,20,30,40,50,60,70,80,90,100}; SqlistL; //初始化顺序表 Initlist_sq(L); cout<<"现在的表长: "< //插入10个数据元素 for(inti=1;i<=10;++i) ListInsert_sq(L,i,a[i-1]); cout<<"插入10个元素后的线性表: "< //遍历 print_sq(L); cout<<"现在的表长: "< //删除第5个元素 intx; ListDel_sq(L,5,x); cout<<"删除的元素值是: "< cout<<"删除第5个元素后的表: "< print_sq(L); cout<<"现在的表长: "< } //单链表的操作 #include structNODE { intdata; NODE*next; }; voidprint(NODE*&head);//遍历 intdata[6]={25,41,17,98,5,6}; voidSetup_L(NODE*&head,intn);//生成单链表 voidInsert_L(NODE*&head,intI,inte);//插入 voidDelete_L(NODE*&head,intI,int&e);//删除 voidConvert_L(NODE*&head);//逆序 voidmain() { NODE*L; Setup_L(L,6); print(L); //Insert_L(L,7,50); print(L); intx; Delete_L(L,0,x); cout<<"X="< print(L); Convert_L(L); print(L); } voidprint(NODE*&head) { NODE*p; p=head->next; while(p) { cout< p=p->next;//后移指针 } cout< } voidSetup_L(NODE*&head,intn) { NODE*q,*p; head=(NODE*)newNODE; head->next=NULL;//先建立一个带头结点的单链表 q=head; for(inti=0;i p=(NODE*)newNODE;//生成新结点 p->data=data[i]; q->next=p;q=p;//插入到表头 } q->next=NULL; } voidInsert_L(NODE*&L,inti,inte) { NODE*p=L,*q; intj=0; while(p&&j {p=p->next; j++; } if(! p||j>i-1) {cout<<"插入值超出范围! "< return; } q=(NODE*)newNODE; q->data=e; q->next=p->next; p->next=q; } voidDelete_L(NODE*&L,inti,int&e) { NODE*p=L,*q; intj=0; while(p&&j {p=p->next; j++; } if(! p||j>i-1) {cout<<"删除值超出范围! "< return; } q=p->next; e=q->data; p->next=q->next; deleteq; } voidConvert_L(NODE*&L) { NODE*p,*q,*r; p=L->next; q=p->next; p->next=NULL; while(q) { r=q->next; q->next=p; L->next=q; p=q; q=r; } } //双链表的基本操作 structNODE { intdata; NODE*next; NODE*prior; }; intdata[6]={3,5,7,19,20,21};//测试用数据 //函数声明 voidprint(NODE*&head); voidSetup_L(NODE*&head,intn); voidInsert_L(NODE*&L,inti,inte); voidDelete_L(NODE*&L,inti,int&e); voidConvert_L(NODE*&L); //主函数和各函数的定义 voidmain() { NODE*L; Setup_L(L,6); print(L); Insert_L(L,7,50); print(L); intx; Delete_L(L,1,x); cout<<"X="< print(L); } voidprint(NODE*&head) {//从头开始顺序输出双链表中的数据 NODE*p; p=head->next; while(p) {cout< p=p->next; } cout< } voidSetup_L(NODE*&head,intn) {//创建一个带头结点的双链表 NODE*q,*p; head=(NODE*)newNODE; head->next=NULL; q=head; for(inti=0;i p=(NODE*)newNODE; p->data=data[i]; //cin>>p->data; p->prior=q;q->next=p;q=p; } q->next=NULL; //return(head); } voidInsert_L(NODE*&L,inti,inte) {//在带头结点的双链表中第i个位置插入元素e NODE*p=L,*q; intj=0;//j为计数器 while(p&&j {p=p->next; j++; }//寻找第i-1个结点 if(! p||j>i-1)//i小于1或大于表长 {cout<<"插入值超出范围! "< return; } q=(NODE*)newNODE;//生成新结点 q->data=e; if(p->next==NULL) {q->next=p->next;p->prior=q;p->next=q;} else {q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;}//插入L中 } voidDelete_L(NODE*&L,inti,int&e) {//在带头结点的双链表L中,删除第i个元素,并由e返回其值 NODE*p=L,*q; intj=0; while(p&&j {p=p->next; j++; } if(! p||j>i-1) {cout<<"删除值超出范围! "< return; } q=p->next; e=q->data; q->next->prior=p; p->next=q->next; deleteq; }//删除并释放结点 3实验要求 按要求编写实验程序,将实验程序上机调试运行,并提交实验报告。 实验2栈和队列的基本操作 1实验目的 (1)深入了解栈和队列的基本特性 (2)熟练掌握栈的基本操作在两种存储结构上的实现。 (3)熟练掌握循环队列的基本操作 (4)熟练掌握链队列的基本操作 2实验内容 (1)设计一个顺序栈的基本操作的演示程序 (2)设计一个链栈的基本操作的演示程序 (3)设计一个循环队列的基本操作的演示程序 (4)设计一个链队列的基本操作的演示程序 【基本要求】 实现下列6种基本运算: (1)初始化; (2)入栈(队列);(3)出栈(队列);(4)遍历;(5)求栈(队列)的长度 【测试数据】自定 参考程序如下: //顺序栈的基本操作 #include #defineMAX10 typedefstruct{ intbase; inttop; intst[MAX]; }SqStack; //基本操作说明 voidInitStack(SqStack&S); voidpush(SqStack&S,inte); voidpop(SqStack&S,int&e); //基本操作的算法描述 voidInitStack(SqStack&S) { S.base=S.top=0; } voidpush(SqStack&S,inte) { if(S.top==MAX) {cout<<”栈满\n”; return; } S.st[S.top]=e; S.top+=1; } voidpop(SqStack&S,int&e) { if(S.top==0) {cout<<”栈空\n”;return;} S.top-=1; e=S.st[S.top]; } voidprint(SqStackS) { cout<<”栈的各个元素如下: \n”; for(intI=0;I cout< cout< } voidmain() { SqStackS; //初始化 cout<<”初始化栈\n”; InitStack(S); cout<<”栈底和栈顶: ”< //入栈 cout<<”5个元素入栈\n”; for(intI=0;I<5;I++) { push(S,2*I+1); cout<<”栈顶为: ”< } print(S); //出栈 intx; pop(S,x); cout<<”出栈元素为: ”< print(S); } //循环队列的基本操作 #include #defineMAX8 typedefstruct { intbase[MAX]; intfront; intrear; }SqQueue; /***********初始化**************/ voidInitQueue(SqQueue&Q) { Q.front=Q.rear=0; } //******求队列长度******// intQueueLength(SqQueueQ) { return(Q.rear-Q.front+MAX)%MAX; } //*****入队列****************// voidEnQueue(SqQueue&Q,inte) { if((Q.rear+1)%MAX==Q.front) cout<<”队列满! ”< else {Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAX;} } //*******遍历队列******// voidtraverse(SqQueue&Q) { intI,k; if(Q.front<=Q.rear) k=0; else k=1; switch(k) { case0: for(I=Q.front;I cout< break; case1: for(I=Q.front;I cout< for(I=0;I cout< break; } } /**************出队************/ intDeQueue(SqQueue&Q,int&e) { if(Q.rear==Q.front)return–1; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAX; return1; } voidmain() { SqQueueQ; InitQueue(Q); intj,m,x; for(j=0;j<7;j++) EnQueue(Q,2*j); traverse(Q); m=QueueLength(Q); cout<<”\n长度”< EnQueue(Q,500); traverse(Q); DeQueue(Q,x); m=QueueLength(Q); cout<<”\n长度”< traverse(Q); EnQueue(Q,500); m=QueueLength(Q); cout<<”\n长度”< traverse(Q); DeQueue(Q,x); m=QueueLength(Q); cout<<”\n长度”< traverse(Q); EnQueue(Q,600); m=QueueLength(Q); cout<<”\n长度”< traverse(Q); } 3实验要求 按要求编写实验程序,将实验程序上机调试运行,并提交实验报告。 实验3二叉树的基本操作 1实验目的 (1)掌握二叉树的非线性和递归特点。 (2)熟练掌握二叉树的存储结构。 (3)熟练掌握二叉树的各种遍历操作和其它操作的实现方法。 2实验内容 设计一个可进行二叉树基本操作的演示程序。 【基本要求】 实现下列六种基本运算: (1)创建二叉树; (2)先序遍历二叉树;(3)中序遍历二叉树;(4)后序遍历二叉树;(5)层序遍历二叉树;(6)求度为1的结点的个数;(7)求叶子结点的个数;(8)求度为2的结点的个数。 二叉树以链式结构表示,主程序以菜单方式的用户界面。 【测试数据】自定 //二叉树的基本操作 #include typedefstructnode//定义结点 { chardata; structnode*lchild,*rchild; }BinTNode; typedefBinTNode*BinTree;//定义二叉树 voidCreateBinTree(BinTree&T);//先序创建二叉树 voidPreOrder(BinTreeT);//先序遍历二叉树 voidInOrder(BinTreeT);//中序遍历二叉树 voidPostOrder(BinTreeT);//后序遍历二叉树 intonechild(BinTreeT);//求度为1的结点的个数 intleafs(BinTreeT);//求叶子结点的个数 inttwochild(BinTreeT);//度为2的结点的个数 voidtranslevel(BinTreeb)//层序遍历二叉树 voidmain() { intn; BinTreeT; charch1,ch2; cout<<"Welcometoenterthetestingprogramforbintreebasicoperator"< cout<<"PleaseChose"< ch1='y'; while(ch1=='y'||ch1=='Y') { cout<<"A--------building\n"; cout<<"B------PreOrder\n"; cout<<"C------InOrder\n"; cout<<"D-------PostOrder\n"; cout<<”E-------translevel\n”; cout<<"F------onechild\n"; cout<<"G-----twochild\n"; cout<<"H------leafs\n"; cout<<"X-------Quit\n"; cin>>ch2; switch(ch2) { case'a': case'A': cout<<"请输入按先序建立二叉树的结点序列: \n"; CreateBinTree(T); break; case'b': case'B': cout<<"二叉树的先序遍历序列: \n"; PreOrder(T); break; case'c': case'C': cout<<"二叉树的中序遍历序列: \n"; InOrder(T); break; case'd': case'D': cout<<"二叉树的后序遍历序列: \n"; PostOrder(T); break; case'f': case'F': cout<<"二叉树的单孩子结点数: \n"; n=onechild(T); cout< break; case'g': case'G': cout<<"二叉树的双孩子结点数: \n"; n=twochild(T); cout< break; case'h': case'H': cout<<"二叉树的叶子结点数: \n"; n=leafs(T); cout< break; case‘e’: case‘E’: cout<<"二叉树的层序遍历序列: \n"; translevel(T); break; case'x': case'X': ch1='x'; break; } } } voidCreateBinTree(BinTree&T) { charch; cin>>ch; if(ch=='0')T=NULL; else { T=(BinTNode*)newBinTNode; T->data=ch; CreateBinTree(T->lchild); CreateBinTree(T->rchild); } } voidInOrder(BinTreeT) { if(T) { InOrder(T->lchild); cout< InOrder(T->rchild); } } voidPostOrder(BinTreeT) { if(T) { PostOrder(T->lchild); PostOrder(T->rchild); cout< } } voidPreOrder(BinTreeT) { if(T) { cout< PreOrder(T->lchild); PreOrder
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验教学 大纲