1.顺序表
例1-1
已知长度为N的线性表A采用顺序存储结构。设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
解：以下两种方法都不满足要求：
- 如果没删除一个值为x的元素都要进行移动，其时间复杂度为O(n^2)，空间复杂度为O(1)；
- 如果借助一个新的顺序表，存放将A中所有不为x的元素，其时间复杂度为O(n)，空间复杂度为O(n)。
//解法一：设删除A中所有值等于x元素后的顺序表位A1,，显然A1包含在A中，为此A1重用A的空间
public void delonde1(SqList *&A,ElemType x){
int k=0,i; //k记录值不等于x的元素个数
for(i=0;i<arr.length;i++)
if(A->data[i]!=x){ //若当前元素不为x,将其插入A中
A->data[k] = A->data[i];
k++; //不等于x的元素增1
}
A.length=k; //顺序表A的长度等于k
}
//解法二：用k记录顺序表A中等于x的元素个数，一边扫描A以便统计k值
public void delonde1(SqList *&A,ElemType x){
int k=0,i=0; //k记录值不等于x的元素个数
while(i<A->length){
if(A->data[i]==x) k++; //当元素值为x时k增1
else A->data[i-k] = A->data[i]; //当前元素不为x时将其前移k个位置
i++;
}
A.length=k; //顺序表A的长度等于k
}
例1-2
设顺序表L有10个正整数。设计一个算法，以第一个元素为分界线，将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素后面。
//解法一：i从前向后找>pivot的元素，j从后向前找<=pivot的元素，两者交换
void move1(int[] arr) {
int i=0,j=arr.length-1,temp;
int pivot = arr[0];
while(i<j) {
//从后向前扫描，再找一个<=pivot的元素
while(i<j&&arr[j]>pivot)
j--;
while(i<j&&arr[i]<=pivot)
i++;
if(i<j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[0];
arr[0]=arr[j];
arr[j] = temp;
}
//解法二：j从后向前找下雨等于pivot的元素：前移；i从前向后找大于pivot的元素：后移。性能比方法一更好
void move2(int[] arr) {
int i=0,j=arr.length-1;
int pivot = arr[0];
while(i<j) {
//从后向前扫描，再找一个<=pivot的元素
while(i<j&&arr[j]>pivot)
j--;
arr[i]=arr[j];
while(i<j&&arr[i]<=pivot)
i++;
arr[j]=arr[i];
}
arr[j] = pivot;
}
2.单链表
例2-3
设计一个算法，删除一个单链表L中元素值最大的节点。
//定义两个指针pre和p同步向后移动，指针maxpre记录最大值的前驱,maxp记录最大值位置
void delmaxnode(LinkList *&L){
LinkList *p=L->next,*pre=L,*maxpre=pre,*maxp=p;
while(p!=NULL){
if(maxp->data < p->data){ //若找到一个更大的结点
maxp = p;
maxpre = pre;
}
pre = p;
p = p->next;
}
maxpre->next = maxxp->next; //删除*maxp节点
free(maxp); //释放*maxp节点
}
例2-4
有一个带头节点的单链表L，设计一个算法使其元素递增有序排列。
void sort(LinkList *&L){
LinkList *p,*pre,*p;
p=L->next->next; //P指向L的第2个数据节点
L->next->next=NULL; //构造只含一个数据节点的有序表
while(p!=NULL){
q=p->next; //q保存*p节点后继节点的指针
pre=L; //从有序表开头进行比较，pre指向插入*p的前驱节点
while(pre->next!=NULL && pre->next->data < p->data)
pre=pre->next; //在有序表中找插入*p的前驱节点*pre
p->next = pre->next;
pre->next = p;
p=q; //扫描单链表余下的结点
}
}
例2-5
假设有一个带头结点的单链表L={a1,a2,…,an}。设计一个算法将所有节点逆置。
//头插法
void Reverse(LinkList *&L){
LinkList *p = L->next,*p;
L->next = NULL;
while(p!=NULL){
q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
例2-6
假设有一个带头结点的单链表L={a1,b2,a2,v2,…,an,bn}。设计一个算法将其拆分成两个带头结点的单链表L1和L2: L1={a1,a2,…}，L2={b1,b2,…}，要求L1使用L的头结点
void split(LinkList *&L,LinkList *&L1,LinkList *&L2){
LinkeList *p = L->next,*p,*r1; //p指向第1个数据节点
L1 = L; //L1利用原来L的头结点
r1 = L1; //r1四种指向L1的尾节点
L2 = （LinkList *)malloc(sizeof(LinkList)); //创建L2的头结点
L2->next = NULL; //置L2的指针域为NULL
while(p!=NULL){
r1->next = p; //采用尾插法将*p插入L1中
r1 = p;
p = p->next; //p移向后一个节点
q = p->next; //用q保存*p的后继节点
p->next = L2->next; //采用头插法将*p插入L2中
L2->next = p;
p=q; //p重新指向 a i+1 的结点
}
r1->next = NULL; //尾节点next置空
}
练习：荷兰国旗问题
设有一个条块序列，每个条块为红(0)、白(1)、兰(2)三种颜色中的一种。假设该序列采用顺序表/单链表存储，设计一个时间复杂度为O(n)的算法，使得这些条块按红、白、兰的顺序排好，即排成荷兰国旗图案。
解1：用0~i表示0元素区间，k~n-1表示2元素区间，中间部分为1元素区间，用j从头开始扫描顺序表L中部的所有元素。
每一次循环：
- j指向元素1：说明它属于中部，保持不动，j++。
- j指向元素0：说明它属于前部，i增1（扩大0元素区间），将i、j位置的元素交换，j++。
- j指向元素2：说明它属于后部，k减1（扩大2元素区间），将j、k位置的元素交换，此时j位置的元素可能还要交换到前部，所以j不前进。
void move1(SqList *&L){
int i=-1,j=0,k=L->length;
while(j<k){
if(L->data[j]==0){
i++;
swap(L->data[i],L->data[j]);
j++
}else if(L->data[j]==2){
k--;
swap(L->data[k],L->data[j]);
}else j++;
}
}
解2：用p指针扫描节点，根据p->data值将该节点插入到3个单链表L、L1和L2（L1和L2不带头节点的）中，最后将它们连接起来。
void move2(LinkList *&L){
LinkList *L1,*L2,*r1,*r2,*p;
L1=NULL;
L2=NULL;
p=L->next;
r=L;
while(p!=NULL){
if(p->data==0){ //建立L带头节点的单链表
r->next=p;r=p;
}else if(p->data==1){ //建立L1不带头节点的单链表
if(L1==NULL) {L1=p;r1=p;}
else {r1->next=p;r1=p;}
}else{
if(L2==NULL) {L2=p;r2=p;}
else {r2->next=p;r2=p;}
}
p=p->next;
}
r->next=r1->next=r2->next=NULL;
r->next=L1;
r1->next=L2;
}
3.双链表
例3-1
有一个带头节点的双链表L，设计一个算法将其所有元素逆置，即第1个元素变成最后一个元素，第2个元素变成倒数第2个元素，…，最后一个元素编程第1个元素
void Reverse(DLinkList *&L){
DLinkList *p=L->next,*p; //p指向
L->next=NULL; //构造只有头节点的双链表L
while(p!=NULL){ //扫描L的数据节点
q=p->next; //用q保存其后继节点
p->next=L->next; //采用头插法将*p节点插入
if(L->next!=NULL) //修改其前驱指针
L-<next->prior=p;
L->next=p;
p->prior=L;
}
}
4.循环链表
例4-1
设计判断带头节点的循环双链表L（含两个以上的节点）是否对称相等的算法。
解：
- p从左向右扫描L，q从右向左扫描L
- 若对应数据节点的data域不相等，则退出小循环
- 否则继续比较，直到p与q相等或p的下一个节点为*q为止。
- 奇数情况和偶数情况有些不同
int Equal(DLinkList *L){
int same = 1;
DLinkList *p=L->next; //p指向第一个数据节点
DLinkList *q=L->prior; //q指向最后数据节点
while(same==1){
if(p->data!=q->data)
same=0;
else{
if(p==q || p==p->prior) break;
q=q->prior; //q前移
p=p->next; //p后移
}
}
return same;
}
5.有序表
例5-1
假设有两个有序表LA和LB。设计一个算法，将它们合并陈一个有序表LC。（归并算法）
//本算法的时间复杂度为O(m+n)，空间复杂度为O(m+n)
//采用顺序表存放有序表
void UnionList(SqList *LA,SqList *LB,SqlList *&LC){
int i=0,j=0,k=0; //i、j分别为LA、LB的下标，k为LC中元素个数
LC=(SqList *)malloc(sizeof(SqList)); //建立有序顺序表LC
while(i<LA->length && j<LB->length){
if(LA->data[i] < LB->data[j])
LC->data[k++] = LA->data[i++];
else LC->data[k++] = LB->data[j++];
}
while(i<LA->length)
LC->data[k++] = LA->data[i++];
while(j<LB->length){
LC->data[k++] = LB->data[j++];
}
LC->length = k;
}
例5-2
一个长度为L的升序序列S，处在L/2向上取整的位置的数成为S的中位数。找出两个等长序列的所有元素的中位数。
解：首先可以采用归并算法，将两个序列合并，然后去中位数即可。
因为只需要找n/2，所以可以定义两个下标分别指向两个数组，要来比较。
//算法的时间复杂度为O(n)，空间复杂度为O(1)
//n是等长序列的长度
int M_Search(int A[],int B[],int n){
int i,j,k;
i=j=k=0;
while(i<n && j<n){
k++;
if(A[i]<B[j]){
if(k==n) return A[i];
i++;
}else{
if(k==n) return B[j];
j++;
}
}
}
例5-3
假设一个有序表采用顺序表存储，设计一个高效算法删除重复的元素。
void deldupnode1(SqList *&L){
int k=1,i=0;
while(i<L->length-1){
if(L->data[i]!=L->data[i+1])
L->data[k++] = L->data[i++];
}
L->length=k;
}
例5-4
假设两个递增有序表采用单链表ha和hc存储。设计一个高效算法求它们的公共元素，将结果存放在单链表hc中。
void InterSect(LinkList *ha,LinkList *hb,LinkList *&hc){
LinkList *pa=ha->next,*pb=pb->next,*s,*r;
hc=(LinkeNode *)malloc(sizeof(LinkeNode));
r=hc;
while(pa!=NULL&&pb!=NULL){
if(pa->data < pb->data) pa=pa->next;
if(pa->data > pb->data) pb=pb->next;
if(pa->data == pb->data){
s==(LinkeNode *)malloc(sizeof(LinkeNode));
s->data = pa->data;
r->next = s; r = s;
pa = pa->data; pb = pb->next;
}
}
r->next=NULL;
}