首页 > 其他分享 >第2章-线性表习题

第2章-线性表习题

时间：2023-06-08 20:12:24浏览次数：26  
标签：LNode int next LinkList link 习题 NULL 线性表

P17

08

#include <stdio.h>
#include<iostream>
using namespace std;
void reverse(int a[],int n,int m,int size)
{
	for(int i=0;i<size;i++){
		a[i]=i+1;
	}
	for(int i=0;i<size;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	int temp[n];
	for(int i=0;i<n;i++)
	{
		temp[i]=a[i];
	}
	for(int j=n;j<size;j++){
		//TODO
		a[j-n]=a[j];
		//cout<<a[j]<<" ";
	}
	//cout<<endl;
	for(int k=m,i=0;k<size;k++)
		a[k]=temp[i++];
	for(int i=0;i<size;i++)
		cout<<a[i]<<" ";
}

int main(){
	int n=8;
	int m=9;
	int size=n+m;
	int a[size];
	reverse(a,n,m,size);
    return 0;
}

10(2010统考真题)

基本设计思想：

1.先用一个临时数组用来存储需要往后移的部分数据

2.再将P后面的数据往前移

3.最后将放在临时数组中的元素移动到原数组的后面

#include<iostream>
using namespace std;
void left_p(int a[],int p,int n)
{
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	int temp[p];
	for(int i=0;i<p;i++)//用另外一个数组暂存要往后移的数
	{
		temp[i]=a[i];
	}
	for(int j=p;j<n;j++)//p后面的数据前移
	{
		a[j-p]=a[j];
	}
	for(int k=n-p,i=0;k<n;k++)//将原来的p个数移到后面
	{
		a[k]=temp[i++];
	}
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}

int main(){
	int n,p;
	scanf("%d%d",&n,&p);
	int a[n];
	for(int i=0;i<n;i++)
	{
		a[i]=i+1;
	}
	left_p(a,p,n);
    return 0;
}

时间复杂度：O(n)

空间复杂度：O(p)?

11(2011统考真题)

基本思想：

1.先将两个数组进行按序合并

2.再找出中位数进行输出

#include<iostream>
using namespace std;
void search_z(int a[],int b[],int c[],int L)
{
	int i=0,j=0,k=0;
	while(i<L && j<L)//将两个数组进行按序合并
	{
		if(a[i]<b[j])
			c[k++]=a[i++];
		else
			c[k++]=b[j++];
	}
	while(i<L)
		c[k++]=a[i++];
	while(j<L)
		c[k++]=b[j++];
	for(int g=0;g<2*L;g++)//测试结果是否已按序排列
		cout<<c[g]<<" ";
	cout<<endl;
	int z=(2*L+1)/2;//生成中位数
	cout<<c[z-1];
}

int main(){
	int L=5;
	//scanf("%d",&L);
	int a[L]={11,13,15,17,19};
	int b[L]={2,4,6,8,20};
	int c[2*L];
	search_z(a,b,c,L);
    return 0;
}

时间复杂度O(n)

空间复杂度O(n)

12(2013统考真题)

基本思想：用一个变量来对出现的次数进行统计，再用另一个变量来统计出现最多的次数

用这个统计最多次数的变量与n/2进行比较来确定是不是主元素

每次统计最多次数的变量变化时，就将相应的元素记录下来，可以在后续进行输出

#include<iostream>
#include<algorithm>
using namespace std;
void main_elem(int a[],int n)
{
	sort(a,a+n);//这里排序算法还没学，暂时用sort来排序
	int max_count=0,max_elem=-1;//用max_count变量来记录出现最多的次数,max_elem记录出现次数最多的元素
	int count=1;
	for(int i=0;i<n;i++)
	{
		if(a[i+1]==a[i]) count++;//count统计出现次数
		else count=1;
		if(count>max_count)
		{
			max_count=count;
			max_elem=a[i];
			//count=1;
		}
	}
	for(int i=0;i<n;i++){
		//TODO
		cout<<a[i]<<" ";
	}
	cout<<endl;
	//cout<<max_count<<endl;
	if(max_count>n/2) cout<<max_elem;
	else cout<<-1;
}

int main()
{
	int n=8;
	int a[n]={0,5,5,3,5,7,5,5};//{0,5,5,3,5,1,5,7}
	main_elem(a,n);
    return 0;
}

时间复杂度O（n）

空间复杂度O（n）

13(2018统考真题)

基本思想：

新建一个数组，将原来数组中出现的值映射为新数组的下标，并将该下标位置的值赋为1

最后遍历新数组，值不为1就是未出现的最小整数

有一种特殊情况就是刚好完全映射，所以也要考虑到这种情况

#include<iostream>
#include<algorithm>
using namespace std;
void find_min(int a[],int n)
{
	int b[n];
	for(int i=1;i<=n;i++)//初始化新数组
	{
		b[i]=0;
	}
	for(int j=0;j<n;j++)//将原数组的值映射为新数组的下标
	{
		if(a[j]>0) b[a[j]]=1;
	}
	for(int i=1;i<=n+1;i++)
	{
		if(i==n+1)//刚好完全映射，输出n+1
		{
			cout<<n+1;
			return ;
		}
		if(b[i]==0) //输出最小正整数
		{
			cout<<i;
			return ;
		}
	}
}

int main()
{
	int n;
	cout<<"输入数组长度：";
	scanf("%d",&n);
	int a[n];
	cout<<"输入数组元素：";
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	find_min(a,n);
    return 0;
}

时间复杂度：O(n)

空间复杂度：O(n)----开辟了一个新的数组

14(2020统考真题)

基本思想：

三重for循环，暴力依次算出各个三元组的距离，然后输出最小的距离

#include<iostream>
#include<algorithm>
using namespace std;
void find_min(int a[],int an,int b[],int bn,int c[],int cn)
{
	int min=999999999;
	for(int i=0;i<an;i++)
	{
		for(int j=0;j<bn;j++)
		{
			for(int k=0;k<cn;k++)
			{
				int temp=abs(a[i]-b[j])+abs(b[j]-c[k])+abs(c[k]-a[i]);
				if(temp<min) min=temp;
			}
		}	
	}
	cout<<min;
}

int main()
{
	int an=3,bn=4,cn=4;
	int a[an]={-1,0,9};
	int b[bn]={-25,-10,10,11};
	int c[cn]={2,9,17,30,41};
	find_min(a,an,b,bn,c,cn);
    return 0;
}

时间复杂度O(n^3)

空间复杂度O(n)

P39

22(2009统考真题)

基本思想：

1.用两个指针p和q分别指向链表头结点的下一个结点

2.p指针先向后移动，当p指针到达k个位置时，q指针也开始向后扫描

3.设置一个变量count用来判断指针p是否已到达k的位置

4.如果count到达了k，说明能够找到倒数第k个值，返回1；否则说明链表长度小于k，查找失败，返回0

函数代码：

int search_k(LinkList list,int k)
{
	LNode *p=list->link,*q=list->link;//p,q都指向头结点的下一个结点
	int count=0;//count初始为0用来计数
	while(p!=NULL)
	{
		//TODO
		if(count<k)	count++;
		else q=q->link;//count到达k之后，p指针才开始向后移动
		p=p->link;//p从刚开始就一直向后移
 	}
 	if(count<k) return 0;//如果count的值没有到达k，说明链表长度小于k，查找失败
 	else
 	{
	 	cout<<q->data;
	 	return 1;
	}
	
}

完整代码：

#include<iostream>
using namespace std;
typedef struct LNode{
	int data;
	struct LNode* link;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL) return false;
	L->link=NULL;
	return true;
}
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false;
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL && j<i-1)
	{
		p=p->link;
		j++;
	}
	if(p==NULL)
	{
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->link=p->link;
	p->link=s;
	return true;
}
int search_k(LinkList list,int k)
{
	LNode *p=list->link,*q=list->link;
	int count=0;
	while(p!=NULL)
	{
		//TODO
		if(count<k)	count++;
		else q=q->link;
		p=p->link;
 	}
 	if(count<k) return 0;
 	else
 	{
	 	cout<<q->data;
	 	return 1;
	}
	
}
int main()
{
	LinkList L;
	InitList(L);
	for(int i=1;i<=7;i++)
	{
		ListInsert(L,i,i);
	}
	search_k(L,2);
    return 0;
}

