数据结构与算法实验指导书

1、数据结构与算法实验报告綦娜娜 编哈尔滨理工大学荣成学院实验一顺序表的实现和应用一、实验目的1、掌握顺序表的定义；2、掌握顺序表的基本操作，如查找、插入、删除及排序等。二、实验内容1、 编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主 函数验证此算法，并分析算法的时间复杂度2、 编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并 分析算法的时间复杂度3、 编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度4、编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法， 并分析算法的时间复杂

2、度三、实验提示1、#inelude #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度*/in t locate(list *l,i nt x)/代码int i;for(i=0;ilast;i+)if(l-datai=x)return i+1;return -1;main ()list b;int x,i,p;b.last=10;for(i=0;ib.l ast;i+)b.datai=i+2;printf(请

3、输入x的值：”)；scan f(%d，& x); p=locate(&b,x);if(p=-1)prin tf( no!);elseprin tf(positi on=%dn,p);请巒人藍的值:5position4Press any key to continue请输入蓝的值：100；no! Press any key to continue.时间复杂度T(n)=O(n);2、#inelude #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并

4、分析算法的时间复杂度*/int delete(list *l,int i)int j,k,p; /if(i=0&i last)for(j=0;jlast;j+) / if(j=i-1) p=l-dataj;定义一个用来保存被删原素; 只接受有效输入/for(k=j;klast;k+) return 0;main ()遍历数组 匹配保存被删原素；/前进一位;l-datak=l-datak+1;break; l-last=l-last-1; return p; /退出循环对于此题来说可以输出p;list b;int x,i;b.last=10;for(i=0;ib.last;i+) b.datai

5、=i+2;printf(请输入x的值：);scan f(%d，& x);if(delete(&b,x)!=O)for(i=0;ib .l ast;i+)prin tf(%3d,b.datai);elseprin tf(Error!);青输人询值 5；234 578 9 10 UPress any key to continueII时间复杂度T(n)=O(n);3、#inelude #defi ne MAXSIZE 20typedef structint dataMAXSIZE;int last;list;I*编写函数，实现在顺序表中第i个位置上插入值为 x的元素，编写主函数验证此算法, 并分析

6、算法的时间复杂度*/int in sert(list *l,i nt x,i nt i)int j,k;if(ilast+1 &i0)if(i=l-last+1)II特殊值last+1要插入到整个数组之后l-datal-last=x;elsefor(j=0;jlast;j+)if(j=i-1)/ 匹配for(k=l-last;kj;k-)II将所选插入位置之后原素后移l-datak=l-datak-1;l-dataj=x;II把x赋值给所选位置break;/数值长度加一无效位置l-last=l-last+1; return 1;return 0;/main ()list b;int x,i;b

7、.last=10;for(i=0;ib.l ast;i+)b.datai=i+2;printf(请输入x的值：);scan f(%d，& x);if(in sert(&b,66,x)!=0)for(i=0;ib .l ast;i+)prin tf(%3d,b.datai);elseprin tf(Error!);價输入y的值=52345666789 10 llPress any key to continueError!Press any key to continuE/时间复杂度T(n)=O(n);#i nclude #defi ne MAXSIZE 20typedef structint

