[原创]数据结构与算法基本程序合集

三、队及其操作
//All copyright are preserved bycobby
//链队列的建立

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define NULL 0

typedef struct node //队列结点的基本数据结构，即队列中每个结点的类型
{
char c;
struct node *next;
}qnode,*basic_node;

typedef struct //队列实际上由头、尾两个结点指针构成，即头指针和尾指针唯一确定时，队列也被唯一确定
{
qnode *head;
qnode *rear;
}queue,*Q;

main()
{
Q q; //定义队列，结构体变量q中含有头指针head和尾指针rear，所以q是一个完整的队列（只不过队列为空）
//事实上，任何由Q定义的结构体变量都是一个独立完整的队列
basic_node p,l; //basic_node是基本结点类型，即是独立的结点，它是组成队列的基本元素。
//基本结点p,l和队列q的关系可由下图表示：
// (q->head)--->p--->l--->p--->l--->……--->p--->l--->(q->rear)
char ch;

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; //l指向第一个元素
}
l->next=p; //使前一个元素指向当前入队的新元素
l=p; //l移动到当前新元素，以备用下次入队操作
q->rear=p; //修改队尾指针，使其总是指向当前最后一个队列元素
scanf("%c",&ch);
getchar();
}
l=q->head;
while(l!=NULL)
{
printf("%c<--",l->c);
l=l->next;
}
printf("\n");
printf("头指针指向元素为%c\t尾指针指向元素为%c\n",q->head->c,q->rear->c );
}

//All copyright are preserved bycobby

//入队和出队

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define NULL 0

typedef struct node //队列结点的基本数据结构，即队列中每个结点的类型
{
char c;
struct node *next;
}qnode,*basic_node;

typedef struct //队列实际上由头、尾两个结点指针构成，即头指针和尾指针唯一确定时，队列也被唯一确定
{
qnode *head;
qnode *rear;
}queue,*Q;

main()
{
Q q; //定义队列，结构体变量q中含有头指针head和尾指针rear，所以q是一个完整的队列（只不过队列为空）
//事实上，任何由Q定义的结构体变量都是一个独立完整的队列
basic_node p,l; //basic_node是基本结点类型，即是独立的结点，它是组成队列的基本元素。
//基本结点p,l和队列q的关系可由下图表示：
// (q->head)--->p--->l--->p--->l--->……--->p--->l--->(q->rear)
char ch;
int choice;

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; //l指向第一个元素
}
l->next=p; //使前一个元素指向当前入队的新元素
l=p; //l移动到当前新元素，以备用下次入队操作
q->rear=p; //修改队尾指针，使其总是指向当前最后一个队列元素
scanf("%c",&ch);
getchar();
}
l=q->head;
while(l!=NULL)
{
printf("%c<--",l->c);
l=l->next;
}
printf("\n");
printf("头指针指向元素为%c\t尾指针指向元素为%c\n",q->head->c,q->rear->c );

//以上建立了一个队列

printf("输入1进行入队，输入2进行出队:\n");
scanf("%d",&choice);
getchar();

if(choice==1)
{
printf("\n输入要入队的元素:\n");
scanf("%c",&ch);
getchar();
p=(qnode*)malloc(sizeof(qnode)); //给新入队的元素分配内存空间
p->c=ch;
p->next=NULL; //新元素为最后一个元素
q->rear->next=p; //原来最后一个元素指向新入队的元素
q->rear=p; //修改队尾指针，使其指向当前最后一个元素
}
else if(choice==2)
q->head=q->head->next;
else
exit(0);

l=q->head;
while(l!=NULL)
{
printf("%c<--",l->c);
l=l->next;
}
printf("\n");
printf("头指针指向元素为%c\t尾指针指向元素为%c\n",q->head->c,q->rear->c );
}

//All copyright are preserved bycobby
//循环队列建立

#include<stdio.h>
#include<malloc.h>
#define MAX 8

typedef struct
{
char c[MAX]; //循环队列是顺序队列的一种，它的核心就是一个数组
int front; //整形变量，作为头指针用
int rear; //整形变量，作为尾指针用
}queue;

