数据结构——链表

镇楼图

Pixiv:飛者

〇、链表构建前的细节问题

顺序表构建时一定需要一个确定的长度吗？

顺序表也可以采用类似链表的方式增加节点，也就是每新增一个节点就开辟一块内存(realloc)

这样顺序表可以不必增加len参数

是否带头节点？

在链表中通常要带头节点指明整个结构。

如果不带，在涉及到表头的操作时则需要修改首元素地址增加额外不必要的负担

是否循环？

和顺序表一样，可做可不做

单链表还是双链表？

链表的索引关系是通过指针来完成的

单链表只有一个指针会使得索引关系具有单向性，即除表头表尾每个节点都只有后继而无前驱

双链表存在两个指针会使得索引关系具有双向性，即除表头表尾每个节点都有后继和前驱

（个人观点：顺序表是除表头表尾都有前驱后继，不过从图的观点来看，顺序表可以认为是一种完全图）

选择什么参数？

这里我推荐加上cnt当前长度的参数

一、单链表

typedef struct{
    int value;
}element,*Element;

typedef struct __llnode{
    element data;//数据域
    struct __llnode *next;//指针域
}*llist_head,*llist_node,llist_size;

typedef struct{
	llist_head head;
    int cnt;
}llist;
/*一般情况得到上面的即可
  不过我增加了额外参数需要进一步封装

基本操作

(1)创建单链表

void llist_create(llist &L){
    //作用：创建链表
    L.cnt = 0;
    L.head = (llist_head)malloc(sizeof(llist_size));
    L.head->next = NULL;
}

(2)输入/输出

void llist_input(llist &L,int n){
    //作用：输入n个数据
    if(n < 0)return;
    llist_node p = L.head;
    L.cnt += n;
    while(p->next)p = p->next;
    while(n--){
        llist_node newnode = new llist_size;
        newnode->next = NULL;
        p->next = newnode;
        scanf("%d ",&newnode->data.value);
        p = p->next;
    }
}

void llist_output(llist &L){
    //作用：输出链表
    llist_node p = L.head->next;
    while(p){
        printf("%d ",p->data.value);
        p = p->next;
    }
    printf("\n");
}

(3)判断单链表是否为空

bool llist_ifempty(llist &L){
    //作用：判断链表是否为空
	return (L.head->next) ? true : false ;
}

(4)获取单链表长度（假设不存在cnt参数）

int llist_length(llist &L){
    //作用：获取链表当前长度
    int count = 0;
    llist_node p = L.head->next;
    while(p){
        count++;
        p = p->next;
    }
    return count;
}

(5)前/后.插入位序为i的参数

void llist_insertpre1(llist &L,int pos,element e){
    //作用：前插入元素e
    if(pos < 1 || pos > L.cnt+1){
        printf("错误：超出范围");
        return;
    }
    llist_node p = L.head;
    //一：pos-1将前插变为后插
    while(pos---1)p = p->next;
    llist_node newnode = (llist_node)malloc(sizeof(llist_size));
    newnode->data = e;
    newnode->next = p->next;
    p->next = newnode;
    L.cnt++;
}

void llist_insertpre2(llist L,int pos,element e){
    //作用：前插入元素e
    if(pos < 1 || pos > L.cnt){
        printf("错误：超出范围");
        return;
    }
    llist_node p = L.head;
    /*二：假设得到的就是当前元素p
    然后需要前插newnode元素
    可以交换p和newnode的数据域
    这样就变成了如何在newnode后插p的问题
    在已知p指针信息的情况下
    该算法时间复杂度降低为O(1)
    不过缺点是pos范围从原来的[1,n+1]
    变为[1,n](n > 0)或?(n = 0)
    */
    while(pos--)p = p->next;
    llist_node newnode = (llist_node)malloc(sizeof(llist_size));
    newnode->data = p->data;
    p->data = e;
    newnode->next = p->next;
    p->next = newnode;
    L.cnt++;
}

void llist_insertpost(llist &L,int pos,element e){
    //作用：后插入元素e
    if(pos < 0 || pos > L.cnt){
        printf("错误：超出范围");
        return;
    }
    llist_node p = L.head;
    for(int i = 0;i < pos;i++)p = p->next;
    llist_node newnode = (llist_node)malloc(sizeof(llist_size));
    newnode->data = e;
    newnode->next = p->next;
    p->next = newnode;
    L.cnt++;
}

(6)删除位序为i的元素

