服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言实现带头结点的链表的创建、查找、插入、删除操作

C语言实现带头结点的链表的创建、查找、插入、删除操作

2021-02-02 14:24C语言程序设计 C/C++

这篇文章主要介绍了C语言实现带头结点的链表的创建、查找、插入、删除操作方法,对于了解数据结构中链表的各项操作有很好的借鉴价值,需要的朋友可以参考下

本文实例讲述了C语言实现带头结点的链表的创建、查找、插入、删除操作。是数据结构中链表部分的基础操作。分享给大家供大家参考。具体方法如下:

?
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node
{
  int data;
  struct node* next;// 这个地方注意结构体变量的定义规则
} Node, *PNode;
 
Node* createLinklist(int length)
{
  int i = 0;
  PNode pHeader = NULL;
  PNode pTail = NULL;
  PNode pTemp = NULL;
  printf("create\n");
 
  pHeader = (PNode)malloc(sizeof(Node));// 申请头结点
  if (!pHeader)
  {
    exit(-1);
  }
  pHeader->next = NULL;
 
  for (i = 0; i < length; i++)
  {
    pTemp = (PNode)malloc(sizeof(Node));// 用malloc要包含头文件
    if (!pTemp)
    {
      exit(-1);
    }
    pTemp->data = i*10;
    pTemp->next = NULL;
    if (!pHeader->next)
    {
      // 第一个结点是空的,则先连接第一个结点
      pHeader->next = pTemp;
    }
    else
    {
      pTail->next = pTemp;
    }
    pTail = pTemp;
  }
  return pHeader;
}
 
Node* search(PNode pHeader, int k)
{
  PNode p = pHeader->next;
  int i = 1;
  printf("search\n");
  while(p && (i < k))
  {
    p = p->next;
    i++;
  }
  if (p && (i == k)) // 这步的i == k是必须的,
  // 因为如果一开始的时候 i就 >= k并且pHeader->next还不为NULL这一步就会必过,导致返回的是第一个元素的值
  {
    return p;
  }
  return NULL;
}
 
int insert(PNode pHeader, PNode pNew, int k)
{
  PNode p = NULL;
  printf("insert\n");
  if ( 1 == k )
  {
    p = pHeader;
  }
  else
  {
    printf("==>");
    p = search(pHeader, k-1);
  }
  if (p)
  {
    // 带头结点和不带头结点的主要区别之一就在这
    // 如果不带头结点,那么在第一个位置插入结点的操作应该是
    // pNew->next = p;
    // p = pNew;
    // 带头结点的操作如下
    pNew->next = p->next;
    p->next = pNew;
    return 1;
  }
  return 0;
}
 
int deleteNode(PNode pHeader, int k)
{
  PNode p = NULL;
  printf("deleteNode\n");
  if (1 == k)
  {
    p = pHeader->next;
  }
  else
  {
    printf("==>");
    p = search(pHeader, k-1);
  }
  if (p && p->next)
  {
    // 不带头结点的操作时删除第一个结点的操作
    // Node* temp = p;
    // p = p->next;
    // free(temp);
    // 带头结点的操作如下
    PNode temp = p->next;
    p->next = temp->next;
    free(temp);
    return 1;
  }
  else
  {
    printf("Not Found\n");
    return 0;
  }
}
 
void print(PNode pHeader)
{
  PNode p = pHeader->next;
  printf("print\n ");
  while(p)
  {
    printf("%4d ", p->data);
    p = p->next;
  }
  putchar('\n');
}
 
void freeList(PNode pH)
{
  PNode p = NULL;
  printf("freeList\n");
  while(NULL != pH)
  {
    p = pH;
    pH = pH->next;
    printf("%4d be freed\n", p->data);
    free(p);
  }
}
 
int main(void)
{
  PNode pHeader = NULL;// C和C++中判断指针为空都是用NULL宏(全大写)
  PNode pNew = NULL;
  PNode result = NULL;
  pHeader = createLinklist(10);
  print(pHeader);
  result = search(pHeader, 5);
  if ( result )
  {
    printf("%d\n", result->data);
  }
  else
  {
    printf("Not Found\n");
  }
  pNew = (PNode)malloc(sizeof(Node));
  if (!pNew)
  {
    exit(-1);
  }
  pNew->data = 100;
  pNew->next = NULL;
  insert(pHeader, pNew, 5);
  print(pHeader);
  deleteNode(pHeader, 12);
  print(pHeader);
  freeList(pHeader);
  return 0;
}

上述实例备有较为详尽的注释,相信不难理解。希望本文所述对大家C程序数据结构与算法设计有所帮助。

延伸 · 阅读

精彩推荐