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;
}
標簽：
c語言
算法
排序
上傳時間：
2017-04-01
上傳用戶：糖兒水嘻嘻
#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-11
上傳用戶：ccccy
