博客

考研数据结构之单链代码

  • Post author:
  • Post category:其他


王道版单链表代码



结构体定义

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;



单链表的建立



头插法

LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    ElemType x;
    scanf("%d",&x);
    while(x!=9999){
        s = (LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}



尾插法

LinkList List_TailInsert(LinkList &L){
    ElemType x;
    L = (LinkList)malloc(sizeof(LinkList));
    LNode *s,*r = L; //*r为尾指针
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next = s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}



单链表的的插入



带头节点

bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)
        return false;
    LNode *p = L;
    int j=0;
    while(j<i-1&&p!=NULL){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}



不带头节点

bool ListInsert_WithnoHead(LinkList &L,int i, ElemType e){
    if(i<1)
        return false;
    if(i==1){
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s -> next = L;
        L =  s;
        return true;
    }
    LNode *p = L;
    int j = 1;
    while(j<i-1&&p!=NULL){
        p = p->next;
        j++;
    }
    if(p==NULL){
        return false;
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}



在某节点后插入元素（后插操作）

bool InsertNextNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}



在某节点前插入元素（前插操作）

bool InsertNextNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}



单链表的删除

bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    int j = 0;
    LNode *p = L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(p->next==NULL)
        return false;
    LNode *q = p->next;
    e = q->data;
    p->next=q->next;
    free(q);
    return true;
}



单链表的查找



按位查找

LNode *GetElem(LinkList L, int i){
    if(i<0)
      return NULL;
    LNode *p=L;
    int j = 0;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}



按位查找

LNode *LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;
    while(p!=NULL&&p->data!=e)
        p = p->next;
    return p;
}



附录（全代码；含测试！）

#include <stdio.h>
#include <malloc.h>
#define ElemType int

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// 头插法建立链表
LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    ElemType x;
    scanf("%d",&x);
    while(x!=9999){
        s = (LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

// 尾插法建立链表(带头节点)
LinkList List_TailInsert(LinkList &L){
    ElemType x;
    L = (LinkList)malloc(sizeof(LinkList));
    LNode *s,*r = L; //*r为尾指针
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next = s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

// 按位查找(返回第i个元素)[带头节点]
LNode *GetElem(LinkList L, int i){
    if(i<0)
      return NULL;
    LNode *p=L;
    int j = 0;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

//按值查找
LNode *LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;
    while(p!=NULL&&p->data!=e)
        p = p->next;
    return p;
}

//求表长度
int length(LinkList L){
    int length = 0;
    LNode *p = L;
    while(p->next!=NULL){
        length++;
        p=p->next;
    }
    return length;
}

//在某个节点后插入节点
bool InsertNextNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 在某个节点前插入元素
bool InsertPriorNode(LNode *p, ElemType e){
    if(p==NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode)); 
    if(s==NULL)
        return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

// 按位序删除
bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    int j = 0;
    LNode *p = L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(p->next==NULL)
        return false;
    LNode *q = p->next;
    e = q->data;
    p->next=q->next;
    free(q);
    return true;
}

// 按位序插入，在第i个位置插入e[带头节点]
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)
        return false;
    LNode *p = L;
    int j=0;
    while(j<i-1&&p!=NULL){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 按位序插入 [不带头节点]
bool ListInsert_WithnoHead(LinkList &L,int i, ElemType e){
    if(i<1)
        return false;
    if(i==1){
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s -> next = L;
        L =  s;
        return true;
    }
    LNode *p = L;
    int j = 1;
    while(j<i-1&&p!=NULL){
        p = p->next;
        j++;
    }
    if(p==NULL){
        return false;
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}


int main(){
    LinkList L;
    L = List_TailInsert(L);
    bool flag = ListInsert(L,1,66);
    LNode *a = GetElem(L,1);
    printf("%d\n",a->data);
    LNode *s = LocateElem(L,99);
    printf("%d\n",s->data);
    printf("%d\n",length(L));
    int tep;
    ListDelete(L,1,tep);
    printf("%d",tep);
    printf("%d",GetElem(L,1)->data);
}