双链表、链式栈、链式队列及实现

77 阅读 0 评论 51 点赞

我是靠谱客的博主笑点低电灯胆，最近开发中收集的这篇文章主要介绍双链表、链式栈、链式队列及实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、双链表

在单链表的基础上再增加一个指向它前驱的指针，就构成了双链表。

所以双链表有三个变量：数据信息info、前驱指针llink、后继指针rlink。

二、双链表操作和实现

由于双链表也为单链表的一种变型，一些相似的操作就没一一列举，可以参考数据结构（四）——单链表、带头结点的单链表、循环链表及其实现

1、数据结构

2、在i位置插入结点

3、在y元素后插入结点

4、删除值为x的结点

1、数据结构

01.typedef int datatype;  
02.  
03.typedef struct dlink_node{  
04.    datatype info;  
05.    dlink_node* llink;  
06.    dlink_node* rlink;  
07.}dnode;

2、在i位置插入结点

01.include"linklist.h"  
02.  
03.node* insert_link_list_index(node *head,int index,datatype x){  
04.    if(index<0){  
05.        printf("index errorn");  
06.        exit(1);  
07.    }  
08.    if(index == 0){         //在链表首插入   
09.        node *q = (node*) malloc(sizeof(node));  
10.        q->info = x;  
11.        if(!head){          //空表的情况   
12.            q->llink = NULL;  
13.            q->rlink = NULL;  
14.            head = q;  
15.            return head;  
16.        }  
17.        head->llink = q;    //非空链表首插入   
18.        q->rlink = head;  
19.        q->llink = NULL;  
20.        head = q;  
21.        return head;  
22.    }  
23.    else{  
24.        node *ptr = find_node(head,index-1);  
25.        node* q = (node*)malloc(sizeof(node));  
26.        q->info = x;  
27.        if(ptr->next){      //链表中插入     
28.            p->rlink = ptr->rlink;  
29.            ptr->rlink->llink = p;  
30.            ptr->rlink = p;  
31.            p->llink = ptr  
32.            return head;  
33.        }  
34.        ptr->rlink = p;      //链表尾插入   
35.        p->llink = ptr;  
36.        p->rlink = NULL;  
37.        return head;  
38.    }  
39.}

3、在y元素之后插入

01.#include"linklist.h"   
02.  
03.node* intsert_node_yx(node *head,datatype x,datatype y){  
04.    node *q=find_node(head,y);  
05.    if(!q){  
06.        printf("not found the node %dn");  
07.        return head;  
08.    }  
09.    node *p = (node*)malloc(sizeof(node));  
10.    p->info = x;  
11.    if(!q->rlink){            //最后一个结点   
12.        q->rlink = p;  
13.        p->llink = q;  
14.        p->rlink = NULL;  
15.        return head;  
16.    }  
17.    p->rlink = q->rlink;     //中间结点    
18.    q->rlink->llink = p;  
19.    q->rlink = p;  
20.    p->llink = q;  
21.    return head;  
22.}

4、删除值为x的结点

01.#include"linklist.h"   
02.  
03.node* del_link_list_node(node* head,datatype x){  
04.    if(!head){  
05.        printf("the list is emptyn");  
06.        return head;  
07.    }  
08.    node* ptr=head;  
09.    while(!ptr && ptr->info != x){  
10.        ptr=ptr->rlink;  
11.    }  
12.    if(!ptr){            //未找到数据   
13.        printf("no datan");  
14.    }else if(ptr == head && ptr->rlink){  //第一个就是，还有后继   
15.        head=ptr->rlink;                 
16.        ptr->rlink->llink = NULL;     //因为这步所以要判断是否有后继   
17.    }else if(ptr == head && !ptr->rlink){ //第一个就是，只有一个元素   
18.        head = NULL;  
19.    }   
20.    }else if(!ptr->rlink){          //链表的最后一个   
21.        ptr->llink->rlink = NULL;  
22.    }else{  
23.        ptr->llink->rlink = ptr->rlink;   //链表中间   
24.        ptr->rlink->llink = ptr->llink;  
25.    }  
26.    free(ptr);  
27.    return head;  
28.}

