《数据结构与算法分析》实验教学大纲

《数据结构与算法分析》实验教学大纲

一、教学目的《数据结构与算法分析》是数据科学与大数据技术专业的一门重要的专业基础课，课程旨在使学生学会计算机加工的数据对象的特性，学会数据的组织方法，以便选择合适的数据的逻辑结构及存储结构，并进行相应的运算通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力实验是该课程实践教学的重要环节，目的是培养学生根据求解问题的性质选择合理的数据结构，提高算法分析、设计、编程以及控制求解算法的时间、空间复杂性的能力

二、基本要求《数据结构与算法分析》是计算机专业的专业核心基础课程，其先修课程有至少一门高级语言数据结构与算法分析课程将覆盖计算机软件实现中的大部分的基本算法，并具有一定的深度和广度，使学生对计算机常用基础算法有一个全盘的了解；通过此课的学习，学生应该具有针对所给的问题设计和实现高效算法的能力通过上机实验，将使学生熟悉、掌握课堂教学中所学的大部分算法同时，上机实验是对学生在软件设计方面的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风通过理论联系实际，以最终提高学生动手操作的能力以及分析问题的能力

三、实验项目设置实验试验学实验名称试验要求试验类型每组人数序号时1顺序表2必修设计12单链表2必修设计1栈必修设计3214队列2必修验证15二叉树的遍历4必修验证16分治法4必修设计1char GetQueue_CSqQueue*Q{〃若队列不为空，则返回队首元素，否则返回NULLint e;ifEmptyQueue_CQ{printfnQueue isempty\nH;returnO;}else{e=Q-datas[Q-front+1%MAXSIZE];return e;}}//GetQueue_C//入队int EnQueue_CSqQueue*Q,int e{〃将元素e插入到队列中，作为新的队尾操作成功返回1,否则返回0ifQ-front==Q-rear+1%MAXSIZE〃队满{printfnQueue isfull.\nH;return0;}else{Q-rear=Q-rear+1%MAXSIZE;Q-datas[Q-rear]=e;return1;}}//EnQueue_C〃出队int DeQueue_CSqQueue*Q{〃删除队头元素，若操作成功返回1,否则返回0ifEmptyQueue_CQ{printfnQueue isempty.\nn;return0;}else{Q-front=Q-front+1%MAXSIZE;return1;}}//DeQueue_C〃输出队void PRINTSqQueue*Qint i;ifQ-front!=Q-rearprintf当前循环队列中从头到尾的元素为”;i=Q-front;whilei!=Q-reari=i+l%MAXSIZE;printfn%d;Q-datas[i];elseprintf当前循环队列为空!putchar\n；mainSqQueue*Q;int n;int i,j,k,sl,s2;Q二SqQueue*mallocsizeofSqQueue;InitQueueQ;EnQueue_CQ,l;printf请输入杨辉三角的层数\nn;scanfn%dH,n;printfnl\nn;fori=2;i=n;i++{//fork=0;kn-i;k++//printf；forj=l,s1=O;ji;j++{int s2;s2=GetQueue_CQ;DeQueue_CQ;printf,,%dH,sl+s2;printf；EnQueue_CQ,s l+s2;sl=s2;printfnln;EnQueue_CQ,l;printfn\nn;

1、分析、理解程序

2、运行、验证示例程序能否打印杨辉三角试描述什么叫杨辉三角

3、试输入不同的行数调试程序，当行数超过11产生什么问题，为什么实验五二叉树的遍历

一、目的掌握二叉树的存储结构和遍历递归和非递归

二、要求用递归算法实现二叉树的遍历

