C++设计单链表习题及解答-创新互联
C++设计单链表习题及解答
网页题目:C++设计单链表习题及解答-创新互联
当前地址:http://scyanting.com/article/diicoj.html
题目:实现一个单链表,链表初始为空,支持三种操作:
公司主营业务:成都网站建设、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。成都创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联推出平南免费做网站回馈大家。
- 向链表头插入一个数
- 删除第 k 个插入的数后面的数;
- 在第 k 个插入的数后插入一个数
(不知道这里题目有没有理解错,我理解的是删除第k个插入的数(x),x的指针next所指向的数,即删除第k-1个插入的数)
第一版源代码:
#include#includeusing namespace std;
typedef struct ListNode
{int data;//数据域
struct ListNode*next;//指针域
}*L;//相当于typedef struct ListNode*L;
//创建节点
void CreateListNode(L*head) //改变链表的操作要用指针传链表 ,也可以不用void,而用指针类型的函数 L CreateListNode(L head){...return head;},这里只是想麻烦地练练手,嘻嘻
{*head = (ListNode *)malloc(sizeof(ListNode)); //创建头结点,为头结点分配内存
(*head)->next = NULL;//初始化头结点的指针head为空指针
}
//向链表头插入一个数
void addAtHead(L*head,int val)
{L newhead=(ListNode *)malloc(sizeof(ListNode));//创建新的头结点,为新的头结点分配内存
newhead->next=(*head)->next;
(*head)->next=newhead;
newhead->data=val;
}
//删除第 k 个插入的数后面的数
void deleteAtIndex(L*head,int k)
{L cur=*head;//辅助指针从第一个节点开始
while(k--)//遍历到第k个位置(非下标),循环次数是k次
{cur=cur->next;
}
L p=cur->next;
if(cur->next->next!=NULL)
cur->next = cur->next->next;
else cur->next=NULL;
free(p);
}
//在第 k 个插入的数后插入一个数
void addAtIndex(L*head,int k,int val)
{L newnode=(ListNode *)malloc(sizeof(ListNode));
L cur=*head;//辅助指针从头指针开始
while(k--) cur=cur->next;//遍历到第k个节点(非下标),循环次数是k次
newnode->next=cur->next;
cur->next=newnode;
newnode->data=val;
}
//打印出链表形态
void printlist(L head)
{L newnode=head->next;
while(newnode!=NULL)
{cout<data;
if(newnode->next!=NULL)cout<<"->";
newnode=newnode->next;
}
cout<L head;
CreateListNode(&head);
int n,x1,k,x2;
cin>>n;
for(int i=0;icin>>x1;
addAtHead(&head,x1);
}
cin>>k;
cin>>x2;
cout<<"n="<
运行结果:
写完才发现,好像混用了C和C++(心痛的感觉),于是经过一番折腾,又诞生了第二版题解
改进:
①引用了C++的struct中特有的构造函数(C没有)
②采用类class
③把malloc换成new
其它一样
第二版源代码:
#includeusing namespace std;
typedef struct ListNode
{int data;
struct ListNode *next;
ListNode(int x) : data(x), next(NULL) {}//有参数构造函数,就是初始化, 注意:若要初始化数组,需先写无参数构造函数
}*L;
class MyLinkedList
{private://private在其他类中被隐藏
L head;
public://把public的函数写在class外更为清晰明了
CreateListNode();
void addAtHead(int val);
void addAtIndex(int k, int val);
void deleteAtIndex(int k);
void printlist();
};//被漏掉的分号(尴尬)
MyLinkedList::CreateListNode()
{head=new ListNode(0);//不能在private内初始化
}
void MyLinkedList::addAtHead(int val)
{L newhead=new ListNode(val);//new是堆中的内存块,与之前的malloc作用相同
newhead->next=head->next;
head->next=newhead;
newhead->data=val;
}
void MyLinkedList::addAtIndex(int k, int val)
{L newnode=new ListNode(val);
L cur=head;
while(k--) cur=cur->next;
newnode->next=cur->next;
cur->next=newnode;
newnode->data=val;
}
void MyLinkedList::deleteAtIndex(int k)
{L cur=head;
while(k--)
{cur=cur->next;
}
L p=cur->next;
if(cur->next->next!=NULL)
cur->next = cur->next->next;
else cur->next=NULL;
delete p;//与之前的free作用相同 ,new分配的内存块由程序员释放(编译器不管) ,所以也要回收
}
void MyLinkedList::printlist()
{L newnode=head->next;
while(newnode!=NULL)
{ cout<data;
if(newnode->next!=NULL)cout<<"->";
newnode=newnode->next;
}
cout<MyLinkedList object;//MyLinkedList类里的object成员
object.CreateListNode();
int n,x1,k,x2;
cin>>n;
for(int i=0;icin>>x1;
object.addAtHead(x1);
}
cin>>k;
cin>>x2;
cout<<"n="<
运行结果:(和之前一样)
学习心得:刚开始写的时候还不知道头结点(不是第一个节点)的好处,写着写着才发现如果不设头指针,链表开始的位置在每一次addAtHead的时候都得改,这样较为方便
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页题目:C++设计单链表习题及解答-创新互联
当前地址:http://scyanting.com/article/diicoj.html