数据结构与算法习题1
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 | 1 | 2 | 3 | 4 | |
p | b | a | b | a | b |
next[j] | -1 | 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;
}
}