当前位置：首页 > java >正文

数据结构学习（day01）

java 2025/8/10 13:44:33

1.数据结构基本概念

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它是计算机存储、组织数据的方式，直接影响程序的效率和性能。

2.数据结构分类

1.逻辑结构

集合结构：所有数据都在一个集合中，元素间关系平等。

线性结构：数据之间是一对一的关系，如数组、链表。

树状结构：数据之间是一对多的关系，如二叉树、B树。

2.物理结构（存储结构）

顺序存储：数据存储在连续的存储单元中，如数组。

链式存储：数据存储单元可以是任意的，通过指针连接，如链表。

链式存储概述

线性表的链式存储（单向链表）解决了顺序存储的以下问题：

插入和删除效率低（顺序表需要移动大量元素）
动态存储问题（顺序表需要预先分配固定空间）

特点：

存储单元可以是连续的，也可以是不连续的。

每个节点（Node）包含：

数据域：存储数据元素

指针域：存储下一个节点的地址通过指针链接各个节点，形成链式结构。

单向链表的基本操作（C语言实现）

头文件定义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef int DATATYPE;  // 数据类型可自定义typedef struct LinkNode {DATATYPE data;          // 数据域struct LinkNode *next;  // 指针域
} LinkNode;typedef struct LinkList {LinkNode *head;  // 头指针int clen;        // 当前链表长度
} LinkList;

创建链表

LinkList *CreateLinkList() {LinkList *ll = (LinkList *)malloc(sizeof(LinkList));if (ll == NULL) {fprintf(stderr, "CreateLinkList malloc failed\n");return NULL;}ll->head = NULL;ll->clen = 0;return ll;
}

头插法

int InsertLinkList(LinkList *ll, DATATYPE *data) {if (ll == NULL || data == NULL) {fprintf(stderr, "Invalid arguments\n");return 1;}LinkNode *newnode = (LinkNode *)malloc(sizeof(LinkNode));if (newnode == NULL) {fprintf(stderr, "InsertLinkList malloc failed\n");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = ll->head;  // 新节点指向原头节点ll->head = newnode;        // 更新头指针ll->clen++;return 0;
}

判断链表是否为空

int IsEmptyLinkList(LinkList *ll) {if (ll == NULL) {fprintf(stderr, "Invalid argument\n");return -1;}return (ll->head == NULL) ? 1 : 0;
}

显示链表

void ShowLinkList(LinkList *ll) {if (ll == NULL || ll->head == NULL) {printf("LinkList is empty\n");return;}LinkNode *temp = ll->head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}

查找节点

LinkNode *SearchLinkList(LinkList *ll, DATATYPE key) {if (ll == NULL || ll->head == NULL) {return NULL;}LinkNode *temp = ll->head;while (temp != NULL) {if (temp->data == key) {return temp;}temp = temp->next;}return NULL;
}

删除节点

int DeleteLinkList(LinkList *ll, DATATYPE key) {if (ll == NULL || ll->head == NULL) {fprintf(stderr, "LinkList is empty\n");return 1;}LinkNode *prev = NULL;LinkNode *curr = ll->head;while (curr != NULL) {if (curr->data == key) {if (prev == NULL) {  // 删除头节点ll->head = curr->next;} else {             // 删除中间或尾节点prev->next = curr->next;}free(curr);ll->clen--;return 0;}prev = curr;curr = curr->next;}fprintf(stderr, "Key not found\n");return 1;
}