数据结构与算法——算法练习篇
2020-04-11 本文已影响0人
A慢慢懂
- 题目一
题⽬目1 :将2个递增的有序链表合并为一个链表的有序链表; 要求结果链表仍然使⽤用两个链表的存储空间,不另外占用其他的存储空间. 表中不允许有重复的数据
条件:1、两个递增的有序链表，合并成有序链表
要求：不能另外开辟的z存储空间,不能有重复空间
La = {2 4 6 8 };
Lb = {3 6 9 12 15 };
代码
Status MergeLinkList(LinkList *La,LinkList *Lb,LinkList *Lc){
//排序，并且不能有重复的数据
LinkList p,p2,target,pc;
target = NULL;
p = (*La)->next;
p2 = (*Lb)->next;
pc = *Lc = *La;
while (p && p2) {
if (p->data<p2->data) {
pc ->next = p;
pc = p;
p = p->next;
}else if(p->data>p2->data){
pc ->next = p2;
pc = p2;
p2 = p2->next;
}else{
//相等的时候
pc ->next = p;
pc = p;
p = p->next;
//删除Lb中相等的值
target = p2->next;
free(p2);
p2 = target;
//删除
}
}
pc->next = p?p:p2;
free(*Lb);
return OK;
}
- 题目二
已知两个链表A和B分别表示两个集合.其元素递增排列. 设计一个算法,用于求出A与B的交集,并存储在A链表中;
La = {2 4 6 8 };
Lb = {3 6 9 12 15 };
void InterseLinkList(LinkList *La,LinkList *Lb,LinkList *Lc){
LinkList pa,pb,pc,temp;
pa = (*La)->next;
pb = (*Lb)->next;
pc = (*Lc)=(*La);
while (pa && pb) {
if (pa->data>pb->data) {
temp = pb->next;
free(pb);
pb = temp;
}else if(pa->data<pb->data){
temp = pa->next;
free(pa);
pa = temp;
}else{
pc->next = pa;
pc = pc->next;
pa = pa->next;
temp = pb->next;
free(pb);
pb = temp;
}
}
//pc->next = NULL;
free(*Lb);
}
- 题目三
题⽬3 :
设计⼀个算法,将链表中所有节点的链接⽅向"原地旋转",即要求仅仅利⽤原表的存储空间. 换句
话说,要求算法空间复杂度为O(1);
例如:L={2,4,6,8,10,12}, 逆转后: L = {12,10,8,6,4,2};
void RotateLinkList(LinkList *L){
LinkList p,temp ;
for (p = (*L)->next; p->next!=NULL;){
temp = p->next;
p->next = temp->next;
temp->next = (*L)->next;
(*L)->next = temp;
}
}
- 题目四
设计思路如下设计⼀个算法,删除递增有序链表中值⼤于等于mink且⼩于等于maxk(mink,maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)的所有元素
image.png
代码
void DeleteSomeNumLinkList(LinkList *L,int mink,int maxk){
LinkList p,deleteP;
p = *L;
deleteP = (*L)->next;
//当删除的结点的data小于等于最大值，循环遍历
while ( deleteP->data <= maxk) {
if ( deleteP->data<mink) {
//删除结点的值小于最小值继续遍历
deleteP = deleteP->next;
p = p->next;
}else{
//大于等于时
p->next = deleteP->next;
free(deleteP);
deleteP = p->next;
}
}
}
运行结果
题目四.png
- 题目五
设将n(n>1)个整数存放到⼀维数组R中, 试设计⼀个在时间和空间两⽅⾯都尽可能⾼效的算法;将R
中保存的序列循环左移p个位置(0<p<n)个位置, 即将R中的数据由(x0,x1,……,xn-1)变换为
(xp,xp+1,...,xn-1,x0,x1,...,xp-1).
例如: pre[10] = {0,1,2,3,4,5,6,7,8,9}, n = 10,p = 3; pre[10] = {3,4,5,6,7,8,9,0,1,2}
设计思路：先把整个数组逆序，变成pre[10] = {9,8,7,6,5,4,3,2,1,0},然后把前面七个逆序变成pre[10] = {3,4,5,6,7,8,9,2,1,0},然后再把后面七个逆序
pre[10] = {3,4,5,6,7,8,9,0,1,2},
时间复杂度: O(n); 时间复杂度:O(1);
void ReverseOrder(int *a,int left,int right){
int i = left,j = right;
int temp;
while (i<j) {
//交换
temp = a[i];
a[i] = a[j];
a[j] = temp;
//i右移,j左移
i++;
j--;
}
}
void moveList(int *a,int n,int p){
for (int i = 0; i < n; i++) {
a[i] = i;
}
ReverseOrder(a,0, n-1);
ReverseOrder(a, 0, n-p-1);
ReverseOrder(a, n-p, n-1);
}
- 题目六
已知一个整数序列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),则A 中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.
设计思路：1、先遍历数组，找到主元素
2、遍历数组，记录主元素出现的次数
3、判断主元素的次数。
Status mainElem(int *pre,ElemType *e,int n){
//1.先循环遍历找到主元素
int elem;
int count = 1;
elem = pre[0];
for (int i = 1; i< n; i++) {
if (pre[i] ==elem) {
count ++;
}else{
if (count >0) {
count --;
}else{
elem = pre[i];
count = 1;
}
}
}
if (count <= 0) {
return -1;
}
count = 0;
for (int i = 0; i< n; i++) {
if (pre[i] == elem) {
count++;
}
}
if (count<n/2) {
return -1;
}else{
return elem;
}
}
- 题目七
用单链表保存m个整数, 结点的结构为(data,link),且|data|<=n(n为正整数). 现在要去设计一个时间复杂度尽可能高效的算法. 对于链表中的data 绝对值相等的结点, 仅保留第一次出现的结点,而删除其余绝对值相等的结点.例如,链表A = {21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};
题目分析:
要求设计一个时间复杂度尽量高效的算法,而已知|data|<=n, 所以可以考虑用空间换时间的方法. 申请一个空间大小为n+1(0号单元不使用)的辅助数组. 保存链表中已出现的数值,通过对链表进行一趟扫描来完成删除.
算法思路:
- 申请大小为n+1的辅助数组t并赋值初值为0;
- 从首元结点开始遍历链表,依次检查t[|data|]的值, 若[|data|]为0,即结点首次出现,则保留该结点,并置t[|data|] = 1,若t[|data|]不为0,则将该结点从链表中删除.
复杂度分析:
时间复杂度: O(m),对长度为m的链表进行一趟遍历,则算法时间复杂度为O(m);
空间复杂度: O(n)
代码：
void DeleteEqualNode(LinkList *L,int n){
//目标: 删除单链表中绝对值相等的结点;
//1. 开辟辅助数组p.
int *p = alloca(sizeof(int)*n);
LinkList r = *L;
//2.数组元素初始值置空
for (int i = 0; i < n; i++) {
*(p+i) = 0;
}
//3.指针temp 指向首元结点
LinkList temp = (*L)->next;
//4.遍历链表,直到temp = NULL;
while (temp!= NULL) {
//5.如果该绝对值已经在结点上出现过,则删除该结点
if (p[abs(temp->data)] == 1) {
//临时指针指向temp->next
r->next = temp->next;
//删除temp指向的结点
free(temp);
//temp 指向删除结点下一个结点
temp = r->next;
}else
{
//6. 未出现过的结点,则将数组中对应位置置为1;
p[abs(temp->data)] = 1;
r = temp;
//继续向后遍历结点
temp = temp->next;
}
}
}
完整代码
//
// main.c
// 算法练习篇
//
// Created by mac on 2020/4/8.
// Copyright © 2020 mac. All rights reserved.
//
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
//1.单向链表的初始化
Status InitLinkList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));
if (!(*L)) {
return ERROR;
}
(*L)->next = NULL;
return OK;
}
//2.单向链表的插入
Status InsertLinkList(LinkList *L,int place,int e){
LinkList p,temp;
int i = 1;
for (p = (*L),i = 1; p->next!=NULL && i < place; p = p->next);
temp = (LinkList)malloc(sizeof(Node));
temp->data = e;
temp->next = p->next;
p->next = temp;
return OK;
}
Status show (LinkList L){
LinkList p;
p = L->next;
do {
printf("%d ",p->data);
p = p->next;
} while (p);
printf("\n");
return OK;
}
/*题⽬目1 :将2个递增的有序链表合并为一个链表的有序链表; 要求结果链表仍然使⽤用两个链表的存储空间,不另外占用其他的存储空间. 表中不允许有重复的数据
条件:1、两个递增的有序链表，合并成有序链表
要求：不能另外开辟的z存储空间,不能有重复空间
La = {2 4 6 8 };
Lb = {3 6 9 12 15 };
*/
Status MergeLinkList(LinkList *La,LinkList *Lb,LinkList *Lc){
//排序，并且不能有重复的数据
LinkList p,p2,target,pc;
target = NULL;
p = (*La)->next;
p2 = (*Lb)->next;
pc = *Lc = *La;
while (p && p2) {
if (p->data<p2->data) {
pc ->next = p;
pc = p;
p = p->next;
}else if(p->data>p2->data){
pc ->next = p2;
pc = p2;
p2 = p2->next;
}else{
//相等的时候
pc ->next = p;
pc = p;
p = p->next;
//删除Lb中相等的值
target = p2->next;
free(p2);
p2 = target;
//删除
}
}
pc->next = p?p:p2;
free(*Lb);
return OK;
}
/*
作业2:
题目:
已知两个链表A和B分别表示两个集合.其元素递增排列. 设计一个算法,用于求出A与B的交集,并存储在A链表中;
La = {2 4 6 8 };
Lb = {3 6 9 12 15 };
*/
void InterseLinkList(LinkList *La,LinkList *Lb,LinkList *Lc){
LinkList pa,pb,pc,temp;
pa = (*La)->next;
pb = (*Lb)->next;
pc = (*Lc)=(*La);
while (pa && pb) {
if (pa->data>pb->data) {
temp = pb->next;
free(pb);
pb = temp;
}else if(pa->data<pb->data){
temp = pa->next;
free(pa);
pa = temp;
}else{
pc->next = pa;
pc = pc->next;
pa = pa->next;
temp = pb->next;
free(pb);
pb = temp;
}
}
//pc->next = NULL;
free(*Lb);
}
/*
题⽬3 :
设计⼀个算法,将链表中所有节点的链接⽅向"原地旋转",即要求仅仅利⽤原表的存储空间. 换句
话说,要求算法空间复杂度为O(1);
例如:L={2,4,6,8,10,12}, 逆转后: L = {12,10,8,6,4,2};
*/
void RotateLinkList(LinkList *L){
LinkList p,temp ;
for (p = (*L)->next; p->next!=NULL;){
temp = p->next;
p->next = temp->next;
temp->next = (*L)->next;
(*L)->next = temp;
}
}
/*
题⽬4 :
设计⼀个算法,删除递增有序链表中值⼤于等于mink且⼩于等于maxk(mink,maxk是给定的两个参
数,其值可以和表中的元素相同,也可以不同)的所有元素
*/
void DeleteSomeNumLinkList(LinkList *L,int mink,int maxk){
LinkList p,deleteP;
p = *L;
deleteP = (*L)->next;
//当删除的结点的data小于等于最大值，循环遍历删除
while ( deleteP->data <= maxk) {
if ( deleteP->data<mink) {
//删除结点的值小于最小值继续遍历
deleteP = deleteP->next;
p = p->next;
}else{
//大于等于时
p->next = deleteP->next;
free(deleteP);
deleteP = p->next;
}
}
}
/*题目五
设将n(n>1)个整数存放到⼀维数组R中, 试设计⼀个在时间和空间两⽅⾯都尽可能⾼效的算法;将R
中保存的序列循环左移p个位置(0<p<n)个位置, 即将R中的数据由(x0,x1,……,xn-1)变换为
(xp,xp+1,...,xn-1,x0,x1,...,xp-1).
例如: pre[10] = {0,1,2,3,4,5,6,7,8,9}, n = 10,p = 3; pre[10] = {3,4,5,6,7,8,9,0,1,2}
*/
void ReverseOrder(int *a,int left,int right){
int i = left,j = right;
int temp;
while (i<j) {
//交换
temp = a[i];
a[i] = a[j];
a[j] = temp;
//i右移,j左移
i++;
j--;
}
}
void moveList(int *a,int n,int p){
for (int i = 0; i < n; i++) {
a[i] = i;
}
ReverseOrder(a,0, n-1);
ReverseOrder(a, 0, n-p-1);
ReverseOrder(a, n-p, n-1);
}
/*
已知一个整数序列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),则A 中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.
*/
Status mainElem(int *pre,ElemType *e,int n){
//1.先循环遍历找到主元素
int elem;
int count = 1;
elem = pre[0];
for (int i = 1; i< n; i++) {
if (pre[i] ==elem) {
count ++;
}else{
if (count >0) {
count --;
}else{
elem = pre[i];
count = 1;
}
}
}
if (count <= 0) {
return -1;
}
count = 0;
for (int i = 0; i< n; i++) {
if (pre[i] == elem) {
count++;
}
}
if (count<n/2) {
return -1;
}else{
return elem;
}
}
void DeleteEqualNode(LinkList *L,int n){
//删除链表中绝对值相等的结点
//1.开辟辅助空间
int *p = alloca(sizeof(int)*n);
LinkList r = *L;
//将数组元素置空
for (int i = 0; i < n; i++) {
*(p+1) = 0;
}
LinkList temp = (*L)->next;
while (temp!=NULL) {
if (p[abs(temp->data)] == 1) {
r->next = temp->next;
free(temp);
temp = r->next;
}else{
p[abs(temp->data)] = 1;
r = temp;
temp = temp->next;
}
}
}
int main(int argc, const char * argv[]) {
// insert code here...
//printf("Hello, World!\n");
LinkList L,L2,L3;
printf("创建L是否成功-------%d\n",InitLinkList(&L));
printf("创建L2是否成功-------%d\n",InitLinkList(&L2));
printf("L------\n");
// for (int i = 1; i < 7; i++) {
// InsertLinkList(&L, i, 2*i);
// }
// show(L);
// printf("L2------\n");
// for (int i = 1; i< 6; i++) {
// InsertLinkList(&L2, i, 3*i);
// }
// show(L2);
// MergeLinkList(&L,&L2, &L3);
// show(L3);
// printf("交集-----------\n");
// InterseLinkList(&L, &L2, &L3);
// show(L3);
//题目三---------旋转
// printf("旋转-----------\n");
// RotateLinkList(&L);
// show(L);
//题目4⃣️，删除其中元素
// printf("L中删除3-10的值\n");
// DeleteSomeNumLinkList(&L, 3, 10);
// show(L);
// printf("题目五-----------\n");
// int n = 10;
// int* a= malloc(sizeof(n));
// int p = 3;
// moveList(a, n, p);
// for (int i =0; i<n; i++) {
// printf("%d ",a[i]);
// }
// printf("\n");
// printf("题目六-----------\n");
// ElemType *e = NULL,*e2 = NULL;
// int a[] = {0,5,5,3,5,7,5,5};
// int b[] = {0,5,5,3,5,1,5,7};
// int c[] = {0,5,5,3,5,1,8,7};
// printf("数组A是否有主元素(-1代表无主元素)%d\n",mainElem(a, e, 8));
// printf("数组B是否有主元素(-1代表无主元素)%d\n",mainElem(b, e2, 8));
// printf("数组B是否有主元素(-1代表无主元素)%d\n",mainElem(c, e2, 8));
printf("题目7-----------\n");
InsertLinkList(&L, 1, 21);
InsertLinkList(&L, 1, -15);
InsertLinkList(&L, 1, 8);
InsertLinkList(&L, 1, -8);
InsertLinkList(&L, 1, 15);
InsertLinkList(&L, 1, 18);
InsertLinkList(&L, 1, -7);
show(L);
printf("删除绝对值后------------\n");
DeleteEqualNode(&L, 21);
show(L);
return 0;
}
