C语言实现链表

发布于 2020-04-12  117 次阅读


单链表

#include<stdio.h>
#include<malloc.h>
#include<windows.h>

//定义一个链表的结构体
typedef struct LNode{
    int val;
    struct LNode *next;
}LNode,*LinkList;

//头插法
void List_HeadInsert(LinkList &L){
    printf("-----------Use headInsert----------\n");
    LNode *s;
    int x;

    L = (LinkList)malloc(sizeof(LNode));

    if(L == NULL){//分配空间失败
        printf("No enough memory!\n");
        return;
    }

    L->next=NULL;
    scanf("%d",&x);

    while(x != 9999){//输入9999停止插入节点
        s = (LNode*)malloc(sizeof(LNode));

        if(s == NULL){//分配空间失败
            printf("No enough memory!\n");
            return;
        }
        s->val=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
}
//尾插法
void  List_TailInsert(LinkList &L){
    printf("-----------Use tailInsert----------\n");
    LNode *s,*r;
    int x;

    L = (LNode*)malloc(sizeof(LNode));

    if(L == NULL){//分配空间失败
        printf("No enough memory!\n");
        return;
    }

    r = L;
    scanf("%d",&x);

    while(x != 9999){//输入9999停止插入节点
        s = (LNode*)malloc(sizeof(LNode));

        if(s == NULL){//分配空间失败
            printf("No enough memory!\n");
            return;
        }

        s->val=x;
        r->next=s;
        r=s;
        scanf("%d", &x);
    }
    r->next = NULL;
}
// 按位置查找节点
LNode *GetElem(LinkList L,int i){
    int j = 1;
    LNode *p = L->next;

    if(i == 0)//0返回头节点
        return L;

    if(i < 1)
        return NULL;

    while(p && j < i){
        p = p->next;
        j++;
    }

    if(p != NULL)
        printf("Search node successed!!!\n Node value: %d\n",p->val);
    else
        printf("Search failed, the Node No.%d is not existed!!!\n",i);

    return p;
}
// 按值查找节点
LNode *LocateElem(LinkList L,int value){
    LNode *p = L->next;

    while(p!=NULL && p->val != value)
        p = p->next;

    if(p != NULL)
        printf("Search node successed!!!\n Node value: %d\n",p->val);
    else
        printf("Search failed, the Node is not existed!!!\n");

    return p;
}
// 按位置插入节点
void InsertElem(LinkList &L,int value,int i){
    LNode *p = GetElem(L,i-1);//获得要插入节点的前一个节点
    LNode *r = (LNode*)malloc(sizeof(LNode));
    if(r == NULL){//分配内存失败
        printf("No enough memory!\n");
        return;
    }
    r->val = value;
    r->next = p->next;
    p->next = r;
    printf("Insert %d successed!!\n",value);
}
// 按位置删除节点
void DeleteElem(LinkList &L,int i){
    LNode *p = GetElem(L,i-1);
    if(p == NULL)
        return;//i超出链表长度
    LNode *r = p->next;
    p->next = r->next;
    free(r);
    printf("Delete No.%d node successed!!\n",i);
}
//销毁链表
void freeLinkList(LinkList &L){
    LNode *p = L;
    while(p != NULL){
        L = L->next;
        free(p);
        p = L;
    }
    printf("Free memory successed!!!\n");
}
int main(){
    LinkList head;
    List_TailInsert(head);

    InsertElem(head,1000,3);
    DeleteElem(head,10);

    LNode *p = head->next;
    while(p != NULL){
        printf("%d\n",p->val);
        p = p->next;
        Sleep(500);
    }
    freeLinkList(head);
    return 0;
}

双链表

#include<stdio.h>
#include<malloc.h>
#include<windows.h>

//定义一个链表的结构体
typedef struct LNode{
    int val;
    struct LNode *pre;
    struct LNode *next;
}LNode,*DLinkList;

//头插法
void List_HeadInsert(DLinkList &L){
    printf("-----------Use headInsert----------\n");
    LNode *s;
    int x;

    L = (DLinkList)malloc(sizeof(LNode));

    if(L == NULL){//分配空间失败
        printf("No enough memory!\n");
        return;
    }

    L->next=NULL;
    scanf("%d",&x);

    while(x != 9999){//输入9999停止插入节点
        s = (LNode*)malloc(sizeof(LNode));

        if(s == NULL){//分配空间失败
            printf("No enough memory!\n");
            return;
        }
        s->val=x;
        s->next=L->next;
        L->next->pre = s;
        s->pre = L;
        L->next=s;
        scanf("%d",&x);
    }
}
//尾插法
void  List_TailInsert(DLinkList &L){
    printf("-----------Use tailInsert----------\n");
    LNode *s,*r;
    int x;

    L = (LNode*)malloc(sizeof(LNode));

    if(L == NULL){//分配空间失败
        printf("No enough memory!\n");
        return;
    }

    r = L;
    scanf("%d",&x);

    while(x != 9999){//输入9999停止插入节点
        s = (LNode*)malloc(sizeof(LNode));

        if(s == NULL){//分配空间失败
            printf("No enough memory!\n");
            return;
        }

        s->val = x;
        r->next = s;
        s->pre = r;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
}
// 按位置查找节点
LNode *GetElem(DLinkList L,int i){
    int j = 1;
    LNode *p = L->next;

    if(i == 0)//0返回头节点
        return L;

    if(i < 1)
        return NULL;

    while(p && j < i){
        p = p->next;
        j++;
    }

    if(p != NULL)
        printf("Search node successed!!!\n Node value: %d\n",p->val);
    else
        printf("Search failed, the Node No.%d is not existed!!!\n",i);

    return p;
}
// 按值查找节点
LNode *LocateElem(DLinkList L,int value){
    LNode *p = L->next;

    while(p!=NULL && p->val != value)
        p = p->next;

    if(p != NULL)
        printf("Search node successed!!!\n Node value: %d\n",p->val);
    else
        printf("Search failed, the Node is not existed!!!\n");

    return p;
}
// 按位置插入节点
void InsertElem(DLinkList &L,int value,int i){
    LNode *p = GetElem(L,i-1);//获得要插入节点的前一个节点
    LNode *r = (LNode*)malloc(sizeof(LNode));
    if(r == NULL){//分配内存失败
        printf("No enough memory!\n");
        return;
    }
    r->val = value;
    r->next = p->next;
    p->next->pre = r;
    r->pre = p;
    p->next = r;
    printf("Insert %d successed!!\n",value);
}
// 按位置删除节点
void DeleteElem(DLinkList &L,int i){
    LNode *p = GetElem(L,i);
    if(p == NULL)
        return;//i超出链表长度
    p->pre->next = p->next;
    p->next->pre = p->pre;

    free(p);
    printf("Delete No.%d node successed!!\n",i);
}
//销毁链表
void freeLinkList(DLinkList &L){
    LNode *p = L;
    while(p != NULL){
        L = L->next;
        free(p);
        p = L;
    }
    printf("Free memory successed!!!\n");
}
int main(){
    DLinkList head;
    List_TailInsert(head);

    InsertElem(head,1000,3);
    InsertElem(head,10000,4);

    DeleteElem(head,3);

    LNode *p = head->next;
    while(p != NULL){
        printf("%d\n",p->val);
        p = p->next;
        Sleep(500);
    }
    freeLinkList(head);
    return 0;
}

天空没有鸟的痕迹,但我已飞过。