数据结构算法C语言实现（五）---2.3重新定义线性链表及其基本操作 ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　一.简述

　　...由于链表在空间的合理利用上和插入、删除时不需要移动等的优点，因此在很多场合下，它是线性表的首选存储结构。然而，它也存在着实现某些基本操作，如求线性表的长度时不如顺序存储结构的缺点；另一方面，由于在链表中，结点之间的关系用指针来表示，则数据元素在线性表中的“位序”的概念已经淡化，而被数据元素在线性链表中的“位置”所代替。为此，从实际应用的角度重新定义线性链表及其基本操作。....（Page37）　

　　此外，书上一些地方我认为存在错误，所以写代码时做了修改和注释。并且，由于一些基本操作书中没有具体使用的实例，所以我只实现了算法2.20和算法2.21中出现的基本操作，其他操作会在需要的时候再做实现。

　　二.头文件

  1 //LinkList.h
  2 /**
  3 《数据结构（C语言版）》 Page 37
  4 ....为此，从实际应用角度出发重新定义线性链表及其基本操作....
  5 */
  6 /**
  7 author:zhaoyu
  8 email:[email protected]
  9 date:2016-6-4
 10 note:realize my textbook <<数据结构（C语言版）>>
 11 */
 12 #ifndef _LINKLIST_H_
 13 #define _LINKLIST_H_
 14 #include "head.h"
 15 #include <cstdlib>
 16 #define ElemType int
 17 typedef struct LNode{
 18     ElemType data;
 19     struct LNode *next;
 20 }*Link, *Position;
 21 typedef struct{//链表类型
 22     Link head, tail;//分别指向线性链表中的头结点和最后一个结点
 23     int len;//指示线性链表中数据元素的个数
 24 }LinkList;
 25 Status MakeNode(Link &p, ElemType e)
 26 {
 27     //分配由 p 指向的值为 e 的结点，并返回 OK；若分配失败，则返回 ERROR
 28     p = (Link)malloc(sizeof(struct LNode));
 29     if (!p)
 30     {
 31         return ERROR;
 32     }
 33     p->data = e;
 34     p->next = NULL;
 35     return OK;
 36 }
 37 Status FreeNode(Link &p)
 38 {
 39     //释放 p 所指节点
 40     p = NULL;//便于回收???释放后再次使用
 41     free(p);
 42 }
 43 Status InitList(LinkList &L)
 44 {
 45     //构造一个空的线性表L
 46     L.head = (Link)malloc(sizeof(struct LNode));
 47     L.head->data = 100;
 48     L.head->next = NULL;
 49     L.tail = L.head->next;
 50     L.len = 0;
 51 }
 52 Status ClearList(LinkList &L)
 53 {
 54     //将线性链表置为空表并释放原链表的结点空间
 55 }
 56 Status InsFirst(LinkList &L, Link &h, Link &s)
 57 {
 58     //已知 h 指向线性链表的头结点，将 s 所指节点插入在第一个结点之前
 59     //note:这里的参数与书上有些不一样，LinkList &L是我添加的
 60     //因为插入新的元素之后，链表长度应该同步变化
 61     //链表的插入是基于地址的，所以我全部加了引用
 62     //这一个函数与书上参数完全不同
 63     //更新 2016-5-5 16:46
 64     //通过分析算法2.20发现 h 不是绝对的头结点，而是接受一个 h
 65     //就以它为头结点作参考操作其它元素
 66     //这个函数花了不少时间，值得反复思考
 67     if (NULL == h)
 68     {
 69         return ERROR;
 70     }
 71     else
 72     {
 73         s->next = h->next;
 74         h->next = s;
 75     }
 76     L.len++;
 77     return OK;
 78 }
 79 Status DelFirst(Link &h, Link &q)
 80 {
 81     //已知 h 指向线性链表的头结点，删除链表中的第一个节点并以 q 返回
 82     if (h == NULL)
 83     {
 84         return ERROR;
 85     }
 86     q = h->next;
 87     h->next = q->next;
 88     q->next = NULL;
 89     return OK;
 90 }
 91 Status Append(LinkList &L, Link &s)
 92 {
 93     //将指针 s 所指（彼此以指针相链）的一串结点
 94     //链接在线性链表 L 最后一个结点
 95     Link q = L.head;
 96     while (q->next != NULL)
 97     {
 98         q = q->next;
 99     }
100     q->next = s;
101     int cnt = 0;
102     Link temp = s;
103     while (temp != NULL)
104     {
105         cnt++;
106         if (NULL == temp->next)
107         {
108             L.tail = temp;//注意更新尾指针
109         }
110         temp = temp->next;
111     }
112 
113     L.len += cnt;
114     //注意要根据这一串结点长度增加链表长度
115     return OK;
116 }
117 Status Remove(LinkList &L, Link &q)
118 {
119     //删除线性链表 L 中的尾结点并以 q 返回，改变链表的尾指针指向新的尾结点
120 }
121 Status InsBefore(LinkList &L, Link &p, Link s)
122 {
123     //已知 p 指向线性链表 L 中的一个结点，将 s 所指结点插入 p 所指节点之前
124     //并修改指针 p 指向新插入的节点
125 }
126 Status InsAfter(LinkList &L, Link &p, Link s)
127 {
128     //已知 p 指向线性链表 L 中的一个结点，将 s 所指结点插入 p 所指节点之后
129     //并修改指针 p 指向新插入的节点
130 }
131 Status SetCurElem(Link &p, ElemType e)
132 {
133     //已知 p 指向线性链表中的一个结点，用 e 更新 p 所指结点中数据元素的值
134 }
135 ElemType GetCurElem(Link p)
136 {
137     //已知 p 指向线性链表中的一个节点，返回 p 所指结点中数据元素的值
138     if (p != NULL)
139     {
140         return p->data;
141     }
142     else
143     {
144         exit(ERROR);
145     }
146 }
147 Status ListEmpty(LinkList L)
148 {
149     //若线性链表 L 为空，则返回 TRUE，否则返回 FALSE
150 }
151 int ListLength(LinkList L)
152 {
153     //返回线性链表 L 中元素的个数
154 
155 }
156 Position GetHead(LinkList L)
157 {
158     //返回线性链表 L 中头结点的位置
159     return L.head;
160 }
161 Position GetLast(LinkList L)
162 {
163     //返回线性链表 L 中最后一个结点的位置
164 }
165 Position PriorPos(LinkList L, Link p)
166 {
167     //已知 p 指向线性链表 L 中的一个结点，返回 p 所指结点直接前驱的位置
168     //若无前驱，则返回NULL
169 }
170 Position NextPos(LinkList L, Link p)
171 {
172     //已知 p 指向线性链表 L 中的一个节点，返回 p 所指结点
173     //的直接后继的位置，若无后继，返回 NULL
174     Link q = L.head;
175     while (q != NULL)
176     {
177         if(q == p)
178         {
179             return p->next;
180         }
181         q = q->next;
182     }
183     return NULL;
184 }
185 Status LocatePos(LinkList L, int i, Link &p)
186 {
187     //返回 p 指示线性链表 L 中第 i 个结点的位置并返回 OK
188     //i 值不合法时返回ERROR
189     int cnt = 2;
190     p = L.head;
191     if (i > L.len || i < 1)
192     {
193         return ERROR;
194     }
195     while (cnt <= i)
196     {
197         p = p->next;
198         cnt++;
199     }
200     return OK;
201 
202 }
203 Position LocateElem(LinkList L, ElemType e, Status (* compare)(ElemType, ElemType))
204 {
205     //返回线性链表中第一个与 e 满足函数compare() 判定关系的元素的位置
206     //若不存在这样的元素，返回 NULL
207 }
208 Status ListTraverse(LinkList L, Status (* visit)())
209 {
210     //依次对 L 中每个元素调用函数 visit()，一旦visit() 失败，则操作失败。
211 }
212 /**
213 My Code
214 */
215 void PrintList(LinkList L)
216 {
217     Link p = L.head->next;
218     int cnt = 1;
219     while (p != NULL && cnt <= L.len)
220     {
221         printf("%d\t", p->data);
222         p = p->next;
223         cnt++;
224     }
225     printf("\n");
226 }
227 int compare(ElemType a, ElemType b)
228 {
229     if (a < b)
230     {
231         return -1;
232     }
233     else if (a == b)
234     {
235         return 0;
236     }
237     else
238     {
239         return 1;
240     }
241 }
242 #endif