三、示例程序#includestdio.h#includestdlib.h#define MAXCSIZE100typedef intTElemType;typedef struct BitNode{TElemType data;structBitNode*lchild,*rchild;}BitNode,*BitTree;/*二叉树的构建*/BitTree CreateBiTreevoid{BitTree bt;TElemType x;scanfn%dH,x;ifx=1bt=NULL;else{bt=BitTreemallocsizeofBitNode;bt-data=x;bt-lchild=CreateBiTree;bt-rchild=CreateB iTree;}return bt;}/*二叉树的中序遍历*/void InOrderTraverseBitTree bt{ifbt!=NULL{InOrderTraversebt-lchild;printfH%dn,bt-data;InOrderTraversebt-rchild;}}/*二叉树的后序遍历列void PostOrderTraverseBitTree bt{ifbt!=NULL{PostOrderTraversebt-lchild;PostOrdcrTravcrscbt-rchild;printfn%dn,bt-data;}/*二叉树的先序遍历刃void PreOrderTraverseBitTreebt{ifbt!=NULL{printfn%dn,bt-data;PreOrderTraversebt-lchild;PreOrderTraversebt-rchild;int main{BitTreebt;bt=CreateB iTree;printfn\n中序遍历”;InOrderTraversebt;printfn\n后序遍历”;PostOrderTraversebt;printfM\n先序遍历PreOrderTraversebt;printfn\nn;

四、实验内容

1、分析、理解程序

2、设计输入一棵树，看程序运行结果与自己计算的遍历顺序是否一致实验六分治法

一、目的理解递归与分治策略的思想和方法

二、要求

