链表c语言视频（C语言链表原理）

本文目录

• C语言链表原理
• 如何C语言创建单链表
• 求c语言链表的详细讲解
• 在C语言中，什么是链表呀
• c语言 链表操作:建立,显示及节点的插入,删除

C语言链表原理

每个节点有一个数据域num保存该节点的数据，以及一个next域指向下一个节点的地址。假设某时刻指针p指向链表头结点，通过一个循环不停地将p赋值为p指向的节点的next域的值，即该节点的下一个节点的地址，即可遍历整个列表。

如何C语言创建单链表

C语言创建单链表如下：

#include"stdio.h"

#include"stdlib.h"

#include"malloc.h"

#include "iostream.h"

typedef struct node

{

int  data;

node * next;

}node , * List;

void create(int n)

{

int c;

List s,L;

L=(List)malloc(sizeof(node));

L-》next=NULL;

printf("请输入第1个数据：");

scanf("%d",&c);

L-》data=c;

for(int i=2;i《=n;i++)

{

s=(List)malloc(sizeof(node));

printf("请输入第%d个数据：",i);

scanf("%d",&c);

s-》data=c;

s-》next=L;

L-》next =s;

}

printf("链表创建成功！");

}

void main()

{

int n;

printf("请你输入链表的个数：");

scanf("%d",&n);

create(n);

}

单链表创建方法：

单链表的建立有头插法、尾插法两种方法。

1． 头插法

单链表是用户不断申请 存储单元和改变链接关系而得到的一种特殊 数据结构，将链表的左边称为链头，右边称为链尾。头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。头插法最先得到的是尾结点。

由于链表的长度是随机的，故用一个while循环来控制链表中结点个数。假设每个结点的值都大于O，则循环条件为输入的值大于o。申请 存储空间可使用malloc()函数实现，需设立一申请单元 指针，但malloc()函数得到的指针并不是指向 结构体的指针，需使用 强制类型转换，将其转换成结构体型指针。刚开始时，链表还没建立，是一空链表，head 指针为NULL。

链表建立的过程是申请空间、得到数据、建立链接的循环处理过程。

2． 尾插法

若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。尾插法建立链表时，头 指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针head、搜索指针p2、申请单元指针pl。尾插法最先得到的是 头结点。

求c语言链表的详细讲解

链表是一种常见的重要的数据结构.它是动态地进行存储分配的一种结构.我们知道,用数组存放数据时,
必须事先定义固定的长度(即元素个数).比如,有的班级有100人,而有的班只有30人,如果要用同一个数组先后存放不同班级的学生数据,则必须定义长度为100的数组.如果事先难以确定一个班的最多人数,则必须把数组定得足够大,以能存放任何班级的学生数据.显然这将会浪费内存.链表则没有这种缺点,它根据需要开辟内存单元.图10.11表示最简单的一种链表(单向链表)的结构.链表有一个"头指针"变量,图中以head表示,它存放一个地址.
该地址指向一个元素.链表中每一个元素称为"结点",每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址.课以看出,head指向第一个元素;第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为’表尾",它的地址部分放一个"NULL"(表示"空地址").链表到此结束.
可以看到:链表中各元素在内存中可以不是连续存放的.要找某一元素,必须先找到上一个元素,根据它提供的下一元素地址才能找到下一个元素.
如果不提供"头指针"(head),则整个链表都无法访问.链表如同一条铁链一样,一环扣一环,中间是不能断开的.打个通俗的比方:幼儿园的老师带领孩子出来散步,老师牵着第一个小孩的手,第一个小孩的另一只手牵着第二个孩子,……,这就是一个"链",最后一个孩子有一只手空着,他是"链尾".要找这个队伍,必须先找到老师,然后顺序找到每一个孩子.

在C语言中，什么是链表呀

