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

赵裕(vimerzhao)

2016-06-06 (最后修改: 2026-07-30)

本文约 3800 字，阅读需 8 分钟。

一.简述

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

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

二.头文件

  1 //LinkList.h
  2 /**
  3 《数据结构（C语言版）》 Page 37
  4 ....为此，从实际应用角度出发重新定义线性链表及其基本操作....
  5 */
  6 /**
  7 author:zhaoyu
  8 email:zhaoyu1995.com@gmail.com
  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:zhaoyu1995.com@gmail.com
  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 }
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

四.测试

总阅读量次。