数据结构与算法基本程序

数据结构与算法基本程序目录

、线性表及其操作

1、尾插法建立一个单链表，并按顺序输出

2、单链表的元素查找，按内容查找

3、元素插入操作

4、按内容元素删除操作

5、按位置删除元素

6、建立双向链表

7、单链表就地逆置

8、约瑟夫环问题

--、栈及其操作

1、建立堆栈

2、进栈与出栈

3、栈的应用，括号匹配

、队及其操作

1、链队列的建立

2、入队和出队

3、循环队列建立

4、循环队列的入队和出队操作

四、串及其操作

1、串的朴素匹配

五、树（二叉树）及其操作

1、二叉排序树

2、哈夫曼编码

六、排序

1、冒泡排序

2、直接选择排序法

一、线性表及其操作

//Allcopyrightarepreservedbycobby

/*尾插法建立一个单链表，并按顺序输出*/

SdefineNULL0/*宏定义*/

typedefstructnode/*定义结点类型的数据结构*/

t

charc;/*数据域，类型为字符型*/

structnode*next;/*指针域，类型为本结构体类型*/

}*L;/*类型重定义，即Node和*L和structnode等

价*/

main()

L1,p,q;/*用指针类型定义三个结点类型的指针*/

charch;

1=(L)malloc(sizeof(L));/*分配内存空间*/

l->c=，\0);/*为头结点的数据域赋值，值为

空*/

l->next=NULL;/*指明下一个结点目前不存

在*/

q=l；/*q为游动指针，链表结点的

连结要用*/

