程序面试题——C实现

平台：win10 x64 +VC6.0

2019/5/22

1.合并三个有序的链表

链表节点定义
struct node
{
    int val;
    struct node* next;
};

struct node* merge_3 (形参由你定义)
{
    //这部分是实现
}

当输入的有序链表是多个的时候，请给出合并算法，并假设链表个数为m，平均长度为n，请分析时间复杂度

1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define MAXSIZE 20
  4  
  5 typedef int ElemType;
  6 typedef struct Node
  7 {
  8     ElemType data;
  9     struct Node *next;
 10  
 11 }Node;
 12  
 13 typedef struct Node *LinkList;
 14  
 15 // 初始化链表
 16 bool InitList(LinkList *L) // 二级指针
 17 {
 18     *L = (LinkList)malloc(sizeof(Node));  //产生头结点，并使L指向此头节点
 19     if (!(*L))   // 存储分配失败
 20         return false;
 21     (*L)->next = NULL;
 22     return true;
 23 }
 24 void CreateFromTail(LinkList L)
 25 {
 26     Node *r, *s;
 27     int temp;
 28     r = L;  // r指向链表的当前表尾，其初值指向头节点
 29     while (1)
 30     {
 31         scanf("%d", &temp);
 32         if (temp == -1)
 33         {
 34             r->next = NULL;
 35             break;
 36         }
 37         s = (Node*)malloc(sizeof(Node));   // 建立新结点s
 38         s->data = temp;
 39         r->next = s;
 40         r = s;
 41         
 42     }
 43 }
 44  
 45 // 遍历链表
 46 void PrintList(LinkList L)
 47 {
 48     bool flag = true;
 49     Node *p;
 50     p = L->next;
 51     while (p)
 52     {
 53         if (flag)
 54         {
 55             printf("%d", p->data);
 56             flag = false;
 57         }
 58         else
 59             printf(" %d", p->data);
 60         p = p->next;
 61     }
 62     printf("\n");
 63 }
 64  
 65 LinkList MergeLinkList(LinkList L1, LinkList L2)
 66 {
 67     LinkList L3;
 68     InitList(&L3);
 69     
 70     Node *p, *q, *r, *s;
 71     p = L1->next;
 72     q = L2->next;
 73     r = L3;
 74     while (p&&q)
 75     {
 76         if (p->data < q->data)
 77         {
 78             s = (Node*)malloc(sizeof(Node));
 79             s->data = p->data;
 80             s->next = NULL;
 81             r->next = s;
 82             r = s;
 83             p = p->next;
 84         }
 85         else
 86         {
 87             s = (Node*)malloc(sizeof(Node));
 88             s->data = q->data;
 89             s->next = NULL;
 90             r->next = s;
 91             r = s;
 92             q = q->next;
 93         }
 94     }
 95     
 96     if (p == NULL)
 97     {
 98         r->next = q;
 99     }
100     if (q == NULL)
101     {
102         r->next = p;
103     }
104     return L3;
105 }
106  
107 int main()
108 {
109     LinkList L1,L2,L3,L4;
110     InitList(&L1);  // 指针的地址
111     InitList(&L2);  // 指针的地址
112     InitList(&L3);  // 指针的地址
113     InitList(&L4);  // 指针的地址
114     CreateFromTail(L1);
115     PrintList(L1);
116     CreateFromTail(L2);
117     PrintList(L2);
118     CreateFromTail(L3);
119     PrintList(L3);
120     L4 = MergeLinkList(L1, L2);
121     PrintList(L4);
122     L4 = MergeLinkList(L3, L4);
123     PrintList(L4);
124     if (L4->next)
125         PrintList(L4);
126     else
127         printf("NULL\n");
128  
129 }

合并三个有序的链表

时间复杂度：O(max(length(L1),length(L2),length(L1)+length(L2),length(L3)))

2019/5/23

1.“ hello world”转为“ world hello”

思路：参看 C语言字符串指针（指向字符串的指针）详解：http://c.biancheng.net/view/2012.html

1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 void ReverseString(char* s, int from, int to)
 5 {
 6     while(from < to)
 7     {
 8         char t = s[from];
 9         s[from++] = s[to];
10         s[to--] = t;
11     }
12 }
13 
14 void LeftRotateString(char* s, int n, int m)
15 {
16     m %=n;
17     ReverseString(s, 0, m-1);
18     ReverseString(s, m+1, n-1);
19     ReverseString(s, 0, n-1);
20 }
21 
22 int main(void)
23 {
24     int n = 0, m = 0, i;
25     char s[] = "hello world";
26     printf("转换前的字符串为:%s\n", s);
27     n = strlen(s);
28     for(i = 0; i < n; i++)
29         if(s[i] == ' ')
30             m = i;
31 
32     printf("n=%d,m=%d\n", n,m);
33     LeftRotateString(s, n, m);
34     printf("转换后的字符串为:%s\n", s);
35     return 0;
36 }

字符串反转

时间复杂度O(n)，空间复杂度O(1)

2.无序数组，找出全部重复元素

思路：参看《编程之法》1.1字符串的旋转 解法二：三步反转

1 #include <stdio.h>
 2  
 3 /* 判断一个数组中是否有重复元素，若有，返回位置及元素 */
 4 void hasDup(int arr[], int n)
 5 {
 6     int i, j;
 7     for(i=0; i<n-1; i++)
 8     {    for(j=i+1; j<n; j++)
 9             if(arr[j] == arr[i])
10             {
11                 printf("数组中第%d个位置存在重复元素:%d\n",j,arr[i]);            
12                 break;    
13             }
14             continue;
15     }
16 }
17  
18 /* 主函数 */
19 int main()
20 {
21     int arr[] = {12, 6, 22, 9, 16, 50, 18, 9, 6, 9};
22     int n = 10;
23 
24     hasDup(arr, n);     
25  
26     return 0; 
27 }

