算法设计作业-单链表

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct LNode
{
int data;
struct LNode *next;
}LNode;
LNode *CreatList(LNode *h,int t,int n)
{
int x;
LNode *s = (LNode *)malloc(sizeof(LNode));
if(t>n) return h;
scanf("%d",&x);
s->data = x;
s->next = h;
h = s;
h = CreatList(h,t+1,n);
return h;
}
void Output(LNode *h)
{
while(h!=NULL){
printf("%d ",h->data);
h =
h->next;
}
printf("n");
}
/* 非递归写法
LNode *Delete(LNode *now,int num)
{
int flag = 0;
LNode *pre,*nhead,*p;
pre = NULL;nhead = NULL;
while(now != NULL){
if(now->data == num){
p = now;
if(pre == NULL){
now = now->next;
}
else{
pre->next = now->next;
now = now->next;
}
free(p);
}
else{
if(flag == 0){
nhead = now;
flag = 1;
}
pre = now;
now = now->next;
}
}
return nhead;
}*/
LNode *Delete(LNode *pre,LNode *now,int num,LNode *nhead,int flag)
{
LNode *p;
if(now == NULL) return nhead;
if(now -> data == num){
p = now;
if(pre == NULL){
now = now->next;
nhead = Delete(pre,now,num,nhead,flag);
}
else{
pre->next = now->next;
now = now->next;
nhead = Delete(pre,now,num,nhead,flag);
}
free(p);
}
else{
if(flag == 0){
nhead = now;
flag = 1;
}
pre = now;
nhead = Delete(pre,now->next,num,nhead,flag);
}
return nhead;
}
int main()
{
int n,x,num;
printf("输入数据的数量为：");
scanf("%d",&n);
printf("请输入n个数据:");
scanf("%d",&x);
LNode *h = (LNode *)malloc(sizeof(LNode));
h->data = x;
h->next = NULL;
LNode *head = CreatList(h,2,n);
printf("当前链表为：");
Output(head);
printf("请输入要删除的数据:");
scanf("%d",&num);
//	LNode *nhead = Delete(head,num);
LNode *nhead = Delete(NULL,head,num,NULL,0);
Output(nhead);
}
// 88 66 100 90 100 65 78 100 85 100

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct BTNode
{
int data;
struct BTNode *lchild,*rchild;
}BTNode;
BTNode *CreatBTree(int a[],int b[],int n)
{
int k;
if(n<=0) return NULL;
int root = a[0];
BTNode *bt = (BTNode *)malloc(sizeof(BTNode));
bt->data = root;
for(k=0;k<n;++k){
if(b[k]==root)
break;
}
bt->lchild = CreatBTree(a+1,b,k);
bt->rchild = CreatBTree(a+k+1,b+k+1,n-k-1);
return bt;
}
void Output_DLR(BTNode *bt)
{
if(bt==NULL) return ;
printf("%d ",bt->data);
Output_DLR(bt->lchild);
Output_DLR(bt->rchild);
}
void Output_LDR(BTNode *bt)
{
if(bt==NULL) return ;
Output_LDR(bt->lchild);
printf("%d ",bt->data);
Output_LDR(bt->rchild);
}
void Output_LRD(BTNode *bt)
{
if(bt==NULL) return ;
Output_LRD(bt->lchild);
Output_LRD(bt->rchild);
printf("%d ",bt->data);
}
int main()
{
int n = 12;
int a[] = {1,2,4,8,9,5,10,11,3,6,12,7};
int b[] = {8,4,9,2,10,5,11,1,12,6,3,7};
BTNode *bt = CreatBTree(a,b,n);
printf("先序：");Output_DLR(bt);printf("n");
printf("中序：");Output_LDR(bt);printf("n");
printf("后序：");Output_LRD(bt);printf("n");
}

1
nhead = Delete(pre,now,num,nhead,flag);