算法实现从顺序表中删除所有元素值介于x和y之间的所有元素且要求空间复杂度为O(1)

发表于 更新于 分类于 Waline：

题目1：设计一个高效的算法，从顺序表L中删除所有元素值介于x和y之间的所有元素，要求空间复杂度为O(1)，即算法最多只额外使用一个元素空间。函数原型如下所示：

int SListDelXY(SeqList *L,ElemType x,ElemType y)

完整程序实现如下： 

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define OK 1;
#define False 0;
typedef int ElemType;	//自定义线性表数据类型 
typedef struct	//定义线性表 
{
	ElemType elem[MAXSIZE];
	int last;
}SeqList;
void InitialSList(SeqList *L)	//初始化线性表 
{
	int i=0;
	printf("Please input int Xing numbers,and input -1 means endinput: \n");
	do {
		scanf("%d",&(L->elem[i]));
		i++;
	} while((L->elem[i-1])!=-1);
	L->last=i-1;
}
int SListDelXY(SeqList *L,ElemType x, ElemType y)	//函数实现删除线性表中元素值介于x和y之间的元素 
{
	if(L->last)	//判断单链表是否为空表 
	{
		int i;
		for(i=0;i<(L->last);i++)
		{
			if((L->elem[i])>x && (L->elem[i])<y)
			{
				int j;
				for(j=i;j<(L->last-1);j++)
					L->elem[j]=L->elem[j+1];
				i--;
				(L->last)--;
			}
		}
		return OK;
	}
	else
		return False;
}
void printSList(SeqList L)	//打印线性表 
{
	int i;
	for(i=0;i<(L.last);i++)
	{
		printf("%d ",L.elem[i]);
	}
	putchar('\n');
}
int main()
{
	SeqList a;
	InitialSList(&a);
	printf("Please input two numbers,and the first one < the next: \n");
	int x,y;
	scanf("%d %d",&x,&y);
	if(SListDelXY(&a,x,y))
		printSList(a);
	else
		printf("ERROR! \n");
	system("pause");
	return 0;
}

实现结果如图：

正确答案： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int SListDelXY(SeqList *L,ElemType x,ElemType y)
{
    int i,j;
    if(!L || x>y)	//判断L是否为空以及x,y取值是否合乎逻辑
    {
        puts("参数错误");
        return ERROR;
    }
    i=j=0;
    while(j<=(L->last))
    {
        if((L->elem[j])>=x && (L->elem[j])<=y)	//判断第j个元素是否在[x,y]区间内，若在，保持i不变，j继续向后推进
            j++;
        else	//若不在，则第i个元素就为第j个元素，i和j均向后推进
            L->elem[i++]=L->elem[j++];
    }
    L->last=i-1;//使不在[x,y]区间内的元素均在数组的前i-1个
    return OK;
}

题目2：已知顺序表L中的元素为int类型，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，将L中的奇数元素都排在前面，偶数元素都排在后面。函数原型如下所示：

int AdjustSqlist(SeqList *L)

完整程序实现如下： 

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define OK 1;
#define False 0;
//还需有待改进 
typedef int ElemType;	//自定义线性表数据类型 
typedef struct	//定义线性表 
{
	ElemType elem[MAXSIZE];
	int last;
}SeqList;
void InitialSList(SeqList *L)	//初始化线性表 
{
	int i=0;
	printf("Please input int Xing numbers,and input -1 means endinput: \n");
	do {
		scanf("%d",&(L->elem[i]));
		i++;
	} while((L->elem[i-1])!=-1);
	L->last=i-1;
}
int AdjustSList(SeqList *L)	//函数实现将线性表中的奇数元素排在前面，偶数元素排在后面 
{
	if(L->last)
	{
		int count=0,i;
		for(i=0;i<(L->last);i++)
		{
			if((L->elem[i])%2)
			{
				ElemType t=L->elem[i];
				L->elem[i]=L->elem[count];
				L->elem[count]=t;
				count++;
			}	
		}
		return OK;
	}
	else
		return False;
}
void printSList(SeqList L)	//打印线性表 
{
	int i;
	for(i=0;i<(L.last);i++)
	{
		printf("%d ",L.elem[i]);
	}
	putchar('\n');
}
int main()
{
	SeqList a;
	InitialSList(&a);
	if(AdjustSList(&a))
		printSList(a);
	else
		printf("ERRPR! \n");
	system("pause");
	return 0;
}

实现结果如图：

正确答案： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int AdjustSqlist(SeqList *L)
{
    int i=0,j;
    if(!L)	//判断顺序表是否为空
        return ERROR;  
    j=L->last;
    while(i<j)
    {
        while((L->elem[i])%2 != 0 && i<j)//从前往后找偶数
            i++;
        while((L0>elem[j])%2 == 0 && i<j)//从后往前找奇数
            j--;
        if(i<j)	//实现前面的的偶数与后面的奇数对调
        {
            int t=L->elem[i];
            L->elem[i]=L->elem[j];
            L->elem[j]=t;
        }
    }
    return OK;
}

