(10)王道数据结构-建立链表

尾插法

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
LinkList ListTailInsert(LinkList &L);
LNode* GetElem(LinkList L, int i);
int length(LinkList L);
int main(void) {
    LinkList L;
    L = ListTailInsert(L);

    if (!Empty(L)) {
        //获取第3个节点的值
        int num = GetElem(L,3)->data;
        printf("第3个节点的值为:%d\n", num);
        printf("链表长度为：%d\n", length(L));
    }
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

//按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p!=NULL && j<i) {    //循环找到第i个节点
        p = p->next;
        j++;
    }
    return p;
}

//尾插法建立单链表(正向建立单链表)
LinkList ListTailInsert(LinkList &L) {
    int x;      
    L = (LinkList)malloc(sizeof(LNode));    //建立头结点
    LNode *s, *r = L;       //r为表尾指针
    scanf("%d", &x);
    while(x!=9999) {    //输入9999结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;      //r指向新的表尾节点
        scanf("%d", &x);
    }
    r->next = NULL;     //尾节点指针置空
    return L;
}

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

头插法

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
LinkList ListHeadInsert(LinkList &L);
LNode* GetElem(LinkList L, int i);
int length(LinkList L);
int main(void) {
    LinkList L;
    L = ListHeadInsert(L);

    if (!Empty(L)) {
        //获取第3个节点的值
        int num = GetElem(L,3)->data;
        printf("第3个节点的值为:%d\n", num);
        printf("链表长度为：%d\n", length(L));
    }
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

//按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p!=NULL && j<i) {    //循环找到第i个节点
        p = p->next;
        j++;
    }
    return p;
}

//头插法建立单链表(逆向建立单链表)
LinkList ListHeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));    //创立头结点
    L->next = NULL;     //初始为空链表
    scanf("%d", &x);    //输入节点的值
    while (x != 9999) { //输入9999结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

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