【原创】《算法导论》链表一章带星习题试解——附C语言实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【原创】《算法导论》链表一章带星习题试解——附C语言实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2078字,纯文字阅读大概需要3分钟。
内容图文
![【原创】《算法导论》链表一章带星习题试解——附C语言实现](/upload/InfoBanner/zyjiaocheng/1131/f3977e86285546578607954cce4522fd.jpg)
原题:
双向链表中,需要三个基本数据,一个携带具体数据,一个携带指向上一环节的prev指针,一个携带指向下一环节的next指针。请改写双向链表,仅用一个指针np实现双向链表的功能。定义np为next XOR prev,请根据表头提供的信息,为双向链表编写插入函数、删除函数和查找函数,并在O(1)时间内实现链表的翻转。
分析:
问题的关键,在于怎样利用prev指针和next指针的异或结果,来获得上一节点或下一节点的地址值。也就是说,如何利用异或来算出具体的prev及next值。我们注意到两点:
1、A XOR B = C => C XOR B = A AND C XOR A = B。A、B两个元素的异或结果C,同A异或后得B,同B异或后得A。也就是说,如果我们能获取到next或者prev其中的一个值,我们就能根据np计算出另一个值。
2、双向链表中,头结点的prev值为0,尾结点的next值为0,因此,可以根据这一点,计算出全部的结点prev及next地址。依据第一点,表头信息需要提供头结点的地址。
实现:
C语言中,指针变量中存储的数值不能直接参与异或运算,需要转换为int型变量参与运算,再转换为指针来指定特定的地址。
根据前述分析,定义两个结构体如下:
typedef struct Node
{
int num;
int np;
}Node;
作为结点的结构体,包含结点必须的两个数据:类型为int的num数据单元,和类型为int的np指针,其中np指针中包含了next和prev两个结点的地址。
typedef struct double_train
{
Node *head;
int length;
}double_train;
作为双向链表的表头,提供了链表的大小、头结点两个数据,以供他人操作该链表。
插入函数void Insert(double_train *L , int value):
该函数接受两个参数——链表L和数据value,该函数的功能为将数据value插入表头。具体代码如下:
void
Insert(double_train *L , int value)
{
Node *p = (Node *)malloc(sizeof(Node));
int temp2;
int temp1;
p->num = value;
temp2 = (int) L->head;
temp2 = 0 ^ temp2;
p->np = temp2;
//插入一个新节点P,设置prev为0,next为L->head,并表示为np。
if(L->head != NULL)
{
temp1 = (int) p;
temp2 = L->head->np;
L->head->np = temp1 ^ temp2;
}
//若链表非空,则更新原先头结点的np值。
L->head = p;
L->length ++;
}
展示函数 void View(double_train *L):
该函数接受一个参数——链表L,该函数的功能为列出链表L中的所有数据单元。具体代码如下:
void
View(double_train *L)
{
int temp1,Last = 0;
Node *Next;
Node *top = L->head;
int count = L->length;
while(count != 0) //从头结点开始,根据每个节点的np值遍历链表
{
temp1 = L->head->np ^ Last;
Next = (Node *) temp1;
Last = (int) L->head;
L->head = Next;
count --;
}
L->head = top;
}
删除函数和查找函数代码从略。下面是主函数测试代码,在windows gcc下编译通过并输出正确结果:
int
main(void) //programmed by wmydx
{
double_train test;
double_train *L = &test;
L->length = 0;
L->head = NULL; //C并非面向对象,因此不能用构造函数初始化
for(int i = 0;i < 5;i++)
{
Insert(L,i);
}
View(L);
system("pause");
}
那么如何实现在O(1)的时间内对链表进行翻转呢?只需要在链表结构体中加一个记录尾结点 Node *tail的代码,然后exchange tail->np with head->np即可完成。
原文:http://www.cnblogs.com/shadowmydx/p/4026517.html
内容总结
以上是互联网集市为您收集整理的【原创】《算法导论》链表一章带星习题试解——附C语言实现全部内容,希望文章能够帮你解决【原创】《算法导论》链表一章带星习题试解——附C语言实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。