欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构:数组

程序员文章站 2024-02-24 15:13:58
...

数组 array
数组是可以在内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组的元素通过数组下标进行访问,数组下标从0开始。
优点:
1 按照索引查询元素速度快
2 按照索引遍历数组方便
缺点:
1 数组的大小固定后就无法扩容了
2 数组只能存储一种类型的数据
3 添加、删除的操作慢,因为要移动其他元素。
应用场景:
频繁查询,对于存储空间要求不大,很少增加和删除内存空间的情况。
下面给出一系列数据结构用数组实现的代码:

1 数组线性表的基本操作
2 数组栈的基本操作
3 数组队列的基本操作
4 数组串的基本操作

数组线性表的基本操作

#define ListSize 数字    				/*线性表的容量*/
typedef 类型 DataType;				/*元素类型定义*/

/*定义线性表数据结构*/
typedef struct
{
	DataType list[ListSize];			/*线性表数组成员*/
	int length;							/*线性表长度*/
}SeqList;	
						/*结构体名称*/
/*初始化线性表*/
void InitList(SeqList *L)    			
{
	L->length=0;					/*把线性表的长度置为0*/
}

/*判断线性表是否为空,线性表为空返回1,否则返回0*/
int ListEmpty(SeqList L)   
{
	if(L.length==0)					/*线性表的长度若为0*/
	{
		return 1;						/*返回1*/
	}
	else	
	{
		return 0;
	} 										/*否则返回0*/
}

/*查找线性表中第i个元素。查找成功将该值返回给e,并返回1表示成功;否则返回-1表示失败。*/
int GetElem(SeqList L,int i,DataType *e)   
{
	if(i<1||i>L.length)  			/*在查找第i个元素之前,判断该序号是否合法*/
	{
		return -1;
	}
	*e=L.list[i-1];					/*将第i个元素的值赋值给e*/
	return 1;
}
/*查找线性表中元素值为e的元素*/
int LocateElem(SeqList L,DataType e)   
{
	int i;
	for(i=0;i<L.length;i++)	 		/*从第一个元素开始与e进行比较*/
	{
		if(L.list[i]==e) 				/*若存在与e值相等的元素*/
		{
			return i+1;		    /*返回该元素在线性表中的序号*/
		}
	}
	return 0;						/*否则,返回0*/
}
/*在顺序表的第i个位置插入元素e,插入成功返回1,如果插入位置不合法返回-1,顺序表满返回0*/
int InsertList(SeqList *L,int i,DataType e)   
{
	int j;
	if(i<1||i>L->length+1)				/*在插入元素前,判断插入位置是否合法*/
	{
		printf("插入位置i不合法!\n");
		return -1;
	}
	else if(L->length>=ListSize)	/*在插入元素前,判断顺序表是否已经满,不能插入元素*/
	{
		printf("顺序表已满,不能插入元素。\n");
		return 0;
	}
	else
	{
		for(j=L->length;j>=i;j--)		/*将第i个位置以后的元素依次后移*/
		{
			L->list[j]=L->list[j-1];
		}
		L->list[i-1]=e;						/*插入元素到第i个位置*/
		L->length=L->length+1;		/*将顺序表长增1*/
		return 1;
	}
}
/*删除线性表中指定内容*/
int DeleteList(SeqList *L,int i,DataType *e)
{
	int j;
	if(L->length<=0)
	{
		printf("顺序表已空不能进行删除!\n");
		return 0;
	}
	else if(i<1||i>L->length)
	{
		printf("删除位置不合适!\n");
		return -1;
	}
	else
	{
		*e=L->list[i-1];
		for(j=i;j<=L->length-1;j++)
		{
			L->list[j-1]=L->list[j];
		}
		L->length=L->length-1;
		return 1;
	}
}
/*返回线性表长度*/
int ListLength(SeqList L)
{
	return L.length;
}
/*清空线性表中的数据*/
void ClearList(SeqList *L)
{
	L->length=0;
}

数组栈的基本操作

#define StackSize 数字					/*栈的容量*/    			
typedef 类型 DataType;					/*元素类型定义*/

typedef struct
{
	DataType stack[StackSize];
	int top;
}SeqStack;

/*初始化栈*/
void InitStack(SeqStack *S)    
{
	S->top=0;							/*把栈顶指针置为0*/
}
   
/*判断栈是否为空,栈为空返回1,否则返回0*/
int StackEmpty(SeqStack S)
{
	if(S.top==0)							/*如果栈顶指针top为0*/
	{	
		return 1;							/*返回1*/
  	}    
	else										/*否则*/
	{
		return 0; 							/*返回0*/
	}
}
  
