数据结构-单链表和顺序表的基本操作

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
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<malloc.h>
#define N 8 //最大节点数
//定义结构体
typedef struct node
{
int n;
struct node *next;
}Node;
//释放链表所有结点
void freeAll(Node *p){
Node *q;
while(p!=NULL)
{
q=p;p=p->next;
free(q);
}
}
//输出链表
void print(Node *p){
Node *q;
while(p!=NULL)
{
printf("%d ",p->n);
p=p->next;
}
printf("n");
}
//创建8个取值100-999的随机数
Node* creat()
{
Node *h,*p;
srand(time(NULL));
h=p=(Node *)malloc(sizeof(Node));
for(int i=0;i<N;i++)
{
p->n=rand()%900+100;
if(i!=N-1)
{p->next=(Node *)malloc(sizeof(Node));p=p->next;}
}
p->next=NULL;
return h;
}
//检索链表中值为n的节点
void check(Node *p,int n)
{
int i=1;
while(p!=NULL)
{
if(p->n==n){printf("%dn",i);return;}
p=p->next;i++;
}
printf("未找到!n");
}
//插入节点,值为n,位置为pos
void insert(Node *h,int n,int pos)
{
Node *p,*q;p=q=h;
int i=1;
if(pos==1){
p=(Node *)malloc(sizeof(Node));
p->n=h->n;h->n=n;
p->next=h->next;h->next=p;return;
}
while(p!=NULL&&i!=pos){q=p;p=p->next;i++;}//找出位置
if(p==NULL){printf("插入位置不合理!n");return;}
p=(Node *)malloc(sizeof(Node));
p->n=n;
p->next=q->next;
q->next=p;
print(h);
}
//删除节点
void del(Node *h,int n)
{
Node *p,*q;p=q=h;
while(p->n!=n&&p!=NULL){q=p;p=p->next;}
if(p==NULL)return;
if(p->next==NULL){q->next=NULL;return;}
p->n=p->next->n;
p->next=p->next->next;
}
//链表反转
void reverse(void *head)//head为主函数指针h的地址
{
Node *h=(Node*)*(int*)head,*p,*q;
//改变头节点钩子
p=h->next;h->next=NULL;
q=p->next;p->next=h;
//改变后续节点钩子
while(q!=NULL)
{
h=q->next;
q->next=p;
p=q;q=h;
}
*(int *)head=(intptr_t)p;//改变主函数h值
}
int main()
{
Node *h;//链表头
h=creat();
print(h);
//	check(h,h->next->n);
//	insert(h,234,8);
//	del(h,n);
reverse(&h);
print(h);
} 

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
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define N 8 //最大元素数
typedef int DataType;
//声明结构体
typedef struct node
{
DataType data[N];
int len;
}Node;
//创建
void creat(Node *f,int n)
{
srand(time(0));
f->len=0;for(int i=0;i<N;i++)f->data[i]=0;//初始化
for(int i=0;i<n;i++)
{
f->data[i]=rand()%900+100;
f->len++;
}
}
//输出顺序表
void print(Node *f)
{
for(int i=0;i<f->len;i++)
printf("%d ",f->data[i]);
printf("n");
}
//查找
void check(Node *f,int n)
{
int pos=1;
for(int i=0;i<f->len;i++)
{
if(f->data[i]==n){printf("position:%dn",pos);return;}
}
printf("No Findn");
}
//插入
void insert(Node *f,int n,int pos)
{
if(f->len==N||pos>N){printf("errorn");return;}
int t;
for(int i=f->len;i>pos-1;i--)
f->data[i]=f->data[i-1];
f->data[pos-1]=n;
f->len++;
}
//删除
void del(Node *f,int n)
{
for(int i=0;i<f->len;i++)
{
if(f->data[i]==n)
{
for(int j=i;j<f->len-1;j++)
f->data[j]=f->data[j+1];
f->len--;
return;
}
}
}
//反转
void reverse(Node *f)
{
int t;
for(int i=0,j=f->len-1;i<j;i++,j--)
{
t=f->data[i];
f->data[i]=f->data[j];
f->data[j]=t;
}
}
int main()
{
Node form;//定义结构体(唯一)
creat(&form,5);
//	check(&form,156);
insert(&form,5,1);
//	insert(&form,123,8);
//	del(&form,5);
reverse(&form);
print(&form);
return 0;
}