• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#子线程中更新主线程UI-----注意项发布时间:2022-07-14
下一篇:
c++进阶学习发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap