昆凌做的广告买化妆品网站,北京建设学院网站,广州地铁运营最新消息,上海建筑工程公司排行榜第二章线性表
综合 一、在什么情况下用顺序表比用链表好 表长度确定#xff0c;很少进行插入删除操作且经常访问元素 二、2-4 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有 127 个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素…第二章线性表
综合 一、在什么情况下用顺序表比用链表好 表长度确定很少进行插入删除操作且经常访问元素 二、2-4 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有 127 个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素? 【解答】 若设顺序表中已有 n last1 个元素last 是顺序表的数据成员表明最 后表项的位置。又设插入或删除表中各个元素的概率相等则在插入时因有 n1 个插入位置(可以在表中最后一个表项后面追加)每个元素位置插入的概率为 1/(n1)但在删除时只能在已有 n 个表项范围内删除所以每个元素位置删除 的概率为 1/n。 插入时平均移动元素个数 AMN(Averagy Moving Number )为 127/2 删除时平均移动元素个数 AMN 为 126/2 算法设计 一、删除带头结点的有序链表中所有其值大于A且小于B的数据元素分析以下删除结点的特点下界A上界BA…B 思路主要分为三步 1、将p指针定位到第一个大于A的位置同时将pre指针定位到最后一个大于等于A的位置 2、将p指针定位到第一个大于等于B的位置 3、使用q指针和s指针将待删除数据free prel;pl-next;
While(pp-dataA){ prep;pp-next;}
if(p)
{
While(pp-dataB)pp-next;
qpre-next; pre-nextp;
While(q!p){sq;qq-next;free(s);}
} 二、链式存储结构的原地逆置 思路首先将首元素next指向NULL接下来每次都将q所指向的元素的next指向H-next并令H-next此元素 void ReverseList( LinkList L )
{// 将L 所指的带头结点的单链表逆置
if( L-next L-next-next){//当链表不是空表或单结点时pL-next;qp-next; p - nextNULL;//将开始结点变成终端结点while (q) {//每次循环将后一个结点变成开始结点pq; qq-next ; p-next L- next ;L-next p;}
}
}第四章串
注意定长顺序存储即将字符存于数组中且总下标1开始而0号单元存储长度
串的模式匹配子串的定位操作
int Index(SString S,SString T, int pos){
//返回子串T在主串S中第pos个字符之后的位置若不存在则函数值为0其中T非空(1≦pos≦StrlengthS。ipos; //指向串s的第pos个字符j1; //指向串t的第1个字符while((iS[0])(jT[0]){if(S[i]T[j]) { i; j; } //继续比较后继字符else {ii-j2; j1;} //串S指针回溯重新开始匹配}if(jT[0]) return i-T[0]; //匹配成功返回模式串t在串s中的起始位置else return 0; //匹配失败返回0
} //Index
第五章数组和广义表
综合 一、若在一维数组 B 中从 0 号位置开始存放则对称矩阵 A 中的任一元素aij 在只存下三角部分的情形下应存于一维数组 B 的什么下标位置给出计算 公式 答只存下三角部分时若 i j则数组元素 A[i][j]前面有 i-1 行1i-1)第 1 行 有 1 个元素第 2 行有 2 个元素第 i-1 行有 i-1 个元素。在第 i 行中第 j 号元素排在第 j-1 个元素位置因此数组元素 A[i][j]在数组 B 中的存放位置为1 2 … (i-1) j-1 ( i-1)*i / 2 j-1 若 i j数组元素 A[i][j]在数组 B 中没有存放可以找它的对称元素 A[j][i]。在数组 B 的第 (j-1)j / 2 i-1 位置中找到。之所以减一是因为从零开始存储 4二维数组A[10][20]采用列序为主方式存储每个元素占一个存储单元且A[0][0]的地址是200则A[6][12]的地址是 。 【答案】326 【解析】采用列主序时LOCA[6][12]LOCA[0][0]12106*1326 第六章树和二叉树 1、求树的深度 int Depth (BiTree T ){ // 返回二叉树的深度if ( !T ) depthval 0;else {depthLeft Depth( T-lchild );depthRight Depth( T-rchild );depthval 1 (depthLeft depthRight ?depthLeft : depthRight);} return depthval;
}2、 由先序ABC##DE#G##F###建树 BiTree CreatBinTree(){BiTree B;B (BiTree)malloc(sizeof(BiTNode));char c;scanf(%c,c);if(c ! #){B-data c;B-lchild CreatBinTree();B-rchild CreatBinTree();}else B NULL;return B;
}第七章图 迪杰斯特拉算法 第九章查找 折半查找非递归算法和递归算法 //非递归
int halfSearch(List list,int x){int low 1;//从一开始存储int high list.length;int mid;while(lowhigh){mid (low high)/2;if(x list[mid])return mid;else if(x list[mid])high mid;else low mid;}return 0;
}//递归
int halfSearch(int low,int high,int x){if(low high)return 0;int mid (low high)/2;if(x list[mid])return mid;else if(x list[mid])return halfSearch(low,mid,x);else return halfSearch(mid,high,x);return 0;
}索引顺序表 索引顺序表是一种性能介于顺序查找和折半查找之间的查找方法。在建立顺序表的同时建立一个索引 解释在0 ~ 5之间21为最大的数在5 ~ 10之间40最大在10以后78最大所以比如要查找33先和21、 40、 78比较3340且3321,所以在第二个区间顺序查找 第十章排序 简单选择排序 void SelectSort(SqList L){ for(i1;iL.length; i) {//进行n-1趟排序每趟选出1个最小记录//假定起始位置为最小记录的位置jSelectMinkey(L,i); //在L.r[i … n]中查找最小记录if(i!j) {temp L.r[i];L.r[i]L.r[j]; L.r[j] temp;}//交换记录若选出的是第i个则不进行交换}// SelectSort一趟快速排序 int Partition (SqList L, int low, int high) {L.r[0] L.r[low]; pivotkey L.r[low].key; //枢轴 while (lowhigh) {while(lowhighL.r[high].keypivotkey)--high;//从右向左搜索L.r[low] L.r[high];while(lowhigh L.r[low].keypivotkey)low;//从左向右搜索L.r[high] L.r[low];}
}// Partition 起泡排序