View Code

　　三.CPP文件

  1 //LinkList.h
  2 /**
  3 《数据结构（C语言版）》 Page 37
  4 ....为此，从实际应用角度出发重新定义线性链表及其基本操作....
  5 */
  6 /**
  7 author:zhaoyu
  8 email:[email protected]
  9 date:2016-6-4
 10 note:realize my textbook <<数据结构（C语言版）>>
 11 */
 12 #ifndef _LINKLIST_H_
 13 #define _LINKLIST_H_
 14 #include "head.h"
 15 #include <cstdlib>
 16 #define ElemType int
 17 typedef struct LNode{
 18     ElemType data;
 19     struct LNode *next;
 20 }*Link, *Position;
 21 typedef struct{//链表类型
 22     Link head, tail;//分别指向线性链表中的头结点和最后一个结点
 23     int len;//指示线性链表中数据元素的个数
 24 }LinkList;
 25 Status MakeNode(Link &p, ElemType e)
 26 {
 27     //分配由 p 指向的值为 e 的结点，并返回 OK；若分配失败，则返回 ERROR
 28     p = (Link)malloc(sizeof(struct LNode));
 29     if (!p)
 30     {
 31         return ERROR;
 32     }
 33     p->data = e;
 34     p->next = NULL;
 35     return OK;
 36 }
 37 Status FreeNode(Link &p)
 38 {
 39     //释放 p 所指节点
 40     p = NULL;//便于回收???释放后再次使用
 41     free(p);
 42 }
 43 Status InitList(LinkList &L)
 44 {
 45     //构造一个空的线性表L
 46     L.head = (Link)malloc(sizeof(struct LNode));
 47     L.head->data = 100;
 48     L.head->next = NULL;
 49     L.tail = L.head->next;
 50     L.len = 0;
 51 }
 52 Status ClearList(LinkList &L)
 53 {
 54     //将线性链表置为空表并释放原链表的结点空间
 55 }
 56 Status InsFirst(LinkList &L, Link &h, Link &s)
 57 {
 58     //已知 h 指向线性链表的头结点，将 s 所指节点插入在第一个结点之前
 59     //note:这里的参数与书上有些不一样，LinkList &L是我添加的
 60     //因为插入新的元素之后，链表长度应该同步变化
 61     //链表的插入是基于地址的，所以我全部加了引用
 62     //这一个函数与书上参数完全不同
 63     //更新 2016-5-5 16:46
 64     //通过分析算法2.20发现 h 不是绝对的头结点，而是接受一个 h
 65     //就以它为头结点作参考操作其它元素
 66     //这个函数花了不少时间，值得反复思考
 67     if (NULL == h)
 68     {
 69         return ERROR;
 70     }
 71     else
 72     {
 73         s->next = h->next;
 74         h->next = s;
 75     }
 76     L.len++;
 77     return OK;
 78 }
 79 Status DelFirst(Link &h, Link &q)
 80 {
 81     //已知 h 指向线性链表的头结点，删除链表中的第一个节点并以 q 返回
 82     if (h == NULL)
 83     {
 84         return ERROR;
 85     }
 86     q = h->next;
 87     h->next = q->next;
 88     q->next = NULL;
 89     return OK;
 90 }
 91 Status Append(LinkList &L, Link &s)
 92 {
 93     //将指针 s 所指（彼此以指针相链）的一串结点
 94     //链接在线性链表 L 最后一个结点
 95     Link q = L.head;
 96     while (q->next != NULL)
 97     {
 98         q = q->next;
 99     }
100     q->next = s;
101     int cnt = 0;
102     Link temp = s;
103     while (temp != NULL)
104     {
105         cnt++;
106         temp = temp->next;
107         if (NULL == temp->next)
108         {
109             L.tail = temp;//注意更新尾指针
110         }
111     }
112 
113     L.len += cnt;
114     //注意要根据这一串结点长度增加链表长度
115     return OK;
116 }
117 Status Remove(LinkList &L, Link &q)
118 {
119     //删除线性链表 L 中的尾结点并以 q 返回，改变链表的尾指针指向新的尾结点
120 }
121 Status InsBefore(LinkList &L, Link &p, Link s)
122 {
123     //已知 p 指向线性链表 L 中的一个结点，将 s 所指结点插入 p 所指节点之前
124     //并修改指针 p 指向新插入的节点
125 }
126 Status InsAfter(LinkList &L, Link &p, Link s)
127 {
128     //已知 p 指向线性链表 L 中的一个结点，将 s 所指结点插入 p 所指节点之后
129     //并修改指针 p 指向新插入的节点
130 }
131 Status SetCurElem(Link &p, ElemType e)
132 {
133     //已知 p 指向线性链表中的一个结点，用 e 更新 p 所指结点中数据元素的值
134 }
135 ElemType GetCurElem(Link p)
136 {
137     //已知 p 指向线性链表中的一个节点，返回 p 所指结点中数据元素的值
138     if (p != NULL)
139     {
140         return p->data;
141     }
142     else
143     {
144         exit(ERROR);
145     }
146 }
147 Status ListEmpty(LinkList L)
148 {
149     //若线性链表 L 为空，则返回 TRUE，否则返回 FALSE
150 }
151 int ListLength(LinkList L)
152 {
153     //返回线性链表 L 中元素的个数
154 
155 }
156 Position GetHead(LinkList L)
157 {
158     //返回线性链表 L 中头结点的位置
159     return L.head;
160 }
161 Position GetLast(LinkList L)
162 {
163     //返回线性链表 L 中最后一个结点的位置
164 }
165 Position PriorPos(LinkList L, Link p)
166 {
167     //已知 p 指向线性链表 L 中的一个结点，返回 p 所指结点直接前驱的位置
168     //若无前驱，则返回NULL
169 }
170 Position NextPos(LinkList L, Link p)
171 {
172     //已知 p 指向线性链表 L 中的一个节点，返回 p 所指结点
173     //的直接后继的位置，若无后继，返回 NULL
174     Link q = L.head;
175     while (q != NULL)
176     {
177         if(q == p)
178         {
179             return p->next;
180         }
181         q = q->next;
182     }
183     return NULL;
184 }
185 Status LocatePos(LinkList L, int i, Link &p)
186 {
187     //返回 p 指示线性链表 L 中第 i 个结点的位置并返回 OK
188     //i 值不合法时返回ERROR
189     int cnt = 2;
190     p = L.head;
191     if (i > L.len || i < 1)
192     {
193         return ERROR;
194     }
195     while (cnt <= i)
196     {
197         p = p->next;
198         cnt++;
199     }
200     return OK;
201 
202 }

