顺序表实现栈的基本操作

顺序表是一种存储格式与链表处于同一层次，可以用来实现一些结构，比如栈等。

一.顺序表

1.顺序表的类型定义（静态）

#define  LIST_MAX_SIZE  100   //空间初始大小
typedef int ElemType;    	 //元素的数据类型
typedef struct 
{
   ElemType elem[ LIST_MAX_SIZE ]; // 存储数组  
    int   length;                //当前元素个数
} SqList;
           

顺序表静态定义，假定 L 是一个类型 SqList 的顺序表，一般用 L.elem[i] 访问。表一旦装满，不能扩充。

2.顺序表的类型定义（动态）

typedef struct 
{
	ElemType *elem;//线性表存储基地址 
	ElemType *base;//线性表底 
	int listsize;//当前分配空间大小 
}SqList; 
           

或

typedef struct 
{
	ElemType *elem;//线性表存储基地址 
	int length;//长度
	int listsize;//当前分配空间大小 
}SqList; 
           

顺序表动态定义，可以扩充，新增的大小计入数据成员 listsize 中。操作时用指针来操作。

二.顺序表基本操作

/*静态顺序表就是用数组实现
动态顺序表是用指针代替数组，根据指针指向空间可以变化大小的性质实现动态的*/ 
#include <iostream>
#include <cstdio>
#include <cstring> 
#include <cstdlib>
#include <algorithm>
using namespace std;
const int LISTINITSIZE = 5;
const int LISTADDSIZE = 2;

typedef int ElemType;
typedef int Status;

int x[12] = {3, 41, 6, 1, 18, 25, 31};

typedef struct 
{
	ElemType *elem;//线性表存储基地址 
	ElemType *base;//线性表底 
	int listsize;//当前分配空间大小 
}SqList; 

void InitList(SqList *L)//初始化顺序表 
{
	L->base = (ElemType *)malloc(LISTINITSIZE*sizeof(ElemType));
	L->elem = L->base;
	L->listsize = LISTINITSIZE;
}

void CreateList(SqList *L, ElemType e)//创建顺序表 
{
	if(L->elem - L->base == L->listsize)//申请新的空间 
	{
		L->base = (ElemType *)realloc(L->base,(LISTADDSIZE+L->listsize)*sizeof(ElemType));
		L->elem = L->base + L->listsize;
		L->listsize = L->listsize + LISTADDSIZE; 
	}
	*(L->elem) = e;
	L->elem++;
}

void ListInsert(SqList *L, ElemType i, ElemType e)//插入 
{
	if(L->elem - L->base >= L->listsize)//申请新的空间 
	{
		L->base = (ElemType *)realloc(L->base,(LISTADDSIZE+L->listsize)*sizeof(ElemType)); 
		L->elem = L->base + L->listsize;
		L->listsize = L->listsize + LISTADDSIZE; 
	}
	ElemType *q = &(L->base[i-1]);
	ElemType *p;
	for(p = L->elem; p>=q; p--)
	{
		*(p+1) = *(p);
	}
	*q = e;
	L->elem++;
}

void LocateElem(SqList *L, ElemType a, ElemType *e)//定位 
{
	ElemType *p = L->base;
	ElemType *q = L->elem;
	for(int i = 0; p<=q; p++, i++)
	{
		if(*p == a)
		{
			(*e) = i+1;
			break;
		}
		
	}
}

void ListDelete(SqList *L, ElemType i, ElemType *e)//删除 
{
	ElemType *q = &(L->base[i-1]);
	(*e) = *q;
	ElemType *p = L->elem;
	for(; q<=p; q++)
	{
		*(q) = *(q+1);
	}
} 

void DestoryList(SqList *L)//销毁顺序表 
{
	free(L->base);
	L->elem = L->base = NULL;
	L->listsize = 0;
}

int main()
{
	SqList L;
	InitList(&L);
	for(int i = 0; i<7; i++)
	{
		CreateList(&L, x[i]);
	}
	ListInsert(&L, 2, 0);//在第二个元素前插入零 
	ElemType e;
	ListDelete(&L, 3, &e);//删掉第三个元素 
	printf("Delete Elem:%d\n", e);
	LocateElem(&L, 25, &e);//查看25是第几个元素 
	printf("25 is Located:%d\n", e);
	DestoryList(&L);
} 
           

三.顺序表实现栈的基本操作

#include <iostream>
#include <cstdio>
#include <cstring> 
#include <cstdlib>
#include <algorithm>
using namespace std;
const int STACKINITSIZE = 20;
const int STACKADDSIZE = 5;
 
typedef int ElemType;//元素类型，可以更改 
typedef int Status;//变量类型，可以更改为double等

typedef struct
{
	ElemType *top;
	ElemType *base;//base为一个指针，或者说为一个数组 
	int stackSize;//总留下的空间 
} sqStack;

void InitStack(sqStack *s)//初始化栈 
{
	s->base = (ElemType *)malloc(STACKINITSIZE*sizeof(ElemType));/****/ 
	//base数组大小 
	s->top = s->base;
	s->stackSize = STACKINITSIZE;
} 

void PushStack(sqStack *s, ElemType e)//压栈 
{
	if(s->top - s->base == s->stackSize)//空间大小不足时，扩展栈 
	{
		s->base = (ElemType *)realloc(s->base,(STACKADDSIZE+s->stackSize)*sizeof(ElemType)); 
	    //扩展原空间，在扩展空间比原空间打时数据不会改变
		s->top =  s->base + s->stackSize;
		s->stackSize = s->stackSize + STACKADDSIZE;
	}
	*(s->top) = e;/*e一定要赋到*(s->top)里面去******/
	s->top++;//数组指针++ 
}

void PopStack(sqStack *s, ElemType *e)//出栈 
{
	(*e) = *(--s->top);/*top向下移，把值赋进去 *******可以改变原函数中e*******/
} 

Status GetStackLen(sqStack *s)
{
	return s->top - s->base;//注意：地址指针相减，结果并不是地址差，而是实际元素的差值。
	//可以看成数组下标相减 
}

void ClearStack(sqStack *s)//清栈 
{
	s->top = s->base;
}

void DestroyStack(sqStack *s)//销毁栈 
{
	free(s->base);
	s->base = s->top = NULL;
	s->stackSize = 0; 
} 

int main()
{
	sqStack s;//是指向结构体的 
	char str[100];
	InitStack(&s);//初始化栈，先&s在函数中*s可以直接修改s ,任意一个元素也是 
	for(int i = 0; i<15; i++)
	{
		PushStack(&s, i);//压栈 
	} 
	ElemType e;
	for(int i = 0; i<10; i++)//弹出十个元素
	{
		PopStack(&s, &e);//会更改e 出栈 
		printf("%d, ", e); 
	}
	printf("\nStack length:%d\n", GetStackLen(&s)); 
	ClearStack(&s);//清栈 
	DestroyStack(&s);//销毁栈
	return 0; 
}