23(2012统考真题)

基本思想：

1.定义两个指针分别指向两个单词所在单链表的头结点

2.计算两个单链表长度，让长的单链表的指针先行移动，直到两个指针所在的结点到表尾的长度相同

3.然后两个指针再开始同时移动，直到两个指针指向同一位置时停止，即共同后缀的起始位置

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*Linklist;
int length(LinkList L)
{
	int len=0;
	LNode *p=L;
	while(p->next!=NULL)
	{
		p=p->next;
		len++;
	}
	return len;
}
LNode* find_add(LinkList str1,LinkList str2)
{
	int m=length(str1);
	int n=length(str2);
	LNode *p=str1,*q=str2;
	for(;m>n;m--)
	{
		p=p->next;
	}
	for(;m<n;n--)
	{
		q=q->next;
	}
	while(p->next!=NULL && p->next!=q->next)
	{
		p=p->next;
		q=q->next;
	}
	return p->next;
}

时间复杂度：O(max(len1,len2))

24(2015统考真题)

基本思想：

采取空间换时间的思想，和之前一道题（p17的13(2018统考真题)）的想法差不多，就是将原链表中的值映射为一个新数组的下标，如果第一次出现，就把该下标对应的位置的值赋为1，如果不是第一次出现，就把该结点删除

