数据的结构及算法实验的指导书.doc

《数据的结构及算法实验的指导书.doc》由会员分享，可在线阅读，更多相关《数据的结构及算法实验的指导书.doc（31页珍藏版）》请在课桌文档上搜索。

1、实验一 顺序表的实现和应用一、实验目的 1、掌握顺序表的定义； 2、掌握顺序表的根本操作，如查找、插入、删除与排序等。二、实验内容1、编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度2、编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度3、编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度4、编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法，并分析算法的时间复杂度三、实验提示1、#include #define MAXS

2、IZE 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;ib.last;i+)b.datai=i+2;printf(请输入x的值：);scanf(%d,&x);p=locate(&b,

3、x);if(p=-1)printf(no!);elseprintf(position=%dn,p);时间复杂度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-d

4、ataj;/保存被删原素;for(k=j;klast;k+)/前进一位；l-datak=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!);/时间复杂度T(n)=O(n);3、

5、#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;elsefor(j=0;jlast;j+)if(j=i-1)/匹配for(k=l-last;kj;k-)/将所选插入位置之后原素后移l-data

6、k=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+)printf(%3d,b.datai);elseprintf(Error!);/时间复杂度T(n)=O(n);4、#include #define MAXSIZE 2

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

8、组中偶数有%d个,奇数有%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(%d,&b.datai);fun(&b);for(i=0;ib.last;i+)printf(%3d,b.datai);/时间复杂度为T(n)=O(n);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进展总结。实验二 链表的实现和应用一、实验目的 1、掌握链表的定义； 2、掌握链表的根本操作，如查找、插入、删除、排序等

9、。二、实验内容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=NULL;tou-data=n;printf(

10、请输入%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-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);main() NODE *head; head=Cre

11、atlink(8,22); outlink(head);2、/查找值为ch的节点在链表中是否出现，如果存在，返回在链表中位序，如果不存在返回0#include #include #define N 8typedef struct list int 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;r

