线性表

动态分配顺序存储结构

通过分析代码我们发现,要注意什么

//动态分配空间的顺序存储结构的线性表
#include<stdio.h>
#include<stdlib.h>

#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0

typedef int Status;
typedef int Elemtype;
typedef struct{
	Elemtype * elem;
	int length;
	int listsize;
}SqList;
void Show(SqList L)
{
	int i;
	for(i=0;i<L.length ;i++)
		printf("%d ",L.elem[i]);
	printf("n");
	return ;
}
Status Create(SqList &amp;L)
{
	L.elem = (Elemtype *)malloc(Linitesize*sizeof(Elemtype));
	if(!(L.elem ))
	return error;
	L.length = 0;
	L.listsize = Linitesize;
	return OK;
} 
//在第i个元素之前插入 ,从1开始计数,就是下标为i
Status Insert(SqList &amp;L,int i,Elemtype e)
{
	
	int j;
	if(i<1||i&gt;L.length+1 )
	return error;

	if(L.length&gt;=L.listsize)
	{
		L.elem =(Elemtype *)realloc(L.elem ,(L.listsize + Laddsize)*sizeof(Elemtype));
		if(!(L.elem ))
		return error;
		L.listsize = L.listsize + Laddsize;
	}
	
	for(j=L.length-1 ;j&gt;=i-1;j--)
		L.elem[j+1] = L.elem[j];
		
	L.elem[i-1] = e;
	L.length ++;
	return OK;
	
 } 
//i为你想要删除的第几个元素 
Status Delete(SqList &amp;L,int i,Elemtype &amp;e)
{
	int j;
	if(i<1||i&gt;L.length )
	return error;
	e = L.elem[i-1];
	
	for(j=i-1;j<L.length-1;j++)
		L.elem[j] = L.elem[j+1];
	L.length --;
	return OK;
}

int main()
{
	int i,j;
	Elemtype e;
	SqList L;

	Create(L);

	for(i=1;i<=5;i++)
		Insert(L,i,i*i);	
	printf("输出具体数据:n");
	Show(L);
	printf("请输入你想要删除第几个元素:n");
	scanf("%d",&amp;j);
	Delete(L,j,e);
	printf("删除数据是:%d n",e);
	Show(L);
	
	return 0;
}

 

考点

关键点,可以学到什么,就是分别用pa,pb,pc,来记录地址,一句话,就是用辅助变量来方便操作

void Merge(Sqlist la,Sqlist lb,Sqlist &amp;lc)
//目标,将原本有序递增的la,pb顺序整合lc ,lc认为有序递增的
{
	pa = la.elem;
	pb = la.elem;
	lc.listsize = lc.length = la.length + lb.length;
	pc =lc.elem = (ElemType *)malloc(lc.listsize*(sizeof(ElemType)));
	if(!lc.elem)
	exit OVERFLOW;
	pa_last = pa + la.length-1;
	pb_last = pb + lb.length-1;
	while(pa<=pa_last&amp;&amp;pb<=pb_last)
	{
		if(*pa<*pb) *pc++ = *pa++;
		else *pc++ = *pb++;
	}
	while(pa<=pa_last) *pc++ = *pa++;
	while(pb<=pb_last) *pc++ = *pb++;
	
}

顺序表优点与缺点

链式存储

在这里插入图片描述

//动态分配空间的顺序存储结构的线性表
#include<stdio.h>
#include<stdlib.h>

#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0

typedef int Status;
typedef int Elemtype;

typedef struct LNode{
	struct LNode * next;
	Elemtype data;
}LNode,*LinkList;
int Length(LinkList L)
{
	int sum=0;
	while(L->next !=NULL)
	{
		sum++;
		L=L->next ;
	}
	return sum;
}
//尾插法 
Status Create(LinkList &amp;L,Elemtype e)
{
	LinkList p = L;//开始p 指向结点 
	while(p->next !=NULL )//找到最后一个结点 
		p=p->next ;
		
	LinkList temp = (LNode *)malloc(sizeof(Elemtype));
	if(!temp) return error;
	temp->data = e;
	//由于p 指向最后一个结点,那么p->next 进行赋值,实际上会改变原来的数据
	
	temp->next = p->next ;
	p->next = temp;
	
	return OK;
	
}
Status Show(LinkList L)
{
	LinkList p = L->next  ;
	while(p !=NULL)
	{
		printf("%d ",p->data );
		p = p->next ;
	}
	printf("n");
	return OK;
}
//在第i 个元素之前插入 ,确保不超过范围 
Status Insert(LinkList &amp;L,int i,Elemtype e)
{
	if(i<1||i>Length(L)+1)
	return error;
	LinkList p = L;//指向结点
	//找到第i-1个结点
	int j ;
	for(j=1;j<i;j++)
		p = p->next ; 
	
	LinkList temp = (LNode * )malloc(sizeof(LNode));
	if(!temp) return error;
	temp->data = e;
	
	temp->next = p->next ;
	p->next = temp;
	return OK;
}
Status Delete(LinkList &amp;L,int i,Elemtype &amp;e)
{
	//删除第i 个元素,并返回其值
	 if(i<1||i>Length(L))
	 return error;
	 //找到第i-1个结点
	 int j;
	 LinkList temp = L;
	 for(j=1;j<i;j++)
	 	temp = temp->next ;
	 e = temp->next->data;
	 temp->next = temp->next->next;
	 
	 return OK;
}
int main()
{
	Elemtype e;
	LinkList L = (LNode *)malloc(sizeof(LNode));
	L->next = NULL;
	for(int i = 1;i<= 5;i++)
		Create(L,i);
	Show(L);
	Insert(L,2,10);
	Show(L);
	Delete(L,3,e);
	Show(L);
	printf("%d n",e);
	return 0;
	
	
}



 

