搜索
数据结构实验-1-数据结构设计性实验项目1.线性表的合并：已知线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。分别采用顺序存储结构和链式结构来实现。2.线性表的逆置：设有一个线性表（e0,e1,…,en-2,en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1,en-2,…,e1,e0）。线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。3.约瑟夫环的实现：设有n个人围坐一圈，用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，现从某个位置s上的人开始报数，数到m的人出列，接着从出列的下一个人又从1开始重新报数，数到m的人出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。如n=8,m=4,s=1时，设每个人的编号依次为1，2，3，…开始报数，则得到的出列次序为4，8，5，2，1，3，7，6。检查程序的正确性和健壮性。(1)采用数组表示作为求解过程中使用的数据结构。(2)采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界限。4.数制转换：利用顺序栈和链栈实现数制转换5.二叉树的遍历：分别以顺序存储结构和二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。6.赫夫曼树与赫夫曼编码：已知某系统在通信联络中只可能出现8种字符a,b,c,d,e,f,g,h，其概率分别为{0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11}，试设计Huffman编码，并计算其平均码长。(1)初始化：从键盘读入8个字符，以及它们的权值，建立Huffman树。(2)编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。(3)译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。(4)打印Huffman树。7.学生成绩管理查询系统：每个学生的数据信息有准考证号（主关键字）、姓名、语文、英语、数学、和总分等数据项，所有学生的信息构成一个学生成绩表。假设准考证号的头两位表示地区编号。请设计一个管理系统达到如下基本要求：（1）初始化：建立一个学生成绩表，输入准考证号、姓名、语文、英语、数学，然后计算每个学生的总分，存入相应的数据项；注意：分析数据对象和它们之间的关系，并以合适的方式进行组织（可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示）；（2）查找：综合应用基本查找算法完成数据的基本查询工作，并输出查询的结果；（3）输出：有选择性地输出满足一定条件的数据记录，如输出地区编号为01，并且总分在550分以上的学生的信息；（4）计算：计算在等概率情况下该查找表的平均查找长度。8.排序：编制程序让机器随机产生2000个整数，放入一个数组中；对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序，并比较它们的运行时间。注意：每三、四个同学组成一个小组。每个实验中的题目，可分别由不同的同学完-2-成。其它题目可以相互交流，以利于互相提高。-3-数据结构验证性实验项目实验一线性表的顺序存储实验一、实验目的及要求1、掌握在TC环境下调试顺序表的基本方法2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。二、实验学时2学时三、实验任务1、生成一个顺序表并动态地删除任意元素和在任意位置插入元素。2、将两个有序表合并成一个有序表。四、实验重点、难点1、在顺序表中移动元素。2、在顺序表中找到正确的插入位置。五、操作要点(一)顺序表基本操作的实现[问题描述]当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。[基本要求]要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。[实现提示]要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。[程序实现]#includestdio.h#includeconio.htypedefintDataType;#definemaxnum20typedefstruct{intdata[maxnum];intlength;}SeqList;/*插入函数*/intinsert(SeqList*L,inti,DataTypex)/*将新结点x插入到顺序表L第i个位置*/{intj;if(i0||i(*L).length+1){printf(\ni值不合法!);return0;}if((*L).length=maxnum-1){printf(\n表满不能插入!);return0;}for(j=(*L).length;j=i;j--)(*L).data[j+1]=(*L).data[j];(*L).data[i]=x;(*L).length++;-4-return1;}/*删除函数*/intdelete(SeqList*L,inti)/*从顺序L中删除第i个结点*/{intj;if(i0||i(*L).length){printf(\n删除位置错误!);return0;}for(j=i+1;j=(*L).length;j++)(*L).data[j-1]=(*L).data[j];(*L).length--;return1;}/*生成顺序表*/voidcreatlist(SeqList*L){intn,i,j;printf(请输入顺序表L的数据个数：\n);scanf(%d,&n);for(i=0;in;i++){printf(data[%d]=,i);scanf(%d,&((*L).data[i]));}(*L).length=n-1;printf(\n);}/*creatlist*//*输出顺序表L*/printout(SeqList*L){inti;for(i=0;i=(*L).length;i++){printf(data[%d]=,i);printf(%d,(*L).data[i]);}/*printout*/printf(\n);}main(){SeqList*L;charcmd;inti,t,x;clrscr();creatlist(L);do{printf(\ni,I-----插入\n);printf(d,D-----删除\n);printf(q,Q-----退出\n);do{cmd=getchar();}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q'));-5-switch(cmd){case'i':case'I':printf(\nPleaseinputtheDATA:);scanf(%d,&x);printf(\nWhere?);scanf(%d,&i);insert(L,i,x);printout(L);break;case'd':case'D':printf(\nWheretoDelete?);scanf(%d,&i);delete(L,i);printout(L);break;}}while((cmd!='q')&&(cmd!='Q'));}（二）有序顺序表的合并[问题描述]已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc[基本要求]lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表[程序实现]#includestdio.h#definemaxnum20typedefintDataType;typedefstruct{DataTypedata[maxnum];intlength;}SeqList;intMergeQL(SeqListla,SeqListlb,SeqList*lc){inti,j,k;if(la.length+1+lb.length+1maxnum){printf(\narrayoverflow!);return0;}i=j=k=0;while(i=la.length&&j=lb.length){if(la.data[i]=lb.data[j])lc-data[k++]=la.data[i++];elselc-data[k++]=lb.data[j++];}/*处理剩余部分*/while(i=la.length)lc-data[k++]=la.data[i++];while(j=lb.length)lc-data[k++]=lb.data[j++];lc-length=k-1;return1;}-6-main(){SeqListla={{3,4,7,12,15},4};SeqListlb={{2,5,7,15,18,19},5};SeqListlc;inti;if(MergeQL(la,lb,&lc)){printf(\n);for(i=0;i=lc.length;i++)printf(%4d,lc.data[i]);}}六、注意事项1、删除元素或插入元素表的长度要变化。2、在合并表中当某一个表到表尾了就不用比较了，直接将另一个表的元素复制到总表去即可。实验二单链表实验一、实验目的及要求1、掌握用在TC环境下上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现3、进一步掌握循环单链表的插入、删除、查找算法的实现二、实验学时4学时三、实验任务1、在带头结点的单链表h中第i个数据元素之前插入一个数据元素。2、将两个有序单链表合并成一个有序单链表。3、生成一个循环单链表。4、在循环单链表中删除一个节点。四、实验重点、难点1、在单链表中寻找到第i-1个结点并用指针p指示。2、比较两个单链表的节点数据大小。3、循环单链表中只有一个节点的判断条件。4、在循环单链表中删除一个节点。五、操作要点（一）单链表基本操作的实现[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。[基本要求]用链式存储结构实现存储[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。[程序实现]-7-#includestdio.h#includemalloc.htypedefcharDataType;typedefstructnode{DataTypedata;/*结点的数据域*/structnode*next;/*结点的指针域*/}ListNode;voidInit_List(ListNode**L){(*L)=(ListNode*)malloc(sizeof(ListNode));/*产生头结点*/(*L)-next=NULL;}intList_Length(ListNode*L){intn=0;ListNode*p=L-next;while(p!=NULL){n++;p=p-next;}returnn;}ListNode*GetNode(ListNode*L,inti){intj;ListNode*p;p=L;j=0;/*从头结点开始扫描*/while(p-next&&j!=i)/*顺指针向后扫描,直到p-next为NULL或i=j为止*/{p=p-n