新版数据结构及算法实验指导书资料

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

2、提不1、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度*/int locate(list *l,int 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;iosition4ress any key to contini_ue请输入K的

3、值！ 100-no! Press any key to continue.时间复杂度T(n)=O(n)；2、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度*/int delete(list *l,int i)int j,k,p; / if(i=0&ilast) 定义一个用来保存被删原素;/只接受有效输入for(j=0;jlast;j+) / if(j=i-1) p=l-dataj;/遍历数组 匹配for(

4、k=j;klast;k+)l-data止l-datak+1;保存被删原素；/前进一位;break;l-last=l-last-1;return p; /退出循环对于此题来说可以输出p;return 0;main()list b;int x,i;b.last=10;for(i=0;ib.last;i+) b.datai=i+2;printf( 请输入x的值：)； scanf(%d,&x);if(delete(&b,x)!=0)for(i=0;ib.last;i+)printf(%3d,b.datai);elseprintf(Error!);请输入其的值,52 3 45 7 8 9 10 UPre

5、ss any key to continueError!Press any key to continue/时间复杂度T(n)=O(n)；3、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法,并分析算法的时间复杂度*/int insert(list *l,int x,int i)int j,k;if(ilast+1&i0)if(i=l-last+1)/特殊值last+1要插入到整个数组之后 l-datal-last=x; e

6、lse for(j=0;jlast;j+)if(j=i-1)/ 匹配for(k=l-last;kj;k-)/将所选插入位置之后原素后移l-datak=l-datak-1;l-dataj=x;/把x赋值给所选位置break;l-last=l-last+1;/ 数值长度加一return 1; return 0;/无效位置 main() list b; int x,i; b.last=10; for(i=0;ib.last;i+)b.datai=i+2; printf( 请输入x的值：); scanf(%d,&x); if(insert(&b,66,x)!=0) for(i=0;ib.last;i+

7、) printf(%3d,b.datai); else printf(Error!); 睛输入丫的值；523 45 66 67 89 10 HPress any key to continueError!Press any key to continue/时间复杂度T(n)=O(n);4、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法,并分析算法的时间复杂度*/void fun(list *l)儿低int i,ou=0,te

8、mp;for(i=0;ilast;i+)if(l-datai%2=0)ou个位置的原素交换位置temp=l-dataou;l-dataou=l-datai;l-datai=temp;ou+=1;/这个代码有点晦涩，但空间时间复杂度是鸡小计数，ou代表偶数个数/循环/判断是不是偶数，如果是偶数的话和当前第/偶数个数加一printf（当前数组中偶数有 个，奇数有d个:n,ou,l-last-ou）;main()list b;int i=0,m=0;b.last=10;printf(请输入数组元素的值：n);for(i=0;ib.last;i+)printf(b.data%d=,i);scanf(%

9、d,&b.datai);fun(&b);for(i=0;ib.last;i+)printf(%3d,b.datai);IL国的国1.力t入LD-11=2、.廿 32=3：, t -1：3=4b. L La4=5 , Tut、5=66=7% mE7二8t.d=9L L L9=10目前数组中偶数有5个,奇数有衿：2 4 6 S 10 3 7 1 9 EPress any key t口 ccnitinu弓/时间复杂度为T(n)=O(n)；四、实验报告要求1、撰写实验报告;2、对实验中出现的问题和结果进行总结。实验二 链表的实现和应用一、实验目的 1、掌握链表的定义； 2、掌握链表的基本操作，如查找、

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

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

12、n() NODE *head;head=Creatlink(8,22);outlink(head);请输入个小鱼22的数，中间用空格隔开：12 3 4 5 6 7 3THE LIST :HEAD -3 -7 -6 -5 -4 -3 -2 -1J-ress any key to continuj1 2 3 100 5 6 7 8输人的第4个数据大于22： GGPress any ksy to continue2、查找值为ch的节点在链表中是否出现，如果存在，返回在链表中位序，如果不存 在返回0#include #include #define N 8typedef struct list int

13、 data;struct list *next; 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-next; return 0; main() SLIST *head; int k; char ch; char aN=m,p,g,a,W,x,r,d; head=creatlist(a); outlist(head); printf(Enter a lett

14、er:); scanf(%c,&ch); k=fun(head,ch);if (k=0) printf(nNot found!n); else printf(The sequence number 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-next=tou-next; tou-next=p; return tou; void outlis

15、t(SLIST *h) SLIST *p; p=h-next; if (p=NULL) printf(nThe list is NULL!n); else printf(nHead); do printf(-%c,p-data); p=p-next; while(p!=NULL); printf(-Endn); 一d-r-x-w-a-g-p-m-EndEnter a letter：gThe sequence nuiriber is : 6Press any key to continue.Head-d-r-i-wa-g-p-m-Bnd inter a letter；zMot found!pre

16、ss 软ny key t口 continue3、去偶操作，链表中各节点按数据域递增有序链接，函数 fun的功能是，删除链表中 数据域值相同的节点，使之只保留一个#include #include #define N 8 typedef struct list int data;struct list *next; SLIST;voidfun( SLIST *h)SLIST *p,*shanchu; p=h-next;while(p-next!=NULL)/用于遍历的指针p,用于删除的指针shanchu/p为寿元节点/终止条件/判断是否有重复原素if(p-data=p-next-data)sha

17、nchu=p-next;p-next=shanchu-next; free(shanchu);elsep=p-next;SLIST *creatlist(int *a) SLIST *h,*p,*q; int i;h=p=(SLIST *)malloc(sizeof(SLIST);for(i=0; idata=ai; p-next=q; p=q;p-next=0;return h;void outlist(SLIST *h) SLIST *p;p=h-next;if (p=NULL) printf(nThe list is NULL!n);else printf(nHead);do print

18、f(-%d,p-data); p=p-next; while(p!=NULL); printf(-Endn);main() SLIST *head; int aN=1,2,2,3,4,4,4,5;head=creatlist(a);printf(nThe list before deleting :n); outlist(head);fun(head);printf(nThe list after deleting :n); outlist(head);The list before deleting ：The list after deleting ;Head-P2-3-4-5-EndPre

19、ss any key to continue4、在main函数中多次调用fun函数，每调用一次fun函数，输出链表尾部节点中的 数据，并释放该节点，使得链表缩短。#include #include #define N 8 typedef struct list int data; struct list *next; SLIST; void fun( SLIST *p) SLIST *bianli,*shanchu;/ 遍历，删除bianli=p; while(bianli-next-next!=NULL) bianli=bianli-next; printf(%d,bianli-next-d

20、ata);/ 输出shanchu=bianli-next;free(shanchu);bianli-next=NULL;/释放SLIST *creatlist(int *a) SLIST *h,*p,*q; int i;h=p=(SLIST *)malloc(sizeof(SLIST);for(i=0; idata=ai; p-next=q; p=q;p-next=0;return h;void outlist(SLIST *h) SLIST *p;p=h-next;if (p=NULL) printf(nThe list is NULL!n);else printf(nHead);do pr

21、intf(-%d,p-data); p=p-next; while(p!=NULL); printf(-Endn);main() SLIST *head;int aN=11,12,15,18,19,22,25,29;head=creatlist(a);printf(nOutput from head:n); outlist(head);printf(nOutput from tail: n);while (head-next != NULL)fun(head);printf(nn);printf(nOutput from head again :n); outlist(head);Output

22、 frcmn head：Head-11-12-15-18-19-22-25-29-EndOutput from tail： 29Output from head 国目日in :Ke3d-ll-12-15-18-19-22-25-End 25Output froon head again :Head-ll-12-15-18-19-22-End 22Output from had again :Had-ll-12-15-18-19-End 19Output from head iftgain :Head-ll-12-15-18-BndISOutput from head again :Hyad-l

23、l-12-15-End15Outj?ut from head aigain :|Hgid-ll-L2-EndOutput from head again :Read-U-12-End12Output from head again :Head-K-End 11Output from head again ：The list is NULL!Press any key to continue,5、实现约瑟夫环函数(选做)#include #include typedef struct list int data;struct list *next; SLIST;SLIST *creatlist(

24、int m)int i;SLIST *tou,*p,*wei;/头指针 生成节点指针 尾指针tou=(SLIST*)malloc(sizeof(SLIST);/ 头节点wei=tou;printf( 请输入外数用空格隔开： for(i=0;idata);wei-next=p;wei=p;wei-next=tou-next;return tou;void outlist(SLIST *h,int m,int c)int i;SLIST *p,*shanchu;p=h-next;while(p!=p-next)for(i=1;inext;shanchu=p-next;printf(%d ,shan

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

26、m);outlist(head,m,c);情分别僦人碑1c的值I 8 3请箫人杯薮用空格隔开1 2 3 4 5 6 7 3.3615284 7Press any key to continue四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验三 栈的实现和应用天天快乐一、实验目的1、掌握栈的建立方法；2、掌握栈的基本操作，如入栈、出栈、判断空栈等;3、栈的应用。二、实验内容1、顺序栈的初始化2、判断栈是否为空3、顺序栈出栈4、顺序栈入栈5、栈的应用-汉诺塔二、实验提不1、栈的基本操作，按提示将函数补充完整#include #include #define STACK_

27、MAX 100 typedef structint top;int dataSTACK_MAX; stack;初始化顺序栈*/判断栈是否为空*/空0/非空1void init(stack *st) /*st-top=0;int Empty(stack *st)/*if(st-top=0)return 0;elsereturn 1;int pop(stack *st) /*出栈 */return st-data-st-top;入栈*/void push(stack *st,int data) /*st-datast-top+=data;int main(void)天天快乐stack st;ini

28、t(&st);push(&st,5);push(&st,6);printf(%d,pop(&st);return 0;SPress any key to continue2、#include void main()void hanoi(int n,char one,char two,char three);/* 对hanoi函数的声明*/int m;printf(input the number of diskes:);scanf(%d,&m);printf(The step to moveing %d diskes:n,m);hanoi(m,A,B,C);void hanoi(int n,c

29、har one,char two,char three)/* 定义hanoi函数，将n个盘从 one座借助two座，移到three座*/static k=1;void move(char x,char y);峰有声明 在此需要提前声明才能使用if(n=1)到第三个上 printf(第 步:,k+);move(one,three); else hanoi(n-1,one,three,two);三个座当桥梁printf(第 步:,k+);move(one,three);hanoi(n-1,two,one,three);个盘上，第一个盘当桥梁/定义静态变量k用来标明走了多少步因为move函数定义在该

30、函数的后边且之前/当第一个座上仅剩一个盘的时候将此盘移/输出是第多少步/移动/将前n-1个盘从第一个座移到二个座上，第/将上边转移到第二个座上的盘转移到第三天天快乐void move(char x,char y) /*定义 move函数 */printf(%c-%cn,x,y);input the number of diskes:4The step to moveing 4 diskes：第1步:第2步:第3步:B乂第4岁;A-圮第5步:CA第6步:C 一圮斯步:AB第建:AC第9步:BC第 10 步:BA11:CAC第 13步:ABCPress any key to continue四、实

31、验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验四 队列的实现和应用天天快乐一、实验目的1、掌握队列的建立方法；2、掌握队列的基本操作，如出队、入队、判断队空等;3、队列的应用。二、实验内容1、顺序队列的初始化2、判断队列是否为空3、顺序队列出队4、顺序队列入队5、队列的应用-回文判断二、实验提不1、队列的基本操作，按提示将函数补充完整#include #include #define STACK_MAX 100 typedef structint front, rear;int data1STACK_MAX; Queue;void initQueue (Queue *q

32、) /*q-front=q-rear=0;int EmptyQueue(Queue *q)/*初始化队列*/判断队列空*/if(q-front=q-rear) return 1;else/1代表空return 0;/0代表非空int DeQueue(Queue *q) /* 出队列*/判断需要出队时队列是否为空if(q-rear=q-front)printf(当前队列已经空了。);exit(0);else天天快乐/将队头原素出列然后队头指针加一return q-data1q-front+;void InQueue(Queue *q,int data) /*if(q-rear=STACK_MAX

33、)printf(当前队列空间已满。exit(0); elseq-data1q-rear=data; q-rear+;int main()Queue q;入队列*/判断需要入队时队列是否已满);/入队initQueue(&q);InQueue(&q,1);InQueue(&q,2);InQueue(&q,3);printf(%dn,DeQueue(&q);printf(%dn,DeQueue(&q);printf(%dn,DeQueue(&q);ress any key to continue2、判断给定的字符序列是否是回文(提示：将一半字符入栈)#include #include #defin

34、e STACK_MAX 100typedef structint top;int dataSTACK_MAX; stack;typedef struct int front, rear;int data1STACK_MAX; Queue;void init(stack *st) /*st-top=0;int Empty(stack *st)/*if(st-top=0)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)printf( 栈已空！);exit(0); else st-datast-top+=data;void initQueue (Queue *q) /*初始化队列 */q-front=q-rear=0;int EmptyQueue(Queue *q)/* 判断队列空 */if(q-front=q-rear)return 1;elsereturn 0;int DeQueue(Queue *q) /*出队列*/return (int)q-

36、data1q-front+;void InQueue(Queue *q,int data) /* 入队列*/q-data1q-rear+=data;int IsHuiWen(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)zhan=k/2;dui=k/2+1;if(k%2=1)zhan=k/2;dui=k/2+2;for(i=0;izhan;i+)push(st,ai);for(i=zhan;

37、ik;i+)InQueue(q,ai);for(i=0;ik/2;i+)if(pop(st)!=DeQueue(q) return 0;return 1;int main()char a10=a,b,c,d,b,a;stack st;Queue q;init(&st);initQueue(&q);printf(%dn,IsHuiWen(&st,&q,a); 0Press any key to continue四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。天天快乐天天快乐实验五二叉树的遍历及应用一、实验目的.掌握二叉树的定义；.掌握二叉树的基本操作，如二叉树的建立、遍历

38、、结点个数统计、树的深度计算等。 二、实验内容用递归的方法 实现以下算法：.以二叉链表表示二叉树，建立一棵二叉树；.输出二叉树的中序遍历结果；.输出二叉树的前序遍历结果；.输出二叉树的后序遍历结果；.计算二叉树的深度；.统计二叉树的结点个数；7、二叉树的层序遍历结果。二、实验提不1、/按要求将程序补充完整#include #include #include #define NULL 0typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;二叉树的建立BiTree Create(BiTree

39、T)char ch;设置一个接收数据的变量scanf(%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)printf(%c ,T-data);Preorder(T-lchild);Preorder(T-rchild);统计二叉树的结点个数int Sumleaf(

40、BiTree T)int n;if(T=NULL) return 0;elsen=1+Sumleaf(T-lchild)+Sumleaf(T-rchild);return n;二叉树的中序递归遍历void zhongxu(BiTree T)if(T)Preorder(T-lchild);printf(%c ,T-data);Preorder(T-rchild);二叉树的后序递归遍历void houxu(BiTree T)if(T)Preorder(T-lchild);Preorder(T-rchild); printf(%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-