共有回帖数 0 个
-
//线性表的基本操作
//编译环境:vc++6.0
#includeiostream
using namespace std; #define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2 typedef int Status; //定义新的数据类型
typedef int ElemType;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList; //结构体 Status InitList_Sq(SqList &L) //分配空间
{ L.elem=new ElemType[LIST_INIT_SIZE];
if(!L.elem)exit(OVERFLOW); //分配空间失败
L.length =0;
L.listsize=LIST_INIT_SIZE;
return OK;
} Status ListInsert(SqList &L,int i,ElemType e) //插入新元素
{ int *q,*p;ElemType *newbase;
if(i1 || iL.length+1) return ERROR;
if(L.length=L.listsize)
{ newbase=new ElemType[L.listsize+LISTINCREMENT];
if(!newbase) exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for (p=&(L.elem[L.length-1]);p=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
return OK;
} Status ListDelete_Sq(SqList &L,int i,ElemType &e) //删除线性表第i个元素
{ ElemType *p, *q;
if(i1 || iL.length) return ERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p=q;++p) *(p-1)=*p;
--L.length;
return OK;
} Status Listlength(SqList L) //求线性表的长度
{ int *p=L.elem; //判断线形表是否存在
while(p)
{ return (L.length); }
} Status GetElem(SqList L, int i,ElemType &e) //取线性表的元素
{ if(i1 || iL.length)
return ERROR;
else
{ e=L.elem[i-1];
return e;
}
} void MergeList(SqList La,SqList Lb,SqList &Lc) //合并两个线性表
{ ElemType ai,bj;
InitList_Sq(Lc);
int i=1,j=1,k=0;
int La_len,Lb_len;
La_len=Listlength(La);
Lb_len=Listlength(Lb);
while((i=La_len)&&(j=Lb_len))
{ GetElem(La,i,ai);GetElem(Lb,j,bj);
if(ai=bj)
{ ListInsert(Lc,++k,ai);++i; }
else
{ ListInsert(Lc,++k,bj);++j; }
}
while(i=La_len)
{ GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
}
while(j=Lb_len)
{ GetElem(Lb,j++,bj);
ListInsert(Lc,++k,bj);
}
} void create(SqList &L,int n) //输入线性表的元素
{ int e;
for(int i=0;in;i++)
{ cine;
L.elem=e;
L.length=i+1; }
} void show(SqList L,int i) //显示线性表的元素
{ int j;ElemType k;
cout"线性表显示如下:"endl;
for(j=0;ji-1;j++)
{ k=L.elem[j];
coutk" "; }
if(j==i-1 && i0)
{ k=L.elem[j]; coutk; }
coutendl;
}
int main() //主菜单
{ SqList L,L1,L2;
int a=5,a1,a2,j,j1,j2,a3,b3=5;
ElemType e,e1,e2,e3;
InitList_Sq(L);
cout"请输入线性表的元素(共"a"个)"endl;
create(L,a); //线性表里面元素的输入
show(L,a);
a1=L.length;
cout"请选择所要插入元素的位置:"; //线性表插入元素的位置
cinj;
while(j0||jListlength(L))
{ cout"输入有误，请重新输入"endl; //判断线性表的插入位置是否大于线性表的长度
cout"请选择所要插入元素的位置:";
cinj; }
cout"要插入的元素:";
cine1;
ListInsert(L,j,e1);
cout"修改后的线性表数据:"endl;
show(L,a1+1);
a2=L.length;
cout"请选择所要删除元素的位置:"; //删除线性表中的元素
cinj1;
while(j10||j1Listlength(L))
{ cout"请选择所要删除元素的位置:";
cinj1; }
ListDelete_Sq(L,j1,e2);
cout"修改后的线性表数据:"endl;
show(L,a2-1);
cout"请选择所要取出元素的位置:"; //取出线性表中的元素
cinj2;
while(j20||j2Listlength(L))
{ cout"请选择所要取出元素的位置:";
cinj2; }
GetElem(L,j2,e3);
cout"取出的元素为:"e3endl;
InitList_Sq(L1);
a3=L.length;
cout"请输入第二个线性表的元素(共"5"个)"endl; //合并线性表
create(L1,b3);
show(L1,b3);
MergeList(L,L1,L2);
cout"合并后的线性表如下："endl;
show(L2,a3+b3);
return 0;
}
//迷宫算法求解
//编译环境: bc++3.1和vc++6.0下调试通过
#includestdio.h
#includeconio.h
#include "stdlib.h"
#define NULL 0 #define rows 10
#define cols 10 typedef struct
{int row;
int col;
}PosType; //坐标点结构 typedef struct
{int ord;//通道块在路径上的"序号"
PosType seat;//通道块在迷宫中的"坐标位置"
int di;//从此通道快走向下一通道块的"方向"
}SElemType;//栈的元素类型 typedef struct
{SElemType *base;
SElemType *top;
int stacksize;
}SqStack;//堆栈结构 int InitStack(SqStack &s)//初始化堆栈
{
s.base=(SElemType *)malloc(100*sizeof(SElemType));
if(!s.base) return 0;
s.top=s.base;
s.stacksize=100;
return 1;
}
int StackEmpty(SqStack s) //栈空判别
{return(s.top==s.base);
} int Pop(SqStack &s,SElemType &e)//弹栈
{if(s.top==s.base)return 0;
e=*--s.top;
return 1;
} int Push(SqStack &s,SElemType e)//将元素压入堆栈
{if(s.top-s.base=s.stacksize)
{s.base=(SElemType *)realloc(s.base,(s.stacksize+10)*sizeof(SElemType));
if(!s.base)exit(-2);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++=e;
return 1;
}
static int maze[rows][cols]=
{{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,1,0,1,0},
{0,1,1,0,1,0,1,0,1,0},
{0,1,1,0,1,0,0,1,1,0},
{0,1,1,0,0,1,1,1,1,0},
{0,1,1,1,0,1,1,1,1,0},
{0,1,0,1,1,1,0,1,1,0},
{0,1,0,0,0,1,0,0,1,0},
{0,0,1,1,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0},
};
//初始迷宫数据（1－通，0－不通）
static int foot[10][10]={0};//标记某点是否走过（1－走过，0－未走过）
void printpath(SqStack &s)//打印迷宫通路
{int i,j;
SElemType e;
while(!StackEmpty(s))
{Pop(s,e);
foot[e.seat.row][e.seat.col]=1;
}
for(i=0;i10;i++)
{printf("n");
for(j=0;j10;j++)
if(foot[j]) printf(" # ");
else printf(" 。");
}
}
int Pass(PosType pos)//判断当前的通道块是否可通
{
return(maze[pos.row][pos.col]);
};
void FootPrint(PosType pos)
{
maze[pos.row][pos.col]=0;
} PosType NextPos(PosType curpos,int dir)//取当前通道块的下一个通道块
{ switch(dir)
{case 1:
curpos.row++;
break;
case 2:
curpos.col++;
break;
case 3:
curpos.row--;
break;
case 4:
curpos.col--;
}
return curpos;//将下一个通道块变为当前通道块
} int END(PosType curpos,PosType end)
{return(curpos.row==end.row && curpos.col==end.col);
}
int MazePath(SqStack &s,PosType start,PosType end)
{
PosType curpos;
int curstep; SElemType e;
InitStack(s);curpos=start;
curstep=1;
do{
if(Pass(curpos))
{
FootPrint(curpos);
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(s,e);
if(END(curpos,end))
return 1;
curpos=NextPos(curpos,1);
curstep++;
}
else
{
if(!StackEmpty(s))
{
Pop(s,e);
while(e.di==4&&!StackEmpty(s))
{
FootPrint(e.seat);
Pop(s,e);
}
if(e.di4)
{
e.di++;
Push(s,e);
curpos=NextPos(e.seat,e.di);
} }
}
}while(!StackEmpty(s));
curstep==0;
return (false);
}
void main()
{
SqStack s;
static PosType start={1,1},end={8,8}; MazePath(s,start,end);
if(!StackEmpty(s))
printpath(s);
else
printf("n NO find the path!");
}
//三元组
//编译环境:vc++6.0
#includestdio.h
#includeconio.h
#includestdlib.h
#includemath.h
#includeiostream.h
#includemalloc.h #define TRUE 1
#define FLASE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NULL 0 typedef int Status;
typedef int ElemType;
typedef ElemType *Triplet;//用initTriplet分配三个元素存储空间
Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3)
{
//构造三元组T，设置T的3个元素的初始值是v1,v2,v3
T=(ElemType *)malloc(3*sizeof(ElemType));//分配3个元素的存储空间
if (!T)exit(OVERFLOW);
T[0]=v1;
T[1]=v2;
T[2]=v3;
return OK;
}
Status DestroyTriplet(Triplet &T)
{
//销毁三元组
free(T);
T=NULL;
return OK;
}
Status Get(Triplet T,int i,ElemType &e)
{
//用e返回T的第i元的值
if (i1||i3){e=0;return ERROR;}
e=T[i-1];
return OK;
}
Status Put(Triplet &T,int i,ElemType e)
{
//改变T的第i元的值e
if (i1||i3){e=0;return ERROR;}
T[i-1]=e;
return OK;
}
Status IsAscending(Triplet T)
{
//如果T的3个元素按升序排列，则返回1，否则返回0
return (T[0]=T[1])&&(T[1]=T[2]);
}//IsAscending
Status IsDescending(Triplet T)
{
//如果T的3个元素按降序排列，则返回1，否则返回0
return (T[0]=T[1])&&(T[1]=T[2]);
}//IsDescending
Status Max(Triplet T,ElemType &e)
{
//用e返回指向T的最大元素的值
e= (T[0]=T[1])?((T[0]=T[2])?T[0]:T[2])
:((T[1]=T[2])?T[1]:T[2]);
return OK;
}//Max
Status Min(Triplet T,ElemType &e)
{
//用e返回指向T的最大元素的值
e= (T[0]=T[1])?((T[0]=T[2])?T[0]:T[2])
:((T[1]=T[2])?T[1]:T[2]);
return OK;
}//Min
void show(Triplet T)
{
//输出三元组
coutT[0]" "T[1]" "T[2]endl;
}//show
int main()
{
cout"输入三元组:"endl;
Triplet T;
int a,b,c;
cinabc;
InitTriplet(T,a,b,c);
cout"输入的三元组为";
show(T);
InitTriplet(T,a,b,c);
int e;
Get(T,0,e);
Get(T,1,e);
cout"判断这个三元组是否为升序:"endl;
show(T);
cout(IsAscending(T)?"是升序":"不是升序")endl;
cout"判断这个三元组是否为降序:"endl;
show(T);
cout(IsDescending(T)?"是降序":"不是降序")endl;
cout"判断其中最大值:"endl;
show(T);
Max(T,e);
cout"最大数="eendl;
cout"判断其中最小值:"endl;
show(T);
Min(T,e);
cout"最小数="eendl;
return 0;
}
两个多项式链表相加
#includeiostream
using namespace std; struct node
{
int co; //系数域
int exp; //指数域
struct node * next;
}; node* Creat() //尾插法建表，有头结点
{
node* head;
node* s, *p;
int c, e;
head=new node; //生成头结点
head-next=NULL;
cout"请分别输入新的一项的系数、指数(以输入10000作为结束):"endl;
cince;
while(c!=10000 && e!=10000) //输入并检测结束
{
s=new node; //生成新结点
s-co = c; //装入数据
s-exp = e;
p=head;
while(p-next!=NULL)
{
p=p-next;
}
p-next = s; //插到最后一个结点后
s-next = NULL;
cout"请分别输入新的一项的系数、指数(以输入10000作为结束):"endl;
cince;
}
return head;
} void Display(node * head)
{
if(head==NULL)
{
cout"多项式不存在！"endl;
return ;
}
node* p;
p=head-next;
while(p!=NULL)
{
if(p-co0)
coutp-co"x^"p-exp;
else
cout"("p-co")""x^"p-exp;
if(p-next!=NULL)
cout"+";
p=p-next;
}
coutendlendl; } node* Add(node * A, node * B)
{
node * C=new node;
C-next=NULL;
node * p1=A-next;
node * p2=B-next;
node * p3;
node * rearC=C;
while(p1!=NULL && p2!=NULL)
{
if(p1-exp p2-exp)
{
p3=new node;
p3-co=p1-co;
p3-exp=p1-exp;
p3-next=NULL;
rearC-next=p3;
rearC=p3;
p1=p1-next;
}
else if (p1-exp p2-exp)
{
p3=new node;
p3-co=p2-co;
p3-exp=p2-exp;
p3-next=NULL;
rearC-next=p3;
rearC=p3;
p2=p2-next;
}
else //p1-exp == p2-exp
{
if((p1-co + p2-co) != 0)
{
p3=new node;
p3-co = p1-co + p2-co;
p3-exp= p1-exp;
p3-next=NULL;
rearC-next=p3;
rearC=p3;
}
p1=p1-next;
p2=p2-next;
}
}
if(p1==NULL)
{
while(p2!=NULL)
{
p3=new node;
p3-co=p2-co;
p3-exp=p2-exp;
p3-next=NULL;
rearC-next=p3;
rearC=p3;
p2=p2-next;
}
}
else //p2==NULL
{
while(p1!=NULL)
{
p3=new node;
p3-co=p1-co;
p3-exp=p1-exp;
p3-next=NULL;
rearC-next=p3;
rearC=p3;
p1=p1-next;
}
}
return C;
}
int main()
{
cout"多项式A："endl;
node * PL1;
PL1=Creat();
cout"多项式A=";
Display(PL1); cout"多项式B："endl;
node * PL2;
PL2=Creat();
cout"多项式B=";
Display(PL2); cout"多项式A+B=";
node * PL3;
PL3=Add(PL1,PL2);
Display(PL3); return 0;
}
楼主 2016-04-28 11:32 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
