20、数据结构相关练习20210202

一、请简述栈区和堆区的区别。

1.栈区借助于栈的思想实现，“先进后出”，地址申请从大地址到小地址；堆区借助队列思想实现，“先进先出”，地址申请从小地址到大地址；

2.栈区的内存由计算机自动申请自动释放，堆区由程序员手动申请（malloc）手动释放（free）；

3.栈区大小一般在几M，堆区一般在几G；

4.由于栈区较小，可能会出现溢出情况（堆栈溢出），如递归调用较深时，计算机会不断在栈区申请内存。

5.栈区内存申请一般较连续，堆区容易出现片段化。

二、有一个整形数组：arr[ ]（数据值由外部输入决定），一个整数型变量：X（也是外部输入决定）要求：

1.删除数组中与x相等的元素

2.不得创建新数组

3.最多只允许使用单层循环

4.无需考虑超出新数组长度后面的元素，所以请返回新数组的长度。

如：{1,2,3,5,7,3,5,9}  x=3  则原数组的有效部分变为：{1,2,5,7,5,9 }。

代码：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#define MAXSIZE 8
typedef struct arr
{
	int data[MAXSIZE];
	int len;
}*pointer;
pointer create_arr()
{
	pointer p=(pointer)malloc(sizeof(struct arr));
	if(NULL==p)
		return NULL;
	memset(p->data,0,sizeof(p->data));
	p->len=0;
	return p;
}
void create(pointer p,int element)
{
	if(NULL==p||p->len==MAXSIZE)
	{	puts("fail or full");
		return;
	}
	p->data[p->len++]=element;
}
void delete_index(pointer p,int i)
{
	for(int j=i+1;j<p->len;j++)
	{
		p->data[j-1]=p->data[j];
	}
	p->len--;	
}
int delete_x(pointer p,int x)
{
	for(int i=0;i<p->len;i++)
	{
		if(x==p->data[i])
		{
			delete_index(p,i);
			i--;
		}
	}
	return p->len;
}
int main(int argc, const char *argv[])
{
	pointer p=create_arr();
	int element;
	for(int i=0;i<MAXSIZE;i++)
	{
	printf("please enter element %d :",i+1);
	scanf("%d",&element);
	create(p,element);
	}
	int x;
	printf("please enter delete x:");
	scanf("%d",&x);
	int l=delete_x(p,x);
	for(int i=0;i<l;i++)
	{
		printf("%d ",p->data[i]);
	}
	puts("");
	return 0;
}

运行结果：

三、请编程实现单链表的头插、头删、尾插、尾删。

代码：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
typedef struct node //定义链表节点结构体：数据域、指针域
{
	int data;
	struct node *next;
}*linklist;
linklist create_node()//创建新节点并初始化，返回节点地址
{
	linklist s=(linklist)malloc(sizeof(struct node));
	if(NULL==s)
		return NULL;
	s->data=0;
	s->next=NULL;
	return s;
}
linklist insert_head(linklist head,int element)
{
	linklist s=create_node();
	if(NULL==s)
	{
		puts("fail");
		return NULL;
	}
	s->data=element;
	if(NULL==head)
	{
		head=s;
		return head;
	}
	s->next=head;
	head=s;
	return head;
}
linklist insert_rear(linklist head,int element)
{
	linklist s=create_node();	
	if(NULL==s)
	{
		puts("fail");
		return NULL;
	}
	s->data=element;
	if(NULL==head)
	{
		head=s;
		return head;
	}
	linklist p=head;
	while(p->next)
		p=p->next;
	p->next=s;
	return head;
}
void output(linklist head)
{
	linklist p=head;
	while(p)
	{
	printf("%d ",p->data);
	p=p->next;
	}
	puts("");
}
linklist delete_head(linklist head)
{
	if(NULL==head)
	{
		puts("empty");
		return head;		
	}
	if(NULL==head->next)
	{
		free(head);
		return NULL;
	}
	linklist del=head;
	head=head->next;
	free(del);del=NULL;
	return head;
}
linklist delete_rear(linklist head)
{
	if(NULL==head)
	{
		puts("empty");
		return head;		
	}
	if(NULL==head->next)
	{
		free(head);
		return NULL;
	}
	linklist p=head;
	while(p->next->next)
		p=p->next;
	linklist del=p->next;
	p->next=NULL;
	free(del);del=NULL;
	return head;
}
int main(int argc, const char *argv[])
{
	linklist head=NULL;//定义单链表头指针并初始化
	int len;//根据终端输入的值确定单链表的长度
	printf("please enter the length of the linklist:");
	scanf("%d",&len);
	int element;
	for(int i=0;i<len;i++)//循环输入数值，头插或尾插创建链表
	{
		printf("%d element:",i+1);
		scanf("%d",&element);
//		head=insert_head(head,element);//头插
		head=insert_rear(head,element);//尾插
	}
	output(head);//遍历
 
	head=delete_head(head);//头删
	head=delete_head(head);
	output(head);
 
	head=delete_rear(head);//尾删
	output(head);
	return 0;
}

运行：