8、dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法,并分析算法的时间复杂度*/void fun( list *l)儿低int i,ou=0,temp; for(i=0;ilast;i+)if(l-datai%2=0)ou个位置的原素交换位置temp=l-dataou; l-dataou=l-datai; l-datai=temp; ou+=1;/这个代码有点晦涩，但空间时间复杂度是鸡i计数，ou代表偶数个数/循环/判断是不是偶数，如果是偶数的话和当前第/偶数个数加一printf(当前数组中偶数有 d(,奇数有 d(

9、:n,ou,l-last-ou);mai n()list b;int i=0,m=0;b.last=10;printf(”请输入数组元素的值：n);for(i=0;ib.l ast;i+)prin tf(b.data%d=,i);scan f(%d, &b.datai);fun(&b);for(i=0;ib.l ast;i+)prin tf(%3d,b.datai);.0ii：3=4=55 -6=8E=9 g=1=2=10/时间复杂度为T(n)=O(n);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验二 链表的实现和应用一、实验目的1、掌握链表的定义；2、掌握链表

10、的基本操作，如查找、插入、删除、排序等。二、实验内容1、单链表的创建2、单链表的查找3、单链表的排序4、单链表的删除5、链表的应用-约瑟夫环问题三、实验提示1、/创建单链表，要求：结点个数为n个，每个节点数据域的值必须小于m编辑主函数验证之。#i nclude #i nclude typedef struct aa int data;struct aa *n ext; NODE;NODE *Creatlink(int n, int m)int i;NODE *tou,*p;/tou 头结点tou=(NODE*)malloc(sizeof(NODE);/ 创建并初始化头结点tou- next=N

11、ULL;tou-data=n;printf(” 请输入d个小鱼d的数，中间用空格隔开：n,n,m); for(i=0;idata);if(p-data=m)printf(输入的第d个数据大于 d,GGn,i+1,m);exit(0);/程序强制中断，好像是在头文件stdlib.h 里p-n ext=tou-n ext;tou-n ext=p;return tou;outli nk(NODE *h) NODE *p;p=h-n ext;printf(nnTHE LIST :nn HEAD ”); while(p) prin tf(-%d ”,p-data);p=p-n ext;prin tf(n

12、);main () NODE *head;head=Creatli nk(8,22);outl in k(head);请输人客个小鱼瞬的数，中间用生格隔开：12 3 4 5 6 7 3THE LIST :HEAD -3 -7 -6 -5 -4 -3 -2 -1 J-ress any key to uonting.1 2 3 100 5 6 7 8嫦入的第4个数据大于22, GGPress any ksy to continue2、/查找值为ch的节点在链表中是否出现，如果存在，返回在链表中位序，如果不存 在返回0#i nclude #i nclude #define N 8typedef st

13、ruct list int data;struct list *n ext; SLIST;SLIST *creatlist(char *);void outlist(SLIST *);int fun( SLIST *h, char ch)int i;SLIST *p;p=h-next;/p赋值为寿元节点for(i=0;idata=ch)return i+1;p=p-n ext;return 0;main () SLIST *head; int k; char ch;char aN=m,p,g,a,w,x,r,d;head=creatlist(a);outlist(head);prin tf(E

14、 nter a letter:);sca nf(%c, &ch);k=fu n( head,ch);if (k=0) prin tf(nNot foun d!n);elseprin tf(The seque nee nu mber is : %dn ”,k);SLIST *creatlist(char *a)int i;SLIST *tou,*p;tou=(SLIST*)malloc(sizeof(SLIST);/ 创建并初始化头结点tou-data=N;tou- next=NULL;for(i=0;idata=ai;p-n ext=tou-n ext;tou-n ext=p;return t

15、ou;void outlist(SLIST *h) SLIST *p;p=h-n ext;if (p=NULL) prin tf(nThe list is NULL!n ”);else prin tf(nH ead);do prin tf(-%c,p-data); p=p-n ext; while(p!=NULL);prin tf(-E ndin ”);Not found!Press any key t口 continue3、/去偶操作，链表中各节点按数据域递增有序链接，函数fun的功能是，删除链表中数据域值相同的节点，使之只保留一个#i nclude #i nclude #define N

16、8typedef struct list int data;struct list *n ext; SLIST;voidfun( SLIST *h)SLIST *p,*sha nchu; p=h-n ext;while(p- next!=NULL) /用于遍历的指针p,用于删除的指针shanchu/p为寿元节点/终止条件if(p-data=p-n ext-data)sha nchu=p-n ext;p-n ext=sha nchu-n ext; free(sha nchu);else/判断是否有重复原素p=p-n ext;SLIST *creatlist(i nt *a) SLIST *h,*

17、p,*q; int i;h=p=(SLIST *)malloc(sizeof(SLIST); for(i=0; idata=ai; p_n ext=q; p=q;p_n ext=0;return h;void outlist(SLIST *h) SLIST *p;p=h-n ext;if (p=NULL) printf(nThe list is NULL!n”);else prin tf(nHead);do pri ntf(-%d,p-data); p=p- next; while(p!=NULL); prin tf(-E ndn);mai n() SLIST *head; int aN=1,

18、2,2,3,4,4,4,5;head=creatlist(a);prin tf(nThe list before delet ing :n); outlist(head);fun( head);prin tf(nThe list after deleti ng :n); outlist(head);The list before deleting :Head-)*1 - 2-2-3-)*4- 4- 4- 5-EndThe list after deleting :Head-l-2-3-4-5-EndPress any key to continue4、/在main函数中多次调用fun函数，每调

19、用一次fun函数，输出链表尾部节点中的 数据，并释放该节点，使得链表缩短。#i nclude #i nclude #define N 8typedef struct list int data;struct list *n ext; SLIST;void fun( SLIST *p)SLIST *bianli,*shanchu;/ 遍历，删除bia nli=p;while(bia nl i- next-next!=NULL)bia nli=bia nli-n ext;printf(%d,bianli-next-data);/ 输出shanchu=bianli-next;/ 释放free(sha

20、 nchu);bia nli- next=NULL;SLIST *creatlist(i nt *a) SLIST *h,*p,*q; int i;h=p=(SLIST *)malloc(sizeof(SLIST);for(i=0; idata=ai; p_n ext=q; p=q;p_n ext=0;return h;void outlist(SLIST *h) SLIST *p;p=h-n ext;if (p=NULL) prin tf(nThe list is NULL!n ”);else prin tf(nHead);do printf(-%d,p-data); p=p-next; w

21、hile(p!=NULL);prin tf(-E ndn);main () SLIST *head;int aN=11,12,15,18,19,22,25,29;head=creatlist(a);prin tf(nOutput from head:n); outlist(head);prin tf(nOutput from tail: n);while (head- next != NULL)fun( head);prin tf(nn);prin tf(nO utput from head aga in :n); outlist(head);Output from head：Head-ll-

22、12-15-18-19-22-25-29-EndOutput from til：29Output from head 也刖in :Hl6ad-11-12-15- 18- 19-22-25-End 25Output froon head again :Head-11-12-15-18-19-22-End 22Output from h呂宣日 again :Headl-ll-12- 15- 18- 19-End 19Output from head iftgain :Head-1l-12-15-18-BndISOutput from head again :Hyad-ll-12-15-End15O

23、u.tjut from head aigain :|Hgid-ll-L2-EndOutput from head again :Read-U-12-End12Output from head again :Head-K-End11Output from head again :The list is NULL!Press any key to continue,5、实现约瑟夫环函数(选做)#i nclude #i nclude typedef struct list int data;struct list *n ext; SLIST;SLIST *creatlist(int m)int i;

24、SLIST *tou,*p,*wei;/头指针生成节点指针尾指针tou=(SLIST*)malloc(sizeof(SLIST);/ 头节点wei=tou;printf(”请输入c个数用空格隔开：for(i=0;idata);wei-n ext=p; wei=p;wei-n ext=tou-n ext;return tou;void outlist(SLIST *h,i nt m,i nt c)int i;SLIST *p,*sha nchu;p=h-n ext; while(p!=p- next)for(i=1;in ext;sha nchu=p-n ext;prin tf(%d ,sha

25、nchu-data);p-n ext=sha nchu-n ext; free(sha nchu);p=p-n ext;prin tf(%d,p-data);free(p);free(h);n ”,m);/尾插法/令最后一个原素指向首元结点成环/用于遍历的指针p,用于删除的指针shanchu/p指向首元结点/当环中只剩下一个原素时结束/根据输入的c剔除节点/sha nchu指向当前要剔除的节点/将shanchu指针指向的节点出环/输出最后的一个节点的内容mai n() SLIST *head;int m,c;printf(请分别输入m和c的值：);scan f(%d,%d,&m,&c);hea

26、d=creatlist(m);outlist(head,m,c);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验三 栈的实现和应用一、实验目的1、掌握栈的建立方法；2、掌握栈的基本操作，如入栈、出栈、判断空栈等;3、栈的应用。二、实验内容1、顺序栈的初始化2、判断栈是否为空3、顺序栈出栈4、顺序栈入栈5、栈的应用-汉诺塔三、实验提示1、栈的基本操作，按提示将函数补充完整#i nclude #i nclude #defi ne STACK_MAX 100 typedef structint top;int dataSTACK_MAX;初始化顺序栈*/判断栈是否为空*

27、/空0/非空1 stack;void in it(stack *st) /*st-top=0;int Empty(stack *st)/*if(st_top=O)return 0;elsereturn 1;int pop(stack *st) /*出栈 */retur n st-data-st-top;入栈*/void push(stack *st,i nt data) /* st-datast-top+=data;int main( void)stack st;in it(&st);push(&st,5);push(&st,6);prin tf(%d,pop( &st); return 0;

28、SPress any key t口 continue2、#inelude void mai n()void hanoi(int n, char on e,ehar two,ehar three);/* 对hanoi函数的声明*/int m;prin tf(i nput the nu mber of diskes:);scan f(%d, &m);prin tf(The step to moveing %d diskes:n,m);han oi(m,A,B,C);void hanoi(int n, char on e,char two,char three)/* 定义hanoi函数，将n个盘从

29、one座借助two座，移到three座*/static k=1;void move(char x,char y);咩有声明 在此需要提前声明才能使用if(n=1)到第三个上prin tf(第 %d:,k+);move(on e,three);elsehanoi(n-1, on e,three,two);三个座当桥梁prin tf(第 %d:,k+);move(on e,three);hanoi(n-1,two ,on e,three);个盘上，第一个盘当桥梁/定义静态变量k用来标明走了多少步/因为move函数定义在该函数的后边且之前/当第一个座上仅剩一个盘的时候将此盘移/输出是第多少步/移动I

30、I将前n-1个盘从第一个座移到二个座上，第/将上边转移到第二个座上的盘转移到第三void move(char x,char y) /*定义 move函数 */prin tf(%c-%cn ”,x,y);input the number of diskes:4 The step to moveing 4 diskes: 第1步:A-B第2步:A一C第M步:BC第4參；當5玉:第&步:C 一B第F步:ATB第8玉:A-C第9玉岀一 C第 10 步:BAAC第 1!3 步:AB第14涉:A_CCPress any key to continue四、实验报告要求1、撰写实验报告；2、对实验中出现的问题

31、和结果进行总结。实验四 队列的实现和应用一、实验目的1、掌握队列的建立方法；2、掌握队列的基本操作，如出队、入队、判断队空等;3、队列的应用。二、实验内容1、顺序队列的初始化2、判断队列是否为空3、顺序队列出队4、顺序队列入队5、队列的应用-回文判断三、实验提示1、/队列的基本操作，按提示将函数补充完整#i nclude #i nclude #defi ne STACK_MAX 100 typedef structint front, rear;int data1STACK_MAX; Queue;初始化队列*/判断队列空*/1代表空/0代表非空void in itQueue (Queue *q

32、) /* q_fron t=q_rear=0;int EmptyQueue(Queue *q)/* if(q-fron t=q-rear) return 1;elsereturn 0;int DeQueue(Queue *q) /* 出队列 */判断需要出队时队列是否为空if(q-rear=q _front)prin tf(当前队列已经空了。);exit(0);elseretur n q_data1q_fr on t+;/将队头原素出列然后队头指针加一void In Queue(Queue *q,i nt data) /*if(q-rear=STACK_MAX)printf(”当前队列空间已满

33、。exit(0);elseq_data1q_rear=data; q-rear+;int mai n()Queue q;入队列*/判断需要入队时队列是否已满）;/入队in itQueue( &q);In Queue(&q,1);In Queue(&q,2);In Queue(&q,3);prin tf(%dn,DeQueue(&q);prin tf(%dn,DeQueue( &q);prin tf(%dn,DeQueue(&q);I：ress any key to continue2、/判断给定的字符序列是否是回文（提示：将一半字符入栈）#in clude #i nclude #defi ne

34、 STACK_MAX 100 typedef structint top;int dataSTACK_MAX; stack;typedef structint front, rear;int data1STACK_MAX; Queue;void in it(stack *st) /*st-top=0;int Empty(stack *st)/*if(st_top=O) return 1;elsereturn 0;int pop(stack *st) /*if(st-top=0)初始化顺序栈*/判断栈空*/出栈*/printf(栈已空!);exit(0);elsechar c;c=st_data

35、_st_top;return (int ) c;void push(stack *st, int data) /*入栈 */if(st-top=STACK_MAX-1)prin tf(栈已空！);exit(0);elsest-datast-top+=data;void initQueue (Queue *q) /*初始化队列 */q_fron t=q_rear=O;int EmptyQueue(Queue *q)/* 判断队列空 */if(q-fron t=q-rear)return 1;elsereturn 0;int DeQueue(Queue *q) /* 出队列 */retur n (

36、in t)q-data1q-fr on t+;void InQueue(Queue *q,int data) /*入队列 */q_data1q_rear+=data;int IsHuiWe n(stack *st,Queue *q,char * a)int i,zhan,dui,k=0;/i计数，zhan代表应往栈里边传几个原素，dui代表应从第几个原素开始往队列传值，k计算数组a中有多少原素while(ak!=0)k+;if(k%2=0)zha n=k/2;dui=k/2+1;if(k%2=1)zha n=k/2;dui=k/2+2;for(i=0;izha n;i+)push(st,ai)

37、;for(i=zha n;ik;i+)In Queue(q,ai); for(i=0;ik/2;i+)if(pop(st)!=DeQueue(q) return 0;return 1;int mai n()char a10=a,b,c,d,b,a; stack st;Queue q;init(& st);in itQueue( &q);prin tf(%dn,lsHuiWe n(&st, &q,a);0Press any key to continue四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验五二叉树的遍历及应用一、实验目的1. 掌握二叉树的定义；2 .掌握二

38、叉树的基本操作，如二叉树的建立、遍历、结点个数统计、树的深度计算等。二、实验内容用递归的方法 实现以下算法：1 以二叉链表表示二叉树，建立一棵二叉树；2 .输出二叉树的中序遍历结果；3 .输出二叉树的前序遍历结果；4 .输出叉树的后序遍历结果；5计算二叉树的深度；6 .统计二叉树的结点个数；7、二叉树的层序遍历结果。三、实验提示1、按要求将程序补充完整#i nclude #in elude #i nclude #defi ne NULL 0typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree

39、;/二叉树的建立BiTree Create(BiTree T)char ch;设置一个接收数据的变量sca nf(%c, &ch);if(ch=#)T=NULL;/ 设置结束符elseT = (BiTree)malloc(sizeof(BiTNode);/ 生成心节点T-data = ch;T-lchild = Create(T-lchild);递归建立T-rchild = Create(T-rchild);return T;/二叉树的前序递归遍历void Preorder(BiTree T)if(T)prin tf(%c ”,T-data);Preorder(T-lchild);Preord

40、er(T-rchild);/统计二叉树的结点个数int Sumleaf(BiTree T)int n;if(T=NULL) retur n 0;elsen=1+Sumleaf(T-lchild)+Sumleaf(T-rchild); return n;/二叉树的中序递归遍历void zhon gxu(BiTree T)if(T)Preorder(T-lchild);prin tf(%c ,T-data);Preorder(T-rchild);/二叉树的后序递归遍历void houxu(BiTree T)if(T)Preorder(T-lchild);Preorder(T-rchild);prin tf(%c ,T-data);/计算二叉树的深度int Depth(BiTree T)谁大选谁int n;if(T=NULL)return 0;elseif(Depth(T-lchild)Depth(T-rchild) return Depth(T-lchild)+1; elsereturn Depth(T-rchild)+1;void mai