20200401-数据结构-单向链表

403 阅读3分钟

单向循环链表代码相关实现

准备

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int ElemType;

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node* LinkList;

初始化

初始化流程

//循环找到尾结点方式
Status CreateList(LinkList *list) {
    int inValue;
    printf("输入结点的值,输入0结束\n");
    while (1) {
        scanf("%d", &inValue);
        if (inValue == 0) {
            break;
        }
        
        if (*list == NULL) {//链表不存在
            *list = (LinkList)malloc(sizeof(Node));
            if (!list) {
                return 0;
            }
            (*list)->data = inValue;
            (*list)->next = *list;
        } else {//链表存在
            LinkList tail = NULL;
            //循环 找到尾结点
            for (tail = *list; tail->next != *list; tail = tail->next){};
            LinkList tem = (LinkList)malloc(sizeof(Node));
            if (!tem) {
                return ERROR;
            }
            tem->data = inValue;
            //新结点要先进行next指向,然后尾结点next指向新结点。如果反过来写新结点的next就指向自己了。
            tem->next = tail->next;
            tail->next = tem;
        }
    }
    
    return OK;
}

通过代码可以看出,每次插入新的结点都要循环找到尾结点,这种方案效率会越来越慢。可以使用一个临时变量指针tail指向尾结点。需要注意,每次新增一个结点,要调整tail的指向。

//尾结点记录方式,没有for循环,时间复杂度更优
Status createList2(LinkList *list) {
    printf("输入结点的值,输入0结束\n");
    int inputValue;
    LinkList tail = NULL;//指向尾结点的指针变量
    while (1) {
        scanf("%d", &inputValue);
        if (inputValue == 0) {
            break;
        }
        if (*list == NULL) {
            
            *list = (LinkList)malloc(sizeof(Node));
            if (!*list) {
                return ERROR;
            }
            (*list)->data = inputValue;
            (*list)->next = *list;
            tail = *list;//指向尾结点
        } else {
            LinkList temp = (LinkList)malloc(sizeof(Node));
            if (!temp) {
                return ERROR;
            }
            temp->data = inputValue;
            temp->next = *list;
            tail->next = temp;//调整指向尾结点
            tail = temp;
        }
    }
    return OK;
}

遍历打印

void showList(LinkList list) {
    if (list == NULL) {
        printf("list == NULL");
        return;
    } else {
        LinkList tempNode = list;
        do {
            printf("%5d", tempNode->data);
            tempNode = tempNode->next;
        } while (tempNode != list);
        printf("\n");
    }
}

插入

代码流程

Status insetNode(LinkList *list, int place, ElemType elem) {
    //1.创建结点并赋值
    LinkList node = (LinkList)malloc(sizeof(node));
    if (!node) {
        return ERROR;
    }
    node->data = elem;
    
    if (place == 0) {//2.插入到链表头,需要修改首元结点
        //3.新结点next指向,原链表的首结点
        node->next = *list;
        //4.循环获取到尾结点
        LinkList tail = NULL;
        for (tail = *list; tail->next != *list; tail = tail->next) {
        }
        //5.尾结点指向新结点
        tail->next = node;
        //6.修改新结点为首结点
        *list = node;
        
    } else {//2.插入到其他位置
        //3.循环获取到指定位置的前一个结点。如果指定位置大于链表长度,获取尾结点。
        LinkList temp = NULL;
        int i;
        for (i = 1, temp = *list; i < place - 1 && temp->next != *list; i++, temp = temp->next) {
        }
        //4.新结点的next指向获取的结点的next
        node->next = temp->next;
        //5.获取到的结点next指向新结点
        temp->next = node;
    }
    
    return OK;
}

删除

Status deleteNode(LinkList *list, int place, ElemType *elem) {
    LinkList temp = NULL;
    LinkList target = NULL;
    if (place == 0) {//1.删除首结点
        //2.获取尾结点
        for (temp = *list; temp->next != *list; temp = temp->next) {
        }
        //3.获取首结点
        target = *list;
        //4.保存删除结点的data
        *elem = target->data;
        //5.切换首结点
        (*list) = (*list)->next;
        //6.尾结点指向新首结点
        temp->next = *list;
        //7.释放删除的结点
        free(target);
    } else {//1.删除非首结点
        //2.获取到要删除结点的前一个结点
        int i;
        for (i = 0, temp = *list; i < place - 1 && temp->next != *list; i++, temp = temp->next) {
        }
        //3.如果找不到要删除的的结点,返回错误
        if (temp->next == *list) {
            return ERROR;
        }
        //4.获取要删除的结点
        target = temp->next;
        //5.保存删除结点的data
        *elem = target->data;
        //6.前一个结点next指向要删除结点的next
        temp->next = target->next;
        //7.释放删除的结点
        free(target);
    }
    return OK;
}

查询

int findValueInList(LinkList list, ElemType value) {
    int i = 0;
    LinkList p = list;
    while (p->next !=list && p->data != value) {
        p = p->next;
        i ++;
    }
    if (p->next == list && p->data != value) {
        return -1;
    }
    
    return i;
}

简单总结

以上操作总体还是比较简单容易的,脑袋中要有一定的画面,还可以在纸上多画画。

需要注意几个点:

插入:先插入,再调整

删除:找前点,再删除

发现

通过对单向链表的学习,感觉双向链表要更加的灵活好用。期待下次的见面。

沿途的风景要比目的地更弯的否