void llist_delete(llist L,int pos){
    //作用：删除元素e
    if(pos < 1 || pos > L.cnt){
        printf("错误：超出范围");
        return;
    }
    llist_node p = L.head,d = L.head->next;
    while(pos---1){
        p = p->next;
        d = d->next;
    }
    p->next = d->next;
    free(d);
    L.cnt--;
}
/*还有一种算法可以只得到要删除元素的前一位p
然后只需要删除p的后继即可，无需前驱

其他操作

(1)反转单链表

void llist_reverse(llist &L){
    //最简单的是直接递归逆向输出（不过多少不会有人接受这种算法）
    //这里采用改变索引关系得到
    llist_node p1 = L.head;
    llist_node p2 = L.head->next;
    llist_node t = NULL;
    while(p2){
        t = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = t;
    }
    L.head->next->next = NULL;
    L.head->next = p1;
}

(2)合并两个有序链表

void llist_union(llist_node &p1,llist_node &p2,llist &L3){
    /*这个算法我已经在顺序表中阐述过了
    不过本次采用递归思路
    下一次队列时我会阐述n次选择思想
    */
    //注：L3必须为空链表
    if(!p1 && !p2)return;
    if(!p1){
        llist_insertpost(L3,L3.cnt,p2->data);
        llist_union(p1,p2->next,L3);
    }else if(!p2){
        llist_insertpost(L3,L3.cnt,p1->data);
        llist_union(p1->next,p2,L3);
    }else{
        if(p1->data.value > p2->data.value){
            llist_insertpost(L3,L3.cnt,p1->data);
            llist_union(p1->next,p2,L3);
        }else{
            llist_insertpost(L3,L3.cnt,p2->data);
            llist_union(p1,p2->next,L3);
        }
    }
}

二、做循环处理的链表

这里不再使用代码演示，仅仅谈我对于循环处理的看法

循环处理即最后一个元素的指针不指向NULL，而是指向头节点或第一个节点

大幅提高遍历的灵活性，可以从任意节点开始遍历得到整个表，如约瑟夫环问题

涉及到与表尾与表头的处理上有所变化，比如判断空表、是否达到表尾等都有所变化

不过一般情况是不需要做循环处理的

三、双链表

单链表在索引时只具有单向性，在部分操作上稍麻烦（如删除元素时若不做特殊处理就无法得到前驱的尴尬）

双链表在索引上具有双向性，比如得知某一节点就能推出前驱和后继

typedef struct{
    int value;
}element,*Element;

typedef struct __llnode{
    element data;//数据域
    struct __llnode *prior,*next;//指针域
}*llist_head,*llist_node,llist_size;

typedef struct{
	llist_head head;
    int cnt;
}llist;

基本操作

(1)创建双链表

void llist_create(llist &L){
    L.cnt = 0;
    L.head = (llist_head)malloc(sizeof(llist_size));
    L.head->prior = NULL;
    L.head->next = NULL;
}

(2)输入/输出

void llist_input(llist &L,int n){
    //作用：输入n个数据
    if(n < 0)return;
    llist_node p = L.head;
    L.cnt += n;
    while(p->next)p = p->next;
    while(n--){
        llist_node newnode = new llist_size;
        newnode->next = NULL;
        newnode->prior = p;
        p->next = newnode;
        scanf("%d ",&newnode->data.value);
        p = p->next;
    }
}

(3)判断是否为空

bool llist_ifempty(llist &L){
    //作用：判断链表是否为空
	return (L.head->next) ? true : false ;
}

(4)前/后插入

void llist_insertpre(llist &L,int pos,element e){
    //作用：前插入元素e
    if(pos < 1 || pos > L.cnt+1){
        printf("错误：超出范围");
        return;
    }
    llist_node p = L.head;
    while(pos--)p = p->next;
    llist_node newnode = new llist_size;
    newnode->data = e;
    newnode->prior = p->prior;
    newnode->next = p;
    p->prior->next = newnode;
    p->prior = newnode;
    L.cnt++;
}

void llist_insertpost(llist &L,int pos,element e){
    //作用：后插入元素e
    if(pos < 0 || pos > L.cnt){
        printf("错误：超出范围");
        return;
    }
    llist_node p = L.head;
    for(int i = 0;i < pos;i++)p = p->next;
    llist_node newnode = (llist_node)malloc(sizeof(llist_size));
    newnode->data = e;
    newnode->prior = p;
    newnode->next = p->next;
    p->next->prior = newnode;
    p->next = newnode;
    L.cnt++;
}

(5)删除

void llist_delete(llist L,int pos){
    //作用：删除元素e
    if(pos < 1 || pos > L.cnt){
        printf("错误：超出范围");
        return;
    }
    llist_node p = L.head;
    while(pos--)p = p->next;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    L.cnt--;
}

参考教程

郝斌 数据结构

C语言技术网 数据结构

参考书籍

《数据结构与算法分析 C语言描述》