数据结构程序.docx
《数据结构程序.docx》由会员分享，可在线阅读，更多相关《数据结构程序.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构程序
单链表
#include
#include
#include
typedefstructNode{
intdata;
structNode*next;
}DanNode;
voidgoujian（DanNode**head,intgeshu）
{
inti,x;
DanNode*p;
*head=（DanNode*）malloc（sizeof（DanNode））;
p=*head;
for（i=0;i{
scanf（"%d",&x）;
p->data=x;
p->next=（DanNode*）malloc（sizeof（DanNode））;
p=p->next;
if（x==-1）
break;
}
scanf（"%d",&x）;
p->data=x;
p->next=0;
}
voidxianshi（DanNode*head）
{
inti;
DanNode*p=head;
i=0;
while（p!
=0）
{
printf（"第%d个节点:
%d\n",i++,p->data）;
p=p->next;
}
}
voidmain（）
{
DanNode*xhead;
goujian（&xhead,10）;
xianshi（xhead）;
getchar（）;
}
双链表
#include
#include
#include
typedefstructDuLNode{
intdata;
structDuLNode*prior;
structDuLNode*next;
}DuLNode,*DuLink;
DuLNode*create（DuLNode*h）
{
DuLNode*c,*r;
inti,n;
r=h;
printf（"请输入建立链表的个数:
"）;
scanf（"%d",&n）;
r->data=n;/*头结点保存链表元素个数*/
for（i=0;i{
c=（DuLNode*）malloc（sizeof（DuLNode））;
printf（"输入节点的值:
"）;
scanf（"%d",&（c->data））;
/*先勾走新建节点的前后链接指针*/
c->prior=r;
c->next=NULL;
/*将新建节点添加到链表尾*/
r->next=c;
/*链表尾指针后移*/
r=c;
}
returnh;
}
voidoutput（DuLNode*h）
{
DuLNode*l;
l=h->next;
while（l!
=NULL）
{
printf（"%d\n",l->data）;
l=l->next;
}
}
intmain（void）
{
DuLNode*p=（DuLNode*）malloc（sizeof（DuLNode））;/*为链表头分配空间*/
create（p）;
output（p）;
free（p）;
return0;
}
堆栈
#include
//数组实现堆栈
typedefstructDalangtong{
intshaobingTong[5];
inttop;
}Dalangtong;
voidchushihua（Dalangtong*xtong）{
xtong->top=0;
}
voidfangshaobing（Dalangtong*xtong,intshaobing）{
if（xtong->top>=5）{
printf（"桶满了，别放了"）;
return;
}
//（*xtong）.shaobingTong[（*xtong）.top]=shaobing;
xtong->shaobingTong[xtong->top]=shaobing;
xtong->top++;
}
intqushaobing（Dalangtong*xtong）{
intx;
if（xtong->top<=0）{
printf（"没有烧饼了！
"）;
return-1;
}
x=xtong->shaobingTong[xtong->top-1];
xtong->top--;
returnx;
}
intkanshaobing（Dalangtong*xtong）{
if（xtong->top<=0）{
printf（"看什么看，没有烧饼了！
"）;
return-1;
}
returnxtong->shaobingTong[xtong->top-1];
}
intmain（）{
Dalangtongtong1,tong2;
inti,x,n;
chushihua（&tong1）;
printf（"请输入烧饼的个数：
"）;
scanf（"%d",&n）;
for（i=0;i{
scanf（"%d",&x）;
fangshaobing（&tong1,x）;
}
for（i=0;i{
printf（"%d\n",qushaobing（&tong1））;
}
getchar（）;getchar（）;
}
树
#include
typedefstructtree{
chardata;
structtree*leftchild;
structtree*rightchild;
}tree;
voidgoujian（tree**root,chart）
{
tree*p;
p=*root;
p=（tree*）malloc（sizeof（tree））;
p->data=t;
p->leftchild=0;
p->rightchild=0;
}
intaddleftchild（tree**node,charx）
{
tree*p;
p=*node;
if（p==0）
return0;
p=（tree*）malloc（sizeof（tree））;
p->data=x;
p->leftchild=0;
p->rightchild=0;
return1;
}
intaddrightchild（tree**node,charx）
{
tree*p;
p=*node;
if（p==0）
return0;
p=（tree*）malloc（sizeof（tree））;
p->data=x;
p->leftchild=0;
p->rightchild=0;
return1;
}
intmain（）
{
tree*root,*m,*n;
goujian（&root,'a'）;
m=addleftchild（&root,'b'）;
n=addrightchild（&root,'c'）;
addleftchild（&m,'d'）;
addrightchild（&m,'e'）;
addleftchild（&n,'f'）;
addrightchild（&n,'g'）;
return0;
}
排序
#include
#include
#include
#include
#defineBUF100
typedefstructStation{
charstationName[50];
charpinyin[50];
intstationId;
}Station;
voidpartString（char*src,char*dst,intstart,intend）{
inti,j;
j=0;
for（i=start;idst[j++]=src[i];
dst[j]=0;
}
voidreadToArray（Station*bjStation,char*filePath）{
FILE*fp_read;
inti=0,j=10;
charsLine[100],stationName[50],pinyin[50],stationIdStr[10];
intstationId;
intfirstIndex,secondIndex;
if（（fp_read=fopen（filePath,"r"））==NULL）
{
printf（"文件打开失败!
\n"）;
}
while（fgets（sLine,BUF,fp_read）!
=0）{
firstIndex=0;
while（sLine[firstIndex]!
=','）firstIndex++;
partString（sLine,stationName,0,firstIndex）;
secondIndex=firstIndex+1;
while（sLine[secondIndex]!
=','）secondIndex++;
partString（sLine,pinyin,firstIndex+1,secondIndex）;
partString（sLine,stationIdStr,secondIndex+1,strlen（sLine）-1）;
strcpy（bjStation[i].stationName,stationName）;
strcpy（bjStation[i].pinyin,pinyin）;
bjStation[i].stationId=atoi（stationIdStr）;
//printf（"%s\n",bjStation[i].stationName）;
i++;
}
}
voidwriteArrayToFile（StationbjStation[],intlen,char*filePath）{
FILE*fp_write;
charsLine[100],stationIdStr[10];
inti;
if（（fp_write=fopen（filePath,"wb"））==NULL）
{
printf（"文件写入失败!
\n"）;
}
//*
for（i=0;isLine[0]=0;//清空字符串
strcat（sLine,bjStation[i].stationName）;
strcat（sLine,","）;
strcat（sLine,bjStation[i].pinyin）;
strcat（sLine,","）;
itoa（bjStation[i].stationId,stationIdStr,10）;
strcat（sLine,stationIdStr）;
strcat（sLine,"\r\n"）;
fputs（sLine,fp_write）;
};
//*/
//fputs（"test\r\n",fp_write）;
//fputs（"asdfj",fp_write）;
fclose（fp_write）;
}
voidcopyStation（Station*src,Station*dest）{//赋值
strcpy（dest->stationName,src->stationName）;
strcpy（dest->pinyin,src->pinyin）;
dest->stationId=src->stationId;
}
voidcharuPaixu（Stationa[],intn）//简单插入排序
{
inti,j;
Stationtemp;
for（i=0;i{
copyStation（&a[i+1],&temp）;
j=i;
while（j>-1&&strcmp（temp.pinyin,a[j].pinyin）<0）
{
copyStation（&a[j],&a[j+1]）;
j--;
}
copyStation（&temp,&a[j+1]）;
}
}
voidBubbleSort（Stationa[],intn）//冒泡排序
{
inti,j,flag=1;
Stationtemp;
for（i=1;i{
flag=0;
for（j=0;j{
if（strcmp（a[j].pinyin,a[j+1].pinyin）<0）
{
flag=1;
copyStation（&a[j],&temp）;
copyStation（&a[j+1],&a[j]）;
copyStation（&temp,&a[j+1]）;
}
}
}
}
voidShellSort（Stationa[],intn,intd[],intnum）//希尔插入排序
{inti,j,k,m,span;
Stationtemp;
for（m=0;m{
span=d[m];
for（k=0;k{
for（i=k;i{
temp=a[i+span];j=i;
while（j>-1&&strcmp（temp.pinyin,a[j].pinyin）<0）
{
copyStation（&a[j],&a[j+span]）;
j=j-span;
}
copyStation（&temp,&a[j+span]）;
}
}
}
}
voidSelectSort（Stationa[],intn）//简单选择排序
{
inti,j,small;
Stationtemp;
for（i=0;i{
small=i;
for（j=i+1;jif（strcmp（a[j].pinyin,a[small].pinyin）<0）
small=j;
if（small!
=i）
{
copyStation（&a[i],&temp）;
copyStation（&a[small],&a[i]）;
copyStation（&temp,&a[small]）;
}
}
}
voidmain（）{
longstart=clock（）;
intd[7]={1000,300,100,40,10,5,1};
charfilePath[200]="D:
\\bjStations.txt";
StationbjStation[9787];
readToArray（bjStation,filePath）;
//charuPaixu（bjStation,9787）;//1640ms简单插入排序
ShellSort（bjStation,9787,d,7）;//62ms希尔插入排序
//SelectSort（bjStation,9787）;//469ms简单选择排序//任选一个
//BubbleSort（bjStation,9787）;//5078ms冒泡排序
//QuickSort（bjStation,0,9786）;//15ms快速排序
//heapSort（bjStation,9787）;//46ms堆排序
writeArrayToFile（bjStation,9787,"D:
\\gj.txt"）;
printf（"执行时间为%ld毫秒\n",clock（）-start）;getchar（）;
}
升级会员 