数据结构第一次作业.doc

#include<iostream>
#include<ctype.h>
using namespace std;

typedef struct node
{
int data;
struct node *next;
}Lnode, *LinkList;

void CreatList(LinkList h, int a[], int n)
{
LinkList s, r;
int i;
r=h;
for(i=0; i<n; i++)
{
s = new Lnode;
s->data = a[i];
r->next = s;
r=s;
}
r->next = NULL;
}

void DispList(LinkList h)
{
LinkList r = h->next;
while(r != NULL)
{
printf("%d ",r->data);
r = r->next;
}
putchar('\n');

}

void InsertList(LinkList h, int x, int y)
{
LinkList s, p, q;
s = new Lnode;
s->data = y;
q = h; p = q->next;
while((p!=NULL) && (p->data != x))
{
q = p;
p = p->next;
}
s->next = p;
q->next = s;
}

void DeleteList(LinkList h, int x)
{
LinkList p, q;
q = h;
p = q->next;
while((p != NULL) && (p->data != x))
{
q = p;
p = p->next;
}
if(p == NULL) printf("no");
else
{
q->next = p->next;
delete(p);
printf("yes");
}
}

void Countnode(LinkList h, int &j)
{
LinkList r;
r = h->next;
while(r != NULL) {j++; r = r->next; }
}

int main()
{
int i, a[100]={0}, x, y, n, j=0;
char p;

LinkList h;
h = new Lnode;
h->next = NULL;
printf("主菜单\n");
printf("1.创建单链表\n");
printf("2.结点的插入\n");
printf("3.结点的删除\n");
printf("4.统计结点个数\n");
printf("5.退出系统\n");

printf("输入单链表的元素个数是n, n<=100 \n");
scanf("%d",&n);
printf("请输入元素：\n");
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
do
{

printf("请输入选择p(1-5)\n");
scanf(" %c",&p);

switch(p)
{
case '1':
CreatList(h, a, n); DispList(h);break;
case '2':
printf("在x的结点之前插入值y的结点，请输入x, y\n");
scanf("%d%d",&x,&y);
InsertList(h, x, y);
DispList(h);break;

case '3':
printf("删除值为x的结点，请输入x\n");
scanf("%d",&x);
DeleteList(h, x);
DispList(h);break;
case '4':
printf("统计结点个数\n");
Countnode(h,j);
printf("结点个数为%d\n",j);break;
case '5':
printf("退出系统\n");
break;
default:printf("选择错误! 请重新选择p(1-5)\n") ;p='0';
}

}while(p < '5');
return 0;
}

#include <iostream>
using namespace std;
#define MaxSize 100
#define NULL 0

typedef struct sqlist
{char data[MaxSize];
int length;
}SqList;

void InitList(SqList *&l)
{l=new SqList;
l->length=0;
}

void CreatList(SqList *l,char a[],int n)
{int i;
for(i=0;i<n;i++)
l->data[i]=a[i];
l->length=n;
}

int ListEmpty(SqList *l)
{return(l->length==0);
}

void DispList(SqList *l)
{int i;
if(ListEmpty(l)) return;
for(i=0;i<l->length;i++)
cout<<l->data[i]<<' ';
cout<<endl;
}

int GetElem(SqList *l,int i,int &m)
{if(i<1||i>l->length)
return 0;
m=l->data[i-1];
return 1;
}

int LocateElem(SqList *l,int k)
{int i=0;
while((i<l->length)&&(l->data[i]!=k))
i++;
if(i>=l->length)
return 0;
else return i+1;
}

void DestroyList(SqList *&l)
{
delete(l);
}