void del_repeat(LinkList L,int n)
{
	LNode *p=L,*r;
	int *q,m;
	q=(int *)malloc(sizeof(int)*(n+1));//因为data的值不超过n，算上0就是n+1
	for(int i=0;i<=n;i++)//数组元素初值为0，初始化
	{
		*(q+i)=0;
	}
	while(p->link!=NULL)
	{
		m=p->link->data>0?p->link->data:-p->link->data;//避免使用abs函数，用一个三目运算符实现取反
		if(*(q+m)==0)//为0表示，该结点的值是第一次出现，然后赋值为1
		{
			*(q+m)=1;
			p=p->link;
		}
		else//如果不是第一次出现，就删除结点
		{
			r=p->link;
			p->link=r->link;
			free(r);
		}	
	}
	free(q);
}

时间复杂度O(m)

空间复杂度O(n)

完整试验代码：

#include<iostream>
using namespace std;
typedef struct LNode{
	int data;
	struct LNode* link;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL) return false;
	L->link=NULL;
	return true;
}
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false;
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL && j<i-1)
	{
		p=p->link;
		j++;
	}
	if(p==NULL)
	{
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->link=p->link;
	p->link=s;
	return true;
}
int length(LinkList L)
{
	int len=0;
	LNode *p=L;
	while(p->link!=NULL)
	{
		p=p->link;
		len++;
	}
	return len;
}
void ListTraver(LinkList L)
{
	LNode *p=L->link;
	while(p->link!=NULL)
	{
		cout<<p->data<<" ";
		p=p->link;
	}	
	cout<<p->data<<endl;
}
bool Del_node(LNode *p)
{
	if(p==NULL) return false;
	LNode *q=p->link;
	p->data=q->data;
	p->link=q->link;
	free(q);
	return true;
}
void del_repeat(LinkList L,int n)
{
	LNode *p=L,*r;
	int *q,m;
	q=(int *)malloc(sizeof(int)*(n+1));//因为data的值不超过n，算上0就是n+1
	for(int i=0;i<=n;i++)//数组元素初值为0，初始化
	{
		*(q+i)=0;
	}
	while(p->link!=NULL)
	{
		m=p->link->data>0?p->link->data:-p->link->data;//避免使用abs函数，用一个三目运算符实现取反
		if(*(q+m)==0)
		{
			*(q+m)=1;
			p=p->link;
		}
		else
		{
			r=p->link;
			p->link=r->link;
			free(r);
		}	
	}
	free(q);
}
int main()
{
	LinkList L;
	InitList(L);
	ListInsert(L,1,3);
	ListInsert(L,2,-3);
	ListInsert(L,3,4);
	ListInsert(L,4,5);
	ListInsert(L,5,-5);
	int n=5;
	ListTraver(L);
	del_repeat(L,n);
	ListTraver(L);	
//	cout<<length(L);
    return 0;
}

