mirror of
https://github.com/Maaaac/408.git
synced 2026-10-29 03:04:54 +08:00
487 lines
17 KiB
Plaintext
487 lines
17 KiB
Plaintext
//2009、含头指针的单链表，查找其链表中倒数第K个位置上的结点
|
||
typedef int ElemType; //链表数据的结构定义
|
||
typedef struct LNode{ //链表结点的结构定义
|
||
ElemType data; //结点数据
|
||
struct Lnode *link; //结点链接指针
|
||
}*LinkList;
|
||
int Search_k(LinkList list ,int k){
|
||
Linklist p = list->link , q = list->link; //指针p、q指向第一个结点
|
||
int count = 0;
|
||
while(p!= NULL){ //遍历链表直到最后一个结点
|
||
if(count < k){
|
||
count ++;
|
||
p = p->link;
|
||
}
|
||
else{
|
||
p = p->link;
|
||
q = q->link;
|
||
}
|
||
}
|
||
if (count < k){ //结点数不足K
|
||
return 0;
|
||
}
|
||
else{
|
||
cout<<q->data;
|
||
return 1;
|
||
}
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
//2010、含n个整数的一维数组R，将R中保存的序列循环左移p个位置，即将R( a0,a1,....,a(n-1) )变换为R( ap,a(p+1),....a(n-1),a0,a1,....,a(p-1) )
|
||
//思路同：将字符串分开的两个子串相互倒转
|
||
void Reverse(int R[],int from,int to){
|
||
int i,temp;
|
||
for(int i = 0; i<(to-from+1)/2;i++){
|
||
temp = R[from+i];
|
||
R[from+i] = R[to-i];
|
||
R[to-i] = temp;
|
||
}
|
||
}
|
||
void Converse(int R[],int n,int p){
|
||
Reverse(R,0,p-1);
|
||
Reverse(R,p,n-1);
|
||
Reverse(R,0,n-1);
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
//2011、对于长度为L的升序序列S，处在第L/2个位置的数成为S的中位数，求两个等长升序序列A、B的中位数
|
||
/*思路：
|
||
1、先分别求出A、B的中位数a、b
|
||
2、若a=b则a或b为所求
|
||
3、若a<b,则舍弃A中较小的一半和B中较大一半(舍弃长度相等)
|
||
4、若a>b,则舍弃A中较大一半和B中较小一半(舍弃长度相等)
|
||
5、重复1234步，直到最后都只剩一个元素，较小者为所求
|
||
*/
|
||
int M_Search(int A[],int B[],int n){
|
||
int s1=0,d1=n-1,m1,s2=1,d2=n-1,m2; //分别表示序列A和B的首位数、末位数、中位数
|
||
while(s1 != d1 || s2 != d2 ){
|
||
m1 = (s1+d1)/2;
|
||
m2 = (s2+d2)/2;
|
||
if(A[m1]==B[m2]){
|
||
return A[m1]; //满足条件a=b
|
||
}
|
||
if(A[m1]<B[m2]){ //a<b
|
||
if((s1+d1)%2==0){
|
||
s1=m1;
|
||
d2=m2;
|
||
}
|
||
else{
|
||
s1=m1+1;
|
||
d2=m2;
|
||
}
|
||
}
|
||
else{
|
||
if((s1+d1)%2==0){
|
||
d1=m1;
|
||
s2=m2;
|
||
}
|
||
else{
|
||
d1=m1;
|
||
s2=m2+1;
|
||
}
|
||
}
|
||
return A[s1]<B[S2]? A[s1]:[s2];
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2012
|
||
用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如“loading”和“being”
|
||
设str1和str2分别指向两个单词所在的单链表的头结点，找出两个链表共同后缀的起始位置
|
||
*/
|
||
/*思路：找到共同后缀的第一个结点
|
||
1、分别求出str1和str2所指两个链表的长度m、n
|
||
2、两个链表以表尾对齐：另指针p、q分别指向str1和str2的头结点，若m>=n，则使p指向链表中的第m-n+1个结点；反之则使q指向其第m-n+1个结点
|
||
3、反复将p和q同步向后移动，并判断它们是否指向同一结点。
|
||
*/
|
||
typedef char ElemType;
|
||
typedef struct LNode
|
||
{
|
||
ElemType data;
|
||
struct Lnode *link
|
||
}LinkList;
|
||
LinkNode *Find_1st_common(LinkList str1,LinkList str2){
|
||
int len1=length(str1),len2=length(str2);
|
||
LinkNode *p,*q;
|
||
for(p=str1;len1>len2;len1--){
|
||
p=p->next;
|
||
}
|
||
for(q=str2;len1<len2;len2--){
|
||
q=q->next;
|
||
}
|
||
while(p->next!=NULL&&p->next!=q->next){
|
||
p=p->next;
|
||
q=q->next;
|
||
}
|
||
return p->next;
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
//2013、整数序列A(a0,a1,...,a(n-1) ),其中0<a<n 若存在值相等的元素x且个数m>n/2，则称x为A的主元素，设计算法求A的主元素
|
||
/*思路：从前往后扫描数组元素，标记出一个可能成为主元素的元素Num，然后重新计数，确认Num是否是主元素
|
||
1、选取候选的主元素：依次扫描所给数组中的每个证书，将第一个遇到的证整数Num保存到c中，记录Num的出现次数为1；
|
||
若遇到的下一个整数仍等于Num，则计数+1，否则计数减1；
|
||
当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述，扫完全部元素
|
||
2、判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素
|
||
*/
|
||
int Majority(int A[],int n){
|
||
int i,c,count=1;
|
||
c = A[0];
|
||
for(i=1;i<n;i++){
|
||
if(A[i] ==c){
|
||
count++;
|
||
}
|
||
else if(count>0){
|
||
count--;
|
||
}
|
||
else{
|
||
c = A[i];
|
||
count = 1;
|
||
}
|
||
}
|
||
if(count>0){
|
||
for(i=count=0;i<n;i++){
|
||
if(A[i] == c){
|
||
count++;
|
||
}
|
||
}
|
||
if(count>=n/2){
|
||
return c;
|
||
}
|
||
else{
|
||
return -1;
|
||
}
|
||
}
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2014
|
||
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。
|
||
给定一棵二叉树，采用二叉链表存储，其中叶结点weight域保存该结点的非负权值，left指向其左孩子，right指向其右孩子
|
||
设root为指向T的根结点，设计求T的WPL的算法
|
||
*/
|
||
//二叉树结点的数据类型定义
|
||
typedef struct BiTNode{
|
||
int weight;
|
||
struct BiTNode *lchild,*rchild;
|
||
}BiTNode,*BiTree;
|
||
/*思路：
|
||
方法1(先序遍历递归算法)：用static变量记录WPL
|
||
1、若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积
|
||
2、若该结点非叶子结点，那么若左子树不空，对左子树调用递归算法，若右子树不空，对右子树调用递归算法，深度参数均为本结点深度参数+1
|
||
3、最后返回计算出的wpl即可
|
||
*/
|
||
int WPL(BiTree root){
|
||
int wpl_PreOrder(root,0);
|
||
}
|
||
int wpl_PreOrder(BiTree root,int deep){
|
||
static int wpl = 0; //定义一个static变量存储wpl
|
||
if(root->lchild == NULL && root->rchild == NULL){
|
||
wpl += deep * root -> weight ; //若为叶子结点，累计wpl
|
||
}
|
||
if(root->lchild != NULL){
|
||
wpl_PreOrder(root->lchid,deep+1);
|
||
}
|
||
if(root->rchild !=NULL){
|
||
wpl_PreOrder(root->rchild,deep+1);
|
||
}
|
||
return wpl;
|
||
}
|
||
|
||
/*
|
||
方法2(基于层次遍历的队列)：
|
||
1、用队列进行层次遍历，记录当前的层数，当遍历到叶子结点时，累计wpl；
|
||
2、当遍历到非叶子结点时把该结点的子树加入队列；
|
||
3、当某结点为该层的最后一个结点时，层数自增1；
|
||
4、队列空时遍历结束，返回wpl
|
||
*/
|
||
#define MaxSize 100 //设置队列的最大容量
|
||
int wpl_LevelOrder(BiTree root){
|
||
BiTree q[MaxSize]; //声明队列,end1为头指针，end2为尾指针
|
||
int end1,end2; //队列最多容纳MaxSize-1个元素
|
||
end1 = end2 =0 ; //头指针指向队头元素，尾指针指向队尾的后一个元素
|
||
int wpl = 0,deep =0; //初始化wpl和深度
|
||
BiTree lastNode; //lastNode用来记录当前层的最后一个结点
|
||
BiTree newlastNode; //newlastNode用来记录下一层的最后一个结点
|
||
lastNode = root; //lastNode初始化为根结点
|
||
newlastNode = NULL; //newlastNode初始化为空
|
||
q[end2++] = root; //根结点入队
|
||
while(end1 != end2){ //层次遍历，若队列不空则循环
|
||
BiTree t = q[end1++]; //拿出队列中的头一个元素
|
||
if(t->lchild == NULL && t->rchild == NULL){
|
||
wpl += deep*t->weight; //若为叶子结点，统计wpl
|
||
}
|
||
if(root->lchild != NULL){ //若非叶子结点把左结点入队
|
||
q[end2++] = t->lchild;
|
||
newlastNode = t->lchild;
|
||
}
|
||
if(root->rchild != NULL){
|
||
q[end2++] = t->rchild;
|
||
newlastNode = t->rchild;
|
||
}
|
||
if(t == lastNode){
|
||
lastNode = newlastNode;
|
||
deep += 1;
|
||
}
|
||
}
|
||
return wpl
|
||
}
|
||
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2015
|
||
用单链表保存m个整数，结点的结构为[data][link]，且[data]<=n
|
||
设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点
|
||
如链表：21 -> -15 -> -15 -> -7 -> 15,删除结点后为：21 -> -15 -> -7
|
||
*/
|
||
/*
|
||
思路：因|data|<=n,故辅助数组q的大小为n+1，各元素的初值均为0.
|
||
依次扫描链表中各结点，同时检查q[|data|]的值，若为0，则保留结点并令q[|data|]=1，否则将该结点删除
|
||
*/
|
||
//单链表结点的数据类型定义
|
||
typedef struct node{
|
||
int data;
|
||
struct node *link;
|
||
}NODE;
|
||
typedef NODE *PNODE
|
||
//算法实现
|
||
void func(PNODE h,int n){
|
||
PNODE p = h , r;
|
||
int *q,m;
|
||
q = (int *)malloc(sizeof(int)*(n+1)); //申请n+1个位置的辅助空间
|
||
for(int i=0;i<n+1;i++){
|
||
*(q+i) = 0;
|
||
}
|
||
while(p->link != NULL){
|
||
m = p->link->data >0 ? p->link->data:-p->link->data;
|
||
if(*(q+m) == 0){ //判断该结点的data是否已出现过
|
||
*(q+m) =1;
|
||
p = p->link;
|
||
}
|
||
else{
|
||
r = p->link;
|
||
p->link = r->link;
|
||
free(r);
|
||
}
|
||
}
|
||
free(q);
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2016
|
||
已知由n(n>=2)个正整数构成的集合A，将其划分为两个不相交的子集A1和A2，元素个数分别为n1和n2
|
||
令A1和A2中元素之和为S1和S2，设计划分算法，满足|n1-n2|最小且|S1-S2|最大
|
||
*/
|
||
/*思路：
|
||
将最小的n/2(向下取整，下同)个元素放在A1中，其余的元素放在A2中，分组结果即可满足题意
|
||
利用快速排序的思想，基于枢轴将n个整数划分为两个子集，根据划分后枢轴所处的位置i分别处理
|
||
1、若i=n/2,则分组完成，算法结束
|
||
2、若i<n/2,则枢轴及之前的所有元素均属于A1，继续对i之后的元素进行划分
|
||
3、若i>n/2,则枢轴及之后的所有元素均属于A2，继续对i之前的元素进行划分
|
||
*/
|
||
int setPartition(int a[],int n[]){
|
||
int pivotkey,low=0,low0=0,high=n-1,flag=1,k=n/2,i;
|
||
int s1=0,s2=0;
|
||
while(flag){
|
||
pivotkey=a[low];
|
||
while(low<high && a[high]>=pivotkey){
|
||
--high;
|
||
}
|
||
if(low != high){
|
||
a[low]=a[high];
|
||
}
|
||
while(low<high && a[low]<=pivotkey){
|
||
++low;
|
||
}
|
||
if(low != high){
|
||
a[high]=a[low];
|
||
}
|
||
a[low] = pivotkey;
|
||
if(low == k-1){
|
||
flag = 0;
|
||
}
|
||
else{
|
||
if(low < k-1){
|
||
low0 = ++low;
|
||
high = high0;
|
||
}
|
||
else{
|
||
high0 = --high;
|
||
low = low0;
|
||
}
|
||
}
|
||
}
|
||
for(i=o;i<k;i++){
|
||
s1+=a[i];
|
||
}
|
||
for(i=k;i<n;i++){
|
||
s2+=a[i];
|
||
}
|
||
return s2-s1;
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2017
|
||
设计算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出
|
||
如下列两棵表达树作为算法的输入时，输出的等价中缀表达式分别为(a+b)*(c*(-d))和(a*b)+(-(c-d))
|
||
* +
|
||
/ \ / \
|
||
+ * * -
|
||
/ \ / \ / \ \
|
||
a b c - a b -
|
||
\ / \
|
||
d c d
|
||
*/
|
||
/*思路：
|
||
表达树的中序序列加上必要的括号即为等价的中缀表达式
|
||
基于二叉树的中序遍历策略
|
||
*/
|
||
//二叉树结点定义：
|
||
typedef struct node{
|
||
char data[10]; //存储操作数或操作符
|
||
struct node *left,*right;
|
||
}BTree;
|
||
//算法
|
||
void BtreeToE(BTree *root){
|
||
BtreeToExp(root,1); //根的高度为1
|
||
}
|
||
void BtreeToExp(BTree *root,int deep){
|
||
if(root == NULL){return;}
|
||
else if(root->left == NULL && root->right == NULL){
|
||
printf("%s",root->data );
|
||
}
|
||
else{
|
||
if(deep>1){
|
||
printf("("); //若有子表达式则加一层括号
|
||
}
|
||
BtreeToExp(root->left,deep+1);
|
||
printf("%s",root->data );
|
||
BtreeToExp(root->right,deep+1);
|
||
if(deep>1){
|
||
printf(")"); //若由子表达式则加一层括号（此处是为了封闭次结点层的运算）
|
||
}
|
||
}
|
||
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2018
|
||
给定一个含n个整数的数组，设计一个时间上尽可能高效的算法，找出数组中未出现的最小正整数
|
||
例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4
|
||
*/
|
||
/*思路：
|
||
由于A中只有n个数，因此若最小的n个正整数全在A内的话，未出现的最小正整数则为n+1，反之，将A中n个数扫一遍后，1~n中有数没被扫到，则最小的那个为所求
|
||
分配一个用于标记的数组B[n],用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中所有值为0
|
||
从A[0]开始遍历A，若0<A[i]<=n,则令B[A[i]-1]==1,否则不做任何操作(对负数和大于n的数都不做处理)
|
||
对A遍历结束后，开始遍历数组B，找到第一个满足B[i]==0的下标，若找到，返回结果(i+1),否则返回(n+1)
|
||
*/
|
||
|
||
int findMissMin(int A[];int n){
|
||
int i,*B; //标记数组
|
||
B = (int *)malloc(sizeof(int)*n); //分配空间
|
||
memset(B,0,sizeof(int)*n); //赋值为0
|
||
for(i=0;i<n;i++){
|
||
if(A[i]>0 && A[i]<=n){
|
||
B[A[i]-1] == 1;
|
||
}
|
||
}
|
||
for(i=0;i<n;i++){
|
||
if(B[i] == 0){
|
||
break;
|
||
}
|
||
return i+1;
|
||
}
|
||
return n+1;
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2019
|
||
设线性表L=( a1,a2,a3,...,a(n-2),a(n-1),an )采用带头结点的单链表保存，链表中结点定义如下：
|
||
|
||
typedef struct node{
|
||
int data;
|
||
struct node *next;
|
||
}NODE;
|
||
|
||
设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'( a1,an,a2,a(n-1),a3,a(n-2),... )
|
||
*/
|
||
/*思路：
|
||
观察俩个线性表，发现L'是由L摘取第一个元素，再摘取倒数第一个元素······依次合并而成的
|
||
为了方便在链表后半段取元素，需要先将L后半段原地逆置，否则每取一个尾部的结点都要几乎完整遍历一遍链表
|
||
1、先找出链表L的中间结点，为此设置两个指针p和q，指针每次走一步，指针q每次走两步，当指针q到达链尾时，指针p正好在链表的中间结点
|
||
2、将L的后半段结点原地逆置
|
||
3、从单链表前后两段中依次各取一个结点，按要求重排
|
||
*/
|
||
|
||
void change_list(NODE *h){
|
||
NODE *p,*q,*r,*s;
|
||
p=q=h;
|
||
while(q->next != NULL){ //寻找中间结点
|
||
p = p->next;
|
||
q = q->next;
|
||
if(q->next != NULL){
|
||
q = q->next;
|
||
}
|
||
}
|
||
q = p->next;
|
||
p->next = NULL;
|
||
while(q != NULL){ //将链表后半段逆置
|
||
r = q->next;
|
||
q->next = p->next;
|
||
p->next = q;
|
||
q=r;
|
||
}
|
||
s = h->next; //s指向前半段的第一个数据结点，即插入点
|
||
q = p->next; //q指向后半段的第一个数据结点
|
||
p->next = NULL;
|
||
while(q != NULL){ //将链表后半段的结点插入到指定位置
|
||
r = q->next; //r指向后半段的下一个结点
|
||
q->next = s->next; //将q所指结点插入到s所指结点之后
|
||
s->next = q;
|
||
s = q->next; //s指向前半段的下一个插入点
|
||
q = r;
|
||
}
|
||
}
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2020
|
||
定义三元组(a,b,c)(均为整数)的具里D=|a-b|+|b-c|+|c-a|
|
||
给定三个非空整数集合S1、S2、S3,按升序分别存储在3个数组中
|
||
设计算法计算并输出所有可能的三元组(a,b,c)中的最小距离(a,b,c分别为S1,S2,S3中的整数)
|
||
例如S1={-1,0,9},S2={-25,-10,10,11},S3={2,9,17,30,41},则最小距离为2，相应的三元组为(9,10,9)
|
||
*/
|
||
|
||
---------------------------------------------------------------------------------------------------------------------------------------
|
||
/*2021
|
||
已知无向连通图G由顶点集V和边集E组成|E|>0
|
||
当G中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为|E|的路径(成为EL路径)
|
||
设图G采用邻接矩阵存储，类型定义如下：
|
||
|
||
Typedef struct{ //图的定义
|
||
int numVertices,numEdges; //图中实际的顶点权和边数
|
||
char VertticesList[MAXV]; //顶点表。MAXV为已定义常量
|
||
int Edge[MAXV][MAXV]; //邻接矩阵
|
||
}:MGraph;
|
||
|
||
设计算法:int IsExistEL(MGraph G),判断G是否存在EL路径，若存在，则返回1，否则返回0
|
||
*/
|
||
/*思路
|
||
对于采用邻接矩阵存储的无向图，邻接矩阵每一行(列)中非零元素的个数为本行(列)对应的顶点的度。
|
||
因此可以依次计算连通图G中各顶点的度，并记录度为奇数的顶点个数，若个数为0或2，则返回1，否则返回0
|
||
*/
|
||
int IsExistEL(MGraph G){
|
||
int degree,i,j,count=0;
|
||
for(i=0;i<G.numVertices;i++){
|
||
degree = 0;
|
||
for(j=0;j<G.numVertices;j++){
|
||
degree += G.Edge[i][j];
|
||
if(degree % 2 != 0){
|
||
count++;
|
||
}
|
||
}
|
||
}
|
||
if(count ==0 || count == 2){
|
||
return 1;
|
||
}
|
||
else
|
||
return 0;
|
||
} |