一、单链表
链表是用一组任意的存储单元存储数据元素。如果是存储线性表中的元素,则称为线性链表。
链表中的结点地址在内存中可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。因此链表中结点的逻辑顺序和物理顺序不一定相同。
如果链表的结点中只有一个指针域,则该链表称为单链表,这也是常用的线性表的存储模式。
单链表适合于比较频繁的增加或者删除线性表中元素,不需要移动元素。
二、创建单链方法
创建单链表的方法主要有“头插入法”和“尾插入法”。顾名思义,“头插入法”就是始终在表头位置插入新的结点,而“尾插入法”就是在链表的末尾插入新的结点。
1.头插入法
假设有线性表a={ 1,2,3 },则使用头插入法创建单链表的过程如下:
1)首先生成链表的表头结点(如果需要),同时让指针h指向该结点
2)插入元素1。先创建一个新结点,存储1,然后将其链接到h的后面。
3)插入元素2。继续创建一个新结点,存储2,然后将其链接到h的后面。
4)继续插入元素3。创建一个新结点,存储3,然后将其链接到h的后面。
平铺之后得到:
2.尾插入法
假设有线性表a={ 1,2,3 },则使用尾插入法创建单链表的过程如下:
1)首先生成链表的表头结点(如果需要),同时让指针h指向该结点
2)插入元素1。创建一个新结点,存储1,然后将其链接到h的后面。
3)插入元素2。创建一个新结点,存储2,然后将其链接到结点1的后面。
4)插入元素3。创建一个新结点,存储3,然后将其链接到结点2的后面。
在尾插入法创建单链表的过程中,为了方便实现插入的工作,引入一个临时指针p指向链表中最后一个结点,则再插入新结点时,就可以利用p建立链接。
例如:
插入元素3的时候,就可以利用p把新结点链接到链表的末尾:
对应的算法为:
p->next = s;
p = s;
三、创建单链算法之C程序
根据已知的数组创建单链表。
链表结点结构:
typedef struct Lnode
{
int data; //数据域
struct Lnode *next; //指针域
}LNode;
1.头插入法
LNode* CreateListHeader( int a[], int n )
{
int i;
LNode *head, *s;
head = ( LNode* )malloc( sizeof( LNode ) );
head->next = NULL; //创建单链表的表头结点
for( i = 0; i < n; i++ )
{
s = ( LNode* )malloc( sizeof( LNode ) );
s->data = a[i];
s->next = head->next;
head->next = s;
}
return (head);
}
2.尾插入法
LNode* CreateListTailer( int a[], int n )
{
int i;
LNode *head, *s, *p;
head = ( LNode* )malloc( sizeof( LNode ) );
head->next = NULL; //创建单链表的表头结点
p = head;
for( i = 0; i < n; i++ )
{
s = ( LNode* )malloc( sizeof( LNode ) );
s->data = a[i];
s->next = NULL;
p->next = s;
p = s;
}
return (head);
}
3.完成的测试代码(仅供参考)文章来源:https://www.toymoban.com/news/detail-719132.html
#include"stdio.h"
#include"malloc.h"
typedef struct Lnode
{
int data; //数据域
struct Lnode *next; //指针域
}LNode;
LNode* CreateListHeader( int a[], int n );
LNode* CreateListTailer( int a[], int n );
int main()
{
LNode *head1, *head2, *p;
int a[] ={ 1, 2, 3, 4, 5 };
int n = 5;
head1 = CreateListHeader( a, n );
printf( "头插入法创建单链表:" );
p = head1->next;
while( p != NULL )
{
printf( "%5d", p->data );
p = p->next;
}
printf( "\n" );
printf( "尾插入法创建单链表:" );
head2 = CreateListTailer( a, n );
p = head2->next;
while( p != NULL )
{
printf( "%5d", p->data );
p = p->next;
}
printf( "\n" );
return 0;
}
// 头插入法创建单链表,链表的头结点head作为返回值
LNode* CreateListHeader( int a[], int n )
{
int i;
LNode *head, *s;
head = ( LNode* )malloc( sizeof( LNode ) );
head->next = NULL; //创建单链表的表头结点
for( i = 0; i < n; i++ )
{
s = ( LNode* )malloc( sizeof( LNode ) );
s->data = a[i];
s->next = head->next;
head->next = s;
}
return (head);
}
// 尾插入法创建单链表,链表的头结点head作为返回值
LNode* CreateListTailer( int a[], int n )
{
int i;
LNode *head, *s, *p;
head = ( LNode* )malloc( sizeof( LNode ) );
head->next = NULL; //创建单链表的表头结点
p = head;
for( i = 0; i < n; i++ )
{
s = ( LNode* )malloc( sizeof( LNode ) );
s->data = a[i];
s->next = NULL;
p->next = s;
p = s;
}
return (head);
}
4.测试结果
文章来源地址https://www.toymoban.com/news/detail-719132.html
到了这里,关于创建单链表详解之C语言版的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!