void main()
{
SqList *A=NULL, *B=NULL;
int num,i,j,e,k,v, xx=0;
char a[100], b[100], c[100];

InitList(A);
InitList(B);

cout<<"how many elements in A?"<<endl;
cin>>num;
cout<<"input A:"<<endl;
for(i=0;i<num;i++)
cin>>a[i];
CreatList( A,a,num);

cout<<"how many elements in B?"<<endl;
cin>>k;
cout<<"input B:"<<endl;
for(i=0;i<k;i++)
cin>>b[i];
CreatList( B,b,k);
cout<<"*************************"<<endl;
cout<<"A is:"<<endl;
DispList(A);
cout<<endl;
cout<<"B is:"<<endl;
DispList(B);
cout<<endl;
cout<<"A - B is:"<<endl;
for(i=0;i<num;i++)
{
for(j=0;j<k;j++)
{
if(A->data[i]==B->data[j])break;
}
if(j==k)
cout<<(c[xx++]=A->data[i])<<' ';
}
cout<<endl<<endl;

cout<<"B - A is:"<<endl;
for(i=0;i<k;i++)
{
for(j=0;j<num;j++)
{
if(B->data[i]==A->data[j])break;
}
if(j==num)
cout<<(c[xx++]=B->data[i])<<' ';
}
cout<<endl<<endl;
cout<<"A - B |_| B - A:"<<endl;
for(i=0; i<xx;i++)
cout<<c[i]<<' ';
DestroyList(A);
DestroyList(B);
cout<<endl;
}

#include <iostream>
using namespace std;

typedef struct sqnode
{int data;
struct sqnode *next;
}ListStack;

void InitStack(ListStack *&s)
{
s=new ListStack;
s->next = NULL;
s->data = 0;
}

int EmptyStack( ListStack *s)
{
return(s->next== NULL);
}

void Push(ListStack *s,int e)
{
ListStack *p = new ListStack;
p->data = e;
p->next = s->next;
s->next = p;
}

void GetTop(ListStack *s,int &e)
{
if (EmptyStack(s))
cout<<"栈空！"<<endl;
else
e=s->next->data;
}

void Pop(ListStack *s,int &e)
{ if (EmptyStack(s))
cout<<"栈空"<<endl;
else
{
ListStack *p = s->next;
e = p->data;
s->next = p->next;
delete p;
}
}

void DispStack(ListStack *s)
{
if(EmptyStack(s))
cout<<"Stack is empty!"<<endl;
else
{
ListStack *p = s->next;
cout<<"Stack is:"<<endl;
while(p != NULL)
cout<<p->data<<' ';
cout<<endl;
}
}

int main()
{
ListStack *s = NULL;
int a, i, num;
InitStack( s);
cout<<"栈数："<<endl;
cin>>num;
cout<<"进栈值："<<endl;
for(i=0;i<num;i++)
{
cin>>a;
Push(s, a);
}
cout<<"栈顶：";
cout<<(GetTop(s,a), a)<<endl;
cout<<"出栈："<<endl;
while(--num>=0)
{
cout<<(Pop(s,a),a)<<' ';
}

return 0;
}

#include <iostream>
using namespace std;
#define MaxSize 50
#define Null 0

typedef struct sqstack
{char data[MaxSize];
int top;
}SqStack;

void InitStack(SqStack *&s)
{
s=new SqStack;
s->top=-1;
}

int EmptyStack( SqStack *s)
{
return(s->top== -1);
}

int FullStack(SqStack *s)
{
return(s->top== MaxSize-1);
}

void Push(SqStack *s,char e)
{ if (FullStack(s)) return ;
s->top++;
s->data[s->top]=e;
return ;
}

void GetTop(SqStack *s,char &e)
{ if (EmptyStack(s))
return ;
e=s->data[s->top];

return ;
}

char Pop(SqStack *s)
{ char e;
if (EmptyStack(s))
return 0;
e=s->data[ s->top];
s->top--;
return e;
}

void DispStack(SqStack *s)
{int i;
if(EmptyStack(s))
cout<<"Stack is empty!"<<endl;
else
{cout<<"Stack is:"<<endl;
for(i=0;i<=s->top;i++)
cout<<s->data[i]<<' ';
cout<<endl;
}
}

void main()
{SqStack *s=NULL;

char y, x;
InitStack(s);

cout<<"Pleast input:"<<endl;
while(x=getchar(), x!=EOF)
{
if(x=='#')
{
Pop(s);
}
else if(x=='@')
{
while(GetTop(s, y),y!='\n' )
{
Pop(s);
}

}
else
{
Push(s,x);
}
}

DispStack(s);

}