main()
{
queue *q;
char ch;
int i;

q=(queue*)malloc(sizeof(queue)); //生成一个空循环队列
for(i=0;i<MAX;i++)
q->c[i]='\0';
q->front=0;
q->rear=0;

printf("输入要入队的元素:\n");
scanf("%c",&ch);
getchar();
while(ch!='!')
{
if((q->rear+1)%MAX==q->front) //若队列已满
{
printf("队列已满，无法入队\n");
break;
}
else
{
q->c[q->rear]=ch; //rear指向当前可入队的数组元素位置

q->rear=(q->rear+1)%MAX; //修改尾指针，向后移动一个位置
//注意，不能简单使用q->rear++，不然会导致队列溢出
}
scanf("%c",&ch);
getchar();
}

for(i=q->front;i<q->rear;i=(i+1)%MAX) //能够用for循环，说明了顺序队列和链式队列的区别
printf("%c<--",q->c[i]);
printf("\n");
}

//All copyright are preserved bycobby
//循环队列的入队和出队操作

#include<stdio.h>
#include<malloc.h>
#define MAX 8

typedef structd
{
char c[MAX]; //循环队列是顺序队列的一种，它的核心就是一个数组
int front; //整形变量，作为头指针用
int rear; //整形变量，作为尾指针用
}queue;

main()
{
queue *q;
char ch;
int i,choice;

q=(queue*)malloc(sizeof(queue)); //生成一个空循环队列
for(i=0;i<MAX;i++)
q->c[i]='\0';
q->front=0;
q->rear=0;

printf("输入要入队的元素:\n");
scanf("%c",&ch);
getchar();
while(ch!='!')
{
if((q->rear+1)%MAX==q->front) //若队列已满
{
printf("队列已满，无法入队\n");
break;
}
else
{
q->c[q->rear]=ch; //rear指向当前可入队的数组元素位置

q->rear=(q->rear+1)%MAX; //修改尾指针，向后移动一个位置
//注意，不能简单使用q->rear++，不然会导致队列溢出
}
scanf("%c",&ch);
getchar();
}

printf("头指针指向元素为%d\t尾指针指向元素为%d\n",q->front,q->rear);

for(i=q->front;i<q->rear;i=(i+1)%MAX) //能够用for循环，说明了顺序队列和链式队列的区别
printf("%c-->",q->c[i]);
printf("\n");

//以上建立了一个循环队列
printf("输入1入队，输入2出队:\n");
scanf("%d",&choice);
getchar();

while(choice==1||choice==2)
{
if(choice==1)
{
printf("输入要入队的元素\n");
scanf("%c",&ch);
getchar();
if((q->rear+1)%MAX==q->front) //若队列已满
{
printf("队列已满，无法入队\n");
break;
}
else
{
q->c[q->rear]=ch; //rear指向当前可入队的数组元素位置
q->rear=(q->rear+1)%MAX; //修改尾指针，向后移动一个位置
//注意，不能简单使用q->rear++，不然会导致队列溢出
}
}
else if(choice==2)
{
if((q->front+1)%MAX!=q->rear) //队非空
{
q->c[q->front]='\0'; //删除元素
q->front=(q->front+1)%MAX; //修改队头指针
}
else
{
printf("队已清空\n");
break;
}
}

if(q->rear>q->front) //尾指针在头指针的右边
{
for(i=q->front;i<q->rear;i=(i+1)%MAX) //能够用for循环，说明了顺序队列和链式队列的区别
printf("%c<--",q->c[i]);
printf("\n");
}
else //尾指针在头指针的左边
{
for(i=q->front;i<(q->rear+MAX);i++) //能够用for循环，说明了顺序队列和链式队列的区别
printf("%c<--",q->c[i%MAX]);
printf("\n");
}
printf("头指针指向元素为%d\t尾指针指向元素为%d\n",q->front,q->rear);

printf("输入1入队，输入2出队:\n");
scanf("%d",&choice);
getchar();
}
}

四、串及其操作
//串的朴素匹配

#include<stdio.h>

