数据结构与算法

本文为一些算法的实现,以C++/C 为编程语言。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 头插法建立双链表
void CreateListF(DLinkList *&L,ElemType a[],int n){
DLinkList * s;
int i;
L = (DLinkList *)malloc(sizeof(DLinkList));
L->prior=L->next=NULL;
for(i=0;i<n;i++){
s = (DLinkList *)malloc(sizeof(DLinkList));
s->data=a[i];
s->next=L->next;
if(L->next!=NULL){
L->next->prior=s;
}
L->next=s;
s->prior=L;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Commnode(LinkList * &LA,LinkList * LB,LinkList * LC){ // TODO:为什么时间复杂度为O(m+n+p)? m.n.p对应各个表的Length
LinkList * pa = LA->next,* pb=LB->next,* pc=LC->next,* q, * r;
LA->next = NULL; //此时LA作为新建单链表的头结点
r=LA; // r始终指向单链表的尾节点
while(pa!=NULL){
while(pb!=NULL&&pa->data>pb->data){
pb=pb->next;
}
while(pc!=NULL&&pa->data>pc->data){
pc=pc->next;
}
if(pb!=NULL && pc!=NULL && pa->data==pb->data&&pa->data==pc->data){
r->next=pa;
r=pa;
pa=pa->next;
}
else{
q=pa;
pa=pa->next;
free(q);
}
}
r->next=NULL; //尾节点的next域置空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
void CreateListR(DLinkList *&L,ElemType a[],int n){
DLinkList * s, * r;
int i;
L = (DLinkList *)malloc(sizeof(DLinkList));
r = L;
for (i=0;i<n;i++){
s=(DLinkList *)malloc(sizeof(DLinkList));
s->data=a[i];
r->next=s;s->piror=r;
r=s;
}
r->next=NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
void dels(LinkList * &L){
LinkList * p = L->next,* q;
while(p->next!=NULL){
if(p->data==p->next->data){
q=p->next;
p->next=q->next;
free(q);
}
else
p=p->next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void move2(SqlList *&L){
int i=0,j=L->length-1;
ElemType pivot=L->data[0];
while(i<j){
while(j>i&&L->data[j]>pivot)
j--;
L-data[i]=L->data[j];
i++;
while(i<j&&L->data[i]<=pivot)
i++;
L->data[j] = L->data[i];
j--;
}
L->data[i]=pivot;
printf("i=%d\n",i);
}
i=0,j=5; pivot=3;
// 第一轮循环
data[0]=1, (1,8,2,7,1,5), i=1 j=4 ,data[4]=8 (1,8,2,7,8,5)
i=1 j=3
// 第2轮循环
(3,8,2,7,1,5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void LinkTable(HList * h1,HList * h2,HList * &h){
int i,j,k;
DList * p = h1->next,* q, * s, * r;
printf("连接字段是:第1个表序号,第二个表序号:");
scanf("%d%d",&i,&j);
h=(HList *)malloc(sizeof(HList));// 创建结果表头节点
h->Row=0;
h->Col=h1->Col+h2->Col;
h->next=NULL;
while(p!==NULL){
q=h2->next;
while(q!==NULL){
if(p->data[i-1]i==q->data[j-1]){
s=(DList *)malloc(sizeof(DList));
for(k=0;k<h1->Col;k++)
s->data[k]=h1->data[k];
for(k=0;k<h2->Col;k++)
s->data[h1->Col+k]=q->data[k];
if(h->next)
h->next=s;
else
r->next=s;
r=s;
h->Row++;
}
q=q->next;
}
p=p->next;
}
r->next=NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool ListDelete(DLinkList *&L,int i,ElemType &e){
int j=0;
DLinkList * p=L,* q;
while(j<i-1&&p!=NULL){
j++;
p=p->next;
}
if(p==NULL)
return false;
else
{
q=p->next;
if(q==NULL)
return false;
e=q->data;
p->next=q->next;
if(p->next!==NULL)
p->next->prior=p;
free(p);
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool ListInsert(DLinkList *&L,int i,ElemType e){
int j=0;
DLinkList * p=L,* s; //p指向头节点,j设置为0
while(j<i-1&&p!=NULL){ // 查找第i-1个节点
j++;
p=p->next;
}
if(p==NULL)
return false;
else
{
s=(DLinkList *)malloc(sizeof(DLinkList));
s->data=e;
s->next=p->next;
if(p->next!=NULL)
p->next->piror=s;
s->piror=p;
p->next=s;
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void ListInsert1(SqList * &L,ElemType e){
int i=0,j;
while(i<L->length && L->data[i]<e){ // 有序表的插入 (递增递减)
i++;
for (j=ListLength(L);j>i;j--){
L->data[j]=L->data[j-1];
}
L->data[i]=e;
L->length++;
}
}
// 单链有序表
void ListInsert2(LinkList * &L,ElemType e){
LinkList * pre = L, * p;
while(pre->next!=NULL&&pre->next->data<e){
pre=pre->next;
}
p=(LinkList *)malloc(sizeof(LinkList));
p->data=e;
p->next=pre->next;
pre->next=p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
void UnionList(SqList * LA,SqList * LB,SqList * &LC){
int i=0,j=0,k=0; // i,j分别为LA,LB的下标,K为LC中元素的个数
LC=(SqList *)malloc(sizeof(SqList)); //建立有序顺序表LC
while(i<LA->length&&j<LB->length){
if(LA->data[i]<LB->data[j]){
LC->data[k]=LA->data[i];
i++;k++;
}
else{
LC->data[k]=LB->data[j];
j++;k++;
}
}
while(i<LA->length){
LC->data[k]=LA->data[i];
i++;k++;
}
while(j<LB->length){
LC->data[k]=LB->data[j];
j++;k++;
}
LC->length=k;
}
// 单链表存放有序表的归并算法如下
void UnionList1(LinkList * LA,LinkList * LB,LinkList * &LC){
LinkList * pa = LA->next,* pb = LB->next, * r,* s;
LC=(LinkList *)malloc(sizeof(LinkList));
r=LC;
while(pa!=NULL&&pb!=NULL){
if(pa->data<pb->data){
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pb->data;
r->next=s;r=s;
pa=pa->next;
}
else
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pb->data;
r->next=s;r=s;
pb=pb->next;
}
}
while(pa!=NULL){
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
r->next=s;
r=s;
pa=pa->next;
}
while(pb!=NULL){
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pb->data;
r->next=s;
r=s;
pb=pb->next;
}
r->next=NULL;
}

Recommended Posts