1．Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x. (Implement exercise 2.3-7.) #include<stdio.h> #include<stdlib.h> void merge(int arr[],int low,int mid,int high){ int i,k; int *tmp=(int*)MALLOC((high-low+1)*sizeof(int)); int left_low=low; int left_high=mid; int right_low=mid+1; int right_high=high; for(k=0;left_low<=left_high&&right_low<=right_high;k++) { if(arr[left_low]<=arr[right_low]){ tmp[k]=arr[left_low++]; } else{ tmp[k]=arr[right_low++]; } } if(left_low<=left_high){ for(i=left_low;i<=left_high;i++){ tmp[k++]=arr[i]; } } if(right_low<=right_high){ for(i=right_low;i<=right_high;i++) tmp[k++]=arr[i]; } for(i=0;i<high-low+1;i++) arr[low+i]=tmp[i]; } void merge_sort(int a[],int p,int r){ int q; if(p<r){ q=(p+r)/2; merge_sort(a,p,q); merge_sort(a,q+1,r); merge(a,p,q,r); } } int main(){ int a[8]={3,5,8,6,4,1,1}; int i,j; int x=10; merge_sort(a,0,6); printf("after Merging-Sort:\n"); for(i=0;i<7;i++){ printf("%d",a[i]); } printf("\n"); i=0;j=6; do{ if(a[i]+a[j]==x){ printf("exist"); break; } if(a[i]+a[j]>x) j--; if(a[i]+a[j]<x) i++; }while(i<=j); if(i>j) printf("not exist"); system("pause"); return 0; }
上传时间： 2017-04-01
上传用户：糖儿水嘻嘻
#include <stdio.h> #include <stdlib.h> ///链式栈 typedef struct node { int data; struct node *next; }Node,*Linklist; Linklist Createlist() { Linklist p; Linklist h; int data1; scanf("%d",&data1); if(data1 != 0) { h = (Node *)MALLOC(sizeof(Node)); h->data = data1; h->next = NULL; } else if(data1 == 0) return NULL; scanf("%d",&data1); while(data1 != 0) { p = (Node *)MALLOC(sizeof(Node)); p -> data = data1; p -> next = h; h = p; scanf("%d",&data1); } return h; } void Outputlist(Node *head) { Linklist p; p = head; while(p != NULL ) { printf("%d ",p->data); p = p->next; } printf("\n"); } void Freelist(Node *head) { Node *p; Node *q = NULL; p = head; while(p != NULL) { q = p; p = p->next; free(q); } } int main() { Node *head; head = Createlist(); Outputlist(head); Freelist(head); return 0; } 2.顺序栈 [cpp] view plain copy #include <iostream> #include <stdio.h> #include <stdlib.h> ///顺序栈 #define MaxSize 100 using namespace std; typedef
上传时间： 2018-05-09
上传用户：123456..
#include <iostream> #include <stdio.head> #include <stdlib.head> #include <string.head> #define ElemType int #define max 100 using namespace std; typedef struct node1 { ElemType data; struct node1 *next; }Node1,*LinkList;//链栈 typedef struct { ElemType *base; int top; }SqStack;//顺序栈 typedef struct node2 { ElemType data; struct node2 *next; }Node2,*LinkQueue; typedef struct node22 { LinkQueue front; LinkQueue rear; }*LinkList;//链队列 typedef struct { ElemType *base; int front,rear; }SqQueue;//顺序队列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 //1．采用链式存储实现栈的初始化、入栈、出栈操作。 LinkList CreateStack()//创建栈 { LinkList top; top=NULL; return top; } bool StackEmpty(LinkList s)//判断栈是否为空，0代表空 { if(s==NULL) return 0; else return 1; } LinkList Pushead(LinkList s,int x)//入栈 { LinkList q,top=s; q=(LinkList)MALLOC(sizeof(Node1)); q->data=x; q->next=top; top=q; return top; } LinkList Pop(LinkList s,int &e)//出栈 { if(!StackEmpty(s)) { printf("栈为空。"); } else { e=s->data; LinkList p=s; s=s->next; free(p); } return s; } void DisplayStack(LinkList s)//遍历输出栈中元素 { if(!StackEmpty(s)) printf("栈为空。"); else { wheadile(s!=NULL) { cout<<s->data<<" "; s=s->next; } cout<<endl; } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 //2．采用顺序存储实现栈的初始化、入栈、出栈操作。 int StackEmpty(int t)//判断栈S是否为空 { SqStack.top=t; if (SqStack.top==0) return 0; else return 1; } int InitStack() { SqStack.top=0; return SqStack.top; } int pushead(int t,int e) { SqStack.top=t; SqStack.base[++SqStack.top]=e; return SqStack.top; } int pop(int t,int *e)//出栈 { SqStack.top=t; if(!StackEmpty(SqStack.top)) { printf("栈为空."); return SqStack.top; } *e=SqStack.base[s.top]; SqStack.top--; return SqStack.top; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 //3．采用链式存储实现队列的初始化、入队、出队操作。 LinkList InitQueue()//创建 { LinkList head; head->rear=(LinkQueue)MALLOC(sizeof(Node)); head->front=head->rear; head->front->next=NULL; return head; } void deleteEle(LinkList head,int &e)//出队 { LinkQueue p; p=head->front->next; e=p->data; head->front->next=p->next; if(head->rear==p) head->rear=head->front; free(p); } void EnQueue(LinkList head,int e)//入队 { LinkQueue p=(LinkQueue)MALLOC(sizeof(Node)); p->data=e; p->next=NULL; head->rear->next=p; head->rear=p; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 //4．采用顺序存储实现循环队列的初始化、入队、出队操作。 bool InitQueue(SqQueue &head)//创建队列 { head.data=(int *)MALLOC(sizeof(int)); head.front=head.rear=0; return 1; } bool EnQueue(SqQueue &head,int e)//入队 { if((head.rear+1)%MAXQSIZE==head.front) { printf("队列已满\n"); return 0; } head.data[head.rear]=e; head.rear=(head.rear+1)%MAXQSIZE; return 1; } int QueueLengthead(SqQueue &head)//返回队列长度 { return (head.rear-head.front+MAXQSIZE)%MAXQSIZE; } bool deleteEle(SqQueue &head,int &e)//出队 { if(head.front==head.rear) { cout<<"队列为空！"<<endl; return 0; } e=head.data[head.front]; head.front=(head.front+1)%MAXQSIZE; return 1; } int gethead(SqQueue head)//得到队列头元素 { return head.data[head.front]; } int QueueEmpty(SqQueue head)//判断队列是否为空 { if (head.front==head.rear) return 1; else return 0; } void travelQueue(SqQueue head)//遍历输出 { wheadile(head.front!=head.rear) { printf("%d ",head.data[head.front]); head.front=(head.front+1)%MAXQSIZE; } cout<<endl; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 //5．在主函数中设计一个简单的菜单，分别测试上述算法。 int main() { LinkList top=CreateStack(); int x; wheadile(scanf("%d",&x)!=-1) { top=Pushead(top,x); } int e; wheadile(StackEmpty(top)) { top=Pop(top,e); printf("%d ",e); }//以上是链栈的测试 int top=InitStack(); int x; wheadile(cin>>x) top=pushead(top,x); int e; wheadile(StackEmpty(top)) { top=pop(top,&e); printf("%d ",e); }//以上是顺序栈的测试 LinkList Q; Q=InitQueue(); int x; wheadile(scanf("%d",&x)!=-1) { EnQueue(Q,x); } int e; wheadile(Q) { deleteEle(Q,e); printf("%d ",e); }//以上是链队列的测试 SqQueue Q1; InitQueue(Q1); int x; wheadile(scanf("%d",&x)!=-1) { EnQueue(Q1,x); } int e; wheadile(QueueEmpty(Q1)) { deleteEle(Q1,e); printf("%d ",e); } return 0; }
上传时间： 2018-05-09
上传用户：123456..
#include <stdio.h> #include <stdlib.h> #define SMAX 100 typedef struct SPNode { int i,j,v; }SPNode; struct sparmatrix { int rows,cols,terms; SPNode data [SMAX]; }; sparmatrix CreateSparmatrix() { sparmatrix A; printf("\n\t\t请输入稀疏矩阵的行数，列数和非零元素个数（用逗号隔开）:"); scanf("%d,%d,%d",&A.cols,&A.terms); for(int n=0;n<=A.terms-1;n++) { printf("\n\t\t输入非零元素值（格式：行号，列号，值）:"); scanf("%d,%d,%d",&A.data[n].i,&A.data[n].j,&A.data[n].v); } return A; } void ShowSparmatrix(sparmatrix A) { int k; printf("\n\t\t"); for(int x=0;x<=A.rows-1;x++) { for(int y=0;y<=A.cols-1;y++) { k=0; for(int n=0;n<=A.terms-1;n++) { if((A.data[n].i-1==x)&&(A.data[n].j-1==y)) { printf("%8d",A.data[n].v); k=1; } } if(k==0) printf("%8d",k); } printf("\n\t\t"); } } void sumsparmatrix(sparmatrix A) { SPNode *p; p=(SPNode*)MALLOC(sizeof(SPNode)); p->v=0; int k; k=0; printf("\n\t\t"); for(int x=0;x<=A.rows-1;x++) { for(int y=0;y<=A.cols-1;y++) { for(int n=0;n<=A.terms;n++) { if((A.data[n].i==x)&&(A.data[n].j==y)&&(x==y)) { p->v=p->v+A.data[n].v; k=1; } } } printf("\n\t\t"); } if(k==1) printf("\n\t\t对角线元素的和：:%d\n",p->v); else printf("\n\t\t对角线元素的和为：:0"); } int main() { int ch=1,choice; struct sparmatrix A; A.terms=0; while(ch) { printf("\n"); printf("\n\t\t 稀疏矩阵的三元组系统 "); printf("\n\t\t*********************************"); printf("\n\t\t 1------------创建 "); printf("\n\t\t 2------------显示 "); printf("\n\t\t 3------------求对角线元素和"); printf("\n\t\t 4------------返回 "); printf("\n\t\t*********************************"); printf("\n\t\t请选择菜单号（0-3）:"); scanf("%d",&choice); switch(choice) { case 1: A=CreateSparmatrix(); break; case 2: ShowSparmatrix(A); break; case 3: SumSparmatrix(A); break; default: system("cls"); printf("\n\t\t输入错误！请重新输入！\n"); break; } if (choice==1||choice==2||choice==3) { printf("\n\t\t"); system("pause"); system("cls"); } else system("cls"); } }
上传时间： 2020-06-10
上传用户：ccccy
