链表--简单学习

1.链表概述：

? ? ? ? 链表是一种数据结构，它采用动态分配存储单元方式。它能够有效地节省存储空间（同数组比较）

? ? ? ? 链表都有一个“头指针”变量（head），它用于指向链表中的一个元素（即用于存放链表中第一个元素的地址）。链表中的元素成为“结点”，链表中的所有结点都是结构体类型，且同一链表中的结点都是同一结构体类型。每个结点都应包括数据部分和下一个结点地址两部分内容。链表的最后一个元素（结点）称为链尾，不再指向其他结点（即该结点的指针成员值为NULL）。

? ? ? ? 链表的访问都是通过指针变量从头结点就开始。

????????由于链表的结点是一个结构体类型，并且结点中的有一个成员用于指向下一个结点。所以定义作为结点的格式：

struct 结构体名
{
    定义数据成员;
    struct 结构体名 *指针变量名;
};

????????例如：

struct student
{
    int num;
    float score;
    struct student *next;
};

struct student a,*p;

2.动态存储分配函数<stdlib.h>

? ? ? ? i.malloc()函数

? ? ? ? 格式：malloc(size)

? ? ? ? 作用是在内存的动态存储区中分配一个长度为size个字节的连续空间，函数返回值为一个指向分配域起始地址的指针（类型是void*），若分配失败，则返回NULL。

? ? ? ? 例如：开辟一个用于存放struct student 数据的内存空间，并让p指向该空间：

struct student *p = (struct student*)malloc(sizeof(struct student));

? ? ? ? ii.free()函数

? ? ? ? 格式：free(p);

? ? ? ? 作用是释放用malloc()分配的内存。

3.链表操作

? ? ? ? i.建立动态链表

#include<stdio.h>
#include<stdlib.h>

struct node 
{
	int num;
	struct node* next;
};

int main() {
	struct node* p, * q, * head;
	p = (struct node*)malloc(sizeof(struct node));
	scanf("%d", &p->num);
	head = p;
	q = (struct node*)malloc(sizeof(struct node));
	scanf("%d", &q->num);
	q->next = NULL;
	p->next = q;
	printf("%d %d",p->num,p->next->num);
	return 0;
}

? ? ? ? ii.访问链表

	struct node *r;
	r=head;
	int sum=0;
	while(r!=NULL){
		sum=sum+r->num;
		r=r->next;	
	}

? ? ? ? iii.链表结点的删除

? ? ? ? a、请将结点b从链表中删除

p->next = p->next->next;

? ? ? ? b、请将结点a从链表中删除并让head重新指向链表中的第一个结点

head = head->next;

? ? ? ? c、删除尾结点

p->next = NULL;

? ? ? ? iiii.增加结点(q指向的是要插入结点的地址，p指向的的是要插入结点的前一个结点的地址)

? ? ? ? a、请将结点c插入结点之间，形成新链表

q->next = p->next;
p->next = q;

? ? ? ? b、请将结点c插到已有链表的末尾

p->next = q;
q->next = NULL;

? ? ? ? c、请将结点c插到已有链表的前面?

q-next = head;
head = q;