服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

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

服务器之家 - 编程语言 - C/C++ - C语言单向链表的表示与实现实例详解

C语言单向链表的表示与实现实例详解

2021-01-21 14:00C语言程序设计 C/C++

这篇文章主要介绍了C语言单向链表的表示与实现,需要的朋友可以参考下

1.概述：

C语言中的单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
如下图所示：

C语言单向链表的表示与实现实例详解
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个节点。
相对于双向链表，这种普通的，每个节点只有一个指针的链表也叫单向链表，或者单链表，通常用在每次都只会按顺序遍历这个链表的时候（例如图的邻接表，通常都是按固定顺序访问的）。

2.程序实现：

?
1
2
3
4
5
6
7
/* c2-2.h 线性表的单链表存储结构 */
 struct LNode
 {
  ElemType data;
  struct LNode *next;
 };
 typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */
?
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
/* bo2-2.c 单链表线性表(存储结构由c2-2.h定义)的基本操作(12个) */
 Status InitList(LinkList *L)
 { /* 操作结果：构造一个空的线性表L */
  *L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
  if(!*L) /* 存储分配失败 */
   exit(OVERFLOW);
  (*L)->next=NULL; /* 指针域为空 */
  return OK;
 }
 Status DestroyList(LinkList *L)
 { /* 初始条件：线性表L已存在。操作结果：销毁线性表L */
  LinkList q;
  while(*L)
  {
   q=(*L)->next;
   free(*L);
   *L=q;
  }
  return OK;
 }
 Status ClearList(LinkList L) /* 不改变L */
 { /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
  LinkList p,q;
  p=L->next; /* p指向第一个结点 */
  while(p) /* 没到表尾 */
  {
   q=p->next;
   free(p);
   p=q;
  }
  L->next=NULL; /* 头结点指针域为空 */
  return OK;
 }
 Status ListEmpty(LinkList L)
 { /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
  if(L->next) /* 非空 */
   return FALSE;
  else
   return TRUE;
 }
 int ListLength(LinkList L)
 { /* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
  int i=0;
  LinkList p=L->next; /* p指向第一个结点 */
  while(p) /* 没到表尾 */
  {
   i++;
   p=p->next;
  }
  return i;
 }
 Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
 { /* L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
  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 ERROR;
  *e=p->data; /* 取第i个元素 */
  return OK;
 }
 int LocateElem(LinkList L,ElemType e,Status(*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;
 }
 Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
 { /* 初始条件: 线性表L已存在 */
  /* 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */
  /*      返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE */
  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 OK;
   }
   p=q; /* p向后移 */
  }
  return INFEASIBLE;
 }
 Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
 { /* 初始条件：线性表L已存在 */
  /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
  /*      返回OK;否则操作失败，next_e无定义，返回INFEASIBLE */
  LinkList p=L->next; /* p指向第一个结点 */
  while(p->next) /* p所指结点有后继 */
  {
   if(p->data==cur_e)
   {
    *next_e=p->next->data;
    return OK;
   }
   p=p->next;
  }
  return INFEASIBLE;
 }
 Status 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 ERROR;
  s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
  s->data=e; /* 插入L中 */
  s->next=p->next;
  p->next=s;
  return OK;
 }
 Status 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 ERROR;
  q=p->next; /* 删除并释放结点 */
  p->next=q->next;
  *e=q->data;
  free(q);
  return OK;
 }
 Status ListTraverse(LinkList L,void(*vi)(ElemType))
 /* vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同 */
 { /* 初始条件：线性表L已存在 */
  /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
  LinkList p=L->next;
  while(p)
  {
   vi(p->data);
   p=p->next;
  }
  printf("\n");
  return OK;
 }
