[数据结构与算法]（最基础数据结构题）第二章 线性表

1.设计一个算法判断单链表中的元素是否是递增的？

bool IsIncrease(Linklist *head)
{
	if(head== NULL || head->next==NULL){return true;}
	else{
			for(p=head,q=head->next;q!=NULL;p=q,q=q->next)
			{
				if(p->data>q->data) return false;
			}
			return true;
		}
}

2.设计一个算法将所有的奇数移所有偶数之前

void quick_move(int a[],int start ,int end)
{
	int tmp;
	while(start < end)
	{
		while(end>=0 && a[end]%2==0)//偶数
		{
			end--;
		}
		while(start < end && a[start]%2!=0)
		{
		start++;
		}
		if(start <end)
		{
		tmp=a[start];
		a[start]=a[end];
		a[end]=tmp;
		}
	}
}

3.设计一个最优算法实现输出链表倒数第K个结点

//算法思想，声明两个指针p1,p2，先让p1移动到K-1的位置，然后两个指针一起向
//后移动，知道p1->next为空，p2指向的就是倒数第K个
ListNode *FindKthToTail(Listnode *head,int k)
{
	ListNode*p1,p2=head;
	for(int i=0;i<k-1;i++)
	{
		p1=p1->next;
	}
	while(p1->next)
	{
		p1=p1->text;
		p2=p2->next;
	}
	return p2;
}

4.设计一个算法实现在单链表中删除值相同的多余节点的算法

typedef struct node{
	int data;
	struct node*next;
}LinkList;

void DelSameNum(LinkList *head)
{
	for(p=head;p!=NULL;p=p->next)
	{
		s=p;
		for(q=p->next;q!=NULL; )
		{
			if(q->data==p->data)
			{
				s->next=q->next;//s指向q的下一个结点
			}else
			{
				s=q;
				q=q->next;//q往后移
			}
		}
	}
}

5.单链表结构实现简单选择排序算法

void Linklist_Select_Sort(LinkList *l)
{
	for(p=l;p->next->next;p=p->next)
	{
		q=p->next;
		x=q->data;
		for(r=q,s=q;r->next;r=r->next)
		{
			if(r->next->data < x)
			{
				x=r->next->data;
				s=r;
			}
			if(s!=q)//找到了值比q->data更小的最小结点
			{
				p->next=s->next;
				s->next=q;
				t=q->next;
				q->next=p->next->next;
				p->next->next=t;
			}
			
		}
	}
}

6.假设有两个元素值递增有序的线性表La和Lb，均以带头结点的单链表作为存储结构，编写算法将La和Lb合并为一个按照元素值递减有序排列的线性表Lc，并要求利用原表的结点空间存放Lc

struct Lnode{
	datatype data;
	struct Lnode*next;
}
void merge_dowum(Linklist &la,Linklist &lb,Linklist &lc)
{
	pa=la->next;
	pb=lb->next;
	pc=la;
	lc->next==NULL;
	while(pa||pb)
	{
		if(!pa)
		{
			pc=pa;
			pa=pa->next;	
		}else if(!pb)
		{
			pc=pb;
			pb=pb->next;
		}
		else if(pa->data<=pb->data)
		{
			pc=pa;
			pa=pa->next;
		}
		else
		{
			pc=pb;
			pb=pb->next;
		}
		else
		{
			pc=pb;
			pb=pb->next;
		}
		pc->next=lc->next;
		lc-<next=pc;
	}
}

7.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同后缀的空间，设计一个算法，找出由str1和str2两个链表共同后缀的起始位置。

//思路：先算出两个长度m和n，将链尾对齐，m，n相等则指针p，q指向头结点，
//若m>n,则一个指向m-n+1的结点，pq同步向后移动，若pq指向同一个结点，则该点为起始位置。
LinkNode *Find_lst_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(p=str2;len1<len2;len2--)
	{
		q=q->next;
	}
	while(p->next!=NULL&&p->next!=q->next)
	{
		p=p->next;
		q=q->next;
	}
	return p->next;
}
//时间复杂度len1+len2

