《数据结构实验答案(共65页).doc》由会员分享，可在线阅读，更多相关《数据结构实验答案(共65页).doc（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上重庆文理学院软件工程学院实 验 报 告 册专 业：_软件工程_ _班 级：_软件工程2班_ _学 号：_4 _姓 名：_周贵宇_课程名称：_ 数据结构 _指导教师：_胡章平_ 2013年 06 月 25 日实验序号1实验名称实验一 线性表基本操作实验地点S-C1303实验日期2013年 04月 22日 实验内容1. 编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。2. 编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。3. 编程序实现将单链表的数据逆置，即将原表的数据（a1,a2.an）变成(an,.a2,a1)。（单链表的数据域数据类型为
2、一结构体，包括学生的部分信息：学号，姓名，年龄）实验过程及步骤1. #include #include #include #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
3、common.h#include seqlist.hvoid 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; ilast; i+)scanf(%d,&l-elemi); px(l,i);printf(请输入要插入的值:n);scanf(%d,&l-elemi);i+；px(l,i);l-last+;for(
4、i=0; ilast; i+)printf(%d ,l-elemi);printf(n);void px(SeqList *A,int j)int i,temp,k;for(i=0;ij;i+)for(k=0;kelemielemk)temp=A-elemi;A-elemi=A-elemk;A-elemk=temp;2. #include #include #include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100 /*此处的宏定义常量表示线性表可
5、能达到的最大长度*/typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList;#include common.h#include seqlist.hvoid 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(iL-last+
6、2) printf(删除位置不合法!);return(ERROR);if(jL-last-i) printf(删除位置不合法!);return(ERROR);for(b=0,a=i-1;aelemb=L-elema; e-last=b; /* 将删除的元素存放到e所指向的变量中*/for(k=i;k+j-1last;k+)L-elemk-1=L-elemk+j-1; /*将后面的元素依次前移*/L-last=L-last-j;printf(删除的元素值为:);for(c=0;celemc);printf(n);return(OK);void main()SeqList *l,*q;int p,
7、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; ilast; i+)scanf(%d,&l-elemi); px(l,i); for(i=0;ielemi);printf(n);printf(请输入要删除的元素位置(位置+个数):n);scanf(%d%d,&p,&j);m=DelList(l,p,q,j); if(m=0
8、)printf(无法删除);exit(0);else if(m=1)printf(线性表内余下元素为：n);for(i=0;ielemi);printf(n);void px(SeqList *A,int j)int i,temp,k;for(i=0;ij;i+)for(k=0;kelemielemk)temp=A-elemi;A-elemi=A-elemk;A-elemk=temp;printf(排序完成！);3. #include #include #include /*#define ElemType char*/typedef struct Node /*结点类型定义*/ int nu
9、m;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*/
10、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
11、;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;ReverseL
12、ist(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. 实验结果实验分析： 我做
13、了两次测试，测试证明代码没有错误。教师评阅 教师签名： 年 月 日实验序号2实验名称实验二 栈和队列基本操作实验地点S-C1303实验日期2013年 05 月 13 日 实验内容1.利用栈的运算实现数制转换-分别将十进制转换为八进制和十六进制。2.编程判断一个字符序列是否是回文序列。输入形式为“*#*”，*为输入的字符，#为两序列的分隔符。3.实现链队列管理-输入一个整数，如果是奇数就入队，如果是偶数就让队头出队，直到输入0就结束，最后输出队列的所有元素。实验过程及步骤（代码）1.#include#include#include#define NULL 0typedef struct Numb
14、erint 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八进制:); Convers
15、ion(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; iN
16、um=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.
17、#include #include #include 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 & in-i-1) /只要相等且还未相遇则继续循环 i+; return (in-i-1)? 0:1); /若ifront
18、=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-fro
19、nt=(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#includevoid main()int c;SeqQueue Q;InitQueue(&Q);prin
20、tf(请输入整数：);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组不同的数据，均能满足实验要求，证
21、明代码是正确的。教师评阅 教师签名： 年 月 日实验序号3实验名称实验三 二叉树基本操作实验地点S-C1303实验日期2013年 05月 27日 实验内容1. 统计一棵二叉树中每种类型结点数（度为0、1、2的结点数）。2. 分别输入一棵有6个结点和8个结点的二叉树，编程序输出先序、中序和后序的遍历结果。3. 哈夫曼树及哈夫曼编码。实验过程及步骤（代码）1. #include #include #include typedef char DataType;int LeafCount,onecount,twocount;typedef struct NodeDataType data;struct
22、 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)lea
23、f_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+;#includehead.hvoid main()BiTree T;int treeleaf;L
24、eafCount = 0;printf(按扩展先序遍历序列建立二叉树，请输入序列:n); CreateBiTree(&T);leaf_a(T);printf(求得的叶子结点数目为:%dn,LeafCount);printf(求得的度为1的结点数目为:%dn,onecount);printf(求得的度为2的结点数目为:%dn,twocount);getch();2. #include #include #include typedef char DataType;int LeafCount,onecount,twocount;typedef struct NodeDataType data;st
25、ruct 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);vo
26、id 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
27、-RChild); /*后序遍历右子树*/Visit(root -data); /*访问根结点*/void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/if (root!=NULL)Visit(root -data); /*访问根结点*/PreOrder(root -LChild); /*先序遍历左子树*/PreOrder(root -RChild); /*先序遍历右子树*/#includehead.hvoid main()BiTree T;int treeleaf;LeafCount = 0;printf(按扩展先序遍历
28、序列建立二叉树，请输入序列:n); CreateBiTree(&T);printf(先序遍历结果：n);PreOrder(T);printf(n);printf(中序遍历结果：n);InOrder(T);printf(n);printf(后序遍历结果：n);PostOrder(T);printf(n);getch();3. #include #include #include typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*/typedef struct unsigned int weight ; /* 用来存放各个结点的权值*/unsigned int
29、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;
30、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号单
31、元未使用*/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为
32、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,HT
33、m.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;
34、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编码为
35、%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 elements 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