DuLinkList.h
typedef int Status;
typedef int ElemType;
typedef struct DuLNode{
ElemType data;
struct DuLNode* prior;
struct DuLNode* next;
}DuLNode, * DuLinkList;
//当第i个元素存在 返回位置
DuLinkList GetElem_L(DuLinkList, int);
//插入
Status ListInsert_DuL(DuLinkList ,int,ElemType);
//删除
Status ListDelete_DuL(DuLinkList ,int ,ElemType *);
//创建
void Create_DuL(DuLinkList *);
//直接插入排序
void InsertSort(DuLinkList);
DuLinkList.c
#include<stdlib.h>
#include "./DuLinkList.h"
//插入
Status ListInsert_DuL(DuLinkList L, int i, ElemType e) {
//获取插入位置
DuLinkList p,s;
p = GetElem_L(L, i);
if (!p) { return -1;};
//创建一个新节点
s = (DuLinkList)malloc(sizeof(DuLNode));
if (!s) { return -1; };
s->data = e;
//如果 p是头结点
if (!p->next) {
p->next = s;
s->prior = p;
s->next = NULL;
return 0;
}
//插入操作
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;
return 0;
};
//删除
Status ListDelete_DuL(DuLinkList L, int i, ElemType* e) {
//获取删除位置
DuLinkList p, s;
p = GetElem_L(L, i);
if (!p) { return -1; };
*e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return 0;
};
//创建
void Create_DuL(DuLinkList* L) {
*L = (DuLinkList)malloc(sizeof(DuLNode));
(*L)->data = 0;
(*L)->next = NULL;
(*L)->prior = NULL;
};
//当第i个元素存在 返回位置
DuLinkList GetElem_L(DuLinkList L, int i) {
DuLinkList p;
int j;
j = 1;
if (!L->next) { return L; };
p = L->next;
while (p && i>j)
{
++j;
p = p->next;
}
if (i > j) {
exit(0);
}
return p;
};
//直接插入排序
void InsertSort(DuLinkList L) {
//记录插入到的位置
DuLinkList poi;
DuLinkList p;
DuLinkList temp;
poi = L->next;
while (poi)
{
temp = poi->prior;
while (temp) {
if (!temp->prior) {
//移动到第一个位置的时候还没有比它小的数字则 插入到第一个位置
p = poi->next;
poi->prior->next = poi->next;
poi->next->prior = poi->prior;
poi->prior = temp;
poi->next = temp->next;
temp->next->prior = poi;
temp->next = poi;
poi = p;
break;
}
//如果小于就把它放在 temp的后面位置
if (temp->data < poi->data) {
if (poi->prior == temp) {
poi = poi->next;
break;
}
p = poi->next;
//断开
if (poi->next) {
poi->prior->next = poi->next;
poi->next->prior = poi->prior;
}else {
//最后一个结点的时候 断开操作
poi->prior->next = NULL;
}
//插在后面
poi->prior = temp;
poi->next = temp->next;
temp->next->prior = poi;
temp->next = poi;
poi = p;
break;
}
temp = temp->prior;
}
}
};
Main.c文章来源:https://uudwc.com/A/dMya4
#include <stdio.h>
#include <stdlib.h>
#include "./DuLinkList.h"
int main() {
DuLinkList l;
Create_DuL(&l);
ListInsert_DuL(l, 0, 1);
ListInsert_DuL(l, 1, 2);
ListInsert_DuL(l, 2, 3);
ListInsert_DuL(l, 1, 6);
ListInsert_DuL(l, 1, 7);
ListInsert_DuL(l, 1, 7);
ListInsert_DuL(l, 1, 7);
ListInsert_DuL(l, 1, 20);
ListInsert_DuL(l, 1, 0);
ListInsert_DuL(l, 1, 16);
ListInsert_DuL(l, 1, 9);
ListInsert_DuL(l, 1, 3);
DuLinkList p;
p = l->next;
while (p)
{
printf("%d\n", p->data);
p = p->next;
};
ElemType e;
printf("delete=====================================\n");
ListDelete_DuL(l,2,&e);
printf("删除了:%d\n", e);
printf("delete=====================================\n");
p = l->next;
while (p)
{
printf("%d\n", p->data);
p = p->next;
};
printf("sort=====================================\n");
InsertSort(l);
p = l->next;
while (p)
{
printf("%d\n", p->data);
p = p->next;
};
return 0;
}
直接插入法
2 15871
12 5871
125 871
1257 81
12578 1
112578
每次保证前面是有序的 ,用后面的值在前面找合适的位置插入
最坏的情况每次都插入到第一个位置 从第二个元素开始比较次数
元素位置 比较次数
2 *************1
3 *************2
4 ************ 3
. ************** .
. ************** .
. **************.
n-1 *********** n-1
最坏情况时间复杂度
1+2+3+…n-1 = (n-1)(1+n-1)/2 = n(n-1)/2文章来源地址https://uudwc.com/A/dMya4