数据结构~06.关于线性表的两个案例

青旅半醒 2023-03-01 10:09 9阅读 0赞

# 数据结构~06.关于线性表的两个案例 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

### 案例1: ###

#####        设顺序表用数组arr\[ \]表示,表中元素存储在数组下标0~m+n-1的范围内,前 m 个元素和后 n 个元素都递增有序,设计一个算法,使整个顺序表有序。 #####

关于这道题,我们先假设元素是int类型。将数组 arr 中的 m + n 个元素看成是两个顺序表：表 L 和 表 R。 将数组当前状态看作是起始状态。此时此刻,表 L 由 arr\[ \] 前 m 个元素构成，表 R 由 arr\[ \] 后 n 个元素构成。要使 arr\[ \] 中 m + n 个元素整体有序。只需将表 R 中的元素逐个插入到表 L 中合适的位置即可。

#include<stdio.h>
    void InsertElem(int arr[],int m,int n) { 
    	int i, j, temp;
    	//将 arr[m , ... , m + n - 1] 插入到 arr[0, ... ,m - 1] 中
    	for (i = m; i < m + n; ++i) { 
    		temp = arr[i];
    		for (j = i - 1; j >= 0 && temp < arr[j]; --j) { 
    			arr[j + i] = arr[j];	//元素后移以便腾出一个位置插入temp
    		}
    		arr[j + 1] = temp;	//插入temp,由于for循环后 j 多前移了一位，因此在 j + 1 处插入
    	}
    }
    int main(int argc, char* argv[]) { 
    	int arr[7] = {  1,3,5,2,4,6,8 };
    	InsertElem(arr, 2,4);
    	for (int i = 0; i < 7; i++) { 
    		printf("%d\t", arr[i]);
    	}
    }

##### 算法的时间和空间复杂度 #####

本题的规模由 m 和 n 共同决定。 取最内层循环中 arr \[ j + 1 \] = arr \[ j \] 。执行次数在最坏的情况下为R中的每个元素为L中的所有元素。又因 R 中元素递增有序，所以对于每个 R 中的元素，要将其插入正确位置都必须进行 m 次移动, R 中共有 n 个元素, 因此 f ( m , n ) = mn。因此,算法复杂度为 O( m n )

### 做下题之前,我们可以先写一段单链表的新增和遍历作为题目素材~ ###

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    typedef struct no_de { 
    	int data;					//数据域
    	struct no_de* next;			//指针域
    }Node;
    Node* getHead() { 
    	Node* head = (Node*)malloc(sizeof(Node));
    	head->data = NULL;
    	head->next = NULL;
    	return head;
    }
    //插入
    void Insert(Node*list,int data) { 
    	Node* temp = (Node*)malloc(sizeof(Node));
    	temp->data = data;
    	temp->next = list->next;
    	list->next = temp;
    }
    //遍历
    void Print(Node *list) { 
    	if (list -> next == NULL) { 
    		printf("[ ]");
    	}
    	Node* temp = list->next;
    	while (temp != NULL) { 
    		if (temp ->next != NULL) { 
    			printf("%d->",temp->data);
    		}
    		else { 
    			printf("%d",temp->data);
    		}
    		temp = temp->next;
    	}
    }	
    int main(int argc,char*argv[]) { 
    	Node* list = getHead();
    	for (int i = 0; i < 10; i++) { 
    		Insert(list,(rand() % 100));
    	}
    	Print(list);
    	getchar();
    }

### 案例2: ###

#####        已知递增有序的单链表 A , B 分别存储了一个集合, 请设计一个算法已求两个集合的差集 A - B ( 指的是仅在A中出现而不在B中出现的元素所构成的集合 ) 将差集保存在单链表 A 中,并保持链表的有序性 #####

关于这道题呢,我们只需要将A中删去A和B中共有的元素即可。由于两个链表中的元素都是递增有序的。因此可以这么做。设计两个指针 p , q 分别指向 A 和 B 的开始结点。循环进行判断: 如果p所指向结点的值小于q所指向结点的值,则 p 后移一位。如果 q 所指结点的值小于 p 所指的结点的值。则q后移一位。如果两者所指结点的值相同,则删除p所指的结点。最后 p 和 q 任意一个为 NULL 时算法结束

void defference(Node *A,Node *B) { 
    	// p 和 q 为辅助指针
    	Node* p = A->next, *q = B->next;
    	//pre 为 A 中 p 所指结点的前驱结点的指针
    	Node* pre = A;	
    	Node* r;
    	while (p != NULL && q != NULL) { 
    		if (p->data < q->data) { 
    			pre = p;
    			//A链表中当前结点指针后移
    			p = p->next;
    		}
    		else if (p -> data > q -> data) { 
    			//B链表中当前结点指针后移
    			q = q->next;	
    		}
    		else { 
    			//删除A , B 中元素值相同的结点
    			pre->next = p->next;	
    			r = p;
    			p = p->next;
    			//释放结点空间
    			free(r);
    		}
    	}
    }

##### 算法的时间复杂度分析 #####

本题的规模由 m 和 n 共同决定。算法中有一个单层循环。循环内的所有操作都是常数级的，因此可以用循环的次数作为基本操作的次数。考虑最坏的情况, p 和 q 都走完了自己所在的链表,循环执行 m + n 次。时间复杂度为 O( m + n )

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/107471315