本文目录一览：
c语言排序和查找？
1）利用readData()函数从data1.txt中读入不同规模的数据存入数组，编写基于数组的顺序查找算法，测试数据量为1万、5万、10万、20万、30万、40万和50万时的数据查询时间。
算法代码如下：
int seqsearch(int a[], int n, int key) {
int k = n - 1;
while (k >= 0 && a[k] != key)
k--;
return (k);
}
2）利用readData()函数从data2.txt中读入不同规模的有序数据存入数组，编写基于数组的二分查找算法，测试数据量为1万、5万、10万、20万、30万、40万和50万时的数据查询时间。
算法代码如下：
int binSearch(int a[], int n, int key) {
int low = 0;
int high = n - 1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == key)
return mid;
if (a[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
3）请设计冒泡排序算法函数void bubbleSort(int a[], int n)，对a[1]..a[n]进行升序排序。并测试在不同数据规模下的排序效率。
算法代码如下：
void bubbleSort(int a[], int n) {
int i = 1, j, flag = 1;
while (i <= n - 1 && flag) {
flag = 0;
for (j = 1; j <= n - 1 - i; j++)
if (a[j + 1] < a[j]) {
a[0] = a[j];
a[j] = a[j + 1];
a[j + 1] = a[0];
flag = 1;
}
i++;
}
}
C 语言编程 （顺序线性表）
#ifndef FUNS_H
#define FUNS_H
void error(char *, ...); /* 输出错误信息，退出程序 */
void flush_stdin(void); /* 清空“输入缓冲区” */
#endif
#ifndef SQLIST_H
#define SQLIST_H
#define INITSIZE 100 /* 顺序表初始空间分配量 */
#define INCREMENT 10 /* 顺序表空间分配增量 */
typedef int ElemType; /* 声明ElemType代表的数据类型 */
/* 定义顺序表结构 */
typedef struct {
ElemType *elem; /* 存储空间基址 */
unsigned length; /* 当前长度 */
unsigned listsize; /* 当前空间分配量 */
} Sqlist;
/* 函数声明 */
int InitList(Sqlist *);
int InputList(Sqlist *);
int InsertList(Sqlist *, unsigned);
void DelList(Sqlist *, unsigned, unsigned);
int Union(Sqlist *, Sqlist *);
void Purge(Sqlist *);
void Purge2(Sqlist *);
void Bubble(Sqlist *, unsigned);
int Compare(Sqlist *, Sqlist *);
void Exchange(Sqlist *, unsigned);
int Location(Sqlist *, ElemType);
void Disp(Sqlist *, unsigned);
void Three(Sqlist *, unsigned, unsigned);
#endif /* end of sqlist.h */
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include "../header/funs.h"
/* begin of error 05-8-15 18:40 */
void error(char *fmt, ...) {
va_list args;
va_start(args, fmt);
fprintf(stderr, "error: ");
vfprintf(stderr, fmt, args);
fprintf(stderr, "\n");
va_end(args);
exit(-1);
} /* end of error */
/* begin of flush_stdin 05-8-31 19:30 */
void flush_stdin(void) /* 清空“输入缓冲区” */ {
int c;
if (!feof(stdin)) {
while ((c = getchar()) != '\n' && c != EOF)
;
}
} /* end of flush_stdin */
#include <stdio.h>
#include <stdlib.h>
#include "../header/sqlist.h"
/* begin of InitList 05-8-13 0:30 */
int InitList(Sqlist *L) /* 创建顺序表 */ {
L->elem = malloc(INITSIZE * sizeof *L->elem); /* 分配初始空间 */
if (!L->elem) {
return 0; /* 创建失败返回 0 */
}
L->length = 0;
L->listsize = INITSIZE;
return 1; /* 创建成功返回 1 */
} /* end of InitList */
/* begin of InputList 05-8-13 2:15 */
int InputList(Sqlist *L) /* 接受用户输入的字符串 */ {
unsigned i;
L->length = 0;
for (i = 0; (L->elem[i] = getchar()) != '\n' && L->elem[i] != EOF; ++i) {
++L->length;
if (L->length == L->listsize) { /* 如果顺序表已满 */
ElemType *newbase = realloc(L->elem, (L->listsize + INCREMENT) * sizeof *L->elem);
if (newbase) { /* 如果分配成功 */
L->elem = newbase; /* 将指针指向新分配好的空间 */
L->listsize += INCREMENT; /* 增大 listsize 的值 */
} else { /* 分配空间失败 */
return 0; /* 增加空间失败，返回 0 */
}
}
}
return 1;
} /* end of InputList */
/* begin of InsertList 05-8-13 5:00 */
int InsertList(Sqlist *L, unsigned pos) /* 插入数据 */ {
Sqlist tmp; /* 用于暂时存储用户输入的字符 */
long i;
if (!InitList(&tmp)) {
return 0;
}
if (InputList(tmp)) {
if (!tmp.length) {
free(tmp.elem);
return 1;
}
if (L->listsize - L->length < tmp.length) {
ElemType *newbase = realloc(L->elem, (L->listsize + tmp.length) * sizeof *L->elem);
if (newbase) {
L->elem = newbase;
L->listsize += tmp.length;
} else {
free(tmp.elem);
return 0;
}
}
--pos;
for (i = L->length - 1; i >= (long)pos; --i) {
L->elem[i + tmp.length] = L->elem[i];
}
i = 0;
while (i < (long)tmp.length) {
L->elem[pos++] = tmp.elem[i++];
}
L->length += tmp.length; /* 更新字符串长度 */
free(tmp.elem);
return 1;
}
free(tmp.elem);
return 0;
} /* end of InsertList */
/* begin of DelList 05-8-13 12:00 */
void DelList(Sqlist *L, unsigned pos, unsigned size) {
for (--pos; pos + size < L->length; ++pos) {
L->elem[pos] = L->elem[pos + size];
}
L->length -= size;
} /* end of DelList */
/* begin of Union 05-8-13 12:30 */
int Union(Sqlist *L1, Sqlist *L2) { /* 求顺序表并集 */
unsigned k;
if (L1 == L2) { /* 如果 L1 和 L2 为同一顺序表 */
return 1;
}
for (k = 0; k < L2->length; ++k) {
if (!Location(L1, L2->elem[k])) {
if (L1->length == L1->listsize) { /* 如果顺序表已满 */
ElemType *newbase = realloc(L1->elem, (L1->listsize + INCREMENT) * sizeof *L1->elem);
if (newbase) {
L1->elem = newbase;
L1->listsize += INCREMENT;
} else {
return 0; /* 增加空间失败，返回 */
}
}
L1->elem[L1->length] = L2->elem[k]; /* 插入到表 L1 */
L1->length++; /* 表 L1 长度增加 */
}
}
return 1; /* 无误返回 */
} /* end of Union */
/* begin of Purge 05-8-13 13:00 */
void Purge(Sqlist *L) /* 删除表中重复元素 */ {
unsigned i, j, k;
for (i = 0; i < L->length; i++) {
for (j = i + 1; j < L->length;) {
if (L->elem[i] == L->elem[j]) { /* 若找到重复元素 */
for (k = j; k < L->length; k++) { /* 删除重复元素 */
L->elem[k] = L->elem[k + 1];
}
L->length--; /* 顺序表长度减1 */
} else {
j++;
}
}
}
} /* end of Purge */
/* begin of Purge2 05-8-13 13:20 */
void Purge2(Sqlist *L) /* 删除表中重复元素 */ {
Sqlist T = *L;
unsigned i;
T.length = 1;
for (i = 1; i < L->length; i++) {
if (!Location(T, L->elem[i])) { /* 若找不到重复元素 */
T.elem[T.length] = L->elem[i]; /* 插入 */
T.length++; /* 更新长度 */
}
}
L->length = T.length; /* 更新长度 */
} /* end of Purge2 */
/* begin of Bubble 05-8-13 14:10 */
void Bubble(Sqlist *L, unsigned ascend) {
ElemType temp;
unsigned i, j, k = L->length - 1;
unsigned l;
if (!L->length) {
return;
}
for (l = 1; l; k--) {
l = 0;
for (i = 0, j = 1; i < k; i++, j++) {
if ((L->elem[i] > L->elem[j]) ^ ascend) {
temp = L->elem[i];
L->elem[i] = L->elem[j];
L->elem[j] = temp;
l = 1;
}
}
}
} /* end of Bubble */
/* begin of Compare 05-8-13 14:40 */
int Compare(Sqlist *L1, Sqlist *L2) /* 比较两个顺序表 */ {
unsigned k;
if (L1 == L2) {
return 0;
}
for (k = 0; k < L1->length && k < L2->length; k++) {
if (L1->elem[k] > L2->elem[k]) {
return 1;
}
if (L1->elem[k] < L2->elem[k]) {
return -1;
}
}
return L1->length - L2->length;
} /* end of Compare */
/* begin of Exchange 05-8-13 15:10 */
void Exchange(Sqlist *L, unsigned i) /* 前N个元素和后M个元素互换 */ {
Three(L, 0, i - 1);
Three(L, i, L->length - 1);
Three(L, 0, L->length - 1);
} /* end of Exchange */
/* begin of Three 05-8-13 14:55 */
void Three(Sqlist *L, unsigned i, unsigned j) /* 三次逆转法 */ {
ElemType temp;
for (; i < j; i++, j--) {
temp = L->elem[i];
L->elem[i] = L->elem[j];
L->elem[j] = temp;
}
} /* end of Three */
/* begin of Location 05-8-13 12:10 */
int Location(Sqlist *L, ElemType elem) /* 求元素位置 */ {
unsigned l;
for (l = 0; l < L->length && L->elem[l] != elem; l++) {
;
}
if (l == L->length) { /* 在顺序表中找不到elem */
return 0; /* 返回0 */
}
return ++l; /* 找到则返回元素位置 */
} /* end of Location */
/* begin of Disp 05-8-13 15:20 */
void Disp(Sqlist *L, unsigned total_lists) /* 显示顺序表信息 */ {
unsigned short i;
unsigned j;
printf("\n当前一共有 %u 个顺序表。每个表的数据如下：\n", total_lists);
for (i = 0; i < total_lists; i++) {
printf("\n顺序表 %d ：", i + 1);
for (j = 0; j < L[i].length; j++) {
printf("%c", L[i].elem[j]);
}
printf("\n字符串长度：%u 顺序表长度：%u\n", L[i].length, L[i].listsize);
}
} /* end of Disp */
#include <stdio.h>
#include <stdlib.h>
#include "header/sqlist.h"
#include "header/funs.h"
#define MAX_LISTS 10 /* 最多可以建立的顺序表个数 */
/* 函数声明 */
char Menu(void); /* 打印菜单，请用户选择 */
unsigned Choose(unsigned, unsigned, char); /* 接收用户输入的选择 */
static int tmp; /* tmp 用于清空输入缓冲区 */
const char *msg[] = {
"\n请问您要对哪个顺序表（%u — %u）进行操作：",
"\n请输入删除数目（%u — %u）：",
"\n请输入字符串（原有数据会被覆盖）：",
"\n请输入插入位置（%u — %u）：",
"\n请输入删除位置（%u — %u）：",
"\n此项操作至少要有两个顺序表才能进行。请再建立一个顺序表。",
"\n重复元素已被删除。",
"\n请问您要进行降序排序还是升序排序（%u 代表降序，%u 代表升序）：",
"\n顺序表 %u %c 顺序表 %u",
"\n请输如互换点（%u — %u）：",
"\n排序完成。"
};
int main(void) {
Sqlist L[MAX_LISTS]; /* 顺序表数组 */
char choice; /* 记录用户选择的操作 */
unsigned short total_lists = 0; /* 用于记录目前一共有多少个顺序表 */
char *init_msg[] = {"内存不足！创建失败。", /* 创建顺序表的提示信息 */
"顺序表创建成功！您可以开始对顺序表进行操作了。"};
printf("\n请先创建一个顺序表。最多可以创建 %u 个顺序表。\n", MAX_LISTS);
while ((choice = Menu())) { /* 根据用户输入选择函数运行 */
if (!total_lists && choice != 1) {
printf("\n请先创建一个顺序表。最多可以创建 %u 个顺序表。\n", MAX_LISTS);
} else {
switch (choice) {
case 1:
if (total_lists == MAX_LISTS) { /* 达到最大限制 */
printf("\n最多只能建立 %u 个顺序表。\n", MAX_LISTS);
} else {
int i = InitList(L[total_lists]);
total_lists += i; /* 更新顺序表数目 */
printf("\n%s\n", init_msg[i]);
}
break;
case 2: {
unsigned num = Choose(total_lists, 1, 0);
printf("%s", msg[choice]);
InputList(L[num - 1]);
break;
}
case 3: {
unsigned num, pos;
num = Choose(total_lists, 1, 0);
pos = Choose(L[num - 1].length + 1, 1, choice);
printf("\n请输入字符串：");
InsertList(L[num - 1], pos);
break;
}
case 4: {
unsigned num, pos, size;
num = Choose(total_lists, 1, 0);
if (!L[num - 1].length) {
printf("\n顺序表为空，不能进行删除操作。\n");
break;
}
pos = Choose(L[num - 1].length, 1, choice);
size = Choose(L[num - 1].length - pos + 1, 1, 1);
DelList(L[num - 1], pos, size);
break;
}
case 5: {
unsigned num1, num2;
if (total_lists < 2) {
puts(msg[choice]);
break;
}
num1 = Choose(total_lists, 1, 0);
num2 = Choose(total_lists, 1, 0);
if (Union(L[num1 - 1], L[num2 - 1])) {
printf("\n并集操作完成。操作结果保存于顺序表 %u 。\n", num1);
} else {
printf("\n并集操作失败。\n");
}
break;
}
case 6: {
unsigned num = Choose(total_lists, 1, 0);
Purge(L[num - 1]);
puts(msg[choice]);
break;
}
case 7: {
unsigned num = Choose(total_lists, 1, 0);
unsigned ascend = Choose(1, 0, choice);
Bubble(L[num - 1], ascend);
puts(msg[10]);
break;
}
case 8: {
unsigned num1, num2;
int flag;
if (total_lists < 2) {
puts(msg[5]);
break;
}
num1 = Choose(total_lists, 1, 0);
num2 = Choose(total_lists, 1, 0);
flag = Compare(L[num1 - 1], L[num2 - 1]);
if (!flag) {
flag = '=';
} else if (flag < 0) {
flag = '<';
} else {
flag = '>';
}
printf(msg[choice], num1, flag, num2);
break;
}
case 9: {
unsigned num = Choose(total_lists, 1, 0), point;
if (L[num - 1].length < 2) {
puts("\n元素太少，不能进行互换。");
break;
}
point = Choose(L[num - 1].length - 1, 1, choice);
Exchange(L[num - 1], point);
puts("\n互换完成。");
break;
}
case 10: {
unsigned num = Choose(total_lists, 1, 0);
Purge2(L[num - 1]);
puts(msg[6]);
break;
}
default:
break;
}
}
/* 打印顺序表的内容 */
Disp(L, total_lists);
}
while (total_lists) {
free(L[--total_lists].elem); /* 释放内存 */
}
puts("\n感谢您使用我们的产品！请按回车退出...");
getchar();
return 0; /* 退出程序 */
} /* end of main */
/* begin of Choose 05-8-13 3:00 */
unsigned Choose(unsigned up, unsigned low, char c) {
unsigned num = 0;
do {
printf(msg[c], low, up);
scanf("%u", &num);
flush_stdin(); /* 清空输入缓冲区 */
} while (num > up || num < low);
return num;
} /* end of Choose */
/* begin of Menu 05-8-12 23:20 */
char Menu(void) /* 打印菜单，并且接受用户输入 */ {
int ch = -1; /* ch 用于接收用户输入 */
for (;;) {
printf("\n********************************\n"
"* 1. 创建顺序表 *\n"
"* 2. 输入数据 *\n"
"* 3. 插入数据 *\n"
"* 4. 删除数据 *\n"
"* 5. 求顺序表并集 *\n"
"* 6. 删除重复元素 *\n"
"* 7. 冒泡排序 *\n"
"* 8. 比较顺序表大小 *\n"
"* 9. 前N个元素和后M个元素互换 *\n"
"*10. 删除重复元素(2) *\n"
"* 0. 退出 *\n"
"********************************\n\n"
"请输入您要执行的操作（按回车确定）：");
scanf("%d", &ch);
flush_stdin(); /* 清空输入缓冲区 */
if (ch <= 10 && ch >= 0) {
break; /* 输入合法，退出循环 */
}
puts("\n请输入 0 到 10 之间的数字。\n");
} /* end of for */
return ch; /* 返回操作号 */
} /* end of Menu */
给你的邮箱，发，，百度难编辑
已经发到你的邮箱了,请注意查收.
## c语言 快速排序。。
```c
int quickSortpx(SqList list, int first, int end) {
int compare;
compare = list.elem[first];
for (; first < end;) {
while (first < end && list.elem[end] >= compare) {
end--;
}
if (first < end && list.elem[end] < compare) {
list.elem[first] = list.elem[end];
first++;
}
while (first < end && list.elem[first] <= compare) {
first++;
}
if (first < end && list.elem[first] > compare) {
list.elem[end] = list.elem[first];
end--;
}
}
/* 你没有把取出的第一个元素放回链表，请在这里添加 */
list.elem[end] = compare; /* 或 list.elem[first] = compare; */
return (first);
}
二级C语言排序技术2
（1）交换类排序法 交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类排序方法。 冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n–1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。 快速排序法也是一种交换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。其关键是对线性表进行分割，以及对各分割出的子表再进行分割。 （2）插入类排序法 插入类排序法主要有简单插入排序法和希尔排序法。 简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。在这种排序方法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n–1)/2次比较。 希尔排序法对简单插入排序做了较大的改进。它是将整个无序序列分割成若干小的子序列分别进行插入排序。希尔排序的效率与所选取的增量序列有关。在最坏情况下，希尔排序所需要的比较次数为O(n^1.5)。 （3）选择类排序 选择类排序主要有简单选择类排序法和堆排序法。 简单选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的线性表，在最坏情况下需要比较n(n–1)/2次。 堆排序法也属于选择类排序法。具有n个元素的序列（h1, h2, ..., hn），当且仅当满足条件：或 (i=1, 2, ..., n/2)时称之为堆。可见，堆顶元素（即第一个元素）必为最大项。 堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。
