单链表

评论

前提知识

  • 结构体
  • typedef
  • 指针
  • 面向对象（后续）

基本概念

链表，linked list

一种数据结构，结构体+指针

1
2
3
4
5
6
7
8
9
10
11
//这是一个声明的内容，不是具体的
struct Button{
    //假设这里有很多关于按键的属性的项
    //……
    
    //在上面结构体声明的基础上，这里定义了新的按键结构体指针
    struct Button* next;
};

//定义
struct Button myButton;
结构体名称 结构体元素 指针
Button（也是该结构体的地址） 多个属性 新的Button结构体地址（即下一个按键结构体）
地址 数据 下一个的地址

相当于第一个记住第二个的地址，第二个记住第三个的地址，一直到最后一个，一般指向空NULL，这就是单链表。

如果最后一个指向第一个，则是循环链表；

如果每个结构体既指向前一个结构体，又指向后一个结构体，就是双向链表；

如果第一个与最后一个互相指向，则是双向循环链表。

另外，每个结构体有了新的名字，节点Node；第一个节点叫头节点，最后一个叫尾节点。

这里只记录单链表。

结构体指针与结构体

1
2
struct Button* next;	//定义一个结构体指针next，它是该结构体的地址
struct Button myButton; //定义一个结构体myButton

简化定义

typedef 起别名，简化结构体的定义

1
2
3
4
5
6
7
8
9
typedef struct Button {
	//xxx
    //yyy
    
	struct Button* next;
}Button;

//定义
Button myButton;

链表操作

单链表

  • 单链表=头节点+n个节点组成

    • 头节点：没有数据，只有指向下一个节点的指针
    • 尾节点：指针为空NULL

  • 定义

    1
    2
    3
    4
    typedef struct __LNode{
        int data;
        __LNode *next;
    }LNode, *LinkList;

  • 初始化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int InitLL(LinkList *L)//L是个二级指针,函数可以修改调用者传入的指针变量的值。
    {
        //(*L) 表示通过二级指针解引用，获取调用者传入的指针变量的值。
        (*L) = (LinkList)malloc(sizeof(LNode));//动态分配一块内存，大小为 LNode 类型的大小,并强转为(LinkList)
        if ((*L) == NULL) 
        {
        	return -1;  // 表示内存分配失败
    	}
        
        //(*L) 是头结点的地址
        (*L)->next = NULL;// (*L)->next表示访问头结点的next指针,使其设为NULL
        return 0;
    }

    • 调用方式

      1
      2
      LinkList L;
      InitLL(&L);  // L 现在指向一个头结点，头结点的 next 指针为 NULL

  • 创建链表

    • 头插法

      O(1)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      void InsertHead(LinkList *L, int data) 
      {
          LNode* newNode = (LNode*)malloc(sizeof(LNode)); // 创建新节点
          
          newNode->data = data;                           // 设置新节点的数据
          newNode->next = (*L)->next;                     // 新节点指向当前头结点的下一个节点
          
          (*L)->next = newNode;                           // 更新头结点的 next 指针
      }

    • 尾插法

      O(n)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void InsertTail(LinkList *L, int data) 
      {
          LNode* newNode = (LNode*)malloc(sizeof(LNode)); // 创建新节点
          newNode->data = data;                           // 设置新节点的数据
          newNode->next = NULL;                            // 新节点的 next 指针指向 NULL

          LNode* tail = *L;                                // 从头结点开始
          while (tail->next != NULL)                      // 遍历链表，找到最后一个节点
          {
              tail = tail->next;
          }
          tail->next = newNode;                            // 将新节点插入到链表尾部
      }

      O(1)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void InsertTailOptimized(LinkList *L, LNode** tail, int data) 
      {
          LNode* newNode = (LNode*)malloc(sizeof(LNode)); // 创建新节点
          newNode->data = data;                           // 设置新节点的数据
          newNode->next = NULL;                            // 新节点的 next 指针指向 NULL

          if (*tail == NULL) {                             // 如果链表为空
              (*L)->next = newNode;                        // 新节点成为第一个节点
          } else {
              (*tail)->next = newNode;                     // 将新节点插入到尾部
          }
          *tail = newNode;                                 // 更新尾指针
      }

  • 插入元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    //p为原链表，elem表示新数据元素，add表示新元素要插入的位置
    link * insertElem(link * p, int elem, int add) 
    {    
        link * temp = p;//创建临时结点temp    
        //首先找到要插入位置的上一个结点    
        for (int i = 1; i < add; i++) 
        {        
            temp = temp->next;        
            if (temp == NULL) 
            {            
                printf("插入位置无效\n");            
                return p;        
            }    
        }    
        //创建插入结点c    
        link * c = (link*)malloc(sizeof(link));    
        c->elem = elem;    
        //向链表中插入结点    
        c->next = temp->next;    
        temp->next = c;    
        return p;
    }

  • 删除元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //p为原链表，add为要删除元素的值
    link * delElem(link * p, int add) 
    {    
        link * temp = p;    //遍历到被删除结点的上一个结点    
        for (int i = 1; i < add; i++) 
        {        
            temp = temp->next;        
            if (temp->next == NULL) 
            {            
                printf("没有该结点\n");            
                return p;        
            }    
        }    
        link * del = temp->next;//单独设置一个指针指向被删除结点，以防丢失    
        temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域    
        free(del);//手动释放该结点，防止内存泄漏    
        return p;
    }

  • 查找元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //p为原链表，elem表示被查找元素、
    int selectElem(link * p,int elem)
    {
        //新建一个指针t，初始化为头指针 p    
        link * t=p;    
        int i=1;    
        //由于头节点的存在，因此while中的判断为t->next    
        while (t->next) 
        {        
            t=t->next;        
            if (t->elem==elem) 
            {            
                return i;        
            }        
            i++;    
    	}    
        //程序执行至此处，表示查找失败    
        return -1;
    }

