单链表复习

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
//单链表的定义:
#include<stdio.h>
#include<stdlib>
#define LEN sizeof(struct node)
#define NULL 0
typedef int datatype;
typedef struct node
{    datatype data;
    struct node *next;
}linklist;


//单链表的尾插法建立： 
linklist hrear_creat()
{
    int x;
    linklist *head,*p,*rear;
    head=struct(node*) malloc(LEN);
    head->data=-999;
    rear=head;
    printf(\t\n"请输入整数以0为结束符！"\t\n);
    scanf("%d,&x")
while(x!=0)
{
    p=struct(node*)malloc(LEN);
    p->data=x;
    rear->next=p;
    rear=p;
    scanf(%d,&x);
}
rear=NULL;
return(head);//返回头指针 
}

//单链表的头插法建立： 
linklist hhead_ creat()
{
    int x;
    linklist *head;*p,*rear;
    head=struct(node*)malloc(LEN);
    head->data=-999;
    head->next=NULL;//置空head结点的指针域 
    rear=head;
    printf("\t\n请输入整数以0为结束符！\t\n");
    scanf("%d,&x");
    while(x!=0)
    {
        p=struct(node*)malloc(LEN);
        p->data=x;
        p->next=head->next;//置空p结点的指针域 
        head->next=p;
        scanf("%d,&x");
    }
    return(head);
    
}
//单链表的按值查找运算： 
linklist key_search(head,keyx)
linklist *head
datatype keyx;
{     linklist *p=head;
    while(p!=NULL)&&(p->data!=keyx){
    p=p->next;
    if(p->data==keyx)
    return(p);
    else
    return(NULL);
}

//单链表按序号查找运算： 
linklist *no_search(head,i)
linklist *head;
int i;
{    linklist *p=head;
    int j=0;
    while(p->next!=NULL)&&(j<i)
    {p=p->next;
    j++;
    }
    if(j==i)
    return(p);
    else
    return(NULL);    
 } 

//单链表的给定某位置（按值查找）后插运算： 
 linklist *data_insert(head,x)
 linklist *p,*s;
 int x;
 {s=struct(node*)malloc(LEN);
 s->data=x;
 p=findnode(head,x);
 s->next=p->next;
 p->next=s;
 return(head);
 }
 linklist *findnode(head,x)
 linklist *head;
 {    int x;
      linklist *p=head;
      while(p->next!=0)&&(p->next->data<x)
      p=p->next;
      return(p);
 }
 
 //单链表的位置（按序号查找）前插运算： 
 linklist *address_insert(head,x,i) 
 linklist *head;
 int x,i;
 {
     linklist *s,*q;
     s=struct(node*)malloc(LEN);
     s->data=x;
     q=no_search(head,i-1);
     s->next=q->next;
     q->next=s;
     return(head)
 }
 //单链表中删除值为x的结点： 
 linklist *key_delete(head,x)
 linklist *head;
 int x;
 {
    linklist *p,*q;
    p=head;
    while(p!=NULL)&&(p->data!=x)
    {
        q=p;p=p->next;    
     }     
     if(p!=NULL)
     {
         q->next=q->next;
         free(p);
              return(head);
     }
    else
    {
        printf("\n\t要删除的结点不存在\n");
        return(NULL); 
    }
     
 } 
//单链表中删除序号为k的结点： 
linklist *no_delete(head,k);
linklist *head;
int k;
{printf("\n\t\t请输入结点的位置k") ;
scanf("%d",&k)
linklist*p;
p=no_search(head,k);
if(p!=NULL)
{    
    p-next=p->next->next;
    return(head);
}
else
{
    printf("\n\t\t要删除的结点不存在")
    return(NULL);
}
}
 
 
 //单链表的逆置： 
 linklist *reverse_linklist(head)
 linlist *head;
 {
     if(head==NULL)//如果为空链表则建立新表再逆置 
     {
         head=hrear_creat(head);
     }
     linklst *p,*s;
     p=head->next;
     head->next=NULL;
     while(p!=NULL)
     {
         s=p;
         p=p->next;
         s->next=head->head;
         head->next=s;    
     }
  }