数据结构 | 第二章线性表 WD课后算法编程题合集【C++ / 可实现】

2.2.3
对长度为n的顺序表编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
#include
using namespace std;

#define MAXSIZE 20
typedef int Elemtype;

typedef struct{
	Elemtype data[MAXSIZE]={5,2,0,1,3,1,4,1,1,4};
	int length=10;
}Sqlist;

void del(Sqlist &L,Elemtype x){
	int k=0;//顺序表不中等于x的元素个数 
	for(int i=0;i 
 
2.2.10 【2010统考真题】循环左移、逆置 
 
#include
using namespace std;

#define maxsize 20

void reverse(int R[],int l,int r){
	for(int i=l;i<(l+r)/2;i++){
		swap(R[i],R[(l+r)-i]);
	}
}

int main(){
	int n=7,p=3;
	int R[maxsize]={1,2,3,4,5,6,7};
	for(int i=0;i 
 
2.2.11 【2011统考真题】找中位数 
 
          向上取整 即 最后一个元素下表除以 2 
【思路】WD课后答案不琢磨了（两个序列各自求中位数），考试也想不到 ~ （全对满分） 
更容易想到：合并后求中位数（归并排序）。排序后判断的算法的时间复杂度是O(n)，空间复杂度是O(n).（扣2分）
类比归并排序，但不实现归并，仅按顺序访问，双指针思想。次优算法(不排序仅访问)的时间复杂度是O(n)，空间复杂度为O(1).（扣1分）
归并排序： 
#include
using namespace std;

#define maxsize 20

int midmerge(int s1[],int s2[],int a[],int n){//a[]为辅助数组 
	int i=0,j=0,k=0;
	while(i 
不排序仅访问： 
#include
using namespace std;

#define maxsize 20

int mid(int s1[],int s2[],int n){
	int i=0,j=0,k=(n*2)/2-1;
	while(k--)
	{
		if(s1[i] 
 
 2.2.12 【2013统考真题】主元素 
 
【思路】 
完美算法：答案所给策略非常完美 (时间复杂度o(n)，空间复杂度o(1))，但是难以想到。答案的思路是两两抵消。
再列举几种容易想到的算法： 
①构建一个大小为n的数组，用于对每个整数的计数，遍历一遍序列然后再遍历1次这个数组找最大值即可，参考代码见下。时间复杂度O(n)，空间复杂度O(n) —— 扣1分
②先对整个序列排序，然后再遍历一遍序列看哪个元素最多。使用o(n log2 n)的排序算法 —— 扣2分，使用o(n2)的排序算法——扣3分
#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;

#define maxsize 20

int find(int A[], int a[], int n) {
	for (int i = 0; i < n; i++) {
		a[A[i]]++;
	}
	for (int i = 1; i < n; i++) {
		if (a[i] > a[0]) a[0] = a[i];
	}
	if (a[0] <= n/2) return -1;
	else return a[0];
}

void print(int s[], int n) {
	for (int i = 0; i < n; i++)
		cout << s[i] << " ";
	cout << endl;
}
int main() {
	int n = 8;
	int a[maxsize] = { 0 };
	int A[maxsize] = { 0,5,4,3,5,7,5,5 };
	cout << find(A, a, n);
}
 
 
 2.2.13 【2018统考真题】 未出现的最小正整数 
 
【思路】 
标记数组
          时间复杂度o(n)，空间复杂度o(n)  
 
#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;

#define maxsize 20

int find(int A[], int a[], int n) {
	for (int i = 0; i < n; i++) {
		if (A[i] <= n && A[i] > 0) a[A[i]]++;//注意大于0的条件！
	}
	for (int i = 1; i <= n; i++) {
		if (0 == a[i]) return i;
	}
}

void print(int s[], int n) {
	for (int i = 0; i < n; i++)
		cout << s[i] << " ";
	cout << endl;
}
int main() {
	int n = 3;
	int a[maxsize] = { 0 };
	int A[maxsize] = { -1,2,3 };
	cout << find(A, a, n);
}
 
 
 2.2.14 【2020统考真题】 三元组最小距离 
 
【思路】 
保持三个下标索引 i,j,k，找出a[i],b[j],c[k]里最小的元素。
如果a[i]最小, 则下一次循环 i=i+1, 其他两个索引不变。
如果b[j]最小, 则下一次循环 j=j+1, 其他两个索引不变。
如果c[k]最小, 则下一次循环 k=k+1, 其他两个索引不变。
如此循环，直至最小的数对应的下标到达该数组尾部。记录最小距离。
 
          时间复杂度：O(n) （每次循环总有一个下标走了一步）  
          空间复杂度：O(1) 
#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;

#define maxsize 20
#define INT_MAX 0x7fffffff
bool compare(int a, int b, int c) {
	if (a <= b && a <= c)
		return true;
	return false;
}
int abs(int a) {
	if (a < 0) return -a;
	return a;
}
int minDistance(int a[], int b[], int c[],int n,int m,int p) {
	int dmin = INT_MAX;
	int i = 0, j = 0, k = 0,d;
	while (i < n && j < m && k < p && dmin>0) {
		d = abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k]);
		if (d < dmin) dmin = d;
		if (compare(a[i], b[j], c[k])) i++;
		else if (compare(b[j], a[i], c[k])) j++;
		else k++;
	}
	return dmin;
}

int main() {
	int a[3] = { -1,0,9 };
	int b[4] = { -25,-10,10,11 };
	int c[5] = { 2,9,17,30,41 };
	cout << minDistance(a,b,c,3,4,5);
}
 
 
 2.3.22 【2009统考真题】单链表 查找倒数第k个元素 
 
【思路】 
          设置两个指针，第二个指针在第一个指针的后k个位置上，当你第一个遍历指针到尾部时，第二个指针就是倒数第k个位置。 
 
          注意‘尽可能高效的算法’和‘在时间和空间两方面都尽可能高效的算法’是不一样的。 
          如果是后者，直接先遍历一遍算出来个数n，然后再遍历一次，到第n-k+1个元素即为所求。 
          此算法的时空复杂度与上述算法相同。但是本题要求不是时空复杂度，而是‘尽可能高效’，也就是考虑到常数的大小了。 
          评分标准：如果能一次遍历找出k，得满分15，超过一次遍历最高得10分 
【标准答案】 
          （1）算法的基本设计思想是∶定义两个指针变量p和g，初始时均指向头结点的下一个结点（链表的第一个结点）。p指针沿链表移动;当p指针移动到第k个结点时，q指针开始与p指针同步移动;当p指针移动到最后一个结点时，q 指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。 
          （2）算法的详细实现步骤（5分）：
 ①count=0，p和 q 指向链表表头结点的下一个结点;
 ②若p为空，转⑤;
 ③若count 等于k，则 q指向下一个结点;否则，count=count+1;
 ④ p指向下一个结点，转②;
 ⑤若 count 等于k，则查找成功，输出该结点的 data 域的值，返回 1;否则，说明 k 值超过了线性表的长度，查找失败，返回 0;
 ⑥算法结束。 
          （3）  
typedef int ElemType; //链表数据的类型定义
typedef struct LNode { //链表结点的结构定义
	ElemType data; //结点数据
	struct LNode *link; //结点链接指针
}*LinkList;
int Search_k(LinkList list, int k) {
	//查找链表list倒数第k个结点，并输出该结点data 域的值
	LinkList p = list->link,q = list->link;//指针p、q指示第一个结点
	int count = 0;
	while (p != NULL) { //遍历链表直到最后一个结点
		if (count < k) count++; //计数，若count < k只移动p
		else q = q->link; p = p->link; //之后让p、q同步移动
	}// while
	if (count < k)
		return 0; //查找失败返回 0
	else { //否则打印并返回1
		printf("%d", q->data);
		return 1;
	}
}//Search_k  
 代码实现： 
#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;

int n = 5;
int a[5] = { 5,4,3,2,1 };

typedef struct lnode {
	int data;
	lnode* next;
}*linklist;

void buildlist(linklist& L) {
	L = new lnode;
	linklist s, r = L;
	for (int i = 0; i < n; i++) {
		s = new lnode;
		s->data = a[i];
		r->next = s;
		r = r->next;
	}
	r->next = NULL;
}
int findk(linklist L,int k) {
	linklist p = L->next, q = L->next;
	int count = 0;
	while (NULL != p) {
		if (count < k) count++;
		else q = q->next;
		p = p->next;
	}
	if (count < k) return 0;
	cout << q->data;
	return 1;
}

int main() {
	linklist L;
	buildlist(L);
	findk(L, 3);
}
 
 
  2.3.23 【2012统考真题】找出单词相同后缀 
 
【思路】 
          注意一下题目的含义是现在这种结构已经存在了，让你去判断这个起始位置在哪。 
          而不是说给你两个单词序列，让你判断这个起始位置应该在哪。那么在已经存在的基础上，只要从尾向前寻找最靠前的相同结点即可。 
          也就是要寻找指针相同(地址相同)的最靠前结点。 
【答案】
 本题的结构体是单链表，釆用双指针法。用指针p、q分别扫描str1和str2，当p、q指向同一个地址时，即找到共同后缀的起始位置。 
1)算法的基本设计思想如下：
 ①分别求出str1和str2所指的两个链表的长度m和n。
 ②将两个链表以表尾对齐：令指针p、q分别指向strl和str2的头结点，若m>=n，则指针P先走，使p指向链表中的第m-n+1个结点；若m ③反复将指针p和q同步向后移动，当p、q指向同一位置时停止，即为共同后缀的其实位置，算法结束。
 2)本题代码如下： 
typedef struct Node {
	char data;
	struct Node* next;
}SNode;
/ 求链表长度的函数 /
int listlen(SNode head) {
	int len = 0;
	while (head->next != NULL) {
		len++;
		head = head->next;
	}
	return len;
}
/ 找出共同后缀的起始地址 /
SNode find_addr(SNode * strl, SNode * str2) {
	int m, n;
	SNode* p, * q;
	m = listlen(strl); //求 strl 的长度
	n = listlen(str2); //求 str2 的长度
	for (p = str1; m > n; m–) //若m>n，使p指向链表中的第m-n+1个结点
		p = p->next;
	for (q = str2; m < n; n–) //若mnext;
	while (p->next != NULL && p->next != q->next) {
		//将指针 p 和 q 同步向后移动
		p = p->next;
		q = q->next;
	}//while
	return p->next; //返回共同后缀的起始地址
} 
 【代码实现】 
#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;

typedef struct lnode {
	char data;
	lnode* next;
}*linklist;

int length(linklist L) {
	int n = 0;
	linklist p = L;
	while (NULL != p->next) {
		n++; p = p->next;
	}
	return n;
}

char findcommon(linklist st1, linklist st2){
	int n1 = length(st1), n2 = length(st2);
	linklist p1 = st1, p2 = st2;
	p1 = st1->next, p2 = st2->next;
	while (n2 > n1) {
		n2--;
		p2 = p2->next;
	}
	while (n1 > n2) {
		n1--;
		p1 = p1->next;
	}
	while (p1->data != p2->data) {
		p1 = p1->next; p2 = p2->next;
	}
	return p1->data;
}

void buildlist(linklist& L,char a[],int n) {
	L = new lnode;
	linklist s, r = L;
	for (int i = 0; i < n; i++) {
		s = new lnode;
		s->data = a[i];
		r->next = s;
		r = r->next;
	}
	r->next = NULL;
}

int main() {
	char a[7] = { 'l','o','a','d','i','n','g' };
	char b[5] = { 'b','e','i','n','g' };
	linklist L1, L2;
	buildlist(L1, a, 7);
	buildlist(L2, b, 5);
	cout << findcommon(L1, L2);
}
 
 
  2.3.24 【2015统考真题】删除单链表绝对值相等结点 
 
 时间复杂度为o(m)，空间复杂度为O(n) 
#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;

int a[22] = { 0 };

typedef struct lnode {
	int data;
	lnode* next;
}*linklist;

int abs(int a) {
	if (a < 0) return -a;
	return a;
}
void delcommon(linklist L) {
	linklist p = L,s;
	while (NULL != p->next) {
		s = p->next;
		if (a[abs(s->data)] == 1) {
			p->next = s->next;
			free(s);
		}
		else {
			a[abs(s->data)] = 1;
			p = p->next;
		}	
	}
}

void buildlist(linklist& L,int a[],int n) {
	L = new lnode;
	linklist s, r = L;
	for (int i = 0; i < n; i++) {
		s = new lnode;
		s->data = a[i];
		r->next = s;
		r = r->next;
	}
	r->next = NULL;
}
void printlist(linklist L) {
	linklist p = L;
	while (p->next != NULL) {
		p = p->next;
		cout << p->data << " ";
	}
}
int main() {
	int x[5] = { 21,-15,-15,-7,15 };
	linklist L;
	buildlist(L, x, 5);
	printlist(L);
	cout << endl;
	delcommon(L);
	printlist(L);
}
 
 
  2.3.25 【2019统考真题】带头结点单链表+穿插+逆置 
 
 
【思路】 
           为了达到穿插+逆置的效果，我们选择分段+逆置+插入
            先观察L=(a1,a2,a3,…an-2,an-1,an)和L’=(a1,an,a2,an-1,a3,an-2,…)
            发现L’是由L摘取第一个元素，再摘取倒数第一个元素…依次合并而成的。
            为了方便链表后半段取元素，需要先将L后半段原地逆置【题目要求空间复杂度为O1，不能借助栈】，否则每取最后一个结点都需要遍历一次链表。 
           1）先找出链表L的中间结点，利用速度差产生路程差法。
            先找出链表L的中间结点、郑此设置两个指针p和q，指针p每次走一步，指针q每次走两步，当指针q到达链尾时，指针p正好在链表的中自结点; 
           2）将L的后半段结点原地逆置
            需要变量：q的后继结点指针r,负责将“逆置指针”的工作 
           3）从单链表前后两段中依次取一个结点，按要求重排。
   
          第1步找中间结点的时间复杂度为O(n)，第2步逆置的时间复杂度为O(n)，第3步合并链表的时间复杂度为O(m)，所以该算法的时间复杂度为O(n)。 
void change_list(Node* L)
{
	Node* p, * q, * r, * s;//
	p = q = L;
	while (q->next != NULL)//寻找中间结点
	{
		p = p->next;//p走一步
		q = q->next;//q走一步
		if (q->next != NULL)
			q = q->next;//q再走一步
	}
	q = p->next;//此时p所指结点为中间结点，q为后半段链表的首结点
	p->next = NULL;//将前半段与后半段断开（分段）
	while (q != NULL)//开始将链表后半段逆置
	{
		r = q->next;//r为q的后继结点，在q反转指针的指向时需要防止断链
		q->next = p->next;//由于就近，利用刚好处于中间结点的p来帮助q反转指向
		p->next = q;//通过循环遍历让p（前半段最后一个元素，即中间结点）从指向后半段第一个结点逐步后移，最终指向后半段最后一个元素（表尾结点）
		q = r;//利用后驱指针r来防止q回不到后半链
	}
	s = L->next;//s为前半段链表的首结点（因为此时p作为中间结点指针需要为添加后半段指针做准备）
	q = p->next;//q为后半段指针
	p->next = NULL;//断开前半段链表
	while (q != NULL)
	{
		r = q->next;//r为后半段链表的后驱指针
		q->next = s->next;//将后半段链表的结点链接到前半段链表中
		s->next = q;//
		s = q->next;//s遍历（一次前进两个结点）
		q = r;//q遍历
	}
} 

                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！
数据结构 | 第二章 线性表 WD课后算法编程题合集【C++ / 可实现】

C/C++/C#相关栏目本月热门文章

数据结构 | 第二章线性表 WD课后算法编程题合集【C++ / 可实现】
