哪位朋友帮忙做下数据结构的题目，我会非常感谢三．假定一个线性-查字典问答网

来自黄照强的问题

　　哪位朋友帮忙做下数据结构的题目，我会非常感谢三．假定一个线性表用带头结点的单链表表示，数据元素是整数类型，头指针为head，(1)试定义单链表的结构；(2)试写出算法（C函数）：将

　　哪位朋友帮忙做下数据结构的题目，我会非常感谢

　　三．假定一个线性表用带头结点的单链表表示，数据元素是整数类型，头指针为head，

　　(1)试定义单链表的结构；

　　(2)试写出算法（C函数）：将该单链表分割为两个均带头结点的单链表：一个是由该单链表的数据元素值为偶数的结点组成的，另一个是由该单链表的数据元素值为奇数的结点组成的，希望在逻辑上仍保持原结点前后之间的相对次序不变；

　　(3)分析你的算法的时间复杂度。

1回答

2020-06-09 16:50

我要回答

请先登录

林兆花

　　typedefstructNode//结点定义

　　{

　　intdata;

　　Node*next;

　　}Node;

　　//链表拆分，其中head是源链表头指针，oddList是偶数链表头指针，evenList是奇数结点链表

　　voidsplitLinklist(Node*head,Node*&oddList,Node*&evenList)

　　{

　　Node*p,*q,*r;

　　p=head->next;

　　q=oddList;

　　r=evenList;

　　while(p!=NULL)

　　{

　　if(p->data%2==0)//偶数结点插入oddList

　　{

　　q->next=p;

　　p=p->next;

　　q=q->next;//q总是指向链表oddList最后一个结点

　　q->next=NULL;

　　}

　　else

　　{

　　r->next=p;

　　p=p->next;

　　r=r->next;//r总是指向链表evenList最后一个结点

　　r->next=NULL;

　　}

　　整个过程遍历链表一次，假设链表长度为n，那么时间复杂度就为O（n）

2020-06-09 16:53:14