/*取栈顶元素。将栈顶元素值返回给e,返回1表示成功,返回0表示失败。*/
int GetTop(SeqStack S, DataType *e) 
{
	if(S.top<=0)						/*如果栈为空*/
	{
		printf("栈已经空!\n");
		return 0;
	}
	else								/*否则*/
	{
		*e=S.stack[S.top-1];			/*在取栈顶元素*/
		return 1;
	}
}

/*将元素e进栈,元素进栈成功返回1,否则返回0.*/
int PushStack(SeqStack *S,DataType e)   
{
	if(S->top>=StackSize)				/*如果栈已满*/
	{
		printf("栈已满,不能将元素进栈!\n");
  		return 0;
	}
	else											/*否则*/
	{
		S->stack[S->top]=e;			/*元素e进栈*/
		S->top++;							/*修改栈顶指针*/
		return 1;
	}
}

/*出栈操作。将栈顶元素出栈,并将其赋值给e。出栈成功返回1,否则返回0*/
int PopStack(SeqStack *S,DataType *e)
{
	if(S->top==0)								/*如果栈为空*/
	{
		printf("栈中已经没有元素,不能进行出栈操作!\n");
		return 0;
	}
	else												/*否则*/
	{
		S->top--;									/*先修改栈顶指针,即出栈*/
		*e=S->stack[S->top];				/*将出栈元素赋给e*/
		return 1;
	}
}

/*求栈的长度*/
int StackLength(SeqStack S)
{
	return S.top;
}
    
/*清空栈*/
void ClearStack(SeqStack *S)
{
	S->top=0;									/*将栈顶指针置为0*/
}

数组队列的基本操作

#define  QueueSize  数字		/*队列的容量*/
typedef 类型 DataType;					/*元素类型定义*/

typedef struct Squeue{
	DataType queue[QueueSize];
	int front,rear; 		/*队头指针和队尾指针*/
}SeqQueue;
  
/*顺序循环队列的初始化*/
void InitQueue(SeqQueue *SCQ) 
{
    SCQ ->front=SCQ ->rear=0;	/*把队头指针和队尾指针同时置为0*/
}
 
/*判断顺序循环队列是否为空,队列为空返回1,否则返回0*/
int QueueEmpty(SeqQueue SCQ)   
{
	if(SCQ.front== SCQ.rear)		/*当顺序循环队列为空时*/
		return 1; 				/*返回1*/
	else						/*否则*/
		return 0; 				/*返回0*/
}

/*将元素e插入到顺序循环队列SQ中,插入成功返回1,否则返回0*/
int EnQueue(SeqQueue *SCQ,DataType e)
{
	if(SCQ->front== (SCQ->rear+1)%QueueSize)
	/*在插入新的元素之前,判断队尾指针是否到达数组的最大值,即是否上溢*/
		return 0;
	SCQ->queue[SCQ->rear]=e;		/*在队尾插入元素e */
	SCQ->rear=(SCQ->rear+1)%QueueSize;		/*队尾指针向后移动一个位置*/
	return 1;
}

/*将队头元素出队,并将该元素赋值给e,删除成功返回1,否则返回0*/
int DeQueue(SeqQueue *SCQ,DataType *e)
{
	if(SCQ->front==SCQ->rear)		/*在删除元素之前,判断顺序循环队列是否为空*/
		return 0;
	else
	{
		*e=SCQ->queue[SCQ->front];		/*将要删除的元素赋值给e*/
		SCQ->front=(SCQ->front+1)%QueueSize;		/*将队头指针向后移动一个位置,指向新的队头*/
		return 1;
	}
}

/*取队头元素,并将该元素赋值给e,取元素成功返回1,否则返回0*/
int GetHead (SeqQueue SCQ,DataType *e)
{
	if(SCQ.front==SCQ.rear)		/*在取队头元素之前,判断顺序循环队列是否为空*/
		return 0;
	else
	{
		*e=SCQ.queue[SCQ.front];	/*将队头元素赋值给e,取出队头元素*/
		return 1;
	}
}

/*清空队列*/
void ClearQueue(SeqQueue *SCQ) 
{
	SCQ->front=SCQ->rear=0;		/*将队头指针和队尾指针都置为0*/
}

数组串的基本操作

#define  MaxLen  数字					/*串的容量*/
typedef 类型 DataType;					/*元素类型定义*/

typedef struct
{
    char str[MaxLen];
    int length;
}SeqString;

/*串的赋值操作*/
void StrAssign(SeqString *S,char cstr[]) 
{
	int i=0;
	for(i=0;cstr[i]!='\0';i++)	/*将常量cstr中的字符赋值给串S*/
		S->str[i]=cstr[i];
	S->length=i;
}

