C链表一——链表增删改查以及初始化的头插法与尾插法

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

线性表的链式存储又称为链表（物理实现方式）；

链式存储是最常用的存储方式之一。它不仅可以用来表示线性表，而且可以用来表示各种非线性的数据结构；

链表又可分为单链表、双链表、循环链表等。

一：单链表

所谓单链表是指数据结点是单向排列的。它包括两个域，一个信息域用于存放数据，一个指针域用于存放下个结点的地址；

单链表中结点类型的描述如下:

struct Node
{
    ElemType data_;  
    Node *next_;  
};

利用单链表可以解决顺序表需要大量的连续的存储空间的缺点，但是单链表附加了指针域，也带来了浪费存储空间的缺点。
注意：本文所有程序都是用“头指针”来表示一个单链表，而没有用带头结点的单链表。

头指针：是指向单链表第一个结点的指针；

头结点：单链表第一个结点之前附加的一个结点，此时，头指针指向头结点，头结点的指针域指向单链表的第一个结点；

结点的定义以及打印函数：

//结点声明
typedef struct tag
{
    int Nnum_;
    struct tag *Nnext_;
}Node, *pNode;

//打印函数
void link_print(pNode phead)
{
    while(phead != NULL)
    {
        printf("Node_value:%4d\n", phead->Nnum_);
        phead = phead->Nnext_;
    }
}

View Code

一：利用尾插法初始化单链表

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct tag
{
    int Nnum_;
    struct tag *Nnext_;
}Node, *pNode;


void link_print(pNode phead)
{
    while(phead != NULL)
    {
        printf("Node_value:%4d\n", phead->Nnum_);
        phead = phead->Nnext_;
    }
}

void link_init_tail(pNode *phead, int size) //传的是地址
{
    pNode pNew = NULL;
    pNode pTail = NULL;

    while( size > 0)
    {
        //申请内存
        pNew = (pNode)malloc(sizeof(Node)); //注意这里为何不用pNode而用Node，因为sizeof(pNode) = 4
        //赋值
        pNew->Nnum_ = rand()%1000;
        //插入链表
        if(*phead == NULL) //链表为空时
        {
            *phead = pNew;//连接新的结点
            pTail = pNew;
        }
        else//不为空
        {
            pTail->Nnext_ = pNew ; //连接新的结点
             pTail = pNew; //改名字
        }
        
        size --;
    }
}

int main(int argc, char const *argv[])
{
    srand(time(NULL));
    pNode phead = NULL;
    link_init_tail(&phead, 10);

    link_print(phead);

    return 0;
}

View Code

二：利用头插法初始化单链表

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <time.h>
 5 
 6 typedef struct tag
 7 {
 8     int Nnum_;
 9     struct tag *Nnext_;
10 }Node, *pNode;
11 
12 
13 void link_print(pNode phead)
14 {
15     while(phead != NULL)
16     {
17         printf("Node_value:%4d\n", phead->Nnum_);
18         phead = phead->Nnext_;
19     }
20 }
21 
22 void link_init_head(pNode *phead, int size)
23 {
24     pNode pNew = NULL;
25 
26     while( size > 0)
27     {
28         //申请内存
29         pNew = (pNode)malloc(sizeof(Node)); //注意这里为何不用pNode而用Node，因为sizeof(pNode) = 4
30         //赋值
31         pNew->Nnum_ = rand()%1000;
32         //插入链表
33         if(*phead == NULL)
34         {
35             *phead = pNew;//连接新的结点;    
36         }
37         else
38         {
39             pNew->Nnext_ = *phead;//将pNew的next域置为phead
40             *phead = pNew;
41         }
42         size --;
43     }
44 }
45 
46 int main(int argc, char const *argv[])
47 {
48     srand(time(NULL));
49     pNode phead = NULL;
50     link_init_head(&phead, 10);
51 
52     link_print(phead);
53     return 0;
54 }

View Code

