本文主要是介绍查找元素x,若x存在,则与其后继交换,否则将x插入,使顺序表有序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#include<stdio.h>
#define LIST_INIT_SIZE 6
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{ElemType *elem;int length;int listsize;
}SqList;void InitSqList(SqList *L);//初始化顺序表
void CreateSqList(SqList *L, ElemType *arr, int n);//给予顺序表初始数据
void ShowSqList(SqList *L);//输出顺序表数据//二分法查找x,找到则返回元素索引,找不到则返回不大于x的最大元素索引的相反数
int SearchByElem(SqList *L, ElemType x);
//第i个数据之前插入x
void InsertByIndex(SqList *L, int i, ElemType x);
//交换数据值
void swap(ElemType *x, ElemType *y);
//查找元素x,若x存在,则与其后继交换,否则将x插入,使顺序表有序
void SearchSwapInsert(SqList *L, ElemType x);int main()
{SqList L;ElemType arr[6] = { 1, 2, 3, 5, 7, 6 };InitSqList(&L);CreateSqList(&L, arr, 6);printf("初始数据列表:");ShowSqList(&L);printf("\n");printf("执行查找交换插入算法,数据为:%d\n",7);SearchSwapInsert(&L, 7);ShowSqList(&L);printf("执行查找交换插入算法,数据为:%d\n", 4);SearchSwapInsert(&L, 4);ShowSqList(&L);getchar();return 0;
}void InitSqList(SqList *L)
{L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));L->length = 0;L->listsize = LIST_INIT_SIZE;
}void CreateSqList(SqList *L, ElemType *arr, int n)
{int i;if (n <= LIST_INIT_SIZE){for (i = 0; i < n; i++){L->elem[i] = arr[i];}L->length = n;}else{printf("插入失败,数据个数应不大于 %d", LIST_INIT_SIZE);}
}void ShowSqList(SqList *L)
{int i;for (int i = 0; i < L->length; i++){printf(" %d ", L->elem[i]);}printf("\n");
}//二分法查找x,找到则返回元素索引,找不到则返回不大于x的最大元素索引
int SearchByElem(SqList *L, ElemType x)
{int high = L->length - 1;int low = 0;int mid;while (low <= high){mid = (high + low) / 2;if (L->elem[mid] == x){return mid;}else if (x < L->elem[mid]){high = mid - 1;}else{low = mid + 1;}}//high为小于x元素集合中的最大值的索引return -high;
}//第i个数据之前插入x
void InsertByIndex(SqList *L, int i, ElemType x)
{if (i<1||i>L->length+1){printf("位置不合法,插入失败!");return;}if (L->length >= L->listsize){ElemType *enew = (ElemType *)realloc(L->elem, (LISTINCREMENT + L->listsize) * sizeof(ElemType));L->elem = enew;L->listsize += LISTINCREMENT;}ElemType *p = &(L->elem[i - 1]);//待插入的位置ElemType *q = &(L->elem[L->length - 1]);//q指向最后一个元素for (; p <= q; q--){*(q + 1) = *q;}*p = x;L->length++;
}void swap(ElemType *x, ElemType *y)
{ElemType t = *y;*y = *x;*x = t;
}void SearchSwapInsert(SqList *L, ElemType x)
{int k;if ((k = SearchByElem(L, x)) >= 0){swap(&(L->elem[k]), &(L->elem[k + 1]));}else{InsertByIndex(L, -k + 2, x);}
}
这篇关于查找元素x,若x存在,则与其后继交换,否则将x插入,使顺序表有序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!