Problem 1.
数组 Q[n] 用来表示一个循环队列, front 为队头元素的前一个位置, rear 为队尾元素的位置, 计算队列中元素个数的公式为 (rear-front+n)%n.
循环队列中, rear-front 的结果可能是负整数, 而对一个负整数求模, 其结果在不同的编译器环境中可能会有所不同.
Problem 2.
栈和队列的共同特点是只允许在端点插入和删除元素.
Problem 3.
一个 n*n 的对称矩阵, 按列优先进行压缩存储, 则其存储容量为 n*(n+1)/2.
对于对称矩阵, 行优先和列优先, 其存储容量是一样的, 1+2+...+n = n (n+1)/2.
Problem 4.
用链表表示线性表的优点是便于插入和删除, 用循环链表表示线性表的主要优点是从表中任何结点出发都能访问整个链表.
Problem 5.
对于由 n 个元素组成的线性表, 建立一个单链表的时间复杂度是 O(n).
Problem 6.
在一个单链表中, 已知 q 所指结点是 p 所指结点的直接前驱, 若在 q 和 p 之间插入 s 所指结点, 则需要执行下列操作: q->next=s; s->next=p;.
Problem 7.
已知一个栈的进栈序列是 1,2,3,...,n, 其输出序列是 p1,p2,...,pn, 若 p1=n, 则 pi 的值是 n-i+1 .
当 p1=n 时, 输出序列是唯一的, 即为 n,n-1,...,2,1, 则 p2=n-1,...,pn=1, 推断出 pi=n-i+1.
Problem 8.
设目标串为 s="abcabababaab", 模式串为 p="babab", 则 KMP 模式匹配算法的 next 数组为 {-1,0,0,1,2} .
next 数组只与模式串 p 有关, 计算过程如下表所示:
j | 0 | 1 | 2 | 3 | 4 |
p | b | a | b | a | b |
next[j] | -1 | 0 | 0 | 1 | 2 |
Problem 9.
在单链表中, 增加头结点的目的是方便运算的实现.
Problem 10.
算法分析的目的是分析算法的效率以求改进.
Problem 11.
给定一个链表, 判断链表是否存在环型链表.
如果链表有环, 那么在遍历链表时则会陷入死循环, 利用这个特征, 我们可以设计这样的算法.
1. 使用一个 slow 指针, 一个 fast 指针.
2. slow 指针一次往后遍历以 1 个节点, fast 指针一次往后遍历 2 个节点, 一直做这样的操作. 如果有环, 肯定 fast 先于或同时 slow 进入环, 进入后因为一快一慢, 又不能跳出循环, 所以有环二者一定相遇. 没环 fast->next=NULL 结束.
- struct link
- {
- int data;
- link *next;
- }
- bool isLoop(link * head)
- {
- //slow,fast 用于遍历链表
- link *slow=head,*fast=head;
- // 若链表长度 < 3, 则不是环型链表
- if(head==NULL||head->next==NULL)
- {
- return false;
- }
- // 否则链表长度 >=3, 遍历链表
- do{
- //slow 一次遍历 1 个节点
- slow=slow->next
- //fast 一次遍历 2 个节点
- fast=fast->next->next;
- // 遍历完链表或 slow 指针和 fast 指针相遇时退出循环
- }while(fast&&fast->next&&slow!=fast)
- // 若 slow 指针和 fast 指针相遇, 存在环
- if(slow==fast)
- return true;
- // 否则说明走到尾节点, 不存在环
- else
- return false;
- }
12. 已知单链表中各结点的元素值为整数且递增有序, 设计算法 "DeleteBetween" 删除链表中所有大于 mink 且小于 maxk 的元素, 并释放被删结点的存储空间.
因为是在有序单链表上的操作, 所以, 要充分利用其有序性.
在单链表中查找第一个大于 mink 的结点和第一个小于 maxk 的结点, 再将二者间的所有结点删除.
- DeleteBetween(Node<T> *first,int mink,int maxk)
- {
- p=first;
- // 遍历到最后一个小于 mink 的节点
- while(p->next!=NULL && p->next->data<=mink)
- p=p->next;
- // q 指向第一个大于 mink 的节点
- if(p->next!=NULL)
- q=p->next;
- // 如果 q->data 小于 mask, 对 q 进行摘链
- while(q!=NULL&&q->data<maxk)
- {
- u=q->next;
- p->next=u;
- delete q;
- q=u;
- }
- }
来源: http://www.bubuko.com/infodetail-3377387.html