[数据结构与算法]算法-耿国华-数据结构-第二章

//从线性表中删除介于X和Y之间的所有元素，空间复杂度O（1）
void delallxy(Sqlist *l,int x,int y)
{
    int i=0;
    int j=0;
    while(i<l->length)
    {
        if(l->data[i]>=x && l->data[i]<=y)
            j++;
        else
            l->data[i-j]=l->data[i];
        i++;
    }
    l->length -= j;
}

//在一个递增有序的单链表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素
void Del_Same(LinkList &L){
	//L是递增有序的单链表，本算法删除表中数值相同的元素
	Node *p ,*q;			//p为扫描工作指针
	p = L->next;
	if(p==NULL)
		return;
	while(p->next!=NULL){
		q=p->next;					//q指向*p的后继结点
		if(p->data==q->data){		//找到重复值的结点
			p->next=q->next;		//释放*q的结点
			free(q);				//释放相同元素值的结点
		}
		else
			p=p->next;
	}
}

//已知顺序表L中的元素为int，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，将L中的奇数元素排在前面，偶数元素放在后面。
void Sort(SeqList *L)
{
	int i=0,j=L->length-1;
	int t;
	while(i<j)
	{
		while(L->data[i]%2==1)
		   i++;
		while(L->data[j]%2==0)
		   j--;
		if(i<j)
		{
			t=L->data[i];
			L->data[i]=L->data[j];
			L->data[j]=t;
		}
	 } 
}

//已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素
void DelXY(LinkList &L,int mink,int maxk)
{
	LinkList p,q,s;
	p=L->next;
	while(p->data!=mink)
	{
		p=p->next;//找到值为mink元素所在的位置
	}
	q=p->next;
	while(q->data!=maxk)//删除比maxk值小的元素
	{
		s=q;
		q=q->next;
		p->next=q;
		free(s);
	}	
}

//编写程序，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度O（n），空间复杂度为O（1）
void delExcrescentValue(SeqList *S){
    int flag = 0,val = S.elem[0];//记录值不等的下标  val为哨兵
    for(int i = 1;i<=S.last;i++){
        if(val != S.elem[i]){
            val = S.elem[i];
            flag += 1;
            S.elem[flag] = val;
        }
    }
    S.last = flag;
    return;
}
//以不同的存储结构实现线性表的就地逆置算法
（1）以一维数组作存储结构
void reverse(SeqList *L)
{
	int t=0,j=L->length-1;
	for(int i=0;i<L->length/2;i++)
	{
		t=L->data[i];
		L->data[i]=L->data[j];
		L->data[j]=t;
		j--;
	}
}

（2）以单链表作存储结构
void reverse(LinkList &L)
{
	LinkList p,q;
	p=L->next;
	L->next=NULL;//逆置单链表初始为空表 
	while(p!=NULL)
	{
		q=p->next;
		p->next=L->next;
		L->next=p;//用头插法将结点插入逆置表中 
		p=q;	
	 } 
}

//编写算法，删除单链表L（L中元素值各不相同）的最大值所对应的结点，并返回该值。
void DeleteMax(LinkList &L,int *e)
{
	LinkList p,q,s;
	p=L->next;   //p从首元结点开始
	q=p->next;   //q从第二个结点开始
	s=p;  //s用来寻找最大值前一个元素的位置
	while(q!=NULL)
	{
		if(p->data < q->data)
		    p=q;
		q=q->next;
	}
	while(s->next!=p)
	{
		if(p==L->next)
		    s=L;    //如果最大值正好是首元结点，就将s指向头结点
		else
		    s=s->next;
	 } 
	*e=p->data;
	s->next = p->next;//将结点p（最大值）从链表中删除
	free(p);
}

//假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中的某个结点的指针，试编写算法删除结点s的前驱结点
void del(LinkList  &zs)
{
    Node *q, *p1, *p2;
    //q是搜索s前驱的前驱，p1是搜索s前驱，p2是搜索s
    q = s;
    p1 = q->next;
    p2 = p1->next;
    while(p2 != s)
    {
        p2 = p2->next;
        p1 = p1->next;
        q = q->next;
    }
    q->next = p2;
    delete(p1);
}