C++设计单链表习题及解答-创新互联

题目：实现一个单链表，链表初始为空，支持三种操作：

公司主营业务：成都网站建设、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联推出平南免费做网站回馈大家。

• 向链表头插入一个数
• 删除第 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的时候都得改，这样较为方便