锐格系统数据结构相关习题

线性表

題目內容:
采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。

输入输出说明:
输入：
2x^2 3x^3 5x^5 7x^7#
-2x^2 2x^3 4x^4 5x^7 9x^9#
输出：
5x^3 4x^4 5x^5 12x^7 9x^9

#include
#include 
struct node
{int co;    int exp;  struct node * next;
};node* Creat()
{node* head;node* s, *p;int c, e;char a;head=new node;head->next=NULL;
do
{scanf("%d*x^%d%c",&c,&e,&a);s=new node;s->co = c;s->exp = e;p=head;while(p->next!=NULL){p=p->next;}p->next = s;s->next = NULL;}while(a!='#');return  head;
}void Display(node * head)
{if(head==NULL){return ;}node* p;p=head->next;while(p!=NULL){printf("%d*x^%d ",p->co,p->exp);p=p->next;}printf("\n");}node* Add(node * A, node * B)
{node * C=new node;C->next=NULL;node * p1=A->next;node * p2=B->next;node * p3;node * pC=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;pC->next=p3;pC=p3;p1=p1->next;}else if (p1->exp > p2->exp){p3=new node;p3->co=p2->co;p3->exp=p2->exp;p3->next=NULL;pC->next=p3;pC=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;pC->next=p3;pC=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;pC->next=p3;pC=p3;p2=p2->next;}}else //p2==NULL{while(p1!=NULL){p3=new node;p3->co=p1->co;p3->exp=p1->exp;p3->next=NULL;pC->next=p3;pC=p3;p1=p1->next;}}return C;
}
int main()
{node * p1;p1=Creat();node * p2;p2=Creat();node * p3;//Display(p1);//Display(p2);p3=Add(p1,p2);Display(p3);return 0;
}

題目內容:
随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。

遍历单向链表。

输入输出说明:
输入：
1 2 3 5 7 8 0
输出：
1 2 3 5 7 8

#include 
#include 
typedef int elemtype;
typedef struct node
{elemtype data;struct node*next;
}Lnode;
void create(Lnode *phead)
{int data;Lnode *p=phead,*q;scanf("%d",&data);while(data!=0){q=(Lnode *)malloc(sizeof(Lnode));q->next=NULL;q->data=data;p->next=q;p=q;scanf("%d",&data);}
}
void output(Lnode* phead)
{phead=phead->next;while(phead!=NULL){printf("%d ",phead->data);phead=phead->next;}
}
int main()
{Lnode *phead=(Lnode *)malloc(sizeof(Lnode));phead->next=NULL;create(phead);output(phead);return 0;
}

題目內容:
试编写算法，把单向链表中元素逆置（不允许申请新的结点空间）。

输入输出说明:
输入：
1 2 4 6 8 9 0
输出：
9 8 6 4 2 1

#include 
#include 
typedef int elemtype;
typedef struct node
{elemtype data;struct node*next;
}Lnode;
void create(Lnode *phead)
{int data;Lnode *p=phead,*q;scanf("%d",&data);while(data!=0){q=(Lnode *)malloc(sizeof(Lnode));q->next=NULL;q->data=data;p->next=q;p=q;scanf("%d",&data);}
}
void output(Lnode* phead)
{phead=phead->next;while(phead!=NULL){printf("%d ",phead->data);phead=phead->next;}
}
void reverse(Lnode *phead)
{Lnode *p=phead,*q;p=phead->next;phead->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=NULL;q->next=phead->next;phead->next=q;}
}int main()
{Lnode *phead=(Lnode *)malloc(sizeof(Lnode));phead->next=NULL;create(phead);reverse(phead);output(phead);return 0;
}

題目內容:
编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。

输入输出说明:
输入：
1 6 4 3 5 8 7 9 0
输出：
1 3 4 5 6 7 8 9

#include 
#include 
typedef int elemtype;
typedef struct node
{elemtype data;struct node*next;
}Lnode;
void create(Lnode *phead)
{int data;Lnode *p=phead,*q;scanf("%d",&data);while(data!=0){q=(Lnode *)malloc(sizeof(Lnode));q->next=NULL;q->data=data;p->next=q;p=q;scanf("%d",&data);}
}
void output(Lnode* phead)
{phead=phead->next;while(phead!=NULL){printf("%d ",phead->data);phead=phead->next;}
}
void reverse(Lnode *phead)
{Lnode *p=phead,*q;p=phead->next;phead->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=NULL;q->next=phead->next;phead->next=q;}
}
void deletee(Lnode *phead)
{Lnode *p,*q;p=phead;q=phead->next;while(q!=NULL){if(q->data%2==0){p->next=q->next;free(q);q=p->next;}else{p=q;q=q->next;}}
}
elemtype length(Lnode *phead)
{Lnode *p;p=phead->next;int a=0;while(p!=NULL){p=p->next;a++;}return a;
}
Lnode *sortlist (Lnode *phead)
{Lnode *p;if(phead->next==NULL){return phead;}int n,i,j;n=length(phead);for(i=1;i<n;i++){p=phead->next;for(j=0;j<n-1;j++){if(p->data > p->next->data){elemtype t=p->data;p->data=p->next->data;p->next->data=t;}p=p->next;}}return phead;
}
int main()
{Lnode *phead=(Lnode *)malloc(sizeof(Lnode));phead->next=NULL;create(phead);Lnode *p=sortlist(phead);output(p);return 0;
}

題目內容:
试编写算法，在单向链表中删除所有的偶数元素结点。

输入输出说明:
输入：
1 2 3 4 6 7 9 0
输出：
1 3 7 9

#include 
#include 
typedef int elemtype;
typedef struct node
{elemtype data;struct node*next;
}Lnode;
void create(Lnode *phead)
{int data;Lnode *p=phead,*q;scanf("%d",&data);while(data!=0){q=(Lnode *)malloc(sizeof(Lnode));q->next=NULL;q->data=data;p->next=q;p=q;scanf("%d",&data);}
}
void output(Lnode* phead)
{phead=phead->next;while(phead!=NULL){printf("%d ",phead->data);phead=phead->next;}
}
void reverse(Lnode *phead)
{Lnode *p=phead,*q;p=phead->next;phead->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=NULL;q->next=phead->next;phead->next=q;}
}
void deletee(Lnode *phead)
{Lnode *p,*q;p=phead;q=phead->next;while(q!=NULL){if(q->data%2==0){p->next=q->next;free(q);q=p->next;}else{p=q;q=q->next;}}
}int main()
{Lnode *phead=(Lnode *)malloc(sizeof(Lnode));phead->next=NULL;create(phead);deletee(phead);output(phead);return 0;
}

題目內容:
建立两个非递减有序单向链表，然后合并成一个非递增链表。

输入输出说明:
输入：
1 9 5 7 3 0
2 8 4 6 0
输出：
9 8 7 6 5 4 3 2 1

#include 
#include
#include 
using namespace std;
typedef int elemtype;
typedef struct node
{elemtype data;struct node*next;
}lnode,*linklist;void createhead(linklist &l)
{l=new lnode;l->next=NULL;int x;linklist p,r;p=new lnode;r=l;scanf("%d",&x);while(x!=0){p=new lnode;p->data=x;p->next=NULL;r->next=p;r=p;scanf("%d",&x);}
}
void output(linklist l)
{linklist p=l->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");
}
void mergelist(linklist &la,linklist &lb,linklist &lc)
{linklist pa=la->next;linklist pb=lb->next;linklist pre;lc=la;la->next=NULL;while(pa&&pb){if(pa->data <= pb->data){pre=pa->next;pa->next=la->next;la->next=pa;pa=pre;}else{pre=pb->next;pb->next=la->next;la->next=pb;pb=pre;}}while(pa){pre=pa->next;pa->next=la->next;la->next=pa;pa=pre;}while(pb){pre=pb->next;pb->next=la->next;la->next=pb;pb=pre;}free(lb);}
/*void mergelist(linklist &la,linklist &lb,linklist &lc)
{linklist pa=la->next;linklist pb=lb->next;linklist pc;pc=lc=la;lc->next=NULL;while(pa||pb){if(!pa){pc=pb;pb=pb->next;}if(!pb){pc=pa;pa=pa->next;}else if(pa->data <= pb->data){pc=pa;pa=pa->next;}else{pc=pb;pb=pb->next;}pc->next=lc->next;lc->next=pc;}delete lb;
}*/
int length(linklist l)
{int n=0;linklist p=l->next;while(p){p=p->next;n++;}return n;
}
lnode *sortlist (lnode *phead)
{lnode *p;if(phead->next==NULL){return phead;}int n,i,j;n=length(phead);for(i=1;i<n;i++){p=phead->next;for(j=1;j<n;j++){if(p->data < p->next->data){elemtype t=p->data;p->data=p->next->data;p->next->data=t;}p=p->next;}}return phead;
}
int main()
{linklist la,lb,lc;createhead(la);createhead(lb);mergelist(la,lb,lc);linklist p= sortlist(lc);output(p);return 0;
}