三：删除结点

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <time.h>
 5 #include <assert.h>
 6 
 7 typedef struct tag
 8 {
 9     int Nnum_;
10     struct tag *Nnext_;
11 }Node, *pNode;
12 
13 void link_print(pNode phead)
14 {
15     int i= 0;
16     while(phead != NULL)
17     {
18         printf("%3d", phead->Nnum_);
19         phead = phead->Nnext_;
20         ++i;
21     }
22     printf("i:%d\n", i);
23 }
24 
25 void link_init_tail(pNode *phead, int size) //传的是地址
26 {
27     pNode pNew = NULL;
28     pNode pTail = NULL;
29 
30     while( size > 0)
31     {
32         //申请内存
33         pNew = (pNode)malloc(sizeof(Node)); //注意这里为何不用pNode而用Node，因为sizeof(pNode) = 4
34         //赋值
35         pNew->Nnum_ = rand()%50;
36         //插入链表
37         if(*phead == NULL) //链表为空时
38         {
39             *phead = pNew;//连接新的结点
40             pTail = pNew;
41         }
42         else//不为空
43         {
44             pTail->Nnext_ = pNew ; //连接新的结点
45              pTail = pNew; //改名字
46         }        
47         size --;
48     }
49 }
50 
51 //该函数只能删除一个相同的结点，如果想要删除所有与num相等的结点值，则直接在while循环里执行删除操作即可
52 void link_delete(pNode *phead, int num)//num表示要删除元素的数值
53 {
54     assert( phead != NULL); //非空
55     pNode pPre = NULL; 
56     pNode pCur = *phead;
57 
58     while( pCur != NULL) //遍历链表找到要删除元素对的位置
59     {
60         if( pCur->Nnum_ == num) //找到
61             break;
62         else 
63             {
64                 pPre = pCur;
65                 pCur = pCur->Nnext_;
66             }
67     }    
68 
69     if( pPre == NULL)//删除的是头结点
70     {
71         pNode tmp = *phead;
72         *phead = (*phead)->Nnext_;
73         free(tmp);
74         tmp = NULL;
75     }
76     else if(pCur != NULL)//删除的是其余结点
77     {    
78         pNode tmp = pCur;
79         pPre->Nnext_ = pCur->Nnext_;
80         free(tmp);
81         tmp = NULL;
82     }
83     else //没找到
84         printf("find no element\n");
85 }
86 
87 int main(int argc, char const *argv[])
88 {
89     srand(time(NULL));
90     pNode phead = NULL;
91     link_init_tail(&phead, 20);
92     link_print(phead);
93 
94 
95     link_delete(&phead, 5);
96     link_print(phead);
97 
98     return 0;
99 }

View Code

四：按照从小到大的顺序依次插入结点：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <time.h>
 5 
 6 typedef struct tag
 7 {
 8     int Nnum_;
 9     struct tag *Nnext_;
10 }Node, *pNode;
11 
12 
13 void link_print(pNode phead)
14 {
15     while(phead != NULL)
16     {
17         printf("%4d", phead->Nnum_);
18         phead = phead->Nnext_;
19     }
20     printf("\n");
21 }
22 
23 void link_insert_by_sort(pNode *phead, int size)
24 {
25     pNode pNew = NULL;
26     pNode pCur, pPre;
27 
28     while( size > 0 )
29     {
30         pNew = (pNode)malloc(sizeof(Node));
31         pNew->Nnum_ = rand()%1000;
32 
33         pPre = NULL;
34         pCur = *phead;
35         while( pCur != NULL)
36         {
37             if( pNew->Nnum_ > pCur->Nnum_) //按照从小到大排序
38             {
39                 pPre = pCur;
40                 pCur = pCur->Nnext_;
41             }
42             else //找到位置
43                 break;
44         }
45         //找到的位置在头部
46         if( pPre == NULL)
47         {
48             pNew->Nnext_ = *phead;
49             *phead = pNew;
50         }else//位置在中间或者尾部
51         {
52             pPre->Nnext_ = pNew;
53             pNew->Nnext_ = pCur;
54         }
55         size --;
56     }
57 }
58 
59 int main(int argc, char const *argv[])
60 {
61     srand(time(NULL));
62     pNode phead = NULL;
63     link_insert_by_sort(&phead, 10);
64 
65     link_print(phead);    
66 
67     return 0;
68 }