数据结构学习笔记文档格式.docx
《数据结构学习笔记文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构学习笔记文档格式.docx（39页珍藏版）》请在冰点文库上搜索。
,&
n）;
请输入这n个数:
for（i=1;
i<
i++）
a[i]）;
InsertSort（a,n）;
排序后的n个数是：
%4d"
a[i]）;
system（"
pause"
}
数据测试：
2、折半插入排序
//折半插入排序。
O
（1）;
voidBInsertSort（inta[],intn）{//对顺序表做折半插入排序。
n;
j++）{
a[0]=a[j];
intlow=1,high=j-1;
while（low<
=high）{//在a[low..high]中折半查找正确插入位置。
intm=（low+high）/2;
if（a[0]<
a[m]）high=m-1;
elselow=m+1;
}
for（k=j-1;
k>
=high+1;
k--）//记录后移。
a[k+1]=a[k];
a[high+1]=a[0];
//插入。
BInsertSort（a,n）;
3、希尔排序：
//希尔排序。
O（nlogn）。
为不稳定算法。
voidShellInsert（inta[],intn,intdk）{//对顺序表a[]做一趟希尔插入排序。
for（j=dk+1;
if（a[j]<
a[j-dk]）{
for（k=j-dk;
0&
&
k-=dk）
a[k+dk]=a[k];
a[k+dk]=a[0];
voidShellSort（inta[],intn,intdlta[],intt）{//按增量序列dlta[]对顺序表做希尔排序。
intm;
for（m=0;
m<
t;
m++）
ShellInsert（a,n,dlta[m]）;
inta[100],dlta[20],n,t,i;
请输入增量序列数的个数t:
t）;
请输入增量序列:
for（i=0;
dlta[i]）;
ShellSort（a,n,dlta,t）;
4、冒泡排序
//起泡排序。
O（n^2）。
为稳定排序算法。
voidBubbleSort（inta[],intn）{
inti,j,temp;
=n-1;
i++）{
for（j=1;
=n-i;
if（a[j]>
a[j+1]）{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
for（i=1;
i++）//注意数组的起始位置。
BubbleSort（a,n）;
5、快速排序：
//快速排序。
O（logn）。
intPartition（inta[],intn,intlow,inthigh）{//返回枢轴所在位置。
intpivotkey;
a[0]=a[low];
pivotkey=a[low];
while（low<
high）{
high&
a[high]>
pivotkey）high--;
a[low]=a[high];
a[low]<
pivotkey）low++;
a[high]=a[low];
a[low]=a[0];
returnlow;
voidQuickSort（inta[],intn,intlow,inthigh）{//递归形式快排。
intpivotloc;
if（low<
pivotloc=Partition（a,n,low,high）;
QuickSort（a,n,low,pivotloc-1）;
QuickSort（a,n,pivotloc+1,high）;
QuickSort（a,n,1,n）;
6、简单选择排序
//简单选择排序。
O（n^2）。
O
（1）
intSelectMinKey（inta[],intn,inti）{
intj,min;
min=i;
for（j=i+1;
a[min]）
min=j;
returnmin;
voidSelectSort（inta[],intn）{
j=SelectMinKey（a,n,i）;
if（i!
=j）{
temp=a[i];
a[i]=a[j];
a[j]=temp;
SelectSort（a,n）;
7、堆排序
代码；
8、归并排序
//归并排序。
voidMerge（intSR[],intTR[],intn,inti,intm,intt）{
//将有序的a[i..m]和a[m+1..t]合并为有序的TR[i..t]。
for（j=m+1,k=i;
=m&
=t;
k++）{
if（SR[i]<
=SR[j]）TR[k]=SR[i++];
elseTR[k]=SR[j++];
if（i<
=m）
while（i<
TR[k++]=SR[i++];
if（j<
=t）
while（j<
TR[k++]=SR[j++];
voidMSort（intSR[],intTR[],intn,ints,intt）{
//将SR[s..t]归并排序为TR[s..t]。
intm,TR1[100];
if（s==t）TR[s]=SR[s];
else{
m=（s+t）/2;
MSort（SR,TR1,n,s,m）;
//递归地将SR[s..m]归并为有序的TR1[s..m]。
MSort（SR,TR1,n,m+1,t）;
//递归地将SR[m+1..t]归并为有序的TR1[m+1..t]。
Merge（TR1,TR,n,s,m,t）;
//将TR1[s..m]、TR1[m+1..t]归并到TR1[s..t];
voidMergeSort（inta[],intn）{
MSort（a,a,n,1,n）;
MergeSort（a,n）;
2、链表与数组
1、假定数组A[N]的n个元素中有多个零元素，编写算法将A中所有的非零元素依次移到A的前端。
【华中科技大学，06年】
while
（1）{
pleaseinputthenumberofthearray:
pleaseinputeveryvalueinthearray:
intp=-1,q=0,m=0;
if（a[i]==0）{
if（!
q）p=i;
//p记录第一个零元素的位置。
q++;
//q记录已经遍历到的零元素的个数。
m++;
if（p>
q>
0）{
a[p]=a[i];
//移动非零元素至前面。
//a[i]=0;
q--;
//零元素个数减1。
if（q>
0）p++;
elseif（m>
0）
a[i-m]=a[i];
thevaluesafterremoving:
2、顺序存储的线性表，其数据元素为整型，试编写一算法，将A拆分成B和C两个表，使A中的元素值大于等于0的存入B，小于0的存入C中。
要求：
（1）表B和C另外设置存储空间。
（2）表B和C不另外设置，而利用A的空间。
（1）代码：
intA[10]={1,2,3,-4,-7,5,7,-9,8,-2};
intB[10],C[10];
inti,j,k;
i=j=k=0;
10;
if（A[i]>
=0）B[j++]=A[i];
elseC[k++]=A[i];
拆分前：
A:
"
A[i]）;
拆分后：
B:
j;
B[i]）;
C:
k;
C[i]）;
（2）代码：
inti=0,j=9,temp,t=0;
for（t=0;
t<
t++）
A[t]）;
while（A[i]>
=0）i++;
while（A[j]<
0）j--;
j）{
temp=A[i];
A[i]=A[j];
A[j]=temp;
i-1;
for（t=i;
9;
3、逆置单链表
无头节点单链表，节点：
数据域data、指针域next，表头指针h。
通过遍历链表，将所有的指针方向逆转，其中表头指针指向最后一个节点。
算法：
voidInverse（&
h）{
if（h==null）return;
p=h->
next;
pr=null;
while（p）{
h->
next=pr;
pr=h;
h=p;
p=p->
4、删除顺序表中元素
长度为n的线性表A采用顺序存储方式，写算法删除线性表中所有值为item的数据元素。
时间复杂度为O（n），空间复杂度为O
（1）。
5、将数组偶数移至奇数之前
设计将数组A[n]中所有的偶数移到奇数之前的算法。
不增加存储空间，且时间复杂度为O（n）。
intA[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
inti,j,x;
//x=A[0];
i=0;
j=19;
x=A[i];
while（A[j]%2==1）j--;
i++;
j）
while（A[i]%2==0）i++;
A[j]=A[i];
j--;
A[i]=x;
20;
%d"
6、逆序输出单链表各元素
typedefstructnode{
chardata;
structnode*next;
}list;
typedeflist*link;
linkCreate（）{//创建链表。
charch;
list*p;
linkhead;
head=NULL;
ch=getchar（）;
while（ch!
='
\n'
）{
p=（list*）malloc（sizeof（list））;
p->
data=ch;
next=head;
head=p;
returnhead;
voidDisplay（linkhead）{
p=head;
头插法建立的链表的输出结果:
%c"
p->
data）;
请输入链表的内容:
head=Create（）;
Display（head）;
7、合并两个单链表（Ⅰ）
A为递增有序的单链表，长度为n。
B为递减有序的单链表，长度为m。
编写程序，利用原表的存储空间，将A、B合并成为一个递增有序的单链表。
时间复杂度为O（m+n）。
//先将单链表B逆转：
voidReverse（Node*r）{
Node*q=r,*p=null,*temp;
while（q）{
temp=q;
q=q->
temp->
next=p;
p=temp;
r=p;
//再合并两个非递减的单链表：
Node*Merge（Node*a,Node*b）{
Node*s,*r;
Node*p=a,*q=b;
while（p!
=NULL&
q!
=NULL）{
if（p->
data<
q->
data）{
if（p==a）{
s=a;
r=a;
elser->
if（q==b）{
s=b;
r=b;
next=q;
r=r->
if（p==NULL&
=NULL）r->
if（q==NULL&
p!
returns;
//主方法。
合并题目所给的两个单链表。
Node*MergeFunc（Node*a,Node*b）{
Reverse（b）;
Node*result=Merge（a,b）;
resultresult;
8、合并两个单链表（Ⅱ）
单链表A、B，数据都为整型有序，编写程序，利用原节点，将A和B中具有相同数据的节点删除，并将B中与原A表不同数据的节点插入A中，保持A的递增有序。
voidMerge（Node*a,Node*b）{
Node*p,*q,*previous;
Node*temp1,*temp2;
//假设a、b带头节点。
p=a->
q=b->
previous=a;
while（p!
if（p->
previous=p;
//previous指示p的前驱。
p=p->
}
elseif（p->
data==q->
temp1=p;
previous->
next=p->
deletetemp;
}
else{
temp2=q;
q=q->
previous->
next=temp;
temp->
previous=previous->
if（p==NULL&
=NULL）previous->
9、两个单链表求∩和∪
已知2个按元素非递减的单链表A和B，设计一算法利用原表节点空间形成连续的新链表A’和B’，使得A’=A∪B，B’=A∩B。
voidAdjust（LinkList&
A,LinkList&
B）{
//假设A、B带头结点。
pa=A;
pb=B;
while（pa->
next!
pb->
if（pa->
next->
data）
pa=pa->
elseif（pa->
data==pb->
pa=pa->
pb=pb->
}
temp=pb->
ne
升级会员 