鲜花

握手

雷人

路过

鸡蛋

该文章已有0人参与评论

请发表评论

全部评论

专题导读

More+

10-27 六六分期app的软件客服如何联系？(六六分期

11-06 可心卡盟:win10系统火狐flash插件崩溃怎么

11-06 亲亲特价:怎么删除回收站图标

11-06 济南大学虚拟社区:鲁大师节能降温的具体办

11-06 xlueops.exe:无线网络安装向导

11-06 女斗合众国:win7系统cf与主机连接不稳定怎

11-06 0xc000022-[cf烟雾头]cf怎么调烟雾头

11-06 qizideyouhuo:应用程序无法正常启动0xc0000

11-06 ipz-185:win7系统vcf文件怎么打开

11-06 傻哥蹦迪:win10系统s4怎么打开usb调试

11-06 八神浩树gtaste:回收站清空了怎么恢复

11-06 妖尾之黑色守护:win10系统电脑没有1440x900

11-06 校园至尊魔王小说:win7系统浏览网页时字体

11-06 女斗合众国:win10系统访问共享文件夹提示请

11-06 tokyo hot n0654:恢复win7系统默认字体一招

11-06 雨酷仙境:设置win7系统转移临时文件夹腾出

11-06 阿穆纳伊之杖:win7系统开始菜单在右边还原

11-06 tunespotting:win10系统火狐flash插件总是

11-06 甘尔葛分析师：计谋网站seo关键词暴涨有什

11-06 蔡贵霖: 计谋网站seo关键词暴涨有什么秘密

11-06 博益网首页:ao3网页版进入不了解决方法

11-06 漏斗子专栏: 网站数据分析小白易懂精华篇

11-06 见证双虹怎么做:win7系统开启telnet命令的

11-06 颾狐蝶蜋:系统资源不足无法完成请求的服务

11-06 国光中学校歌:提交网站到alexa查询详细步骤

11-06 西安有情天:静态网页和动态网页的区别

11-06 红木雅尚斋:外部链接构造对网站的好处

11-06 前官礼遇：防止域名劫持–增强域安全性的10

11-06 密传二转答案: 中文分词算法有哪些

11-06 金泉家园邮编:百度快照劫持的表现及应对方

C#子线程中更新主线程UI-----注意项发布时间：2022-07-14

c++进阶学习发布时间：2022-07-14

剪的笔顺,诠释剪的笔画,认识剪的部首

1 六六分期app的软件客服如何联系？(六六分期

六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期

阅读：19143|2023-10-27

2 可心卡盟:win10系统火狐flash插件崩溃怎么

今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知

阅读：9973|2022-11-06

3 亲亲特价:怎么删除回收站图标

今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道

阅读：8317|2022-11-06

4 济南大学虚拟社区:鲁大师节能降温的具体办

今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要

阅读：8686|2022-11-06

5 xlueops.exe:无线网络安装向导

我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多

阅读：8627|2022-11-06

6 女斗合众国:win7系统cf与主机连接不稳定怎

今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不

阅读：9643|2022-11-06

7 0xc000022-[cf烟雾头]cf怎么调烟雾头

电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很

阅读：8611|2022-11-06

8 qizideyouhuo:应用程序无法正常启动0xc0000

我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法

阅读：7991|2022-11-06

9 ipz-185:win7系统vcf文件怎么打开

今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win

阅读：8642|2022-11-06

10 傻哥蹦迪:win10系统s4怎么打开usb调试

今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎

阅读：7527|2022-11-06

客服电话

电子邮件

数据结构算法C语言实现（五）---2.3重新定义线性链表及其基本操作 ...

请发表评论

全部评论

上一篇：

下一篇：

Delphi中文本文件的操作

dphi-official/Machine_Learning_Bootcamp

juven/maven-bash-completion: Maven Bash

win7系统注册表编辑器打开的操作方法

route101/mastoinker: Quick image view as

剪的笔顺,诠释剪的笔画,认识剪的部首

六六分期app的软件客服如何联系？(六六分期

florent37/ViewAnimator: A fluent Android

florent37/Shrine-MaterialDesign2: implem

CVE-2020-36276

SimpleSoftwareIO/simple-sms: Send and re

关于我们

产品与服务

解决方案

139-2527-9053