printf("Inputacharacter:\n/z);

scanf("*c”,&ch);

getchar();//此语句用来吸收键盘输入的回车符，没

有其它含义

while(ch!=，!")/*输入!表示输入结束*/

{

p=(L)malloc(sizeof(L));/*为新输入的数据分配内

存空间*/

p->c=ch;

p->next=NULL;/*新输入的结点在

链表的最后，即它的后面没有其它元素*/

q->next=p;/*q用于将上一个元

素链接至当前新元素*/

q=p;/*q自己移到当前

最后一个元素，以备继续链接所用*/

scanf("%c”,&ch);

getchar();

)

q=l；/*输入整个链表前，先将q

移到链表头，1一般不动*/

while(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

{

printf(，?%c->”,q->next->c);/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

)

)

//Allcopyrightarepreservedbycobby

/*单链表的元素查找，按内容查找*/

#defineNULL0/*宏定义*/

typedefstructnode/*定义结点类型的数据结构*/

{

charc;/*数据域，类型为字符型*/

structnode*next;/*指针域，类型为本结构体类型*/

}*L;/*类型重定义，即Node和*L和structnode等

价*/

main()

{

Ll,p,q;/*用指针类型定义三个结点类型的指针*/

charch;

intn;

1=(L)malloc(sizeof(L));/*分配内存空间*/

l->c=，\0';/*为头结点的数据域赋值，值为

空*/

l->next=NULL;/*指明下一个结点目前不存

在*/

q=i;/*q为游动指针，链表结点的

连结要用*/

printf(Z/Inputacharacter:\n/z);

scanf(“*c”,&ch);

getchar();

while(ch!-!")/*输入!表示输入结束*/

{

p=(L)malloc(sizeof(L));/*为新输入的数据分配内

存空间*/

p->c=ch;

p->next=NULL;/*新输入的结点在

链表的最后，即它的后面没有其它元素*/

q->next=p;/*q用于将上一个元

素链接至当前新元素*/

q=p;/*q自己移到当前

最后一个元素，以备继续链接所用*/

scanf&ch);

getchar();

)

q=l；/*输入整个链表前，先将q

移到链表头，1一般不动*/

while(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

printf(zz%c->”,q->next->c);/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

/*-------以上为建立一个单链表-------------*/

printf("\nlnputacharacteryouwannafind\n");

scanf&ch);

printf("\nthecharacteryouwannafindis%c\nzz,ch);

q=l->next;/*q移至头结点的后一个元素，即实际第

一个数据点*/

n=l;//位置计数器

while(q!=NULL)/*若q不为空，即该结点存在*/

(

if(q-〉c==ch)/*字符匹配*/

printf("'characterfoundinposition%d\n',n);

q=q->next;/*移至下一个元素继续查找*/

n++;

)

//Allcopyrightarepreservedbycobby

/*元素插入操作*/

#defineNULL0/*宏定义*/

typedefstructnode/*定义结点类型的数据结构*/

{

charc;/*数据域，类型为字符型*/

structnode*next;/*指针域，类型为本结构体类型*/

}Node,*L;/*类型重定义，即Node和*L和struct

node等价*/

main()

{

Ll,p,q;/*用指针类型定义三个结点类型的指针*/

charch;

intpos,n;

1=(L)malloc(sizeof(Node));/*分配内存空间*/

l->c=，\0';/*为头结点的数据域赋值，值为

空*/

l->next=NULL;/*指明下一个结点目前不存

在*/

q=l；/*q为游动指针，链表结点的

连结要用*/

printfC?Inputacharacter:\n/，);

scanf("枇",&ch);

getchar();

while(ch!=，!")/*输入!表示输入结束*/

(

p=(L)malloc(sizeof(Node));/*为新输入的数据分

配内存空间*/

p->c=ch;

p->next=NULL;/*新输入的结点在

链表的最后，即它的后面没有其它元素*/

q->next=p;/*q用于将上一个元

素链接至当前新元素*/

q=p;/*q自己移到当前

最后一个元素，以备继续链接所用*/

scanf&ch);

getchar();

)

q=l;/*输入整个链表前，先将q

移到链表头，1一般不动*/

while(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

{

printf(//%c->”,q->next->c);/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

)

/*以上为建立一个单链表*/

printf(Z/Inputthecharacteranditsposition,suchass,3\n\n");

scanf(z/%c,%d，z,&ch,&pos);

q=l;

n=l;

while(n!=pos&&q->next!=NULL)/*未找到插入位置，

且后面还有元素*/

{

q=q->next;

n++;

)

/*退出循环后，要么找到插入位置，要么表已到最后，输入的插入位置

过大*/

if(n<pos)/*表已读完，仍未找到插入位置*/

printf(/z\n\nincorrectposition,insertfailed\n\n");

else/*找到插入位置*/

/*将进行插入操作*/

p=(L)malloc(sizeof(Node));/*给新输入的数据分

配内存空间*/

p->c=ch;

p->next=q->next;

q->next=p;

}

/*操作完成，然后输出新表*/

q=l；/*输入整个链表前，先将q

移到链表头，1一般不动*/

while(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

{

printf(/"%c->”,q->next->c);/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

//Allcopyrightarepreservedbycobby

/*按内容元素删除操作*/

#include<malloc.h>

#include<stdio.h>

SdefineNULL0/*宏定义*/

typedefstructnode/*定义结点类型的数据结构*/

{charc;/*数据域，类型为字符型*/

structnode*next;/*指针域，类型为本结构体类型*/

}Node,*L;/*类型重定义，即Node和*L和struct

node等价*/

main()

{

Ll.p.q;/*用指针类型定义三个结点类型的指针*/

charch;

intn;

1=(L)malloc(sizeof(Node));/*分配内存空间*/

『>c='\0';/*为头结点的数据域赋值，值为

空*/

1一〉next二NULL;/*指明下一个结点目前不存

在*/

q=l;/*q为游动指针，链表结点的

连结要用*/

printf("Inputacharacter:\nz，);

scanf&ch);

getchar();

while(ch!=，!")/*输入!表示输入结束*/

{

p=(L)malloc(sizeof(Node));/*为新输入的数据分

配内存空间*/

p->c=ch;

p->next=NULL;/*新输入的结点在

链表的最后，即它的后面没有其它元素*/

q->next=p;/*q用于将上一个元

素链接至当前新元素*/

q=p;/*q自己移到当前

最后一个元素，以备继续链接所用*/

scanf("枇"，&ch);

getchar();

)

q=l；/*输入整个链表前，先将q

移到链表头，1一般不动*/

while(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

printf(/"%c->”,q->next->c);/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

/*以上为建立单链表*/

printf("inputthecharacteryouwannadelete\n\n");

scanf&ch);

printf(/?theelementyouwannadeleteis%c\n\nz，,ch);

q=l->next;

P=l；

n=l;

while(q!=NULL&&q->c!=ch)

P=q；

q=q->next;

n++;

/*退出循环时可能找到指定元素，也可能表读完，需要进一步判断*/

if(q==NULL)

printf("elementnotfound,deletefailed\n\n");

else

p->next=q->next;

q=l->next;/*输入整个链表前，先

将q移到链表头，1一般不动*/

while(q!=NULL)/*若q所指向的元素后面还有其它

元素，则将该元素的数据输出*/

(

printf(z/%c->”,q->c);/*q->next-〉c表示q所指向

的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

)

//Al1copyrightarepreservedbycobby

/*按位置删除元素*/

SdefineNULL0/*宏定义*/

typedefstructnode/*定义结点类型的数据结构*/

(

charc;/*数据域，类型为字符型*/

structnode*next;/*指针域，类型为本结构体类型*/

}Node,*L;/*类型重定义，即Node和*L和struct

node等价*/

main()

{

Ll.p,q;/*用指针类型定义三个结点类型的指针*/

charch;

intpos,n;

1=(L)malloc(sizeof(Node));/*分配内存空间*/

『>c='\0';/*为头结点的数据域赋值，值为

空*/

l->next=NULL;/*指明下一个结点目前不存

在*/

q=l；/*q为游动指针，链表结点的

连结要用*/

printfC?Inputacharacter:\n/，);

scanf("枇",&ch);

getchar();

while(ch!=，!")/*输入!表示输入结束*/

(

p=(L)malloc(sizeof(Node));/*为新输入的数据分

配内存空间*/

p->c=ch;

p->next=NULL;/*新输入的结点在

链表的最后，即它的后面没有其它元素*/

q->next=p;/*q用于将上一个元

素链接至当前新元素*/

q=p;/*q自己移到当前

最后一个元素，以备继续链接所用*/

scanf&ch);

getchar();

)

q=l;/*输入整个链表前，先将q

移到链表头，1一般不动*/

while(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

printf(z/%c->”,q->next->c);/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

)

/*以上为建立单链表*/

printf("Inputtheposition'll");

scanf&pos);

p=l；

n=l;

while(p->next!=NULL&&n!=pos)

(

p=p->next;

n++;

)

/*退出循环后，可能找到删除的元素位置，可能表读完，需要进一步判

断*/

if(n==pos)/*删除位置找到，删除该位置上的元素*/

p->next=p->next->next;

//free(p);

else

printf(""incorrectposition,deletefailed'rT);

q=l；/*输入整个链表前，先将q

移到链表头，1一般不动*/

whi1e(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

{

printfC%c->”,q->next->c);/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

〃建立双向链表

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#defineNULL0

typedefstructdlnode

(

charch;

structdlnode*pri,*next;

}dnode,*dl;

main()

{

dl1,p,q；

charc;

1=(dl)malloc(sizeof(dnode));

l->ch=\0';

l->next=NULL;

l->pri=NULL;

q=l;

printf("输入字符建立双向链表\n");

scanf&c);

getchar();

while(c!=，)

p=(dl)malloc(sizeof(dnode));

p->ch=c;

p->pri=q;

p->next=NULL;

q->next=p;

q=p;

scanf(〃%c〃,&c);

getchar();

}

q=i;

while(q->next!=NULL)

(

q=q->next;

printf(z/%c->〃，q->ch);

printf(〃\n〃)；

while(q->pri!=NULL)

(

printf(zz%c-->〃,q->ch);

q=q->pri;

)

printf(〃\n〃)；

/单链表就地逆置

ttdefineNULL0/*宏定义*/

typedefstructnode/*定义结点类型的数据结构*/

(

charc;/*数据域，类型为字符型*/

structnode*next;/*指针域，类型为本结构体类型*/

}Node,*L;/*类型重定义，即Node和*L和struct

node等价*/

main()

(

Ll,p,q,r;/*用指针类型定义三个结点类型的指针

*/

charch;

1=(L)malloc(sizeof(Node));/*分配内存空间*/

1->■'\0';/*为头结点的数据域赋值，值为

空*/

l->next=NULL;/*指明下一个结点目前不存

在*/

q=l；/*q为游动指针，链表结点的

连结要用*/

printf("Inputacharacter:\n，z);

scanf&ch);

getchar();

while(ch!=，!!)/*输入!表示输入结束*/

{

p=(L)malloc(sizeof(Node));/*为新输入的数据分

配内存空间*/

p->c=ch;

p->next=NULL;/*新输入的结点在

链表的最后，即它的后面没有其它元素*/

q->next=p;/*q用于将上一个元

素链接至当前新元素*/

q=p;/*q自己移到当前

最后一个元素，以备继续链接所用*/

scanf&ch);

getchar();

)

q=i;/*输入整个链表前，先将q

移到链表头，1一般不动*/

while(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

(

printf(//%c-q->next->c)：/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

printf("\n");

〃以上完成了单链表的创建

q=l->next;

p=q->next;

r=p->next;

q->next=NULL;

while(r!=NULL)

{

p->next=q;

q=p;

P=r;

if(r->next!=NULL)〃「后面还有结点，则逆置继续

r=r->next;

else

break;

)

r->next=q;

l->next=r;〃头结点指向最后一个结点

q=l；/*输入整个链表前，先将q

移到链表头，1一般不动*/

while(q->next!=NULL)/*若q所指向的元素后面还

有其它元素，则将该元素的数据输出*/

(

printfC%c->”,q->next->c);/*q->next->c表示q

所指向的下一个元素的数据*/

q=q->next;/*完成该元素的输出

后，q移至下一个元素重复输出操作*/

)

printf("\n");

)

〃约瑟夫环问题

#include<stdio.h>

#include<malloc.h>

typedefstructInode

{

intnum;

structInode*next;

}node,*L;

main()

{

intamount,start,circle,n,c;

Lp,1,q；

printf("一共有几个人围成一圈？\n");

scanf("%d”,&amount);

getchar();

printf(〃从第几个开始计数？\n〃)；

scanf(“%d”,&start);

getchar();

printf("每几人一次循环？\n");

scanf(z，%d/z,&circle);

getchar();

1=(L)malloc(sizeof(node));〃头结点

1->next=NULL;

l->num=0;

q二l；

n=0;

while(n++<amount)

(

p=(L)malloc(sizeof(node));

p->next=NULL;

p->num=n;

q->next=p;

q=P；

)

q->next=l->next;〃形成循环链表

〃以上完成了单向循环链表的建立

p=l->next;

q=l；

n=l;

while(n++<start)

(

p=p->next;

q=q->next;

)

〃退出循环时p,q分别位于指定位置

〃接下去进行周期性结点删除，直到链表只余一个结点为止

n=l;//n计算被删除的结点的数量，当n=amount-l

时删除结束

while(n++<amount)

{

c=l;//c作为循环临时变量

while(c++<circle)

(

p=p->next;

q=q->next;

)

〃删除当前p指向的结点

printf(〃删除结点%d\t〃，p->num);

q->next=p->next;

p=p->next;

printf(z，\n最后剩下%d\n〃,p->num);

)

二、栈及其操作

//Allcopyrightarepreservedbycobby

/*建立堆栈*/

#include<stdio.h>

#include<malloc.h>

ttdefineNULL0

typedefstructnode

(

charch;

structnode*next;

}Snode,*stack;

mainO

(

stacks,top,p;

charch;

s=(stack)malloc(sizeof(Snode));

s->ch=，\0,;

s->next=NULL;/*建立栈底指针*/

top=s;

scanf(〃%c〃,&ch);

getchar();

while(ch!=，)

(

p=(stack)malloc(sizeof(Snode));

p->ch=ch;

p->next=top;

top=p;

scanf(〃%c〃，&ch);

getchar();

)

while(top->next!=NULL)

(

printf(z，%c->〃，top->ch);

top=top->next;

printf(〃\n〃)；

//Allcopyrightarepreservedbycobby

/*进栈与出栈*/

#include<stdio.h>

#include<malloc.h>

SdefineNULL0

typedefstructnode

(

charch;

structnode*next;

}Snode,*stack;

main()

(

stacks,top,p;

charch;

intchoice;

s=(stack)malloc(sizeof(Snode));

s->ch=，!);

s->next=NULL;/*建立栈底指针*/

top=s;

scanf(〃%c〃,&ch);

getchar();

while(ch!=，!5)

(

p=(stack)malloc(sizeof(Snode));

p->ch=ch;

p->next=top;

top=p;

scanf(〃%c〃，&ch);

getchar();

)

while(p->next!=NULL)〃此处p可用top代替

(

printf(z，%c->”,p->ch);

p=p->next;

printf("\n");

/*以上建立了一个堆栈*/

printf(“进栈或出栈？输入“1”为进栈，输入“2”为出栈，其它则退

出程序\n〃);

scanffechoice);

getchar();

while(choice==l||choice==2)〃若不是输入1或2,则不做

任何操作

{

if(choice==l)

{

/*进栈*/

printf("\n输入要入栈的元素\n");

scanf&ch);

getchar();

p=(stack)malloc(sizeof(Snode));

p->ch=ch;

p->next=top;

top=p;

)

elseif(choice==2)

{

if(top->next!=NULL)

top=top->next;

else

(

printf("栈已清空\n");

exit();

)

/*出栈*/

)

//printf(/z%c—top->ch);

p=top;

while(p->next!=NULL)

(

printf(z/%c―p->ch);

p=p->next;

)

printf(〃\n");

printf("进栈或出栈？输入'T为进栈，输入“2”为出栈,

其它则退出程序\n〃);

scanf(〃％d〃,&choice);

getchar();

)

)

//Allcopyrightarepreservedbycobby

〃栈的应用，括号匹配

#include<stdio.h>

#include<malloc.h>

ttdefineNULL0

typedefstructnode

{

charch;

structnode*next;

}snode,*stack;

main()

(

stacks,top,p;

char"string,ch[100]=〃〃；

s=(stack)malloc(sizeof(snode));〃建立栈底元素

s->ch=，\0J;

s->next=NULL;

top=s;

printf(〃输入一个含括号的四则运算表达式：\n〃)；

scanf(〃%s〃,ch);

string=ch;

while(*string!=，\0')

(

if("string=二'('||*string==，[，||"string=二'{，)/

/遇到左括号，入栈

{

p=(stack)malloc(sizeof(snode));

p->ch=*string;

p->next=top;

top=p;

)

else

if(*string二二')'||"string二二'||*string=二'}')〃遇到右括号

if(*string==，),)

if(top-〉ch=='(')〃括号匹配

top=top->next;

else

(

printf(〃小括号不匹配”)；

exit(0);

)

elseif(*string==，]')

if(top-〉ch=='[')〃括号匹配

top=top->next;

else

{

printf("中括号不匹配”)；

exit(0);

)

else

if(top->ch=={")〃括号匹配

top=top->next;

else

(

printf(“大括号不匹配”)；

exit(0);

)

)

string++;

)

if(top->ch!=,\0")

printf("多出左括号为c\n”,top->ch);

三、队及其操作

//Allcopyrightarepreservedbycobby

〃链队列的建立

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#defineNULL0

typedefstructnode〃队列结点的基本数据结构,

即队列中每个结点的类型

charc;

structnode*next;

}qnode,*basic_node;

typedefstruct〃队列实际上由头、尾两个结点指针

构成，即头指针和尾指针唯一确定时，队列也被唯一确定

qnode*head;

qnode*rear;

}queue,*Q;

main()

Qq；〃定义队列，结构体变量q中含有头指针head和尾指针

rear,所以q是一个完整的队列(只不过队列为空)

〃事实上，任何由Q定义的结构体变量都是一个独立

完整的队列

basic_nodep,1;//basic_node是基本结点类型，即

是独立的结点，―它是组成队列的基本元素。

〃基本结点P,1和队列Q的关系可由下图表示：

//(q->head)--->p--->1--->p--->1--->....>p--->1--->(q->

rear)

charch;

q=(Q)malloc(sizeof(queue));

q->head=NULL;〃初始化时队列为空

q->rear=NULL;

printf(〃输入队列元素:\n〃)；

scanf("%c〃，&ch);

getchar();

while(ch!=，!?)

(

p=(qnode*)malloc(sizeof(qnode));

p->c=ch;

p->next=NULL;〃新来的元素一定在队列的

最后，它的后面没有其它元素

if(q->head==NULL)

q->head=p;〃第一个元素入队时,

队头指针指向它

l=q->head;//I指向第一个元素

l->next=p;〃使前一个元素指向

当前入队的新元素

1=P；//I移动到当前新

元素，以备用下次入队操作

q->rear=p;//修改队尾指针，使其

总是指向当前最后一个队列元素

scanf("%c”,&ch);

getchar();

)

l=q->head;

while(1!=NULL)

{

printf(z/%c<一”,l->c);

l=l->next;

)

printf("\n");

printf("头指针指向元素为枇\t尾指针指向元素

为%c\n”,q->head->c,q->rear->c);

//Allcopyrightarepreservedbycobby

〃入队和出队

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#defineNULL0

typedefstructnode〃队列结点的基本数据结构，

即队列中每个结点的类型

{

charc;

structnode*next;

}qnode,*basic_node;

typedefstruct〃队列实际上由头、尾两个结点指针

构成，即头指针和尾指针唯一确定时，队列也被唯一确定

{

qnode*head;

qnode*rear;

}queue,*Q;

main()

Qq；〃定义队列，结构体变量q中含有头指针head和尾指针

rear,所以q是一个完整的队列(只不过队列为空)

〃事实上，任何由Q定义的结构体变量都是一个独立

完整的队列

basic_nodep,1;//basic_node是基本结点类型，即

是独立的结点，它是组成队列的基本元素。

〃基本结点P,1和队列Q的关系可由下图表示：

//(q->head)--->p--->1--->p--->1--->....>p--->1--->(q->

rear)

charch;

intchoice;

q=(Q)malloc(sizeof(queue));

q->head=NULL;〃初始化时队列为空

q->rear=NULL;

printf("输入队列元素:\n");

scanf&ch);

getchar();

while(ch!=，!")

(

p=(qnode*)malloc(sizeof(qnode));

p->c=ch;

p->next=NULL;〃新来的元素一定在队列的

最后，它的后面没有其它元素

if(q->head==NULL)

{

q->head=p;〃第一个元素入队时，

队头指针指向它

l=q->head;//I指向第一个元素

)

l->next=p;