数据结构之链表的实现

1、顺序链表

       //.h文件

#define  MaxSize 50
typedef char ElemType;
typedef struct {
    ElemType elem[MaxSize];
    int length;
}SqList;
//.cpp文件
void InitList(SqList *&L){
    
    L=(SqList*)malloc(sizeof(ElemType)*MaxSize);
    L->length=0;
    
}
void DestroyList(SqList *L){
    free(L);
    
}
int ListEmpty(SqList *L){
    return L->length==0;
    
}
int ListLength(SqList *L){
    return L->length;
}
void DispList(SqList *L){
    int i;
    if(ListEmpty(L))return;
    for(i=0;i<L->length;i++){
        printf("%c",L->elem[i]);
    }
    printf("\n");
    
}
int GetElem(SqList *L,int i,ElemType& e){
    if(i<1||i>=L->length){
        return 0;
    }
    e=L->elem[i-1];
    
    return 1;
}
int LocateElem(SqList *L,ElemType e){
    
    int i=0;
    while(i<L->length&&L->elem[i]!=e)i++;
    return i>=L->length?0:i+1;
    
}

int ListInsert(SqList * &L,int i,ElemType e){
    int j;
    if(i<1||i>L->length+1)
        return 0;
    i--;
    for (j=L->length; j>i; j--) {
        L->elem[j]=L->elem[j-1];
    }
    L->elem[i]=e;
    L->length++;
    return 1;

}
int ListDelete(SqList * &L,int i,ElemType &e){
    
    int j;
    if(i<1||i>L->length+1)
        return 0;
    i--;
    for (j=i; j<L->length-1; j++) {
        L->elem[j]=L->elem[j+1];
    }
    L->length--;
    
    return 1;
    
}

 2、链式链表

 

//.h文件
typedef char ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LinkList;
//.cpp文件

#include "LinkList.h"
void InitList(LinkList *&L)
{
    L=(LinkList*)malloc(sizeof(LinkList));
    L->next=NULL;
}
void DestroyList(LinkList* &L)
{
    LinkList *p=L,*q=p->next;
    while (q!=NULL) {
        free(p);
        p=q;
        q=p->next;
    }
    free(p);
}
int ListEmpty(LinkList* L)
{
    return L->next==NULL;
}
int ListLength(LinkList* L)
{
    LinkList *p=L;int i=0;
    while (p->next!=0) {
        i++;
        p=p->next;
    }
    return i;
}
void DispList(LinkList* L)
{
    LinkList *p=L;
    while (p->next!=NULL) {
        p=p->next;
        printf("%c",p->data);
        
    }
    printf("\n");
}
int GetElem(LinkList* L,int i,ElemType &e)
{
    int j=0;
    LinkList *p=L;
    while(j<i&&p!=NULL){
        j++;
        p=p->next;
    }
    if(p==NULL){
        return 0;
    }else{
        e=p->data;
        return 1;
    }
    
}
int LocateElem(LinkList *L,ElemType e)
{
    
    LinkList *p=L->next;
    int n=1;
    while (p!=NULL&&p->data!=e) {
        p=p->next;
        n++;
    }
    if(p==NULL){
        return 0;
    }else{
        return n;
    }
   
    
}
int ListInsert(LinkList* &L,int i, ElemType e)
{
    
    int j=0;
    LinkList *p=L;
    while (j<i-1&&p!=NULL) {
        j++;
        p=p->next;
    }
    if(p==NULL){
        return 0;
    }else{
        LinkList *q=(LinkList *)malloc(sizeof(LinkList));
        q->data=e;
        q->next=p->next;
        p->next=q;
        return 1;
    }
}
int ListDelete(LinkList* &L,int i,ElemType &e)
{   int j=0;
    LinkList *p=L,*q;
    while(j<i-1&&p!=NULL){
        j++;
        p=p->next;
            }
    if(p==NULL){
       
        return 0;
    }else{
        if(p->next!=NULL){
          q=p->next;
          p->next=q->next;
          free(q);
          return 1;
        }else{
            return 0;
        }
        
    }
    
}