顺序表实现
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 = -1; return L; } /* 查找 */ #define ERROR -1 Position Find( List L, ElementType X ) { Position i = 0; 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-1) { /* 表空间已满,不能插入 */ printf("表满"); return false; } if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */ printf("位置不合法"); return false; } for( i=L->Last; i>=P; i-- ) L->Data[i+1] = 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<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */ printf("位置%d不存在元素", P ); return false; } for( i=P+1; i<=L->Last; i++ ) L->Data[i-1] = 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; } }链表
堆栈线性存储
1 typedef int Position; 2 struct SNode { 3 ElementType *Data; /* 存储元素的数组 */ 4 Position Top; /* 栈顶指针 */ 5 int MaxSize; /* 堆栈最大容量 */ 6 }; 7 typedef struct SNode *Stack; 8 9 Stack CreateStack( int MaxSize ) 10 { 11 Stack S = (Stack)malloc(sizeof(struct SNode)); 12 S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType)); 13 S->Top = -1; 14 S->MaxSize = MaxSize; 15 return S; 16 } 17 18 bool IsFull( Stack S ) 19 { 20 return (S->Top == S->MaxSize-1); 21 } 22 23 bool Push( Stack S, ElementType X ) 24 { 25 if ( IsFull(S) ) { 26 printf("堆栈满"); 27 return false; 28 } 29 else { 30 S->Data[++(S->Top)] = X; 31 return true; 32 } 33 } 34 35 bool IsEmpty( Stack S ) 36 { 37 return (S->Top == -1); 38 } 39 40 ElementType Pop( Stack S ) 41 { 42 if ( IsEmpty(S) ) { 43 printf("堆栈空"); 44 return ERROR; /* ERROR是ElementType的特殊值,标志错误 */ 45 } 46 else 47 return ( S->Data[(S->Top)--] ); 48 }堆栈线性存储
堆栈链式存储
1 typedef struct SNode *PtrToSNode; 2 struct SNode { 3 ElementType Data; 4 PtrToSNode Next; 5 }; 6 typedef PtrToSNode Stack; 7 8 Stack CreateStack( ) 9 { /* 构建一个堆栈的头结点,返回该结点指针 */ 10 Stack S; 11 12 S = (Stack)malloc(sizeof(struct SNode)); 13 S->Next = NULL; 14 return S; 15 } 16 17 bool IsEmpty ( Stack S ) 18 { /* 判断堆栈S是否为空,若是返回true;否则返回false */ 19 return ( S->Next == NULL ); 20 } 21 22 bool Push( Stack S, ElementType X ) 23 { /* 将元素X压入堆栈S */ 24 PtrToSNode TmpCell; 25 26 TmpCell = (PtrToSNode)malloc(sizeof(struct SNode)); 27 TmpCell->Data = X; 28 TmpCell->Next = S->Next; 29 S->Next = TmpCell; 30 return true; 31 } 32 33 ElementType Pop( Stack S ) 34 { /* 删除并返回堆栈S的栈顶元素 */ 35 PtrToSNode FirstCell; 36 ElementType TopElem; 37 38 if( IsEmpty(S) ) { 39 printf("堆栈空"); 40 return ERROR; 41 } 42 else { 43 FirstCell = S->Next; 44 TopElem = FirstCell->Data; 45 S->Next = FirstCell->Next; 46 free(FirstCell); 47 return TopElem; 48 } 49 }堆栈链式存储
队列线性存储
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 = 0; Q->MaxSize = MaxSize; return Q; } bool IsFull( Queue Q ) { return ((Q->Rear+1)%Q->MaxSize == Q->Front); } bool AddQ( Queue Q, ElementType X ) { if ( IsFull(Q) ) { printf("队列满"); return false; } else { Q->Rear = (Q->Rear+1)%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+1)%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