示例代码

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h>
#include <stdlib.h>

typedef struct Link {
    int  elem;
    struct Link *next;
}link;

link * initLink();

//链表插入的函数，p是链表，elem是插入的结点的数据域，add是插入的位置
link * insertElem(link * p, int elem, int add);

//删除结点的函数，p代表操作链表，add代表删除节点的位置
link * delElem(link * p, int add);

//查找结点的函数，elem为目标结点的数据域的值
int selectElem(link * p, int elem);

//更新结点的函数，newElem为新的数据域的值
link *amendElem(link * p, int add, int newElem);

void display(link *p);

int main() 
{
    //初始化链表（1，2，3，4）
    printf("初始化链表为：\n");
    link *p = initLink();
    display(p);
    printf("在第4的位置插入元素5：\n");
    p = insertElem(p, 5, 4);
    display(p);
    printf("删除元素3:\n");
    p = delElem(p, 3);
    display(p);
    printf("查找元素2的位置为：\n");
    int address = selectElem(p, 2);
    if (address == -1) 
	{
        printf("没有该元素");
    }
    else 
	{
        printf("元素2的位置为：%d\n", address);
    }
    printf("更改第3的位置上的数据为7:\n");
    p = amendElem(p, 3, 7);
    display(p);
    return 0;
}


link * initLink() 
{
    link * p = (link*)malloc(sizeof(link));//创建一个头结点
    link * temp = p;//声明一个指针指向头结点，用于遍历链表
    //生成链表
    for (int i = 1; i < 5; i++) 
	{
        link *a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}

link * insertElem(link * p, int elem, int add) 
{
    link * temp = p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < add; i++) 
	{
        temp = temp->next;
        if (temp == NULL) 
		{
            printf("插入位置无效\n");
            return p;
        }
    }
    //创建插入结点c
    link * c = (link*)malloc(sizeof(link));
    c->elem = elem;
    //向链表中插入结点
    c->next = temp->next;
    temp->next = c;
    return  p;
}

link * delElem(link * p, int add) 
{
    link * temp = p;
    //遍历到被删除结点的上一个结点
    for (int i = 1; i < add; i++) 
	{
        temp = temp->next;
        if (temp->next == NULL) 
		{
            printf("没有该结点\n");
            return p;
        }
    }
    link * del = temp->next;//单独设置一个指针指向被删除结点，以防丢失
    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点，防止内存泄漏
    return p;
}

int selectElem(link * p, int elem) 
{
    link * t = p;
    int i = 1;
    while (t->next) 
	{
        t = t->next;
        if (t->elem == elem) 
		{
            return i;
        }
        i++;
    }
    return -1;
}

link *amendElem(link * p, int add, int newElem) 
{
    link * temp = p;
    temp = temp->next;//tamp指向首元结点
    //temp指向被删除结点
    for (int i = 1; i < add; i++) 
	{
        temp = temp->next;
    }
    temp->elem = newElem;
    return p;
}

void display(link *p) 
{
    link* temp = p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while (temp->next) 
	{
        temp = temp->next;
        printf("%d ", temp->elem);
    }
    printf("\n");
}

运行结果：

1
2
3
4
5
6
7
8
9
10
初始化链表为：
1 2 3 4
在第4的位置插入元素5：
1 2 3 5 4
删除元素3:
1 2 5 4
查找元素2的位置为：
元素2的位置为：2
更改第3的位置上的数据为7:
1 2 7 4

JiangHeStudent

个人简介。