数据结构各种算法.docx
- 文档编号:1629251
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:61
- 大小:171.65KB
数据结构各种算法.docx
《数据结构各种算法.docx》由会员分享,可在线阅读,更多相关《数据结构各种算法.docx(61页珍藏版)》请在冰点文库上搜索。
数据结构各种算法
一,串的模式匹配
/*思路:
从源串首址开始和子串的第一个字符进行比较,不同时源串加一,子串不变,当遇到相同时,记录此时源串位置A,源串子串同时加一,假如子串可以比较完,则说明模式匹配成功,假如有一个不同时就说明匹配不成功,这时源串返回到A处,子串返回首址,如此直到源串比较完毕。
*/
//模式匹配的程序代码
#include
#include
#include
//顺序串的结构类型定义
#definemaxsize100
typedefstruct
{
charstr[maxsize];
intlen;
}seqstring;
intIndex(seqstring*,seqstring*);
voidmain()
{
intw;
seqstring*s,*subs;
s=(seqstring*)malloc(sizeof(seqstring));
subs=(seqstring*)malloc(sizeof(seqstring));
printf("输入串:
");gets(s->str);
s->len=strlen(s->str);
printf("输入子串:
");gets(subs->str);
subs->len=strlen(subs->str);
if(Index(s,subs)>0)printf("匹配成功!
\n");
elseprintf("匹配失败!
\n");
scanf("%d",&w);
}
//添加顺序串的朴素模式匹配算法
intIndex(seqstring*s,seqstring*subs)
{
seqstring*p,*q;
inti,j;
p=s;q=subs;//分别设置p,q为工作指针
i=0;
while(p->str[i]!
=0)//判断结束条件
{
j=0;//每一次比较都是从字串的首址开始
while(p->str[i]==q->str[j]&&q->str[j]!
=0)
{i++;j++;}
if(q->str[j]==0)//子串比较完毕,说明匹配成功
{return1;}//比较成功,返回
else
{i=i-j+1;}//此次比较不成功,源串返回到初始状态
}
return0;
}
二,单链表逆置
/*思路:
先设置3个连续的工作指针,利用第三个来标识逆置过程中与前面断开的后续节点,利用两个来进行逆置即可,链表逆置完毕后在进行最后的特殊例如头结点等处理即可*/
#include
#include
//单链表结构类型定义
typedefchardatatype;
typedefstructnode
{
datatypedata;
structnode*next;
}linklist;
voidcreate(linklist*&);
voidprint(linklist*);
voidinvert(linklist*);
intmain()
{
intn;
linklist*head;
create(head);
print(head);
invert(head);//调用单链表逆置的函数
print(head);
scanf("%d",&n);
}
//采用尾插法建立具有头结点的单链表
voidcreate(linklist*&head)
{
charch;
linklist*s,*r;
head=(linklist*)malloc(sizeof(linklist));
r=head;
while((ch=getchar())!
='*')
{
s=(linklist*)malloc(sizeof(linklist));
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
}
//输出单链表
voidprint(linklist*head)
{
linklist*p=head->next;
while(p!
=NULL)
{
printf("%2c",p->data);
p=p->next;
}
printf("\n");
}
//添加单链表逆置算法
voidinvert(linklist*head)
{linklist*a,*b,*c;
a=head->next;b=a->next;c=b->next;//abc分别是工作指针
while(c->next!
=NULL)//操作结束的标志
{b->next=a;a=b;b=c;c=c->next;}//逆置操作
c->next=b;b->next=a;head->next->next=NULL;head->next=c;
}
三,分解单链表
/*思路:
输入单链表后从首址开始逐个判断,每判断一个就对相应的链表插入一个,但是注意应该先将原来的节点取下,插入一个时要兴建一个节点避免将原来链表中该节点的后续节点连接进去*/
#include
#include
#include
#include
typedefchardatatype;
typedefstructnode
{datatypedata;
structnode*next;
}linklist;
voidcreate(linklist*&);
voidresolve(linklist*,linklist*,linklist*,linklist*);
voidinsert(linklist*,linklist*);
voidprint1(linklist*);
voidprint2(linklist*);
voidmain()
{
intn;
linklist*head,*letter,*digit,*other;
create(head);
print1(head);
letter=(linklist*)malloc(sizeof(linklist));//建立3个空循环链表
letter->next=letter;
digit=(linklist*)malloc(sizeof(linklist));
digit->next=digit;
other=(linklist*)malloc(sizeof(linklist));
other->next=other;
resolve(head,letter,digit,other);//调用分解单链表的函数
print2(letter);//输出循环链表
print2(digit);
print2(other);
scanf("%d",&n);
}
//建立单链表
voidcreate(linklist*&head)
{datatypex;
linklist*s,*r;
head=newlinklist;
r=head;
while((x=getchar())!
='$')
{
s=(linklist*)malloc(sizeof(linklist));
s->data=x;
r->next=s;
r=s;
}
r->next=NULL;
}
//在循环链表中插入
voidinsert(linklist*h,linklist*p)
{linklist*q=h;
while(q->next!
=h)q=q->next;
q->next=p;
p->next=h;
}
//输出单链表
voidprint1(linklist*head)
{linklist*p=head->next;
while(p!
=NULL)
{printf("%c",p->data);
p=p->next;
}
printf("\n");
}
//输出循环链表
voidprint2(linklist*head)
{linklist*p=head->next;
while(p!
=head)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
voidresolve(linklist*head,linklist*letter,linklist*digit,linklist*other)//添加按l字母、数字、其它字符分解单链表算法
{
linklist*r,*s;
r=head->next;
while(r!
=NULL)
{
if(r->data>='A'&&r->data<='Z')
{
s=(linklist*)malloc(sizeof(linklist));//建立3个空循环链表
s->data=r->data;s->next=NULL;
insert(letter,s);
}
elseif(r->data>='a'&&r->data<='z')
{
s=(linklist*)malloc(sizeof(linklist));//建立3个空循环链表
s->data=r->data;s->next=NULL;
insert(letter,s);
}
elseif(r->data>='0'&&r->data<='9')
{
s=(linklist*)malloc(sizeof(linklist));//建立3个空循环链表
s->data=r->data;s->next=NULL;
insert(digit,s);
}
else
{
s=(linklist*)malloc(sizeof(linklist));//建立3个空循环链表
s->data=r->data;s->next=NULL;
insert(other,s);
}
r=r->next;
}
}
四,分块查找
/*思路:
现在索引表中进行二分法查找,找到对应的范围然后根据起始节点和该范围的结点个数进行顺序查找直到找出给该节点,不然返回查找不到的标志位*/
//分块查找的程序代码
#include
//类型定义
typedefintkeytype;
typedefstruct
{
keytypekey;
intlow,high;
}index;
typedefstruct
{
keytypekey;
}record;
constintrecN=18;
constintidxN=3;
intblksearch(record[],index[],keytype,int);
voidmain()
{
recordr[recN]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};
indexidx[idxN]={{22,0,5},{48,6,11},{86,12,17}};
keytypekey;
intloc,i,s;
printf("待查找的记录关键字表:
\n");
for(i=0;i printf("%5d",r[i]); printf("\n"); printf("输入所要查找记录的关键字: "); scanf("%d",&key); loc=blksearch(r,idx,key,idxN); if(loc! =-1)printf("查找到,是第%d个记录。 \n",loc+1); elseprintf("记录查找不到! \n"); scanf("%d",&s); } //添加折半查找索引表,块内顺序查找算法 intblksearch(recordr[recN],indexidx[idxN],keytypekey,intidxN) { intn,i,j=idxN-1;//i作为二分法的下限,j是上限,n是标记位 intq;//q是中间位 n=-1; i=0; while(j-i>=0)//结束循环的条件就是上限比下限小 { q=(i+j)/2; if(idx[q].key>key)//当中间比关键字大时的操作 {j=q-1;} elseif(idx[q].key {i=q+1;} else//当中间等于关键字时的操作 {break;} } q=i>=j? i: j;//q即就是最后二分法的结果,属于哪个范围 for(i=idx[q].low;i<=idx[q].high;i++)//顺序查找 { if(r[i].key==key) {n=i;break;} } return(n);//返回结果 } 五,交换左右子树 /*思路: 可以仿照前序遍历二叉树的方法来进行交换左右子树,注意当根节点交换后它后面的节点已经交换*/ //交换左右子树的程序代码 #include #include //二叉链表的结构类型定义 constintmaxsize=1024; typedefchardatatype; typedefstructnode { datatypedata; structnode*lchild,*rchild; }bitree; bitree*creattree(); voidpreorder(bitree*); bitree*swap(bitree*); voidmain() { intq; bitree*pb; pb=creattree(); preorder(pb); printf("\n"); swap(pb); preorder(pb); printf("\n"); scanf("%d",&q); } //二叉树的建立 bitree*creattree() { charch; bitree*Q[maxsize]; intfront,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf("按层次输入二叉树,虚结点输入'@',以'#'结束输入: \n"); while((ch=getchar())! ='#') { s=NULL; if(ch! ='@') { s=(bitree*)malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; elseQ[front]->rchild=s; if(rear%2==1)front++; } } returnroot; } //先序遍历按层次输出二叉树 voidpreorder(bitree*p) { if(p! =NULL) { printf("%c",p->data); if(p->lchild! =NULL||p->rchild! =NULL) { printf("("); preorder(p->lchild); if(p->rchild! =NULL)printf(","); preorder(p->rchild); printf(")"); } } } //添加交换左右子树算法 bitree*swap(bitree*p) { bitree*s;//设置s为工作节点 if(p! =NULL) { s=p->lchild;//一下三行实现左右节点的交换 p->lchild=p->rchild; p->rchild=s; swap(p->lchild);//交换左子树的子树 swap(p->rchild);//交换右子树的子树 } returnp;//返回根结点,交换完毕 } 六,马鞍点 /*思路;先逐行扫描,找出每一行的最小值并记录其位置信息,然后根据其列数找对应列的最大数,若列的最大数和行的最小数的位置信息一样就说明该位置对应的是马鞍点*/ //找马鞍点程序代码 #include #include //数组的结构类型定义 constintm=3; constintn=3; typedefstruct{ intA[m+1][n+1]; intmax[m+1],min[n+1]; }array; intminmax(array*); voidmain() { array*pa=(array*)malloc(sizeof(array)); inti,j; intq; for(i=0;i<=m;i++) for(j=0;j<=n;j++) scanf("%d",&pa->A[i][j]); minmax(pa); scanf("%d",&q); } //添加找马鞍点算法 intminmax(array*pa) { inti,j,x,a,r,c,b,d; c=0;d=0;r=0;b=0;x=0;a=0; intflag=0; for(i=0;i<=m;i++) { a=pa->A[i][0]; r=i;c=0; for(j=0;j<=n;j++) { if(a>pa->A[i][j]) { a=pa->A[i][j];//a里面是一行中的最小值 r=i;c=j;//r里面是行数,c里面是列数 } } //到此,一行中最小的数的资料在r和c中 b=pa->A[0][c]; for(x=0;x<=m;x++) { if(b { b=pa->A[x][c];//b里面是c列的最大值 d=x;//d里面是行号 } } if(a==b&&d==r) { printf("A[%d][%d]=%d是马鞍点\n",d,c,pa->A[d][c]); flag=1;break; } } if(flag==0) { printf("没有马鞍点\n"); return0; } return1; } 七,判断括号匹配 /*思路: 首先将表达式扫描一遍将左括号压入堆栈,完毕后在扫描一遍表达式,当遇到右括号时就将前面压入堆栈的左括号弹出堆栈与当前的右括号进行比较,匹配时就进行下一轮比较,不等时就结束比较,返回标志位*/ #include #include #include #include #definemaxsize1024 typedefstruct { inthuan[maxsize]; inttop; }seqstack; voidintseqstack(seqstack*p) {p->top=0;} intpush(seqstack*p,chara) { if(p->top==maxsize) { printf("toped! "); return0; } else { p->huan[++p->top]=a; return1; } } charpop(seqstack*p) { chara; if(p->top==0) { //printf("右括号多于左括号! "); p->top--; return(0); } else { a=p->huan[p->top--]; return(a); } } intmain() { seqstack*p; p=(seqstack*)malloc(sizeof(seqstack)); intseqstack(p); intj=1; inti=0; intn,flag=1;//flag是标示变量,起到标志作用 charaa[]="[2+(1-0)}]"; chara; while(aa[i]! =0) { if(aa[i]==')'||aa[i]=='}'||aa[i]==']')//加入刚开始就是右括号,标示不匹配,直接退出 {break;} if((aa[i]=='('||aa[i]=='{'||aa[i]=='['))//遇到左括号就压栈,以便在后面比较 {push(p,aa[i]);} i++; } if(aa[i]==0)//标示一直到最后也没有遇到左括号,直接退出 {printf("只有左括号! 不匹配! \n"); exit(0); } while(aa[i]! =0) { //遇到右括号时就弹出已经压栈的左括号与其比较,假若不相等就让标示位置0,然后退出即可,假若相等就继续比较 if(aa[i]==']'||aa[i]=='}'||aa[i]==')') {a=pop(p); } if(aa[i]=='(') { if(a! =')') {printf("no\n");flag=0;break;} } if(aa[i]=='[') { if(a! =']') {printf("no\n");flag=0;break;} } if(aa[i]=='{') { if(a! ='}') {printf("no\n");flag=0;break;} } i++; } //最后用标示位的数值来决定括号是否匹配 if(flag==1&&p->top==0) {printf("yes! \n");} else {printf("no! \n");}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 各种 算法