题目3：已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析所编写算法的时间复杂度。函数原型如下所示：

int ListDelRange(LinkList L,int mink,int maxk)

完整程序实现如下： 

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define OK 1;
#define False 0;
//还需有待改进 
typedef int ElemType;	//自定义线性表数据类型 
typedef struct Node	//定义线性表为单链表 
{
	ElemType data;
	struct Node * next;
}Node, *LinkList;
void InitList(LinkList *L)	//初始化单链表 
{
	*L=(LinkList)malloc(sizeof(Node));
	(*L)->next=NULL;
}
void CFTail(LinkList L)	//使用尾插法建立单链表 
{
	Node *r,*s;
	int i=1;
	r=L;
	ElemType c;
	printf("Please input int Xing numbers,and input -1 means endinput: \n");
	do {
		scanf("%d",&c);
		if(c!=-1)
		{
			s=(Node *)malloc(sizeof(Node));
			s->data=c;
			r->next=s;
			r=s;
		}
		else
		{
			i=0;
			r->next=NULL;
		}
	} while(i);
}
int ListDelRange(LinkList L, int mink, int maxk)	//函数实现删除表中所有大于mink且小于maxk的元素 
{
	Node *r,*s;
	r=L;
	s=L;
	if(r->next!=NULL)	//判断是否为空表 
	{
		r=r->next;
		for(;r->next!=NULL;r=r->next)
		{
			if((r->data)>mink && (r->data)<maxk)
			{
				s->next=r->next;
				r=s;
			}
			else
				s=r;
		}
		if((r->data)>mink && (r->data)<maxk)
		{
			s->next=r->next;
		}
		return OK;
	}	
	else
		return False;
}
void printLList(LinkList L)	//打印单链表 
{
	Node *r;
	r=L->next;
	while(r->next!=NULL)
	{
		printf("%d ",r->data);
		r=r->next;
	}
	printf("%d ",r->data);
	putchar('\n');
}
int main()
{
	LinkList L;
	InitList(&L);
	CFTail(L);
	printf("Please input two numbers,and the first one < the next: \n");
	int mink,maxk;
	scanf("%d %d",&mink,&maxk);
	if(ListDelRange(L,mink,maxk))
		printLList(L);
	else
		printf("ERROR! \n");
	free(L);
	system("pause");
	return 0;
}

实现结果如图：

正确答案： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int ListDelRange(LinkList L,int mink,int maxk)
{
    Node *pre,*p;
    if(mink>=maxk || !L)	//判断[mink,maxk]区间是否合理以及L不为空表
        return ERROR;
    pre=L;	//pre指向头结点
    p=L->next;	//p指向首元结点
    while(p && (p->data)<maxk)	//p不指向NULL且p的数据域小于给定的最大数，前提是得非递减有序排列
    {
        if((p->data)>mink)	//p的数据域大于给定的最小数
        {//进行删除p指向的结点的操作
            pre->next=p->next;
            free(p);
            p=pre->next;
        }
        else	//p的数据域小于给定的最小数，向后推进
        {
            pre=pre->next;
            p=p->next;
        }
    }
    return OK;
}

题目4：假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，要求利用原A表和B表的节点空间存放表C(提示：用头插法)。函数原型如下所示：

LinkList MergeLinkListR(LinkList LA, LinkList LB)

完整程序实现如下： 

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define OK 1;
#define False 0;
//还需有待改进 
typedef int ElemType;	//自定义线性表数据类型 
typedef struct Node	//定义线性表为单链表 
{
	ElemType data;
	struct Node * next;
}Node, *LinkList;
void InitList(LinkList *L)	//初始化单链表 
{
	*L=(LinkList)malloc(sizeof(Node));
	(*L)->next=NULL;
}
void CFTail(LinkList L)	//使用尾插法建立单链表 
{
	Node *r,*s;
	int i=1;
	r=L;
	ElemType c;
	printf("Please input int Xing numbers,and input -1 means endinput: \n");
	do {
		scanf("%d",&c);
		if(c!=-1)
		{
			s=(Node *)malloc(sizeof(Node));
			s->data=c;
			r->next=s;
			r=s;
		}
		else
		{
			i=0;
			r->next=NULL;
		}
	} while(i);
}
LinkList  MergeLinkListR(LinkList LA, LinkList LB)	//使用头插法合并线性表 
{
	Node *r,*s,*t;
	LinkList LC;
	r=LA->next;
	s=LB->next;
	LC=LA;
	LC->next=NULL;
	for(;r!=NULL && s!=NULL;)
	{
		if((r->data)<(s->data))
		{
			t=(Node *)malloc(sizeof(Node));
			t->data=r->data;
			t->next=LC->next;
			LC->next=t;
			r=r->next;
		}
		else
		{
			t=(Node *)malloc(sizeof(Node));
			t->data=s->data;
			t->next=LC->next;
			LC->next=t;
			s=s->next;
		}
	}
	if(r)
	{
		for(;r!=NULL;)
		{
			t=(Node *)malloc(sizeof(Node));
			t->data=r->data;
			t->next=LC->next;
			LC->next=t;
			r=r->next;
		}
	}
	else
	{
		for(;s!=NULL;)
		{
			t=(Node *)malloc(sizeof(Node));
			t->data=s->data;
			t->next=LC->next;
			LC->next=t;
			s=s->next;
		}
	}
	return LC;
}
void printLList(LinkList L)	//打印单链表 
{
	Node *r;
	r=L->next;
	while(r->next!=NULL)
	{
		printf("%d ",r->data);
		r=r->next;
	}
	printf("%d ",r->data);
	putchar('\n');
}
int main()
{
	LinkList LA,LB;
	InitList(&LA);
	CFTail(LA);
	InitList(&LB);
	CFTail(LB);
	printLList(MergeLinkListR(LA,LB));
	system("pause");
	return 0;
}

