数据结构(5)-线性表面试题
2020-04-12 本文已影响0人
xxxxxxxx_123
准备工作
定义单链表结构，初始化单链表，通过数组生成单链表，打印链表元素。
#define L_MAX_SIZE 100
#define T_ERROR -1
#define T_OK 1
typedef int TStatus;
typedef int ElementType;
typedef struct Node{
ElementType data;
struct Node *next;
}Node;
typedef struct Node * linkList;
TStatus InitLinkList(linkList *ll) {
*ll = (linkList)malloc(sizeof(Node));
if (*ll == NULL) {
return T_ERROR;
}
(*ll)->next = NULL;
(*ll)->data = -1;
return T_OK;
}
TStatus CreateLinkListWithTrail(linkList *ll, int arr[], int size) {
*ll = (linkList)malloc(sizeof(Node));
(*ll)->data = -1;
(*ll)->next = NULL;
linkList trail = *ll; // 最后一个元素
for (int i = 0; i < size; i++) {
int e = arr[i];
linkList p = (linkList)malloc(sizeof(Node));
p->data = e;
p->next = NULL;
trail->next = p;
trail = p;
}
return T_OK;
}
TStatus PrintLinkList(linkList *ll) {
printf("***********循环打印开始*********\n");
linkList p = *ll;
while (p) {
if (p->data != -1) {
printf("====%d====\n", p->data);
}
p = p->next;
}
printf("***********循环打印结束*********\n");
return T_OK;
}
正题
- 将2个递增的有序链表合并为⼀个有序链表，要求结果链表仍然使用这两个链表的存储空间，不另外占用其他的存储空间，而且表中不不允许有重复的数据。如：
{2, 4, 6, 8} 和 {4, 6, 8, 10} => {2, 4, 6, 8, 10}
该题目中需要注意的点有2个，一是不占用其他存储空间，所以我们不能开辟新的结点空间；二是需要主要把重复的数据去重之后，要释放结点的内存。
TStatus MergeIncrementLinkList(linkList *l1, linkList *l2, linkList *l3) {
if (*l1 == NULL && *l2 == NULL) {
return T_ERROR;
}
linkList lq1 = (*l1)->next;
linkList lq2 = (*l2)->next;
(*l3) = *l1;
linkList lq3 = (*l3);
linkList temp;
while (lq1 && lq2) {
// 判断 lq1->data 和 lq2->data的大小
// 谁小就把lq3往谁那里指
if (lq1->data < lq2->data) {
// 将lq3的next指针指向lq1
lq3->next = lq1;
// 移动lq3指针到下一个位置，保证lq3是链表的最后一个位置
lq3 = lq3->next;
lq1 = lq1->next;
} else if (lq1->data > lq2->data) {
lq3->next = lq2;
lq3 = lq3->next;
lq2 = lq2->next;
} else {
lq3->next = lq1;
lq3 = lq3->next;
lq1 = lq1->next;
temp = lq2->next;
// 释放结点空间
free(lq2);
lq2 = temp;
}
}
// 由于是递增链表，跳出循环之后 如果某一个链表有值 说明这些值都比已经被lq3指向的值大
// 所以直接修改指针的指向即可
lq3->next = lq1 ? lq1: lq2;
return T_OK;
}
- 已知两个链表
A和B分别表示两个集合。其元素递增排列。设计⼀个算法，⽤于求出A与B的交集，并存储在A链表中。如
{2, 4, 6, 8} 和 {4, 6, 8, 10} => {4 ,6 , 8}
这个题目其实和上个题目很类似，修改指针指向，释放不相同结点即可。
TStatus GetIntersection(linkList *l1, linkList *l2, linkList *l3) {
if (*l1 == NULL && *l2 == NULL) {
return T_ERROR;
}
linkList lq1 = (*l1)->next;
linkList lq2 = (*l2)->next;
(*l3) = *l1;
linkList lq3 = (*l3);
linkList temp;
while (lq1 && lq2) {
if (lq1->data < lq2->data) {
temp = lq1->next;
free(lq1);
lq1 = temp;
} else if (lq1->data > lq2->data) {
temp = lq2->next;
free(lq2);
lq2 = temp;
} else {
lq3->next = lq1;
lq3 = lq3->next;
lq1 = lq1->next;
temp = lq2->next;
free(lq2);
lq2 = temp;
}
}
// 由于是递增链表，跳出循环之后 如果某一个链表有值 全部释放即可
while (lq1) {
temp = lq1->next;
free(lq1);
lq1 = temp;
}
while (lq2) {
temp = lq2->next;
free(lq2);
lq2 = temp;
}
return T_OK;
}
- 设计一个算法，将链表中所有节点的链接方向"原地旋转"，即要求仅利用原表的存储空间。换句话说，要求算法空间复杂度为
O(1)。如
{0, 2, 4, 6, 8, 10} 逆转后：{10, 8, 6, 4, 2, 0}
逆序链表，其实就相当于将原来链表中的结点按照原来的顺序使用前插法重新插一遍即可。
TStatus InverseLinkList(linkList *ll) {
linkList p, q;
p = (*ll)->next;
(*ll)->next = NULL;
// 遍历链表 用前插法重新插一遍
while (p) {
// 先保存下一个结点
q = p->next;
// 使用头插法将元素重新插入
// 自己的next指向后面
p->next = (*ll)->next;
// 表头的next指向自己
(*ll)->next = p;
p = q;
}
return T_OK;
}
- 设计⼀个算法,删除递增有序链表中值大于等于
mink且⼩于等于maxk的所有元素(mink、maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同)。
{1, 2, 4, 5, 6, 8, 10}, mink = 4, maxk = 9 => {1, 2, 10}
判断限制条件，改变指针指向即可，释放不符合条件的结点。
TStatus GetIntervalLinkList(linkList *l1, linkList *l2, int mink, int maxk) {
if ((maxk < mink) || *l1 == NULL) {
return T_ERROR;
}
linkList lq1 = (*l1)->next;
(*l2) = *l1;
linkList lq2 = (*l2);
linkList temp;
while (lq1) {
if (lq1->data < mink || lq1->data > maxk) {
lq2->next = lq1;
lq2 = lq2->next;
lq1 = lq1->next;
} else {
temp = lq1;
free(lq1);
lq1 = temp->next;
}
}
return T_OK;
}
- 设将
n(n>1)个整数存放到一维数组R中，试设计一个在时间和空间两⽅面都尽可能高效的算法，将R中保存的序列循环左移p个位置(0<p<n)个位置, 也就是将R中的数据由(x0,x1,......,xn-1)变换为(xp,xp+1,...,xn-1,x0,x1,...,xp-1)。
{0,1,2,3,4,5,6,7,8,9}, n = 10,p = 3 => {3,4,5,6,7,8,9,0,1,2}
这个题目有两种思路：
- 使用辅助空间，将前
p个元素装起来，移动原来数组，再把之前的辅助空间的p个元素放到后面原来数组的后面 - 使用逆序的方式，首先把元素整体进行一遍逆序，然后在前
n-p个元素逆序，最后再把后p个元素逆序，通过3次逆序的方式实现
下面我们来看一下具体的实现：
第一种方式：
TStatus LeftShiftArray1(int *arr, int n, int p) {
if (p <= 0 || p >= n) {
return T_ERROR;
}
int pArr[p];
for (int i = 0; i < p; i++) {
pArr[i] = arr[i];
}
for (int i = 0; i < n - p; i++) {
arr[i] = arr[p+i];
}
for (int i = 0; i < p; i++) {
arr[n-p+i] = pArr[i];
}
return T_OK;
}
第二种方式：
// 逆序数组
void InverseArray(int *arr, int left, int right) {
if (left > right) {
return;
}
int i = left;
int j = right;
int temp;
while (i < j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i += 1;
j -= 1;
}
}
TStatus LeftShiftArray2(int *arr, int n, int p) {
if (p <= 0 || p >= n) {
return T_ERROR;
}
InverseArray(arr, 0, n-1);
InverseArray(arr, 0, n-p-1);
InverseArray(arr, n-p, n-1);
return T_OK;
}
- 已知一个整数序列
A = (a0,a1,a2,...an-1)，其中(0 <= ai <= n)，(0 <= i<= n)。若存在ap1 = ap2 = ...= apm = x，且m > n/2(0 <= pk < n，1 <= k <= m),则称x为A的主元素。例如，A = (0,5,5,3,5,7,5,5)，则5是主元素；若B = (0,5,5,3,5,1,5,7)，则B中没有主元素，假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出数组元素中的主元素，若存在主元素则输出该元素，否则输出-1。
这道题最核心的问题就是找到数组中出现次数最多的元素。只要找到次数出现最多的元素，然后再来判断该元素出现的次数是否满足m > n/2即可。
思路1：作为一名iOS开发人员，看到这道题的第一想法是使用swift的字典处理，遍历数组，将数作为key，出现的次数作为value，遍历完成之后，取出字典中最大的value，比较value和数组长度的大小，如果符合主元素，则取出value对应的key。然而，C语言并没有字典的说法，除非自己实现这样的结构。换个思路，可以使用一个数组来存储，将数值的大小作为下标，对应的数组元素的值为出现的次数。但是这样实现的问题是会浪费大量的内存空间。
// mEle 找到的主元素 TStatus为1则是找到，为-1则找不到
TStatus GetMainElement1(int *arr, int len, int *mEle) {
// 申请空间为len的辅助空间
int *a = alloca(sizeof(int)*len);
for (int k = 0; k < len; k++) {
*(a+k) = 0;
}
int x;
for (int i = 0; i < len; i++) {
x = arr[i];
a[x] += 1;
}
PrintArray(a, len);
int count = 0, m = 0; // count 是次数
for (int j = 0; j < len; j++) {
if (count < a[j]) {
count = a[j];
m = j;
}
}
if (count > len/2) {
*mEle = m;
return T_OK;
}
return T_ERROR;
}
思路2：如果存在多个出现的次数一样多(都是最多)的元素，则不存在主元素，可以直接返回-1。使用一个变量m假设为出现次数最多的元素，count为其出现的次数，遍历数组，遇到的数如果和m相等则count加1，否则count减1，当减至为0的时候，就m改为下一个遍历的值。遍历完成之后，如果count等于0则说明存在多个出现次数都是最多的元素，直接返回-1。如果count大于0，m就是出现次数最多的元素。重新遍历数组，获取到m出现的真实次数，再来确定m是否是主元素。
TStatus GetMainElement2(int *arr, int len, int *mEle) {
int m = arr[0];
int count = 1;
for (int i = 0; i < len; i++) {
if (m == arr[i]) {
count += 1;
} else {
if (count > 0) {
count -= 1;
} else {
m = arr[i];
count = 1;
}
}
}
if (count > 0) {
count = 0;
for (int j = 0; j < len; j++) {
if (arr[j] == m) {
count += 1;
}
}
if (count > len/2) {
*mEle = m;
return T_OK;
}
}
return T_ERROR;
}
- 用单链表保存
m个整数，结点的结构为(data,link)，且|data|<=n(n为正整数)。现在要去设计一个时间复杂度尽可能高效的算法，对于链表中的data绝对值相等的结点，仅保留第一次出现的结点，而删除其余绝对值相等的结点。例如，链表A = {21,-15,15,-7,15}，删除后的链表A={21,-15,-7}。
此题和第6题的第一种解法思路比较类似。
TStatus DeleteAbsoluteValueNode(linkList *ll, int n) {
if (*ll == NULL) {
return T_ERROR;
}
// 使用链表结点data的绝对值作为数组的下标
// 如果该下标对应的值为0，则说明没有使用该节点，如果为1则说明使用过该结点，直接将其释放
// 申请空间为len的辅助空间
int *a = alloca(sizeof(int)*n);
for (int k = 0; k < n; k++) {
*(a+k) = 0;
}
linkList p = (*ll)->next;
linkList temp = *ll;
while (p) {
if (a[abs(p->data)] == 0) {
// 没使用过该结点 则使用
a[abs(p->data)] = 1;
// temp记录上一次循环的时候尾结点的位置
temp = p;
p = p->next;
} else {
// 当前结点丢弃 将链表的尾结点指向下一个结点
temp->next = p->next;
free(p);
p = temp->next;
}
}
return T_OK;
}