应用

优点以及缺点

栈与队列

定义:只能在表尾进行插入与删除的线性表(先进后出)

  • 表尾是栈顶,表头是栈底

在这里插入图片描述

顺序

#include<stdio.h>
#include<stdlib.h>

#define initsize 100
#define addsize 50
#define OK 1
#define error 0

typedef int Status;
typedef int Elemtype;

typedef struct{
	Elemtype *base,*top;
	int stacksize;
}SqStack;
Status Init(SqStack &S)
{
	S.base =(Elemtype *)malloc(initsize*sizeof(Elemtype ));
	if(!S.base )
	return error;
	S.top = S.base ;//说明此时栈为空
	S.stacksize = initsize;
	return OK;
	 
}
Status Push(SqStack &S,Elemtype e)
{
	if(S.top -S.base >=S.stacksize )//栈满
	{
		S.base =(Elemtype *)realloc(S.base ,(initsize + addsize)*sizeof(Elemtype));
		if(!S.base)
		return error;
			
	}
	*(S.top ) = e;
	S.top ++;
	return OK;
}
Status Pop(SqStack &S,Elemtype &e)
{
	if(S.base == S.top )
	return error;//栈为空
	S.top --;
	e = *(S.top );
	return OK;
	 
}
int main()
{
	int n,i;
	Elemtype e;
	SqStack S;
	Init(S);
	printf("请输入你想要入栈的元素的个数:n");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		printf("请输入你要入栈的元素:");
		scanf("%d",&e);
		Push(S,e);
	}
	printf("出栈 n");
	for(i=1;i<=n;i++)
	{
		Pop(S,e);
		printf("%d ",e);
	}
	
	return 0;
}

链栈

在这里插入图片描述


#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define Error 0

typedef int Status;
typedef int Elemtype;

typedef struct Node {
	Elemtype data;
	struct Node * next;
}Node,*ListStack;

Status InitStack(ListStack &S)
{
	S =(ListStack )malloc(sizeof(Node));
	if(!S)  return Error;
	S->next = NULL ;
	return OK;
	
}
Status Pop(ListStack &S,Elemtype &e)
{
	if(S->next ==NULL)//栈为空
	return Error;
	ListStack p = S->next ;
	e = p->data  ;
	S->next = p->next ;
	free(p);
	return OK; 
}

Status Push(ListStack &S,Elemtype e)
{
	ListStack p =(ListStack )malloc(sizeof(Node));
	if(!p)	return Error;
	
	p->data = e;
	p->next = S->next ;
	S->next = p;
	return OK;
}

int main()
{
	ListStack S;
	Elemtype e;
	int i; 
	InitStack(S);
	printf("请输入想要进栈的6个数据:n");
	for(i=1;i<=6;i++)
	{
	scanf("%d",&e);
	Push(S,e);
	}
	printf("依次出栈:n");
	for(i=1;i<=6;i++)
	{
	Pop(S,e);
	printf("%d ",e);
	}
	return 0;
	
	
	
}

队列

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define Error 0

typedef int Status ;
typedef int Elemtype;

typedef struct QNode{
	Elemtype data ;
	struct QNode * next;
	
}QNode,*QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

Status InitQueue(LinkQueue &Q)
{
	QNode * p=(QNode *)malloc(sizeof(QNode));//头结点 
	if(!p)	return Error;
	p->next =NULL;  
	Q.front =Q.rear =p;
	return OK;
}
Status Push(LinkQueue &Q,Elemtype e)
{
	QNode * p=(QNode *)malloc(sizeof(QNode));
	if(!p)	 return Error;

	p->data =e;
	p->next = Q.rear ->next;
	Q.rear ->next = p;
	Q.rear = p ;
	return OK;
}
Status Pop(LinkQueue &Q,Elemtype &e)
{
	if(Q.front ==Q.rear )//队列为空
	return Error;
	QNode * p ;
	p = Q.front ->next;
	e = p->data;
	Q.front ->next = p->next ;
	if(Q.rear == p)
	Q.rear = Q.front ; 
	free(p);
	return OK;
}
int main()
{
	LinkQueue Q;
	Elemtype e;
	printf("创建带有头结点的链队列n");
	InitQueue(Q);
	printf("请输入5个你想要依次入队列的数字n");
	for(int i=1;i<=5;i++)
	{
		scanf("%d",&e);
		Push(Q,e);
	}
	printf("依次出队列n");
	for(int i=1;i<=5;i++)
	{
		Pop(Q,e);
		printf("%d ",e);
	}

	return 0;
	
}


原文地址:https://blog.csdn.net/weixin_74850661/article/details/134610275

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_22006.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注