链表
链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。
概况
链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据(data fields)和一或两个用来指向明上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。
本段特点
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如概述旁的图所示），表示线性表中一个数据元素 。
本段扩展
根据情况，也可以自己设计链表的其它扩展。但是一般不会在边上附加数据，因为链表的点和边基本上是一一对应的（除了第一个或者最后一个节点，但是也不会产生特殊情况）。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向，反向标记加在边上可能会更方便。 对于非线性的链表，可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn)，和平衡二叉树一样。 其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。 由分别表示,,…, 的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表.
本段三个链表函数（C语言描述）
#include 《stdio.h》
#include 《stdlib.h》
#include 《iostream》
struct Node{
int data;//数据域
struct Node * next;//指针域
}; /************************************************************************************** *函数名称:insert
*函数功能:在链表中插入元素. *输入:head 链表头指针,p新元素插入位置,x 新元素中的数据域内容 *输出:无 *************************************************************************************/ void insert(Node * head,int p,int x)
{ Node * tmp = head; //for循环是为了防止插入位置超出了链表长度 for(int i = 0;i《p;i++)
{
if(tmp == NULL)
return ;
if(i《p-1)
tmp = tmp-》next;
}
Node * tmp2 = new Node;
tmp2-》data = x;
tmp2-》next = tmp-》next;
tmp-》next = tmp2;
} /************************************************************************************** *函数名称：del *函数功能:删除链表中的元素 *输入:head 链表头指针,p 被删除元素位置 输出:被删除元素中的数据域.如果删除失败返回-1 **************************************************************************************/
int del(Node * head,int p)
{
Node * tmp = head;
for(int i = 0;i《p;i++)
{
if(tmp == NULL)
return -1;
if(i《p-1)
tmp = tmp-》next;
}
int ret = tmp-》next-》data;
tmp-》next = tmp-》next-》next;
return ret;
}
void print(Node *head)
{
for(Node *tmp = head;
tmp!=NULL; tmp = tmp-》next)
printf("%d ",tmp-》data);
printf("\n");
}
int main()
{
Node * head;
head = new Node;
head-》data = -1;
head-》next=NULL;
return 0;
}
本段结语
C语言是学习数据结构的很好的学习工具。理解了C中用结构体描述数据结构，那么对于理解其C++描述，Java描述都就轻而易举了！
本段两种链表形式
一、循环链表 循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。 循环链表的运算与单链表的运算基本一致。所不同的有以下几点： 1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。 2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。
二、双向链表 双向链表其实是单链表的改进。 当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。 在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

c语言 链表操作:建立,显示及节点的插入,删除

