数组的分类：便于遍历
静态数组：int arr[10]数据过多造成空间溢出，数据过小空间浪费
动态数组：malloc calloc realloc 合理利用空间不能快捷的插入或删除数据（会涉及到大量的数据移动）
知识点一：链表的基本概念
链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构
链表由一系列节点( 链表中每一个元素称为节点)组成，节点在运行时动态生成(malloc) ，每个节点包括两个部分：
1）存储数据元素的数据域 2）存储下一个节点地址的指针域
知识点二：链表结点的定义（结构体实现）
typedef struct stu
{
//数据域(自定义)
int num;
char name[32];
float score;
//指针域
struct stu *next; //保存 下一个节点的地址:
}STU;
知识点三：静态链表
typedef struct stu
{
int num;
char name[32];
float score;
struct stu *next; //保存 下一个节点的地址:
}STU;
void test1()
{
STU datal = {100, "德玛",59};
STU data2 = {101, "小炮",89};
STU data3 = {102, "小法",79};
STU data4 = {103,"盲僧",99};
STU data5 = {104, "快乐风男",39};
//链表头
STU *head = NULL;
head = &datal;
datal.next = &data2;
data2.next = &data3;
data3.next = &data4;
data4.next = &data5;
data5.next = NULL;
//遍历链表
STU *pb = head;
while(pb != NULL)
{
printf("%d %s %f\n", pb->num, pb->name, pb->score) ;
pb = pb->next; //pb指向下一一个节点
}
}
知识点四：动态链表
1、布局整个框架（main.c）
#include<stdio.h>
#include<string.h>
void stu_help(void);
int main(int argc,char *argv[])
{
stu_help();
while(1)
{
printf("请输入操作指令:");
char cmd[32] = "";
scanf( "%s",cmd);
if(strcmp(cmd,"help") == 0)
{
printf("-----help------\n");
}
else if(strcmp(cmd,"insert") == 0)
{
printf("-----insert------\n");
}
else if(strcmp(cmd,"print") == 0)
{
printf("-----print------\n");
}
else if(strcmp(cmd,"search") == 0)
{
printf("-----search------\n");
}
else if(strcmp(cmd,"delete") == 0)
{
printf("-----delete------\n");
}
else if(strcmp(cmd,"free") == 0)
{
printf("-----free------\n");
}
else if(strcmp(cmd,"quit") == 0)
{
break;
}
}
return 0;
}
void stu_help(void)
{
printf("############################\n");
printf("#help:打印帮助信息 #\n");
printf("#insert:插入链表节点 #\n");
printf("#print:遍历链表节点信息 #\n");
printf("#search:查询链表节点 #\n");
printf("#delete:删除链表节点 #\n");
printf("#free:释放链表 #\n");
printf("#quit:退出 #\n");
printf("############################\n");
return;
}
2、链表插入节点之头部之前插入
3、在链表尾部插入
4、链表的有序插入
知识点五：链表查询某个节点
知识点六：删除链表指定节点
知识点七：链表的释放
STU* free_link(STU *head)
{
//1、判断链表是否存在
if(head == NULL)//不存在
{
printf("link not found\n");
retrun head;
}
else //存在
{
STU *pb = head;
//逐个节点释放
while(pb != NULL)
{
//head保存下一个节点的位置
head = pb->next;
//释放pb指向的节点
free(pb);
//pb指向head
pb = head;
}
printf("链表已经释放完毕\n");
return head;
}
return head;
}
知识点八：链表逆序
STU* reverse_link(STU *head)
{
//1、判断链表是否存在
if(head == NULL)//不存在
{
printf("link not found\n");
retrun head;
}
else//存在
{
//int *p,num; //p为int *, num为int
STU *pb,*pr; //pb为STU *,pr 为STU *
//pb保存head->next ( 原因head->next会置NULL)
pb = head->next;
//将head->next置NULL(原因:头节点变尾节点)
head->next = NULL;
while(pb != NULL)
{
//pr 保存pb->next ( 原因:pb->next会指向head)
pr = pb -> next;
//pb->next指向head ( 原因:逆转方向)
pb->next = head ;
//保存逆转方向的代码可以重复执行
head = pb;
pb = pr;
}
return head;
}
return head;
}
知识点九：链表排序
选择法排序：（以数组实现）
#include<stdio.h>
int main()
{
int arr[10] = {0};
int n = sizeof(arr)/sizeof(arr[0]);
int i = 0,j = 0,min = 0;
printf("请输入%d个int数据\n", n);
for(i = 0; i<n; i++)
{
scanf("%d",arr+i);
}
for(i = 0;i < n-1;i++)
{
for(min = i,j = min+1;j < n;j++)
{
if (arr[min] > arr[j])
min = j;
}
if (min != i)
{
int tmp = 0;
tmp = arr[i];
arr[i] = arr[min];
arr [min] = tmp;
}
}
for(i = 0;i < n;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
选择法排序：（以链表实现）
知识点十：认识双向链表
知识点十一：双链表插入
知识点十二：双向链表删除指定节点
知识点十三：结构的浅拷贝和深拷贝
1、指针变量作为结构体的成员
typedef struct
{
int num;
char *name;//指针变量作为结构体的成员
}DATA;
void test01()
{
DATA data = {100, "hehehehaha"};
printf("%d\n",sizeof(DATA));//8字节
printf("num = %d\n" ,data.num) ;
//指针变量作为结构体的成员保存的是空间的地址
printf("name = %s\n", data. name);
}
2、指针变量作为结构体的成员 操作前 必须有合法空间
void test02()
{
DATA data;
printf( "%d\n",sizeof(DATA));
printf("num = %d\n", data.num) ;
//指针变量作为结构体的成员操作前必须有合法的空间
//data.name = "hehe" ;
//给name事先申请一块堆区空间
data.name = (char *)calloc(1,10);
strcpy(data.name,"hahaha");
printf("name = %s\n", data.name ) ;
//如果name指向堆区空间一定要记得释放
if(data. name != NULL )
{
free(data. name) ;
data. name = NULL;
}
}
3、指针变量作为结构体成员，结构体变量间的赋值操作容易导致“浅拷贝”发生
运行结果：出现段错误
两个结构体变量中的指针成员指向同-块堆区空间
void test03()
{
DATA data1;
DATA data2;
data1.num = 100;
data1.name = (char *)calloc(1,10);
strcpy(data1.name,"my data");
//指针变量作为结构体的成员结构体变量间的赋值操作容易导致"浅拷贝”发生
data2 = data1; //"浅拷贝”
printf("data2: num = %d,name = %s\n", data2.num,data2.name);
if(datal.name != NULL)
{
free(data1.name);
data1.name = NULL;
}
if( data2.name != NULL)
{
free(data2.name);
data2.name = NULL;
}
}
4、深拷贝
前提：是指针变量作为结构体的成员
两个结构体变量中的指针成员指向各自的堆区空间
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
int num;
char *name;
} DATA;
void test01()
{
DATA datal ;
DATA data2 ;
datal.num = 100;
datal.name = (char *)calloc(1,12);
strcpy (datal.name,"my data");
data2. num = datal. num;
//为结构体变量 申请 独立空间
data2.name = (char *)calloc(1,12);
strcpy(data2.name,datal.name) ;
printf("data1:num = %d,name = %s\n",datal.num,datal.name);
printf("data2:num = %d,name = %s\n",data2.num,data2.name);
if (datal.name!=NULL)
{
free(datal.name);
datal.name = NULL;
}
if (data2.name!=NULL)
{
free(data2.name);
data2.name = NULL;
}
}
