数据结构-1-链表

单链表

指针大法好

真正到学习数据结构的时候才发现自己对指针的特性理解得非常肤浅，在真正使用链表的时候卡了很久

核心

增

p=(Link*)malloc(sizeof (Link));
p->data=*data++; //data为数据集合
p->next=L->next;
L->next=p;

删

Link *q;
q=p->next;
p->next=q->next;
free(q);

查

1	e=p->data; //e为节点data

插

Link *s;
s=(Link*)malloc(sizeof(Link));
s->data=e; //e为节点data
s->next=p->next;
p->next=s;

实现

#include <stdio.h>
#include <stdlib.h>

typedef char Elemtype;

struct Node{
    Elemtype data;
    struct Node *next;
};

typedef struct Node Link;

Link **head;
Link **tail;

// 先进后出link
void d_CreateLink(Link **L,Elemtype data[],int n){
    Link *p;
    int i;
    *L=(Link *)malloc(sizeof (Link));
    (*L)->next=NULL;
    for (i = 0; i < n; ++i) {
        p=(Link*)malloc(sizeof (Link));
        p->data=*data++;
        p->next=(*L)->next;
        (*L)->next=p;
    }
}

//先进先出link
void CreateLink(Link **L,Elemtype data[],int n) {
    Link *p,*r;
    int i;
    *L=(Link *)malloc(sizeof (Link));
    r=*L;
    for (i = 0; i < n; i++) {
        p=(Link*)malloc(sizeof (Link));
        p->data=*data++;
        r->next=p;
        r=p;
    }
    r->next=NULL;
}

// 增量式单链表（正序）
void AddLink(Link **L,Elemtype data[],int n) {
    Link *p,*r;
    int i;
    if (tail!=NULL){
        r=*tail;
    }else {
        *L=(Link *)malloc(sizeof (Link));
        r=*L;
    }
    for (i = 0; i < n; i++) {
        p=(Link*)malloc(sizeof (Link));
        p->data=*data++;
        r->next=p;
        r=p;
    }
    r->next=NULL;
    *tail=r;
}



// 得到第i个节点的data
Elemtype GetElem(Link *L,int i,Elemtype e){
    int j;
    Link *p;
    p=L->next;
    j=1;
    while (p&&j<i){
        p=p->next;
        j++;
    }
    if (!p||j>i){
        return -1;
    }
    e=p->data;
    return e;
}


// 在第i个节点之前插入新的node，L长度+1
void InsertElem(Link *L,int i,Elemtype e)  {
    int j;
    Link *p,*s;
    p=L;
    j=1;
    while (p&&j<i){
        p=p->next;
        ++j;
    }
    if (!p||j>i) {
        return;
    }
    s=(Link*)malloc(sizeof(Link));
    s->data=e;
    s->next=p->next;
    p->next=s;
}

Elemtype DeleteElem(Link *L,int i,Elemtype e){
    int j;
    Link *p,*q;
    p=L;
    j=1;
    while (p->next&&j<i){
        p=p->next;
        j++;
    }
    if (!(p->next)||j>i){
        return -1;
    }
    q=p->next;
    p->next=q->next;
    free(q);
    return e;
}