北大数据结构与算法作业1及答案

北京大学数据结构与算法作业(一)及答案1.1设字符集为字母和数字的集合，字符的顺序为A，B，C，…，Z，0，l，2，…，9，请将下列字符串按字典顺序排列并存储。PAB，5C，PABC，CXY，CRSI，7，B899，B9并分析可以采取的存储方案。答：一、排序：因为这里的顺序是字母在前面，数字在后面，所以排序时不能直接使用strcmp函数直接完成，必须要自己完成。intcompare(char*ch1,char*ch2)//比较函数,比较前后两个单词的大小，如果第一{字符串小，就返回-1，反之返回1for(i=0;i1000;i++)//一个循环，逐个字符比较{if(*(ch1+i)==’\0’)return-1;//第一个字符串先出现’\0’，一定小elseif(*(ch2+i)==’\0’)return1;//道理同上elseif{if(*(ch1+i)='A'&&*(ch1+i)='Z'&&*(ch2+i)='A'&&*(ch2+i)='Z'||*(ch1+i)='0'&&*(ch1+i)='9'&&*(ch2+i)='0'&&*(ch2+i)='9')//在相同的范围内，{直接比较if(*(ch1+i)*(ch2+i))return-1;elsereturn1;}if(*(ch1+i)='A'&&*(ch1+i)='Z'&&*(ch2+i)='0'&&*(ch2+i)='9')//在不同的范围内return-1;数字一定比字母小if(*(ch1+i)='0'&&*(ch1+i)='9'&&*(ch2+i)='A'&&*(ch2+i)='Z')return1;}}}设两个字符串最长的一个长度为n,则规模为O(n).for(inti=1;i8;i++)//冒泡排序for(intj=0;j8-i;j++){if(compare(ch[j],ch[j+1])==1){temp=ch[j];ch[j]=ch[j+1];ch[j+1]=ch;}}算法规模为O(n*n)排序后的结果：B899，B9，CRSI，CXY，PAB，PABC，5C，7二、存储1、顺序存储：用二位数组charch[i][j]，其中i表示第几个元素，j表示该元素的第几个字母，而j的取值要不小于所有i个元素中字母最多的元素的字母个数2、链接存储：用单链表：structList{chardata[x];//x根据给定的字符串决定List*link;}排序时（比如更换a[n]与a[n+1]的位置）：Listtemp;temp=a[n];a[n-1]-link=a[n+1];//此时a[n+1]变成了a[n]temp-link=a[n+1];a[n]-link=temp;3、索引存储：用一个字符串charcdata[1000]把所有的数据储存。用一个字符指针数组char*cind[n]指向存储区域的一个数据结点.排序时，直接互换两个指针的指向内容。4、散列存储：voidSortAndSave::input(intnum){intarraysize;char*array;cinarraysize;array=newchar[arraysize];for(intj=0;jarraysize;j++){cinarray[j];}c[num]=array;}？？考虑了一个算法，不知道算不算散列：先开一个字符指针数组c[8]，然后每次开一个动态空间，再用指针指向这个空间的首地址……？？1.2有一个包括100个元素的数组，每个元素的值都是实数，请写出求最大元素的值及其位置的算法，讨论它所可能采取的存储结构。答：一、排序函数：voidtaxis(double*dnum)//参数是已经存放了数据的100个元素的数组{doublemax，maxp;//存放最大值和最大值的位置,inti;max=dnum[0];//把第一个数赋为最大值maxp=0;for(i=1;i100;i++){if(dnum[i]max){maxp=i;max=dnum[i];}}}算法规模为O(n),其中n为数组的元素个数。二、存储结构：1、顺序：一维数组dnum[100],节省空间。2、链表：structList{doublenum;List*link;}Lista[100];//建立数组voidlinking(){//联接链表…}doublemax，maxp;//存放最大值和最大值的位置,inti;max=a[0]-num;//把第一个数赋为最大值maxp=0;for(i=1;i100;i++){if(a[i]-nummax){maxp=i;max=a[i]-num;}}3、索引：建立一个index[100],每一个指针指向一个数，没有必要。4、散列：由于题目简单，用散列存储更加没有必要。1.3以学生每周的课程表为例，讨论它的数据结构，叙述其逻辑结构，存储结构、和相关运算等三个方面。答：一、逻辑结构：用线性结构。其中星期，节次，单双周都为线性关系。二、存储结构：用三维数组Lessonscourse[2][7][12].第一维表示单双周的不同课程，分为单周双周的前后关系；第二维表示一周不同星期的不同课程安排，分为从周一到周日的前后关系；第三维表示每天的12节不同课程，分为从第一节到第十二节的前后关系。整个储存为顺序结构其中每一个课程元素为一个结构structLessons，其中包含该课程的各种信息。三、相关运算：可以在课表的上增课，退课，查课，换课等功能。voidInsert(Lessonsadd,inti,intj,intk){add=course[i][j][k]}//增加课程Lessonsadd到course[i][j][k]voidDelete(inti,intj,intk);{course[i][j][k].exist=0}//删除课程course[i][j][k]//Boolexist为Lessons结构中的一个元素，表示课程是否存在，不存在为falsevoidView(inti,intj,intk){//…}//查课,输出所有关于course[i][j][k]的所有信息voidChange(inti1,intj1,intk1,inti2,intj2,intk2){Lessonstemp;temp=course[i1][j1][k1];course[i1][j1][k1]=course[i2][j2][k2];course[i2][j2][k2]=temp;}//换课，互换两个课程course[i1][j1][k1]，course[i2][j2][k2]的位置。