冒泡排序(顺序表)和简单选择排序(单链表)

    xiaoxiao2021-12-12  2

    河南理工大学

    16 学年—17学年第 1 学期 数据结构 实验任务书

    专业名称:              实验学时:    2    

    课程名称:数据结构      任课教师:  翟海霞     

    实验题目:     排序算法实现与比较            

    实验环境:    Visual C++ 6.0                    

     

    实验八:

    实验目的和要求:熟悉多种排序算法,理解每种排序算法思想,掌握排序算法的基本设计方法,掌握排序算法时间复杂度和空间复杂度的分析方法。

    实验内容:1.对所讲过算法深入理解。

              2. 将冒泡排序再做进一步的优化。如果有100个数的数组,当前仅前面10个无序,后面90个都已排好序且都大于前面10个数字,那么在该一趟遍历后,最后发生交换的位置必定小于10,且这个位置之后的数据必定已经有序了,记录下这位置,下次只要从数组头部遍历到这个位置就可以了。

               3. 试以单链表为存储结构,实现简单选择排序算法。

          

    #include<stdio.h> #include<stdlib.h> #define Maxsize 20 typedef struct { int key; }RedType; typedef struct { RedType r[Maxsize+1]; int length; }SqList; void Bubblesort(SqList *L) { int i,j,n,change; RedType x; n=L->length;change=1; for(i=0;i<n-1&&change;++i) { change=0; for(j=0;j<n-i-1;++j) if(L->r[j].key>L->r[j+1].key) {x=L->r[j];L->r[j]=L->r[j+1];L->r[j+1]=x;change=1; } } } typedef struct Node { int date; struct Node *next; }node,*List; //创建单链表 List creat_list(int n) { int i=0; List head,L,temp; head=(List)malloc(sizeof(node)); head->next=NULL; temp=head; for(;i<n;i++) { L=(List)malloc(sizeof(node)); L->next=NULL; printf("Please input the date:"); scanf("%d",&L->date); temp->next=L; temp=L; } return head; } List getmin(List L) {//取得从指针L开始的链表中记录的最小值 List min; min=L; while(L->next) { if(min->date>(L->next->date)) { min=L->next; } L=L->next; } return min;//返回较小值的指针 } void selectsort(List head)//简单选择排序--单链表 { List j,i=head->next; int temp; for(;i->next!=NULL;i=i->next) { j=getmin(i); if(i->date!=j->date) { temp=i->date; i->date=j->date; j->date=temp; } } } //输出单链表 void printf_list(List head) { List p=head->next; while(p) { printf("=",p->date); p=p->next; } } int main() { List head,temp; SqList L,*p=&L; int i;L.length=10; int choose,n; printf("————————————排序算法与比较——————————\n\n"); printf("操作:\n"); printf("1.冒泡排序\n"); printf("2.简单选择排序\n"); printf("0.退出\n"); choose=-1; while(1) { printf("请输入您的操作:"); scanf("%d",&choose); switch(choose) { case 1:{ //printf("请输入数据个数:"); //scanf("%d",&n); printf("请输入数据:\n"); for(i=0;i<L.length;i++) scanf("%d",&L.r[i].key); printf("原数据:"); for(i=0;i<L.length;i++) printf("M",L.r[i].key); Bubblesort(p); printf("\n排序后:"); for(i=0;i<L.length;i++) printf("M",L.r[i].key); printf("\n"); } break; case 2:{ printf("请输入元素个数:"); scanf("%d",&n); head=creat_list(n); printf_list(head); printf("\n"); selectsort(head); printf_list(head); printf("\n"); }break; case 0:exit(0); } } return 0; }

        

     

    转载请注明原文地址: https://ju.6miu.com/read-900257.html

    最新回复(0)