数据结构实验报告

浙江师范大学

实 验 报 告

学 院： 数理与信息工程学院 专 业： 计算机科学与技术 姓 名： 杨富生 学 号： 201531910137 课程名称： 数据结构 指导教师： 钟发荣 实验时间： 2016-06-15

2016年6月15日

实验一

1. 实验要求

1.1 掌握数据结构中线性表的基本概念。

1.2 熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度

及合并并运算在顺序存储结构上的实验。

2. 实验内容

2.1 编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所

有元素，要求以较高效率来实现。

#include typedef int elemtype; #define maxsize 10

int del(int A[],int n,elemtype x,elemtype y) {

int i=0,k=0; while(i

{if(A[i]>=x&&A[i]<=y) k++; else A[i-k]=A[i]; i++; }

return(n-k); }

void main() {

int i,j;

int a[maxsize];

printf(\输入%d个数:\\n\ for(i=0;i

printf(\输出删除后剩下的数:\\n\ for(i=0;i

printf(\ \}

2.2 试写一个算法，在无头结点的动态单链表上实现线性表插入操作

INSERT(L,i,b)。

void Insert(Linklist &L,int i,elemtype x) {

if(!L) {

2

}

L=(Linklist)malloc(sizeof(Lnode)); (*L).data=x;(*L).next=NULL; } else { if(i==1) { s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=L;L=s; } else { p=L;j=1; while(p&&jnext;} if(p||j>i-1) return error; s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=p->next;p->next=s; } }

2.3 生成两个多项式PA和PB，求他们的和，输出“和多项式”。 typedef struct node {int exp; float coef;

struct node *next; }polynode;

polynode *polyadd(polynode *pa,polynode *pb) {

polynode *p,*q,*pre,*r; float x;

p=pa->next; q=pb->next; pre=pa;

while((p!=NULL)&&(q!=NULL)) if(p->exp>q->exp) { r=q->next; q->next=p; pre->next=q; pre=q; q=r; }

3

}

else if(p->exp==q->exp) { x=p->coef+q->coef; if(x!=0) {p->coef=x; s=p; } else {pre->next=p->next; free(p); } p=pre->next; r=p; q=q->next; free(r); } else if(p->expexp) { pre=p; p=p->next; } if(q!=NULL) pre->next=q; free(pb);

2.4 设计一个统计选票的算法，输出每个候选人的得票结果。

typedef int elemtype typedef struct linknode {

elemtype data;

struct linknode *next; }nodetype;

nodetype *create() {

elemtype d;

nodetype h=NULL,*s,*t; int i=1;

printf(\建立单链表:\\n\ while(1) { printf(\输入第%d个结点数据域\ scanf(\

4

if(d==0)break; if(i==1) { h=(nodetype *)malloc(sizeof(nodetype)); h->data=d;h->next=NULL;t=h; } else { s=(nodetype *)malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s; } i++; }

return h; }

void sat(nodetype *h,int a[]) {

nodetype *p=h; while(p!=NULL) { a[p->data]++; p=p->next; } }

void main() {

int a[N+1],i; for(i=0;i

nodetype *head; head=create(); sat(head,a);

printf(\候选人:\

for(i=1;i<=N;i++) printf(\ printf(\得票数\\n\ for(i=1;i<=N;i++) printf(\ printf(\}

3. 实验心得体会

线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。

5

实验二

1. 实验要求

1.1 了解栈和队列的特性，以便灵活运用。 1.2 熟练掌握栈和有关队列的各种操作和应用。

2. 实验内容

2.1 设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。 #include #include #include #define NULL 0 typedef struct list {

char str;

struct list *next; }list;

void push(char,list *); int pop(char.list *); void deal(char *str); main(void) {char str[20];

printf(\请输入一个算式:\\n\gets(str); deal(str);

printf(\正确!\getchar(); return 0; }

void deal(char *str) {list *L;

L=(list *)malloc(sizeof(list)); if(!L) {

printf(\错误!\ exit(-2); }

L->next=NULL; while(*str) {

6

if(*str=='('||*str=='['||*str=='{') push(*str,L); else if(*str==')'||*str==']'||*str=='}') if(pop(*str,L)) {puts(\错误,请检查!\ puts(\按回车键退出\ getchar();exit(-2); } str++; }

if(L->next)

{puts(\错误,请检查!\puts(\按任意键退出\getchar();exit(-2); } }

void push(char c,list *L) {list *p;

p=(list *)malloc(sizeof(list)); if(!p) {

printf(\错误!\ exit(-2); }

p->str=c;

p->next=L->next; L->next=p; }

#define check(s) if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);} int pop(char c,list *L) {

list *p;

if(L->next==NULL)return 1; switch(c) {

case')':check('(') break; case']':check('[') break; case'}':check('{') break; }

return 1;

7

实验三

1. 实验要求

1.1 掌握二叉树，二叉树排序数的概念和存储方法。 1.2 掌握二叉树的遍历算法。

1.3 熟练掌握编写实现树的各种运算的算法。 2. 实验内容

2.1 编写程序，求二叉树的结点数和叶子数。 #include #include struct node{ char data;

struct node *lchild,*rchild; }bnode;

typedef struct node *blink; blink creat() {

blink bt; char ch;

ch=getchar();

if(ch==' ') return(NULL); else { bt=(struct node *)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat(); }

return bt; }

int n=0,n1=0;

void preorder(blink bt) {

if (bt) { n++; if(bt->lchild==NULL&&bt->rchild==NULL) n1++; preorder(bt->lchild); preorder(bt->rchild); } }

void main()

8

{ }

blink root; root=creat(); preorder(root);

printf(\此二叉数的接点数有:%d\\n\printf(\此二叉数的叶子数有:%d\\n\

2.2 编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。 int get_deep(bitree T,int x) {

if(T->data==x) { printf(\ exit 1; } else { if(T->lchild)get_deep(T->lchild,x); if(T->rchild)get_deep(T->rchild,x); }

int get_depth(bitree T) {

if(!T)return 0; else { m=get_depth(T->lchild); n=get_depth(T->rchild); return(m>n?m:n)+1; } }

2.3 编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。 #include #include struct node{ char data;

struct node *lchild,*rchild; }bnode;

typedef struct node *blink; blink creat() {

blink bt; char ch;

ch=getchar();

if(ch==' ') return(NULL);

9

else { bt=(struct node *)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat(); }

return bt; }

void preorder(blink bt) {

if (bt) { printf(\ preorder(bt->lchild); preorder(bt->rchild); } }

void inorder(blink bt) { if(bt) { inorder(bt->lchild); printf(\ inorder(bt->rchild); } }

void postorder(blink bt) { if(bt) { postorder(bt->lchild); postorder(bt->rchild); printf(\ } }

int max(int x,int y) {

if(x>y) return x; else return y; }

int depth(blink bt)

10

本文来源：https://www.bwwdw.com/article/1vtt.html