<算法笔记>第七章

题目: Codeup

单链表及其操作

结点结构

• 由一个指针域和一个数据域组成

typedef struct NODE{
    int data;
    struct NODE *next;
}Node, *node;

创建带头结点的单链表

// 创建链表
node create(int Array[]){
    node p, pre, head;
    head = (node)malloc(sizeof(Node));
    head->next = NULL;
    pre = head;
    for(int i=0; i < 5 ; i++ ){
        p = (node)malloc(sizeof(Node));
        p->data = Array[i];
        p->next = NULL;
        pre->next = p;
        pre = p;
    }
    return head;
}

将每个结点数据域打印出来

int printList(node head){
    node p = head->next;
    while( p ){
        printf("%d ", p->data);
        p = p->next;
        if(!p) printf("\n");
    }
    return 0;
}

按值查找

// 查找值为x的结点, 返回符合的结点个数
int search(node head, int x){
    int count = 0;
    node p = head->next;
    while(p){
        if(p->data == x){
            count++ ;
        }
        p = p->next;
    }
    return count;
}

固定位置插入

// 在第pos位置插入元素x
int insert(node head, int pos, int x){
    node p = head;
    for(int i = 0; i != pos - 1 ; i++){
        p = p->next;
    }
    node q = (node)malloc(sizeof(Node));
    q->data = x;
    q->next = p->next;
    p->next = q;
    return 0;
}

按值删除

// 删除数据域为x的元素
int del(node head, int x){
    node p = head->next;
    node pre = head;
    while(p){
        if( p->data == x ){
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
        else{
            pre = p;
            p = p->next;
        }
    }
    return 0;
}

作业比赛编号 : 100000607 - 《算法笔记》7.3小节——数据结构专题(1)->链表处理

节点交换, 将相邻两个结点进行交换

// 交换pre的后两个结点
int exchangeNode(node pre){
    node p = pre->next;
    node q = p->next;
    pre->next = q;
    p->next = q->next;
    q->next = p;
    return 0;
}

链表排序

• 冒泡排序

int sortList(node head){
    node pre = head;
    node p = head->next;
    node q = p->next;
    int ischange = 1;
    while( ischange ){
        ischange = 0;
        while(q){
            if(p->data>q->data) {
                exchangeNode(pre);
                ischange = 1;
            }
            pre = p;
            p = q;
            q = q->next;
        }
    }
    return 0;
}

问题 E: 算法2-24 单链表反转

node reverse(node head){
    if(!head) return head;
    node pre = NULL;
    node next = NULL;
    head = head->next;
    while(head){
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    node new_head = (node)malloc(sizeof(Node));
    new_head->next = pre;
    return new_head;
}