1.1链表青铜挑战笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了1.1链表青铜挑战笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

0.C语言中如何构造链表

为每一个元素配一个指针，每个元素的指针都指向自己的直接后继元素。
逻辑关系：一对一

0-1链表基本结构：结点(数据域+指针域)

数据域：存储元素的值

指针域：存放指针

0-2构造方法

typedef struct link{

char elem; //代表数据

struct link *next; //代表指针，指向直接后继元素

}Link;

struct ListNode* initLink() [
        int i;
        //1、创建头指针
        struct ListNode* p = NULL;
        //2、创建头结点
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->val = 0 ;
        temp->next = NULL:
        //头指针指向头结点
        p = temp;
        //3、每创建一个结点，都令其直接前驱结点的指针指向它

        for (i = 1; i < 5; i++) {
                //创建一个结点
                struct ListNode* a = (struct ListNode*)malloc(sizeof(struct ListNode));
                a->val = i;
                a->next = NULL;
                //每次 temp 指向的结点就是 a 的直接前驱结点
                temp->next = a;
                //temp指向下一个结点(也就是a),为下次添加结点做准备temp = temp->next;

}
return p;

}

测试方法：

int main() (
        struct ListNode*p = NULL;

        printf("初始化链表为: n”);

        //创建链表{1,2,3,4}

        p = initLink();

        return 0;

}

1.链表插入及处理

1.1在首部增加元素

易出现问题：忘记head重新指向表头

步骤：(1)newNode->next = head; //在表头新增加一个结点,后继是head

(2)head = newNode; //让head重新做回表头

1.2在中间增加元素

易出现问题：在中间增加元素需要连接左右两边的结点，要先连右边，再连左边，如果操作反向则会导致原来的后继结点路径丢失

步骤：(1)newNode->next = Node->next;

(2)Node->next = newNode;

1.3在尾部增加元素

较易，只需将尾结点指向新结点即可

链表插入三种方法代码：

struct ListNode* insertNode(struct ListNode* head, struct ListNode* nodeInsert, int position) {
        if (head == NULL) {

                // 这里可以认为待插入的节点就是链表的头节点，也可以抛出不能插入的异常

                return nodeInsert;

        }
        int size = getLength(head);

        if (position > size + 1 position < 1) {

                printf("位置参数越界");
                return head;

        }
        // 插入节点到头部
        if (position == 1) {

                nodeInsert->next = head;

                head = nodeInsert;

                return head;

        }
        struct ListNode* pNode = head;

        int count = 1;

        // 遍历链表，找到插入位置的前一个节点

        while (count < position - 1) {

                pNode = pNode->next;

                count++;
                nodeInsert->next = pNode->next;

                pNode->next = nodeInsert;
                return head;

}

测试方法：

void testInsert(
        struct ListNode* head = NULL;
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));

        node->val=1;

//插入第一个元素
        head=insertNode(head ,node ,1);

        printList(head);
//插入第二个元素，在尾部插入

        node = (struct ListNode*)malloc(sizeof(struct ListNode));

        node->val=3;

        head=insertNode(head ,node ,2);
        printList(head);
//插入第二个元素，在中间插入

        node = (struct ListNode*)malloc(sizeof(struct ListNode));

        node->val=2;

        head=insertNode(head ,node,2);

        printList(head);

}

2.链表删除及处理

2.1删除首部元素

较易，只需head = head -> next即可，将头指针直接移到下一个结点

2.2删除中间元素

删除时要找到被删除结点的前驱结点，即node->next = 被删结点，然后直接node->next = node ->next ->next即可删除

2.3删除尾部元素

同删除中间元素，只要找到被删除节点的前驱结点，然后node->next = null即可删除

删除元素

struct ListNode* deleteNode(struct ListNode*head, int position){

        if (head == NULL) {
                return NULL;

}
        int size = getLength(head);

        if (position > size position < 1) {

                printf("输入的参数有误\n");

                return head;

}
        if (position == 1) {

                return head->next;

        else {
        struct ListNode* preNode = head;

        int count = 1;

        while (count < position - 1) {

        preNode = preNode->next;

        count++;
        struct ListNode*curNode = preNode->next;

        preNode->next = curNode->next;

        free(curNode);

        return head;

}

}

测试方法:

void testDelete(){
        struct ListNode* p = NULL;printf("create list: t\n");

        //创建链表0-9

        p = initLink();

        printList(p);
        // 删除第一个元素0

        p= deleteNode(p,1);

        printList(p);
        //删除中间元素

        p= deleteNode(p,5);

        printList(p);
        //删除末尾元素9

        p= deleteNode(p,8);

        printList(p);

}

4.双向链表

4.1双向链表的构造

双向链表有两个指针，一个向前*pre,一个向后*next,可方便的移动元素

typedef struct DoubleNode {

        // 数据域

        int data;
        // 指向下一个结点

        struct DoubleNode *next;

        struct DoubleNode *prev;

}DoubleNode;
        // 创建新结点

DoubleNode* newNode(int data) {
        DoubleNode *newNode = (DoubleNode*)malloc(sizeof(DoubleNode));

newNode->data = data;

newNode->next = NULL;

newNode->prev = NULL;

        return newNode;

}
        //打印结点的数据域
void displayNode(DoubleNode *node){

        printf("%d"，node->data);

}

void traverse(DoubleNode *head){

        DoubleNode *p = head;

        // 定义指针p，指向头节点

        while (p != NULL){

                printf("%d"，p->data);

                // 输出当前节点的数据域值

                p = p->next;

                // 移动指针p到下一个节点

}

}