| « | July 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | |
|
公告 |
|
谦卑，荣誉，牺牲，英勇，怜悯，诚实，精神，公正。 |
| Blog信息 |
|
blog名称:
日志总数:183
评论数量:698
留言数量:7
访问次数:3020859
建立时间:2005年12月29日 |
| |
|
 [编程学习]Sort
软件技术
newqiang 发表于 2006/11/7 22:31:19 |
| 文件中有一组整数，要求排序后输出到另一个文件中答案：
＃i nclude<iostream>
＃i nclude<fstream>
using namespace std;
void Order(vector<int>& data) //bubble sort{int count = data.size() ;int tag = false ; // 设置是否需要继续冒泡的标志位for ( int i = 0 ; i < count ; i++){for ( int j = 0 ; j < count - i - 1 ; j++){if ( data[j] > data[j+1]){tag = true ;int temp = data[j] ;data[j] = data[j+1] ;data[j+1] = temp ;}}if ( !tag )break ;}}
void main( void ){vector<int>data;ifstream in("c:\\data.txt");if ( !in){cout<<"file error!";exit(1);}int temp;while (!in.eof()){in>>temp;data.push_back(temp);}in.close(); //关闭输入文件流Order(data);ofstream out("c:\\result.txt");if ( !out){cout<<"file error!";exit(1);}for ( i = 0 ; i < data.size() ; i++)out<<data[i]<<" ";out.close(); //关闭输出文件流}
40. 链表题：一个链表的结点结构struct Node{int data ;Node *next ;};typedef struct Node Node ;
(1)已知链表的头结点head,写一个函数把这个链表逆序 ( Intel)
Node * ReverseList(Node *head) //链表逆序{if ( head == NULL || head->next == NULL )return head;Node *p1 = head ;Node *p2 = p1->next ;Node *p3 = p2->next ;p1->next = NULL ;while ( p3 != NULL ){p2->next = p1 ;p1 = p2 ;p2 = p3 ;p3 = p3->next ;}p2->next = p1 ;head = p2 ;return head ;}(2)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。(保留所有结点，即便大小相同）Node * Merge(Node *head1 , Node *head2){if ( head1 == NULL)return head2 ;if ( head2 == NULL)return head1 ;Node *head = NULL ;Node *p1 = NULL;Node *p2 = NULL;if ( head1->data < head2->data ){head = head1 ;p1 = head1->next;p2 = head2 ;}else{head = head2 ;p2 = head2->next ;p1 = head1 ;}Node *pcurrent = head ;while ( p1 != NULL && p2 != NULL){if ( p1->data <= p2->data ){pcurrent->next = p1 ;pcurrent = p1 ;p1 = p1->next ;}else{pcurrent->next = p2 ;pcurrent = p2 ;p2 = p2->next ;}}if ( p1 != NULL )pcurrent->next = p1 ;if ( p2 != NULL )pcurrent->next = p2 ;return head ;}(3)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。 (Autodesk)答案：Node * MergeRecursive(Node *head1 , Node *head2){if ( head1 == NULL )return head2 ;if ( head2 == NULL)return head1 ;Node *head = NULL ;if ( head1->data < head2->data ){head = head1 ;head->next = MergeRecursive(head1->next,head2);}else{head = head2 ;head->next = MergeRecursive(head1,head2->next);}return head ;}
41. 分析一下这段程序的输出 (Autodesk)class B{public:B(){cout<<"default constructor"<<endl;}~B(){cout<<"destructed"<<endl;}B(int i):data(i) //B(int) works as a converter ( int -> instance of B){cout<<"constructed by parameter " << data <<endl;}private:int data;};
B Play( B b) {return b ;}
(1) results:int main(int argc, char* argv[]) constructed by parameter 5{ destructed B(5)形参析构B t1 = Play(5); B t2 = Play(t1); destructed t1形参析构return 0; destructed t2 注意顺序！} destructed t1
(2) results:int main(int argc, char* argv[]) constructed by parameter 5{ destructed B(5)形参析构B t1 = Play(5); B t2 = Play(10); constructed by parameter 10return 0; destructed B(10)形参析构} destructed t2 注意顺序！
destructed t1
42. 写一个函数找出一个整数数组中，第二大的数 （microsoft）答案：const int MINNUMBER = -32767 ;int find_sec_max( int data[] , int count){int maxnumber = data[0] ;int sec_max = MINNUMBER ;for ( int i = 1 ; i < count ; i++){if ( data[i] > maxnumber ){sec_max = maxnumber ;maxnumber = data[i] ;}else{if ( data[i] > sec_max )sec_max = data[i] ;}}return sec_max ;}
43. 写一个在一个字符串(n)中寻找一个子串(m)第一个位置的函数。
KMP算法效率最好，时间复杂度是Ｏ(n+m)。
44. 多重继承的内存分配问题： 比如有class A : public class B, public class C {} 那么A的内存结构大致是怎么样的？这个是compiler-dependent的, 不同的实现其细节可能不同。如果不考虑有虚函数、虚继承的话就相当简单；否则的话，相当复杂。可以参考《深入探索C++对象模型》，或者：http://blog.csdn.net/wfwd/archive/2006/05/30/763797.aspx
45. 如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针） struct node { char val; node* next;} bool check(const node* head) {} //return false : 无环；true: 有环
一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：bool check(const node* head){ if(head==NULL) return false; node *low=head, *fast=head->next; while(fast!=NULL && fast->next!=NULL) { low=low->next; fast=fast->next->next; if(low==fast) return true; } return false;} |
|
|
回复:Sort
软件技术
ajunjun(游客)发表评论于2006/11/26 22:13:51 |
|
» 1 »
|