シーケンス表はスタックの基本操作を実現する.
4971 ワード
シーケンステーブルは、ストレージフォーマットとチェーンテーブルが同じレベルにあり、スタックなどの構造を実現するために使用できます.
一.手順表
1.シーケンステーブルの種類定義(静的)
2.シーケンステーブルの種類定義(ダイナミック)
二.手順表の基本操作
一.手順表
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
#include
#include
#include
#include
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
", e);
LocateElem(&L, 25, &e);// 25
printf("25 is Located:%d
", e);
DestoryList(&L);
}
三.シーケンス表はスタックの基本操作を実現する.#include
#include
#include
#include
#include
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("
Stack length:%d
", GetStackLen(&s));
ClearStack(&s);//
DestroyStack(&s);//
return 0;
}