数据结构--线性结构

顺序存储结构

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

以上为顺序存储结构的初始化查找插入删除。

线性表基本操作
1、List MakeEmpty()：初始化一个空线性表L；
2、ElementType FindKth( int K, List L )：根据位序K，返回相应元素 ；
3、int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置；
4、void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X；
5、void Delete( int i, List L )：删除指定位序i的元素；
6、int Length( List L )：返回线性表L的长度n。

链式存储结构

 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 = -1; 
    S->MaxSize = MaxSize; 
return S; 
} 

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

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 == -1); 
} 

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