数据结构完整题目及答案1.doc

数据结构与算法实验报告目 录实验一 学生成绩分析程序.41.1 上机实验的问题和要求（需求分析）： .41.2 程序设计的基本思想，原理和算法描述： .41.3 调试和运行程序过程中产生的问题及采取的措施：.41.4 运行输出结果：.41.5 源程序及注释： .5实验二 线性表的基本操作.82.1 上机实验的问题和要求（需求分析）：.82.2 程序设计的基本思想，原理和算法描述： .82.3 调试和运行程序过程中产生的问题及采取的措施：.82.4 运行输出结果：.82.5 源程序及注释： .8实验三 链表的基本操作.11 3.1 上机实验的问题和要求（需求分析）：.113.2 程序设计的基本思想，原理和算法描述： .113.3 调试和运行程序过程中产生的问题及采取的措施：.113.4 运行输出结果：.113.5 源程序及注释： .11实验四 单链表综合实验 .14 4.1 上机实验的问题和要求（需求分析）：.144.2 程序设计的基本思想，原理和算法描述： .144.3 调试和运行程序过程中产生的问题及采取的措施：.144.4 运行输出结果：.144.5 源程序及注释： .14实验五 串.195.1 上机实验的问题和要求（需求分析）：.195.2 程序设计的基本思想，原理和算法描述： .195.3 调试和运行程序过程中产生的问题及采取的措施：.195.4 运行输出结果：.195.5 源程序及注释： .21实验六 循环队列的实现与运算.226.1 上机实验的问题和要求（需求分析）：.226.2 程序设计的基本思想，原理和算法描述： .226.3 调试和运行程序过程中产生的问题及采取的措施：.22 6.4 运行输出结果：.226.5 源程序及注释： .23实验七 栈子系统.267.1 上机实验的问题和要求（需求分析）：.267.2 程序设计的基本思想，原理和算法描述： .267.3 调试和运行程序过程中产生的问题及采取的措施：.26 7.4 运行输出结果：.267.5 源程序及注释： .28实验八 树.368.1 上机实验的问题和要求（需求分析）：.368.2 程序设计的基本思想，原理和算法描述： .398.3 调试和运行程序过程中产生的问题及采取的措施：.39 8.4 运行输出结果：.39 8.5 源程序及注释： .41实验九 建立哈夫曼树与哈夫曼树与码.509.1 上机实验的问题和要求（需求分析）：.509.2 程序设计的基本思想，原理和算法描述： .509.3 调试和运行程序过程中产生的问题及采取的措施：.50 9.4 运行输出结果：.50 9.5 源程序及注释： .50实验十 图.5310.1 上机实验的问题和要求（需求分析）：.5310.2 程序设计的基本思想，原理和算法描述： .5310.3 调试和运行程序过程中产生的问题及采取的措施：.53 10.4 运行输出结果：.53 10.5 源程序及注释： .53实验一 学生成绩分析程序一、 上机实验的问题和要求（需求分析）：【题目】设一个班有10个学生，每个学生有学号，以及数学、物理、英语、语文、体育 5 门课的成绩信息。分别编写3个函数以实现以下3个要求：（1） 求数学的平均成绩。（2） 对于有两门以上课程不及格的学生，输出他们的学号、各门课成绩及平均成绩。（3） 输出成绩优良的学生（平均成绩在85分以上或全部成绩都在80分以上）的学号、各门课成绩和平均成绩。二、 程序设计的基本思想，原理和算法描述：【算法描述】（1）用数组id3,name10,score5来记录是个学生的各门课程的成绩.将数学科目的成绩相加再求出平均成绩。（2）取一个未知数A来求学生的不及格数，a=2时输出学生的名字学号和成绩。（3）求出所有的成绩的平均分并输出各门成绩和平均成绩。三、调试和运行程序过程中产生的问题及采取的措施：基本上是输入时的细节如大括号的位置等。四、运行输出结果五、源程序及注释：输入学生的学号姓名和成绩：#includestdio.hstruct STUDENTchar id3;char name10;int score5;double ave;stu10;void main()int num=10,i,j,all=0;for(i=0;inum;i+)printf(t请输入第%d学生的数据:,i+1);printf(t学号: );scanf(%S,stui.id);printf(t姓名: );scanf(%s,); j=0; printf(t语文课的成绩);scanf(%d,&stui.scorej);j+; printf(t数学课的成绩); scanf(%d,&stui.scorej);j+;printf(t物理课的成绩);scanf(%d,&stui.scorej);j+;printf(t英语课的成绩);scanf(%d,&stui.scorej);j+;printf(t体育课的成绩);scanf(%d,&stui.scorej); pj ();bjg();yx();输出数学平均成绩：void pj(stu10)int a,b,i;for(i=0;i10;i+);a=a+stui.score2; b=a/10;printf(tthe everage score is:%d,b);求出不及格人数：void bjg()int i,j=0,c=0;for(i=0;i10;i+);for(j=0;j5;i+);if(stui.scorej=2);printf(两门课以上不及格的同学：);printf(%dt%dt%dt%dt,stui.id,,stui.score);输出优秀学生：void yx()int i,j=0,c=0;for(i=0;i10;i+);for(j=0;j=80)c=c+;if(c=5);printf(优秀学生为：);printf(%dt%dt%dt%dt,stui.id,,stui.score); 实验二 线性表的基本操作一、 上机实验的问题和要求（需求分析）：【题目】线性表的插入，删除。二、 程序设计的基本思想，原理和算法描述：【算法描述】当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。三、调试和运行程序过程中产生的问题及采取的措施：四、运行输出结果：五、源程序及注释：#includetypedef struct linknodechar data;struct linknode *next;linnode;linnode *head;int n;创建线性表：void Createlist()n=0;linknode *p,*s;char x;int z=1;head=new linknode;p=head;printf(ntt请逐个输入结点，以“X”为结素标记！n);while(z)printf(tt输入一个字符数据，并按回车：);scanf(%c,&x);getchar();if(x!=x)s=new linknode;n+;s-data=x;p-next=s;s-next=NULL;p=s;else z=0;线性表的插入：void InsList(int i,char x)linknode *s,*p;p=head;int j=0;while(p!=NULL&jnext;if(p!=NULL)s=new linknode;s-data=x;s-next=p-next;p-next=s;n+;elseprintf(ntt线性表为空或插入位置超出！n);线性表的删除：void DelList(char x)linknode *p,*q;if(head-next=NULL)printf(ntt线性表下溢！);return;if(head-next=NULL)printf(ntt线性表已经为空！);return;q=head;p=head-next;while(p!=NULL&p-data!=x)q=p;p=p-next;if(p!=NULL)q-next=p-next;delete p;n-;printf(ntt结点已经被删除！);scanf(nt抱歉！没有找到您要删除的节点.);实验三 链表的基本操作一、 上机实验的问题和要求（需求分析）：【题目】建立线性链表，链表的插入、删除，查找。二、 程序设计的基本思想，原理和算法描述：【算法描述】线性链表不需要用地址连续的存储空间来实现，链式存储的线性表对于插入、删除操作不再需要移动数据元素。三、调试和运行程序过程中产生的问题及采取的措施：四、运行输出结果：五、源程序及注释：建立线性链表：#includetypedef struct linknodechar data;struct linknode *next;linnode;linnode *head;int n;void CreateList()n=0;linnode *p,*s;char x;int z=1;head=new linnode;p=head;printf(ntt建立一个线性表);printf(ntt说明：请逐个输入字符，结素标记为x!n);while(z)printf(tt put in: );scanf(%c,&x);getchar();if(x!=x)s=new node;n+;s-data=x;s-next=s;else z=0;链表的插入：void InsList(int i,char x)linnode *s,*p;p=head;int j=0;while(p!=NULL&jnext; if(p!=NULL)s=new linnode;s-data=x;s-next=p-next;p-next=s;n+;else printf(ntt线性表为空或插入位置出错！n);链表的删除：void DelList(char x)node *p,*q;if(head=NULL)printf(tt链表下溢!n);return;if(head-next=NULL)printf(tt线性表已经为空！);return;q=head;p=head-next;while(p!=NULL&p-data!=x)q=p;p=p-next;if(p!=NULL)q-next=p-next;delete p;n-;printf(tt已经被删除！n);elseprintf(tt未找到！n);链表的查找：实验四 单链表综合实验一、 上机实验的问题和要求（需求分析）：【题目】（1）、建立自己的有关单链表的头文件（2）、单链表基本操作的实现问题描述要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。二、 程序设计的基本思想，原理和算法描述：【算法描述】链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。三、调试和运行程序过程中产生的问题及采取的措施：四、运行输出结果：五、源程序及注释：# include # include typedef char DataType ;建立数组：typedef struct node DataType data; struct node *next; ListNode;产生头结点：void Init_List(ListNode *L)(*L)=(ListNode *)malloc(sizeof(ListNode);(*L)-next=NULL;测量单链表长度：int List_Length(ListNode *L )int n=0;ListNode *p=L-next;while(p!=NULL)n+;p=p-next;return n;单链表的查找第i个节点：ListNode* GetNode(ListNode *L,int i) int j;ListNode *p; p=L;j=0; /*从头结点开始扫描*/ while(p-next&j!=i) /*顺指针向后扫描,直到p-next为NULL或i=j为止*/ p=p-next; j+; if(i=j) return p; /*找到了第i个结点*/ else return NULL; /*当ij时,找不到第i个结点*/ 单链表在第i个节点插入：void InsertList(ListNode *L,DataType x,int i) ListNode *p,*s; p=GetNode(L,i-1); /*寻找第i-1个结点*/ if (p=NULL) /*in+1时插入位置i有错*/ printf(error!); return ; s=(ListNode *)malloc(sizeof(ListNode); /*建立一个新的节点*/ s-data=x;s-next=p-next;p-next=s; /*将节点插入单链表*/ 删除单链表第i个节点：void DeleteList(ListNode *L ,int i)ListNode *p,*r;p=GetNode(L,i-1); /*找到第i-1个结点*/if (p=NULL|p-next=NULL) printf(error!); return ; r=p-next; /*使r指向被删除的结点a*/p-next=r-next; /*将ai从链上删除*/free(r); 使用头插法建立带头结点链表算法:ListNode * CreatListF(void)char ch;ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成头结点*/ListNode *s; /*工作指针*/head-next=NULL; ch=getchar(); /*读入第1个字符*/while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode); /*生成新结点*/ s-data=ch; /*将读入的数据放入新结点的数据域中*/ s-next=head-next; head-next=s; ch=getchar(); /*读入下一字符*/return head; 使用尾插法建立带头结点链表算法:ListNode * CreatListR1(void) char ch; ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成头结点*/ ListNode *s,*r; /*工作指针*/ r=head; /*尾指针初值也指向头结点*/ while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode); s-data=ch; r-next=s; r=s; r-next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/ return head; /*复制链表A中的内容到表B中*/ void copy(ListNode *a, ListNode *b) ListNode *pa=a-next; ListNode *u; ListNode *rb=b; while(pa!=NULL) u=( ListNode *)malloc(sizeof(ListNode); u-data=pa-data; rb-next=u; rb=u; pa=pa-next;rb-next=NULL;/*输出带头结点的单链表*/void DisplaySL(ListNode *la, char *comment) ListNode *p ; p=la-next ; if(p)printf(n%sn , comment) ; while(p)printf(%4c,p-data);p=p-next; printf(n) ;/*主函数*/main( ) ListNode *la ,*lb,*lc, *p ;int n,x,i;printf(n用头插法建立链表la，请输入节点内容:);la=CreatListF();DisplaySL(la,新生成链la节点内容:); printf(n链表la的长度: %2d,List_Length(la);printf(n请输入要插入的元素: );scanf(%c,&x) ;printf(n请输入要插入的位置：);scanf(%d,&i) ;InsertList(la,x,i);DisplaySL(la,插入后链la节点内容);printf(n请输入要删除元素的位置：);scanf(%d,&i);DeleteList(la,i);DisplaySL(la, 删除后链la节点内容);printf(n用尾插法建立链表lb，请输入节点内容:);fflush(stdin);lb=CreatListR1();DisplaySL(lb,新生成链lb节点内容:); Init_List(&lc);copy(la,lc);DisplaySL(lc,复制生成的链lc节点内容:); 实验五 串一、 上机实验的问题和要求（需求分析）：串的基本运算：创建一个串；串的复制；求串的长度；求子串；输入一个自串；删除一个子串；连接两个串；输出串。【题目】1、下列是一个置换函数，采用顺序存储方式存储串，将串s1中的第I个字符开始的j个字符（包括第I个字符）构成的子串用s2串进行替换，函数名为replace(s1,I,j,s2)。例如：replace（“abcd”,1,3,xyz”）返回”xyzd”。（填空）二、程序设计的基本思想，原理和算法描述：先提取s1中位置I之前的所有字符构成的子串str1,再提取位置I+j-1及之后的所有字符构成的子串 str2，最后将str1,s2,str2连接起来便构成了结果串三、 调试和运行程序过程中产生的问题及采取的措施：四、 运行输出结果：【题目】1、下列是一个置换函数，采用顺序存储方式存储串，将串s1中的第I个字符开始的j个字符（包括第I个字符）构成的子串用s2串进行替换，函数名为replace(s1,I,j,s2)。例如：replace（“abcd”,1,3,xyz”）返回”xyzd”。（填空）# include # include #define MaxLen 20typedef structchar ch MaxLen；int len； strtype；void create (strtype *s, char str)strcpy (s-ch, str)；s-len=strlen (str)；void disp(strtype *s)if (s-len= =0)printf( “空串n”）；else printf（“%cn”,s-ch)；strtype replace(strtype *sl, int I, int j, strtype *s2)strtype s；int n, k；if (I+j-1len)for (n=0；nchn；for (n=0；nlen；n+)s.chI+n-1=s2-chn；s.len=I+s2-len-1；for (n=s.len, k=I+j-1；kchk；s.len=n；s.chs.len=0；elses.ch0=0；s.len=0；return(s)；void main()strtype s,s1,s2；int pos, n；char strmaxlen；printf（“字符串：”）；gets(str)；create (&s1, str)；printf( “位置：”)；scanf（“%d”,& create (strtype *s, char str) )；printf( “长度：”)；scanf（“%d”,& disp(strtype *s) )；printf（“子串：”）；gets( *s2 )；create(&s2, str)；s=replace(&s1, pos, n, &s2)；disp(&s)；输出：字符串：12345678位置： 3长度： 4子串：abcdefgh五、 源程序及注释：实验六、循环队列的实现与运算一、 上机实验的问题和要求（需求分析）：1掌握队列“先进先出”的特点；2.复习队列的入队、出队、插入、删除等基本运算；3.掌握循环队列的特点，以及循环队列的应用。 二、 程序设计的基本思想，原理和算法描述1.在顺序存储结构上实现输出受限制的双端循环队列的入队和出队（只允许队头输出）算法；2.设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。3.循环队列数据类型：#define MAXLEN 10Typedef structInt dataMAXLEN;Int front,rear;csequeue;4.入队作业处理的预计执行时间可以用随机数函数rand()产生，也可以从键盘输入。三、 调试和运行程序过程中产生的问题及采取的措施：四、 运行输出结果：五、 源程序及注释：#include#define MAXLEN 10typedef struct int dataMAXLEN; / 定义数据的类型 int front,rear; / 定义队头、队尾指针csequeue;csequeue q; void IniQueue() / 初始化队列 q.front=q.rear=MAXLEN-1; void InQueue() / 入队函数 int x ; printf(ntt 输入一个入队的整数数据：); scanf(%d,&x); if (q.front=(q.rear+1) % MAXLEN ) printf(ntt 队满，不能入队! n); return; q.rear=(q.rear+1) % MAXLEN; q.dataq.rear=x; printf(ntt 入队成功! n); void Outsequeue() / 出队函数 if (q.front=q.rear) printf (ntt 此队列为空! ); return ; / 队空不能出队 else q.front=(q.front+1) % MAXLEN; printf(ntt 出队元素为：%dn,q.dataq.front); / 输出队头元素 return; void ShowQueue() / 显示函数 int k=q.front; if (k=q.rear) printf(ntt 此队列为空! n); return; printf(ntt 此队列元素为：); do k=(k+1)%MAXLEN; printf(%4d,q.datak); while(k!=q.rear); printf(n);int length() int k; k=(q.rear-q.front+MAXLEN)% MAXLEN; return k;void main() / 主函数 int i=1; int choice; IniQueue(); while (i) printf(ntt 循 环 队 列n);printf(ntt*);printf(ntt* 1-进 队 *);printf(ntt* 2-出 队 *);printf(ntt* 3-显 示 *); printf(ntt* 4-求 队 列 长 度 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(nntt 请选择菜单号: );scanf(%d,&choice);switch(choice) case 1: InQueue(); break; case 2: Outsequeue(); break; case 3: ShowQueue(); break; case 4: printf(ntt 队列长度为: %d n,length();break; case 0: i=0; break; 实验七、栈子系统一、 上机实验的问题和要求（需求分析）：【题目】（1）设计一个字符型的链栈。（2）编写进栈、出栈、显示栈中全部元素的程序。（3）编写一个把十进制整数转换成二进制数的应用程序。（4）编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序。（5）设计一个选择式菜单，以菜单方式选择上诉操作。二、 程序设计的基本思想，原理和算法描述：利用栈“后进先出”的特点做成一个存储数据的系统。三、 调试和运行程序过程中产生的问题及采取的措施：四、 运行输出结果：五、 源程序及注释：#include#include#define STACKMAX 100/*建立结构体*/typedef struct stacknodeint data;struct stacknode *next;stacknode;typedef structstacknode *top;/*指向栈顶的指针*/linkstack;/*进栈*/void Push(linkstack *s,int x)stacknode *p=new stacknode;/*建立一个新的结点*/p-data=x;p-next=s-top;s-top=p;/*出栈*/int Pop(linkstack *s)int x;stacknode *p=s-top;x=p-data;s-top=p-next;delete p;return x;/*显示栈的内容*/void ShowStack(linkstack *s)stacknode *p=s-top;if(p=NULL)printf(ntt栈为空.);elseprintf(ntt栈元素为：);while(p!=NULL)printf(%6d,p-data);p=p-next;printf(n);/*十进制转二进制*/ void ConversionB(int n)linkstack s;int x;s.top=NULL;/*置栈空*/dox=n%2;/*取余数*/n=n/2;/*取新的商*/stacknode *p=new stacknode;/*申请新的结点*/p-next=s.top;s.top=p;s.top-data=x;while(n);printf(ntt转换后的二进制数值为：);while(s.top)printf(%d,s.top-data);stacknode *p=s.top;s.top=s.top-next;delete p;printf(n);getchar();/十进制转十六进制（1）void ConversionX1(int n)linkstack s;int x;s.top=NULL;dox=n%16;n=n/16;stacknode *p=new stacknode;p-next=s.top;s.top=p;s.top-data=x;while(n);printf(ntt转换后的十六进制数值为：);while(s.top)if(s.top-data=10)printf(A);else if(s.top-data=11