现在的位置: 首页 > 综合 > 正文

单链表、带头结点的单链表、循环单链表 以及其操作实现

2013年10月12日 ⁄ 综合 ⁄ 共 5798字 ⁄ 字号 小 中 大 ⁄ 评论关闭

一、 链式存储

      以结点的形式存储数据。除了存放一个结点的信息外，还需附设指针。

           

 

    数据在内存中存储是不连续的，每个结点只能也只有它能知道下一个结点的存储位置。

 

 

二、单链表

  单链表是线性表链式存储的一种，其储存不连续。单链表的数据结构中包含两个变量：数据和指向下一结点的指针。一个结点只知道下一个结点的地址。一个单链表必须有一个头指针，指向单链表中的第一个结点。否则链表会在内存中丢失。

三、单链表的操作和实现

1、单链表定义

2、创建一个空链表

3、打印链表

4、查找数据值为x的结点

5、查找索引值为index的结点

6、在i位置插入一个结点

7、在数据y之后插入一个x结点

8、删除i位置的结点

9、删除值为x的结点

 

1、单链表定义

01.typedef int datatype;  
02.  
03.typedef struct link_node{  
04.    datatype info;  
05.    struct link_node* next;  
06.}node;

 

2、创建一个空链表

01.#include"linklist.h"   
02.  
03.node* init_linklist(){  
04.    return NULL;  
05.}

3、打印链表

01.#include"linklist.h"   
02.  
03.void display_link_list(node *head){  
04.    if(head == NULL){  
05.        printf("the list is empty!\n");  
06.    }else{  
07.        node *ptr = head;  
08.        while(ptr){  
09.            printf("5%d",ptr->info);  
10.            ptr = ptr->next;  
11.        }  
12.    }  
13.}

4、查找数据值为x的结点

01.#include"linklist.h"   
02.  
03.node *find_node(node* head,datatype x){  
04.    node* ptr= head;  
05.    while(ptr && ptr->info != x)  
06.        ptr= ptr->next;  
07.    return ptr;  
08.}

5、查找索引值为index的结点

01.#include"linklist.h"   
02.  
03.node* find_index(node* head,int index){  
04.    node *ptr = head;  
05.    int pos = 0;  
06.    if(index<0){  
07.        printf("Index Error\n");  
08.        exit(1);  
09.    }  
10.    while(ptr && pos != index){  
11.        ptr=ptr->next;  
12.        pos++;  
13.    }  
14.    return ptr;  
15.}

6、在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 error\n");  
06.        exit(1);  
07.    }  
08.    if(index == 0){          //在头插入元素，不用判断链表是否为空   
09.        node *q = (node*) malloc(sizeof(node));  
10.        q->info = x;  
11.        q->next = head;  
12.        head = q;  
13.        return head;  
14.    }  
15.    else{  
16.        node *ptr = find_node(head,index-1);  
17.        node* q = (node*)malloc(sizeof(node));  
18.        q->info = x;  
19.        q->next = ptr->next;  
20.        ptr->next = q;  
21.        return head;  
22.    }  
23.}

7、在数据y之后插入一个x结点 

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 %d\n");  
07.        return head;  
08.    }  
09.    node *p = (node*)malloc(sizeof(node));  
10.    p->info = x;  
11.    p->next= q->next;  
12.    q->next = p;  
13.    return head;  
14.}

 

8、删除i位置的结点

01.#include"linklist.h"   
02.  
03.node* del_link_list_index(node* head,int index){  
04.    if(!head){  
05.        printf("the list is empty\n");  
06.        return head;  
07.    }  
08.    node* p=head,*q=NULL;  
09.    if(index == 0){          //第一个元素   
10.        head = head->next;  
11.    }else{  
12.        p=find_index(head,index-1);      //上面定义的第5个函数   
13.        if(p && p->next){  
14.            q = p->next;  
15.            p->next= q->next;  
16.        }else{  
17.            printf("the index is not exit\n");  
18.            return head;  
19.        }  
20.    }  
21.    free(q);  
22.    return head;  
23.}

9、删除值为x的结点

01.#include"linklist.h"   
02.  
03.node* del_link_list_node(node* head,datatype x){  
04.    if(!head){  
05.        printf("the list is empty\n");  
06.        return head;  
07.    }  
08.    node* ptr=head,*pre=NULL;  
09.    while(!ptr && ptr->info != x){  
10.        pre = ptr;  
11.        ptr=ptr->next;  
12.    }  
13.    if(!ptr){                  //没找到   
14.        printf("no data\n");  
15.    }else if(pre){            //第一个就是   
16.        head=ptr->next;  
17.    }else{                    //链表中的某个位置   
18.        pre->next= ptr->next;  
19.    }  
20.    free(ptr);  
21.    return head;  
22.}

三、带头结点的单链表

    头结点的单链表中，head指示的是所谓的头结点，它不是实际的结点，不是用来储存数据的。可以这样理解，头结点牺牲了一个储存单元，来化简代码，因为头不可能为空了。或者用来存储一些全局量，比如链表长度，这要依具体需求而定。

     

 

 

四、带头结点的单链表操作实现

因为结构有变化，所以实现有变化但是变化并不多。

1、创建一个空链表

2、打印链表

3、删除值为x的结点

 

1、创建一个空链表

