链表结构详解
本文最后更新于 457 天前,其中的信息可能已经有所发展或是发生改变。

链表的概念及结构

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

  1. 链表结构在逻辑上是连续的,但是在物理上不一定是连续的
  2. 现实中的结点一般都是从堆上申请出来的
  3. 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

 

链表分类

简单分类来讲,我们把链表的属性分为以下三种:

  1. 单向或者双向
  2. 有头或者无头
  3. 循环或者非循环

根据2^3=8推出链表一共分为8种类型,而在这8种链表中最常见的是:

无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。

有头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。

 

链表的实现

单向无头非循环链表

假设我们需要创建一个由个人信息组成的链表。

第一步:先创建关于person的结构体,并将其包含在listNode链表对象之中作为成员。

struct person {
    char name[10];
    int year;
    char sex;
};

struct listNode {
    person info;
    listNode* next;
};

第二步:为listNode提供操作函数

/*
    开辟内存
*/
list* createList(person info) {
    /*
    不直接使用malloc分配内存
    listNode l;
    l.info = info;
    l.next = NULL;
    return &l;
    */

    listNode* l = (listNode*)malloc(sizeof(listNode));
    l->info = info;
    l->next = NULL;
    return l;
}

/*
    尾部插入
*/
void pushback(person info, listNode** head) {
    listNode* add = createList(info);
    if (*head == NULL) {
        *head = add;
    }
    else {
        listNode* tail = *head;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = add;
    }
}

/*
    头部插入
*/
void pushfront(person info, listNode** head) {
    listNode* add = createList(info);
    if (*head == NULL) {
        *head = add;
    }
    else {
        add->next = *head;
        *head = add;
    }
}

/*
    尾部删除
*/
void popback(listNode** head) {
    if (*head != NULL) {
        listNode* temp = *head;
        listNode* prev = temp;
        while (temp->next != NULL) {
            prev = temp;
            temp = temp->next;
        }
        prev->next = NULL;
        free(temp); //释放内存
        temp = NULL;
    }
}

/*
    头部删除
*/
void popfront(listNode** head) {
    if (*head != NULL) {
        listNode* temp = *head;
        *head = (*head)->next;
        free(temp);
        temp = NULL;
    }
}

/*
    打印链表
*/
void printList(listNode* head) {
    assert(head != NULL); //断言assert(0) 则abort();退出
    while (head != NULL) {
        printf("%s %d %c\n", head->info.name, head->info.year, head->info.sex);
        head = head->next;
    }
}

第三步:在main函数中操作链表

int main() {
    person p = { "XiaoMing",8,'M' };
    person p2 = { "XiaoHong",8,'F' };
    person p3 = { "XiaoGang",8,'M' };
    listNode* l = NULL;
    pushback(p, &l);
    pushback(p2, &l);
    pushback(p3, &l);
    pushfront(p3, &l);
    popfront(&l);
    popback(&l);
    printList(l);
}

Output:

XiaoMing 8 M
XiaoHong 8 F

双向有头循环链表

现在我们创建班级的双向有头循环链表。

第一步:构造cls结构体,并对cls重载符号==函数(在后面进行Search操作时会用到)。并将cls包含在我们的listNode链表结构体内。

struct cls {
    int id;
    int memnum;
    //重载==符号函数
    bool operator == (const cls& clazz) {
        return clazz.id == this->id && this->memnum == clazz.memnum;
    }
};

struct listNode {
    cls clazz;
    listNode* pre;
    listNode* next;
};

第二步:为listNode提供操作函数,具体作用查看注释。

/*
    申请空间
*/
listNode* createList(cls clazz) {
    listNode* node = (listNode*)malloc(sizeof(listNode));
    node->clazz = clazz;
    return node;
}

/*
    初始创建链表头节点
*/
listNode* headInit(void) {
    listNode* head = createList(cls{0,0});
    head->next = head;
    head->pre = head;
    return head;
}

/*
    查询cls对应节点
*/
listNode* listSearch(listNode** list, cls clazz) {
    listNode* pos = *list;
    while (!(pos->clazz == clazz)) {
        pos = pos->next;
        if (pos == *list) {
            return NULL;
        }
    }
    return pos;
}

/*
    删除指定cls节点
*/
void listErase(listNode* list, cls clazz) {
    listNode* pos = listSearch(&list,clazz);
    pos->pre->next = pos->next;
    pos->next->pre = pos->pre;
    free(pos);
}

/*
    头插
*/
void pushFront(listNode** head,cls clazz) {
    assert(*head != NULL);
    listNode* node = createList(clazz);
    listNode* phead = (*head)->next; //头节点后的第一位单元

    phead->pre = node;
    (*head)->next = node;
    node->next = phead;
    node->pre = *head;
}

/*
    尾插
*/
void pushBack(listNode** head, cls clazz) {
    listNode* ptail = (*head)->pre;
    listNode* node = createList(clazz);

    ptail->next = node;
    node->pre = ptail;
    node->next = *head;
    (*head)->pre = node;
}

/*
    头删
*/
void popFront(listNode** head) {
    assert(*head != NULL);
    listErase(*head,(*head)->next->clazz);
}

/*
    尾删
*/
void popBack(listNode** head) {
    assert(*head != NULL);
    listErase(*head, (*head)->pre->clazz);
}

/*
    指定cls前插入
*/
void insert(listNode** head,cls clazz) {
    listNode* node = createList(clazz);
    listNode* pos = listSearch(head, clazz);

    pos->pre->next = node;
    node->pre = pos->pre;
    pos->pre = node;
    node->next = pos;
}

/*
    打印链表
*/
void listPrint(listNode* head) {
    assert(head != NULL); 
    listNode* phead = head->next;
    while (phead != head) {
        printf("Class:%d Mem:%d\n", phead->clazz.id, phead->clazz.memnum);
        phead = phead->next;
    }
}

第三步:在main函数中进行操作测试。

int main() {
    cls c1 = { 1,50 };
    cls c2 = { 2,60 };
    cls c3 = { 3,40 };
    cls c4 = { 4,40 };
    listNode* list = headInit();
    printf("==================\n尾插\n");
    pushBack(&list, c1);
    pushBack(&list, c2);
    listPrint(list);
    printf("==================\n头插\n");
    pushFront(&list, c3);
    pushFront(&list, c4);
    listPrint(list);
    printf("==================\n删c1\n");
    listErase(list, c1);
    listPrint(list);
    printf("==================\n头删\n");
    popFront(&list);
    listPrint(list);
    printf("==================\n尾删\n");
    popBack(&list);
    listPrint(list);
}

Output:

==================
尾插
Class:1 Mem:50
Class:2 Mem:60
==================
头插
Class:4 Mem:40
Class:3 Mem:40
Class:1 Mem:50
Class:2 Mem:60
==================
删c1
Class:4 Mem:40
Class:3 Mem:40
Class:2 Mem:60
==================
头删
Class:3 Mem:40
Class:2 Mem:60
==================
尾删
Class:3 Mem:40

小结

因其长度可变,内存不连续等优点,链表的运用将极大提高对多个同一结构的操作效率。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