线性结构

线性结构的增删改查

1.顺序表 (C)

1 typedef int Position; 2 typedef struct LNode *List; 3 struct LNode { 4 ElementType Data[MAXSIZE]; 5 Position Last; 6 }; 7 8 /* 初始化 */ 9 List MakeEmpty() 10 { 11 List L; 12 13 L = (List)malloc(sizeof(struct LNode)); 14 L->Last = -1; 15 16 return L; 17 } 18 19 /* 查找 */ 20 #define ERROR -1 21 22 Position Find( List L, ElementType X ) 23 { 24 Position i = 0; 25 26 while( i <= L->Last && L->Data[i]!= X ) 27 i++; 28 if ( i > L->Last ) return ERROR; /* 如果没找到，返回错误信息 */ 29 else return i; /* 找到后返回的是存储位置 */ 30 } 31 32 /* 插入 */ 33 /*这里P是存储下标位置（从0开始）*/ 34 bool Insert( List L, ElementType X, Position P ) 35 { /* 在L的指定位置P前插入一个新元素X */ 36 Position i; 37 38 if ( L->Last == MAXSIZE-1) { 39 /* 表空间已满，不能插入 */ 40 printf("表满"); 41 return false; 42 } 43 if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */ 44 printf("位置不合法"); 45 return false; 46 } 47 for( i=L->Last; i>=P; i-- ) 48 L->Data[i+1] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */ 49 L->Data[P] = X; /* 新元素插入 */ 50 L->Last++; /* Last仍指向最后元素 */ 51 return true; 52 } 53 54 /* 删除 */ 55 /*这里P是存储下标位置（从0开始）*/ 56 bool Delete( List L, Position P ) 57 { /* 从L中删除指定位置P的元素 */ 58 Position i; 59 60 if( P<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */ 61 printf("位置%d不存在元素", P ); 62 return false; 63 } 64 for( i=P+1; i<=L->Last; i++ ) 65 L->Data[i-1] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */ 66 L->Last--; /* Last仍指向最后元素 */ 67 return true; 68 }

 

2.链表 (C)

1 typedef struct LNode *PtrToLNode; 2 struct LNode { 3 ElementType Data; 4 PtrToLNode Next; 5 }; 6 typedef PtrToLNode Position; 7 typedef PtrToLNode List; 8 9 /* 查找 */ 10 #define ERROR NULL 11 12 Position Find( List L, ElementType X ) 13 { 14 Position p = L; /* p指向L的第1个结点 */ 15 16 while ( p && p->Data!=X ) 17 p = p->Next; 18 19 /* 下列语句可以用 return p; 替换 */ 20 if ( p ) 21 return p; 22 else 23 return ERROR; 24 } 25 26 /* 带头结点的插入 */ 27 /*这里P是链表结点指针，在P之前插入新结点 */ 28 bool Insert( List L, ElementType X, Position P ) 29 { /* 这里默认L有头结点 */ 30 Position tmp, pre; 31 32 /* 查找P的前一个结点 */ 33 for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; 34 if ( pre==NULL ) { /* P所指的结点不在L中 */ 35 printf("插入位置参数错误\n"); 36 return false; 37 } 38 else { /* 找到了P的前一个结点pre */ 39 /* 在P前插入新结点 */ 40 tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */ 41 tmp->Data = X; 42 tmp->Next = P; 43 pre->Next = tmp; 44 return true; 45 } 46 } 47 48 /* 带头结点的删除 */ 49 /*这里P是拟删除结点指针 */ 50 bool Delete( List L, Position P ) 51 { /* 这里默认L有头结点 */ 52 Position tmp, pre; 53 54 /* 查找P的前一个结点 */ 55 for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; 56 if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */ 57 printf("删除位置参数错误\n"); 58 return false; 59 } 60 else { /* 找到了P的前一个结点pre */ 61 /* 将P位置的结点删除 */ 62 pre->Next = P->Next; 63 free(P); 64 return true; 65 } 66 }

 3.1堆栈 (数组实现)

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 }

3.2堆栈(链表实现)

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 }

 4.1队列(数组实现)

1 typedef int Position; 2 struct QNode { 3 ElementType *Data; /* 存储元素的数组 */ 4 Position Front, Rear; /* 队列的头、尾指针 */ 5 int MaxSize; /* 队列最大容量 */ 6 }; 7 typedef struct QNode *Queue; 8 9 Queue CreateQueue( int MaxSize ) 10 { 11 Queue Q = (Queue)malloc(sizeof(struct QNode)); 12 Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType)); 13 Q->Front = Q->Rear = 0; 14 Q->MaxSize = MaxSize; 15 return Q; 16 } 17 18 bool IsFull( Queue Q ) 19 { 20 return ((Q->Rear+1)%Q->MaxSize == Q->Front); 21 } 22 23 bool AddQ( Queue Q, ElementType X ) 24 { 25 if ( IsFull(Q) ) { 26 printf("队列满"); 27 return false; 28 } 29 else { 30 Q->Rear = (Q->Rear+1)%Q->MaxSize; 31 Q->Data[Q->Rear] = X; 32 return true; 33 } 34 } 35 36 bool IsEmpty( Queue Q ) 37 { 38 return (Q->Front == Q->Rear); 39 } 40 41 ElementType DeleteQ( Queue Q ) 42 { 43 if ( IsEmpty(Q) ) { 44 printf("队列空"); 45 return ERROR; 46 } 47 else { 48 Q->Front =(Q->Front+1)%Q->MaxSize; 49 return Q->Data[Q->Front]; 50 } 51 }

4.2队列(链表实现)

1 typedef struct Node *PtrToNode; 2 struct Node { /* 队列中的结点 */ 3 ElementType Data; 4 PtrToNode Next; 5 }; 6 typedef PtrToNode Position; 7 8 struct QNode { 9 Position Front, Rear; /* 队列的头、尾指针 */ 10 int MaxSize; /* 队列最大容量 */ 11 }; 12 typedef struct QNode *Queue; 13 14 bool IsEmpty( Queue Q ) 15 { 16 return ( Q->Front == NULL); 17 } 18 19 ElementType DeleteQ( Queue Q ) 20 { 21 Position FrontCell; 22 ElementType FrontElem; 23 24 if ( IsEmpty(Q) ) { 25 printf("队列空"); 26 return ERROR; 27 } 28 else { 29 FrontCell = Q->Front; 30 if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */ 31 Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */ 32 else 33 Q->Front = Q->Front->Next; 34 FrontElem = FrontCell->Data; 35 36 free( FrontCell ); /* 释放被删除结点空间 */ 37 return FrontElem; 38 } 39 }

 

转载于:https://www.cnblogs.com/Jovesun/p/11196169.html