三、示例程序分析并掌握“二分搜索问题”的递归与分治算法示例；二分搜索的先决条件表中结点按关键字有序，且顺序一维数组存储二分法思想取中，比较1求有序表的中间位置mid2若r[mid],key=二k,查找成功；若keyk,在左子表中继续进行二分查找；若r[mid].keyk,则在右子表中继续进行二分查找算法描述int Searchbinelemtype r[],int n,keytype k{//r[l]..r[n]是按key排序的n个元素，在表中查找ki=l；j=n;whilei=j{mid=i+j/2;〃取中if k==r[mid],key returnmid;//查找成功else ifk r[mid].key j-mid-1;//在左半部分继续查找else i=niid+1;〃在右半部分继续查找return0;//k不在该有序表中r[j].keykr[i].key请分析“二分搜索问题”的时间复杂性和空间复杂性

九、实验考核结合平时实验过程中的程序调试、实验报告，实验成绩占课程总成绩的20虬

四、实验项目说明实验一顺序表

一、目的熟练掌握线性表的基本操作在顺序存储结构上的实现

二、要求掌握顺序表的建立、查找、插入、删除等基本操作

三、示例程序#includestdio.h#includestdlib.h#define MAXSIZE30struct SqListchar datas[MAXSIZE];int length;；typedef structSqList SqList;//建立顺序表L voidcreat_SqSqList*L char x;int j;〃按要求建立顺序表printf按要求输入顺序表初始时的元素切换用回车，以#结束\n”；fflushstdin;scanfH%cn,x;j=0;while x!=#L-datas[jJ=x;L-length++;j++;fflushstdin;scanfn%cn,x;}〃查找操作int LocateElem_SqSqList*L,char x{〃在顺序线性表L中查找第1个值与x相等的元素，若找到，则返回其在L中的位序，否则返回0int k;k=l;〃k的初值为第1个元素的位序whilek=L-lengthL-datas[k-l]!=x k++;ifk=L-lengthreturn k;elsereturn0;〃求顺序表长度int Get_lengthSqList*Lreturn L-length;〃插入操作voidListInsert_Sq SqList*L,int i,char e{〃在顺序表L的第i个位置前插入一个新的元素exlxvL*xtxxlxsixvL*xt*xtxxjxxjxxjsxjxxjxxjxXJXxyx XJX✓Jx〃删除操作void ListDelete_SqSqList*L,int i{〃在顺序表L中删除第i个数据元素int k;ifivl||iL・length||L-length=O〃出错处理,考虑算法的健壮性printfnerrorn;〃i值不合法或表己空则出错else{for k=i;kL-length;k++〃将第i+1至第n个元素逐一向前移一个位置L-datas[k-1]=L-datas[k];L-length=L-length-1;//将顺序表的长度减1〃输出顺序表void PRINTSqList*L{int i;printf顺序表的当前值为\nn;fori=0;iL-length;i++printfH%c H,L-datas[iJ;printfH\nn;main{SqList*L;int k;int i;charx;//初始化顺序表L=SqList*mallocsizeofSqList;L-length=O;〃空表长度为0printf请选择您要进行的操作\nH;printfCO:退出\n”;printffl:建立顺序表L\n”;printf2:查找操作查找某个元素的位序\n”；printf3:求顺序表的长度\n；printf4:插入操作在顺序表L的第i个位置前插入一个新元素e\nH;printf5:删除操作删除顺序表L中的第i元素\nprintf”6:输出操作输出顺序表的当前值\n”;scanfn%d\k;while k0||k6printf您只能选择06请重新输入:；scanfn%dn,k;while k=0k=6switchkcase0:exitO;case1:creat_SqL;break;case2:printf请输入待查找的元素x:；fflushstdin;scanfn%cn,x;printfH%d在顺序表中的位序为:％d\n”,x,LocateElem_SqL,x;break;case3:printf顺序表的长度为%d\nn,Get_lengthL;break;case4:printf”请输入待插入元素的位置i及元素的值x:n;scanfn%dn,i;fflushstdin;scanfH%cM,x;ListInsert_Sq L,i,x;break;case5:printf请输入待删除元素的位置i:n;scanfn%dM,i;ListDclctc_SqL,i;break;case6:PRINTL;break;default:printf您只能选择0-6,请重新输入:；printf（H---rjC rjC{|C rjCr|C—\n），printf（请选择您要进行的操作\nH）;printf（O:退出\n）printfCl:建立顺序表L\n”）;printf（2:查找操作（查找某个元素的位序）\n）printf（3:求顺序表的长度\n”）;printf（”4:插入操作（在顺序表L的第i个位置前插入一个新元素e）\nn）;printf（5:删除操作（删除顺序表L中的第i元素）\n”）；printf（”6:输出操作（输出顺序表的当前值）W”）;scanf（n%dn,k）;））

四、实验内容分析、理解程序完成插入操作的函数设计调试程序建立12个元素的顺序表SqList={c,h,i,n,a,w,e,1,c,o,m,e）,分别实现以下操作:1）查找元素y在SqList中的位序，输出为0则表示“y不在SqList中”；2）在SqList的元素6之前插入一个新元素#,输出插入后的结果；3）删除SqList中第8个元素，输出删除后的结果实验二单链表

一、目的熟练掌握线性表的基本操作在链式存储结构上的实现

二、要求掌握单链表的建立、插入、删除等基本操作；

三、示例程序#includeHstdio.h#includeHstring.hn#includeHstdlib.hn#includenctype.h〃定义结点chardata

[10];〃结点的数据域为字符串struct node*next;〃结点的指针域JListNode;typedef ListNode*LinkList;//自定义LinkList单链表类型typedef structnodeLinkList CreatListR1void;ListNode*LocatcNodcLinkList head,char*kcy;void DeleteListLinkList head,char*key;void printlistLinkList head;void DeleteAllLinkListhead;//==========主函数=============void mainchar ch

[10],num

[2];LinkListhead;head=CreatListR1;〃用尾插入法建立单链表，返回头指针printlisthead;〃遍历链表输出其值printfn Deletenode y/n:”；//输入“y“或”n”去选择是否删除结点scanfn%sH,num;ifstrcmpnum,nyn==O||strcmpnum,nYn==0{printfHPlease inputDelete_data:H;scanfn%sH,ch;//输入要删除的字符串DeleteListhead,ch;printlisthead;，DeleteAllhead;〃删除所有结点释放内存〃=====用尾插入法建立带头结点的单链表=======LinkList CreatListRlvoidcharch

[10];LinkListhead=LinkListmaHocsizeofListNode;〃生成头结点ListNode*s,*r,*pp;『head;r-next=NULL;printfHInput#to end；〃输入代表输入结束printfHPlease inputNode_data:n;scanf”%s”,ch;〃输入各结点的字符串whilestrcmpch,n#n!=O{pp=LocateNodehead,ch;〃按值查找结点，返回结点指针ifpp==NULL{〃没有重复的字符串，插入到链表中s=ListNode*mallocsizeofListNode;strcpys-data,ch;r-next=s;r=s;r-next=NULL;printfHInput#to end;printfHPlease inputNode_data:H;scanfn%su,ch;return head;〃返回头指针//======按值查找结点，找到则返回该结点的位置，否则返回NULL ListNode*LocateNodeLinkListhead,char*keyListNode*p=head-next;〃从开始结点比较while pstrcmpp-data,key!=0〃直至lj p为NULL或p-data为key止p=p-next;〃扫描下一个结点return p;〃若p=NULL则查找失败，否则p指向找到的值为key的结点〃======删］除带头结点的单链表中的指定结点=====void DeleteListLinkListhead,char*key ListNode*p,*r,*q=head;p=LocateNodehead,key;〃按key值查找结点的KL*zts zfsts zjsXTS ZTS✓TS//======#丁印链表====void printlistLinkListhead ListNode*p=head-next;〃从开始结点打印whilep{printfn%s,n,p-data;p=p-next;printfn\nn;，〃======删除所有结点释放空间========void DeleteAllLinkListhead ListNode*p=head,*r;whilep-next{r=p-next;freep;P=r;freep;

四、实验内容1分析、理解程序，将void DeleteListLinkListhead,char*key函数补充完整

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

一、目的掌握栈的基本特点，能把递归算法运用栈转换成非递归算法

二、要求掌握顺序栈的建立、入栈、出栈等操作

三、示例程序#includestdio.h#includestdlib.h#define MAXSIZE10typedef struct{int datas[MAXSIZE];int top;JSqStack;void InitStackSqStack*s{s-top=-1;}//InitStackint EmptyStackSqStack*s{〃若栈空返回1;否则返回0if s-top==-l return1;else return0;}//Empty StackvoidPushSqStack*s,int e{〃若栈满返回0;否则将e入栈，并返回1ifs-top==MAXSIZE-l{printfn Overflow\nn;}else{s-top++;s-datas[s-top]=e;}//Pushint PopSqStack*s{//若栈空则返回NULL；否则返回栈顶元素，栈顶指示器递减int e;if EmptyStacks{printfnUnderflow\nn;returnO;1else{e=s-datas[s-top];s-top-;return c;}〃Pop mainSqStack*s;int k,t;sl、z s、lz slzxlz^Iz*TX^TXT**TSXJX XT**T^printf”请输入十进制的数:；scanfn%d\k;whilek!=O%Jxxlzsixslzsixsixsix%lxX7XTXXT^XT*XIXXTVXjXwhile!EmptyStacks、、、xlzslz%lzvizvizstz%lz%lz%lx%lzzj zj^T%*T%ZT^zj XIXZTSXT%*T%XT%printfn\nn;

四、实验内容补充主函数实现对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数实验四队列

一、目的掌握队列的特点和队列的基本操作

二、要求熟练掌握顺序队列的建立、入队、出队等操作

三、示例程序#includestdio.h#includestdlib.h#define MAXSIZE20typedef struct{int datas[MAXSIZE];int front,rear;JSqQueue;〃初始化队void InitQueueSqQueue*Q{Q-front=Q-rear=-1;int EmptyQueue_CSqQueue*Q{〃若队列为空，返回1,否则返回0ifQ-rear==Q-front return1;else return0;}//EmptyQueue_C//取对头元素。