基本資料結構與演算法
（1）堆疊的基本操作
一.用陣列實作
//定義節點結構
#define MaxSize <陣列元素個數>
typedef struct sNode{
ElemType data[MaxSize];
int top;
}stack;
//創建堆疊
stack* createStack()
{
stack* s=(stack*)malloc(sizeof(stack));
s->top=-1;//陣列下標為-1時代表為空堆疊
return s;
}
//壓堆疊操作
void push (stack* ptrS,ElemType item)
{
if(ptrS->top==MaxSize-1)//陣列下表從零開始，故判斷MaxSize-1為堆疊滿情況
{
printf("堆疊已滿")；
return；
}
else
{
//先讓頭部指標向上移動，再添加資料元素
ptrS->data[++top]=item;
return;
}
}
//出堆疊
ElemType pop(stack* ptrS)
{
if(ptrS->top==-1)
{
printf("堆疊已空");
return NULL;
}
else
{
//取得資料后讓top向下移
return ptrS->data[ptrS->top--];
}
}
//判斷堆疊是否為空
bool isEmpty(stack* ptrS)
{
if(ptrS->top==-1)
return true;
else
return false;
}
//判斷堆疊是否已滿
bool isFull(stack* ptrS)
{
if(ptrS->top==MaxSize-1)
return true;
else
return false;
}
//求堆疊的深度
int Size(stack* ptrS)
{
return ptrS->top+1;//陣列從零開始，故需加一
}
//獲取堆疊頂元素
ElemType top(stack* ptrS)
{
if(ptrS->top==-1)//堆疊為空
{
return NULL;
}
return ptrS->data[top];
}
用陣列實作堆疊時由于要預先分配后好存盤空間，故在大多數時候會造成空間資源的浪費，因此為了提高空間利用率，采用兩個堆疊各自向中間延伸的方法，
#define MaxSize <資料最大存盤量>
typedef struct sNode
{
ElemType data[MaxSize];
int top1;
int top2;
}stack;
void initStack(stack* ptrS)
{
ptrS->top1=-1;
ptrS->top2=MaxSize;
}
void push(stack* ptrS,ElemType item,int tag)
{/*tag作為標志，取值為1時向第一個堆疊中加入資料，為2時向第二個堆疊中加入資料*/
if(ptrS->top2-ptrS->top1==1)
{
printf("堆疊已滿")；
return;
}
else if(tag==1)
{
//和單一堆疊的操作一致
ptrS->data[++ptrS->top1]=item;
}
else if(tag==2)
{
//和單一堆疊的操作一致
ptrS->data[++ptrS->top2]=item;
}
}
ElemType pop(stack* ptrS,int tag)
{
if(tag==1)
{
if(ptrS->top1==-1)
{
printf("堆疊1已空");
return NULL;
}
else
return ptrS->data[ptrS->top1--];
}
else
{
if(ptrS->top2==MaxSize)
{
printf("堆疊2已滿");
return NULL;
}
else
return ptrS->data[ptrS->top2--];
}
}
二.用鏈表實作
堆疊的鏈式存盤結構實際上是一個單鏈表，堆疊的入堆疊與出堆疊只能在鏈表的頭部進行，
//定義鏈表的堆疊節點
typedef struct sNode
{
ElemType Data;
sNode* next;
}stack;
/*構建一個鏈表頭指標*/
stack* createStack()
{
stack* s=(stack*)malloc(sizeof(stack));
s->next=NULL;
return s;
}
void push(stack* ptrS,ElemType item)
{
//創建新的節點
stack* tmp=(stack*)malloc(sizeof(stack));
tmp->Data=item;//將資料元素賦值給新節點的資料域
tmp->next=ptrS->next;//將新節點的指標域指向下一節點
ptrS->next=tmp;//將頭節點的指標域指向新節點
}
ElemType pop(stack* ptrS)
{
/*彈堆疊操作*/
ElemType elem;//存盤彈堆疊資料
stack* p=ptrS->next;//創建臨時指標指向彈堆疊節點
ptrS->next=p->next;//讓頭指標指向后一個節點
elem=p->Data;
free(p);//釋放掉出堆疊后元素對應的記憶體空間
return elem;
}
bool isEmpty(stack* ptrS)
{
/*判斷堆疊是否為空*/
if(ptrS->next==NULL)
return true;
else
return false;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226157.html
標籤：其他
上一篇：奧森版中國地圖