一、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度 算法如下:
LinkList Link( LinkList L1 , LinkList L2 ) {
//将两个单链表连接在一起 ListNode *p , *q p=L1; q=L2;
while ( p-next ) p=p-next; //查找终端结点
p-next = q-next //将L2的开始结点链接在L1之后 return L1 }
本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为： m+1=O(m)
二、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点指针，试编写算法在链表中删除指针s所指结点的前驱结点。
void Delprior ( Link s){ p = q = s;
while (p-next!=s){ q = p;
p = p-next; }
q-next = s; delete ( p); }
三、指出以下算法中的错误和低效之处，并把它改写为一个既正确又高效的算法。
Status DeleteK( SqList &a,int I, int k){ //本过程从顺序存储结构的线性表a中删除第I个元素起的k个元素。
if (I<1|| k<0|| I+k a.length) return ERROR; else {
for (count=1;count<k;count++){ //删除一个元素
for (j=a.Length; j =I+1;j--) a.elem[j-1] = a.elem[j]; a.length--; }
rreturn OK; }//DeleteK
更正：for (j = I+k; j <=a.Length; j++) a.elem[j-k] = a.elem[j]; a.Length = a.Length k;
四、假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也用三元组表示。
算法如下：
void transpose(smaxix A, smaxix B) {
int m,n,p,q,t,col;
//m为A中行数，n为A中列数，t为A中非0元素个数 //q为B的下一项位置，p为A的当前项 m=A[0][0];n=A[0][1];t=A[0][2];
B[0][0]=n;B[0][1]=m;B[0][2]=t;//产生第0行的结果 if(t0)//非0矩阵才做转置 {
q=1;
for(col=0;col<n;col++)//按列转置 for(p=1;p<=t;p++) if( A[p][1]==col) {
B[q][0]=A[p][1]; B[q][1]=A[p][0]; B[q][2]=A[p][2]; q++; } } }
五、假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也采用三元组。
void transpose(A,B) smatrik A,B;
{ int m,n,q,p,t,col; /*m为A中行数，n为A中的列数，t为A中非0元素个数*/
/*q为B的下一项位置，p为A的当前项*/
m=A[0][0]; n=A[0][1]; t=A[0][2]; B[0][0]=n; B[0][1]=m; B[0][2]=t; if (t0) { q=1;
for(col=0;col<n;col++) for(p=1;p<=t;p++)
if(A[p][1]==col) {
B[q][0]=A[p][1]；
B[q][1]=A[p][0]； B[q][2]=A[p][2]； q++; }
} }
六、设二维数组A5*6的每个元素占4个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a45的起始地址为多少？按行和按列优先存储时，a25的起始地址分别为多少？
解：A共占的字节数为：5*6*4=120
a45的起始地址为：Loc（a00）+（4*6+5）*4 =1000+116=1116
按行优先存储时，a25的起始地址为：Loc（a00）+（2*6+5）*4=1000+68=1068 按列优先存储时，a25的起始地址为：Loc（a00）+（5*5+2）*4=1000+108=10108 编写下列算法（假定下面所用的串均采用顺序存储方式，参数ch、ch1和ch2均为字符型）：
• 将串r中所有其值为ch1的字符换成ch2的字符。 • 将串r中所有字符按照相反的次序仍存放在r中。 • 从串r中删除其值等于ch的所有字符。
• 从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。 •
从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数和第（3）小题的删除子串的函数）。
答：
（1）本小题的算法思想是：从头到尾扫描r串，对于值为ch1的元素直接替换成ch2即可。 其函数如下：
orderstring *trans（r，ch1，ch2） orderstring *r； char ch1，ch2； {
int i；
for（i=0；i<r-len; i++）
if（r-vec[ i ]==ch1）r-vec[ i ]=ch2; return（r）； }
（2）本小题的算法思想是：将第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，如此下去，便将该串的所有字符反序了。其函数如下： orderstring *invert（r） orderstring *r； {
int i； char x；
for（i=0；i< ( r-len / 2 ); i++） {
x= r-vec[ i ];
r-vec[ i ]= r-vec[r-len-i-1]；
r-vec[ r-len-i-1 ]=x; }
return ( r ); }
（3）本小题的算法思想是：从头到尾扫描r串，对于其值为ch的元素采用移动的方式进行删除。其函数如下： orderstring *delall（r，ch） orderstring *r； char ch {
int i，j；
for（i=0；i<r-len; i++）
if（r-vec[ i ]==ch） {
for（j=i；j<r-len-1; j++）
r-vec[ j ]=r-vec[ j+1 ];
i--;
r-len--; }
return（r）； }
（4）本小题的算法思想是：从第index个元素开始扫描r1，当其元素值与r2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到r2结束为止，若都相同则返回，否则继续上述过程直到r1扫描完为止。其函数如下： int partposition（r2，r1，index） orderstring *r2，*r1； int index； {
int i，j，k；
for（i=index；i<r2-len; i++）
for（j=i，k=0；r2-vec[ j ]== r1-vec[ k ]; j++, k++） if（!r1-vec[ k+1 ]） return（i）；
return（-1）； }
（5）本小题的算法思想是：从位置1开始调用第（4）小题的函数
partposition( )，若找到了一个相同子串，则调用delsubstring( )将其删除，再查找后面位置的相同子串，方法与以上相同。其函数如下：
orderstring *delstringall（r，r3）
orderstring *r，*r3； {
int i=0，k；
while（i<r-len）/*当调用delsubstring( )进行删除操作时, r-len也减小了*/ {
if（（k=partposition（r, r3, i）!=-1））
r=delsubstring（r，k+1，r3-len）；
else i++； }
return r； }
版权声明
声明：有的资源均来自网络转载，版权归原作者所有，如有侵犯到您的权益
请联系本站我们将配合处理！