数据结构实验答案(共65页).doc

精选优质文档-倾情为你奉上重庆文理学院软件工程学院实 验 报 告 册专 业：_软件工程_ _班 级：_软件工程2班_ _学 号：_4 _姓 名：_周贵宇_课程名称：_ 数据结构 _指导教师：_胡章平_ 2013年 06 月 25 日实验序号1实验名称实验一 线性表基本操作实验地点S-C1303实验日期2013年 04月 22日 实验内容1. 编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。2. 编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。3. 编程序实现将单链表的数据逆置，即将原表的数据（a1,a2.an）变成(an,.a2,a1)。（单链表的数据域数据类型为一结构体，包括学生的部分信息：学号，姓名，年龄）实验过程及步骤1. #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList;#include "common.h"#include "seqlist.h"void px(SeqList *A,int j);void main()SeqList *l;int p,q,r;int i;l=(SeqList*)malloc(sizeof(SeqList);printf("请输入线性表的长度:");scanf("%d",&r);l->last = r-1;printf("请输入线性表的各元素值:n");for(i=0; i<=l->last; i+)scanf("%d",&l->elemi); px(l,i);printf("请输入要插入的值:n");scanf("%d",&l->elemi);i+；px(l,i);l->last+;for(i=0; i<=l->last; i+)printf("%d ",l->elemi);printf("n");void px(SeqList *A,int j)int i,temp,k;for(i=0;i<j;i+)for(k=0;k<j-1;k+)if(A->elemi<A->elemk)temp=A->elemi;A->elemi=A->elemk;A->elemk=temp;2. #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList;#include "common.h"#include "seqlist.h"void px(SeqList *A,int j);int DelList(SeqList *L,int i,SeqList *e,int j)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1iL.last+1 */ int k,a,b,c;if(i<1)|(i>L->last+2) printf("删除位置不合法!");return(ERROR);if(j>L->last-i) printf("删除位置不合法!");return(ERROR);for(b=0,a=i-1;a<i+j-1;b+,a+)e->elemb=L->elema; e->last=b; /* 将删除的元素存放到e所指向的变量中*/for(k=i;k+j-1<=L->last;k+)L->elemk-1=L->elemk+j-1; /*将后面的元素依次前移*/L->last=L->last-j;printf("删除的元素值为:");for(c=0;c<b;c+)printf("%d ",e->elemc);printf("n");return(OK);void main()SeqList *l,*q;int p,r;int i,j,m;l = (SeqList*)malloc(sizeof(SeqList);q = (SeqList*)malloc(sizeof(SeqList);printf("请输入线性表的长度:");scanf("%d",&r);l->last = r-1;printf("请输入线性表的各元素值:n");for(i=0; i<=l->last; i+)scanf("%d",&l->elemi); px(l,i); for(i=0;i<=r-1;i+)printf("%d ",l->elemi);printf("n");printf("请输入要删除的元素位置(位置+个数):n");scanf("%d%d",&p,&j);m=DelList(l,p,q,j); if(m=0)printf("无法删除");exit(0);else if(m=1)printf("线性表内余下元素为：n");for(i=0;i<=r-j-1;i+)printf("%d ",l->elemi);printf("n");void px(SeqList *A,int j)int i,temp,k;for(i=0;i<j;i+)for(k=0;k<j-1;k+)if(A->elemi<A->elemk)temp=A->elemi;A->elemi=A->elemk;A->elemk=temp;printf("排序完成！");3. #include <stdio.h>#include <stdlib.h>#include <string.h>/*#define ElemType char*/typedef struct Node /*结点类型定义*/ int num;char name10;int age;struct Node * next;Node, *LinkList; /* LinkList为结构指针类型*/LinkList CreateFromTail()/*通过键盘输入表中元素值，利用尾插法建单链表,并返回该单链表头指针L*/ LinkList L;Node *r, *s;int a;char b10;int c;int flag =1; /*设置一个标志，初值为1，当输入"-1"时，flag为0，建表结束*/L=(Node * )malloc(sizeof(Node); L->next=NULL; /*为头结点分配存储空间，建立空的单链表L*/r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ /*循环输入表中元素值，将建立新结点s插入表尾*/printf("输入学生的信息：n");printf("学号姓名年龄n");while(flag)scanf("%d",&a);if(a=-1)flag=0;else scanf("%s%d",b,&c);s=(Node*)malloc(sizeof(Node);s->num=a; strcpy(s->name,b);s->age=c;r->next=s;r=s; r->next=NULL; return L; void ReverseList(LinkList L) Node *p,*q;p=L->next;L->next=NULL;while(p!=NULL) q=p->next; /*q指针保留p->next得值*/p->next=L->next;L->next=p; /*将p结点头插入到单链表L中*/p=q; /*p指向下一个要插入的结点*/ void main()LinkList l;Node *p;printf("请输入链表数据,以-1结束!n"); l = CreateFromTail();printf("输入的单链表为:n");p = l->next;while(p!=NULL)printf("%d %s %dn",p->num,p->name,p->age);p=p->next;ReverseList(l);printf("逆置后的单链表为:n");p = l->next;while(p!=NULL)printf("%d %s %dn",p->num,p->name,p->age);p=p->next;实验结果及分析1.实验结果： 实验分析：我做了三次实验，分别插入数列前，中，后的数字，实验证明代码没有错误，能正常运行、排序、输出。存在的问题：我不明白为什么我写的是降序排序，计算机运行后就是升序排序了。希望老师能帮我修改一下。2.实验结果实验分析：我通过三次实验（正常删除、删除个数超出、删除位置不正确）证明代码的正确性。改代码可实现派讯，删除，读取删除的内容和输出的功能。4. 实验结果实验分析： 我做了两次测试，测试证明代码没有错误。教师评阅 教师签名： 年 月 日实验序号2实验名称实验二 栈和队列基本操作实验地点S-C1303实验日期2013年 05 月 13 日 实验内容1.利用栈的运算实现数制转换-分别将十进制转换为八进制和十六进制。2.编程判断一个字符序列是否是回文序列。输入形式为“*#*”，*为输入的字符，#为两序列的分隔符。3.实现链队列管理-输入一个整数，如果是奇数就入队，如果是偶数就让队头出队，直到输入0就结束，最后输出队列的所有元素。实验过程及步骤（代码）1.#include<stdio.h>#include<malloc.h>#include<windows.h>#define NULL 0typedef struct Numberint num; struct Number *next;Num;void Conversion(int iNum,int i); /转换数字，进栈，iNum为待转换的数，i代表进制void Pop(struct Number *top,int i); /显示结果，出栈，top为栈顶指针，i代表进制void main()int m=8,n=2,j=16; int iNum; char choose,c; printf("数制转换nn"); printf("请输入一个十进制数: "); scanf("%d",&iNum); printf("转换后结果为:n"); printf("n八进制:"); Conversion(iNum,m); printf("十六进制:"); Conversion(iNum,j); printf("n转换完毕!n");void Conversion(int iNum,int i) /进栈struct Number *top=NULL,*NewP; while(iNum!=0) NewP=(struct Number *)malloc(sizeof(struct Number); if(top=NULL) NewP->next=NULL; top=NewP; top->num=iNum%i; else NewP->next=top; top=NewP; top->num=iNum%i; iNum=iNum/i; /while Pop(top,i); printf("n");void Pop(struct Number *top,int i) /出栈 if(top=NULL) printf("栈空!n"); else char cell="ABCDEF" struct Number *temp,*q; switch(i) case 8: /输出八进制 case 16: /输出十六进制 temp=top; while(temp!=NULL) printf("%c",celltemp->num); q=temp;temp=temp->next;free(q);break; /switch /else2.#include <stdio.h>#include <string.h>#include <conio.h>int huiWen(const char *p);int main() char test225;printf("请输入序列：n"); gets(test); if(huiWen(test) printf("是回文!n"); else printf("不是回文!n"); getch(); return 0;int huiWen(const char *p) int i=0,n=strlen(p); while(pi=pn-i-1 && i<n-i-1) /只要相等且还未相遇则继续循环 i+; return (i<n-i-1)? 0:1); /若i<n-i-1表示中途遇到不相等的字符而退出循环3.#define TRUE 1#define FALSE 0#define MAXSIZE 50 /*队列的最大长度*/typedef structint elementMAXSIZE; /* 队列的元素空间*/int front; /*头指针指示器*/int rear; /*尾指针指示器*/SeqQueue;/*初始化操作*/void InitQueue(SeqQueue *Q) /* 将*Q初始化为一个空的循环队列 */Q->front=Q->rear=0;/*入队操作*/int EnterQueue(SeqQueue *Q, int x) /*将元素x入队*/if(Q->rear+1)%MAXSIZE=Q->front) /*队列已经满了*/return(FALSE);Q->elementQ->rear=x;Q->rear=(Q->rear+1)%MAXSIZE; /* 重新设置队尾指针 */return(TRUE); /*操作成功*/*出队操作*/int DeleteQueue(SeqQueue *Q) /*删除队列的队头元素，用x返回其值*/if(Q->front=Q->rear) /*队列为空*/return(FALSE);Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/return(TRUE); /*操作成功*/int output(SeqQueue *Q)int x,i=Q->front;/*提取队列的队头元素，用x返回其值*/if(Q->front=Q->rear) /*队列为空*/return(FALSE);while(i!=Q->rear)x=Q->elementi;printf("%d ",x);i+;return(TRUE); /*操作成功*/#include "seqqueue1.h"#include<stdio.h>void main()int c;SeqQueue Q;InitQueue(&Q);printf("请输入整数：");scanf("%d",&c);while(c!=0)if(c%2=1)EnterQueue(&Q,c);else DeleteQueue(&Q);printf("请输入整数：");scanf("%d",&c); output(&Q);实验结果及分析（每道题的运行结果及分析总结） 1. 实验结果： 实验分析：我测视了两组数据，均正确，证明我的代码没有错误。该代码可实现将一个十进制数转换为八进制和十六进制的数。2. 实验结果实验分析： 我做了四次实验有不同长度的回文序列、长度相同的非回文序列和长度不同的非回文序列。实验正经代码正确。3.实验分析：测试了3组不同的数据，均能满足实验要求，证明代码是正确的。教师评阅 教师签名： 年 月 日实验序号3实验名称实验三 二叉树基本操作实验地点S-C1303实验日期2013年 05月 27日 实验内容1. 统计一棵二叉树中每种类型结点数（度为0、1、2的结点数）。2. 分别输入一棵有6个结点和8个结点的二叉树，编程序输出先序、中序和后序的遍历结果。3. 哈夫曼树及哈夫曼编码。实验过程及步骤（代码）1. #include <stdio.h>#include <malloc.h>#include <conio.h>typedef char DataType;int LeafCount,onecount,twocount;typedef struct NodeDataType data;struct Node *LChild;struct Node *RChild;BiTNode, *BiTree;void CreateBiTree(BiTree *bt)char ch;ch = getchar(); if(ch='.') *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); /生成一个新结点 (*bt)->data=ch; CreateBiTree(&(*bt)->LChild); /生成左子树 CreateBiTree(&(*bt)->RChild); /生成右子树void leaf_a(BiTree root)if(root!=NULL)leaf_a(root->LChild);leaf_a(root->RChild);if (root ->LChild=NULL && root ->RChild=NULL)LeafCount+;else if(root ->LChild!=NULL) && (root ->RChild=NULL)|(root ->LChild=NULL) && (root ->RChild!=NULL)onecount+;else if(root ->LChild!=NULL) && (root ->RChild!=NULL)twocount+;#include"head.h"void main()BiTree T;int treeleaf;LeafCount = 0;printf("按扩展先序遍历序列建立二叉树，请输入序列:n"); CreateBiTree(&T);leaf_a(T);printf("求得的叶子结点数目为:%dn",LeafCount);printf("求得的度为1的结点数目为:%dn",onecount);printf("求得的度为2的结点数目为:%dn",twocount);getch();2. #include <stdio.h>#include <malloc.h>#include <conio.h>typedef char DataType;int LeafCount,onecount,twocount;typedef struct NodeDataType data;struct Node *LChild;struct Node *RChild;BiTNode, *BiTree;void CreateBiTree(BiTree *bt)char ch;ch = getchar(); if(ch='.') *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); /生成一个新结点 (*bt)->data=ch; CreateBiTree(&(*bt)->LChild); /生成左子树 CreateBiTree(&(*bt)->RChild); /生成右子树void Visit(DataType a)printf("%C",a);void InOrder(BiTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/if (root!=NULL)InOrder(root ->LChild); /*中序遍历左子树*/Visit(root ->data); /*访问根结点*/InOrder(root ->RChild); /*中序遍历右子树*/void PostOrder(BiTree root) /* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL)PostOrder(root ->LChild); /*后序遍历左子树*/PostOrder(root ->RChild); /*后序遍历右子树*/Visit(root ->data); /*访问根结点*/void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/if (root!=NULL)Visit(root ->data); /*访问根结点*/PreOrder(root ->LChild); /*先序遍历左子树*/PreOrder(root ->RChild); /*先序遍历右子树*/#include"head.h"void main()BiTree T;int treeleaf;LeafCount = 0;printf("按扩展先序遍历序列建立二叉树，请输入序列:n"); CreateBiTree(&T);printf("先序遍历结果：n");PreOrder(T);printf("n");printf("中序遍历结果：n");InOrder(T);printf("n");printf("后序遍历结果：n");PostOrder(T);printf("n");getch();3. #include <stdio.h>#include <stdlib.h>#include <string.h>typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*/typedef struct unsigned int weight ; /* 用来存放各个结点的权值*/unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/HTNode, * HuffmanTree; /*动态分配数组，存储哈夫曼树*/void select(HuffmanTree *ht,int n, int *s1, int *s2)int i;int min;for(i=1; i<=n; i+)if(*ht)i.parent = 0)min = i;i = n+1;for(i=1; i<=n; i+)if(*ht)i.parent = 0)if(*ht)i.weight < (*ht)min.weight)min = i;*s1 = min;for(i=1; i<=n; i+)if(*ht)i.parent = 0 && i!=(*s1)min = i;i = n+1;for(i=1; i<=n; i+)if(*ht)i.parent = 0 && i!=(*s1)if(*ht)i.weight < (*ht)min.weight)min = i;*s2 = min;void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) /* w存放已知的n个权值，构造哈夫曼树ht */int m,i;int s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /*0号单元未使用*/for(i=1;i<=n;i+) /*1-n号放叶子结点，初始化*/(*ht)i.weight = wi;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0;for(i=n+1;i<=m;i+)(*ht)i.weight = 0;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0; /*非叶子结点初始化*/*-初始化完毕！对应算法步骤1-*/for(i=n+1;i<=m;i+) /*创建非叶子结点,建哈夫曼树*/ /*在(*ht)1(*ht)i-1的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/select(ht,i-1,&s1,&s2);(*ht)s1.parent=i;(*ht)s2.parent=i;(*ht)i.LChild=s1;(*ht)i.RChild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight; /*哈夫曼树建立完毕*/void outputHuffman(HuffmanTree HT, int m)if(m!=0)printf("%d ", HTm.weight);outputHuffman(HT,HTm.LChild);outputHuffman(HT,HTm.RChild);void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/char *cd;int i;unsigned int c;int start;int p;hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); /*分配n个编码的头指针*/cd=(char * )malloc(n * sizeof(char ); /*分配求当前编码的工作空间*/cdn-1='0' /*从右向左逐位存放编码，首先存放编码结束符*/for(i=1;i<=n;i+) /*求n个叶子结点对应的哈夫曼编码*/start=n-1; /*初始化编码起始指针*/for(c=i,p=(*ht)i.parent; p!=0; c=p,p=(*ht)p.parent) /*从叶子到根结点求编码*/if( (*ht)p.LChild = c) cd-start='0' /*左分支标0*/else cd-start='1' /*右分支标1*/hci=(char *)malloc(n-start)*sizeof(char); /*为第i个编码分配空间*/strcpy(hci,&cdstart);free(cd);for(i=1;i<=n;i+)printf("%d编码为%sn",(*ht)i.weight,hci);void main() HuffmanTree HT; HuffmanCode HC; int *w; int i,n; / the number of elements; int wei; / the weight of a element; int m;printf("input the total number of the Huffman Tree:" ); scanf("%d",&n); w=(int *)malloc(n+1)*sizeof(int); for(i=1;i<=n;i+) printf("input the %d element's weight:",i); fflush(stdin);scanf("%d",&wei); wi=wei; CrtHuffmanTree(&HT,w,n); m = 2*n-1;outputHuffman(HT,m); printf("n");CrtHuffmanCode(&HT,&HC,n);实验结果及分析（每道题的运行结果及分析总结） 1. 实验结果：（1） abcdefgh叶子结点有三个：d e h 度为1 的结点有三个：b f g 度为2的结点有两个：a c实验证明代码正确。（2）123456789叶子结点有5个：3 5 6 8 9度为1的结点有0