main()
{
char str1[100],str2[100],*p;
int i=0,j=0,len_str1=0,len_str2=0,num=0;
printf("输入母串:\n");
scanf("%s",str1);
getchar();

printf("%输入子串:\n");
scanf("%s",str2);
getchar();

p=str1;
while(*p!='\0') //获取母串长度
{
len_str1++;
p++;
}

p=str2; //获取子串长度
while(*p!='\0')
{
len_str2++;
p++;
}

for(i=0;i<len_str1;i++) //i为母串下标
{
for(j=0;j<len_str2;j++) //j为子串下标
{
num++;
if(str1[i+j]!=str2[j])
break; //若当前字符不匹配，则指针向母串下一个字符移动
}
if(j==len_str2)
{
printf("子串在母串中的位置为%d\n",i+1);
//break; //若子串在母串中多次出现，则全部找到其位置。若恢复break语句则只找出最前的一个匹配子串
}
}
printf("母串长度为%d,子串长度为%d\n核心语句执行次数为%d\n",len_str1,len_str2,num);
}

哈夫曼算法程序太大，一个贴放不下，下面两个贴均为哈夫曼编码程序.

//2005/4/28
//All Copyright Are Reserved By cobby
//哈夫曼编码

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define NULL 0

typedef struct huff_code_node //存储编码的链表
{
char ch; //编码对应的字符
char code[100]; //字符对应的哈夫曼码
struct huff_code_node *next;
}hnode,*huff;

typedef struct tree_Node //二叉树结点
{
char ch; //字符内容
int amount; //字符在字符串中出现的次数
struct tree_Node *left,*right; //指向左子树与右子树
}tnode,*bt;

typedef struct list_node //链表结点
{
char ch; //存储字符串中的字符
int amount; //字符在字符串中出现的次数
tnode *son; //链表结点带有二叉子树的根结点指针
struct list_node *next; //指向链表中下一个结点
}Node,*L;

typedef struct stack_node
{
char ch; //存储字符
int amount; //出现次数
bt son; //指向二叉树的某结点
struct stack_node *next;
}snode,*stack;

char t[200],*str,*c; //用于存储和处理输入的字符串
bt root=NULL; //哈夫曼树
L l,p,q,new_node; //链表结点
huff hlist; //计算得到的编码表
int char_num; //输入的不同字符数量
int char_amount; //输入的所有字符数量
int code_sum; //哈夫曼编码总长

void initial() //初始化操作
{
l=(Node*)malloc(sizeof(Node)); //建立空链表
l->ch='\0';
l->amount=0;
l->son=NULL;
l->next=NULL;

str=t; //将字符串指针指向字符串的第一个位置
//键盘输入字符串
printf("输入字符串进行哈夫曼编码:\n");
scanf("%s",str);
getchar();
}

void pull_in_list()
{
int exist; //表示当前字符是否存在于链表中，0为不存在，1为已存在
int n; //计算输入不同字符的数量，计算后赋值给全局变量char_num
int m; //计算输入所有字符的数量，计算后赋值给全局变量char_amount

c=str; //c指向第一个字符

while(*c!='\0') //若字符串未读完
{
exist=0;
p=l; //p指向链表头结点
//寻找该字符是否已经在链表中
while(p->next!=NULL) //若链表非空
{
p=p->next;
if(p->ch==*c) //若当前字符已经在链表中
{
exist=1;
p->amount++; //字符出现次数加1
break;
}
}

if(exist==0) //若当前字符不存在于链表中，则分配一个结点入表
{
new_node=(Node*)malloc(sizeof(Node));
new_node->ch=*c;
new_node->amount=1;
new_node->next=NULL;
new_node->son=NULL;
p->next=new_node;
p=new_node;
}
c++; //读下一个字符
}

printf("统计结果:\n");
p=l;
n=0;
m=0;
while(p->next!=NULL)
{
n++;
p=p->next;
m+=p->amount;
printf("%c——%d\n",p->ch,p->amount);
}
char_num=n;
char_amount=m;
printf("一共有%d种字符输入，字符总数%d\n",char_num,char_amount);
}

int list_element_amount() //计算链表中结点的数量（不包括头结点）
{
L temp; //定义临时指针
int n=0; //结点数量
temp=l;
while(temp->next!=NULL) //后面还有结点
{
n++;
temp=temp->next;
}
return n;
}