題目內容:
编写算法建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

输入输出说明:
输入：
1 2 3 4 5 6 7 8 9 0
输出：
1 3 5 7 9
2 4 6 8

//https://blog.csdn.net/wuxuanyi27/article/details/51174330
#include 
#include 
typedef int elemtype;
typedef struct node
{elemtype data;struct node*next;
}Lnode;
void create(Lnode *phead)
{int data;Lnode *p=phead,*q;scanf("%d",&data);while(data!=0){q=(Lnode *)malloc(sizeof(Lnode));q->next=NULL;q->data=data;p->next=q;p=q;scanf("%d",&data);}
}
void output(Lnode* phead)
{phead=phead->next;while(phead!=NULL){printf("%d ",phead->data);phead=phead->next;}
}
void reversee(Lnode *phead)
{Lnode *p=phead,*q;p=phead->next;phead->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=NULL;q->next=phead->next;phead->next=q;}
}
void deletee(Lnode *phead)
{Lnode *p,*q;p=phead;q=phead->next;while(q!=NULL){if(q->data%2==0){p->next=q->next;free(q);q=p->next;}else{p=q;q=q->next;}}
}
elemtype length(Lnode *phead)
{Lnode *p;p=phead->next;int a=0;while(p!=NULL){p=p->next;a++;}return a;
}
Lnode *sortlist (Lnode *phead)
{Lnode *p;if(phead->next==NULL){return phead;}int n,i,j;n=length(phead);for(i=1;i<n;i++){p=phead->next;for(j=0;j<n-1;j++){if(p->data > p->next->data){elemtype t=p->data;p->data=p->next->data;p->next->data=t;}p=p->next;}}return phead;
}
void insertt(Lnode *p,Lnode *t)
{Lnode *p1=p->next,*p2=p;if(p->next==NULL){p->next=t;return;}while(p1->data<t->data&&p1->next!=NULL){p2=p1;p1=p1->next;if(p1->next!=NULL){t->next=p2->next;p2->next=t;}else{if(p1->data > t->data){t->next=p2->next;p2->next=t;}else{t->next=p1->next;p1->next=t;}}}
}
void add(Lnode *p1,Lnode *p2)
{Lnode *p,*q;p=p2->next;while(p!=NULL){q=p;p=p->next;insertt(p1,q);}
}void create1(Lnode *phead)
{int data;Lnode *p=phead,*q;scanf("%d",&data);while(data!=0){q=(Lnode *)malloc(sizeof(Lnode));q->next=NULL;q->data=data;insertt(p,q);scanf("%d",&data);}
}
void divide(Lnode * head)//分为左右两部分，左边的元素为奇数，右边所有元素为偶数
{Lnode *L=head,*p,*q,*r,*s;r=L;p=L->next;int i,j=0;while(p!=NULL){s=p;//s为最后一个节点；p=p->next;j++;}r=L;p=L->next;q=p->next;for( i=0; i<j-1; i++){if((p->data)%2==0){r->next=q;p->next=NULL;s->next=p;s=p;p=q;q=p->next;}else{r=p;p=q;q=p->next;}}
}
void depart(Lnode * head,Lnode* l)
{Lnode* q=head,*p;q=q->next;while(q->data%2==1){elemtype x;x=q->data;p=(Lnode *)malloc(sizeof(Lnode));p->data=x;p->next=l->next;l->next=p;head->next=q->next;free(q);q=head->next;}
}int main()
{Lnode *phead=(Lnode *)malloc(sizeof(Lnode));phead->next=NULL;create(phead);divide(phead);Lnode* l;l=(Lnode* )malloc(sizeof(Lnode));l->next=NULL;depart(phead,l);sortlist(l);output(l);printf("\n");output(phead);//output(phead);return 0;
}

栈和队列

題目內容:
试编写算法，采用链式存储实现栈的初始化、入栈、出栈操作。

输入输出说明:
输入：
1 2 3 4 5 6 7 8 9 0
输出：
9 8 7 6 5 4 3 2 1

#include 
#include
#include 
using namespace std;
typedef int elemtype;
typedef struct stacknode
{elemtype data;struct stacknode*next;
}stacknode,*linkstack;
void init(linkstack &top)
{top=NULL;
}
void push(linkstack &top,elemtype x)
{stacknode *s;
s=new stacknode;// scanf("%d",&x);// while(x!=0)// {s=new stacknode;s->data=x;s->next=top;top=s;//  scanf("%d",&x);//}
}
elemtype pop(linkstack &s)
{linkstack p=new stacknode;int x;if(s!=NULL){x=s->data;p=s;s=s->next;free(p);return x;}
}
int main()
{linkstack l,s;s=new stacknode;int n=0,i,x;init(s);scanf("%d",&x);while(x){push(s,x);n++;scanf("%d",&x);}for(i=0;i<n;i++){printf("%d ",pop(s));}
}

題目內容:
试编写算法，采用顺序存储实现栈的初始化、入栈、出栈操作。

输入输出说明:
输入：1 2 3 4 5 6 7 8 9 0
输出：9 8 7 6 5 4 3 2 1

#include
#define m 50
typedef int elemtype;
typedef struct
{elemtype data[m];int top;
}SqStack;
void init(SqStack &s)
{s.top=-1;
}
int push(SqStack &s,elemtype x)
{if(s.top==m-1) return 0;s.data[++s.top]=x;return 1;
}
void pop(SqStack &s,elemtype x)
{if(s.top!=-1){x=s.data[s.top--];printf("%d ",x);}
}
void gettop(SqStack s,elemtype &x)
{if(s.top!=-1){x=s.data[s.top];printf("%d ",x);}
}
int main()
{SqStack s;int n=0,i,e,x;init(s);scanf("%d",&x);while(x){push(s,x);scanf("%d",&x);n++;}for(i=0;i<n;i++){pop(s,e);}return 0;
}

題目內容:
编程，采用链式存储实现队列的初始化、入队、出队操作。

输入输出说明:
输入：1 2 3 4 5 6 7 8 9 0
输出：1 2 3 4 5 6 7 8 9

#include
#include 
using namespace std;
typedef char elemtype;
typedef struct node
{elemtype data;struct node*next;
}node,*queuenode;
typedef struct
{queuenode f;queuenode r;
}linkqueue;
void init(linkqueue &q)
{q.f=q.r=new node;q.f->next=NULL;
}
void enqueue(linkqueue &q,elemtype e)
{queuenode p=new node;p->data=e;p->next=NULL;q.r->next=p;q.r=p;
}
void dequeue(linkqueue &q,elemtype &e)
{if(q.f!=q.r){queuenode p=q.f->next;e=p->data;q.f->next=p->next;if(q.r==p) q.r=q.f;delete p;}
}
int main()
{linkqueue q;int i,x,n=0;char e;init(q);scanf("%d",&x);while(x)
{enqueue(q,x);n++;scanf("%d",&x);
}for(i=0;i<n;i++){dequeue(q,e);printf("%d ",e);}return 0;
}

題目內容:
编程，采用顺序存储实现循环队列的初始化、入队、出队操作。

输入输出说明:
输入：
1 2 3 4 5 6 7 8 9 0
输出：
1 2 3 4 5 6 7 8 9

#include
#include 
#define m 100
using namespace std;
typedef char elemtype;
typedef struct
{elemtype *b;int f;int r;
}sqqueue;
void init(sqqueue &q)
{q.b=new elemtype[m];if(q.b){q.f=q.r=0;}
}
void enqueue(sqqueue &q,elemtype e)
{if((q.r+1)%m!=q.f){q.b[q.r]=e;q.r=(q.r+1)%m;}
}
void dequeue(sqqueue &q,elemtype &e)
{if(q.f!=q.r){e=q.b[q.f];q.f=(q.f+1)%m;}
}
int main()
{sqqueue q;int i,x,n=0;char e;init(q);scanf("%d",&x);while(x)
{enqueue(q,x);n++;scanf("%d",&x);
}for(i=0;i<n;i++){dequeue(q,e);printf("%d ",e);}return 0;
}

題目內容:
编程，利用栈实现数制转换（将一个十进制数转换成d进制数）

输入输出说明:
输入：
117 6
输出：
117(10)=313(6)

#include
#define m 50
typedef int elemtype;
typedef struct
{elemtype data[m];int top;
}SqStack;
void init(SqStack &s)
{s.top=-1;
}
int stackempty(SqStack s)
{if(s.top==-1) return 1;return 0;
}
int push(SqStack &s,elemtype x)
{if(s.top==m-1) return 0;s.data[++s.top]=x;return 1;
}
void pop(SqStack &s,elemtype &x)
{if(s.top!=-1){x=s.data[s.top--];printf("%d",x);}
}
void gettop(SqStack s,elemtype &x)
{if(s.top!=-1){x=s.data[s.top];printf("%d ",x);}
}
void convert(int n,int a)
{SqStack s;init(s);int e;while(n){push(s,n%a);n=n/a;}while(!stackempty(s)){pop(s,e);// printf("%d ",e);}
}
int main()
{SqStack s;int a,x,i;init(s);scanf("%d%d",&x,&a);printf("%d(10)=",x);convert(x,a);printf("(%d)\n",a);return 0;
}

利用队列打印杨辉三角：编写程序，根据输入的行数，屏幕显示杨辉三角

输入输出说明:
输入：
9
输出：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1

#include 
#include 
#include 
using namespace std;
#define MAXQSIZE 1000 
typedef int QElemType;
typedef struct
{QElemType *base;int front;int rear;
} SqQueue;
int InitQueue(SqQueue &Q)
{Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base) return 0;Q.front=Q.rear=0;return 1;
}
int EnQueue(SqQueue &Q, QElemType e)
{if((Q.rear+1)%MAXQSIZE==Q.front) return 0;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return 1;
}
int DeQueue(SqQueue &Q, QElemType &e)
{if(Q.front==Q.rear) return 0;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return 1;
}
int GetQueue(SqQueue &Q, QElemType &e)
{if(Q.front==Q.rear) return 0;e=Q.base[Q.front];return 1;
}
int main()
{int n;cin>>n;SqQueue Q;InitQueue(Q);//EnQueue(Q,0);for(int i=1;i<=n;i++){for(int j=1;j<=n-i;j++)cout<<"  ";printf("%2d  ",1);///cout<<1<<"  ";for(int k=3;k<=i;k++){int x,e;DeQueue(Q,x);GetQueue(Q,e);EnQueue(Q,x+e);printf("%2d  ",x+e);}if(i!=1){printf("%2d  ",1);}EnQueue(Q,1);cout<<endl;}return 0;
}

題目內容:
综合训练:试编写算法，利用栈实现表达式求值算法。

输入输出说明:
输入：
20-2*(5-1-3*(4-1)-2)-6#
输出：
-28

#include
#include
#include#define FALSE 0
#define TRUE 1typedef struct stacknode{float data;struct stacknode * next;
}StackType;float get_stack(StackType *, float *);            
float pop_stack(StackType *, float *);             
float Push_stack(StackType *, float);      
char compare(char, char);               
float Operation(float , float, float );       StackType * Init_stack()
{StackType * top;top = (StackType *)malloc(sizeof(StackType));top->next = NULL;return top;
}float Push_stack(StackType * top, float x)
{StackType * p;p = (StackType *)malloc(sizeof(StackType));if(p == NULL){return FALSE;}p->data = x;p->next = top->next;top->next = p;return TRUE;
}float pop_stack(StackType * top, float * x)
{StackType * p;if(top->next == NULL){return -1;}p = top->next;top->next = p->next;*x = p->data;free(p);return 0;
}float getnext(float * n)                       
{char c;*n = 0;while((c = getchar()) == ' ');         if(!isdigit(c)){                        *n = c;return 1;}do{*n = *n * 10 + (c - '0');           //使用循环获得连续的数字，乘10进位c = getchar();}while(isdigit(c));ungetc(c, stdin);                      return 0;
}char compare(char a, char b)
{int i, j;char pre[7][7] ={                     {'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','0'},{'>','>','>','>','0','>','>'},{'<','<','<','<','<','0','='},};switch(a){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(b){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;case  10: printf("表达式要以#结尾！！！\n");exit(1);}return pre[i][j];
}float Operation(float a, float operate, float b)           
{float result;a = (float)a;b = (float)b;switch((int)operate){case '+': result = a + b; break;case '-': result = a - b; break;case '*': result = a * b; break;case '/': result = a / b; break;}return result;
}float EvaluateExpression()
{float n;float c;                                  float flag;                               float x;                                  float operate;                            float a, b;                              StackType * top_oprd, * top_optr;       char op[] = "+-*/()#";top_oprd = Init_stack();top_optr = Init_stack();Push_stack(top_optr, '#');flag = getnext(&c);get_stack(top_optr, &x);while((float)c != '#' || (float)x != '#')        {if(flag == 0)                   {Push_stack(top_oprd, c);flag = getnext(&c);}else                          {get_stack(top_optr, &x);       switch(compare((float)x, (float)c)){case '<':               Push_stack(top_optr, c);flag = getnext(&c);break;case '>':               pop_stack(top_optr, &operate);pop_stack(top_oprd, &a);pop_stack(top_oprd, &b);Push_stack(top_oprd, Operation(b, operate, a));        break;case '=':              pop_stack(top_optr, &operate);flag = getnext(&c);break;case '0':             printf("input error!\n");exit(1);}}get_stack(top_optr, &x);}get_stack(top_oprd, &c);return c;}float get_stack(StackType * top, float * x)
{if(top->next == NULL){return -1;}*x = top->next->data;return 0;
}int main(void)
{float c;c = EvaluateExpression();printf("-%d",(int)c);getchar();
}

二叉树

題目內容:
试编写算法，输入一个字符序列，建立其二叉链表存储结构，并对该二叉链表进行后序遍历。

输入输出说明:
输入数据：
ABD@@E@@CF@@G@@
输出数据：
D E B F G C A

#include 
using namespace std;
typedef char datatype;
struct tnode
{datatype data;tnode *l;tnode *r;
};
void create(tnode *&root)
{char d;cin>>d;if(d=='@') root=NULL;else{root=new tnode;root->data=d;create(root->l);create(root->r);}
}
void posorder(tnode *&root)
{if(root!=NULL){posorder(root->l);posorder(root->r);cout<<root->data<<" ";}
}
int main()
{tnode *root=NULL;create(root);posorder(root);cout<<endl;return 0;
}

題目內容:
假设二叉树用二叉链表存储，试编写算法，求二叉树的高度。

输入输出说明:
输入：
AB@E@R@@CF@@@
输出：
4

#include 
using namespace std;
typedef char datatype;
struct tnode
{datatype data;tnode *l;tnode *r;
};
void create(tnode *&root)
{char d;cin>>d;if(d=='@') root=NULL;else{root=new tnode;root->data=d;create(root->l);create(root->r);}
}
void posorder(tnode *&root)
{if(root!=NULL){posorder(root->l);posorder(root->r);cout<<root->data<<" ";}
}
int height(tnode *root)
{int m,n;if(root==NULL) return 0;else{m=height(root->l);n=height(root->r);if(m>n) return (m+1);else return (n+1);}
}
int main()
{tnode *root=NULL;create(root);int n=height(root);cout<<n<<" ";//posorder(root);cout<<endl;return 0;
}

題目內容:
设二叉树用二叉链表存储，编写算法，求二叉树的叶子结点个数。

输入输出说明:
二叉树节点的数据类型为字符型

#include 
#include 
#include 
#include 
using namespace std;typedef char elemtype;
typedef struct binode
{elemtype data;struct binode *l,*r;
}binode,*bitree;
bitree create()
{bitree t;elemtype item;cin >>item;if(item=='@') t=NULL;else{t=(binode *)malloc(sizeof(binode));t->data=item;t->l=create();t->r=create();}return t;
}
int count(bitree t)
{if(t==NULL) return 0;else if(t->l==NULL && t->r==NULL) return 1;elsereturn (count(t->l)+count(t->r));
}int main(){int n;bitree t;t=create();n=count(t);printf("%d\n",n);}

題目內容:
假设二叉树用二叉链表存储，试编写二叉树的非递归中序遍历算法。

输入输出说明:
输入数据：
ABD@@E@@CF@@G@@
输出数据：
D B E A F C G

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef struct binode
{char data;binode*l,*r;
}binode,*bitree;
void create(bitree &t)
{char ch;scanf("%c",&ch);if(ch=='@'){t=NULL;return;}else{t=(binode *)malloc(sizeof(binode));if(!t) exit(1);t->data=ch;create(t->l);create(t->r);}
}
void traverse(bitree t)
{stack<bitree> Stack;if(!t) return;while(t || !Stack.empty()){while(t){Stack.push(t);t=t->l;}t=Stack.top();Stack.pop();printf("%c ",t->data);t=t->r;}
}int main()
{bitree t;create(t);traverse(t);printf("\n");return 0;
}

題目內容:
试编写算法，用森林的孩子兄弟链表表示法，计算森林中叶子个数。

输入输出说明:
输入：
ABD@@E@R@@CF@@GI@@@
输出：
5

#include "stdio.h"
#include "malloc.h"typedef struct node{char data;struct node *lc,*rb;}node,*list;void create(list &t)
{char ch;scanf("%c",&ch);if(ch!='@'){t=(node *)malloc(sizeof(node));t->data=ch;create(t->lc);create(t->rb);}elset=NULL;
}
int count(list t)
{if(t==NULL) return 0;if(t->lc==NULL) return count(t->rb)+1;else return count(t->lc)+count(t->rb);
}int main(){list t;create(t);printf("%d\n",count(t));}

題目內容:
试编写算法，建立中序线索二叉树，并实现中序遍历。

输入输出说明:
二叉树各结点数据类型为字符型，空节点数据为@

#include 
#include 
#include 
using namespace std;
typedef char elemtype;
typedef struct binode
{char data;int ltag,rtag;struct binode *lchild;struct binode *rchild;
}binode,*bitree;
void create(bitree &t)
{char ch;scanf("%c",&ch);if(ch=='@') t=NULL;else{t=(binode *)malloc(sizeof(binode));t->data=ch;t->ltag=0;t->rtag=0;create(t->lchild);create(t->rchild);}
}
int intraverse(bitree t,int(*visit)(elemtype e))
{bitree p=t->lchild;while(p&&(p!=t)){while(p->ltag==0){p=p->lchild;}visit(p->data);while(p->rtag==1&&p->rchild!=t){p=p->rchild;visit(p->data);}p=p->rchild;}return 1;
}void threading(bitree p,bitree &pre)
{if(p){threading(p->lchild,pre);if(!p->lchild){p->ltag=1;p->lchild=pre;}if((!pre->rchild)&&pre->rchild==NULL){pre->rtag=1;pre->rchild=p;}pre=p;threading(p->rchild,pre);}
}
int print(char e)
{printf("%c ",e);return 1;
}int traverse(bitree &t1,bitree t)
{t1=(bitree)malloc(sizeof(binode));t1->ltag=0;t1->rtag=1;t1->rchild=t1;bitree pre;if(!t)t1->lchild=t1;else{t1->lchild=t;pre=t1;threading(t,pre);pre->rchild=t1;pre->rtag=1;t1->rchild=pre;}return 1;
}int main()
{bitree t,t1;create(t);if(traverse(t1,t)==1){intraverse(t1,print);}printf("\n");return 0;}

題目內容:
试编写算法实现，借助队列实现二叉树的层次遍历。

输入输出说明:
二叉树的结点数据类型位字符型，空指针域的结点值为@

#include 
#include 
#include 
using namespace std;
typedef struct tnode *bitree;
struct tnode
{char data;bitree lchild;bitree rchild;
};
typedef bitree elemtype;
typedef struct qnode *queue;
struct qnode
{elemtype data[100];int f,r;
};
int isempty(queue q)
{if(q->f==q->r) return 0;else return 1;
}
queue create()
{queue p;p=(queue)malloc(sizeof(struct qnode));p->f=0;p->r=0;return p;
}
void enqueue(queue *p,elemtype x)
{if((((*p)->r)+1)%100==(*p)->f)return;(*p)->data[((*p)->r)++]=x;(*p)->r=((*p)->r)%100;return;}
bitree out(queue *p)
{int a;if((*p)->f==(*p)->r)return NULL;a=(*p)->f;(*p)->f=(((*p)->f)+1)%100;return (*p)->data[a];
}
void createt(bitree *t)
{char n;scanf("%c",&n);if(n=='@') t=NULL;else{*t=(bitree)malloc(sizeof(struct tnode));(*t)->data=n;createt(&((*t)->lchild));createt(&((*t)->rchild));}
}
void traverse(bitree t)
{queue q;bitree t1;if(!t) return;q=create();enqueue(&q,t);while(isempty(q)){t=out(&q);printf("%c ",t->data);if(t->lchild) enqueue(&q,t->lchild);if(t->rchild) enqueue(&q,t->rchild);}return;
}
int main()
{bitree t;t=(bitree)malloc(sizeof(struct tnode));createt(&t);traverse(t);return 0;
}

图

題目內容:

试编写算法，请从键盘输入数据，（1）建立一个有向图的邻接表存储。

       （2）输出该邻接表。(3)输出深度优先遍历序列；（4）输出广度优先遍历序列

输入输出说明:
输入数据：
6 6
A B C D E F
A B
A C
B D
C D
D E
C F
A
输出：
0：A 2 1
1:B 3
2:C 5 3
3:D 4
4:E
5:F
A C F D E B

#include 
#include 
#include 
#include 
using namespace std;
typedef struct arcnode
{int adjvex;struct arcnode *nextarc;
} arcnode;
typedef struct vnode
{    char data;arcnode *firstarc;} vnode,adjlist[100];
typedef struct
{adjlist vertices;int vexnum,arcnum;
} algraph;
int locatevex(algraph g,char v)
{int i;for(i=0; i<g.vexnum; i++)if(g.vertices[i].data==v)return i;}
void create(algraph &g){int i,j,k;char v1,v2;arcnode *p;cin>>g.vexnum>>g.arcnum;for(i=0; i<g.vexnum; i++){
cin>>g.vertices[i].data;
g.vertices[i].firstarc=NULL;}for(k=0; k<g.vexnum; k++){
cin>>v1>>v2;i=locatevex(g,v1);j=locatevex(g,v2);p=new arcnode;p->adjvex=j;p->nextarc=g.vertices[i].firstarc;g.vertices[i].firstarc=p;}}
void output(algraph &g){
int i;arcnode *p;for(i=0; i<g.vexnum; i++){cout<<i<<':';cout<<g.vertices[i].data<<" ";p=g.vertices[i].firstarc;while(p){cout<<p->adjvex<<" ";p=p->nextarc;}cout<<endl;}}void DFS(algraph g,int v1,int visit[]){int i=0,w;arcnode *p;cout<<g.vertices[v1].data<<" ";visit[v1]=1;p=g.vertices[v1].firstarc;while(p!=NULL){
w=p->adjvex;if(visit[w]!=1)
DFS(g,w,visit);p=p->nextarc;}}int main(){char c;int i;int visit[10];algraph g;
create(g);for(i=0; i<g.vexnum; i++)visit[i]=0;cin>>c;i=locatevex(g,c);output(g);DFS(g,i,visit);}

題目內容:
在有向图的邻接表存储的基础上，试设计算法计算各顶点的度，并输出。

输入输出说明:
输入：
6 6
A B C D E F
A B
A C
B D
C D
D E
C F
输出：
A 0 2 2
B 1 1 2
C 1 2 3
D 2 1 3
E 1 0 1
F 1 0 1

#include 
#include 
#include 
#include 
using namespace std;
typedef struct arcnode
{int adjvex;struct arcnode *nextarc;
} arcnode;
typedef struct vnode
{    char data;arcnode *firstarc;} vnode,adjlist[100];
typedef struct
{adjlist vertices;int vexnum,arcnum;
} algraph;
int locatevex(algraph g,char v)
{int i;for(i=0; i<g.vexnum; i++)if(g.vertices[i].data==v)return i;}
void create(algraph &g){int i,j,k;char v1,v2;arcnode *p;cin>>g.vexnum>>g.arcnum;for(i=0; i<g.vexnum; i++){
cin>>g.vertices[i].data;
g.vertices[i].firstarc=NULL;}for(k=0; k<g.vexnum; k++){
cin>>v1>>v2;i=locatevex(g,v1);j=locatevex(g,v2);p=new arcnode;p->adjvex=j;p->nextarc=g.vertices[i].firstarc;g.vertices[i].firstarc=p;}}
/*(void output(algraph &g){
int i;arcnode *p;for(i=0; iadjvex<<" ";p=p->nextarc;}cout<void output(algraph g)
{int i,j,k=0,count,m,n=0,a[100]={0},b[100]={0},s[200]={0};arcnode *p,*q;for(i=0;i <g.vexnum;i++){count=0;for(j=0;j <g.vexnum;j++){p=g.vertices[j].firstarc;while(p!=NULL){if(p->adjvex==i)count++;p=p->nextarc;}}a[k++]=count;}for(i=0;i<g.vexnum;i++){p=g.vertices[i].firstarc;m=0;while(p!=NULL){m++;p=p->nextarc;}b[n++]=m;}for(i=0;i<g.vexnum;i++){s[i]=a[i]+b[i];}for(i=0;i<g.vexnum;i++){printf("%c %d %d %d\n",g.vertices[i].data,a[i],b[i],s[i]);}
}int main(){char c;int i;int visit[10];algraph g;
create(g);for(i=0; i<g.vexnum; i++)visit[i]=0;cin>>c;//i=locatevex(g,c);output(g);//  DFS(g,i,visit);}

題目內容:
以有向图的邻接表为基础实现输出它的拓扑排序序列。

输入输出说明:
输入：
12 16
c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12
c1 c4
c1 c2
c1 c3
c1 c12
c4 c5
c2 c3
c3 c5
c3 c7
c5 c7
c3 c8
c9 c12
c9 c10
c10 c12
c9 c11
c11 c6
c6 c8
输出：
c9 c10 c11 c6 c1 c4 c2 c3 c5 c7 c8 c12

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define m 20
//typedef char VertexType;
//typedef char InfoArc;
//typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef struct ArcNode
{int adjvex;// int value;struct ArcNode *nextarcs;
} ArcNode;
typedef struct VNode
{char data[3];ArcNode *firstarc;
} VNode, AdjList[m];
typedef struct
{AdjList vertices;int vexnum,arcnum;
} ALGraph;int visited[m];
int indegree[m];
void CreatGraph(ALGraph &G)
{ArcNode *p,*q;int i,j,flag1,flag2,value;VNode v1,v2;scanf("%d%d",&G.vexnum,&G.arcnum);getchar();for(i=0; i<G.vexnum; i++){scanf("%s ",G.vertices[i].data);G.vertices[i].firstarc = NULL;}for(i=0; i<G.arcnum; i++){flag1=flag2=-1;scanf("%s %s",v1.data,v2.data);getchar();for(j=0; j<G.vexnum; j++){if(G.vertices[j].data[0] == v1.data[0])if(G.vertices[j].data[1] == v1.data[1])if(G.vertices[j].data[2] == v1.data[2])flag1 = j;if(G.vertices[j].data[0] == v2.data[0])if(G.vertices[j].data[1] == v2.data[1])if(G.vertices[j].data[2] == v2.data[2])flag2 = j;}if(flag1==-1||flag2==-1){printf("Input error!\n");exit(-1);}else{p = (ArcNode *)malloc(sizeof(ArcNode));p->nextarcs = NULL;p->adjvex = flag2;q = G.vertices[flag1].firstarc;indegree[flag2]++;if(q == NULL)G.vertices[flag1].firstarc = p;else{p->nextarcs = G.vertices[flag1].firstarc;G.vertices[flag1].firstarc = p;}}}
}int FirstAdjVex(ALGraph &G, int v)
{if(G.vertices[v].firstarc==NULL)return -1;elsereturn G.vertices[v].firstarc->adjvex;
}
int NextAdjVex(ALGraph &G, int v, int w)
{ArcNode *p = G.vertices[v].firstarc;while(p->adjvex!=w){p = p->nextarcs;}if(p->nextarcs!=NULL)return p->nextarcs->adjvex;elsereturn -1;
}int TopologicalSort(ALGraph G, int *topo)
{stack<int> S;int i,k,n=0;ArcNode *p;for(i=0; i<G.vexnum; i++)if(indegree[i]==0)S.push(i);while(!S.empty()){i = S.top();S.pop();topo[n] = i;n++;p = G.vertices[i].firstarc;while(p!=NULL){k = p->adjvex;--indegree[k];if(indegree[k]==0)S.push(k);p = p->nextarcs;}}if(n<G.vexnum)return -1;elsereturn 1;
}int main()
{ALGraph G;int topo[m];for(int i=0; i<m; i++)indegree[i] = 0;CreatGraph(G);int flag = TopologicalSort(G,topo);for(int i=0; i<G.vexnum; i++)cout<<G.vertices[topo[i]].data<<" ";return 0;
}

題目內容:
采用邻接表存储实现无向图的广度优先遍历。

输入输出说明:
输入：
12 16
c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12
c1 c4
c1 c2
c1 c3
c1 c12
c4 c5
c2 c3
c3 c5
c3 c7
c5 c7
c3 c8
c9 c12
c9 c10
c10 c12
c9 c11
c11 c6
c6 c8
输出：
c1 c12 c3 c2 c4 c10 c9 c8 c7 c5 c11 c6

#include 
#include 
#include 
#include 
using namespace std;
typedef struct ArcNode
{int adjvex;struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode
{char data[10];ArcNode * firstarc;
}VNode,Adjlist[100];
typedef struct
{Adjlist vertices;int vexnum,arcnum;
}ALGraph;
int LocateVex(ALGraph G,char v[10])
{for(int i=0;i<G.vexnum;i++)if(strcmp(v,G.vertices[i].data)==0)return i;return -1;
}
void creat(ALGraph &G)
{cin>>G.vexnum>>G.arcnum;int i,k,j;char v1[10],v2[10];ArcNode * p1,*p2;for(i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}for(k=0;k<G.arcnum;k++){cin>>v1>>v2;i=LocateVex(G,v1);j=LocateVex(G,v2);p1=new ArcNode;p1->adjvex=j;p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;p2=new ArcNode;p2->adjvex=i;p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;}
}
typedef struct
{char k[100];int front;int rear;
}SqQueue;void InItQueue(SqQueue &q)
{q.front=q.rear=0;
}
void EnQueue(SqQueue &q,int e)
{q.rear=(q.rear+1)%100;q.k[q.rear]=e;
}
void DeQueue(SqQueue &q,int &e)
{q.front=(q.front+1)%100;e=q.k[q.front];
}
int QueueEmpty(SqQueue q)
{if(q.front==q.rear)return 1;elsereturn 0;
}
int visited[100];
void bfs(ALGraph G,int n)
{SqQueue q;int u;printf("%s ",G.vertices[n].data);visited[n]=1;InItQueue(q);EnQueue(q,LocateVex(G,G.vertices[n].data));ArcNode*p;while(!QueueEmpty(q)){DeQueue(q,u);p=G.vertices[u].firstarc;while(p!=NULL){if(!visited[p->adjvex]){visited[p->adjvex]=1;EnQueue(q,p->adjvex);printf("%s ",G.vertices[p->adjvex].data);}p=p->nextarc;}}
}
int main()
{ALGraph G;creat(G);int k;for(k=0;k<100;k++)visited[k]=0;bfs(G,0);return 0;
}

題目內容:
采用邻接表存储实现无向图的深度优先非递归遍历。

输入输出说明:
输入：
12 16
c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12
c1 c4
c1 c2
c1 c3
c1 c12
c4 c5
c2 c3
c3 c5
c3 c7
c5 c7
c3 c8
c9 c12
c9 c10
c10 c12
c9 c11
c11 c6
c6 c8
输出
c1 c12 c10 c9 c11 c6 c8 c3 c7 c5 c4 c2

#include 
#include 
#include 
#include 
using namespace std;
typedef struct ArcNode
{int adjvex;struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode
{char data[10];ArcNode * firstarc;
}VNode,Adjlist[100];
typedef struct
{Adjlist vertices;int vexnum,arcnum;
}ALGraph;
int LocateVex(ALGraph G,char v[10])
{for(int i=0;i<G.vexnum;i++)if(strcmp(v,G.vertices[i].data)==0)return i;return -1;
}
void creat(ALGraph &G)
{cin>>G.vexnum>>G.arcnum;int i,k,j;char v1[10],v2[10];ArcNode * p1,*p2;for(i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}for(k=0;k<G.arcnum;k++){cin>>v1>>v2;i=LocateVex(G,v1);j=LocateVex(G,v2);p1=new ArcNode;p1->adjvex=j;p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;p2=new ArcNode;p2->adjvex=i;p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;}
}
typedef struct
{int k[100];int top;
}SqQueue;void InItQueue(SqQueue &q)
{q.top=-1;
}
void EnQueue(SqQueue &q,int e)
{q.top=q.top+1;q.k[q.top]=e;
}
void DeQueue(SqQueue &q,int &e)
{e=q.k[q.top];q.top=q.top-1;}
int QueueEmpty(SqQueue q)
{if(q.top==-1)return 1;elsereturn 0;
}
int visited[100];
void dfs(ALGraph G,int n)
{SqQueue q;int u;printf("%s ",G.vertices[n].data);visited[n]=1;int v;InItQueue(q);EnQueue(q,n);ArcNode*p;while(!QueueEmpty(q)){DeQueue(q,u);p=G.vertices[u].firstarc;while(p!=NULL){v=p->adjvex;if(!visited[v]){printf("%s ",G.vertices[p->adjvex].data);visited[v]=1;EnQueue(q,p->adjvex);break;}elsep=p->nextarc;}}
}
void Dfs(ALGraph G)
{for(int i=0;i<G.vexnum;i++)if(!visited[i])dfs(G,i);
}
int main()
{ALGraph G;creat(G);int k;for(k=0;k<100;k++)visited[k]=0;Dfs(G);return 0;
}

查找

題目內容:
试编写实现有序表折半查找算法。

输入输出说明:
输入：
1 2 3 4 5 6 7 8 9 0
4
输出：
4

#include 
#include 
#include 
using namespace std;
typedef struct
{int a[100];int length;
}node;
int create(node &s)
{int m;s.length=0;scanf("%d",&m);while(m!=0){s.a[s.length]=m;s.length++;scanf("%d",&m);}return 1;
}
int search(node &s,int k)
{int l,h,m;l=1,h=s.length;while(l<=h){m=(l+h)/2;if(k==s.a[m]) return m;else if(k<=s.a[m]) h=m-1;else l=m+1;}return 0;
}
int main()
{node s;int k,c;create(s);scanf("%d",&k);c=search(s,k);printf("%d\n",c+1);return 0;
}

題目內容:
随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键字元素。

输入输出说明:
输入：
1 5 4 2 3 6 8 7 9 11 14 13 12 16 19
输出：
1 2 3 4 5 6 7 8 9 11 12 13 14 16 19
输入：
19
输出：
查找成功！
输入：
14
输出：
1 2 3 4 5 6 7 8 9 11 12 13 19 16

#include 
#include 
#include 
using namespace std;typedef struct bstnode
{int key;struct bstnode *lchild,*rchild;
} bstnode,*bstree;void insert_bst(bstnode *&t,int key)
{bstree x;if(!t){x=new bstnode;x->key=key;x->lchild=x->rchild=NULL;t=x;}else{if(t->key==key)return;else if(key<t->key) insert_bst(t->lchild,key);else insert_bst(t->rchild,key);}}
bstnode* creactbst()
{int key,i;char c;bstnode *t;t=NULL;cin>>key;i=0;while(i<15){insert_bst(t,key);cin>>key;i++;}return t;
}void delete_bst(bstree &t,int key)
{bstnode *p,*f,*q,*s;p=t;f=NULL;while(p){if(p->key==key) break;f=p;if(p->key>key) p=p->lchild;else p=p->rchild;}if(p==NULL) return;q=p;if((p->lchild)&&(p->rchild)){s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->key=s->key;if(q!=p) q->rchild=s->lchild;else q->lchild=s->lchild;delete s;return;}else if(!p->rchild)p=p->lchild;else p=p->rchild;
}void inordertraverse(bstnode *t)
{if(t!=NULL){inordertraverse(t->lchild);cout<<t->key<<" ";inordertraverse(t->rchild);}}void search_bst(bstree t,int key)
{if(key==t->key)printf("查找成功！\n");else if(key<t->key) return search_bst(t->lchild,key);else return search_bst(t->rchild,key);
}
int main()
{bstnode *t;t=creactbst();inordertraverse(t);cout<<endl;int x;cin>>x;search_bst(t,x);cin>>x;delete_bst(t,x);inordertraverse(t);
}

題目內容:
已知散列函数为H(key)=key%p（p为自定的常数），冲突处理方法分别为线性探测法实现散列表的建立（利用插入算法实现）。

输入输出说明:
输入：
19 14 23 1 68 20 84 27 55 11 10 79 0
输出：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 14 1 68 27 55 19 20 84 79 23 11 10 0 0

#include 
#include 
#include 
#include 
using namespace std;
int main()
{int p=13,x;int flag[15];int key;int i=0,j;int a[15];for(i=0; i<15; i++){flag[i]=0;a[i]=0;}cin>>x;while(x!=0){key=x%p;if(flag[key]==0){a[key]=x;flag[key]=1;}else{while(flag[key]!=0){key=(key+1+14)%14;}a[key]=x;flag[key]=1;}cin>>x;}for(i=0; i<15; i++)cout<<i<<"  ";cout<<endl;for(i=0; i<15; i++)cout<<a[i]<<"  ";}

題目內容:
已知散列函数为H(key)=key%p（p为自定的常数），冲突处理方法分别为线性探测法、外拉链法实现散列表的建立（利用插入算法实现）。

输入输出说明:
输入：
19 14 23 1 68 20 84 27 55 11 10 79 0
输出：
0
1 1 14 27 79
2
3 55 68
4
5
6 19 84
7 20
8
9
10 10 23
11 11
12

#include 
#include 
#include 
#include 
using namespace std;
typedef struct node
{int data;struct node *next;
} node;int main()
{node a[13];int i;int x;int key;node *p,*q,*s;for(i=0; i<13; i++){a[i].data=i;a[i].next=NULL;}cin>>x;while(x!=0){key=x%13;s=new node;s->data=x;p=a[key].next;if(p!=NULL){if(p->data>x){a[key].next=s;s->next=p;}else{q=p->next;while(q!=NULL){if(q->data<x){p=q;q=q->next;}}s->next=p->next;p->next=s;}}else{s->next=NULL;a[key].next=s;}cin>>x;}for(i=0; i<13; i++){cout<<"  "<<a[i].data<<" ";p=a[i].next;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;}
}

排序

題目內容:
试设计算法实现冒泡排序。

输入输出说明:
输入：
2 4 3 9 6 8 7 5 1 0
输出：
1 2 3 4 5 6 7 8 9

#include 
#include 
using namespace std;
int main()
{int a[100],i=0,j,m=0,n,t;
scanf("%d",&n);
while(n)
{a[i++]=n;scanf("%d",&n);m++;
}for(i=0;i<m;i++){for(j=i+1;j<m;j++){if(a[j]<a[i]){t=a[i];a[i]=a[j];a[j]=t;}}}for(i=0;i<m;i++){printf("%d ",a[i]);}printf("\n");return 0;
}

題目內容:
试设计算法实现直接插入排序

输入输出说明:
输入：
2 5 3 4 8 7 9 6 1 0
输出：
1 2 3 4 5 6 7 8 9

#include 
#include 
using namespace std;
int main()
{int a[100],i=0,j,m=0,n,t;
scanf("%d",&n);
while(n)
{a[i++]=n;scanf("%d",&n);m++;
}for(i=1;i<m;i++){for(j=0;j<i;j++){if(a[j]>a[i]){t=a[i];a[i]=a[j];a[j]=t;}}}for(i=0;i<m;i++){printf("%d ",a[i]);}printf("\n");return 0;
}

題目內容:
试设计算法实现简单选择排序。

输入输出说明:
输入：
7 4 3 5 2 1 8 9 0
输出：
1 2 3 4 5 7 8 9

#include 
#include 
using namespace std;
int main()
{int a[100],i=0,j,m=0,n,t,k;
scanf("%d",&n);
while(n)
{a[i++]=n;scanf("%d",&n);m++;
}
t=0;
for(i=0;i<m;i++)
{k=i;for(j=m-1;j>i;j--){if(a[j]<a[k]){k=j;}}t=a[i];a[i]=a[k];a[k]=t;
}for(i=0;i<m;i++){printf("%d ",a[i]);}printf("\n");return 0;
}

題目內容:
试编写算法，实现希尔排序。

输入输出说明:
输入：
1 8 4 6 7 9 5 3 2 0
输出：
1 2 3 4 5 6 7 8 9

#include 
#include 
using namespace std;
int main()
{int a[100],i=0,j,m=0,n,t,k;scanf("%d",&n);while(n){a[i++]=n;scanf("%d",&n);m++;}t=m/2;for(t; t>0; t/=2){for(i=t; i<m; i++){k=a[i];for(j=i-t; j>=0&&k<a[j]; j-=t){a[j+t]=a[j];}a[j+t]=k;}}for(i=0; i<m; i++){printf("%d ",a[i]);}printf("\n");return 0;
}

題目內容:
试编写算法实现快速排序算法。

输入输出说明:
输入：
1 9 8 5 7 6 4 3 2 0
输出：
1 2 3 4 5 6 7 8 9

#include 
#define maxsize 20
using namespace std;typedef int keytype;
typedef struct
{keytype key[maxsize];int length;
} lnode,*list;void bobblesort(lnode &l);//冒泡排序
void insertsort(lnode &l);//直接插入法
void shellinsert(lnode &l);//希尔插入
void shellsort(lnode &l,int dt[],int t);//希尔排序
void selectsort(lnode &l);//简单选择排序
int partition(lnode &l,int low,int high);//一趟快速排序
void qsort(lnode &l,int low,int high);//递归快速排序
void quicksort(lnode &l);//快速排序void creact(lnode &l)
{int x;cin>>x;l.length=1;while(x!=0){l.key[l.length]=x;l.length++;cin>>x;}
}void read(lnode l)
{int i;for(i=2; i<=l.length; i++)cout<<l.key[i]<<" ";cout<<endl;
}
int main()
{int t,dk[10];lnode l;creact(l);quicksort(l);read(l);
}int partition(lnode &l,int low,int high)
{int pivotkey;l.key[0]=l.key[low];pivotkey=l.key[0];while(low<high){while(low<high&&l.key[high]>=pivotkey) --high;l.key[low]=l.key[high];while(low<high&&l.key[low]<=pivotkey) ++low;l.key[high]=l.key[low];}l.key[low]=l.key[0];return low;
}void qsort(lnode &l,int low,int high)
{int pivotloc;if(low<high){pivotloc=partition(l,low,high);qsort(l,low,pivotloc-1);qsort(l,pivotloc+1,high);}}void quicksort(lnode &l)
{qsort(l,1,l.length);
}

題目內容:
试编写算法实现堆排序算法。

输入输出说明:
输入：
1 9 8 5 7 6 4 3 2 0
输出：
1 2 3 4 5 6 7 8 9

#include 
#define maxsize 20
using namespace std;typedef int keytype;
typedef struct
{keytype key[maxsize];int length;
} lnode,*list;void bobblesort(lnode &l);//冒泡排序
void insertsort(lnode &l);//直接插入法
void shellinsert(lnode &l);//希尔插入
void shellsort(lnode &l,int dt[],int t);//希尔排序
void selectsort(lnode &l);//简单选择排序
int partition(lnode &l,int low,int high);//快速排序 找枢轴位置
void qsort(lnode &l,int low,int high);//递归快速排序
void quicksort(lnode &l);//快速排序
void heapadjust(lnode &l,int s,int m);//筛选法调整堆
void creactheap(lnode &l);//建初堆
void heapsort(lnode &l);//堆排序void creact(lnode &l)
{int x;cin>>x;l.length=1;while(x!=0){l.key[l.length]=x;l.length++;cin>>x;}
}void creactheap(lnode &l)
{int n,i;n=l.length;for(i=n/2;i>0;i--)heapadjust(l,i,n);
}void read(lnode l)
{int i;for(i=2; i<=l.length; i++)cout<<l.key[i]<<" ";cout<<endl;
}
int main()
{int t,dk[10];lnode l;creact(l);heapsort(l);//quicksort(l);//selectsort(l);//read(l);//insertsort(l);// bobblesort(l);/* t=0;dk[t]=l.length/2;while(dk[t]!=0){t++;dk[t]=dk[t-1]/2;cout<read(l);}void heapadjust(lnode &l,int s,int m)//筛选法调整堆
{int j,rc;rc=l.key[s];for(j=s*2;j<=m;j=j*2){if(j<m&&l.key[j]<l.key[j+1]) j++;if(rc>=l.key[j]) break;l.key[s]=l.key[j];s=j;}l.key[s]=rc;
}void heapsort(lnode &l)
{int i,x;creactheap(l);for(i=l.length;i>1;--i){x=l.key[1];l.key[1]=l.key[i];l.key[i]=x;heapadjust(l,1,i-1);}
}

平时作业

題目內容:
将两个递增有序的单链表合并成一个递增有序的单链表，要求利用原表空间（注意重复值只保留一个）。输出合并后的单链表。设数据结点的值域为整型

输入说明：

输入n个有序的整数（无重复值），以0做结束，分别创建单链表A和B；

输出说明：

输出合并后的单链表，数据之间用一个空格分隔。

输入输出说明:
输入：
3 5 7 9 0
3 4 5 6 7 0
输出：
3 4 5 6 7 9

#include 
#include
#include 
using namespace std;
typedef int elemtype;
typedef struct node
{elemtype data;struct node*next;
}lnode,*linklist;void createhead(linklist &l)
{l=new lnode;l->next=NULL;int x;linklist p,r;p=new lnode;r=l;scanf("%d",&x);while(x!=0){p=new lnode;p->data=x;p->next=NULL;r->next=p;r=p;scanf("%d",&x);}
}
void output(linklist l)
{linklist p=l->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");
}void mergelist(linklist &la,linklist &lb,linklist &lc)
{linklist pa=la->next;linklist pb=lb->next;linklist pre;lc=la;la->next=NULL;while(pa&&pb){if(pa->data <= pb->data){pre=pa->next;pa->next=la->next;la->next=pa;pa=pre;}else{pre=pb->next;pb->next=la->next;la->next=pb;pb=pre;}}while(pa){pre=pa->next;pa->next=la->next;la->next=pa;pa=pre;}while(pb){pre=pb->next;pb->next=la->next;la->next=pb;pb=pre;}free(lb);}
void del(linklist &l)
{lnode *p=l->next,*q,*p1,*t;while(p!=NULL){q=p;p1=q->next;while(p1!=NULL){if(p1->data==p->data){t=p1->next;q->next=t;free(p1);p1=t;}else{q=p1;p1=p1->next;}}p=p->next;}
}
int length(linklist l)
{int n=0;linklist p=l->next;while(p){p=p->next;n++;}return n;
}
lnode *sortlist (lnode *phead)
{lnode *p;if(phead->next==NULL){return phead;}int n,i,j;n=length(phead);for(i=1;i<n;i++){p=phead->next;for(j=1;j<n;j++){if(p->data > p->next->data){elemtype t=p->data;p->data=p->next->data;p->next->data=t;}p=p->next;}}return phead;
}
int main()
{linklist la,lb,lc;createhead(la);createhead(lb);mergelist(la,lb,lc);del(lc);linklist p= sortlist(lc);output(p);return 0;
}

題目內容:
利用栈的运算，实现一个表达式（以#结束）中括号的匹配算法：括号只含有｛｝，（），[ ]。匹配输出1，否则输出0。

输入格式：

1+(2+3)[36]/{4+5}+{[8*7]}#

输出：

1

输入输出说明:
输入格式：
1+(2+3)[36]/{4+5}+{[8*7]}#
输出：
1

#include 
#include 
#define MAXSIZE 30
typedef struct
{char data[MAXSIZE];int top;
}mystack_char;void Init(mystack_char *a)
{a->top=-1;
}
int  push(mystack_char *a,char x)
{if(a->top==MAXSIZE-1) return 0;a->data[++a->top]=x;return 1;
}
int pop(mystack_char *a)
{if(a->top==-1) return 0;a->top--;return 1;
}
int empty(mystack_char *a)
{return a->top==-1;
}
char top(mystack_char *a)
{if(a->top==-1) return -1;return a->data[a->top];
}
int match()
{char c;mystack_char p;Init(&p);while((c=getchar())!='#'){switch(c){case '(' :push(&p,c);break;case '[' :push(&p,c);break;case '{' :push(&p,c);break;case ')' :if(top(&p)!='('||empty(&p))return 0;pop(&p);break;case ']' :if(top(&p)!='['||empty(&p))return 0;pop(&p);break;case '}' :if(top(&p)!='{'||empty(&p))return 0;pop(&p);break;}}if(!empty(&p)) return 0;return 1;
}
int main()
{printf("%d\n",match());return 0;
}

題目內容:
在二叉链表表示的二叉树中（值域为字符型），查找值为x的结点的所有祖先结点并输出。

输入说明：

利用二叉树的先序递归创建二叉树，键盘输入字符序列，已*代表空结点，中间不允许有重复的值，建立二叉树，接着输入字符x。

输出说明：

若x为根，输出：没有祖先结点。

若x不存在，则输出：x不存在；

否则，依次输出x的祖先结点，从离x最近的父节点开始，输出到根节点，数据之间用一个空格分隔。

注意：此处的输入请采用C++模式，用cin来接收数据。

输入输出说明:
输入：
ABDE*FC**
F
输出：
E B A

#include 
#include 
char q[20];
typedef struct BiTree
{char data;struct BiTree *lchild,*rchild;
} BiTree;
BiTree *create()
{BiTree *T;char c;scanf("%c",&c);if(c=='*') T=NULL;else{T=(BiTree *)malloc(sizeof(BiTree));T->data=c;T->lchild=create();T->rchild=create();}return T;
}
void fun(BiTree *T,char x,int n)
{int i;if(T==NULL) return;if(T->data==x){for(i=n-1;i>=0;i--)printf("%c ",q[i]);return ;}else{q[n]=T->data;fun(T->lchild,x,n+1);fun(T->rchild,x,n+1);}
}
void search(BiTree *T,char x)
{if(T==NULL) return;if(T->lchild==NULL&&T->rchild==NULL) {printf("无祖先结点。\n"); return;}fun(T,x,0);
}
int main()
{char x;BiTree *T;T=create();scanf(" %c",&x);search(T,x);return 0;
}

題目內容:
在用邻接表存储的有向图G中（结点的编号从1到n），利用深度优先或广度优先算法判断结点i到j之间是否存在路径。是返回1，否返回0。

输入：

首先输入图的顶点个数m和边的数目n

接着输入n条边，用i，j的格式输入。

之后输入顶点i和j

输出：

输出i到j是否存在路径，是则输出1，否则输出0。

输入输出说明:
输入：
5 4
1,2
2,3
2,4
2,5
3 5
输出：
0

#include 
#include 
#define MAX 100
int TF[MAX];
typedef struct P {int x; struct P *next;}Bianji;
typedef struct {int dian; Bianji *next; }Dianji;
typedef struct
{Dianji dianji[MAX];int bianshu,dianshu;
} Graph2;
void chushihua2(Graph2 *p)
{int i;p->bianshu=p->dianshu=0;for(i=0;i<MAX;i++)p->dianji[i].next=NULL;
}
Graph2 chuangjian2()
{Graph2 p;chushihua2(&p);Bianji *q1;int i,j,m,n,x,y;scanf("%d%d",&i,&j);p.bianshu=j;p.dianshu=i;for(i=0;i<p.dianshu;i++)p.dianji[i].dian=i+1;for(i=0;i<p.bianshu;i++){scanf("%d,%d",&x,&y);m=n=0;while(p.dianji[m].dian!=x) m++;while(p.dianji[n].dian!=y) n++;q1=(Bianji *)malloc(sizeof(Bianji));q1->x=n;q1->next=p.dianji[m].next;p.dianji[m].next=q1;}return p;
}
void digui2(Graph2 p, int v)
{Bianji *q;q=p.dianji[v].next;TF[v]=1;while(q!=NULL){if(TF[q->x]!=1) digui2(p,q->x);q=q->next;}
}
int fun(Graph2 p,int x,int y)
{int i;for(i=0;i<MAX;i++)TF[i]=0;digui2(p,x-1);return TF[y-1];
}
int main()
{int i,j;Graph2 G2;G2=chuangjian2();scanf("%d%d",&i,&j);printf("%d\n",fun(G2,i,j));return 0;
}

題目內容:
在表长为15的哈希表中存储一批整型数据（个数小于等于15），哈希函数采用H（key）=key%13，用闭散列中的线性探测法解决冲突，请输出存储后的哈

希表，格式分为两列：第一列是下标i。第二列是数值x，每行上的数据中间用一个空格分隔，没有存放数据的地方输出-1。

输入数据（以0做结束）：

34 5 75 43 21 66 44 55 0

输出格式如下：

0 -1
1 66
2 -1
3 55
4 43
5 5
6 44
7 -1
8 34
9 21
10 75
11 -1
12 -1

13 -1

14 -1

#include 
#include 
#include 
#include 
using namespace std;
int main()
{int p=13,x;int flag[15];  int key;int i=0,j;int a[15];for(i=0; i<15; i++){flag[i]=0; a[i]=-1;}cin>>x;while(x!=0){key=x%p;if(flag[key]==0){a[key]=x;flag[key]=1;}else{while(flag[key]!=0){key=(key+1+14)%14;}a[key]=x;flag[key]=1;}cin>>x;}for(i=0; i<15; i++){cout<<i<<" "<<a[i]<<endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！