『壹』 數據結構線性表（C版）問題 設計演算法
Locate_Sq(Splist *L,int i)
{ if(L->len==0) return 0;
for(j=1;j<=l->len;j++)
if(l->elem[i]==x) retrun i;
else return 0;
}
『貳』 求數據結構試驗 線性表的順序存儲結構
查找：
順序表的順序查找演算法：
int Seqsearch1(int r[],int n,int k)
{
r[0]=k;
i=n;
while(r[i]!=k)
i--;
return i;
}
單鏈表的順序查找演算法：
int Seqsearch2(Node<int> *first,int k)
{
p=first->next;j=1;
while(p!=NULL&&p->data!=k)
{
p=p->next;
j++;
}
if(p->data==k)return j;
else return 0;
}
折半查找：
非遞歸
int Binsearch1(int r[],int n,int k)
{
high=n;low=1;
while(low<=high)
{
mid=(high+low)/2;
if(k<mid) high=mid-1;
else if(k>mid) low=mid+1;
else return mid;
}
return 0;
}
遞歸
int Binsearch2(int r[],int low,int high,int k)
{
if(low>high) return 0;
else
{
mid=(low+high)/2;
if(K<mid) return Binsearch2(r,low,mid-1,k);
else if(K>mid) return Binsearch2(r,mid+1,high,k);
else return mid;
}
}
二叉樹排序：
class BiSortTree
{
public:
BiSortTree(int a[],int n);
~BiSortTree();
void InsertBST(BiNode<int> *root,BiNode<int> *s);
void DeleteBST(BiNode<int> *p,BiNode<int> *f);
BiNode<int>* SearchBST(BiNode<int> *root,int k);
private:
BiNode<int> *root;
};
void BiSortTree::InsertBST(BiNode<int> *root,BiNode<int> *s);
{
if(root==NULL) root=s;
else if(s->data<root->data) InsertBST(root->lchild,s);
else InsertBST(root->rchild,s);
}
BiSortTree::BiSortTree(int r[],int n)
{
for(i=0;i<n;i++)
{
s=new BiNode<int>;s->data=r[i];
s->lchild=s->rchild=NULL;
InsertBST(root,s);
}
}
void BiSortTree::DeleteBST(BiNode<int> *p,BiNode<int> *f)
{
if(!p->lchild&&!p->rchild)
{
f->lchild=NULL;
delete p;
}
else if(!p->lchild)
{
f->lchild=p->rchild;
delete p;
}
else if(!p->rchild)
{
f->lchild=p->lchild;
delete p;
}
else
{
par=p;s=p->rchild;
while(s->lchild!=NULL)
{
par=s;
s=s->lchild;
}
p->data=s->data;
if(par==p) par->rchild=s->rchild;
else par->lchild=s->rchild;
delete s;
}
}
BiNode<int> *BiSortTree::SearchBST(BiNode<int> *root,int k)
{
if(root==NULL) return NULL;
else if(root->data==k) return root;
else if(root->data<k) return SearchBST(root->lchild,k);
else return SearchBST(root->rchild,k);
}
閉散列表的查找演算法：
int HashSearch1(int ht[],int m,int k)
{
j=H[k];
if(ht[j]==k) return j;
i=(j+1)%m;
while(ht[i]!=Empty&&i!=j)
{
if(ht[i]==k) return i;
i=(i+1)%m;
}
if(i==j) throw"溢出";
else ht[i]=k;
}
開散列表的查找演算法：
Node<int> *HashSearch2(Node<int> *ht[],int m,int k)
{
j=H[k];
p=ht[j];
while(p&&p->data!=k)
p=p->next;
if(p->data==k) return p;
else
{
q=new Node<int>;q->data=k;
q->next=ht[j];
ht[j]=q;
}
}
排序：
插入
直接插入排序演算法：
void InsertSort(int r[],int n)
{
for(i=2;i<=n;i++)
{
r[0]=r[i];
for(j=i-1;r[0]<r[j];j--)
r[j+1]=r[j];
r[j+1]=r[0];
}
}
希爾排序演算法：
void ShellSort(int r[],int n)
{
for(d=n/2;d>=1;d=d/2)
{
for(i=d+1;i<=n;i++)
{
r[0]=r[i];
for(j=i-d;j>0&&r[0]<r[j];j=j-d)
r[j+d]=r[j];
r[j+d]=r[0];
}
}
}
交換
起泡排序：
void BubbleSort(int r[],int n)
{
exchange=n;
while(exchange)
{
bound=exchange;exchange=0;
for(j=1;j<bound;j++)
if(r[j]>r[j+1])
{
r[j]<-->r[j+1];
exchange=j;
}
}
}
快速排序：
int Partition(int r[],int first,int end);
{
i=first;j=end;
while(i<j)
{
while(i<j&&r[i]<=r[j]) j--;
if(i<j)
{
r[i]<-->r[j];
i++;
}
while(i<j&&r[i]<=r[j]) i++;
if(i<j)
{
r[i]<-->r[j];
j--;
}
}
return i;
}
void QuickSort(int r[],int first,int end)
{
if(first<end)
{
pivot=partition(r,first,end)
QuickSort(r,first,pivot-1);
QuickSort(r,pivot+1,end);
}
}
選擇
簡單選擇排序：
void SelectSort(int r[],int n)
{
for(i=1;i<n;i++)
{
index=i;
for(j=i+1;j<n;j++)
if(r[j]<r[index]) index=j;
if(index!=i) r[i]<-->r[index];
}
}
堆排序：
void Sift(int r[],int k,int m)
{
i=k;j=2*i;
while(j<=m)
{
if(j<m&&r[j]<r[j+1])j++;
if(r[i]>r[j]) break;
else
{
r[i]<-->r[j];
i=j;j=2*i;
}
}
}
void HeapSort(int r[],int n)
{
for(i=n/2;i>=1;i--)
sift(r,i,n);
for(i=1;i<n;i++)
{
r[1]<-->r[n-i+1];
sift(r,1,n-i);
}
}
歸並
二路歸並排序：
void Merge(int r[],int r1[],int s,int m,int t)
{
i=s;j=m+1;k=s;
while(i<=m&&j<=t)
{
if(r[i]<=r[j]) r1[k++]=r[i++];
else r1[k++]=r[j++];
}
if(i<=m) while(i<=m)
r1[k++]=r[i++];
else while(j<=t)
r1[k++]=r[j++];
}
void Merge(int r[],int r1[],int n,int h)
{
i=1;
while(i<=n-2h+1)
{
Merge(r,r1,i,i+h-1,i+2h-1);
i=i+2*h;
}
if(i<n-h+1) Merge(r,r1,i,i+h-1,n)
else for(k=i;k<=n;k++)
r1[k]=r[k];
}
void MergeSort1(int r[],int r1[],int n)
{
h=1;
while(h<n)
{
MergePass(r,r1,n,h);
h=2*h;
MergePass(r1,r,n,h);
h=2*h;
}
}
void MergeSort2(int r[],int r1[],int s,int t)
{
if(s==t) r1[s]=r[t];
else
{
m=(s+t)/2;
MergeSort2(r,r1,s,m);
MergeSrot2(r,r1,m+1,t);
Merge(r1,r,s,m,t);
}
}