(09)王道数据结构-单链表的查找

按位查找

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
LNode* GetElem(LinkList L, int i);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！\n");
    }

    int e = 0;
    ListDelete(L, 8, e);

    //判断是否删除成功
    LNode* node = NULL;
    node = GetElem(L, 8);
    if (node == NULL) {
        printf("删除成功！\n");
    }
    node = GetElem(L, 6);
    printf("获取元素:%d\n", node->data);
    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个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
        printf("插入失败!\n");
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p != NULL && j < i-1) {      //循环找到第i-1个节点
        p = p->next;
        j++;
    }
    if (p == NULL) {    //i值不合法
        return false;
        printf("插入失败!\n");
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;        //将节点s连接到p之后
    return true;        //插入成功
}

//按位序删除：带头结点
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    LNode *p;       //指针p指向当前扫描到的节点
    int j = 0;      //当前p指向的是第几个节点
    p = L;          //L指向头结点，头结点是第0个节点（不存数据）
    while(p != NULL && j < i-1) {   //循环找到第i-1个节点
        p = p->next;
        j++;
    }

    if (p==NULL) {  //i值不合法
        return false;
    }
    if (p->next == NULL) {  //第i-1个节点之后已无其他节点
        return false;
    }
    LNode *q = p->next;     //令p指向被删除节点
    e = q->data;            //用e返回元素的值
    p->next = q->next;      //将*q节点从链中“断开”
    free(q);
    return true;
}

//按位查找，返回第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;
}

封装之后

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
bool InsertNextNode(LNode *p, int e);
LNode* GetElem(LinkList L, int i);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！\n");
    }

    int e = 0;
    ListDelete(L, 8, e);

    //判断是否删除成功
    LNode* node = NULL;
    node = GetElem(L, 8);
    if (node == NULL) {
        printf("删除成功！\n");
    }
    node = GetElem(L, 6);
    printf("获取元素:%d\n", node->data);
    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个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    return InsertNextNode(p, e);    //p后插入新元素e
}

//按位序删除：带头结点
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    if (p==NULL) {  //i值不合法
        return false;
    }
    if (p->next == NULL) {  //第i-1个节点之后已无其他节点
        return false;
    }
    LNode *q = p->next;     //令p指向被删除节点
    e = q->data;            //用e返回元素的值
    p->next = q->next;      //将*q节点从链中“断开”
    free(q);
    return true;
}

//按位查找，返回第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;
}

//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->data = e;    //用节点s保存数据元素e
    s->next = p->next;
    p->next = s;
    return true;
}

按值查找

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
bool InsertNextNode(LNode *p, int e);
LNode* LocalElem(LinkList L, int e);
LNode* GetElem(LinkList L, int i);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！\n");
    }

    int e = 0;
    ListDelete(L, 8, e);

    //判断是否删除成功
    LNode* node = NULL;
    node = LocalElem(L, 88);
    if (node == NULL) {
        printf("删除成功！\n");
    }
    node = LocalElem(L, 66);
    printf("获取元素位序:%d\n", node->data);
    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个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    return InsertNextNode(p, e);    //p后插入新元素e
}

//按位序删除：带头结点
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    if (p==NULL) {  //i值不合法
        return false;
    }
    if (p->next == NULL) {  //第i-1个节点之后已无其他节点
        return false;
    }
    LNode *q = p->next;     //令p指向被删除节点
    e = q->data;            //用e返回元素的值
    p->next = q->next;      //将*q节点从链中“断开”
    free(q);
    return true;
}

//按值查找，找到数据域==e的节点
LNode* LocalElem(LinkList L, int e) {
    LNode *p = L->next;
    //从第一个节点开始查找数据域为e的节点
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

//按位查找，返回第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;
}

//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->data = e;    //用节点s保存数据元素e
    s->next = p->next;
    p->next = s;
    return true;
}

求表长度

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool InsertNextNode(LNode *p, int e);
LNode* GetElem(LinkList L, int i);
int length(LinkList L);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    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个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    return InsertNextNode(p, e);    //p后插入新元素e
}

//按位查找，返回第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;
}

//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->data = e;    //用节点s保存数据元素e
    s->next = p->next;
    p->next = s;
    return true;
}

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