C++经典基础题(链表).doc

//声明: 以下函数均是个人编写，不代表最安全的编码实践 //取材均是 很常见的 C++基础题，对初学习C++者应该帮助很大。 //面试中常考的。欢迎下载学习。Main函数中为测试用例 // test.cpp : Defines the entry point for the console application. // #include stdafx.h #include assert.h #include iostream using namespace std; //定义链表 typedef struct student { student* next; int data; }node; //从输入流中创建链表，读取的数字依次存入链表中，当输入0时，该链表结束创建，并且0不存入链表中 node* create() { node* head=new node; head-next=NULL; node* p=head; int x(0); while(1) { printf(please input a number); scanf(%d,x); if(x) { node* p1=new node; p1-data=x; p-next=p1; p=p1; } else break; } p-next=NULL; return head-next; } //从链表中删除指定的元素 node* del(node* head,int num) { node* p=head; node* prev=NULL; while(pp-data!=num) { prev=p; p=p-next; } if(!p) { printf(no element is found); return head; } if(p==head) { node* p=head-next; free(head); return p; } prev-next=p-next; free(p); return head; } //在链表中插入一个数，此时假定该链表是个有序的链表，即链表是根据其中的数据是按从小到大的排列的 node* insert(node* head,int num) { node* p=head; node* prev=NULL; while(p(num(p-data))) { prev=p; p=p-next; } node* pNewNode=new node; pNewNode-data=num; if(p==head) { pNewNode-next=head; return pNewNode; } if(!p) { prev-next=pNewNode; pNewNode-next=NULL; return head; } prev-next=pNewNode; pNewNode-next=p; return head; } //将链表顺序反转 node* reverse(node* head) { if(!head || !(head-next)) return head; node* p1=head; node* p2=head-next; node* p3=p2-next; head-next=NULL; while(p3) { p2-next=p1; p1=p2; p2=p3; p3=p3-next; } p2-next=p1; return p2; } //融合两个链表，前提是Head1和head2是两个有序的链表，即都是从小到大排列的 //merge对Head1和head2实行重组，因此融合后,head1和head2指向的内容均被改变。 node* merge(node* head1,node* head2) { assert(head1!=NULL head2!=NULL); node* p1=head1; node* p2=head2; node* p3=new node,*p4; p4=p3; while(p1p2) { if(p1-datap2-data) { p3-next=p1; p1=p1-next; } else { p3-next=p2; p2=p2-next; } p3=p3-next; } if(!p1) p3-next=p2; else p3-next=p1; p3