链表

1.链表顺序存储

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
const int MAXSIZE = 100;
struct LNode 
{
    ElementType Data[MAXSIZE];  
    int Last;                
};
typedef struct LNode *List;
List MakeEmpty(); 
ElementType FindKth(int K, List Ptrl);
int Find(ElementType X, List Ptrl);
void Insert(ElementType X, int i, List Ptrl);
void Delete(int i, List Ptrl);
int Length(List Ptrl);
int main(void) 
{
    List P;
    P = MakeEmpty();
    for(int i = 0; i < 10; i++)
    {
        Insert(i,i+1,P);
    }
    for( int k = 0; k <= P->Last; k++ )
    printf( "%d ", P->Data[k] );
    printf("\n");
    printf( "找下标为五也就是第六个元素的值\n" ); 
    printf( "%d\n", FindKth(5, P));
    printf( "查找值为三并返回下标\n" ); 
    printf( "%d\n", Find(3,P));
    printf( "删除第六个\n" );
    Delete(6, P);
    for( int k = 0; k <= P->Last; k++ )
    printf( "%d ", P->Data[k] );
    printf("\n");
    printf( "长度为：%d", Length(P));
    free(P);
    return 0;
}
List MakeEmpty() 
{
    List Ptrl;                                
    Ptrl = (List)malloc(sizeof(struct LNode));  
    Ptrl->Last = -1;  
    return Ptrl;      
}
ElementType FindKth(int K, List Ptrl) 
{
    return Ptrl->Data[K];
}
int Find(ElementType X, List Ptrl) 
{
    int i = 0;
    while (i <= Ptrl->Last && Ptrl->Data[i] != X) 
    {
        i++;
    }
    if (i > Ptrl->Last)
        return -1;
    else
        return i;
}
void Insert(ElementType X, int i, List Ptrl) 
{
    if (Ptrl->Last == MAXSIZE - 1) 
    {  
        printf("表满");
        return;
    }
    if (i < 1 || i > Ptrl->Last + 2) 
    {  
        printf("位置不合法");
        return;
    }
    int j;
    for (j = Ptrl->Last; j >= i - 1; j--)  
        Ptrl->Data[j + 1] = Ptrl->Data[j];
    Ptrl->Data[i - 1] = X;
    Ptrl->Last++;  
    return;
}
void Delete(int i, List Ptrl) 
{
    int j;
    if (i < 1 || i > Ptrl->Last + 1) 
    {  
        printf("不存在第%d个元素", i);
        return;
    }
    for (j = i; j <= Ptrl->Last; j++)  
        Ptrl->Data[j - 1] = Ptrl->Data[j];
    Ptrl->Last--;
    return;
}
int Length(List Ptrl)
{
    return Ptrl->Last + 1;
}

2.链表链式存储

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
const int MAXSIZE = 100;
typedef struct LNode *List;
struct LNode 
{
    ElementType Data;
    List Next;  
};
List Insert(ElementType X,int i,List PtrL);  
List FindKth(int K, List PtrL);  
List Find(ElementType X, List PtrL);  
List Delete(int i, List PtrL);  
int Length(List PtrL);        
int main(void) 
{
    List P = NULL;
    for (int i = 0; i < 10; i++) 
    {
        P = Insert(i, 1, P);
    }
    List s;
    printf( "长度为：%d\n", Length(P)); 
    printf( "遍历整个数组 ：" ); 
    for ( s = P; s->Next != NULL; s = s->Next )
    {
        printf( "%d ", s->Data );
    }
    printf("\n");
    printf( "第3个元素为：" );
    s = FindKth(3, P);
    if(s) 
    printf( "%d\n", s->Data);
    printf( "删除第四个元素\n" );
    Delete(4, P);
    printf( "删除后第四个元素为:" );
    s = FindKth(4, P);
    if (s) 
    printf( "%d\n", s->Data);
    printf("表中是否有元素6：");
    s = Find(6, P);
    if (s) 
    printf( "%d\n", s->Data);
    printf("表中是否有元素5：");
    s = Find(5, P);
    if (s) 
    printf( "yes" );
    free(P);
    return 0;
}    
List Insert(ElementType X, int i, List PtrL) 
{
    List p, s;
    if (i == 1) 
    {               
        s = (List)malloc( sizeof(struct LNode) );  
        s->Data = X;
        s->Next = PtrL;
        return s;  
    }
    p = Find(i - 1, PtrL);  
    if (p == NULL) 
    {        
        printf("参数i错");
        return NULL;
    } else {
        s = (List)malloc( sizeof(struct LNode) );  
        s->Data = X;
        s->Next = p->Next;  
        p->Next = s;
        return PtrL;
    }
}
List Find(ElementType X, List PtrL) 
{
    List p = PtrL;
    while(p != NULL && p->Data != X) 
        p = p->Next;
    if(p == NULL) 
    {          
        printf( "查无此元素\n" );
        return NULL;
    } 
    else  return p;
}
List FindKth(int K, List PtrL) 
{
    List p = PtrL;
    int i = 1;
    while (p != NULL && i < K) 
    {
        p = p->Next;
        i++;
    }
    if(i == K) 
    return p;
    else 
    {              
        printf( "查无此元素\n" );
        return NULL;
    }
}
List Delete(int i, List PtrL) 
{
    List p, s;
    if( i == 1) 
    {   
        s = PtrL;           
        if (PtrL != NULL)   
        PtrL = PtrL->Next;  
        else 
        return NULL;
        free(s);                           
        return PtrL;
    }
    p = FindKth(i-1, PtrL);     
    if (p == NULL) 
    {
        printf("第%d个结点不存在", i-1);
        return NULL;
    } 
    else if (p->Next == NULL) 
    {
        printf("第%d个结点不存在",i);
        return NULL;
    } 
    else 
    {
        s = p->Next;            
        p->Next = s->Next;      
        free(s);                
        return PtrL;
    }
}
int Length(List PtrL) 
{
    List p = PtrL;
    int j = 0;
    while(p) 
    {
        p = p->Next;
        j++;
    }
    return j;
}