12、eturn 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 letter:); 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(si

13、zeof(SLIST);/创建并初始化头结点tou-data=N;tou-next=NULL;for(i=0;idata=ai;p-next=tou-next;tou-next=p;return tou;void outlist(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); 3、/去偶操作,链表中各节点按数据域递增有序，函数fun的功

14、能是，删除链表中数据域值一样的节点，使之只保存一个#include #include #define N 8typedef struct list int data; struct list *next; SLIST;void fun( SLIST *h)SLIST *p,*shanchu;/用于遍历的指针p,用于删除的指针shanchup=h-next;/p为寿元节点while(p-next!=NULL)/终止条件if(p-data=p-next-data)/判断是否有重复原素shanchu=p-next;p-next=shanchu-next;free(shanchu);elsep=p-n

15、ext;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 printf(-%d,p-data); p=p-next; while(p!=NULL); printf(

16、-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);4、/在main函数中屡次调用fun函数，每调用一次fun函数，输出链表尾部节点中的数据，并释放该节点，使得链表缩短。#include #include #define N 8typedef struct list int d

17、ata; 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-data);/输出shanchu=bianli-next;/释放free(shanchu);bianli-next=NULL;SLIST *creatlist(int *a) SLIST *h,*p,*q; int i; h=p=(SLIST *)malloc(sizeof(SLIST

18、); 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 printf(-%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); print

19、f(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); 5、实现约瑟夫环函数选做#include #include typedef struct list int data; struct list *next; SLIST;SLIST *creatlist(int m) int i;SLIST *tou,*p,*w

20、ei; /头指针 生成节点指针 尾指针tou=(SLIST*)malloc(sizeof(SLIST);/头节点wei=tou;printf(请输入%d个数用空格隔开：n,m);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，用于删除的指针shanchup=h-next;/p指向首元结点while(p!=p-next)/当环中只剩下一个原素时完毕for(

21、i=1;inext;shanchu=p-next;/shanchu指向当前要剔除的节点printf(%d ,shanchu-data);p-next=shanchu-next;/将shanchu指针指向的节点出环free(shanchu);p=p-next;printf(%d,p-data);/输出最后的一个节点的内容free(p);free(h);main( ) SLIST *head; int m,c; printf(请分别输入m和c的值：);scanf(%d,%d,&m,&c); head=creatlist(m); outlist(head,m,c);四、实验报告要求1、撰写实验报告；

22、2、对实验中出现的问题和结果进展总结。实验三 栈的实现和应用一、实验目的 1、掌握栈的建立方法； 2、掌握栈的根本操作，如入栈、出栈、判断空栈等； 3、栈的应用。二、实验内容1、顺序栈的初始化2、判断栈是否为空3、顺序栈出栈4、顺序栈入栈5、栈的应用-汉诺塔三、实验提示1、栈的根本操作，按提示将函数补充完整#include #include #define STACK_MAX 100typedef struct int top; int dataSTACK_MAX; stack;void init(stack *st) /*初始化顺序栈*/st-top=0;int Empty(stack *s

23、t)/*判断栈是否为空*/if(st-top=0)return 0;/空0else return 1;/非空1int pop(stack *st) /*出栈*/return st-data-st-top;void push(stack *st,int data) /*入栈*/st-datast-top+=data;int main(void) stack st; init(&st); push(&st,5); push(&st,6); printf(%d,pop(&st); return 0;2、#include void main()void hanoi(int n,char one,cha

24、r 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,char one,char two,char three) /* 定义hanoi函数,将个盘从one座借助two座，移到three座 */ static k=1;/定义静态变量k用来标明走了多少步void move(char x,char y);/因为mov

25、e函数定义在该函数的后边且之前咩有声明 在此需要提前声明才能使用if(n=1)/当第一个座上仅剩一个盘的时候将此盘移到第三个上printf(第%d步:,k+);/输出是第多少步move(one,three);/移动elsehanoi(n-1,one,three,two);/将前n-1个盘从第一个座移到二个座上，第三个座当桥梁printf(第%d步:,k+);move(one,three);hanoi(n-1,two,one,three);/将上边转移到第二个座上的盘转移到第三个盘上，第一个盘当桥梁 void move(char x,char y) /* 定义move函数 */ printf(%

26、c-%cn,x,y); 四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进展总结。实验四 队列的实现和应用一、实验目的 1、掌握队列的建立方法； 2、掌握队列的根本操作，如出队、入队、判断队空等； 3、队列的应用。二、实验内容1、顺序队列的初始化2、判断队列是否为空3、顺序队列出队4、顺序队列入队5、队列的应用-回文判断 三、实验提示1、/队列的根本操作，按提示将函数补充完整#include #include #define STACK_MAX 100typedef struct int front, rear; int data1STACK_MAX; Queue;void in

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

28、f(q-rear=STACK_MAX)/判断需要入队时队列是否已满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);2、/判断给定的字符序列是否是回文提示：将一半字符入栈#include #include #define STACK_M

29、AX 100typedef struct int 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;else return 0;int pop(stack *st) /*出栈*/if(st-top=0)printf(栈已空!);exit(0);elsechar c;c=st-data-st-to

30、p;return intc;void push(stack *st,int data) /*入栈*/if(st-top=STACK_MAX-1)printf(栈已空！);exit(0);elsest-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-data1q-front+;v

31、oid 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;ik;i+)InQueue(q,a

32、i);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);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进展总结。实验五 二叉树的遍历与应用一、实验目的1掌握二叉树的定义；2掌握二叉树的根本操作，如二叉树的建立、遍历、结点个数统计、树的深度计算等。二、实验内容用递归的方法实现以下算法：1以二叉链表表示二叉树，建立

33、一棵二叉树；2输出二叉树的中序遍历结果；3输出二叉树的前序遍历结果；4输出二叉树的后序遍历结果；5计算二叉树的深度；6统计二叉树的结点个数；7、二叉树的层序遍历结果。 三、实验提示1、/按要求将程序补充完整#include #include #include #define NULL 0 typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; /二叉树的建立BiTree Create(BiTree T) char ch;/设置一个接收数据的变量 scanf(%c,&ch); if(ch

34、=#)T=NULL;/设置完毕符 else T = (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(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