数据结构实验——查找算法C语言_数据结构查找算法c语言

以下是通过链表进行排序查找：
涉及 顺序查找、二分查找、快速排序

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1000

struct LNode{
	int Data[MAXSIZE];  //Data为待排序序列数组 
	int Last;  //Last为最后一个元素的数组下标 
}; 
typedef struct LNode *List; 

List Create()
{
	List L;
	L = (List)malloc(sizeof(struct LNode));
	int i,j = 1,ch; 
	printf("请输入需要处理的数字，按Ctrl+Z结束:\n");
	while(scanf("%d",&ch)!=EOF)
	{ 
		L->Data[j] = ch;
		j++;
	}
	L->Last = j-1;
	return L;
}

//输出顺序表
void PrintList(List L)
{
	int i;
	for(i=1;i <= L->Last;i++)
	{
		printf("Data[%d]=%d\n",i,L->Data[i]);
	}
 } 

//顺序查找
int SeqSearch(List L,int K)
{
	L->Data[0]=0;
	for(int i = 1;i <= L->Last;i++){
		if(L->Data[i] == K){
			L->Data[0]=i;
			break;
		}
	}
	return L->Data[0];
} 

//二分查找
int BinSearch(List L,int K)
{
	L->Data[0]=0;
	int	Low = 1,High = L->Last,mid;
	while(Low<=High){
		mid=(Low+High)/2;
		if(L->Data[mid] == K){
			L->Data[0]=mid;
			break;
		}
		if(K>L->Data[mid]){
			Low=mid+1;
		}
		if(K<L->Data[mid]){
			High=mid-1;
		}
	}
	return L->Data[0];
}

void swap(int *a,int *b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;	
}

//快速排序 
void quicksort(List L,int low,int high){
	int left = low;
    int right  = high;
    int key = L->Data[left];
    if(low >= high)
        return;
    while(left < right)
    {
        while(left < right && L->Data[right] > key) right--;
        L->Data[left] = L->Data[right];
        while(left < right && L->Data[left] < key) left++;
        L->Data[right] = L->Data[left];
    }
    L->Data[left] = key;

    quicksort(L, low, left-1);
    quicksort(L, left+1, high);
}
int main()
{
	int n,i;
	List L = Create();

	printf("所创建的顺序表为：\n");
	PrintList(L);
	
	//顺序查找
	int  key,index;
	printf("\n请输入你要查找的元素key（顺序查找）：");
	scanf("%d",&key);
	index = SeqSearch(L,key);
	if(index == 0)
	{
		printf("查找失败,元素%d不在顺序表内\n",key);
	}else{
		printf("查找成功，您要查找的%d在顺序表中的第%d个位置\n",key,index);
	}	
	
	//快速排序
	quicksort(L,1,L->Last);     
	printf("\n对未排序序列进行快速排序的结果为：");		
	for(i=1;i<=L->Last;i++)
	printf("%d ",L->Data[i]);
	
	//二分查找
	int key1,index1; 
	printf("\n请输入您要查找的元素key（二分查找）:");
	scanf("%d",&key1);
	
	index1 = BinSearch(L,key1);
	if(index1 == 0)
	{
		printf("查找失败，元素%d不在顺序表内",key1); 
	}
	else
	{
		printf("查找成功，您要查找的%d在顺序表中的第%d个位置",key1,index1);
	} 
	
    return 0;
} 
/*
85 12 59 36 62 43 94 7 35 52 44
^Z
*/
/*调试
请输入需要处理的数字，按Ctrl+Z结束:
85 12 59 36 62 43 94 7 35 52 44
^Z
所创建的顺序表为：
Data[1]=85
Data[2]=12
Data[3]=59
Data[4]=36
Data[5]=62
Data[6]=43
Data[7]=94
Data[8]=7
Data[9]=35
Data[10]=52
Data[11]=44

请输入你要查找的元素key（顺序查找）：52
查找成功，您要查找的52在顺序表中的第10个位置

对未排序序列进行快速排序的结果为：44 12 35 36 7 43 52 62 59 85 94
请输入您要查找的元素key（二分查找）:
*/
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166