实现结果如图：

正确答案： 

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
30
LinkList MergeLinkListR(LinkList LA,LinkList LB)
{
    Node *pa,*pb,*r;
    LinkList LC;
    if(!LA || !LB)//LA,LB均不能为空
        return ERROR;
    pa=LA->next;	//pa指向LA首元结点
    pb=LB->next;	//pb指向LB首元结点
    LC=LA;
    LC->next=NULL;
    while(pa!=NULL || pb!=NULL)//只要有一个不为空，循环继续
    {
        if(pa && (!pb || (pa->data)<(pb->data)))
        {
            r=pa->next;
            pa->next=LC->next;//pa指向的结点指向LC的首元结点
            LC->next=pa;//LC的首元结点为pa指向的结点
            pa=r;//pa指针向原LA的后续结点后移
        }
        else	//分析同上
        {
            r=pb->next;
            pb->next=LC->next;
            LC->next=pb;
            pb=r;
        }
        free(LB);
        return LC;
    }
}

题目5：假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点，函数原型如下所示：

int DelPrior(Node *s)

完整程序实现如下： 

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define OK 1;
#define False 0;
//还需有待改进 
typedef int ElemType;	//自定义线性表数据类型 
typedef struct Node	//定义线性表为单链表 
{
	ElemType data;
	struct Node * next;
}Node, *LinkList;

void InitCLinkList(LinkList *CL)	//初始化循环单链表 
{
	*CL=(LinkList)malloc(sizeof(Node));
	(*CL)->next=*CL;
}

void CCLinkList(LinkList CL)	//利用尾插法建立循环单链表 
{
	Node *r,*s;
	ElemType c;
	r=CL;
	printf("Please input int Xing numbers,and input -1 means endinput: \n");
	scanf("%d",&c);
	while(c!=-1) 
	{
		s=(Node *)malloc(sizeof(Node));
		s->data=c;
		r->next=s;
		r=s;
		scanf("%d",&c);
	}
	r->next=CL;
}

int DelPrior(Node *s)	//函数实现删除s所指节点的前驱节点 
{
	if(s)	//判断是否为空循环链表 
	{
		Node *r;
		r=s->next;
		for(;(r->next->next)!=s;)
			r=r->next;
		r->next=s;
		return OK;
	}
	else
		return False;
}

Node * FindNum(LinkList CL,ElemType c)	//函数实现寻找循环链表中指定数的指针 
{
	Node *r;
	r=CL;
	for(;(r->next)!=CL;)
	{
		r=r->next;
		if((r->data)!=c)
			continue;
		else
			break;
	}
	return r;
}

void printLList(LinkList CL)	//打印单链表 
{
	Node *r;
	r=CL->next;
	while((r->next)!=CL)
	{
		printf("%d ",r->data);
		r=r->next;
	}
	printf("%d ",r->data);
	putchar('\n');
}

int main()
{
	LinkList CL;
	InitCLinkList(&CL);
	CCLinkList(CL);
	printf("Please input the number's later number you want to delete: \n");
	ElemType c;
	scanf("%d",&c);
	if(DelPrior(FindNum(CL,c)))
		printLList(CL);
	else
		printf("ERROR! \n");
	system("pause");
	return 0;
}

实现结果如图：

正确答案： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int DelPrior(Node *s)
{
    Node *p,*pre;
    if(!s)	//判断s指向是否为空
        return ERROR;
    pre=s;
    p=s->next;
    if(p==s)	//只有一个结点，但已被约束不可能发生
        return ERROR;
    while((p->next)!=s)	//p先找到s的前驱
    {
        pre=pre->next;
        p=p->next;
    }
    pre->next=p->next;//使p的前驱指向p的后继
    free(p);
    return OK;
}

完！