目录
2.25假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合(即同一表中的元素值各不相同),现要求另辟空间构成一个线性表C,其元素为A和B中元素的交集,且表C中的元素也依值递增有序排列。试对顺序表编写求C的算法。
2.26要求同2.25题。是对单链表编写求C的算法
2.27 对2.25题的条件作以下两点修改,对顺序表重新编写求得表C的算法(1)假设在同一表(A或B)中可能存在值相同的元素,但要求新生成的表C中的元素值各不相同;(2)利用A表空间存放表C。
2.28 对2.25题的条件作以下两点修改,对单链表重新编写求得表C的算法(1)假设在同一表(A或B)中可能存在值相同的元素,但要求新生成的表C中的元素值各不相同;(2)利用A表空间存放表C。
2.29 已知A,B和C为三个递增有序的线性表,现要求对A表作如下操作:删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法,并分析你的算法的时间复杂度(注意:题中没有特别指明同一表中的元素值各不相同)。
2.30 要求同2.29题.试对单链表编写算法,请释放A表中的无用结点空间。
2.25假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合(即同一表中的元素值各不相同),现要求另辟空间构成一个线性表C,其元素为A和B中元素的交集,且表C中的元素也依值递增有序排列。试对顺序表编写求C的算法。
本题代码如下
sqlist jiaoji(sqlist* a, sqlist* b)
{sqlist c; // 定义一个结构体变量,用于存储交集结果c.length = 0; // 初始化交集长度为0int i = 0; // 定义一个整型变量,用于遍历顺序表aint j = 0; // 定义一个整型变量,用于遍历顺序表bint k = 0; // 定义一个整型变量,用于记录交集元素在结果中的位置while (i < a->length && j < b->length) // 当两个顺序表都没有遍历完时,进行循环{if (a->s[i] == b->s[j]) // 如果顺序表a和b当前位置的元素相等{c.s[k++] = a->s[i++]; // 将该元素添加到交集结果中,并将交集长度加1j++; // 顺序表b的指针向后移动一位}else if (a->s[i] < b->s[j]) // 如果顺序表a当前位置的元素小于顺序表b当前位置的元素{i++; // 顺序表a的指针向后移动一位}else // 如果顺序表a当前位置的元素大于顺序表b当前位置的元素{j++; // 顺序表b的指针向后移动一位}}c.length = k; // 更新交集长度return c; // 返回交集结果
}
完整测试代码如下
#include<stdio.h>
#define Max 10
typedef struct sqlist
{int s[Max]; // 定义一个结构体数组,用于存储顺序表的元素int length; // 定义一个整型变量,用于存储顺序表的长度
}sqlist;
// 定义一个函数,用于求两个顺序表的交集
sqlist jiaoji(sqlist* a, sqlist* b)
{sqlist c; // 定义一个结构体变量,用于存储交集结果c.length = 0; // 初始化交集长度为0int i = 0; // 定义一个整型变量,用于遍历顺序表aint j = 0; // 定义一个整型变量,用于遍历顺序表bint k = 0; // 定义一个整型变量,用于记录交集元素在结果中的位置while (i < a->length && j < b->length) // 当两个顺序表都没有遍历完时,进行循环{if (a->s[i] == b->s[j]) // 如果顺序表a和b当前位置的元素相等{c.s[k++] = a->s[i++]; // 将该元素添加到交集结果中,并将交集长度加1j++; // 顺序表b的指针向后移动一位}else if (a->s[i] < b->s[j]) // 如果顺序表a当前位置的元素小于顺序表b当前位置的元素{i++; // 顺序表a的指针向后移动一位}else // 如果顺序表a当前位置的元素大于顺序表b当前位置的元素{j++; // 顺序表b的指针向后移动一位}}c.length = k; // 更新交集长度return c; // 返回交集结果
}
int main()
{sqlist a, b; // 定义两个顺序表变量a和bint i = 0; // 定义一个整型变量,用于遍历顺序表a和ba.length = 5; // 设置顺序表a的长度为5b.length = 5; // 设置顺序表b的长度为5printf("请输入A顺序表的元素:"); // 提示用户输入顺序表a的元素for (i = 0; i < a.length; i++) // 遍历顺序表ascanf("%d", &a.s[i]); // 读取用户输入的元素并存储到顺序表a中printf("请输入B顺序表的元素:"); // 提示用户输入顺序表b的元素for (i = 0; i < b.length; i++) // 遍历顺序表bscanf("%d", &b.s[i]); // 读取用户输入的元素并存储到顺序表b中sqlist c = jiaoji(&a, &b); // 调用函数求两个顺序表的交集,并将结果存储到变量c中printf("C顺序表中的元素:"); // 提示用户输出交集结果for (i = 0; i < c.length; i++) // 遍历交集结果printf("%d ", c.s[i]); // 输出交集结果中的每个元素return 0; // 程序正常结束,返回0
}
测试结果如下
2.26要求同2.25题。是对单链表编写求C的算法
本题代码如下
linklist jiaoji(linklist* A, linklist* B)
{lnode* C = (lnode*)malloc(sizeof(lnode));C->next = NULL;lnode* ra = (*A)->next, * rb = (*B)->next;lnode* rc = C, * r;while (ra && rb){if (ra->data == rb->data){r = ra;ra = ra->next;rb = rb->next;rc->next = r;r->next = NULL;rc = r;}else if (ra->data < rb->data){ra = ra->next;}else{rb = rb->next;}}return C;
}
完整测试代码如下
#include<stdio.h>
#include<stdlib.h>
typedef struct lnode
{int data;struct lnode* next;
}lnode, * linklist;
int a[5] = { 1,2,3,4,5 };
int b[5] = { 3,4,5,6,7 };
int n = 5;
void buildlinklist(linklist* L, int str[])
{*L = (lnode*)malloc(sizeof(lnode));(*L)->next = NULL;int i = 0;lnode* s, * r = *L;for (i = 0; i < n; i++){s = (lnode*)malloc(sizeof(lnode));s->data = str[i];s->next = r->next;r->next = s;r = s;}r->next = NULL;
}
linklist jiaoji(linklist* A, linklist* B)
{lnode* C = (lnode*)malloc(sizeof(lnode));C->next = NULL;lnode* ra = (*A)->next, * rb = (*B)->next;lnode* rc = C, * r;while (ra && rb){if (ra->data == rb->data){r = ra;ra = ra->next;rb = rb->next;rc->next = r;r->next = NULL;rc = r;}else if (ra->data < rb->data){ra = ra->next;}else{rb = rb->next;}}return C;
}
void print(linklist* L)
{lnode* k = (*L)->next;while (k){printf("%d ", k->data);k = k->next;}
}
int main()
{linklist A, B;buildlinklist(&A, a);printf("A单链表元素为:");print(&A);buildlinklist(&B, b);printf("\nB单链表元素为:");print(&B);linklist C = jiaoji(&A, &B);printf("\nC单链表元素为:");print(&C);return 0;
}
测试结果如下
2.27 对2.25题的条件作以下两点修改,对顺序表重新编写求得表C的算法
(1)假设在同一表(A或B)中可能存在值相同的元素,但要求新生成的表C中的元素值各不相同;
(2)利用A表空间存放表C。
本题代码如下
sqlist jiaoji(sqlist* a, sqlist* b)
{int i = 0; // 定义一个整型变量,用于遍历顺序表aint j = 0; // 定义一个整型变量,用于遍历顺序表bint k = 0; // 定义一个整型变量,用于记录交集元素在结果中的位置int c[Max];for (i = 0; i < a->length; i++)c[i] = a->s[i];i = 0;while (i < a->length && j < b->length) // 当两个顺序表都没有遍历完时,进行循环{if (c[i] == b->s[j]) // 如果顺序表a和b当前位置的元素相等{a->s[k++] = c[i++]; // 将该元素添加到交集结果中,并将交集长度加1j++; // 顺序表b的指针向后移动一位}else if (c[i] < b->s[j]) // 如果顺序表a当前位置的元素小于顺序表b当前位置的元素{i++; // 顺序表a的指针向后移动一位}else // 如果顺序表a当前位置的元素大于顺序表b当前位置的元素{j++; // 顺序表b的指针向后移动一位}}a->length = k;return *a; // 返回交集结果
}
完整测试代码如下
#include<stdio.h>
#define Max 10
typedef struct sqlist
{int s[Max]; // 定义一个结构体数组,用于存储顺序表的元素int length; // 定义一个整型变量,用于存储顺序表的长度
}sqlist;
// 定义一个函数,用于求两个顺序表的交集
sqlist jiaoji(sqlist* a, sqlist* b)
{int i = 0; // 定义一个整型变量,用于遍历顺序表aint j = 0; // 定义一个整型变量,用于遍历顺序表bint k = 0; // 定义一个整型变量,用于记录交集元素在结果中的位置int c[Max];for (i = 0; i < a->length; i++)c[i] = a->s[i];i = 0;while (i < a->length && j < b->length) // 当两个顺序表都没有遍历完时,进行循环{if (c[i] == b->s[j]) // 如果顺序表a和b当前位置的元素相等{a->s[k++] = c[i++]; // 将该元素添加到交集结果中,并将交集长度加1j++; // 顺序表b的指针向后移动一位}else if (c[i] < b->s[j]) // 如果顺序表a当前位置的元素小于顺序表b当前位置的元素{i++; // 顺序表a的指针向后移动一位}else // 如果顺序表a当前位置的元素大于顺序表b当前位置的元素{j++; // 顺序表b的指针向后移动一位}}a->length = k;return *a; // 返回交集结果
}
int main()
{sqlist a, b; // 定义两个顺序表变量a和bint i = 0; // 定义一个整型变量,用于遍历顺序表a和ba.length = 5; // 设置顺序表a的长度为5b.length = 5; // 设置顺序表b的长度为5printf("请输入A顺序表的元素:"); // 提示用户输入顺序表a的元素for (i = 0; i < a.length; i++) // 遍历顺序表ascanf("%d", &a.s[i]); // 读取用户输入的元素并存储到顺序表a中printf("请输入B顺序表的元素:"); // 提示用户输入顺序表b的元素for (i = 0; i < b.length; i++) // 遍历顺序表bscanf("%d", &b.s[i]); // 读取用户输入的元素并存储到顺序表b中sqlist c = jiaoji(&a, &b); // 调用函数求两个顺序表的交集,并将结果存储到变量c中printf("交集存于A顺序表中的元素:"); // 提示用户输出交集结果for (i = 0; i < c.length; i++) // 遍历交集结果printf("%d ", c.s[i]); // 输出交集结果中的每个元素return 0; // 程序正常结束,返回0
}
测试结果为
2.28 对2.25题的条件作以下两点修改,对单链表重新编写求得表C的算法
(1)假设在同一表(A或B)中可能存在值相同的元素,但要求新生成的表C中的元素值各不相同;
(2)利用A表空间存放表C。
本题代码如下
linklist Union(linklist* A, linklist* B)
{lnode* ra = (*A)->next, * rb = (*B)->next;(*A)->next = NULL;lnode* r = *A;while (ra && rb){if (ra->data<rb->data)//若A中当前结点小于B中当前结点值{r->next = ra;r = ra;ra = ra->next;r->next = NULL;}else if (ra->data>rb->data)//若A中当前结点大于B中当前结点值{r->next = rb;r = rb;rb = rb->next;r->next = NULL;}else{r->next = ra;r = ra;ra = ra->next;rb= rb->next;r->next = NULL;}}r->next = NULL; //结果表的表尾结点置空return *A;
}
完整测试代码如下
#include<stdio.h>
#include<stdlib.h>
typedef struct lnode
{int data;struct lnode* next;
}lnode, * linklist;
int na = 5;
int nb = 5;
int a[5] = { 1,3,5,7,9};
int b[5] = {1,2,3,4,5};
void buildlinklist(linklist* L, int arr[], int n)//创建链表
{*L = (lnode*)malloc(sizeof(lnode));(*L)->next = NULL;lnode* s = *L, * r = *L;int i = 0;for (i = 0; i < n; i++){s = (lnode*)malloc(sizeof(lnode));s->data = arr[i];s->next = r->next;r->next = s;r = s;}r->next = NULL;
}
linklist Union(linklist* A, linklist* B)
{lnode* ra = (*A)->next, * rb = (*B)->next;(*A)->next = NULL;lnode* r = *A;while (ra && rb){if (ra->data<rb->data)//若A中当前结点小于B中当前结点值{r->next = ra;r = ra;ra = ra->next;r->next = NULL;}else if (ra->data>rb->data)//若A中当前结点大于B中当前结点值{r->next = rb;r = rb;rb = rb->next;r->next = NULL;}else{r->next = ra;r = ra;ra = ra->next;rb= rb->next;r->next = NULL;}}r->next = NULL; //结果表的表尾结点置空return *A;
}
void print(linklist* L)//输出单链表
{lnode* k = (*L)->next;while (k){printf("%d ", k->data);k = k->next;}
}
int main()
{linklist A, B;buildlinklist(&A, a, na);buildlinklist(&B, b, nb);printf("A链表为:");print(&A);printf("\nB链表为:");print(&B);linklist C = Union(&A, &B);printf("\n两个表元素交集的链表为:");print(&C);return 0;
}
2.29 已知A,B和C为三个递增有序的线性表,现要求对A表作如下操作:删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法,并分析你的算法的时间复杂度(注意:题中没有特别指明同一表中的元素值各不相同)。
本题代码如下
void delete_common_elements(int A[], int B[], int C[], int* lenA, int* lenB, int* lenC)
{int i = 0, j = 0, k = 0;while (i < *lenA && j < *lenB && k < *lenC) {if (A[i] == B[j] && A[i] == C[k]){for (int m = i; m < *lenA - 1; m++) {A[m] = A[m + 1];}(*lenA)--;}else if (A[i] < B[j]) {j++;}else if (A[i] < C[k]){k++;}else {i++;}}
}
完整测试代码为
#include <stdio.h>
void delete_common_elements(int A[], int B[], int C[], int* lenA, int* lenB, int* lenC)
{int i = 0, j = 0, k = 0;while (i < *lenA && j < *lenB && k < *lenC) {if (A[i] == B[j] && A[i] == C[k]){for (int m = i; m < *lenA - 1; m++) {A[m] = A[m + 1];}(*lenA)--;}else if (A[i] < B[j]) {j++;}else if (A[i] < C[k]){k++;}else {i++;}}
}
int main() {int A[] = { 1, 2, 3, 4, 5 };int B[] = { 2, 3, 4,5,6 };int C[] = { 3, 4, 5,6,7 };int lenA = sizeof(A) / sizeof(A[0]);int lenB = sizeof(B) / sizeof(B[0]);int lenC = sizeof(C) / sizeof(C[0]);delete_common_elements(A, B, C, &lenA, &lenB, &lenC);for (int i = 0; i < lenA; i++) {printf("%d ", A[i]);}return 0;
}
测试结果为
2.30 要求同2.29题.试对单链表编写算法,请释放A表中的无用结点空间。
本题代码如下
void deleterepeat(linklist* A, linklist* B, linklist* C)
{lnode* ra = (*A)->next, *rb = (*B)->next, * rc = (*C)->next;lnode* r = *A,*q;while (ra&&rb&&rc){if (ra->data == rb->data && ra->data == rc->data){q = ra;r->next = ra->next;ra = ra->next;rb = rb->next;rc = rc->next;free(q);}else if(rb->data<ra->data){rb = rb->next;}else if (rc->data < ra->data){rc = rc->next;}else{r = ra;ra = ra->next;}}
}
完整测试代码如下
#include<stdio.h>
#include<stdlib.h>
typedef struct lnode
{int data;struct lnode* next;
}lnode,*linklist;
int a[5] = { 2,3,4,5,6 };
int b[5] = { 3,4,5,6,7 };
int c[5] = { 1,2,3,4,5 };
int n = 5;
void buildlinklist(linklist* L,int str[])
{*L = (lnode*)malloc(sizeof(lnode));(*L)->next = NULL;lnode* s, * r = *L;int i = 0;for (i = 0; i < n; i++){s = (lnode*)malloc(sizeof(lnode));s->data = str[i];s->next = r->next;r->next = s;r = s;}r->next = NULL;
}
void deleterepeat(linklist* A, linklist* B, linklist* C)
{lnode* ra = (*A)->next, *rb = (*B)->next, * rc = (*C)->next;lnode* r = *A,*q;while (ra&&rb&&rc){if (ra->data == rb->data && ra->data == rc->data){q = ra;r->next = ra->next;ra = ra->next;rb = rb->next;rc = rc->next;free(q);}else if(rb->data<ra->data){rb = rb->next;}else if (rc->data < ra->data){rc = rc->next;}else{r = ra;ra = ra->next;}}
}
void print(linklist* L)
{lnode* k = (*L)->next;while (k){printf("%d ", k->data);k = k->next;}
}
int main()
{linklist A, B, C;buildlinklist(&A, a);buildlinklist(&B, b);buildlinklist(&C, c);deleterepeat(&A, &B, &C);printf("删除之后的A单链表中的元素为:");print(&A);return 0;
}
测试结果为