顺序表中的数据元素递增有序,试着写一算法,将x插入到顺序表上的适当位置上,以保持该表的有序性。"/>
设顺序表中的数据元素递增有序,试着写一算法,将x插入到顺序表上的适当位置上,以保持该表的有序性。
算法分析
首先应该创建一个顺序表,从键盘输入数据;
显示顺序表
在插入之前先找到插入的位置;
将插入位置后面的数据往后移动;
完整的代码
#include<stdio.h>2 #include<stdlib.h>3 4 #define LIST_INIT_SIZE 1005 #define LISTINCREMENT 106 typedef struct7 {8 int *elem;//存储空间基址9 int length ;10 int listsize;11 }SqList;12 13 void InitList(SqList *L)14 {15 L->elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int));//创建一个空列表16 L->length = 0;//空表长度为017 L->listsize =LIST_INIT_SIZE;//初始存储容量18 19 }20 21 void InputData(SqList *L)22 {23 24 int n;25 int *p;26 p = L->elem;27 printf("请输入列表元素个数:");28 scanf("%d",&n);29 /*进行判断,是否超过列表长度*/30 if(n>L->listsize)//超过存储容量,再分配空间31 {32 L->elem = (int*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));//再分配空间33 L->listsize +=(n+LISTINCREMENT);34 while(n!=0)35 {36 scanf("%d",p);37 p++;38 n--;39 L->length++;40 }41 }42 else43 {44 45 while(n!=0)46 {47 scanf("%d",p);48 p++;49 n--;50 L->length++;51 }52 }53 }54 55 void DisplayList(SqList *L)//显示顺序列表56 57 {58 59 int i;60 int *p = L->elem;61 for(i = 0; i<L->length; i++){63 printf("%d\n",*p);64 p++;65 }66 67 }68 69 void InsertElem(SqList *L,int e)//往顺序表中插入一个元素,使其递增有序70 {71 //进行溢出判断72 if(L->length+1>L->listsize)//在分配内存空间73 {74 L->elem = (int*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));//再分配空间75 L->listsize +=(LISTINCREMENT);76 }77 if(L->length == 0)//如果列表为空78 printf("error !List empty");79 int *p = L->elem;80 int *p_last = L->elem+L->length-1;81 /* 先查找插入元素的位置*/82 while(e > *p&&p<p_last)83 {84 p++;85 }86 /*p为元素的插入位置,p及后面的元素依次往后移动*/87 int *q ;88 for(q = (L->elem)+(L->length)-1;q>=p;q--)89 {90 *(q+1) = *q;91 }92 *p=e;93 L->length++;94 }95 96 int main()97 {98 SqList L; //定义一个顺序表99 InitList(&L);//初始化
100 InputData(&L);//输入数据
101 DisplayList(&L);//显示数据
102 printf("插入数据:\n");
103 int m;
104 scanf("%d",&m);
105 InsertElem(&L,m);
106 printf("显示插入后的顺序表\n");
107 DisplayList(&L);
108
109 return 0;
110 }
更多推荐
设顺序表中的数据元素递增有序,试着写一算法,将x插入到顺序表上的适当位置上,以保持该表的有序性。
发布评论