三、链式栈

栈的链式存储称为链式栈。它的插入和删除规定在单链表的同一端进行，栈顶指针用top表示。

1、输出各个结点的值

2、取得栈顶元素

3、入栈

4、出栈

1、输出各个结点的值

void display_link_list(node *stack){  
04.    if(!stack){  
05.        printf("the list is empty!n");  
06.    }else{  
07.        int i;  
08.        node *ptr = stack;  
09.        while(ptr){  
10.            printf("5%d",ptr->info);  
11.            ptr = ptr->next;  
12.        }  
13.    }  
14.}

2、取得栈顶元素

01.#include"linklist.h"   
02.  
03.node* get_top(node *stack){  
04.    if(!stack){  
05.        printf("the stack is emptyn");  
06.        return stack;  
07.    }  
08.    return stack->info;  
09.}

3、入栈

01.#include"linklist.h"   
02.  
03.node* push(node* stack,datatype x){  
04.    node *p = (node*)malloc(sizeof(node));  
05.    p->info = x;  
06.    p->next = stack;  //当stack为空时，则有p->next = NULL   
07.    stack = p;  
08.    return p;  
09.}

4、出栈

01.#include"linklist.h"   
02.  
03.node* pop(node *stack,datatype *x){  
04.    if(!stack){  
05.        printf("the stack is emptyn");  
06.        return stack;  
07.    }  
08.    node *p = stack;  
09.    stack=stack->next;  
10.    *x = p->info;  
11.    free(p);  
12.    return stack;  
13.}

四、链式队列

以队列形式存储的链式队列，插入和删除在单链表的不同端进行，队首和队尾指针存在一个数据结构中。

1、结构定义

2、建立一个空队列

3、判断是否为空

4、取得首节点值

5、输出各个结点

6、入列

7、出列

1、结构定义

01.typedef int datatype;  
02.  
03.typedef struct link_queue_node{  
04.    datatype info;  
05.    struct link_queue_node* next;  
06.}node;  
07.  
08.typedef struct queue{  
09.    node* front;  
10.    node* rear;  
11.}queue;

2、建立一个空队列

01.#include"linkqueue.h"   
02.  
03.queue* init_link_queue(){  
04.    queue *q = (queue*) malloc(sizeof(queue));  
05.    q->front = NULL;  
06.    q->rear = NULL;  
07.    return q;  
08.}

3、判断是否为空

01.#include"linkqueue.h"   
02.  
03.int is_empty_link_queue(queue *q){  
04.    return q->front? 0:1;  
05.}

4、取得首节点值

01.#include"linkqueue.h"   
02.  
03.datatype* get_head(queue *q){  
04.    if(!q){  
05.        printf("the queue is emptyn");  
06.        exit(1);  
07.    }  
08.    return q->front->info;  
09.}

5、输出各个结点

01.#include"linkqueue.h"   
02.  
03.void display_link_queue(queue *q){  
04.    if(!q){       
05.        printf("the queue is empty!n");          
06.    }else{  
07.        node *p = q->front;  
08.        while(p){  
09.            printf("%5d",p->info);  
10.            p=p->next;  
11.        }  
12.    }  
13.}

6、入列

01.#include"linkqueue.h"   
02.  
03.queue* en_list_queue(queue *q,datatype x){  
04.    node* p = (node*)malloc(sizeof(node));  
05.    p->info = x;  
06.    p->next = NULL;  
07.    if(!q->front){  
08.        q->front = p;  
09.        q->rear = p;  
10.    }else{  
11.        rear->next = p;  
12.        rear = p;  
13.    }  
14.    return q;  
15.}

7、出列

01.#include"linkqueue.h"   
02.  
03.queue* del_link_queue(queue *q,datatype *x){  
04.    if(!q->front){  
05.        printf("the queue is emptyn");  
06.        return q;  
07.    }  
08.    node *p = q->front;  
09.    if(q->front == q->rear){  
10.        q->front=q->rear=NULL;  
11.    }else{  
12.        q->front = p->next;  
13.    }  
14.    *x = p->info;  
15.    free(p);  
16.    return q;  
17.}

转载：点击打开链接