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

数据结构与算法实验报告綦娜娜 编哈尔滨理工大学荣成学院实验一 顺序表的实现和应用一、实验目的 1、掌握顺序表的定义； 2、掌握顺序表的基本操作，如查找、插入、删除及排序等。二、实验内容1、编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度2、编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度3、编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度4、编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法，并分析算法的时间复杂度三、实验提示1、#include <stdio.h>#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度 */int locate(list *l,int x)/代码int i;for(i=0;i<l->last;i+)if(l->datai=x)return i+1;return -1;main()list b;int x,i,p;b.last=10;for(i=0;i<b.last;i+)b.datai=i+2;printf("请输入x的值：");scanf("%d",&x);p=locate(&b,x);if(p=-1)printf("no!");elseprintf("position=%dn",p);时间复杂度T(n)=O(n);2、#include <stdio.h>#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度 */int delete(list *l,int i)int j,k,p; /定义一个用来保存被删原素；if(i>=0&&i<l->last)/只接受有效输入for(j=0;j<l->last;j+) /遍历数组if(j=i-1)/匹配p=l->dataj;/保存被删原素;for(k=j;k<l->last;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;i<b.last;i+)b.datai=i+2;printf("请输入x的值：");scanf("%d",&x);if(delete(&b,x)!=0)for(i=0;i<b.last;i+)printf("%3d",b.datai);elseprintf("Error!");/时间复杂度T(n)=O(n);3、#include <stdio.h>#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度 */int insert(list *l,int x,int i)int j,k;if(i<=l->last+1&&i>0)if(i=l->last+1)/特殊值last+1 要插入到整个数组之后l->datal->last=x;elsefor(j=0;j<l->last;j+)if(j=i-1)/匹配for(k=l->last;k>j;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;i<b.last;i+)b.datai=i+2;printf("请输入x的值：");scanf("%d",&x);if(insert(&b,66,x)!=0)for(i=0;i<b.last;i+)printf("%3d",b.datai);elseprintf("Error!");/时间复杂度T(n)=O(n);4、#include <stdio.h>#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法，并分析算法的时间复杂度 */void fun(list *l)/这个代码有点晦涩，但空间时间复杂度是鸡儿低int i,ou=0,temp;/i计数，ou代表偶数个数for(i=0;i<l->last;i+)/循环if(l->datai%2=0)/判断是不是偶数，如果是偶数的话和当前第ou个位置的原素交换位置temp=l->dataou;l->dataou=l->datai;l->datai=temp;ou+=1;/偶数个数加一printf("当前数组中偶数有%d个,奇数有%d个:n",ou,l->last-ou);main()list b;int i=0,m=0;b.last=10;printf("请输入数组元素的值：n");for(i=0;i<b.last;i+)printf("b.data%d=",i);scanf("%d",&b.datai);fun(&b);for(i=0;i<b.last;i+)printf("%3d",b.datai);/时间复杂度为T(n)=O(n);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验二 链表的实现和应用一、实验目的 1、掌握链表的定义； 2、掌握链表的基本操作，如查找、插入、删除、排序等。二、实验内容1、单链表的创建2、单链表的查找3、单链表的排序4、单链表的删除5、链表的应用-约瑟夫环问题三、实验提示1、/创建单链表,要求：结点个数为n个，每个节点数据域的值必须小于m。编辑主函数验证之。#include <stdio.h>#include <stdlib.h>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("请输入%d个小鱼%d的数，中间用空格隔开:n",n,m);for(i=0;i<n;i+)/头插法p=(NODE*)malloc(sizeof(NODE);scanf("%d",&p->data);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=Creatlink(8,22); outlink(head);2、/查找值为ch的节点在链表中是否出现，如果存在，返回在链表中位序，如果不存在返回0#include <stdio.h>#include <stdlib.h>#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;i<N;i+)if(p->data=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 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(sizeof(SLIST);/创建并初始化头结点tou->data=N;tou->next=NULL;for(i=0;i<N;i+)/前叉法p=(SLIST*)malloc(sizeof(SLIST);p->data=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的功能是，删除链表中数据域值相同的节点，使之只保留一个#include <stdio.h>#include <stdlib.h>#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->next;SLIST *creatlist(int *a) SLIST *h,*p,*q; int i; h=p=(SLIST *)malloc(sizeof(SLIST); for(i=0; i<N; i+) q=(SLIST *)malloc(sizeof(SLIST); q->data=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=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 <stdio.h>#include <stdlib.h>#define N 8typedef 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->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); for(i=0; i<N; i+) q=(SLIST *)malloc(sizeof(SLIST); q->data=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); 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); 5、实现约瑟夫环函数（选做）#include <stdio.h>#include <stdlib.h>typedef struct list int data; struct list *next; SLIST;SLIST *creatlist(int m) int i;SLIST *tou,*p,*wei; /头指针 生成节点指针 尾指针tou=(SLIST*)malloc(sizeof(SLIST);/头节点wei=tou;printf("请输入%d个数用空格隔开：n",m);for(i=0;i<m;i+)/尾插法p=(SLIST*)malloc(sizeof(SLIST);scanf("%d",&p->data);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(i=1;i<c-1;i+)/根据输入的c剔除节点p=p->next;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、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验三 栈的实现和应用一、实验目的 1、掌握栈的建立方法； 2、掌握栈的基本操作，如入栈、出栈、判断空栈等； 3、栈的应用。二、实验内容1、顺序栈的初始化2、判断栈是否为空3、顺序栈出栈4、顺序栈入栈5、栈的应用-汉诺塔三、实验提示1、栈的基本操作，按提示将函数补充完整#include <stdio.h>#include <stdlib.h>#define STACK_MAX 100typedef struct int top; int dataSTACK_MAX; stack;void init(stack *st) /*初始化顺序栈*/st->top=0;int Empty(stack *st)/*判断栈是否为空*/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 <stdio.h>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,char one,char two,char three) /* 定义hanoi函数,将个盘从one座借助two座，移到three座 */ static k=1;/定义静态变量k用来标明走了多少步void move(char x,char y);/因为move函数定义在该函数的后边且之前咩有声明 在此需要提前声明才能使用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("%c->%cn",x,y); 四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验四 队列的实现和应用一、实验目的 1、掌握队列的建立方法； 2、掌握队列的基本操作，如出队、入队、判断队空等； 3、队列的应用。二、实验内容1、顺序队列的初始化2、判断队列是否为空3、顺序队列出队4、顺序队列入队5、队列的应用-回文判断 三、实验提示1、/队列的基本操作，按提示将函数补充完整#include <stdio.h>#include <stdlib.h>#define STACK_MAX 100typedef struct int front, rear; int data1STACK_MAX; Queue;void initQueue (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) /*入队列*/if(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 <stdio.h>#include <stdlib.h>#define STACK_MAX 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->top;return （int）c;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+;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;i<zhan;i+)push(st,ai);for(i=zhan;i<k;i+)InQueue(q,ai);for(i=0;i<k/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以二叉链表表示二叉树，建立一棵二叉树；2输出二叉树的中序遍历结果；3输出二叉树的前序遍历结果；4输出二叉树的后序遍历结果；5计算二叉树的深度；6统计二叉树的结点个数；7、二叉树的层序遍历结果。 三、实验提示1、/按要求将程序补充完整#include <stdio.h> #include <string.h>#include <stdlib.h>#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='#')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);