数据结构C语言实现

青旅半醒 2021-11-05 15:20 307阅读 0赞

顺序表实现

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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;   
    }

顺序表

链表实现

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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;
        }
    }

链表

堆栈线性存储

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

堆栈线性存储

堆栈链式存储

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

堆栈链式存储

队列线性存储

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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];
        }
    }

队列线性存储

队列链式存储

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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

转载于:https://www.cnblogs.com/cnblogs-xiaoqi/p/11257140.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211105/457d514b653f43048193106c0a3330eb.png