东北大学秦皇岛分校数据结构实验报告.doc

数据结构实验报告（数据结构）班级学号学生姓名提交日期2014年12月9日成 绩 ：计算机与通信工程学院2013实验一 线性表的应用【实验目的】：1、掌握线性表的逻辑结构定义2、掌握线性表的两种存储结构（顺序和链式）3、掌握顺序表和链表的定义及基本操作【实验内容】通过编程完成具有一定实际意义的课题，加深对线性表应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：字母链表n 功能要求：生成26个字母的线性表，并实现对特定字母的插入和删除。n 程序说明：使用顺序表或者链表生成字母有序表，并应用相应数据结构实现对单个字母的插入和删除操作。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。源程序如下：#include<stdio.h>#include<malloc.h>typedef struct listchar data;struct list*link;test;test *p,*q,*r,*head,*d;int L;int m=sizeof(test);void build();void display();int insert_char(char,char);int delet_char(char);void build()int i;head=(test*)malloc(m);p=head;for(i=1;i<L;i+)p->data=i+'a'-1;p->link=(test*)malloc(m);p=p->link;p->data=i+'a'-1;p->link=NULL;void display(int l)d=head;while(d->link!=NULL)printf("%c->",d->data);d=d->link;printf("%cn",d->data);printf("the list length is:%dn",l);int insert_char(char X,char Y)p=head;r=(test*)malloc(m);r->data=X;if (Y<'a') Y=Y+32;if(head->data=Y)head=r;r->link=p;elsewhile(p->data!=Y)&&(p->link!=NULL) q=p;p=p->link;if(p->data=Y)q->link=r;r->link=p;elsep->link=r,r->link=NULL;L+;return L;int delet_char(char X)p=head;if (X<'a') X=X+32;if(head->data=X)head=head->link;free(p);elsewhile(p->data!=X)&&(p->link!=NULL)q=p;p=p->link;if(p->data=X)q->link=p->link;free(p);else return(-1);L-;return L;int main(void)int m,x,y,z,l;L=26;build();display(L);printf("n请选择：1.插入字母 2.删除字母n");m=getchar();fflush(stdin);/清除键盘缓冲区switch(m)case '1':printf("you will insert the char X before char Y:n");scanf("%c,%c",&x,&y);display(insert_char(x,y);break;case '2':printf("you will Delete the char X:n");scanf("%c",&z);l=delet_char(z);display(l);break;default:printf("ERROR,please input your choice of: 1 or 2n");break;2、实验题目：链表的创建n 功能要求：使用简单数据类型，利用指针创建一个基本链表。n 程序说明：使用指针，通过在头结点之后插入新节点的操作，逐步生成基本链表。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。源程序如下：#include "stdlib.h"#include "stdio.h"#include<malloc.h>struct listint data;struct list*next;typedef struct list node;typedef node *link;int main()link ptr,head;int num,i;head=(link)malloc(sizeof(node);ptr=head;printf("please input 5 numbers=>n");for(i=0;i<=4;i+)scanf("%d",&num);ptr->data=num;ptr->next=(link)malloc(sizeof(node);if(i=4)ptr->next=NULL;else ptr=ptr->next;ptr=head;while(ptr!=NULL)printf("The value is =>%dn",ptr->data);ptr=ptr->next;3、 实验题目：链表的逆序输出n 功能要求：使用简单数据类型，利用指针创建一个基本链表。n 程序说明：使用指针，通过在尾结点之前插入新节点的操作，逐步逆序生成基本链表，之后，利用头结点实现顺序输出，以达到链表逆序的功能。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。#include <stdlib.h>#include <stdio.h>struct list int data; struct list*next;typedef struct list node ;typedef node *link;int main()link ptr,head,tail; int N,num,i,L=0; tail=(link)malloc(sizeof(node); tail->next=NULL; ptr=tail; printf("nplease input the num of the data=>n"); scanf("%d",&N); printf("nplease input %d data=>n",N); for(i=0;i<N;i+) scanf("%d",&num); ptr->data=num; head=(link)malloc(sizeof(node); head->next=ptr; ptr=head; ptr=ptr->next; /*从尾结点向前插入生成链表*/while(ptr!=NULL)printf("The value is=>%dn",ptr->data); /*结点输出*/ ptr=ptr->next;L+;/*计算链表结点个数*/printf("The langth of the link is=>%dn",L);4、 连接两个链表n 功能要求：使用简单数据类型，利用指针创建一个基本链表。n 程序说明：使用指针，首先使用程序一生成两个基本链表，之后使用两个链表的头尾指针相连，从而实现两个链表的连接。其中，结构体或类的使用，可参考教材、辅导教材或其它应用实例。源程序如下：#include <stdlib.h>#include <stdio.h>struct listint data;struct list*next;typedef struct list node;typedef node *link;link create_list(int array,int num)link tmp1,tmp2,pointer;int i;pointer=(link)malloc(sizeof(node);pointer->data=array0;tmp1=pointer;for(i=0;i<num;i+)tmp2=(link)malloc(sizeof(node);tmp2->next=NULL;tmp2->data=arrayi;tmp1->next=tmp2;tmp1=tmp1->next;return pointer;int display(link ptr)while(ptr!=NULL)printf("%d->",ptr->data);ptr=ptr->next;printf("n");link concatenate(link pointer1,link pointer2)link tmp;tmp=pointer1;while(tmp->next)tmp=tmp->next;tmp->next=pointer2;return pointer1;void main(void)int arr1=3,12,8,9,11; int arr2=55,39,17,21,76; link ptr,ptr1,ptr2,ptr3;ptr1=create_list(arr1,5);display(ptr1);ptr2=create_list(arr2,5);display(ptr2);ptr3=concatenate(ptr1,ptr2);display(ptr3);实验二 栈与队列的应用【实验目的】：1、 掌握栈和队列的结构定义和特性2、 掌握栈和队列的基本操作以及栈和队列在程序设计中的应用。【实验内容】通过编程完成具有一定实际意义的课题，加深对栈与队列应用的理解和掌握。参考题目如下所示。学生可在完成以下题目之后经指导教师同意自行设计其它选题并将选题源程序与执行结果提交指导教师审阅。1、实验题目：利用栈实现数制转换n 功能要求：使用栈完成十进制数到各种不同进制数的数制转换。n 程序说明：利用堆栈工作原理实现对任意十进制数的数值转换操作。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10/定义栈中的常量typedef int Status;/指定栈操作的返回值类型typedef int SElemType;/定义栈元素的数据类型struct STACKSElemType *base;SElemType *top;int stacksize;typedef struct STACK SqStack;typedef struct STACK *pSqStack;/栈结构的定义Status InitStack(SqStack &S);Status StackEmpty(SqStack S);Status Push(SqStack &S,SElemType e);Status Pop(SqStack &S,SElemType &e);/栈的基本操作函数声明#include <stdlib.h>#include <stdio.h>int e;SqStack S;/全局变量定义void conversion(int n,int f); /数制转换函数声明;int main()int N,F;printf("请输入待转换数制:n");scanf("%d",&F);printf("Input a number to convert to %d:n",F);scanf("%d",&N);conversion(N,F);getchar();printf("nn");return 0;/主程序Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;elsereturn FALSE;/StackEmpty();Status InitStack(SqStack &S)/*S=(pSqStack)malloc(sizeof(SqStack);S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/initStack();Status Push(SqStack &S,SElemType e)if(S.top - S.base>=S.stacksize) if(!S.base)exit(OVERFLOW);S.base=(SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top+)=e;return OK;/ Push();Status Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR;/*e=*(-(S.top);-S.top;e=*S.top;return OK;/Pop();void conversion(int n,int f)InitStack(S);if (n<0)printf("nThe number must be over 0->");return;if(!n) Push(S,0);while(n)Push(S,n%f);n=n/f;printf("the result is: ");while(!StackEmpty(S)Pop(S,e);printf("%d",e);2、实验题目：简单四则运算程序n 功能要求：使用堆栈数据结构，完成10以内的四则运算。n 程序说明：按照操作符的优先级，使用堆栈数据结构，由左至右读入字符并判定计算步骤完成操作，并生成结果输出。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。#include<stdio.h>#include<malloc.h>#include<string.h>#include "stack.h"#define OVERFLOW -1#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;typedef int Status;struct STACKSElemType *base;SElemType *top;int stacksize;typedef struct STACK SqStack;typedef struct STACK *pSqStack;/*堆栈的基本数据定义*/Status InitStack(SqStack *S);Status DestroyStack(SqStack *S);SElemType GetTop(SqStack S);Status Push(SqStack *S,SElemType *e);Status Pop(SqStack *S,SElemType *e);Status StackTraverse(SqStack S,Status(*visit)(SElemType *e);/*堆栈基本操作的函数声明*/Status InitStack(SqStack *S)(*S)=(SqStack*)malloc(sizeof(SqStack);(*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!(*S)->base)exit(OVERFLOW);(*S)->top=(*S)->base;(*S)->stacksize=STACK_INIT_SIZE;return OK;/*堆栈的初始化*/Status DestroyStack(SqStack *S)free(S->base);free(S);return OK;/*堆栈的销毁操作*/SElemType GetTop(SqStack S)if(S.top=S.base) return ERROR;return *(S.top-1);/*取得栈顶元素*/Status Push(SqStack *S,SElemType e)if(S->top - S->base>=S->stacksize)S->base=(SElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(SElemType);if(!S->base)exit(OVERFLOW);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;*(S->top+)=e;return OK;/*将数据压栈*/Status Pop(SqStack *S,SElemType *e)if(S->top=S->base)return ERROR;*e=*(-(S->top);return OK;/*数据从堆栈弹出*/Status StackTraverse(SqStack S,Status (*visit)(SElemType *e)while (S.top>S.base)visit(-S.top);return OK;/*堆栈的遍历*/char OP10='+','-','*','/','(',')','#'int precede77=1,1,2,2,2,1,1,1,1,2,2,2,1,1,1,1,1,1,2,1,1,1,1,1,1,2,1,1,2,2,2,2,2,3,0,1,1,1,1,0,1,1,2,2,2,2,2,0,3;/*对数据操作符数组OP及优先权矩阵的定义*/int In(char c,char *op)int i=0;while(i<7)if(c=opi+)return 1;return 0;/*判断输入字符是否为操作符，否则将其认为是数字*/char Precede(char op,char c)int pos_op;int pos_c;int i;for (i=0;i<7;i+)if(op=OPi) pos_op=i;if(c=OPi) pos_c=i;switch(precedepos_oppos_c)case 1: return '>'case 2: return '<'case 3: return '='return OK;/*对判定为操作符的字符根据优先权矩阵判断其优先顺序*/char Operate(int a,char theta,int b)switch(theta)case '+': return a+b-'0'case '-': return a-b+'0'case '*': return (a-'0')*(b-'0')+'0'case '/': return (a-'0')/(b-'0')+'0'return OK;/*对表达式进行计算，返回计算结果*/char EvaluateExpression()SqStack *OPND,*OPTR;char c,x,theta;char a,b;InitStack(&OPTR); Push(OPTR,'#');InitStack(&OPND);c=getchar();while(c!='#'|GetTop(*OPTR)!='#')if(!In(c,OP)Push(OPND,c);c=getchar();/*使用OPND栈存放数字*/elseswitch (Precede(GetTop(*OPTR),c)case '<':Push(OPTR,c); /*使用OPTR栈存放操作符*/c=getchar();break;case '=':Pop(OPTR,&x);c=getchar();break;case '>':Pop(OPTR,&theta);Pop(OPND,&b);Pop(OPND,&a);Push(OPND,Operate(a,theta,b);break;/*使用栈操作进行表达式的计算*/c=GetTop(*OPND); /*取得 OPND栈顶元素为最终结果*/DestroyStack(OPTR);DestroyStack(OPND);return c;int main()char i;printf("nnn表达式只能连续输入0.9单个数字及+-*/四个运算符,以#结束:n");i=EvaluateExpression();printf("nThis expression's result is: ");printf("%dnnnn",i-'0');3、 实验题目：表达式括号匹配程序n 功能要求：使用堆栈，对整行输入的表达式进行括号匹配操作，并判定匹配与否将结果输出。n 程序说明：使用堆栈与字符比较，判定表达式括号是否匹配。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。#include<stdio.h>#include<malloc.h>#include "stack.h"#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef int Status;struct STACKSElemType *base;SElemType *top;int stacksize;typedef struct STACK SqStack;typedef struct STACK *pSqStack;/*堆栈的基本数据定义*/Status InitStack(SqStack *S);Status StackEmpty(SqStack S);Status Push(SqStack *S,SElemType *e);Status Pop(SqStack *S,SElemType *e);/*堆栈基本操作的函数声明*/Status InitStack(SqStack *S)(*S)=(SqStack*)malloc(sizeof(SqStack);(*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!(*S)->base)exit(OVERFLOW);(*S)->top=(*S)->base;(*S)->stacksize=STACK_INIT_SIZE;return OK;/*堆栈的初始化*/Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;elsereturn FALSE;/*判断堆栈是否为空栈*/Status Push(SqStack *S,SElemType e)if(S->top - S->base>=S->stacksize)S->base=(SElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(SElemType);if(!S->base)exit(OVERFLOW);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;*(S->top+)=e;return OK;/*将数据压栈*/Status Pop(SqStack *S,SElemType *e)if(S->top=S->base)return ERROR;*e=*(-(S->top);return OK;/*数据从堆栈弹出*/Status AllBrackets_Test(SqStack *S,char *str)InitStack(&S); char *p;int c;for(p=str;*p!='#'p+)if(*p='('|*p=''|*p='')Push(S,*p);else if(*p=')'|*p=''|*p='')if(StackEmpty(*S) return ERROR;Pop(S,&c);if(*p=')'&&c!='(')return ERROR;if(*p=''&&c!='')return ERROR;if(*p=''&&c!='')return ERROR;/end forif(!StackEmpty(*S)return ERROR;int main()SqStack S;char str50,c; char *s=str;int i=0;printf("请输入算术表达式，以'#'为结束：n");while(c!='#')scanf("%c",&c);stri=c;i+;int tag=AllBrackets_Test(&S,s);if(tag)printf("nRight!n");elseprintf("nWrong!n");4、 堆栈与队列的遍历操作（可选）n 功能要求：使用简单数据类型，利用指针分别创建一个基本栈和一个基本队列，并使用指针将堆栈与队列元素按顺序输出。n 程序说明：使用指针，首先两个基本数据结构，之后分别使用两个不同数据结构的指针实现对各自元素的输出。其中，实现堆栈功能的各个库函数由自行建立的头文件“stack.h”提供，“stack.h”可参考授课教材相关章节，结构体或类的使用，可参考教材、辅导教材或其它应用实例。#include<stdio.h>#include"stack.h"#include"queue.h"#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;typedef char QElemType;typedef int Status;struct STACKSElemType *base;SElemType *top;int stacksize;typedef struct STACK SqStack;typedef struct STACK *pSqStack;typedef int Status;typedef struct QNodeQElemTypedata;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;/*堆栈的基本数据定义*/Status InitStack(SqStack *S);Status InitQueue(LinkQueue &Q);Status Push(SqStack *S,SElemType *e);Status EnQueue(LinkQueue &Q,QElemType e);Status QueueTraverse(LinkQueue Q,Status(*visit)();Status StackTraverse(SqStack S,Status(*visit)(SElemType *e);/*堆栈基本操作的函数声明*/Status InitStack(SqStack *S)(*S)=(SqStack*)malloc(sizeof(SqStack);(*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!(*S)->base)exit(OVERFLOW);(*S)->top=(*S)->base;(*S)->stacksize=STACK_INIT_SIZE;return OK;/*堆栈的初始化*/Status Push(SqStack *S,SElemType e)if(S->top - S->base>=S->stacksize)S->base=(SEl