25(2019年统考真题)

基本思想：

1.先用两个指针p,q指向第一个结点（头结点的下一个结点），然后p每次移动一个位置，q移动两个位置，从而找到中间的位置

2.接着将后半部分的链表以头插法的形式进行逆置（相当于一个链表拆分成两个）

3.将后半部分的元素逐个插入到前半部分中

函数代码：

void change_list(LinkList L)
{
	LNode *p,*q,*r,*s;
	p=L,q=L;
	while(q->next!=NULL)//寻找中间结点
	{
		p=p->next;
		q=q->next;
		if(q->next!=NULL) q=q->next;//q每次走两步
	}
	q=p->next;
	p->next=NULL;
	while(q!=NULL)//单链表逆置，先插进去的会在后面
	{
		r=q->next;
		q->next=p->next;
		p->next=q;
		q=r;
	}
	s=L->next;//s指向单链表的第一个位置
	q=p->next;//p一直指向的都是中间位置没有变化
	p->next=NULL;
	while(q!=NULL)
	{
		r=q->next;
		q->next=s->next;	//将q插入到第一个结点的后面
		s->next=q;	
		s=q->next;	//s指向下一个插入点
		q=r;
	}
	
}

完整试验代码：

#include<iostream>
using namespace std;
typedef struct LNode{
	int data;
	struct LNode* next;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL) return false;
	L->next=NULL;
	return true;
}
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false;
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL && j<i-1)
	{
		p=p->next;
		j++;
	}
	if(p==NULL)
	{
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
int length(LinkList L)
{
	int len=0;
	LNode *p=L;
	while(p->next!=NULL)
	{
		p=p->next;
		len++;
	}
	return len;
}
void ListTraver(LinkList L)
{
	LNode *p=L->next;
	while(p->next!=NULL)
	{
		cout<<p->data<<" ";
		p=p->next;
	}	
	cout<<p->data<<endl;
}
//bool Del_node(LNode *p)
//{
//	if(p==NULL) return false;
//	LNode *q=p->next;
//	p->data=q->data;
//	p->next=q->next;
//	free(q);
//	return true;
//}
void del_repeat(LinkList L,int n)
{
	LNode *p=L,*r;
	int *q,m;
	q=(int *)malloc(sizeof(int)*(n+1));//因为data的值不超过n，算上0就是n+1
	for(int i=0;i<=n;i++)//数组元素初值为0，初始化
	{
		*(q+i)=0;
	}
	while(p->next!=NULL)
	{
		m=p->next->data>0?p->next->data:-p->next->data;//避免使用abs函数，用一个三目运算符实现取反
		if(*(q+m)==0)
		{
			*(q+m)=1;
			p=p->next;
		}
		else
		{
			r=p->next;
			p->next=r->next;
			free(r);
		}	
	}
	free(q);
}

LinkList Reverse(LinkList L)
{
	LNode *p,*r;
	p=L->next;
	L->next=NULL;
	while(p!=NULL)
	{
		r=p->next;
		p->next=L->next;
		L->next=p;
		p=r;
	}
	return L;
}
void change_list(LinkList L)
{
	LNode *p,*q,*r,*s;
	p=L,q=L;
	while(q->next!=NULL)//寻找中间结点
	{
		p=p->next;
		q=q->next;
		if(q->next!=NULL) q=q->next;//q每次走两步
	}
	q=p->next;
	p->next=NULL;
	while(q!=NULL)//单链表逆置，先插进去的会在后面
	{
		r=q->next;
		q->next=p->next;
		p->next=q;
		q=r;
	}
	s=L->next;//s指向单链表的第一个位置
	q=p->next;//p一直指向的都是中间位置没有变化
	p->next=NULL;
	while(q!=NULL)
	{
		r=q->next;
		q->next=s->next;	//将q插入到第一个结点的后面
		s->next=q;	
		s=q->next;	//s指向下一个插入点
		q=r;
	}
	
}
int main()
{
	LinkList L;
	InitList(L);
	int n=6;
	for(int i=1;i<=n;i++)
	{
		ListInsert(L,i,i);
	}
	ListTraver(L);
	change_list(L);
	ListTraver(L);
    return 0;
}

时间复杂度：O(n)

标签：LNode,int,next,LinkList,link,习题,NULL,线性表
From： https://www.cnblogs.com/Jinx8823/p/17467535.html

相关文章

  • Java面试题查缺补漏习题，锁的升级，动态代理
    之前我们总结了Java面试题目中的关于计算机网络，操作系统，以及JVM虚拟机，以及Java的相关特性。今天又看了很多面试的视频，对面试的题目进行一下仔细的补充。1.对称加密与非对称加密的区别：非对称加密和对称加密在加密和解密过程、加密解密速度、传输的安全性上都有所不同，具体介绍如下：......
  • 2022-2023期末复习题
    2022-2023期末复习题一、单选题1、世界上第一个分组交换网称为（C）。A、TCP/IP网B、局域网C、ARPAnetD、X.25网2、用路由器连接的地域广大的网络称为（A）。A、广域网B、互联网C、局域网D、城域网3、（B）属于通信子网设备。A、服务器B、通信处理机C、终端D、主机......
  • NEFU高级程序设计-期末复习习题组
    1.用链表实现单词序列倒序输出题目用链表实现单词序列倒序输出。与以往不同，请考虑采用一种完全的动态分配方式！为降低难度，“仁慈”的我已经给出了输出和释放的代码，你只要写出创建链表的creat函数定义就可以了。比如输入为：abcbcdcde则输出为：cdebcdabc见题干！你只能在代码输入......
  • 每日记录(线性表链式存储结构（链表）)
    链表的基本概念建议每次写的时候都加一个头节点各结点由两个域组成：数据域：存储元素数值数据指针域：存储直接后继结点的存储位置结点：数据元素的存储映像。由数据域和指针域两部分组成链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构单链表......
  • 每日记录(2.4线性表的应用)
    有序表的合并已知线性表La和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。La=(1,7,8)Lb=(2,4,6,8,10,11)Lc=(1,2,4,6,7,8,8,10,11)0.新建一个链表新建一个空表C，直接在A和B中每次选取最小值......
  • 每日记录(数据结构 第二章 线性表() )
     线性表的定义：存在唯一一个“第一个”元素存在唯一一个“最后一个”元素除第一个元素外，每一个元素都有且只有一个前驱除最后一个元素外，每个元素都有且只有一个后继一、线性表顺序存储结构（顺序表）0.线性表的基本概念线性表强调元素在逻辑上紧密相邻，所以首先想到用数组存储。但是......
  • 数据库习题一
    8.数据库管理系统的功能主要有哪些方面？有效地组织、存取和维护数据数据的定义功能数据的操纵功能数据库的事务管理和运行管理数据库的建立和维护功能9.调查业界常用的数据库管理系统软件，简要叙述其中1～2个产品的情况。Oracle；sqlServer；人大金仓kingbase；达梦DMsqlServ......
  • [学习笔记]数据结构_线性表_顺序表and单链表
    线性表线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面上的概念。线性表的基本操作boolInitList(&L)//初始化表，构造一个空的线性表intLength(L)//求表长。返回线性表L的长度，即L中数据元素的个数intLocateElem(L,e)//按......
  • 王道练训练营习题7.1
    /*题目：输入一个整型数,存入变量i,通过子函数change把主函数的变量i除2,然后打印i,,例如:如果输入的为10,打印出5,如果输入的是7,打印3*/#include<stdio.h>#pragmawarning(disable:4996)voidchange(int*j){ *j=*j/2;}intmain(){ while(1) { inti; scanf......
  • 线性表的顺序存储结构
    线性表的顺序存储结构标签（空格分隔）：DS线性表顺序存储1.线性表的顺序存储结构#defineMAXSIZE20//数组最大长度typedefstruct{ElemeTypedata[MAXSIZE];//数组顺序存储元素，data即为存储空间的起始位置intlength;//线性表当前长度:表中元素的个数length<=MAXSIZE}SqLi......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99