01.#include"linklist.h"   
02.  
03.node* init_hlink_list(){  
04.    node *head;  
05.    head=(node*)malloc(sizeof(node));  
06.    head->next=NULL;  
07.    return head;  
08.}

2、打印链表

01.#include"linklist.h"   
02.  
03.void display_link_list(node *head){  
04.    if(head->next == NULL){  
05.        printf("the list is empty!\n");  
06.    }else{  
07.        node *ptr = head->next;  
08.        while(ptr){  
09.            printf("5%d",ptr->info);  
10.            ptr = ptr->next;  
11.        }  
12.    }  
13.}

3、删除值为x的结点

01.#include"linklist.h"   
02.  
03.node* del_link_list_node(node* head,datatype x){  
04.    if(!head->next){  
05.        printf("the list is empty\n");  
06.        return head;  
07.    }  
08.    node* ptr=head->next,*pre=head;  
09.    while(!ptr && ptr->info != x){       
10.        pre = ptr;  
11.        ptr=ptr->next;  
12.    }  
13.    if(ptr){                
14.        printf("no data\n");  
15.    }else {          //两种情况合并到一起了   
16.        pre->next= ptr->next;  
17.    }  
18.    free(ptr);  
19.    return head;  
20.}

五、循环单链表

    链表中最后一个结点的指针指向第一个结点。在这个链表中，若首指针为head，最后一个结点的判断条件为：p->next == head。

 

六、循环单链表的操作和实现

1、打印链表

2、获得最后一个结点

3、找到值为x的结点

4、在i位置插入一个结点

5、在数据y之后插入一个x结点

6、删除值为x的结点

1、打印链表

01.#include"linklist.h"   
02.  
03.void display_link_list(node *head){  
04.    if(head == NULL){  
05.        printf("the list is empty!\n");  
06.    }else{  
07.        node *ptr = head->next;    
08.        printf("%5d",head->info);  
09.        while(ptr != head){    //如果采用ptr->next != head 的方法无法判断最后一个元素！   
10.            printf("5%d",ptr->info);  
11.            ptr = ptr->next;  
12.        }  
13.    }  
14.}

2、获得最后一个结点

01.#include"linklist.h"   
02.  
03.node* get_rear(node *head){  
04.    node* ptr = head;  
05.    while(ptr &&ptr->next != head) {  
06.        ptr= ptr->next;  
07.    }  
08.    return head;  
09.}

3、找到值为x的结点

01.#include"linklist.h"   
02.  
03.node *find_node_clink(node* head,datatype x){  
04.    node*ptr = head->next;  
05.    if(head->info != x){   //如果第一个元素就是就直接走else返回   
06.        while(ptr != head && ptr->info != x){  
07.            ptr= ptr->next;  
08.        }  
09.        if(ptr == head){   //处理没有找到的情况   
10.            ptr = NULL;  
11.        }   
12.        return ptr;  
13.    }else{  
14.        return head;  
15.    }  
16.}

 

4、在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 error\n");  
06.        exit(1);  
07.    }  
08.    if(index == 0){        //在链表头插入   
09.        node *p = (node*) malloc(sizeof(node));  
10.        node *rear;  
11.        p->info = x;  
12.        if(!head){        //空链表的处理   
13.            head = p;  
14.            p->next = head;  
15.            return head;  
16.        }else{            //正常在链表头插入的处理   
17.            rear = get_rear(head);  
18.            rear->next = p;  
19.            p->next = head;  
20.            head = p  
21.            return head;  
22.        }  
23.    }  
24.    else{                 //在链表中插入的处理   
25.        node *ptr= find_node(head,index-1);  
26.        node* q = (node*)malloc(sizeof(node));  
27.        q->info = x;  
28.        q->next = ptr->next;  
29.        ptr->next = q;  
30.        return head;  
31.    }  
32.}

5、在数据y之后插入一个x结点

01.#include"linklist.h"   
02.  
03.node* intsert_node_yx(node *head,datatype x,datatype y){  
04.    node *q=find_node_clink(head,y);         //此处调用的是第3个函数   
05.    if(!q){  
06.        printf("not found the node %d\n");  
07.        return head;  
08.    }  
09.    node *p = (node*)malloc(sizeof(node));  
10.    p->info = x;  
11.    p->next= q->next;  
12.    q->next = p;  
13.    return head;  
14.}

6、删除值为x的结点

01.#include"linklist.h"   
02.  
03.node* del_link_list_node(node* head,datatype x){  
04.    if(!head){  
05.        printf("the list is empty\n");  
06.        return head;  
07.    }  
08.    node* ptr=head,*pre=NULL;  
09.    while(ptr->next != head && ptr->info != x){  
10.        pre = ptr;  
11.        ptr=ptr->next;  
12.    }  
13.    if(ptr->info != x){          //判断最后一个元素的同时也判断了是否找到元素   
14.        printf("no data\n");  
15.    }else if(!pre){              //第一个元素就是x   
16.        pre = get_rear(head);    //不要忘了尾指针指头   
17.        head=ptr->next;  
18.        pre->next =ptr;  
19.    }else{                       //在链表中的情况   
20.        pre->next= ptr->next;  
21.    }  
22.    free(ptr);  
23.    return head;  
24.}

转载：点击打开链接

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