bt create() //建立最优二叉树
{
//=========================================
//这些变量用于寻找最小结点
L min1_pos,min2_pos,t,min_pri;
bt min1_son,min2_son;
int min1,min2;
char min1_c,min2_c;
//=========================================

//=========================================
//这些变量用于构造二叉子树
bt left,right,root;
//==========================================

//==========================================
//这些变量用于将二叉子树信息插入链表
L made,temp_p;
//============================================

while(list_element_amount()>=2) //若表中还有两个或以上结点，则归并继续
{
//选择次数值最小的两个结点

//============================================================================
//先寻找第一个小结点
t=l->next;
min1=t->amount; //将第一个结点的次数值赋给min1
min1_pos=t; //将第一个结点的位置指针赋给min1_pos
min1_c=t->ch; //将第一个结点的字符赋值给min1_c
min1_son=t->son; //将第一个结点的二叉指针赋值给min1_son
min_pri=l; //min_pri始终指向最小结点的前驱，以方便删除最小结点

while(t->next!=NULL)
{
t=t->next;
if(min1>t->amount) //发现更小的结点
{
min1=t->amount; //将当前结点的次数值赋给min1
min1_pos=t; //将当前结点的位置指针赋给min1_pos
min1_c=t->ch; //将当前结点的字符赋值给min1_c
min1_son=t->son; //将当前结点的二叉指针赋值给min1_son
}
}//退出本循环时，最小结点的信息找出，将该结点删除

min_pri=l;
while(min_pri->next!=min1_pos)
min_pri=min_pri->next;
//退出循环时min_pri指向min1_pos的前驱
min_pri->next=min1_pos->next; //删除结点min1_pos
//寻找第一个小结点完成
//=================================================================

//=================================================================
//先寻找第二个小结点
t=l->next;
min2=t->amount; //将第二个结点的次数值赋给min2
min2_pos=t; //将第二个结点的位置指针赋给min2_pos
min2_c=t->ch;
min2_son=t->son;
min_pri=l; //min_pri始终指向最小结点的前驱，以方便删除最小结点

while(t->next!=NULL)
{
t=t->next;
if(min2>t->amount) //发现更小的结点
{
min2=t->amount; //将当前结点的次数值赋给min2
min2_pos=t; //将当前结点的位置指针赋给min2_pos
min2_c=t->ch;
min2_son=t->son;
}
}//退出本循环时，最小结点的信息找出，将该结点删除

min_pri=l;
while(min_pri->next!=min2_pos)
min_pri=min_pri->next;
//退出循环时min_pri指向min1_pos的前驱
min_pri->next=min2_pos->next; //删除结点min2_pos
//寻找第二个小结点完成
//=================================================================

//==================================================================
//两个最小结点找到，由这对结点级成一个二叉子树，将根结点插入链表中
if(min1_son==NULL) //该结点无二叉子树指针，则须新分配一个二叉树结点
{
left=(bt)malloc(sizeof(tnode)); //产生左孩子
left->amount=min1; //次数值复制
left->ch=min1_c; //字符复制
left->left=NULL;
left->right=NULL;
}
else //该结点为计算产生的结点，它已指向一个二叉子树
left=min1_son; //left直接指向已经生成的二叉子树的根结点

if(min2_son==NULL) //该结点无二叉子树指针，则须新分配一个二叉树结点
{
right=(bt)malloc(sizeof(tnode)); //产生右孩子
right->amount=min2; //次数值复制
right->ch=min2_c; //字符复制
right->left=NULL;
right->right=NULL;
}
else
right=min2_son; //left直接指向已经生成的二叉子树的根结点

root=(bt)malloc(sizeof(tnode));
root->amount=min1+min2;
root->ch='\0'; //对于计算产生的树结点，字符均为空
root->left=left;
root->right=right;
//二叉子树完成

//生成一个对应上面已产生二叉子树地址的链表结点
made=(L)malloc(sizeof(Node));
made->amount=root->amount;
made->ch=root->ch;
made->next=NULL;
made->son=root;

//将生成的链表结点插入链表中
temp_p=l;
while(temp_p->next!=NULL)
temp_p=temp_p->next;
//退出循环时temp_p指向链表最后一个结点
temp_p->next=made; //将生成的结点插入链表
}

temp_p=l->next;
return temp_p->son;
}