先写个头文件，包含链表的各种操作。具体代码如下：
#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED
//线性表的单链表存储结构
struct LNode
{
ElemType data;
LNode *next;
};
typedef LNode *LinkList; // 另一种定义LinkList的方法
//单链表线性表的基本操作(12个)
int InitList(LinkList &L)
{
// 操作结果：构造一个空的线性表L
L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点
if(!L) // 存储分配失败
exit(0);
L-》next=NULL; // 指针域为空
return 1;
}
void CreateList_L(LinkList &L, int n) // 算法2.11
{
// 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L
LinkList p;
int i;
L = (LinkList)malloc(sizeof(LNode));
L-》next = NULL; // 先建立一个带头结点的单链表
for (i=n; i》0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); // 生成新结点
p-》data = rand()%200; // 改为一个随机生成的数字(200以内)
p-》next = L-》next;
L-》next = p; // 插入到表头
}
} // CreateList_L
int DestroyList(LinkList &L)
{
// 初始条件：线性表L已存在。操作结果：销毁线性表L
LinkList q;
while(L)
{
q=L-》next;
****(L);
L=q;
}
return 1;
}
int ClearList(LinkList L) // 不改变L
{
// 初始条件：线性表L已存在。操作结果：将L重置为空表
LinkList p,q;
p=L-》next; // p指向第一个结点
while(p) // 没到表尾
{
q=p-》next;
****(p);
p=q;
}
L-》next=NULL; // 头结点指针域为空
return 1;
}
int ListEmpty(LinkList L)
{
// 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
if(L-》next) // 非空
return 0;
else
return 1;
}
int ListLength(LinkList L)
{
// 初始条件：线性表L已存在。操作结果：返回L中数据元素个数
int i=0;
LinkList p=L-》next; // p指向第一个结点
while(p) // 没到表尾
{
i++;
p=p-》next;
}
return i;
}
int GetElem(LinkList L,int i,ElemType &e) // 算法2.8
{
// L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回1,否则返回-1
int j=1; // j为计数器
LinkList p=L-》next; // p指向第一个结点
while(p&&j《i) // 顺指针向后查找,直到p指向第i个元素或p为空
{
p=p-》next;
j++;
}
if(!p||j》i) // 第i个元素不存在
return -1;
e=p-》data; // 取第i个元素
return 1;
}
int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType))
{
// 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0)
// 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。
// 若这样的数据元素不存在,则返回值为0
int i=0;
LinkList p=L-》next;
while(p)
{
i++;
if(compare(p-》data,e)) // 找到这样的数据元素
return i;
p=p-》next;
}
return 0;
}
int PriorElem(LinkList L,ElemType cur_e,ElemType ⪯_e)
{
// 初始条件: 线性表L已存在
// 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,
// 返回1;否则操作失败,pre_e无定义,返回-1
LinkList q,p=L-》next; // p指向第一个结点
while(p-》next) // p所指结点有后继
{
q=p-》next; // q为p的后继
if(q-》data==cur_e)
{
pre_e=p-》data;
return 1;
}
p=q; // p向后移
}
return -1;
}
int NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
{
// 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 返回1;否则操作失败，next_e无定义，返回-1
LinkList p=L-》next; // p指向第一个结点
while(p-》next) // p所指结点有后继
{
if(p-》data==cur_e)
{
next_e=p-》next-》data;
return 1;
}
p=p-》next;
}
return -1;
}
int ListInsert(LinkList L,int i,ElemType e) // 算法2.9。不改变L
{
// 在带头结点的单链线性表L中第i个位置之前插入元素e
int j=0;
LinkList p=L,s;
while(p&&j《i-1) // 寻找第i-1个结点
{
p=p-》next;
j++;
}
if(!p||j》i-1) // i小于1或者大于表长
return -1;
s=(LinkList)malloc(sizeof(LNode)); // 生成新结点
s-》data=e; // 插入L中
s-》next=p-》next;
p-》next=s;
return 1;
}
int ListDelete(LinkList L,int i,ElemType &e) // 算法2.10。不改变L
{
// 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值
int j=0;
LinkList p=L,q;
while(p-》next&&j《i-1) // 寻找第i个结点,并令p指向其前趋
{
p=p-》next;
j++;
}
if(!p-》next||j》i-1) // 删除位置不合理
return -1;
q=p-》next; // 删除并释放结点
p-》next=q-》next;
e=q-》data;
****(q);
return 1;
}
int ListTraverse(LinkList L,void(*vi)(ElemType))
// vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同
{
// 初始条件：线性表L已存在
// 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败
LinkList p=L-》next;
while(p)
{
vi(p-》data);
p=p-》next;
}
printf("\n");
return 1;
}
LinkList ReverseList(LinkList phead)//实现链表的逆置
{
LinkList p,q,r;
p=phead;
q=r=NULL;
while(p)
{
q=p-》next;
p-》next=r;
r=p;
p=q;
}
return r;
}
#endif // LINKEDLIST_H_INCLUDED
再写主函数：
#include 《stdio.h》
#include 《stdlib.h》
typedef int ElemType;
#include "LinkedList.h"
int compare(ElemType c1,ElemType c2)
{
if(c1==c2)
return 1;
else
return 0;
}
void visit(ElemType c)
{
printf("%d ",c);
}
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{
// 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
LinkList pa, pb, pc;
pa = La-》next;
pb = Lb-》next;
Lc = pc = La; // 用La的头结点作为Lc的头结点
while (pa && pb)
{
if (pa-》data 《= pb-》data)
{
pc-》next = pa;
pc = pa;
pa = pa-》next;
}
else
{
pc-》next = pb;
pc = pb;
pb = pb-》next;
}
}
pc-》next = pa ? pa : pb; // 插入剩余段
****(Lb); // 释放Lb的头结点
} // MergeList_L
int main()
{
LinkList L;
ElemType e,e0;
int i;
InitList(L);
for(i=1; i《=10; i++)
ListInsert(L,1,10-i);
//CreateList_L(L,10);
printf("在L的表尾依次插入10个数据后：L=");
ListTraverse(L,visit);
GetElem(L,4,e);
printf("第4个元素的值为：%d\n",e);
ListDelete(L,4,e); // 删除第4个数据
printf("删除第4个数据后：L=");
ListTraverse(L,visit);
DestroyList(L);
LinkList La, Lb, Lc;
int a = {3,5,8,11};
int b = {2,6,8,9,11,15,20};
InitList(La);
InitList(Lb);
for(i=1; i《=4; i++)
ListInsert(La, i, a);
for(i=1; i《=7; i++)
ListInsert(Lb, i, b);
printf("La=");
ListTraverse(La,visit);
printf("Lb=");
ListTraverse(Lb,visit);
MergeList_L(La, Lb, Lc);
printf("Lc=");
ListTraverse(Lc,visit);
DestroyList(Lc);
}
你不需要的操作可以注释掉！