查找无序数组重复元素及位置

3.给定数组arr，返回arr的最长递增子序列

​

1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h> 
 4 int main()
 5 {
 6     int n=1,k[10000],h[1000],g=0,j,t;
 7     char c;
 8     char m[100000];
 9     printf("请输入子序列：");
10     memset(k,0,sizeof(k)); //把数组k元素全置为零
11     while(n--)
12     {
13         int i=0,l=0;
14         getchar();//滤掉回车
15         while((c=getchar())!='\n')
16         {
17             m[i++]=c;//把输入的元素逐个存入数组
18         }
19           for(j=0;j<i-1;j++)
20          {
21              if(m[j]<m[j+1])
22              {
23                  k[l]=k[l]+1;
24              }
25              else
26                 l++;
27          }
28          l++;
29          if(l==2)
30          {
31              if(k[0]<k[1])
32              {
33                 t=k[0];
34                 k[0]=k[1];
35                 k[1]=t;
36              }
37          }
38           if(l>2)
39          {
40                for(j=0;j<l-1;j++)
41                  for(i=0;i<l-j-1;i++)
42                      if(k[i]<k[i+1])
43                      {
44                       t=k[i];
45                       k[i]=k[i+1];
46                       k[i+1]=t;
47                      }
48          }
49          
50          h[g]=k[0];
51          g++;
52      }
53     for(int i=0;i<g;i++)
54     {
55         printf("\n");
56         printf("单调递增最长子序列长度为：%d\n",h[i]+1);
57     }
58     return 0;  
59 }

输入数组arr,返回最长递增子序列的长度

4.升序数组，找出最接近定值sum的两个元素，并输出

问题：long long定义时，如果还用scanf()函数输入，编译器不报错，但是输入的数字完全改变。

1 #include<stdio.h>
 2 #include<stdlib.h>
 3 int a[1000];//存放升序排列的一列数字
 4 int b[1];//存放要找的数字
 5 int m;//输入要查找的数的个数
 6 long finder(int mx, int mn, int mid, int j)//
 7 {//第一步区分查找的这个数是否在开区间内
 8     if (b[j] <= a[mn] || b[j] >= a[mx])//不在
 9     {
10         //对内部进行细分，到底是比最小的还小，还是比最大的还大
11         if (b[j] <= a[mn])  //比最小的还小
12         {    
13             printf("%d\n", a[mn]);
14             printf("%d\n", a[mn+1]);
15         }
16         else//比最大的还大
17         {
18             printf("%d\n", a[mx-1]);
19             printf("%d\n", a[mx]);
20         }
21     }
22     else//位于最小的数字和最大的数字之间
23     {
24         //根据mid来分，比mid大还是比mid小，还是和mid相等
25         if (a[mn]<b[j] && b[j]<a[mid])//比mid小
26         {
27             if (mid - mn != 1)
28             {
29                 mx = mid - 1;//将mx替换为mid
30                 mid = (mn + mx) / 2;//重新计算mid下标
31                 finder(mx, mn, mid, j);
32             }
33             else
34             {
35                 if (a[mid] - b[j]>b[j] - a[mn])//比较距离
36                     printf("%d\n", a[mn]);
37                 else if (a[mid] - b[j]<b[j] - a[mn])
38                     printf("%d\n", a[mid]);
39                 else
40                     printf("%d %d\n", a[mn], a[mid]);
41             }
42  
43         }
44         else if (a[mid]<b[j] && b[j]<a[mx])//比mid大
45         {
46  
47             if (mx - mid != 1)
48             {
49                 mn = mid;//重新计算mn
50                 mid = (mn + mx) / 2;//重新计算mid下标
51                 finder(mx, mn, mid, j);
52             }
53             else
54             {
55                 if (b[j] - a[mid]>a[mx] - b[j])
56                     printf("%d\n", a[mx]);
57                 else if (b[j] - a[mid]<a[mx] - b[j])
58                     printf("%d\n", a[mid]);
59                 else
60                     printf("%d %d\n", a[mid], a[mx]);
61             }
62         }
63         else//和mid相等
64         {
65             printf("%d\n", b[j]);
66             if((b[j]-a[mid-1]) >= (a[mid+1]-b[j]))
67                 printf("%d\n", a[mid+1]);
68             else
69                 printf("%d\n", a[mid-1]);
70         }
71     }
72     return 0;
73 }
74 int main()
75 {
76     int j = 0;//用作函数循环的
77     int n;//输入非降序序列的长度
78     printf("请输入非降序序列的长度：");    
79     scanf("%d", &n);
80     printf("请输入非降序序列：");    
81     for (int i = 0; i<n; i++) //循环输入n个数字
82         scanf("%d", &a[i]);
83     //scanf("%d", &m);    //输入要查询的数字个数
84     //for (int i = 0; i<m; i++) //循环输入要查找的数，存在b[i]中
85     printf("请输入要查找的元素sum：");    
86         scanf("%d", &b[0]);
87     int mx = n - 1, mn = 0;
88     int mid = (mx + mn) / 2;
89 //    for (j = 0; j<m; j++)//循环调用函数，把b[j]中存储的所有要找的数字找完
90         finder(mx, mn, mid, 0);
91     //system("pause");
92     return 0;
93  
94 }

输入一升序数组，返回最接近给定值的两个元素