数据结构简单入门/复习(一)-线性链表(C语言)(2020/11/18更新)

这个系列是为了简单入门与复习而作的,因此内容并不完全,如本篇的线性链表除了创建、插入、删除外,还有一些较为复杂的操作,并且,本篇内容提到的也不涉及任何判断成功与否的代码,但个人认为,只要这三个部分掌握了,剩余的基础用法都能很快解决。

2020/11/18:
更新了较完整的链表代码。
文章排版美化。

基础知识

指针的基本使用。

结构体的定义。

分配内存:
使用 待分配变量 = (分配变量数据类型)malloc(分配大小);
其中,分配大小一般用 sizeof(数据类型) 获得,如果需要分配N倍的空间,使用sizeof(数据类型)*N
假设要给 指针node 分配五个 Node*类型 的空间,就应该
node = (Node*)malloc(sizeof(Node)*5);

释放指针内存:
即时释放,可以防止过多过期数据占据内存。free(指针名称)
例如
int *node;
node = (int*)malloc(sizeof(int));
free(node); //这样就释放掉了上一行分配的内存。

free()是用来释放内存的,一个单纯指向性的指针并不需要释放,但如果这个指向性的指针 被分配了内存 来存储临时数据,则应该释放。(这里入门搞不懂,问题不大,多写点就有感觉了。)

定义与创建

线性链表的存取必须由头指针开始,头指针仅用来指向第一个数据结点的位置。
线性链表包括两个域,数据域与指针域,数据域用来存储数据,而指针域用来指向链表的下一个结点(Node)。
且因为线性链表的最后结点没有后继结点,因此其指针域为空(NULL)。

即,对于一个有三个数据的链表结构 |data – next|,它的形式应该是这样的:
|empty – first| -> |data1 – second| -> |data2 – third| -> |data3 – NULL|

#define ElemType int      //元素类型设置为int
typedef struct LNode{    //链表结构定义
    ElemType data;       //数据域
    struct LNode *next;  //指针域
}LNode;

链表的创建及结点添加

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

#define ElemType int      //元素类型设置为int
typedef struct LNode{    //链表结构定义
    ElemType data;       //数据域
    struct LNode *next;  //指针域
}LNode;

int main(){
    

    //链表头结点创建
    LNode *LHead;
    LHead = (LNode*)malloc(sizeof(LNode));    //使用malloc为头结点分配内存空间
    LHead->next = (LNode*)malloc(sizeof(LNode));    //为头结点的下一个结点,即第一个数据结点分配内存。
    
    //设置一个临时变量存储当前结点所在的位置。
    LNode *LTemp;

    //将临时变量调整到第一个数据结点。
    LTemp = LHead->next;

    //通过临时变量  对第一个数据结点赋值,及下一个结点的创建。
    LTemp->data = 1;     //等效为 LHead->next->data = 1;
    LTemp->next = (LNode*)malloc(sizeof(LNode));    //同上等效

    //将临时变量设置为第二个数据结点。
    LTemp = LTemp->next;

    //通过临时变量  为第二个数据结点赋值,且第二个结点为最后一个结点。
    LTemp->data = 22;
    LTemp->next = NULL;    //表示第二个结点的下一个结点地址是NULL,即没有下一个结点


    system("PAUSE");      //在运行结束后停留
    return 0;
}

通过这个方法,即可创建一个
|empty – first| -> |1 – second| ->|22 – NULL|
的线性链表。

插入结点

目的:只知道A地址,结点B需要插入到A与C当中,此时A的下一个结点是C(A->next == C;)

原理:先将B的next设置为C,再将A的next设置为B
原因:这样可以在 不加入临时变量 记录C的地址 的前提下,将B插入。

B->next = A->next;
A->next = B;

删除结点

目的:只知道A地址,A的下一个是B,B的下一个是C,需要删除B

原理:添加临时变量记录C的地址,将B先释放,再设置C。或记录B,先设置C再释放B。

LNode *temp;
temp = A->next->next;    //将temp设置成A的下一个的下一个,即C
free(A->next);    //释放B结点
A->next = temp;    //将A的下一个设置为C

这样不释放temp,因为此时temp存储的是C的内存,不是新增加的临时内存,这个temp只是指示器,不需要释放。

一份迟来的完整代码

这篇文章写完后的第三个月,在做题的时候,用到了链表,于是就写了下完整的单链表代码,
然后发现之前因为用不习惯wordpress,排版有点丑,改了下。

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

typedef struct lNode{
	int data;
	struct lNode *next;
}lNode;

lNode *createLink();
void insertLNode(lNode *node, int newData);
void deleteLNode(lNode *node);
void printLink(lNode *head);

int main() {
	lNode *head = createLink();
	printf("输出链表内容:");
	printLink(head);

	system("PAUSE");
	return 0;
}

lNode *createLink() {		//创建链表,并返回一个带头结点的链表。
	lNode *head = (lNode*)malloc(sizeof(lNode));
	lNode *node = head;
	head->next = NULL;
	int i = 0;
	for (i = 1; i <= 5; i++) {	//链表结点自动生成,用作测试
		insertLNode(node, i);
		node = node->next;
	}
	return head;
}

void insertLNode(lNode *node, int newData) {	//插入结点
	if (node->next == NULL) {
		node->next = (lNode*)malloc(sizeof(lNode));
		node->next->next = NULL;
		node->next->data = newData;
	}
	else {
		lNode *temp = (lNode*)malloc(sizeof(lNode));
		temp->next = node->next;
		temp->data = newData;
		node->next = temp;
	}
}

void deleteLNode(lNode *node) {		//删除结点
	if (node->next == NULL) {
		free(node);
	}
	else {
		lNode *temp;
		temp = node->next;
		node->data = temp->data;
		node->next = temp->next;
		free(temp);
	}
}

void printLink(lNode *head) {		//打印带头结点的链表,若不带头结点,将第一行head->next改为head即可。
	lNode *node = head->next;
	while (node) {
		printf("%d ", node->data);
		node = node->next;
	}
	printf("\n");
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注