1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 typedef char * ElemType; 6 7 typedef struct DuLNode { 8 ElemType data; 9 struct DuLNode *prior, *next; 10 } DuLNode, *DuLinkList; 11 12 13 DuLinkList create(){ 14 return (DuLinkList)malloc(sizeof(DuLNode)); 15 } 16 17 char * create_str(char *str){ 18 char *ss = (char *)malloc((strlen(str) + 1) * sizeof(char)); 19 strcpy(ss, str); 20 return ss; 21 } 22 23 void scan(DuLinkList L){ 24 int n; 25 char str[1024]; 26 DuLinkList lp, p = L; 27 scanf("%d", &n); 28 while(n--){ 29 scanf("%s", str); 30 31 lp = create(); 32 lp->data = create_str(str); 33 lp->prior = p; 34 lp->next = NULL; 35 36 p->next = lp; 37 38 p = lp; 39 } 40 } 41 void insertion_sort(DuLinkList L){ 42 int cnt = 0; 43 for(DuLinkList pcnt = L->next; pcnt != NULL; pcnt = pcnt->next){ 44 cnt++; 45 } 46 47 DuLinkList sign = NULL, p1, p2; 48 while(--cnt){ 49 for(p1 = L->next, p2 = L->next->next; p2 != sign; p1 = p1->next, p2 = p2->next){ 50 if(strcmp(p1->data, p2->data) >= 0){ 51 //交换两个节点 52 p1->prior->next = p2; 53 if(p2->next != NULL){ 54 p2->next->prior = p1; 55 } 56 p1->next = p2->next; 57 p2->prior = p1->prior; 58 59 p1->prior = p2; 60 p2->next = p1; 61 62 DuLinkList tmp = p1; 63 p1 = p2; 64 p2 = tmp; 65 } 66 } 67 sign = p1; 68 } 69 } 70 71 void print(DuLinkList L){ 72 DuLinkList p = L->next; 73 while(p != NULL){ 74 printf("%s ", p->data); 75 p = p->next; 76 } 77 puts(""); 78 } 79 80 int main(){ 81 //freopen("data.txt", "r", stdin); 82 DuLNode L; 83 //输入数据 84 scan(&L); 85 //打印输出 86 print(&L); 87 //冒泡排序 88 insertion_sort(&L); 89 //打印数据 90 print(&L); 91 92 return 0; 93 }
测试代码
10
9只小昆虫
8只小昆虫
7只小昆虫
6只小昆虫
5只小昆虫
4只小昆虫
3只小昆虫
2只小昆虫
1只小昆虫
0只小昆虫