顺序表实现

typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last;
};

/* 初始化 */
List MakeEmpty()
{
List L;

L = (List)malloc(sizeof(struct LNode));  
L->Last = -;

return L;  

}

/* 查找 */
#define ERROR -1

Position Find( List L, ElementType X )
{
Position i = ;

while( i <= L->Last && L->Data\[i\]!= X )  
    i++;  
if ( i > L->Last )  return ERROR; /\* 如果没找到，返回错误信息 \*/  
else  return i;  /\* 找到后返回的是存储位置 \*/  

}

/* 插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Insert( List L, ElementType X, Position P )
{ /* 在L的指定位置P前插入一个新元素X */
Position i;

if ( L->Last == MAXSIZE-) {  
    /\* 表空间已满，不能插入 \*/  
    printf("表满");  
    return false;  
}  
if ( P< || P>L->Last+ ) { /\* 检查插入位置的合法性 \*/  
    printf("位置不合法");  
    return false;  
}  
for( i=L->Last; i>=P; i-- )  
    L->Data\[i+\] = L->Data\[i\]; /\* 将位置P及以后的元素顺序向后移动 \*/  
L->Data\[P\] = X;  /\* 新元素插入 \*/  
L->Last++;       /\* Last仍指向最后元素 \*/  
return true;  

}

/* 删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Delete( List L, Position P )
{ /* 从L中删除指定位置P的元素 */
Position i;

if( P< || P>L->Last ) { /\* 检查空表及删除位置的合法性 \*/  
    printf("位置%d不存在元素", P );  
    return false;  
}  
for( i=P+; i<=L->Last; i++ )  
    L->Data\[i-\] = L->Data\[i\]; /\* 将位置P+1及以后的元素顺序向前移动 \*/  
L->Last--; /\* Last仍指向最后元素 \*/  
return true;  

}

顺序表

链表实现

typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

/* 查找 */
#define ERROR NULL

Position Find( List L, ElementType X )
{
Position p = L; /* p指向L的第1个结点 */

while ( p && p->Data!=X )  
    p = p->Next;

/\* 下列语句可以用 return p; 替换 \*/  
if ( p )  
    return p;  
else  
    return ERROR;  

}

/* 带头结点的插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */
bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */
Position tmp, pre;

/\* 查找P的前一个结点 \*/  
for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;  
if ( pre==NULL ) { /\* P所指的结点不在L中 \*/  
    printf("插入位置参数错误\\n");  
    return false;  
}  
else { /\* 找到了P的前一个结点pre \*/  
    /\* 在P前插入新结点 \*/  
    tmp = (Position)malloc(sizeof(struct LNode)); /\* 申请、填装结点 \*/  
    tmp->Data = X;  
    tmp->Next = P;  
    pre->Next = tmp;  
    return true;  
}  

}

/* 带头结点的删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */
bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */
Position tmp, pre;

/\* 查找P的前一个结点 \*/  
for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;  
if ( pre==NULL || P==NULL) { /\* P所指的结点不在L中 \*/  
    printf("删除位置参数错误\\n");  
    return false;  
}  
else { /\* 找到了P的前一个结点pre \*/  
    /\* 将P位置的结点删除 \*/  
    pre->Next = P->Next;  
    free(P);  
    return true;  
}  

}

链表

堆栈线性存储

typedef int Position;
struct SNode {
ElementType *Data; /* 存储元素的数组 */
Position Top; /* 栈顶指针 */
int MaxSize; /* 堆栈最大容量 */
};
typedef struct SNode *Stack;

Stack CreateStack( int MaxSize )
{
Stack S = (Stack)malloc(sizeof(struct SNode));
S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
S->Top = -;
S->MaxSize = MaxSize;
return S;
}

bool IsFull( Stack S )
{
return (S->Top == S->MaxSize-);
}

bool Push( Stack S, ElementType X )
{
if ( IsFull(S) ) {
printf("堆栈满");
return false;
}
else {
S->Data[++(S->Top)] = X;
return true;
}
}

bool IsEmpty( Stack S )
{
return (S->Top == -);
}

ElementType Pop( Stack S )
{
if ( IsEmpty(S) ) {
printf("堆栈空");
return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
}
else
return ( S->Data[(S->Top)--] );
}

堆栈线性存储

堆栈链式存储

typedef struct SNode *PtrToSNode;
struct SNode {
ElementType Data;
PtrToSNode Next;
};
typedef PtrToSNode Stack;

Stack CreateStack( )
{ /* 构建一个堆栈的头结点，返回该结点指针 */
Stack S;

 S = (Stack)malloc(sizeof(struct SNode));  
 S->Next = NULL;  
 return S;  

}

bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
return ( S->Next == NULL );
}

bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
PtrToSNode TmpCell;

 TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));  
 TmpCell->Data = X;  
 TmpCell->Next = S->Next;  
 S->Next = TmpCell;  
 return true;  

}

ElementType Pop( Stack S )
{ /* 删除并返回堆栈S的栈顶元素 */
PtrToSNode FirstCell;
ElementType TopElem;

 if( IsEmpty(S) ) {  
     printf("堆栈空");  
     return ERROR;  
 }  
 else {  
     FirstCell = S->Next;  
     TopElem = FirstCell->Data;  
     S->Next = FirstCell->Next;  
     free(FirstCell);  
     return TopElem;  
 }  

}

堆栈链式存储

队列线性存储

typedef int Position;
struct QNode {
ElementType *Data; /* 存储元素的数组 */
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue;

Queue CreateQueue( int MaxSize )
{
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->Front = Q->Rear = ;
Q->MaxSize = MaxSize;
return Q;
}

bool IsFull( Queue Q )
{
return ((Q->Rear+)%Q->MaxSize == Q->Front);
}

bool AddQ( Queue Q, ElementType X )
{
if ( IsFull(Q) ) {
printf("队列满");
return false;
}
else {
Q->Rear = (Q->Rear+)%Q->MaxSize;
Q->Data[Q->Rear] = X;
return true;
}
}

bool IsEmpty( Queue Q )
{
return (Q->Front == Q->Rear);
}

ElementType DeleteQ( Queue Q )
{
if ( IsEmpty(Q) ) {
printf("队列空");
return ERROR;
}
else {
Q->Front =(Q->Front+)%Q->MaxSize;
return Q->Data[Q->Front];
}
}

队列线性存储

队列链式存储

typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode Position;

struct QNode {
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue;

bool IsEmpty( Queue Q )
{
return ( Q->Front == NULL);
}

ElementType DeleteQ( Queue Q )
{
Position FrontCell;
ElementType FrontElem;

if  ( IsEmpty(Q) ) {  
    printf("队列空");  
    return ERROR;  
}  
else {  
    FrontCell = Q->Front;  
    if ( Q->Front == Q->Rear ) /\* 若队列只有一个元素 \*/  
        Q->Front = Q->Rear = NULL; /\* 删除后队列置为空 \*/  
    else  
        Q->Front = Q->Front->Next;  
    FrontElem = FrontCell->Data;

    free( FrontCell );  /\* 释放被删除结点空间  \*/  
    return  FrontElem;  
}  

}

队列链式存储

2019-07-27