数据结构算法实验考试代码合集

#include <cstdlib> #include <iostream> using namespace std; //定义单链表的接点 typedef struct Node{ int data; struct Node * next; }Nodes; //将两个单调递增链表合并成一个 单调递增链表 void merge(Node * a,Node * b,Node * &c){ Node * p=a->next;//永远指向a的最小的接点 Node * q=b->next; //永远指向b的最小的接点 Node * r;//永远指向c的最后一个接点 c=a; //使用a的头结点 c->next=NULL; free(b);//释放b的头结点 r=c;//当前c的最后一个接点 也是它的第一个接点 while(p!=NULL && q!=NULL){ if((p->data)>(q->data)){ r->next=q; q=q->next; r=r->next; } else{ r->next=p; p=p->next; r=r->next; } } if(p!=NULL) r->next=p;//将a的剩余接点 添加到c的后面 if(q!=NULL) r->next=q;//将b的剩余接点 添加到c的后面 } //将两个单调递增的单链表合并成一个 单调递减的单链表 void mergeDown(Node * a,Node * b,Node * &c){ Node * p=a->next;//永远指向a的最小的接点 Node * q=b->next; //永远指向b的最小的接点 Node * r;//即将插入的接点 c=a; //使用a的头结点 c->next=NULL; free(b);//释放b的头结点 while(p!=NULL && q!=NULL){ if((p->data)>(q->data)){ r=q; q=q->next; r->next=c->next; c->next=r; } else{ r=p; p=p->next; r->next=c->next; c->next=r; } } while(p!=NULL){//将a的剩余接点 添加到c的后面 r=p; p=p->next; r->next=c->next; c->next=r; } while(q!=NULL){//将b的剩余接点 添加到c的后面 r=q;q=q->next; r->next=c->next; c->next=r; } } //创建链表 尾插法 void createList(Node * &node ,int data[],int length){ Node * p;//指向最后一个接点 Node * q;//指向新创建的接点 //创建头结点 node=(Node *)malloc(sizeof(Node)); node->next=NULL; p=node; int i; for(i=1;i<=length;i++){ q=(Node *)malloc(sizeof(Node)); q->data=data[i]; p->next=q; p=q; } p->next=NULL; } //创建链表 头插法 void createListHead(Node * &node ,int data[],int length){ Node * q;//指向新创建的接点 //创建头结点 node=(Node *)malloc(sizeof(Node)); node->next=NULL; int i; for(i=length;i>=1;i--){ q=(Node *)malloc(sizeof(Node)); q->data=data[i]; q->next=node->next; node->next=q; } } //遍历单链表 void showList(Node * node){ Node * p;//指向当前遍历的接点 if(node!=NULL) p=node->next; while(p!=NULL){ printf("%d-->",p->data); p=p->next; } } int main(int argc, char *argv[]) { Node * node=NULL; Node * node2=NULL; Node * node3=NULL; int data[11]; int data2[11]; int i; for(i=1;i<=10;i++){ data[i]=i*i ; } for(i=1;i<=10;i++){ data2[i]=i ; } int length=10; createList(node ,data,length); createListHead(node2 ,data2,length); showList(node); printf("\n"); showList(node2); printf("\n"); merge(node,node2,node3); showList(node3); system("PAUSE"); return EXIT_SUCCESS; }