?
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
/* algo2-5.c 主程序 */
 #include"c1.h"
 typedef int ElemType;
 #include"c2-2.h"
 #include"bo2-2.c"
 void CreateList(LinkList *L,int n) /* 算法2.11 */
 { /* 逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L */
  int i;
  LinkList p;
  *L=(LinkList)malloc(sizeof(struct LNode));
  (*L)->next=NULL; /* 先建立一个带头结点的单链表 */
  printf("请输入%d个数据\n",n);
  for(i=n;i>0;--i)
  {
   p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
   scanf("%d",&p->data); /* 输入元素值 */
   p->next=(*L)->next; /* 插入到表头 */
   (*L)->next=p;
  }
 }
 void CreateList2(LinkList *L,int n)
 { /* 正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表 */
  int i;
  LinkList p,q;
  *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成头结点 */
  (*L)->next=NULL;
  q=*L;
  printf("请输入%d个数据\n",n);
  for(i=1;i<=n;i++)
  {
   p=(LinkList)malloc(sizeof(struct LNode));
   scanf("%d",&p->data);
   q->next=p;
   q=q->next;
  }
  p->next=NULL;
 }
 void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 算法2.12 */
 { /* 已知单链线性表La和Lb的元素按值非递减排列。 */
  /* 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列 */
  LinkList pa=La->next,pb=(*Lb)->next,pc;
  *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; /* 插入剩余段 */
  free(*Lb); /* 释放Lb的头结点 */
  Lb=NULL;
 }
 void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */
 {
  printf("%d ",c);
 }
 void main()
 {
  int n=5;
  LinkList La,Lb,Lc;
  printf("按非递减顺序, ");
  CreateList2(&La,n); /* 正位序输入n个元素的值 */
  printf("La="); /* 输出链表La的内容 */
  ListTraverse(La,visit);
  printf("按非递增顺序, ");
  CreateList(&Lb,n); /* 逆位序输入n个元素的值 */
  printf("Lb="); /* 输出链表Lb的内容 */
  ListTraverse(Lb,visit);
  MergeList(La,&Lb,&Lc); /* 按非递减顺序归并La和Lb,得到新表Lc */
  printf("Lc="); /* 输出链表Lc的内容 */
  ListTraverse(Lc,visit);
 }

 

  • C语言
  • 单向链表

    • 延伸 · 阅读

    精彩推荐
    • C/C++深入C++拷贝构造函数的总结详解

      深入C++拷贝构造函数的总结详解

      本篇文章是对C++中拷贝构造函数进行了总结与介绍。需要的朋友参考下...

      C++教程网5182020-11-30
    • C/C++C语言实现双人五子棋游戏

      C语言实现双人五子棋游戏

      这篇文章主要为大家详细介绍了C语言实现双人五子棋游戏，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      两片空白7312021-11-12
    • C/C++OpenCV实现拼接图像的简单方法

      OpenCV实现拼接图像的简单方法

      这篇文章主要为大家详细介绍了OpenCV实现拼接图像的简单方法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      iteye_183805102021-07-29
    • C/C++C语言main函数的三种形式实例详解

      C语言main函数的三种形式实例详解

      这篇文章主要介绍了 C语言main函数的三种形式实例详解的相关资料,需要的朋友可以参考下...

      ieearth6912021-05-16
    • C/C++c/c++实现获取域名的IP地址

      c/c++实现获取域名的IP地址

      本文给大家汇总介绍了使用c/c++实现获取域名的IP地址的几种方法以及这些方法的核心函数gethostbyname的详细用法，非常的实用，有需要的小伙伴可以参考下...

      C++教程网10262021-03-16
    • C/C++关于C语言中E-R图的详解

      关于C语言中E-R图的详解

      今天小编就为大家分享一篇关于关于C语言中E-R图的详解，小编觉得内容挺不错的，现在分享给大家，具有很好的参考价值，需要的朋友一起跟随小编来看看...

      Struggler095962021-07-12
    • C/C++使用C++制作简单的web服务器（续）

      使用C++制作简单的web服务器（续）

      本文承接上文《使用C++制作简单的web服务器》，把web服务器做的功能稍微强大些，主要增加的功能是从文件中读取网页并返回给客户端，而不是把网页代码...

      C++教程网5492021-02-22
    • C/C++c/c++内存分配大小实例讲解

      c/c++内存分配大小实例讲解

      在本篇文章里小编给大家整理了一篇关于c/c++内存分配大小实例讲解内容，有需要的朋友们可以跟着学习参考下。...

      jihite5172022-02-22
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 素数交换 　 地址参数 　 多继承法 　 ZOJ 　 Fishing 　 同名 　 libfreetype 　 Simulink 　 数据滚动 　 右值引用 　 NSString 　 消息传递 　 平滑处理 　 Visual C++ 　 栈区 　 堆区 　 C语言程序设计 　 内存错误 　 对象模型 　 颜色加亮 　 程序内部 　 strcat 　 WinExec 　 打开程序 　 错误调试 　 C++教程 　 tinyxml 　 XML解析器 　 静态存储区 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图