数据结构(顺序表，单链表的经典算法题01）_通过一趟遍历找到链表中值最大的节点。

数据结构(顺序表，单链表经典算法题01)

单链表的基本操作代码实现
顺序表的基本操作代码实现

1、通过一趟遍历，确定长度为n的单链表中值最大的结点。

LNode * FindMaxNode(LinkList L)
{
   LNode *p=L->next;    //指向单链表中的第一个元素
   LNode *q;    //用来指定数值最大的结点
   ElemType temp=-100;    //用来记录最大值
    while (p!=NULL){
        if(p->data>temp){
            temp=p->data;
            q=p;
        }
        p=p->next;
    }
    q->data=temp;
    return q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、设计一个算法将链表中结点的链接方向全部逆转(要求算法的空间复杂度为O（1）—利用原表的存储空间)**

过程图解（参考）

操作过程：

• ① 初始化pNext至当前节点的下一个节点，为断链做准备
• ②判断下一个节点是否为NULL，若为NULL则为尾节点，即反转后的头指针pNewHead指向该节点
• ③ 反转当前节点
• ④ 当前节点反转完成后，准备下一轮反转操作，pPre前进至当前节点 ⑤ pNow前进一个节点

LinkList reverseList(LinkList L)
{
    LNode *pnow = L->next;
    LNode *ppre = NULL;
    LNode *pnext = NULL;
    //开始遍历链表，若链表为空，返回NULL
    while(NULL != pnow){
        //若当前指针非NULL，则将pnext初始化为当前节点的下一个
        pnext = pnow->next;
        //链表只有一个元素，无需执行翻转操作
        if(NULL == pnext){
            L->next = pnow;
        }
        //当前节点指向前一个节点ppre
        pnow->next = ppre;
        //前一个节点ppre向后移动一个节点
        ppre = pnow;
        //当前节点pnow向后移动一个节点
        pnow = pnext;
    }
    printf("Reverse done!\n");
    return L;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3、设计一个高效的算法，将顺序表L的所有元素置逆，要去空间复杂度为O(1)

算法思想：将数组A从两边进行交换

void reverse(SqList &L){
	ElemType temp;
	int i=0,;//实现从顺序表两边进行元素的交换 
	for(i;i<L.length/2;i++){
		temp=L.data[L.length-1-i];
		L.data[L.length-1-i]=L.data[i];
		L.data[i]=temp;
	}
}
void reverse(SqList &L,int low,int high){	//递归的实现
	if(low<high){
		swap(L.data[low],L.data[high]);
		reverse(&L,low+1,high-1);
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4、将两个有序的顺序表(单链表）合并成一个新的顺序表（单链表），并有函数返回结果顺序表（单链表）

顺序表

算法思想：将A数组和B数组进行比较，将小的元素复制到C数组中；若有比较完后一个数组有剩余的元素时，此时将该数组剩余的元素接到C数组中。

//将两个有序的顺序表合并 
int MergeSqList(SqList A,SqList B,SqList &C){	//取地址符是为了返回结果顺序表
	int i=0,j=0,k=0;
	if(A.length+B.length>C.length)
		return 0; //新数组的长度没有AB两个加起来长的时候，合并失败
	while(i<A.length&&j<B.length){	//只是单纯的比较，此时不涉及特殊情况 
		if(A.data[i]<B.data[j]){	//将A中的元素插入到C中 
			C.data[k]=A.data[i];
			i++;k++; 
		}
		else{
			C.data[k]=B.data[j];
			j++;k++;
		}
	} 
	/*特殊情况：当一个数组已经遍历结束，另外一个数组并没遍历结束，
	 			此时只需要将没有遍历完的数组直接接到C数组的后面 */
	 while(i<A.length){		//若A中的元素没有完时，将剩余元素接到C的后面 
	 	C.data[k]=A.data[i];
		 i++;k++; 
	 }
	 while(j<B.length){		//若B中的元素没有完时，将剩余元素接到C的后面 
	 	C.data[k]=B.data[j];
	 	k++;j++;
	 }
	 return 1 ;		//成功
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

单链表
算法思想：将A链表和B链表进行比较，将小的元素复制到C链表中；若有比较完后一个链表有剩余的元素时，此时将该链表剩余的元素接到C链表中。

//算法思想：将A链表和B链表进行比较，将小的元素复制到C链表中；若有比较完后一个链表有剩余的元素时，此时将该链表剩余的元素接到C链表中。**
void ListContact(LinkList La,LinkList Lb,LinkList &Lc){
	LNode la=La->next;
	LNode lb=Lb->next;
	LNode lc=Lc->next; 
	while(la!=NULL&&lb!=NULL)}{
		if(la->data>lb->data){	//将较小的结点的值给lc,并将它们的指针向后移动一个单位 
			lc->data=lb->data;
			lb=lb->next;
			lc=lc->next;
		}
		else{
			lc->data=la->data;
			la=la->next;
			lc=lc->next;
		}
		//特殊情况：当有一个链表以及扫描完成时，另一个个链表还没有到头的时候，将剩余结点的元素值交给lc
		if(la!=NULL){
			lc->data=la->data;
			la=la->next;
			lc=lc->next;
		} 
		if(lb!=NULL){
			lc->data=lb->data;
			lb=lb->next;
			lc=lc->next;
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

5、设计一个算法求整型数组A[n]的第k 个（1≤k≤n）最小元紊.

算法思想：利用快排，由于每趟快排之后都会有一个数值，左边小（相等）且右边大（相等），该元素就是第（下标+1小的元素）

完整过程参考

6、 在有序的顺序表中删除所有其值重复的元素，使表中的元素均不同。

有序—>重复的元素是在相邻位置的
算法思想：第一元素（不重复）依次向后扫描，不重复就保留，重复就不保留。
初始两个工作指针 i=0（保留不重复的元素）、j=1（遍历整个顺序表）

void Del_repeat(SqList &L)
{
	if(L.length==0)  return 0;	//删除失败 
	int i,j;
	for(i=0,j=1;j<L.length;j++){
		if(L.data[i]!=L.data[j]){	//不相同就把L.data[j]加入到前面已经不重复的序列 
			L.data[++i]=L.data[j];
		}
	}
	L.length=i+1;	//修改顺序表的长度(i是从0开始的） 
	return 1;		//删除成功 
}
1
2
3
4
5
6
7
8
9
10
11
12

7、在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，编写算法实现上述操作。

算法思想：
pre（前驱指针）、p（遍历链表）、q（指向当前找到的结点，用于删除）

• 指针初始化
• 遍历单链表；当p不为空时，
• 如果当前结点的值等于要删除的元素的值，那么修改指针的指向，释放结点；如果值不相等，则将pre指针和p指针向后移动一位。

void Del_x(LinkList L,ElemType x) {
	LNode *pre=L;
	LNode *q,*p=L->next;
	while(p){
		if(p->data==x){
			q=(LNode *)malloc(sizeof(LNode));	//每次释放之后在申请一个临时结点，以保证下次得删除正常执行
			q=p;		//q指向当前结点 
			p=p->next;	//p指针向后移动 
			pre->next=p;//pre指向p移动后的结点 
			free(q);	//删除q结点释放内存 
		}
		else{	//在不相等的情况下pre和p指针向后移动一位 
			pre=p;
			p=p->next;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

8、在顺序表中，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，更该算法删除线性表中所有值为x的元素

• 编写一个时间复杂度为O(n) -->只能变量一遍
• 空间复杂度为O(1)的算法–>申请常数个辅助空间

算法思想1：扫描顺序表记录其中x的个数（k）,将其中不为x的元素向前移动k个单位

void Del_AllX(SqList &L,ElemType x){
	int k=0;	//用来记录顺序表中元素值为x的个数
	for(int i=0;i<L.length;i++){		//第一次扫描用来记录x的个数 
		if(L.data[i]==x)
			k++;
		else{
			L.data[i-k]=L.data[i];		//
		}
	}
	L.length=L.length-k;	//修改删除后的顺序表的长度 

}
1
2
3
4
5
6
7
8
9
10
11
12

算法思想2：遍历顺序表，保留下不是x的值（删除所有的x）

void Del_AllX(SqList &L,ElemType x){
	int k=0;
	for(int i=0;i<L.length;i++){	
		if(L.data[i]!=x){
			L.data[k]=L.data[i];
			k++;	
		}
	}
	//和上面不同的是此时k保留的是除了x之外的元素个数
	L.length=k;	//修改顺序表的长度 
}
1
2
3
4
5
6
7
8
9
10
11

9、从顺序表中删除其值在给定值s与t之间(包含s和t,要求s <t)的所有元素，如或t不合理或顺序表为空，则显示出错信息并退出运行。(思想同8)

算法思想1：从头开始扫描，用k来统计数组中元素在当前范围内的元素个数，将不在范围内的元素直接向前移动k个单位

int Dels_t(SqList &L,ElemType s,ElemType t) {
	int k=0;	//用来记录顺序表中元素值在当前范围内的个数 
	if(L.length==0)	
	{
		printf("当前顺序表是空的");
		return 0;	//返回值为0表示顺序表是空的 
	} 
	if(s>=t) {
		printf("给出的范围不合理！");
		return 0;
	}
	for(int i=0;i<L.length;i++){
		if(L.data[i]<=t&&L.data[i]>=s){	//统计当前元素以及之前的顺序表的元素在s-t范围内的个数 
			k++;
		}
		else{
			L.data[i-k]=L.data[i];		//将不在范围内的元素，向前移动k个单位 
		}
	}
	 L.length=L.length-k;				//修改顺序表的长度
	 return 1;	//成功删除 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

*算法思想2：从头开始扫描，让不在范围内的元素重新组织到当前数组中

int Dels_t(SqList &L,ElemType s,ElemType t) {
		if(L.length==0)	
	{
		printf("当前顺序表是空的");
		return 0;	//返回值为0表示顺序表是空的 
	} 
	if(s>=t) {
		printf("给出的范围不合理！");
		return 0;
	}
	int k=0;
	for(int i=0;i<L.length;i++){	
		if(L.data[i]<s||L.data[i]>t){	//把不在范围s-t之间的元素直接重新组织到数组的头 
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;	//修改顺序表的长度 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

10、设计一个算法，删除递增有序链表中值大于mink小于maxk的所有元素(参考9,7）

算法思想：定义三个指针，pre（当前结点的前驱）、p（该结点）、q（用来支持删除操作）,然后遍历改链表，删除结点的值在范围内的结点

int  Delst(LinkList &L,ElemType mink,ElemType maxk) {
	LNode *p=L->next,*q,*pre=L;
	if(p==NULL){
		printf("链表为空！");
		return 0; 
	}
	while(p){
		if(p->data>mink&&p->data<maxk){	//结点的元素值在范围内的时候，将当前结点进行删除操作 
			q=p;
			p=p->next; 
			pre->next=p;	//前驱结点指向p 
			free(q);		//释放内存空间 
		}else{
			pre=p;
			p=p->next;
		}
	}
	return 1;		//删除成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

11、已知在一维数组A[m+n]中依次存放两个线性表 (al，a2，a3…，am)和 (b1，b2,b3…， bn)。试编写一个函数，将数组中两个顺序表的位置互换，即将(b1，b2,b3…bn)放在(a1，a2，a3…，am)的前面。

等价题目：

算法思想：首先将a序列逆序，然后将b序列逆序，最后将整体逆序（三次逆序）

第一步：al，a2，a3…，am----->am,am-1…,a2,a1
第二步：b1，b2,b3…， bn------->bm,bm-1…b2,b1
第三步：am,am-1…,a2,a1.bm,bm-1…b2,b1—>b1，b2,b3…bn.a1，a2，a3…，am

void reverse(SqList &L,int m,int n){	//将数组置为逆序 
	ElemType temp; 
	L.length=n-m+1;						//保证每次传入的参数为顺序表的长度 
	for(int i=0;i<L.length/2;i++){
		temp=L.data[L.length-1-i];
		L.data[L.length-1-i]=L.data[i];
		L.data[i]=temp;
	}
}
void change(SqList &L,int m,int n){	//三次逆序实现
	reverse(&L,0,m-1);	//将a序列逆序 
	reverse(&L,m,n-1);	//将b序列逆序 
	reverse(&L,0,n-1); 	//将逆序后的结果逆序 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14