程序 文本文档
顺序表
#include
#include
#include
#define MAXSIZE 100
typedef int Elemtp;//数据类型的重命名
typedef struct//顺序表的结构体
{
Elemtp elem[MAXSIZE];
int len;
int last;
}SeqList;
void Init(SeqList *L)//初始化函数
{
L->len=0;
L->last=-1;
}
void Input(SeqList *L)//输入函数
{
int i,n;
printf("\n请输入元素个数：");
scanf("%d",&n);
L->len=n;//元素个数赋值给表长度
printf("\n请输入%d个元素：",n);
printf("\n");
for(i=1;i<=L->len;i++)//循环输入数据
/////////////
哈弗曼数
#include
#include
#include
#define N 20
#define M 2*N-1
typedef struct
{
int weight;
int parent;
int LChild;
int RChild;
}HTNode,HuffmanTree[M+1];
typedef char * HuffmanCode[N+1];
/*
int CountWeight(char *ch,int *w,char *save)
{
int i,j=0,t[N];
for(i=0;i
t[ch[i]%97]++;
printf("%d ",ch[i]);
}
for(i=0;i <26;i++)
{
if(t[i]!=0)
{
w[j]=t[i];
ch[j]=i+97;
j++;
}
}
return j;
}
*/
int Input(char *ch,int *w)
{
int i=1;
printf("请输入字符和对应的权值:\n");
for(scanf(" %c,%d",&ch[i],&w[i]);w[i]!=0;scanf(" %c%d",&ch[i],&w[i]))
{
i++;
}
return i-1;
}
void select(HuffmanTree ht,int i,int *s1,int *s2)
{
int j;
int t1,t2;
*s1=0;
*s2=0;
t1=1000;
t2=1000;
for(j=0;j
if(ht[j].parent==0)//没父亲的节点.可以用于构造树
{
if(ht[j].weight
t1=ht[j].weight;
if(ht[*s1].parent==0)
{
*s2=*s1; //如果s1有更小的.那么前一个s1就是次小的
t2=ht[*s1].weight;
}
*s1=j;
}
if(ht[i].weight
t2=ht[*s1].weight;
*s2=j;
}
}
}
}
/*
void select(HuffmanTree ht,int i,int *s1,int *s2)
{
int j,num;
for(j=1;j <=i-1;j++)
{
if(ht[j].parent==0&&ht[j].weight <*s1)
{
*s1=ht[j].weight;
num=j;
}
}
for(j=1;j <=i-1;j++)
{
if(ht[j].parent==0&&ht[j].weight <*s1&&j!=num)
*s2=ht[j].weight;
}
}
*/
/*
void select(HuffmanTree ht,int i,int *s1,int *s2)
{
int j;
int t1,t2;
*s1=0;
*s2=0;
t1=1000;
t2=999;//临时辅助量用于比较
for(j=0;j
if(ht[j].parent==0)
if(ht[j].weight <*s2)
if(ht[j].weight <*s1)
{
t2=t1;
t1=ht[j].weight;
*s2=*s1;
*s1=j;
}
else
{
t2=ht[j].weight;
*s2=j;
}
}
}
*/
void CreateHuffmanTree(HuffmanTree ht,int *w,int n)
{
int i;
int s1,s2;
int m;
m=2*n-1;
for(i=1;i <=n;i++)
{
ht[i]
.weight=w[i];
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i <=m;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i <=m;i++)
{
select(ht,i-1,&s1,&s2);
ht[i].weight=ht[s1].weight+ht[s2].weight;
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].LChild=s1;
ht[i].RChild=s2;
printf("#%d %d %d#\n",i,s1,s2);
}
}
void CreateHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n)
{
int i,start,c,p;
char * cd;
cd=(char *)malloc((n+1)*sizeof(char));
cd[n-1]='\0';
for(i=1;i <=n;i++)
{
start=n-1;
c=i;
p=ht[i].parent;
while(p!=0)
{
--start;
if(ht[i].LChild==c)
cd[start]='0';
else
cd[start]='1';
c=p;
ht[p].parent;
}
hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],&cd[start]);
}
free(cd);
}
void PrintCode(HuffmanTree ht,HuffmanCode hc,int n,char *ch)
{
int i;
for(i=1;i
printf("%c",ch[i]);
puts(hc[i]);
printf("\n");
}
}
void Print(char *ch,int *w)
{
int i=1;
while(w[i]!=0)
{
printf("%c %d",ch[i],w[i]);
i++;
}
}
void PrintHu(HuffmanTree ht,int n)
{
int i;
for(i=1;i <=2*n-1;i++)
printf("%d %d %d %d\n",ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
}
int main()
{
HuffmanTree hf;
HuffmanCode hc;
char ch[N];
int w[N],n;
//int c,count;
n=Input(ch,w);
Print(ch,w);
printf("\n");
CreateHuffmanTree(hf,w,n);
PrintHu(hf,n);
printf("\n");
PrintCode(hf,hc,n,ch);
return 0;
//Input(&c);
//count=CountWeight(c,w,ch);
//Output(ch,w,count);
}
{
scanf("%d",&L->elem[i]);
}
return;//返回空
}
void Output(SeqList L)//输出函数
{
int i;
printf("\n执行操作后的元素是：");
for(i=1;i<=L.len;i++)
{
printf("%4d",L.elem[i]);
}
}
int length(SeqList L)//求表的长度
{
return(L.len);
}
int GetData(SeqList L,int i)//得到某位的数据
{
if(i>0&&i<=L.len)
return(L.elem[i]);
return(-10000);//当没有找到这位的数据时，返回一个虚元素
}
int Insert(SeqList *L,Elemtp x,int i)//在i位的前面插入一个数
{
int j;
if(i<1||i>L->len)
{
printf("\n插入的位置不合法！失败！");
return 0;
}
if(L->len==MAXSIZE-1)
{
printf("\n表溢出！失败！");
return 0;
}
for(j=L->len;j>=i;j--)
{
L->elem[j+1]=L->elem[j];
}
L->elem[i]=x;
L->len++;//计算表的长度
return 1;
}
int Delete1(SeqList *L,int i)//删除第i位的元素
{
int j;
if(i<1||i>L->len)
{
printf("删除位置不合法！失败！");
return 0;
}
for(j=i;j<=L->len;j++)
{
L->elem[j]=L->elem[j+1];
}
L->len--;//改变表的长度
return(1);
}
int Locate(SeqList L,Elemtp x)//确定某个数的位置
{
int i=1;
while(i<=L.len
&&L.elem[i]!=x)
i++;
if(i<=L.len)
return i;
return 0;
}
int Delete2(SeqList *L,Elemtp x)//删除某个元素
{
int i;
i=Locate(*L,x);//查找这个元素的位置，调用查找函数
if(i>0)
{
Delete1(L,i);//调用删除1函数
return 1;
}
else printf("无此元素！失败！");
return 0;
}
int marge(SeqList LA,SeqList LB,SeqList *LC)//归并函数
{
int i,j,k;
if(LA.len+LB.len>=MAXSIZE)
{
printf("\n下标超界！失败！");
return 0;
}
i=1;j=1;k=1;
while(i<=LA.len&&j<=LB.len)//但i、j的值都小于各自的长度时，将小的数先赋值给Lc
{
if(LA.elem[i]
LC->elem[k]=LA.elem[i];
i++;
k++;
}
else
{
LC->elem[k]=LB.elem[j];
j++;
k++;
}
}
while(i<=LA.len)//将剩余La的数据赋值给Lc
{
LC->elem[k]=LA.elem[i];
i++;
k++;
}
while(j<=LB.len)//将剩余Lb的数据赋值给Lc
{
LC->elem[k]=LB.elem[j];
j++;
k++;
}
LC->len=LA.len+LB.len;//计算长度
return 1;
}
void main()
{
int ch,c,d,i,x,t;
SeqList LA,LB,LC;
do//列菜单
{
puts("\n按任意键执行清屏，进行其他的操作！");
getch();
system("cls");//清屏
printf("\n 0 退出程序！");
printf("\n 1 初始化");
printf("\n 2 输入数据");
printf("\n 3 求表长度");
printf("\n 4 查找某位数据");
printf("\n 5 插入");
printf("\n 6 删除某位数据");
printf("\n 7 删除某个元素");
printf("\n 8 查找");
printf("\n 9 归并");
printf("\n 10 输出");
puts("\n请输入你的选择：");
scanf("%d",&ch);
switch(ch)//多分支选择
{
case 0:exit(1);//正常退出
case 1:Init(&LA);break;
case 2:Input(&LA);break;
case 3:c=length(LA);
printf("该表的长度是%d",c);break;
case 4:printf("\n请输入位置：");
scanf("%d",&i);
d=GetData(LA,i);
printf("第%d位的数据是:%d",i,d);break;
case 5:printf("\n请输入位置：");
scanf("%d",&i);
printf("\n请输入元素：");
scanf("%d",&x);
if(Insert(&LA,x,i)>0)
{
printf("\n插入成功！");
Output(LA);
}
else printf("插入失败！");break;
case 6:printf("\n请输入位置：");
scanf("%d",&i);
if(Delete1(&LA,i)>0)
{
printf("删除成功！");
Output(LA);
}
else printf("删除失败！");break;
case 7:printf("\n请输入元素：");
scanf("%d",&x);
if(Delete2(&LA,x)>0)
{
printf("删除成功！");
Output(LA);
}
else
printf("删除失败！");break;
case 8:printf("\n请输入要查找的元素：");
scanf("%d",&x);
t=Locate(LA,x);
if(t>0)
printf("此元素在第%d位上",t);
else printf("没有此元素！");break;
case 9:printf("输入顺序表LA中的元素：");
Input(&LA);
printf("\n输入顺序表LB中的元素：");
Input(&LB);
if(marge(LA,LB,&LC)>0)
{
printf("归并成功！");
Output(LC);
}
else printf("归并失败！");break;
case 10:Output(LA);break;
default:puts("选择错误！");
}
}
while(ch!=0);
}
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
、、
如果有如下定义：
typedef int ElemType ;
typedef struct node
{
ElemType data;
struct node *next;
}Node, *LinkList;
编写算法实现如下操作：链表的初始化、链表的创建（头部插入法、尾部插入法）、求表长、查找（按值查找、按序号查找）、插入、删除、输出、两个有序单链表的合并等。
编写程序验证所写算法的正确性。
创建菜单，实现对各种操作的选择。
#include
#include
#include
#include
#define NULL 0
typedef int Elemtp;
typedef struct Node
{
Elemtp Date;
struct Node *next;
}Node, *LinkList;
void sort(LinkList L)
{
LinkList p,q,s;
int temp;
for(p=L->next;p->next!=NULL;p=p->next)
{
s=p;
for(q=p->next;q;q=q->next)
{
if(q->Date
{
s=q;
}
}
if(s!=p)
{
temp=p->Date;
p->Date=s->Date;
s->Date=temp;
}
}
}
void Init(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));
(*L)->next=NULL;
}
LinkList create(int n)
{
LinkList h,r,p;
int x,i;
h=(Node*)malloc(sizeof(Node));
r=h;
printf("输入数字:\n");
for(i=1;i<=n;i++)
{
scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->Date=x;
r->next=p;
r=p;
}
r->next=NULL;
return h;
}
void GetDate(LinkList L,int i)
{
LinkList p;
int j=1;
p=L->next;
while(p!=NULL&&j
j++;
p=p->next;
}
if(!p||j>i)
printf("位置不合法！");
else
printf("%d",p->Date);
}
void Output(LinkList L)
{
LinkList p;
p=L->next;
while(p!=NULL)
{
printf("\n%d ",p->Date);
p=p->next;
}
}
int InsList(LinkList *L,int i,Elemtp x)
{
LinkList p=(*L);
int j=0;
while(p&&j
p=p->next;
j++;
}
if(!p||j>i-1)
{
printf("插入位置不合法！");
}
LinkList q;
q=(LinkList)malloc(sizeof(Node));
q->Date=x;
q->next=p->next;
p->next=q;
return 1;
}
int Locate(LinkList L,Elemtp x)
{
int i=1;
LinkList p;
p=L->next;
while(p&&p->Date!=x)
{
p=p->next;i++;
}
if(p==NULL)
return NULL;
return i;
}
int Delete(LinkList *L,int i)
{
LinkList q,p;int j;
if(i==1)
{
p=(*L);
(*L)=(*L)->next;
free(p);
return 1;
}
q=(*L);j=0;
while(q->next&&j
j++;
q=q->next;
}
if(q==NULL&&j>i-1)
{
printf("删除位置不合法！");
return 0;
}
p=q->next;
q->next=p->next;
free(p);
return 1;
}
int Delete1(LinkList*L,Elemtp x)
{
LinkList q,p;
if((*L)->Date==x)
{
p=(*L);
(*L)=(*L)->next;
free(p);
return 1;
}
p=(*L);q=(*L);
while(p&&p->Date!=x)
{
q=p;
p=p->next;
}
if(p==NULL)
{
printf("元素不存在!");
return 0;
}
q->next=p->next;
free(p);
return 1;
}
LinkList merge(LinkList LA,LinkList LB)
{
LinkList LC;
LinkList q,p,r;
q=LA->next;
p=LB->next;
LC=LA;
LC->next=NULL;r=LC;
while(q!=NULL&&p!=NULL)
{
if(q->Date<=p->Date
)
{
r->next=q;r=q;q=q->next;
}
else
{
r->next=p;r=p;p=p->next;
}
}
if(q)
{
r->next=q;
}
else
{
r->next=p;
}
free(LB);
return(LC);
}
void main()
{
LinkList LA,LB;
int i;Elemtp x;char ch,m;
while(ch!=0)
{
getch();
system("cls");
puts("请选择:");
puts("\n");
puts("0退出");
puts("1输入");
puts("2查找");
puts("3删除");
puts("4输出");
puts("5读取");
puts("6插入");
puts("7排序");
puts("8合并");
printf("请输入功能代码:");
scanf("%c",&ch);
switch(ch)
{
case '0': puts("\n");
return;
case '1': printf("输入数字的个数(n):\n");
scanf("%d",&i);
LA=create(i);break;
case '2':
printf("请输入你要查找的元素：");
scanf("%d",&x);
if(Locate(LA,x)!=NULL)
printf("查找成功，%d在%d号位置！",x,Locate(LA,x));
else
printf("无此元素，查找失败！");
break;
case '3':
puts("\n");
puts("0序号");
puts("1元素");
printf("请选择:");
scanf("%c",&m);
m=getch();
if(m=='0')
{
printf("请输入序号：");
scanf("%d",&i);
Delete(&LA,i);
Output(LA);
}
if(m=='1')
{
printf("请输入元素：");
scanf("%d",&x);
if(Delete1(&LA,x)!=0)
printf("%d删除成功！",x);
Output(LA);
}
break;
case '4':Output(LA);break;
case '5':
printf("请输入元素序号：");
scanf("%d",&i);
GetDate(LA,i);
break;
case '6':
printf("请输入所插入的位置：");
scanf("%d",&i);
printf("请输入所插入的元素：");
scanf("%d",&x);
InsList(&LA,i,x);
Output(LA);break;
case '7':
sort(LA);
Output(LA);
break;
case '8':
printf("请输入表1的数据：");
printf("输入数字的个数(n):\n");
scanf("%d",&i);
LA=create(i);sort(LA);
printf("请输入表2的数据：");
printf("输入数字的个数(n):\n");
scanf("%d",&i);
LB=create(i);sort(LB);
Output(merge(LA,LB));
break;
default:puts("\n输入错了，请重新选择！");
}
}
}
写一个算法，实现从十进制数（包括整数和实数）到任何进制数的转换（二进制、八进制、十六进制）。
#include
#define Max 20
typedef int Elemtp;
typedef struct //栈的定义
{
Elemtp Data[Max];
int top;
}Stack;
Stack s,*p;
void Init(Stack *s)//初始化
{
s->top==0;
}
int Push(Stack *s,Elemtp x)//进栈
{
if(s->top==Max-1)
{
printf("\n栈溢出！进栈
操作失败！");
return 0;
}
s->top++;
s->Data[s->top]=x;
return 1;
}
Elemtp Pop(Stack *s)//出栈
{
Elemtp x;
if(s->top==0)
return('\0');
x=s->Data[s->top];
s->top--;
return x;
}
int change(float r,int t)//转换
{
int p,b,i,c,x1,x2,t1;
int a[Max];
Stack s;
float q,t2;
p=(int)r;
Init(&s);
do
{
x1=p%t;
t1=(p-x1)/t;
c=Push(&s,x1);
}
while(t1!=0&&c>0);
while(Pop(&s))
{
a[i]=Pop(&s);
i++;
}
b=i;
a[b]='.';
q=r-p;
do
{
x2=(int)(q*t);
t2=q*t-x2;
a[b+1]=x2;
b++;
}
while(t2);
a[b]='\0';
return a[0];
}
void main()
{
Stack s;
float r;
int a[Max]={0},a1[Max],a2[Max],a3[Max];
printf("\n请输入一个十进制数\n");
scanf("%f",&r);
printf("\n输入的十进制数是：%f",r);
*a1=change(r,2);
printf("\n转换后的二进制是：%d",a1);
*a2=change(r,8);
printf("\n转换后的八进制是：%d",a2);
*a3=change(r,16);
printf("\n转换后的十六进制是：%d",a3);
}
查找相关资料，根据教材81页的算法思想，编写算法实现一个中缀表达式的求值
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
char ops[7]={'+','-','*','/','(',')','#'}; /*运算符数组*/
int cmp[7][7]={{2,2,1,1,1,2,2}, /*用来进行比较运算符优先级的矩阵,3代表'=',2代表'>',1代表'<',0代表不可比*/
{2,2,1,1,1,2,2},
{2,2,2,2,1,2,2},
{2,2,2,2,1,2,2},
{1,1,1,1,1,3,0},
{2,2,2,2,0,2,2},
{1,1,1,1,1,0,3}};
typedef struct
{
char elem[Stack_Size];
int top;
}SeqStack; /*运算符栈的定义*/
typedef struct
{
int elem[Stack_Size];
int top;
}nSeqStack; /* 运算数栈的定义*/
void InitStack(SeqStack *S) /*初始化运算符栈*/
{
S->top =-1;
}
void InitStackn(nSeqStack *S) /*初始化运算数栈*/
{
S->top =-1;
}
int IsEmptyn(nSeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
{
return(S->top==-1?TRUE:FALSE);
}
/*判栈满*/
int IsFull(SeqStack *S) /*判断栈S为满栈时返回值为真，反之为假*/
{
return(S->top==Stack_Size-1?TRUE:FALSE);
}
int IsFulln(nSeqStack *S) /*判断栈S为满栈时返回值为真，反之为假*/
{
return(S->top==Stack_Size-1?TRUE:FALSE);
}
int Push(SeqStack
*S, char x) /*运算符栈入栈函数*/
{
if (S->top==Stack_Size-1)
{
printf("Stack is full!\n");
return FALSE;
}
else
{
S->top++;
S->elem[S->top]=x;
return TRUE;
}
}
int Pushn(nSeqStack *S, int x) /*运算数栈入栈函数*/
{
if (S->top==Stack_Size-1)
{
printf("Stack is full!\n");
return FALSE;
}
else
{
S->top++;
S->elem[S->top]=x;
return TRUE;
}
}
int Pop(SeqStack *S, char *x) /*运算符栈出栈函数*/
{
if (S->top==-1)
{
printf("运算符栈空!\n");
return FALSE;
}
else
{
*x=S->elem[S->top];
S->top--;
return TRUE;
}
}
int Popn(nSeqStack *S, int *x) /*运算数栈出栈函数*/
{
if (S->top==-1)
{
printf("运算符栈空!\n");
return FALSE;
}
else
{
*x=S->elem[S->top];
S->top--;
return TRUE;
}
}
char GetTop(SeqStack *S) /*运算符栈取栈顶元素函数*/
{
if (S->top ==-1)
{
printf("运算符栈为空!\n");
return FALSE;
}
else
{
return (S->elem[S->top]);
}
}
int GetTopn(nSeqStack *S) /*运算数栈取栈顶元素函数*/
{
if (S->top ==-1)
{
printf("运算符栈为空!\n");
return FALSE;
}
else
{
return (S->elem[S->top]);
}
}
int Isoperator(char ch) /*判断输入字符是否为运算符函数,是返回TRUE,不是返回FALSE*/
{
int i;
for (i=0;i<7;i++)
{
if(ch==ops[i])
return TRUE;
}
return FALSE;
}
char Compare(char ch1, char ch2) /*比较运算符优先级函数*/
{
int i,m,n;
char pri;
int priority;
for(i=0;i<7;i++) /*找到相比较的两个运算符在比较矩阵里的相对位置*/
{
if(ch1==ops[i])
m=i;
if (ch2==ops[i])
n=i;
}
priority = cmp[m][n];
switch(priority)
{
case 1:
pri='<';
break;
case 2:
pri='>';
break;
case 3:
pri='=';
break;
case 0:
pri='$';
printf("表达式错误!\n");
break;
}
return pri;
}
int Execute(int a, char op, int b) /*运算函数*/
{
int result;
switch(op)
{
case '+':
result=a+b;
break;
case '-':
result=a-b;
break;
case '*':
result=a*b;
break;
case '/':
result=a/b;
break;
}
return result;
}
int ExpEvaluation()
/*读入一个简单算术表达式并计算其值。optr和operand分别为运算符栈和运算数栈，OPS为运算符集合*/
{
int a,b,v,temp;
char ch,op;
char *str;
int i=0;
SeqStack optr;
nSeqStack operand;
InitStack(&optr);
InitStackn(&operand);
Push(&optr,'#');
printf("请输入表达式(以#结束):\n"); /*表达式输入*/
str =(char *)malloc(50*sizeof(char));
gets(str);
ch=str[i];
i++;
while(ch!='#'||GetTop(&optr)!='#')
{
if(!Isoperator(ch))
{
temp=ch-'0'; /*将字符转换为十进制数*/
ch=str[i];
i++;
while(!Isoperator(ch))
{
temp=temp*10 + ch-'0'; /*将逐个读入运算数的各位转化为十进制数*/
ch=str[i];
i++;
}
Pushn(&operand,temp);
}
else
{
switch(Compare(GetTop(&optr),ch))
{
case '<':
Push(&optr,ch);
ch=str[i];
i++;
break;
case '=':
Pop(&optr,&op);
ch=str[i];
i++;
break;
case
'>':
Pop(&optr,&op);
Popn(&operand,&b);
Popn(&operand,&a);
v=Execute(a,op,b); /* 对a和b进行op运算 */
Pushn(&operand,v);
break;
}
}
}
v=GetTopn(&operand);
return v;
}
void main() /*主函数*/
{
int result;
result=ExpEvaluation();
printf("\n表达式结果是%d\n",result);
}
定义顺序栈如下：
#define Stack_Size 50
typedef struct
{
StackElemType elem[Stack_Size];
int top;
}SeqStack;
编写程序实现一个顺序栈S的初始化、进栈、出栈、取栈顶元素。
利用栈的基本操作实现十进制数a转换为二进制数的过程。
#include
#include
#define Stack_Size 100
typedef int StackElemType;
typedef struct
{
StackElemType elem[Stack_Size];
int top;
}SeqStack;
//初始化一个栈
void InitStack(SeqStack *S)
{
S->top =-1;
}
//清空一个栈
void ClearStack(SeqStack *S)
{
S->top =-1;
}
//入栈
int Push(SeqStack *S,StackElemType x)
{
if(S->top ==Stack_Size-1)
{
puts("栈满，无法入栈!");
return 0;
}
S->top ++;
S->elem[S->top]=x;
return 1;
}
//出栈
int Pop(SeqStack *S ,StackElemType *x)
{
if(S->top ==-1)
{
puts("栈空，无法出栈!");
return 0;
}
*x=S->elem[S->top];
S->top--;
return 1;
}
//取栈顶元素
int GetTop(SeqStack S ,StackElemType *x)
{
if(S.top ==-1)
{
printf("栈空，无法出栈!");
return 0;
}
*x=S.elem[S.top];
return 1;
}
//判空
int IsEmpty(SeqStack S)
{
if(S.top ==-1)
return 1;
else
return 0;
}
//输出栈
void Output(SeqStack S)
{
int i;
for(i=0;i<=S.top;i++)
printf("%5d",S.elem[i]);
printf("\n");
}
//十进制转换为二进制
void transform1(long num)
{
SeqStack S; ;
int k,w;
InitStack(&S);
while(num!=0)
{
k=num%2;
Push(&S,k);
num=num/2;
}
while(!IsEmpty(S))
{
Pop(&S,&w);
printf("%d",w);
}
printf("\n");
}
//十进制转换为十六进制
void transform2(long num)
{
SeqStack S; ;
int k,w;
InitStack(&S);
while(num!=0)
{
k=num%16;
Push(&S,k);
num=num/16;
}
while(!IsEmpty(S))
{
Pop(&S,&w);
printf("%d",w);
}
printf("\n");
}
void main()
{
SeqStack S1;
StackElemType e,m;
int i;
InitStack (&S1);
printf("输入入栈的8个元素并入栈\n");
for(i=0;i<8;i++)
{
scanf("%d",&e);
Push(&S1,e);
}
printf("输出栈中的元素");
Output(S1);
printf("让栈中的3个元素出栈\n");
Pop(&S1,&m);
printf("出栈元素为%d\n",m);
Pop(&S1,&m);
printf("出栈元素为%d\n",m);
Pop(&S1,&m);
printf("出栈元素为%d\n",m);
Output(S1);
int x;
printf("请输入要转换为二进制和十六进制的整数：");
scanf("%d",&x);
printf("十进制%d转换为二进制后是：",x);
transform1(x);
printf("转换成功！\n");
printf("十进制%d转换为十六进制后是：",x);
transform2(x);
printf("转
换成功！\n");
}
定义定长顺序存储的串类型如下：
#define MAXLEN 30
typedef struct
{
char ch[MAXLEN]；
int len;
}SString;
编写程序实现如下算法：
串的初始化、串的赋值、串的输出。
1）利用上面的算法实现对两个串S="abcdabcacad",T="bcac"的赋值操作，并输出。
2）编程实现BF算法（教材P112页算法4.10），并用上面的两个串进行验证。
# include
# include
# include
# define TRUE 1
# define FALSE 0
# define MAXLEN 30
//定义顺序串
typedef struct
{
char ch[MAXLEN];
int len;
}SString;
//字符串的初始化
void InitStrLen(SString *s)
{
s->len=-1;
}
//字符串的赋值
void StrAsign(SString *s,char str[])
{
int i=0;
while(str[i]!='\0')
{
s->ch[i]=str[i];
i++;
}
s->len=i;
}
//字符串的输出
void StrOut(SString s)
{
int i=0;
if(s.len==0)
{
printf("串中元素为: ");
return;
}
while(i<=s.len-1)
{
putchar(s.ch[i]);
i++;
}
printf("\n");
}
//顺序串的简单模式匹配函数
int StrIndex(SString s,int pos,SString t)
{
int i,j,start;
//模式串为空串时时，任意串的匹配串
if(t.len==0) return 0;
//主串从pos开始，模式串从头开始
start=pos;i=start;j=0;
while(i
//当前对应字符相等时推进
if(s.ch[i]==t.ch[j]){i++;j++;}
else
{
start++; //当前对应字符不等时回溯
i=start; //主串从start开始，模式串从头开始
j=0;
}
//匹配成功时，返回成功起始位置，否则返回-1
if(j>=t.len) return start;
else return -1;
}
void main()
{
SString s;
char str[MAXLEN];
InitStrLen(&s);
printf("\n请输入字符串:");
gets(str);
StrAsign(&s,str);
StrOut(s);
}
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
根据教材P131页稀疏矩阵的三元组表类型的定义，实现算法5.2 稀疏矩阵“列序”递增转置算法。
# include
# include
# include
# define TRUE 1
# define FALSE 0
# define MAXLEN 30
//定义顺序串
typedef struct
{
char ch[MAXLEN];
int len;
}SString;
//字符串的初始化
void InitStrLen(SString *s)
{
s->len=-1;
}
//字符串的赋值
void StrAsign(SString *s,char str[])
{
int i=0;
while(str[i]!='\0')
{
s->ch[i]=str[i];
i++;
}
s->len=i;
}
//字符串的输出
void StrOut(SString s)
{
int i=0;
if(s.len==0)
{
printf("串中元素为: ");
return;
}
while(i<=s.len-1)
{
putchar(s.ch[i]);
i++;
}
printf("\n");
}
//顺序串的简单模式匹配函数
int StrIndex(SString s,int pos,SString t)
{
int i,j,start;
//模式串为空串时时，任意串的匹配串
if(t.len==0) return 0;
//主串从pos开始，模式串从头开始
start=pos;i=start;j=0;
while(i
//当前对应字符相等时推进
if(s.ch[i]==t.ch[j]){i++;j++;}
else
{
start++; //当前对应字符不等时回溯
i=start; //主串从start开始，模式串从头开始
j=0;
}
//匹配成功时，返回成功起始位置，否则返回-1
if(j>=t.len) return start;
else return -1;
}
void main()
{
SString s;
char str[MAXLEN];
InitStrLen(&s);
printf("\n请输入字符串:");
gets(str);
StrAsign(&s,str);
StrOut(s);
}
崔化雪 16:05:08
# include
# define MAXSIZE 100
typedef int ElementType;
typedef struct
{
int row,col;
ElementType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE +1];
int m,n,len;
}TSMatrix;
void ASSign(TSMatrix *A)
{
int i;
printf("输入该稀疏矩阵的行数、列数和非零元的个数\n");
scanf("%d,%d,%d",&A->m,&A->n,&A->len);
puts("依次输入非零元的行标、列标和非零元数值，以逗号分隔:");
for(i=1;i<=A->len;i++)
{
scanf("%d,%d,%d",&A->data[i].row,&A->data[i].col,&A->data[i].e);
}
}
void Output(TSMatrix A)
{
int i;
printf("\n");
for(i=1;i
printf("%5d%5d%5d\n",A.data[i].row,A.data[i].col,A.data[i].e);
}
}
void TransposeTSMatrix(TSMatrix A,TSMatrix *B)
{
int i,j,k;
B->m=A.n;B->n=A.m;B->len=A.len;
if(B->len>0)
{
j=1;
for(k=1;k<=A.n;k++)
for(i=1;i<=A.len;i++)
if(A.data[i].col==k)
{
B->data[j].row=A.data[i].col;
B->data[j].col=A.data[i].row;
B->data[j].e=A.data[i].e;
j++;
}
}
}
void main()
{
TSMatrix A,B;
ASSign(&A);
Output(A);
TransposeTSMatrix(A,&B);
Output(B);
}
、、、、、、、、、、、、、、、、、、、、
如果二叉树采用二叉链表的方式存储，其结点定义为：
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BiTNode,*BiTree;
请实现如下算法：
1）创建一棵二叉树；
2）分别对该二叉树进行先序遍历、中序遍历和后序遍历，输出遍历结果
3）分别设计算法，计算所创建的二叉树的高度、叶子
结点个数和结点个数。
#include
#include
#define M 20
#define len sizeof(BiTNode)
typedef char DataType;
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BiTNode,*BiTree;
BiTNode *create()
{
BiTNode *BiTree;
char ch;
scanf("%c",&ch);
if(ch=='#')
BiTree=NULL;
else
{
BiTree=(BiTNode*)malloc(len);
BiTree->data=ch;
BiTree->lchild=create();
BiTree->rchild=create();
}
return BiTree;
}
void Preorder(BiTNode *BiTree)
{
int i=0;
BiTNode *s[M];
do
{
while(BiTree!=NULL)
{
printf("%3c",BiTree->data);
if(BiTree->rchild!=NULL)
s[i++]=BiTree->rchild;
BiTree=BiTree->lchild;
}
if(i>0)
BiTree=s[--i];
}while(i>0||BiTree!=NULL);
}
void Inorder(BiTNode *BiTree)
{
int i=0;
BiTNode *s[M];
do
{
while(BiTree!=NULL)
{
s[i++]=BiTree;
BiTree=BiTree->lchild;
}
if(i>0)
{
BiTree=s[--i];
printf("%3c",BiTree->data);
BiTree=BiTree->rchild;
}
}while(i>0||BiTree!=NULL);
}
void Postorder(BiTNode *BiTree)
{
int s1[M];
int i=0;
BiTNode *s[M];
do
{
while(BiTree!=NULL)
{
s[i]=BiTree;
s1[i++]=0;
BiTree=BiTree->lchild;
}
while(i>0&&s1[i-1]==1)
{
BiTree=s[--i];
printf("%3c",BiTree->data);
free(BiTree);
}
if(i>0)
{
s1[i-1]=1;
BiTree=s[i-1];
BiTree=BiTree->rchild;
}
}while(i>0);
}
int high(BiTNode *BiTree)
{
int h,lh,rh;
if(!BiTree)
return 0;
lh=high(BiTree->lchild);
rh=high(BiTree->rchild);
h=lh>rh?lh+1:rh+1;
return h;
}
int leafcount(BiTNode *BiTree,int n)
{
if(BiTree)
{
if(BiTree->lchild==NULL&&BiTree->rchild==NULL)
n++;
n=leafcount(BiTree->lchild,n);
n=leafcount(BiTree->rchild,n);
}
return n;
}
void main()
{
BiTNode *BiTree;
int n=0;
printf("输入数据源：");
BiTree=create();
printf("Preorder: ");
Preorder(BiTree);
printf("\n Inorder: ");
Inorder(BiTree);
printf("\n 叶子数为：");
n=leafcount(BiTree,0);
printf("%d",n);
printf("\n 树的深度为：");
n=high(BiTree);
printf("%d",n);
printf("\n Postorder: ");
Postorder(BiTree);
printf("\n");
}