THIS IS B3c0me

记录生活中的点点滴滴

0%

顺序表和链表

数据结构=结构定义+结构操作

1.顺序表
1 2 3 4 5

size=9; length=5; data_type=xxx;

(1)顺序表的插入操作
1 2 6 3 4 5

size=9; length=6; data_type=xxx;

(2)顺序表的删除操作
1 2 6 3 4 5

size=9; length=5; data_type=xxx;

(3)顺序表的代码演示
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
  #include<stdio.h>
#include<stdlib.h>
#include<time.h>
//结构定义
typedef struct Vector{
int *data;
int size,length;
}Vector;
//初始化一个可以存储n个元素的顺序表(顺序表的初始化操作)
Vector *init(int n)
{
Vector *vec=(Vector *)malloc(sizeof(Vector));
vec->data=(int *)malloc(sizeof(int)*n);
vec->size=n;
vec->length=0;
return vec;
}
//顺序表的销毁工作
void clear(Vector *vec)
{
if(vec==NULL)return ;
free(vec->data);
free(vec);
return ;
}
//扩容操作
int expand(Vector *vec)
{
vec->size*=2;
vec->data= (int*)realloc(vec->data,sizeof(int)*vec->size);
return 1;
}
//插入
int insert(Vector *vec,int ind,int val)
{
//判断顺序表是否有效
if(vec==NULL) return 0;//如果数据表是空的(没有空间)则无效
if(vec->length==vec->size) return 0;//如果数据表已满则无效
if(!expand(vec)){
return 0;
}
printf("expand to %d \n",vec->size);//输出扩容的结果
if(ind<0||ind>vec->length) return 0;//位置超前或溢出表空间则无效
//数据表中插入元素,注意要从后往前插入,否则会破坏原有数据
for(int i=vec->length-1;i>=ind;i--){
vec->data[i]=vec->data[i-1];
}
vec->data[ind]=val;
vec->length+=1;
return 1;//返回1表示插入动作完成

}
//删除
int erase(Vector *vec,int ind)
{
if(vec==NULL) return 0;
if(vec->length==0) return 0;
if(ind<0||ind>=vec->length) return 0;
for(int i=ind+1;i<=vec->length;i++){
vec->data[i-1]=vec->data[i];
}
vec->length-=1;
return 1;

}
//输出顺序表
void output(Vector *vec)
{
printf("Vector(%d)=[",vec->length);
for(int i=0;i<=vec->length;i++){
if(i!=0){
printf(", ");
}
printf("%d",vec->data[i]);
}
printf("]\n");
return ;
}

int main()
{
srand(time(0));//按照时间取随机数,需要导入<time.h>
#define MAX_OP 20 //定义一个最大选项的宏
Vector *vec=init(1);//初始化顺序表
int op,ind,val;
for(int i=0;i<=MAX_OP;i++){
op=rand()%2;//随机产生0或1
ind=rand()%(vec->length+1);
val=rand()%100;//随机产生1到100的数
switch(op){
case 0:{
printf("inset %d at %d to vector\n",val,ind);
insert(vec,ind,val);
}break;
case 1:{
printf("erase item %d from vector\n",ind);
erase(vec,ind);
}break;

}
output(vec);//每进行一次操作之后输出一次数表
}

return 0;
}
运行结果:

(4)关于realloc函数

a. realloc函数先尝试在原来的数表后面去扩展空间 ,如果成功,则返回原来的首地址(记为p)

b. 如果原有数表之后无法再继续扩充,realloc函数会调用malloc函数,真正地去重新分配空间,然后把原来空间中的数据拷贝到新的空间,最后再返回新申请空间的首地址 (p’)

c. malloc申请新的空间并完成拷贝之后会自动释放原来p的空间

d. 如果申请p’的步骤都失败了,realloc不会释放原来的空间,会返回一个空地址(无法找到原来地址,会造成内存泄漏)

e. 上述bug解决办法:

1
2
3
4
5
6
int new_size=vec->size*2;
int *p=(int*)realloc(vec->data,sizeof(int)*new_size);//新建一个指针存储realloc的返回地址
if(p==NULL) return 0;
vec->size=new_size;
vec->data=p;
return 1;
2.链表

链表的插入

单向循环链表

头指针存储的是尾结点的地址

链表的代码演示
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

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//定义链表结点
typedef struct ListNode
{
//数据域
int data;
//指向下一个结点的指针域
struct ListNode* next;
}ListNode;
//定义链表结构
typedef struct LinkList
{
//指向头结点的指针
ListNode head;
//链表的总长度
int length;
}LinkList;
//初始化链表结点
ListNode* init_ListNode(int val)
{
//定义一个指针指向链表结点
ListNode* p = (ListNode*)malloc(sizeof(ListNode));
//给链表赋值
p->data = val;
p->next = NULL;
return p;
}
//初始化链表
LinkList* init_LinkList()
{
//定义一个指向链表的指针
LinkList* l = (LinkList*)malloc(sizeof(LinkList));
//初始化链表的头指针
l->head.next = NULL;
//开始链表的总长度为0
l->length = 0;
return l;
}
int insert(LinkList* l, int ind, int val)
{
if (l == NULL)return 0;
if (ind<0 || ind>l->length)return 0;
ListNode* p = &(l->head), * node = init_ListNode(val);
while (ind--) {
p = p->next;
}
node->next = p->next;
p->next = node;
l->length += 1;
return 1;
}

//销毁结点
void clear_ListNode(ListNode* node)
{
if (node = NULL)return;
free(node);
return;
}
//销毁链表 结点
void clear_LinkList(LinkList* l)
{
if (l == NULL) return;
ListNode* p = l->head.next, * q;
while (p) {
q = p->next;
clear_ListNode(p);
p = q;
}
free(l);
return;
}
//销毁链表
int erase(LinkList* l,int ind)
{
if (l == NULL)return 0;
if (ind < 0|| ind >= l->length) return 0;
ListNode* p = &(l->head), * q;
while (ind--) {
p = p->next;
}
q = p->next->next;
clear_ListNode(p->next);
p->next = q;
l->length -= 1;
return 1;

}
void output(LinkList* l)
{
printf("LinkList(%d)=", l->length);
ListNode* i =l->head.next;
for (i; i; i = i->next) {
printf("%d -> ", i->data);
}
printf("NULL\n");
return;
}
#define MAX_OP 30
int mian()
{
LinkList* l = init_LinkList();
srand(time(0));
int i = 0;
for (i = 0; i < MAX_OP; i++) {
int op = rand() % 4;
int ind = rand() % (l->length + 1);
int val = rand() % 100;

switch (op) {
case 0:
case 1:
case 2: {
printf("insert %d at %d to LinkList=%d",
val, ind, insert(l, ind, val));
break;
}
case 3: {
printf("erase item at %d from LinkList=%d", ind,
erase(l, ind));
break;
}
}
output(l);
printf("\n");
}


return 0;
}

欢迎关注我的其它发布渠道