北京大学数据结构与算法作业1及答案.doc

北京大学数据结构与算法作业(一)及答案1.1 设字符集为字母和数字的集合，字符的顺序为 A ， B ， C ，…， Z ， 0 ， l ， 2 ，…， 9 ，请将下列字符串按字典顺序排列并存储 PAB ， 5C ， PABC ， CXY ， CRSI ， 7 ， B899 ， B9 　并分析可以采取的存储方案 答：一、排序：因为这里的顺序是字母在前面，数字在后面，所以排序时不能直接使用strcmp函数直接完成，必须要自己完成int compare(char * ch1, char * ch2) //比较函数,比较前后两个单词的大小，如果第一{ 字符串小，就返回-1，反之返回1 for (i=0;i<1000;i++) //一个循环，逐个字符比较 { if ( * (ch1 + i)==’\0’) return -1; //第一个字符串先出现’\0’，一定小else if ( * (ch2 + i)==’\0’)return 1; //道理同上else if{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; else return 1; } 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') return 1; } }}设两个字符串最长的一个长度为n,则规模为O(n).for (int i = 1; i < 8; i++) //冒泡排序 for (int j = 0; j < 8-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、顺序存储：用二位数组char ch[i][j]，其中i表示第几个元素，j表示该元素的第几个字母，而j的取值要不小于所有i个元素中字母最多的元素的字母个数2、链接存储：用单链表：struct List{char data[x];//x根据给定的字符串决定List * link;}排序时（比如更换a[n]与a[n+1]的位置）：List temp;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、索引存储：用一个字符串char cdata[1000]把所有的数据储存。

用一个字符指针数组 char * cind[n]指向存储区域的一个数据结点.排序时，直接互换两个指针的指向内容 4、散列存储： void SortAndSave::input(int num){ int arraysize; char * array; cin >>arraysize; array=new char[arraysize]; for (int j=0;j>array[j]; } c[num]=array; } ？？考虑了一个算法，不知道算不算散列：先开一个字符指针数组c[8]，然后每次开一个动态空间，再用指针指向这个空间的首地址……？？1.2 有一个包括 100 个元素的数组，每个元素的值都是实数，请写出求最大元素的值及其位置的算法，讨论它所可能采取的存储结构 答：一、排序函数：void taxis(double * dnum) //参数是已经存放了数据的100个元素的数组 {double max， maxp; //存放最大值和最大值的位置,int i; max = dnum[0]; //把第一个数赋为最大值 maxp = 0; for (i = 1; i < 100; i++) { if (dnum[i] > max){maxp = i; max = dnum[i];} } } 算法规模为O(n),其中n为数组的元素个数。

二、存储结构：1、 顺序：一维数组dnum[100], 节省空间2、 链表：struct List{double num;List * link;}List a[100]; //建立数组void linking(){//联接链表…}double max， maxp; //存放最大值和最大值的位置,int i; max = a[0]->num; //把第一个数赋为最大值 maxp = 0; for (i = 1; i < 100; i++) { if (a[i]->num > max){maxp = i; max = a[i]->num;} }3、 索引：建立一个index[100],每一个指针指向一个数，没有必要4、 散列： 由于题目简单，用散列存储更加没有必要　1.3 以学生每周的课程表为例，讨论它的数据结构，叙述其逻辑结构，存储结构、和相关运算等三个方面 答：一、 逻辑结构：用线性结构其中星期，节次，单双周都为线性关系二、 存储结构：用三维数组Lessons course[2][7][12].第一维表示单双周的不同课程，分为单周双周的前后关系；第二维表示一周不同星期的不同课程安排，分为从周一到周日的前后关系；第三维表示每天的12节不同课程，分为从第一节到第十二节的前后关系。

整个储存为顺序结构其中每一个课程元素为一个结构struct Lessons，其中包含该课程的各种信息三、 相关运算：可以在课表的上增课，退课，查课，换课等功能 void Insert(Lessons add, int i, int j, int k){add=course[i][j][k]}//增加课程Lessons add到course[i][j][k] void Delete(int i, int j, int k);{course[i][j][k].exist=0} //删除课程course[i][j][k]//Bool exist为Lessons结构中的一个元素，表示课程是否存在，不存在为false void View(int i, int j, int k){//…}//查课,输出所有关于course[i][j][k]的所有信息 void Change(int i1, int j1, int k1, int i2, int j2, int k2) { Lessons temp; 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]的位置。