8.已知一个整数序列A=（a0,a1，…，an-1），若存在ap1=ap2=apm=x且m>n/2,则x为A的主元素，如A=（0,5，5,3，5,7，5,5），则5为主元素，A元素保存在数组里面，存在主元素找出，不存在返回-1；

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;
}
//时间复杂度n，空间复杂度1

9.单聊表保存m个整数，data绝对值小于等于n，设计一个时间复杂度尽可能高的算法，对于链表绝对值相等的点，仅保留第一次出现的结点而删除其他绝对值相等的点

void del_same(LinkList &head,int n){
    LNode *p=head->next,*pre=head;
    if(p==NULL) return;
    int arr[n+1],m;
    //初始化辅助数组
    for(int i=0;i<arr.length;i++)   arr[i]=0;
    while(p!=NULL){
        m=p->data>=0?p->data:-p->data;
        if(arr[p->data]==0){    //没出现过
            arr[p->data]=1;
            pre=p;
            p=p->next;
        }else{  //出现过了
            pre->next=p->next;
            free(p);p=pre->next;
        }
    }
}
//时间复杂度m，空间复杂度n

10.已知由n个正整数构成的集合A，将其划分为两个不相交的子集A1和A2，元素个数分别为n1和n2，A1和A2元素之和分别为S1和S2，设计一个划分算法，满足n1-n2的绝对值最小且s1-s2的绝对值最大。

//前n/2放在a1后一半放在a2
int setPartition(int a[],int n)
{
	int pivotkey,low=0,low0=0;high=n-1;high0=n-1,flag=1,k=n/2,i;
	int s1=0;s2=0;
	while(flag)
	{
		piovtkey=a[low];
		while(low<high)
		{
			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=0;i<k;i++) s1+=a[i];
	for(i=k;i<n;i++) s2+=a[i];
	return s2-s1;
}
//时间复杂度n，空间复杂度1

11.无表头结点的单链表la和lb，写一算法，删除单链表la第i个结点起长度为冷的结点，并将其插入到单链表lb的第j个结点上

s=la;
q=lb;
for(int a=0;a<i;a++)
{
	p=p->next;
	s=s->next;
	
}//p,s都指向第i个结点
for(int a=0;a<len;a++)
{
	p->next=s->next;
	s=s->next;
}//执行完删除la第i个元素之后的元素
for(int a=0;a<j-1;a++)
{
	q=q->next;//执行完后q为lb的j-1个结点
	m=m->next;//m为lb第j个结点
}
q->next=la;//lb的j-1结点指向la
while(p->next!=null)
p=p->next;//p为la最后一个结点。
p->next=m;//la最后一个结点指向lb第一个结点

12.带头结点的单链表，判断线性表是否符合，所有的奇数在前面，偶数在后面。

int discriminant(List&l)
{
	Vector<int> result;
	int index=0;
	List p;
	p=l;
	while(p)
	{
		if(p->data%2!=0)//奇数入列
		{
			result.append(index);
		}
		p=p->next;
		index++;
	}
	for(int i=0;i<result.size()-1;i++)
	{
		flag=result[i+1]-result[i];//如果满足条件，result相邻元素差值为1
		if(flag!=1) return 0;//不满足
		
	}
	return 1;//满足
}

13.写出递归删除单链表所有值为item的算法

delete(LinkList &l,ElemType item)
{
	int p;
	if(l!=NULL) return ;//递归出口
	if(l->data==item){
	p=l;
	l=l->next;
	free(p);
	delete(l,item);}//删除结点
	else  delete(l->next,item);
}

14.给定一个值，求出所有得到的新值的个数。例如给出值为345，将其各为数字相加的新值为12，对12各位相加得到的新值为3，则345得到的新值的个数为三个，包括本身。

//算法思想：需要使用双循环，外循环用于计数，并将和赋值给新的数，内循环
//用于统计数字的和，外循环结束条件为数字只有一位，内循环的结束条件是数字为0。
int newNum(int num)
{
	int sum=num,i=1;
	while(sum%10!=0)//统计个数并将新的和赋值给num
	{
		i++;
		num=sum;
		sum=0;
		while(num!=0)//每一位相加的内循环
		{
			sum+=num%10;
			num=num/10;
		}
	}
	return i;
}