void encoding() //根据建立的哈夫曼树编码
{
stack code,top,temp,readcode;
bt r;
huff temp_huff,hp;
char huff[100]=""; //用于存储当前字符的哈夫曼编码串
int i,j,n=0;

hlist=(hnode*)malloc(sizeof(hnode));
hlist->ch='\0';
for(i=0;i<100;i++)
hlist->code[i]='\0';
hlist->next=NULL;
hp=hlist;

//建立空栈
code=(stack)malloc(sizeof(snode));
code->amount=0;
code->ch='\0';
code->next=NULL;
code->son=NULL; //栈的头结点指向树的根结点
top=code;

r=root;
temp=(stack)malloc(sizeof(snode)); //给哈夫曼树的根结点分配栈结点
temp->amount=r->amount;
temp->ch='0';
temp->next=top;
temp->son=r;
top=temp;

while(r!=NULL) //当前结点存在
{
if(r->left!=NULL&&r->left->amount!=-1) //当前结点有左孩子
{
r=r->left; //r转向左孩子
r->amount=-1;

temp=(stack)malloc(sizeof(snode)); //给左孩子分配栈结点
temp->amount=r->amount;
temp->ch='0';
temp->next=top;
temp->son=r;
top=temp;
}
else if(r->right!=NULL&&r->right->amount!=-1) //当前结点有右孩子
{
r=r->right; //r转向右孩子
r->amount=-1;

temp=(stack)malloc(sizeof(snode)); //给右孩子分配栈结点
temp->amount=r->amount;
temp->ch='1';
temp->next=top;
temp->son=r;
top=temp;
}
else //无未访问的孩子结点
{

if(r->left==NULL&&r->right==NULL) //当前结点为叶子结点
{
for(i=0;i<100;i++) //对哈夫曼编码数组初始化
huff[i]='\0';

//先输出该叶子结点的编码
printf("字符%c,编码为:",r->ch);
readcode=top;
i=0;

while(readcode!=code)
{
huff[i++]=readcode->ch; //将栈元素倒置入哈夫曼编码数组中
readcode=readcode->next;
}

temp_huff=(hnode*)malloc(sizeof(hnode)); //为当前字符及其编码创建结点
temp_huff->ch=r->ch; //存储编码的原字符
for(j=0;j<100;j++) //初始化编码串数组
temp_huff->code[j]='\0';

j=0;

for(i=i-2;i>=0;i--) //依次读出哈夫曼编码数组中的编码串
{
printf("%c",huff[i]);
temp_huff->code[j++]=huff[i];
}
temp_huff->next=NULL;
hp->next=temp_huff;
hp=temp_huff;

printf("\t\t");
if(++n%2==0)
printf("\n");
}

if(top->next!=code) //若栈非空
{
top=top->next;
r=top->son;
}
else
break;
}
}
}

六、排序
/* 冒泡排序 */

#include<stdlib.h>
#include<stdio.h>

main()
{
int i,j,temp,a[30000];
long TIME=0;
rand();

for(i=0;i<30000;i++)
{
a[i]=rand();
printf("%d\t",a[i]);
}

for(i=29999;i>=0;i--)
for(j=0;j<=i;j++)
if(a[j+1]<a[j])
{
TIME++;
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}

for(i=0;i<=29999;i++)
printf("%d\t",a[i]);
printf("\n%d\n",TIME);
}

/* 直接选择排序法 */

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
//#include<time.h>

main()
{
int i,j,value,pos,temp,a[30000];
long TIME=0;

rand();
for(i=0;i<30000;i++) /* make up the rand numbers*/
{
a[i]=rand();
printf("%d\t",a[i]);
}

for(i=0;i<30000;i++) /* sort */
{
value=a[i];
pos=i;
for(j=i+1;j<30000;j++)
{
TIME++;
if(value>a[j])
{
value=a[j];
pos=j;
}
}
temp=a[i];
a[i]=a[pos];
a[pos]=temp;
}
for(i=0;i<30000;i++)
printf("%d\t",a[i]);
printf("\n\n%ld\n",TIME);
}

好东西。顶～～～

以来是老师，有礼了！

好东西,顶下

真的啊.
老师你的意思是说sizeof(node)==sizeof(node*)
是这样的吗?

#include <stdio.h>

#define NULL 0 /*宏定义*/

typedef struct node /*定义结点类型的数据结构*/
{
char c; /*数据域，类型为字符型*/
struct node *next; /*指针域，类型为本结构体类型*/
}*L; /*类型重定义，即Node和*L和struct node等价*/

int main()
{
printf("%d\n",sizeof(L));
printf("%d\n",sizeof(struct node));
return 0;
}

[此贴子已经被作者于2007-10-27 22:02:31编辑过]