帮忙看一下两个程序时间复杂度
第一个#include<stdio.h>
#include<malloc.h>
typedef struct lnode//单链表结点类型
{
int data;
struct lnode *next;
}list,*linklist;
void initList(linklist &l)//单链表初始化
{
char c;
linklist p;
l=(linklist)malloc(sizeof(list));
l->next=0;
while((c=getchar())!='\n')
{
p=(linklist)malloc(sizeof(list));//新建结点p插入l
p->data=c-48;
p->next=l->next;
l->next=p;
}
}
void traverselist(linklist l)//单链表遍历并输出
{
l=l->next;
while(l!=0)
{
printf("%d",l->data);
l=l->next;
}
}
void add(linklist &l,linklist l1,linklist l2)//单链表相加
{
int a,b=0;
linklist p;
l1=l1->next;
l2=l2->next;
l=(linklist)malloc(sizeof(list));
l->next=0;
while(l1!=0&&l2!=0)//相同数位上均不为零
{
a=l1->data+l2->data+b;
l1=l1->next;
l2=l2->next;
b=a/10;
a=a%10;
p=(linklist)malloc(sizeof(list));
p->data=a;
p->next=l->next;
l->next=p;
}
if(!l1&&!l2)//两个相加结点均为空
{
if(b==1)
{
p=(linklist)malloc(sizeof(list));
p->data=1;
p->next=l->next;
l->next=p;
}
}
if(l1)//l1存在，l2为空
{
while(l1!=0)
{
a=l1->data+b;
l1=l1->next;
b=a/10;
a=a%10;
p=(linklist)malloc(sizeof(list));
p->data=a;
p->next=l->next;
l->next=p;
}
if(b==1)
{
p=(linklist)malloc(sizeof(list));
p->data=1;
p->next=l->next;
l->next=p;
}
}
if(l2)//l2存在，l1为空
{
while(l2!=0)
{
a=l2->data+b;
l2=l2->next;
b=a/10;
a=a%10;
p=(linklist)malloc(sizeof(list));
p->data=a;
p->next=l->next;
l->next=p;
}
if(b==1)
{
p=(linklist)malloc(sizeof(list));
p->data=1;
p->next=l->next;
l->next=p;
}
}
}
void main()//主函数
{
linklist l1,l2,l3;
printf("请输入第一个整数：\n");
initList(l1);
printf("请输入第二个整数：\n");
initList(l2);
printf("两个整数的和是：\n");
add(l3,l1,l2);
traverselist(l3);
printf("\n");
}
第二个
#include <stdio.h>
#include <stdlib.h> //整数变成字符型
#include <string.h> //字符串操作
#define NULL 0
#define ERROR -1
#define STACKSIZE 20 //栈长
//站的定义
typedef struct
{
char stackname[20];
char *base;
char *top;
}Stack;
//变量声明
Stack OPTR, OPND; //定义运算符栈和操作数栈
char expr[255] = ""; //定义字符串
char *ptr = expr;
//栈的初始化
int InitStack(Stack *s, char *name)
{
s->base=(char *)malloc(STACKSIZE*sizeof(char)); //为栈底分配空间
if(!s->base) exit (ERROR); //分配失败
strcpy(s->stackname, name); //字符串拷贝
s->top=s->base; //空栈
return 1;
}
//In
int In(char ch)
{
return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');
}
//入栈
int Push(Stack *s,char ch)
{
char *name = s->stackname;
if(strcmp(name, "OPND") == 0)
printf("\tPUSH(%s, %d)", name, ch);
else
printf("\tPUSH(%s, %c)", name, ch);
*s->top=ch;
s->top++;
return 0;
}
//出栈
char Pop(Stack *s)
{
char p;
printf("\tPOP(%s)", s->stackname);
s->top--;
p=*s->top;
return (p);
}
//取栈顶
char GetTop(Stack s)
{
char p=*(s.top-1);
return (p);
}
//判定运算符栈的栈顶运算符和输入运算符之间的优先级
char Precede(char c1,char c2)
{
int i=0,j=0;
static char array[49]={
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', '!',
'>', '>', '>', '>', '!', '>', '>',
'<', '<', '<', '<', '<', '!', '='};
switch(c1)
{
//i为下面array的横标
case '+' : i=0;break;
case '-' : i=1;break;
case '*' : i=2;break;
case '/' : i=3;break;
case '(' : i=4;break;
case ')' : i=5;break;
case '#' : i=6;break;
}
switch(c2)
{
//j为下面array的纵标
case '+' : j=0;break;
case '-' : j=1;break;
case '*' : j=2;break;
case '/' : j=3;break;
case '(' : j=4;break;
case ')' : j=5;break;
case '#' : j=6;break;
}
return (array[7*i+j]); //返回运算符
}
//进行二元运算a op b，op为运算符集合
int Operate(int a,char op,int b)
{
printf("\tOPERATE(%d, %c, %d)", a, op, b);
switch(op)
{
case '+' : return (a+b);
case '-' : return (a-b);
case '*' : return (a*b);
case '/' : return (a/b);
}
}
//表达式的计算（算符优先法）
int EvalExpr( )
{
char c,theta,x,m,ch;
int a,b;
c = *ptr++;
while(c!='#'||GetTop(OPTR)!='#')
{
if(!In(c)) //不是运算符，则进操作数栈
{
m=atoi(&c);
Push(&OPND,m);
c = *ptr++;
}
else
switch(Precede(GetTop(OPTR),c))
{
case '<': //栈顶元素优先权低
Push(&OPTR,c);
c = *ptr++;
break;
case '=': //托括号并接受下一字符
x=Pop(&OPTR);
c = *ptr++;
break;
case '>': //退栈并将运算结果入站
theta=Pop(&OPTR);
b=Pop(&OPND); a=Pop(&OPND);
Push(&OPND,Operate(a,theta,b));
break;
}
}
return GetTop(OPND); //返回操作数栈的栈顶元素
}
//主函数
main( )
{
printf("Input the expression(end with \"#\" sign):");
do
{
gets(expr);
}
while(!*expr); //do...while...循环 读取输入数据
InitStack(&OPTR, "OPTR"); //初始化运算符栈
Push(&OPTR,'#'); //首先将"#"入站
InitStack(&OPND, "OPND"); //初始化操作数栈
printf("\n\nresult:%d\n", EvalExpr());
return;
}
这么长
