单链表-练习

假设采用带头的结点的单链表保存单词，但两个单词有相同的后缀时，可共享相同的存储的空间，例如：“loading”和“being”的存储映射像如下图所示.

str.png

//
//  wordlist.c
//  Ccode
//  实现单词操作，初始化，单词有相同的后缀， 共享存储空间
//  Created by XX on 2020/4/5.
//  Copyright © 2020 XX. All rights reserved.
//

#include "wordlist.h"
#include <stdlib.h>
#include <assert.h>

typedef char ElemChar;
typedef struct word {
    ElemChar data;
    struct word *next;
}word, *pword;

//新建结点
pword NewWord(ElemChar data) {
    pword temp = (word *)malloc(sizeof(word));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

//初始化
void InitWord(pword *str) {
    *str = (word *)malloc(sizeof(word));
    (*str)->next = NULL;
}

//尾插
void InsertWordTail(pword *str, ElemChar data) {
    assert(*str);
    pword new = NewWord(data);
    pword p = (*str)->next;
    if (p == NULL) {
        (*str)->next = new;
        return;
    }
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = new;
}

//打印
void PrintWord(pword str) {
    assert(str);
    pword p = str->next;
    if (p == NULL) {
        printf("空表...\n");
        return;
    }
    while (p) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

//str1+str be+ing = being
void JoinWord(pword *str1, pword *str) {
    assert(str1);
    assert(str);
    pword c1 = (*str1)->next;
    pword c = (*str)->next;
    while (c1->next != NULL) {
        c1 = c1->next;
    }
    c1->next = c;
}

//计算单词长度
int WordLength(pword str) {
    assert(str);
    int length = 0;
    pword p = str->next;
    if (p == NULL) {
        printf("空表...\n");
        return 0;
    }
    while (p) {
        length ++;
        p = p->next;
    }
    return length;
}

//找出共同后缀的起始位置
pword FindAddr(pword str1, pword str2) {
    assert(str1);
    assert(str2);
    int m, n;
    pword p, q;
    m = WordLength(str1);
    n = WordLength(str2);
    for (p=str1; m>n; m--) {
        p = p->next;
    }
    for (q=str2; m<n; n--) {
        q = q->next;
    }
    while (p && p->next != q->next) {
        p = p->next;
        q = q->next;
    }
    return p->next;//返回共同结点的起始地址
}

//测试
void testWord() {
    word list;
    pword str1 = &list;
    InitWord(&str1);
    pword str2 = &list;
    InitWord(&str2);
    pword str = &list;
    InitWord(&str);
    InsertWordTail(&str1, 'b');
    InsertWordTail(&str1, 'e');
    PrintWord(str1);
    InsertWordTail(&str2, 'l');
    InsertWordTail(&str2, 'o');
    InsertWordTail(&str2, 'a');
    InsertWordTail(&str2, 'd');
    PrintWord(str2);
    InsertWordTail(&str, 'I');
    InsertWordTail(&str, 'n');
    InsertWordTail(&str, 'g');
    PrintWord(str);
    JoinWord(&str1, &str);
    JoinWord(&str2, &str);
    PrintWord(str1);
    PrintWord(str2);
    pword find = &list;
    find->next = FindAddr(str1, str2);
    PrintWord(find);
}

1.用单链表保存m个整数，对于链表中data绝对值相等的结点，仅保留第一次出现的结点吧而删除其余绝对值相等的结点，如：

absulote.png

2.重组，实现L={1,2,3,4,5,6,7,8,9}转变为L'={1,9,2,8,3,7,4,6,5}

//
//  absolute.c
//  Ccode
//
//  Created by XX on 2020/4/5.
//  Copyright © 2020 XX. All rights reserved.
//

#include "absolute.h"
#include <stdlib.h>
#include <assert.h>
#include <math.h>

typedef int ElemType;
typedef struct absolute{
    ElemType data;
    struct absolute *link;
}absolute, *Abs;
//创建结点
Abs NewAbs(ElemType data)
{
    Abs tmp = (absolute *)malloc(sizeof(absolute));
    tmp->data = data;
    tmp->link = NULL;
    return tmp;
}
//初始化
void InitAbs(Abs *head) {
    (*head) = (absolute *)malloc(sizeof(absolute));
    (*head)->link = NULL;
}
//首插
void InsertAbsFront(Abs *head, ElemType data) {
    assert(*head);
    Abs next = (*head)->link;
    Abs new = NewAbs(data);
    (*head)->link = new;
    new->link = next;
}
//打印
void PrintAbs(Abs head) {
    assert(head);
    Abs p = head->link;
    if (head == NULL) {
        printf("空表...\n");
        return;
    }
    while (p) {
        printf("%d\t", p->data);
        p = p->link;
    }
    printf("\n");
}
//仅保留第一次出现的结点而删除其余绝对值相等的结点
void RemoveAbs(Abs *head) {
    assert(*head);
    Abs p = (*head)->link;
    Abs q = (*head)->link;
    if (p == NULL) {
        printf("空表...\n");
        return;
    }
    p = p->link;
    int count = 0;
    while (p->link != NULL) {
        count ++;
        Abs pmove = (*head)->link;
        for (int i = 0; i<count; i++) {
            if (abs(p->data) == abs(pmove->data)) {
                Abs next = p->link;
                q->link = next;
                free(p);
                p = next;
            }
            else
                pmove = pmove->link;
        }
        p = p->link;
        q = q->link;
    }
    if (p->link == NULL) {
        count ++;
        Abs pmove = (*head)->link;
        for (int i = 0; i<count; i++) {
            if (abs(p->data) == abs(pmove->data)) {
                q->link = NULL;
                free(p);
                return;
            }
            else
                pmove = pmove->link;
        }
    }
}
//重组，实现L={1,2,3,4,5,6,7,8,9}转变为L'={1,9,2,8,3,7,4,6,5}
void change_list(Abs *head) {
    assert(*head);
    Abs p, q, r, s;
    q = *head;
    p = *head;
    if ((*head)->link == NULL) {
        printf("空表...\n");
        return;
    }
    while (q) {//寻找中间结点
        p = p->link;
        q = q->link;
        if (q) {//p走一步，q走两步，完成前走到链表中间，q到达b链尾
            q = q->link;
        }
    }
    q = p->link;//p为中间结点，q为后半段的首元结点
    p->link = NULL;
    //原地逆置
    while (q) {
        r =q->link;//保留当前结点的后一个结点；
        q->link = p->link;
        p->link = q;
        q = r;
    }
    s = (*head)->link;//s指向前半段的首元结点
    q = p->link;//q指向后半段的首元结点
    p->link = NULL;
    while (q) {
        r = q->link;//保存q的下一个结点
        q->link = s->link; //将q所指结点插入到s所指结点之后
        s->link = q;
        s =q->link;//s指向q的下一个结点，其实就是前半段的s之前的下一个结点
        q = r;
    }
}

void testAbs() {
    absolute list;
    Abs head = &list;
    InitAbs(&head);
    InsertAbsFront(&head, 15);
    InsertAbsFront(&head, -7);
    InsertAbsFront(&head, -15);
    InsertAbsFront(&head, -15);
    InsertAbsFront(&head, 21);
    PrintAbs(head);
    change_list(&head);
    PrintAbs(head);
    RemoveAbs(&head);
    PrintAbs(head);
}