|
文章结构：
第一部分是描述相关信息，第二部分是相关操作（初始化、增删改查），第三部分是解答相关习题（《数据结构–严蔚敏》），第四部分是leetcode题目（一道easy+一道middle）
青春的幻想既狂热又可爱。一约肖特豪斯
线性表
线性表是由相同数据类型的 nn 个数据元素 a0，a1，an?1组成的有限序列。一个数据元素可以由若干个数据项组成。若用 LL 命名线性表，则其一般表示如下：
L=（a0，a1……an?1）
顺序表
信息描述
顺序表是在计算机内存中以数组形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。
设顺序表的第一个元素a0，的存储地址为 Loc(a0)，每个元素占 d 个存储空间，则第 i 个元素的地址为
Loc(a i?1)=Loc(a0)+(i?1)×d
顺序表在程序中通常用一维数组实现，一维数组可以是静态分配的，也可以是动态分配的。
- 在静态分配时，由于数组的大小和空间是固定的，一旦空间占满，就无法再新增数据，否则会导致数据溢出。
- 而在动态分配时，存储数组的空间在程序执行过程中会动态调整大小，当空间占满时，可以另行开辟更大的存储空间来储存数据。
优点和缺点：
- 顺序表最主要的特点是可以进行 随机访问，即可以通过表头元素的地址和元素的编号（下标），在 O(1) 的时间复杂度内找到指定的元素。
- 顺序表的不足之处是插入和删除操作需要移动大量的元素，从而保持逻辑上和物理上的连续性。
为什么不用数组？在函数中定义的数组是在栈段中的，但是栈段在内存中被限制了大小
初始化、增删改查
顺序表的动态存储分配
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
typedef struct Vector {
int* data;
int len;
int size;
}Vec;
Vec* init(int n) {
Vec* v = (Vec*)malloc(sizeof(Vec));
v->data = (int*)malloc(sizeof(int) * n);
v->size = n;
v->len = 0;
return v;
}
void freeVec(Vec* v) {
if (v) {
free(v->data);
free(v);
}
return;
}
int insert(Vec* v, int idx, int val) {
if (v == NULL) {
return 0;
}
if (idx < 0 || idx > v->len) {
return 0;
}
if (v->len == v->size) {
return 0;
}
memcpy(v->data + idx + 1, v->data + idx, sizeof(v->len - idx));
v->data[idx] = val;
v->len++;
return 1;
}
void delete(Vec* v, int idx) {
if (v == NULL) {
return 0;
}
if (idx < 0 ||| idx >= v->len) {
return 0;
}
memcpy(v->data + idx, v->data + idx + 1, sizeof(v->len - idx - 1));
v->len--;
return 1;
}
int expand(Vec* v) {
if (v == NULL) {
return 0;
}
int expsize = v->size;
while (expsize) {
int tmp* = realloc(v->data, sizeof(int) * (v->size + expsize));
if (tmp) {
break;
}
expsize >>= 2;
}
v->data = tmp;
v->size += expsize;
return 1;
}
链表
信息描述
链表想象成火车，火车头便是链表的表头，每节车厢就是链表的元素，车厢里载的人和物就是元素的数据域，连接车厢的部件就是元素的指针。由此，我们可以得出链表的一个特点：元素之间前后依赖，串联而成。
为什么不用顺序表？顺序表的插入和删除需要移动大量元素，浪费资源
链表是种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是
通过链表中的指针链接次序实现的数据结构。
我个人觉得链表把头结点，头指针，第一个结点和最后一个结点的位置弄懂了就能懂了，我个人的理解是：头指针只是一个指针，初始化一个链表类型的指针后她就是一个空链表，而这个头指针在传入函数的时候该头指针代表是一个头结点，但是这个头结点可以为NULL
初始化、增删改查
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node *next;
}Node, *LinkedList;
LinkedList insert(LinkedList head, Node *node, int index) {
if (head == NULL) {
if (index != 0) {
printf("failed\n");
return head;
}
head = node;
printf("success\n");
return head;
}
if (index == 0) {
node->next = head;
head = node;
printf("success\n");
return head;
}
Node *current_node = head;
int count = 0;
while (current_node->next != NULL && count < index - 1) {
current_node = current_node->next;
count++;
}
if (count == index - 1) {
node->next = current_node->next;
current_node->next = node;
printf("success\n");
return head;
}
printf("failed\n");
return head;
}
void output(LinkedList head) {
if (head == NULL) {
return;
}
Node *current_node = head;
while (current_node != NULL) {
printf("%d ", current_node->data);
current_node = current_node->next;
}
printf("\n");
}
LinkedList delete_node(LinkedList head, int index) {
if (head == NULL) {
printf("failed\n");
return head;
}
LinkedList current_node = head;
if (index == 0) {
head = head->next;
free(current_node);
printf("success\n");
return head;
}
int count = 0;
while (current_node->next != NULL && count < index-1) {
current_node = current_node->next;
count++;
}
if (count == index-1 && current_node->next != NULL) {
LinkedList node = current_node->next;
current_node->next = node->next;
free(node);
printf("success\n");
return head;
}
else {
printf("failed\n");
return head;
}
}
LinkedList reverse(LinkedList head) {
if (head == NULL) return head;
LinkedList current_node, next_node;
current_node = head->next;
head->next = NULL;
while (current_node != NULL) {
next_node = current_node->next;
current_node->next = head;
head = current_node;
current_node = next_node;
}
return head;
}
void clear(LinkedList head) {
Node *current_node = head;
while (current_node != NULL) {
Node *delete_node = current_node;
current_node = current_node->next;
free(delete_node);
}
}
int main() {
LinkedList linkedlist = NULL;
int n;
int a, b;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int signal;
scanf("%d", &signal);
if (signal == 1) {
scanf("%d %d", &a, &b);
LinkedList node = (LinkedList)malloc(sizeof(Node));
node->data = b;
node->next = NULL;
linkedlist = insert(linkedlist, node, a);
}
else if (signal == 2) {
output(linkedlist);
}
else if (signal == 3) {
scanf("%d", &a);
linkedlist = delete_node(linkedlist,a);
}
else if (signal == 4) {
linkedlist = reverse(linkedlist);
}
}
return 0;
}
特殊链表
循环链表：是另一种形式的链式存储结构，她的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点触发均可找到表中其他结点
LinkedList insert(LinkedList head, Node *node, int index) {
if (head == NULL) {
if (index != 0) {
return head;
}
head = node;
head->next = head;
return head;
}
if (index == 0) {
node->next = head->next;
head->next = node;
return head;
}
Node *current_node = head->next;
int count = 0;
while (current_node != head && count < index - 1) {
current_node = current_node->next;
count++;
}
if (count == index - 1) {
node->next = current_node->next;
current_node->next = node;
}
if (node == head->next) {
head = node;
}
return head;
}
双向链表：在单链表中找到下一个结点的时间复杂度为O(1)，找上一个结点的时间复杂度为O(n)，为了克服这种缺点，可以利用双向链表。
typedef struct DuLNode {
int data;
struct DuLNode* next;
struct DuLNode* prior;
};
静态链表
#define MAXSIZE 100
typedef struct {
int data;
int cur;
}Lisk[MAXSIZE];
Leetcode
leetcode上面的题目一般是头结点即第一个结点（即无头结点）
|