C语言回顾--简单的单向链表头插法和尾差法编程
程序员文章站
2022-03-09 15:18:43
...
------------------------------------------------------------------------------------------------
前言:
准备笔试题绕不开数据结构,因此最近重新复习关于链表的编程包含单向链表双向链表,以及介绍在制作单向链表中用到的头插法和尾差法;
------------------------------------------------------------------------------------------------
单向链表:
结构体定义:
typedef struct _st_node //定义结构体,并且结构体中包含指向下一个节点结构体指针
{
int data;
struct _st_node *next;
}st_node;
头插法的核心思想:
在不考虑刚开始创建第一个节点,和最后一个节点的处理:只需要一个指针Head即可完成;
newnode->next = head;
head = newnode;
而单单只靠for循环和带入上述代码是无法创建一个完整的链表:临界处:创建第一个节点,新的节点直接接在Head后面即可,最后一个新节点则需要将结构体内的next指向NULL;
附上完整的头插法代码:
st_node *head_insert(int n) //返回值为st_node *类型
{
st_node *head = NULL;
st_node *new_node;
int i;
for(i = 0; i < n ; i++)
{
new_node =(st_node *) malloc(sizeof(st_node));
if(NULL == new_node)
{
printf("Malloc failure\n");
exit(-1);
}
new_node->data = i+1;
new_node->next = NULL; //创建一个节点的同时将next指向NULL
if( NULL == head ) //插入第一个节点时
{
head = new_node;
printf("Add head node [%d]\n",new_node->data);
}
else //非临界插入
{
new_node->next = head;
head = new_node;
printf("Add new node [%d]\n",new_node->data);
}
}
return head;
}
尾差法的核心思想:
同样,在不考虑刚开始创建第一个节点,和最后一个节点的处理:此时需要2个指针Head和tail来完成,这个tail指针在其中的作用就是每添加一个节点,tail指针就往后移动一个节点:
tail->next = new_node;
tail = new_node;
跟头插法相同,考虑临界点:新节点接在Head的后面同时,也将tail指针指向新节点:
附上代码:
st_node *tail_insert(int n)
{
st_node *head = NULL;
st_node *new_node,*tail;
int i;
for( i=0 ;i < n ; i++)
{
new_node = (st_node *)malloc(sizeof(st_node));
new_node->data = i+1;
new_node->next = NULL;
if(NULL == head)
{
head = new_node;
tail = head;
printf("Add head node [%d]\n",new_node->data);
}
else
{
tail->next = new_node;
tail = new_node;
printf("Add new node [%d]\n",new_node->data);
}
}
return head;
}
附上完整的程序,包括遍历链表和销毁链表:
/*********************************************************************************
* Copyright: (C) 2018 guozhihao
* All rights reserved.
*
* Filename: link.c
* Description: This file
*
* Version: 1.0.5(08/23/2018)
* Author: Guozhihao <aaa@qq.com>
* ChangeLog: 4, Release initial version on "08/23/2018 15:04:18 PM"
*
********************************************************************************/
#include <stdio.h>
#include <stdlib.h>
typedef struct _st_node
{
int data;
struct _st_node *next;
}st_node;
st_node *head_insert(int n);
st_node *tail_insert(int n);
void travel_list(st_node *head, int (*func_ptr)(st_node *node)); //函数的第二个参数为函数指针
int print_data(st_node *node);
int print_total(st_node *node);
void destory_list(st_node *head);
int main (int argc, char **argv)
{
st_node *head = NULL;
int i;
/* head insert */
head_insert(head,10);
/* tail insert */
//head = tail_insert(10);
travel_list(head,print_data);
//travel_list(head,print_total);
destory_list(head);
return 0;
} /* ----- End of main() ----- */
int print_data(st_node *node)
{
printf("node [%d] node adress :%p\n",node->data,node);
}
int print_total(st_node *node)
{
static int total = 0;
total += node->data;
printf("total: %d\n",total);
}
void travel_list(st_node *head,int (*func_ptr)(st_node *node))
{
st_node *node;
node = head;
while( node != NULL )
{
func_ptr(node);
node = node->next;
}
return ;
}
void destory_list(st_node *head)
{
st_node *node;
do
{
node = head;
head = head->next;
printf("free node [%d] node adress :%p\n",node->data,node);
free(node);
}while(head != NULL);
}
st_node *head_insert(int n)
{
st_node *head = NULL;
st_node *new_node;
int i;
for(i = 0; i < n ; i++)
{
new_node =(st_node *) malloc(sizeof(st_node));
if(NULL == new_node)
{
printf("Malloc failure\n");
exit(-1);
}
new_node->data = i+1;
new_node->next = NULL;
if( NULL == head )
{
head = new_node;
printf("Add head node [%d]\n",new_node->data);
}
else
{
new_node->next = head;
head = new_node;
printf("Add new node [%d]\n",new_node->data);
}
}
return head;
}
st_node *tail_insert(int n)
{
st_node *head = NULL;
st_node *new_node,*tail;
int i;
for( i=0 ;i < n ; i++)
{
new_node = (st_node *)malloc(sizeof(st_node));
new_node->data = i+1;
new_node->next = NULL;
if(NULL == head)
{
head = new_node;
tail = head;
printf("Add head node [%d]\n",new_node->data);
}
else
{
tail->next = new_node;
tail = new_node;
printf("Add new node [%d]\n",new_node->data);
}
}
return head;
}
程序运行结果:
[aaa@qq.com C6]$ ./a.out
Add head node [1]
Add new node [2]
Add new node [3]
Add new node [4]
Add new node [5]
Add new node [6]
Add new node [7]
Add new node [8]
Add new node [9]
Add new node [10]
node [1] node adress :0xa0c010
node [2] node adress :0xa0c030
node [3] node adress :0xa0c050
node [4] node adress :0xa0c070
node [5] node adress :0xa0c090
node [6] node adress :0xa0c0b0
node [7] node adress :0xa0c0d0
node [8] node adress :0xa0c0f0
node [9] node adress :0xa0c110
node [10] node adress :0xa0c130
free node [1] node adress :0xa0c010
free node [2] node adress :0xa0c030
free node [3] node adress :0xa0c050
free node [4] node adress :0xa0c070
free node [5] node adress :0xa0c090
free node [6] node adress :0xa0c0b0
free node [7] node adress :0xa0c0d0
free node [8] node adress :0xa0c0f0
free node [9] node adress :0xa0c110
free node [10] node adress :0xa0c130
上一篇: 利用递归求n以内的素数之和
下一篇: MySQL 数据库的创建&修改