`
langzhe
  • 浏览: 286729 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

关于单链表的思考

    博客分类:
  • c
 
阅读更多

当我看了这个例子后http://learn.akae.cn/media/ch26s01.html

感觉很简单没什么特别的(这感觉往往遗漏很多细节)。

例子中用了static 定义了关键字 static link head = NULL;

看到后我就想用非static来重写单链表。

习惯了Erlang的函数编程,在定义C语言中的函数时刻意不用指针去实现,为了进一步理解代码还刻意不用typedef定义变量。可是奋斗了很久也没实现。

不得不用取地址方式,最后也没实现。不得不用指针了,这样就造成了传输指针又返回指针了,对于C 语言这可是多此一举。

创建链表时是从表头插入的

 75 struct node * insert(struct node *node, char ch)

 76 {             

 77     struct node *node1 = create_node(ch); 

 78     node1->next = node;                                                                                                                                                                                         

 79     return node1;

 80 }

 81 

 82 struct node * create_node(char ch)

 83 {

 84     struct node *node = malloc(sizeof *node);

 85     node->element = ch;

 86     node->next = NULL;

 87     return node; 

 88 }

 

 

写完创建,又写了个删除但是删除不掉

154 struct node * no_delete_node(struct node *head, char ch)

155 {

156 

157     printf("no_delete_node2 head->data=%c\n", ch);                                                                                      

158     struct node *ret = head;

159     struct node *pre = head;                                                                                                                      

160     for(;pre; pre = pre->next){

161         if(pre->element==ch){

162             pre = pre->next;

163             return ret;

164         }

165     }

166     return ret;

167 }   

 

后来改成 (这代码实在在冗余了)就可以删除了,

关键就是 142 行                head->next = pre ->next->next;     这句代码实现了删除

125 struct node * delete_node(struct node *head, char ch)

126 {

127     printf("delete_node head->element=%c\n", head->element);

128     struct node *ret = head;

129     struct node *pre = head;

130     if(head == NULL){

131         return head; 

132     }else{

133         if(head->element == ch){

134             head = head ->next;

135             //ret = head->next;

136             return ret;

137         }

138         while(head->next != 0){

139             if(pre->next-> element == ch){

140                 struct node *node = pre->next;

141                 free_node(node);

142                head->next = pre ->next->next;    

143                 printf("found del %c\n", head ->element);

144             }else{

145                 printf("notfound del%c\n", head ->element);

146             }

147             pre = head->next;

148         }

149     }

150     return ret;

151 } 

152 

就可以删除了,

 

最后改成这样实现

171 struct node * delete_node2(struct node *head, char ch)

172 {   

173     

174     printf("delete_node2 head->data=%c\n", ch);                                                                                      

175     struct node **pre = &head;                                                                                                                      

176     for(;*pre; pre = &(*pre)->next){

177         if((*pre)->element==ch){

178             *pre = (*pre)->next;

179             return head;

180         }

181     }

182     return head;

183 }   

相比较delete_node2 代码简洁多了,乍看上跟no_delete_node方法差不多,本质上却不同。

no_delete_node2并没有删除节点。delete_node2则利用取地址的方式实现,这正是C语言地址指针的妙处。

刚开始想到在node再加一个属性前驱节点,但这已经不是原先数据结构了。

 

delete_node2



 

 no_delete_node



 

 

 

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
link3.c
#include <stdio.h>
struct node{
    char element; 
    struct node *next;
};
  
struct node * create_node(char ch);
void   free_node(struct node *node);
struct node * search_node(struct node *node, char ch);
struct node * insert (struct node *node, char ch);
struct node * delete_node(struct node *node, char ch);
struct node * delete_node2(struct node *node, char ch);
struct node * delete_node4(struct node *node, char ch);
struct node * no_delete_node(struct node *head, char ch);
void   destroy(struct node *node);
void traverse(void (*visit)(struct node *), struct node *head);
void print_item(struct node *p);
struct node * push(struct node *node, char ch);
struct node * pop(struct node *node);
  
void list_link(struct node  *node);
void list_link2(struct node  *node);
  
void main(void)
{
    struct node *node = create_node('a'); 
    struct node *found_node = malloc(sizeof(*found_node));
    struct node *c_node = malloc(sizeof(*c_node));
    printf("node->element=%c\n", node->element);
    node = insert(node, 'b');
    printf("node->element=%c\n", node->element);
    node = insert(node, 'c');
    printf("node->element=%c\n", node->element);
    node = insert(node, 'd');
    printf("node->element=%c\n", node->element);
    node = insert(node, 'e');
    printf("node->element=%c\n", node->element);
  
  
    found_node = search_node(node, 'c');
    //free_node(found_node);
    printf("found_node->element=%c\n", found_node->element);
    puts("before\n");
    list_link2(node);
    puts("del\n");
    c_node = delete_node2(node, 'b');
    //c_node = no_delete_node(node, 'b');
    puts("after ret c_node \n");
    list_link(c_node);
    puts("after node \n");
    list_link(node);
    //puts("destroy node \n");
    //destroy(node);
    //list_link(node);
    traverse(print_item, node);
}
  
  
void list_link2(struct node  *head)
{
    while(head){
        printf("%c\n", head ->element);
        head = head ->next;    
    }
}
  
  
void list_link(struct node  *node)
{
    printf("%c\n", node->element);
    struct node *head = node;
    while(head->next){
        head = head ->next;    
        printf("%c\n", head ->element);
    }
}
  
struct node * insert(struct node *node, char ch)
{
    struct node *node1 = create_node(ch);
    node1->next = node;
    return node1;
}
  
struct node * create_node(char ch)
{
    struct node *node = malloc(sizeof *node);
    node->element = ch;
    node->next = NULL;
    return node; 
}
  
struct node * search_node(struct node *head, char ch)
{
    struct node *pre = head;
    if(pre == NULL){
        return NULL; 
    }else{
        while(pre != NULL){
            if(pre -> element == ch){
                printf("found pre->element=%c\n", pre ->element);
                return pre;
            }
            pre = pre->next;
        }
        return NULL;
    }
  
  
struct node * delete_node(struct node *head, char ch)
{
    printf("delete_node head->element=%c\n", head->element);
    struct node *ret = head;
    struct node *pre = head;
    if(head == NULL){
        return head; 
    }else{
        if(head->element == ch){
            head = head ->next;
            return ret;
        }
        while(head->next != 0){
            if(pre->next-> element == ch){
                struct node *node = pre->next;
                free_node(node);
                head->next = pre ->next->next;    
                printf("found del %c\n", head ->element);
            }else{
                printf("notfound del%c\n", head ->element);
            }
            pre = head->next;
        }
    }
    return ret;
  
  
struct node * no_delete_node(struct node *head, char ch)
{
  
    printf("no_delete_node2 head->data=%c\n", ch);                                                 
    struct node *ret = head;
    struct node *pre = head;                                                                       
    for(;pre; pre = pre->next){
        if(pre->element==ch){
            pre = pre->next;
            return ret;
        }
    }
    return ret;
}
  
  
  
struct node * delete_node2(struct node *head, char ch)
{
  
    printf("delete_node2 head->data=%c\n", ch);                                                    
    struct node **pre = &head;                                                                     
    for(;*pre; pre = &(*pre)->next){
        if((*pre)->element==ch){
            *pre = (*pre)->next;
            return head;
        }
    }
    return head;
}
  
struct node * delete_node4(struct node *head, char ch)
{
    printf("delete_node4 head->data=%c\n", ch);                                     
    struct node *ret = head;
    struct node *pre = head;                                
    
    while(NULL != pre->next)
    {
        if(pre->next->element == ch)
        {
            printf("found del %c\n", pre->next->element);
            pre->next = pre ->next->next;    
           
        }else pre = pre->next;
    }
    return ret;
  
  
void free_node(struct node *node)
{
      
    free(node);
}
  
void   destroy(struct node *head)
{
    struct node *del = head;
    while(head){
        del = head;
        head = head-> next;
        free_node(del);
    }
}
  
void traverse(void (*visit)(struct node *), struct node *head)
{
    puts("traverse  \n");
    while(head){
        printf("traverse %c\n", head->element);
        head = head->next;
    }
         
}
  
void print_item(struct node *p)
{
    printf("%c\n", p->element);
}
  
struct node * push(struct node *node, char ch)
{
    return insert(node, ch);
}
  
struct node * pop(struct node *head)
{
         
}
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
link2.c
  
#include <stdio.h>
  
struct node{
    char element; 
    struct node *next;
};
  
struct node * create_node(char ch);
struct node * delete_node(struct node *node, char ch);
struct node * delete_node4(struct node *node, char ch);
struct node * search_node(struct node *node, char ch);
struct node * insert (struct node *node, char ch);
  
void list_link(struct node  *node);
  
void main(void)
{
    struct node *c_node = malloc(sizeof(*c_node));
      
    struct node *node = create_node('a'); 
    struct node *node2 = node; 
    printf("node->element=%c\n", node->element);
    node = insert(node, 'b');
    printf("node->element=%c\n", node->element);
    node = insert(node, 'c');
    printf("node->element=%c\n", node->element);
    node = insert(node, 'd');
    printf("node->element=%c\n", node->element);
    node = insert(node, 'e');
  
    //found_node = search_node(node, 'b');
    //printf("found_node->element=%c\n", found_node->element);
    puts("before\n");
    list_link(node);
    puts("del\n");
    c_node = delete_node4(node, 'b');
    puts("after c_node\n");
    list_link(c_node);
    puts("after list node\n");
    list_link(node);
    puts("after list node2\n");
    list_link(node2);
    //printf("%d\n", node.next);
}
  
void list_link(struct node  *node)
{
    printf("%c\n", node->element);
    struct node *head = node;
    while(head->next != 0){
        head = head ->next;    
        printf("%c\n", head ->element);
    }
}
  
struct node * insert(struct node *head, char ch)
{
    struct node *node1 = create_node(ch);
    node1->next = head;
    return node1;
}
  
struct node * create_node(char ch)
{
    struct node *head = (struct node *)malloc(sizeof(struct node));
    head->element = ch;
    head->next = NULL;
    return head; 
}
  
struct node * search_node(struct node *head, char ch)
{
    struct node *pre = head;
    if(pre == NULL){
        return NULL; 
    }else{
        while(pre != NULL){
            if(pre -> element == ch){
                printf("found pre->element=%c\n", pre ->element);
                return pre;
            }
            pre = pre->next;
        }
        return NULL;
    }
  
  
struct node * delete_node(struct node *head, char ch)
{
    printf("delete_node head->element=%c\n", head->element);
    struct node *ret = head;
    struct node *pre = head;
    if(pre == NULL){
        return ret; 
    }else{
        if(pre->element == ch){
            pre = pre ->next;
            return ret;
        }
        while(pre->next != NULL){
            printf("----- %c\n", pre ->element);
            if(pre->next-> element == ch){
                printf("found del %c\n", pre ->element);
                struct node *del = pre->next;
                free(del);
                pre->next = pre ->next->next;    
            }else{
                printf("notfound del%c\n", pre ->element);
            }
            pre = pre->next;
        }
    }
    return ret;
  
  
  
struct node * delete_node4(struct node *head, char ch)            
{
  printf("delete_node4 head->data=%d\n", ch);               
  struct node *ret = head;
  struct node *pre = head;                                            
  while(NULL != pre->next)
  {
      if(pre->next->element == ch)
      {
          printf("found del %d\n", pre->next->element);
          pre->next = pre ->next->next;    
           
      }
      else pre = pre->next;
  }
  return ret;

 

  • 大小: 163.7 KB
  • 大小: 132.1 KB
0
6
分享到:
评论

相关推荐

    单链表排序

    在探讨“单链表排序”这一主题时,我们首先需要理解单链表的...综上所述,单链表排序不仅涉及基本的数据结构知识,还涉及到算法设计与优化的深度思考。通过不断实践和学习,可以更好地掌握这一领域的核心概念和技术。

    单链表操作验证

    6. **结论**:总结学习成果,可能包括对链表理解的加深,以及对数据结构应用的思考。 通过这样的练习,学生可以深入理解单链表的工作原理,提升编程技巧,并掌握如何有效地验证和测试数据结构操作的正确性。

    合并单链表(Java)代码

    在Java编程中,合并两个已排序的单链表是一个常见的数据...此外,这个任务也让我们思考了迭代和递归两种不同的解决问题的策略,以及它们各自的优缺点。在实际编程中,我们需要根据具体需求和性能考虑来选择合适的方法。

    单链表的建立(c语言版)

    思考与提高部分提出了两个问题: 1. 如果反向输入数据元素,可以先创建一个空的顺序表,然后从最后一个元素开始,依次将输入的元素插入到表的末尾。 2. 在 main 函数中去掉 `L=&a` 会导致 `L` 不指向任何实际分配的...

    单链表的基本操

    ### 六、思考与总结 通过本实验,我们不仅掌握了单链表的基本操作,还深入了解了链表的内部机制,这对于后续学习更复杂的数据结构和算法至关重要。同时,实验过程中遇到的问题和解决策略,也是提升编程能力和逻辑...

    自己写的单链表的增删查改

    5. **效率分析**:思考每个操作的时间复杂度,了解如何优化链表操作。 通过分析和实践这个项目,你可以深化对单链表的理解,增强你的编程能力,特别是处理动态数据结构的能力。这对于学习更复杂的算法和数据结构,...

    数据结构实验指导书(单链表验证二叉树图的存储)

    单链表、二叉树和图是重要的数据结构,它们在实验中分别扮演着不同的角色。 单链表是一种线性数据结构,每个元素(节点)包含数据和指向下一个节点的引用。在“单链表操作验证”实验中,学生需要实现链表的基本操作...

    Python单链表实现详解及其基本操作(包含详细的完整的程序和数据)

    本文深入探讨了单链表这种线性数据结构的概念与特性,并提供了一套详尽易懂的 Python 实现方案。从理论出发到代码层面进行剖析讲解,涉及链表的关键组成部分以及如何利用 Python 来构建支持基本操作(如插入、删除和...

    用单链表实现任意两个一元多项式的加减运算详解.docx

    在调试分析过程描述中,项目对测试数据和测试输出结果进行了描述,并对程序调试过程中存在的问题进行了思考。例如,对于排序出现问题的错误现象,解决方法是修改主函数,并使用 while 循环和 switch 选择调用函数。...

    数据结构C++ 线性表——顺序表和单链表基本操作(含代码和注释).docx

    3. **学习建议**:鼓励读者在学习过程中养成独立思考的习惯,不要仅依赖于提供的代码示例。 ### 结语 通过上述介绍,我们可以看到文档中对于顺序表和单链表的基本操作进行了详细的阐述,并提供了具体的实现代码。...

    20151910042-刘鹏-DSA思考题-041

    在本课程中,刘鹏同学针对数据结构与算法进行了深入思考,涉及了各种存储结构和它们在不同场景下的适用性。 1. 基本存储结构分为顺序结构和链式结构。顺序结构主要指数组,它通过下标快速访问元素,适用于频繁的...

    创新数据结构实验教学的思考与探索.pdf

    文件标题“创新数据结构实验教学的思考与探索”指明了文章的主题,即对数据结构实验教学进行创新性思考和探索性的实践。文章的描述和标签“数据结构 数据分析 大数据 参考文献 专业指导”突出了文章内容涉及的领域和...

    数据结构实验1_数据结构实验1_数据结构实验_

    1. 实现单链表、双向链表的操作,如插入、删除、遍历。 2. 编写栈和队列的代码,展示它们的基本操作。 3. 设计和实现二分查找树,以及查找、插入和删除操作。 4. 创建一个简单的散列表,研究冲突解决策略,如开放...

    C++用链表完成学籍管理系统

    #### 实践意义与扩展思考 通过构建这样一个学籍管理系统,不仅加深了对C++语法的理解,特别是指针和结构体的应用,同时也锻炼了利用链表解决实际问题的能力。此外,此项目还涉及到用户交互设计、错误处理等方面,有...

    “数据结构”课程教学的实践和思考.pdf

    标题《数据结构课程教学的实践和思考》所涉及的知识点主要包括数据结构在计算机专业教学中的重要性、教学方法和策略的改进、多媒体教学在数据结构教学中的应用、教学内容的前后呼应与深度联系、因材施教的重要性以及...

    数据结构实验

    2.复习关于队列操作的基础知识。 3.编写完整程序完成下面的实验内容并上机运行。 4.整理并上交实验报告。 三、实验内容 1.任意输入队列长度和队列中的元素值,构造一个顺序循环队列,对其进行清空、插入新元素、...

    20151910042-刘鹏-DSA思考题-05 - Stack and Queue1

    单链表也不好使,因为尾部删除总是代价很高,双链结构还算不错,因为有head与tail,所以首尾插删都很容易。 队列的应用非常广泛,例如多进程的管理。在操作系统中,队列可以用来管理多个进程的运行。双端队列是一种...

    链表基本操作实验报告.doc

    通过本次实验,参与的学生不仅提高了编程能力,还学习到了如何更加系统地思考问题、解决问题的方法。在调试过程中遇到的问题促使学生更加细致地分析问题所在,从而有效地提升了编程技巧和问题解决能力。 #### C语言...

    《数据结构与算法》实验指导书.pdf

    思考与提高部分提出了关于存储优化、栈空与栈满的判断条件以及多栈共存的问题。例如,如何在不预分配过大空间的情况下避免栈上溢,以及如何利用链栈灵活地实现多个栈的共享存储。 通过这三个实验,学生能够深入理解...

Global site tag (gtag.js) - Google Analytics