- 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。
#include <iostream>
#include<malloc.h>
#include<cstdio>
using namespace std;
typedef int ElemType;typedef struct
{ElemType data[50];int length;
} SqList;
void CreateList(SqList *&L,ElemType a[],int n)
//建立顺序表
{L=(SqList *)malloc(sizeof(SqList));for (int i=0; i<n; i++)L->data[i]=a[i];L->length=n;
}
void InitList(SqList *&L)
{L=(SqList *)malloc(sizeof(SqList));L->length=0;
}
void DispList(SqList *L)
{for (int i=0; i<L->length; i++)printf("%d ",L->data[i]);printf("\n");
}/*
//核心算法
void Delete(SqList *&L,int item)
{int i=0,k=0;while(i<L->length){if(L->data[i]!=item)L->data[k++]=L->data[i];i++;}L->length=k;
}*/int main()
{SqList *L;int n=5,e,i;ElemType a[]= {11,13,15,13,19};CreateList(L,a,n);DispList(L);printf("\n");Delete(L,13);cout<<"删除之后的结果是: "<<endl;DispList(L);
}
- 设有一个顺序表L，含有2n个整数，其中n个为负数，n个为正数，设计一个算法将L中所有元素按正负数相间排列。要求本算法的时间复杂度为O(n)，空间复杂度为O(1) 。
void Sort(SqList *&L)
{int i=0,j=L->length-1;while(i<j){while(L->data[i]>0)i++;while(L->data[j]<0)j--;if(i<j)swap(L->data[i],L->data[j]);}i=1,j=L->length-2;while(i<j){swap(L->data[i],L->data[j]);i+=2;j-=2;}}- 设计一个算法从一给定的有序顺序表L中删除元素值在x到y（x<=y）之间的所有元素，要求以较
高的效率来实现。要求算法的空间复杂度为O(1)
void Seek(SqList *&L,ElemType x,ElemType y)
{int k=0,i=0;while(i<L->length){if(L->data[i]>=x&&L->data[i]<=y)k++;else L->data[i-k]=L->data[i];i++;}L->length=L->length-k;
}4.试写一算法，对单链表实现就地逆置
void oppose(LinkList *&La)
{LinkList p,q;p=L->next;L->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=L->next;//头插法L->next=q;}}5．将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
void MergeList(LinkList *&La,LinkList *&Lb,LinkList *&Lc)
{LinkList pa,pb,pc,q;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa!=NULL&&pb!=NULL){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}else if(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}else{pc->next=pa;pc=pa;pa=pa->next;q=pb;pb=pb->next;free(q);}}//只把后面这一段链上就行if(pa!=NULL)pc->next=pa;if(pb!=NULL)pc->next=pb;//pc->next=pa?pa:pb;delete Lb;
}
6.将两个非递减（递增）的有序链表合并为一个非递增（递减）的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
void MergeList(LinkList *&La,LinkList *&Lb,LinkList *&Lc)
{LinkList pa,pb,pc,q;pa=pa->next;pb=pb->next;Lc=pc=La;Lc->next=NULL;while(pa!=NULL&&pb!=NULL){if(pa->data<=pb->data){q=pa;q->next=Lc->next;Lc->next=q;pa=pa->next;}else{q=pb;pb->next=Lc->next;Lc->next=q;pb=pb->next;}}while(pa!=NULL){q=pa;q->next=Lc->next;Lc->next=q;pa=pa->next;}while(pb!=NULL){q=pb;pb->next=Lc->next;Lc->next=q;pb=pb->next;}delete Lb;}7．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（ 若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
void Delete(LinkList *&L,ElemType maxi,ElemType mini)
{LinkList pa,q;pa=La->next;while(pa->data<=maxi){if(pa->data>=mini){q=pa;free(q);}pa=pa->next;}
}
8.已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change§,交换p所指向的结点和它的前缀结点的顺序。
void change(Linklist *&L)
{
q=p->prior;
p->prior=q->prior;
q-prior->next=p;
q->next=p>next;
p->next->prior=q;
p->next=q;
q->next=p;
}