/*判断串是否为空,串为空返回1,否则返回0*/
int StrEmpty(SeqString S)   
{
    if(S.length==0)			/*如果串的长度等于0*/
        return 1;			/*返回1*/
    else                    /*否则*/
        return 0;            /*返回0*/
}
/*求串的长度*/
int StrLength(SeqString S) 
{
	return S.length;
}
/*串的复制操作.*/
void StrCopy(SeqString *T,SeqString S) 
{
	int i;
	for(i=0;i<S.length;i++)		/*将串S的字符赋值给串T*/
		T->str[i]=S.str[i];
	T->length=S.length; 		/*将串S的长度赋值给串T*/
}
/*串的比较操作*/
int StrCompare(SeqString S,SeqString T)
{
	int i;
	for(i=0;i<S.length&&i<T.length;i++)	/*从第一个字符开始比较两个串中的字符*/
		if(S.str[i]!=T.str[i]) 			/*如果有不相等的字符*/
			return (S.str[i]-T.str[i]);      /*返回两个字符的差值*/
		return (S.length-T.length); 			/*如果比较完毕,返回两个串的长度的差值*/
}
/*串的插入。在S中第pos个位置插入T分为三种情况*/
int StrInsert(SeqString *S,int pos,SeqString T)
{
	int i;
	if(pos<0||pos-1>S->length) 		/*插入位置不正确,返回0*/
	{
		printf("插入位置不正确");
		return 0;
	}
	if(S->length+T.length<=MaxLen)/*第1种情况,插入子串后串长≤MaxLen,子串T完整地插入到串S中*/
	{
		/*在插入子串T前,将S中pos后的字符向后移动len个位置*/
		for(i=S->length+T.length-1;i>=pos+T.length-1;i--)
			S->str[i]=S->str[i-T.length];
		/*将串插入到S中*/
		for(i=0;i<T.length;i++)
			S->str[pos+i-1]=T.str[i];
		S->length=S->length+T.length;
		return 1;
	}
	/*第2种情况,子串可以完全插入到S中,但是S中的字符将会被截掉*/
	else if(pos+T.length<=MaxLen)
	{
		for(i=MaxLen-1;i>T.length+pos-1;i--)	/*将S中pos以后的字符整体移动到数组的最后*/
			S->str[i]=S->str[i-T.length];
		for(i=0;i<T.length;i++)					/*将T插入到S中*/
			S->str[i+pos-1]=T.str[i];
		S->length=MaxLen;
		return 0;
	}
	/*第3种情况,子串T不能被完全插入到S中,T中将会有字符被舍弃*/
	else
	{
		for(i=0;i<MaxLen-pos;i++)			/*将T直接插入到S中,插入之前不需要移动S中的字符*/
			S->str[i+pos-1]=T.str[i];
		S->length=MaxLen;
		return 0;
	}
}
/*在串S中删除pos开始的len个字符*/
int StrDelete(SeqString *S,int pos,int len)
{
	int i;
	if(pos<0||len<0||pos+len-1>S->length)		/*如果参数不合法,则返回0*/
	{
		printf("删除位置不正确,参数len不合法");
		return 0;
	}
	else
	{
		for(i=pos+len;i<=S->length-1;i++)		/*将串S的第pos个位置以后的len个字符覆盖掉*/
			S->str[i-len]=S->str[i];
		S->length=S->length-len; 				/*修改串S的长度*/
		return 1;
	}
}
/*将串S连接在串T的末尾*/
int StrConcat(SeqString *T,SeqString S)
{
	int i,flag;
	/*第1种情况,连接后的串长小于等于MaxLen,将S直接连接在串T末尾*/
	if(T->length+S.length<=MaxLen)
	{
		for(i=T->length;i<T->length+S.length;i++)	/*串S直接连接在T的末尾*/
			T->str[i]=S.str[i-T->length];
		T->length=T->length+S.length; 			/*修改串T的长度*/
		flag=1; 							/*修改标志,表示S完整连接到T中*/
	}
	/*第2种情况,连接后串长大于MaxLen,S部分被连接在串T末尾*/
	else if(T->length<MaxLen)
	{
		for(i=T->length;i<MaxLen;i++)			/*将串S部分连接在T的末尾*/
			T->str[i]=S.str[i-T->length];
		T->length=MaxLen; 				     /*修改串T的长度*/
		flag=0; 							/*修改标志,表示S部分被连接在T中*/
	}
	return flag;
}
/*清空串,只需要将串的长度置为0即可*/
void StrClear(SeqString *S) 
{
	S->length=0;
}