一，什么是数据结构
1，数据结构的起源
1968年，美国高德娜教授，《计算机程序设计艺术》第一卷《基本算法》，开创了数据结构与算法的先河
数据结构是研究数据之间关系和操作的学科，而非计算方法
数据结构 + 算法 = 程序 美国沃斯提出 这句话揭示了程序的本质
2，数据结构相关基础概念
数据：
所有能够输入到计算机中，能够被程序处理的描述客观事物的符号
数据项：
有独立含义的数据的最小单位，也称为数据域
数据元素：
组成数据有一定含义的基本单位，也称为节点、结点、记录
数据结构：
相互之间存在一种或多种特定关系的数据元素的集合
算法：
数据结构中所具备的功能、解决某种特定问题的方法
3，数据结构的三个方面
数据之间的逻辑关系
数据之间的存储关系
数据结构的运算
二，数据结构的逻辑和存储关系
逻辑关系：
集合：同属于同一个集体，但元素之间没有任何关系
线性结构：数据元素之间存在一对一关系
树型结构：数据元素之间存在一对多关系
图型结构：数据元素之间存在多对多关系
存储关系（物理关系）
顺序结构：
数据元素存储连续的内存中，可以通过数据元素的相对位置来表示关系
优点：支持随机访问，访问查找效率极高，适合用于频繁的结构
缺点：对插入、删除时效率低不方便，内存的空间利用率低、要求高
链式结构：
数据元素存储在彼此相互独立的内存中，每个独立的元素也叫做节点，每个节点中增加一项数据项用于存储其他相关节点的地址，以此表示节点之间的关系
优点：插入、删除更方便，空间利用率极高，内存要求不高
缺点：不支持随机访问，只能从头到尾逐个访问
tap：存储结构、逻辑结构采用哪种要根据实现难度、空间、时间要求、操作习惯等方面综合考虑选择合适的结构
逻辑结构与存储结构的关系：
表： 顺序 链式
树： 链式 顺序
图： 顺序 + 链式
三，数据结构运算
1，创建数据结构 create creat
2，销毁数据结构 destory
3，清空数据结构 clean
4，排序数据结构 sort
5，插入元素 insert
6，删除元素 deltet
7，访问元素 access
8，查询元素 query
9，修改元素 modify
10，遍历数据结构 ergodic show print
四，顺序表和链式表实现
顺序表：
数据项：
存储元素的连续内存的首地址
表的容量
当前元素数量
运算：
创建、销毁、清空、插入、删除、访问、查询、修改、排序、遍历
tap：
1，要时刻保持数据元素的连续性
2，不要越界
链式表：
元素（节点）的数据项：
数据域：可以是任何类型的若干个数据项
指针域：指向下一个节点
若干个节点通过指针域连接到一起就形成了链表
不带头节点的单链表：
第一个节点的数据域是存储有效数据
缺点：添加、删除节点时，可能会修改指向第一个节点的指针，因此参数要使用二级指针，才能更改指针的指向，麻烦
带头节点的单链表：
第一个节点的数据域是不存储有效数据，仅仅只是使用他的指针域永远指向链表的第一个数据有效的节点
优点：插入、删除时会比不带头节点更方便
tap：其他操作都要从头结点的下一个结点开始
功能受限的表结构：
对表结构的部分功能加以限制，形成了特殊的表结构
栈：
只有一个进出口的表结构，先进后出，FILO
顺序栈：
数据域：
存储元素的连续内存的首地址
栈的容量
栈顶的位置
运算：
创建、销毁、入栈、出栈、栈顶、栈满、栈空
栈的应用：
1，函数的调用、栈内存特点
2，生产者和消费者模型（仓库->栈）
3，表达式解析
链式栈：
栈结构数据项：
栈顶节点
节点数量
运算
创建、销毁、入栈、出栈、栈空、栈顶
队列：
有两个端口，一个端口只能入队，另一个只能出队，先进先出 FIFO
顺序队列：
数据项：
存储元素的内存首地址
容量
队头下标 出队
队尾下标 入队
运算：
创建、销毁、入队、出队、队空、队满、队头、队尾、数量
顺序队列的注意点：
由一维数组+队头下标front+队尾下标tail组成，入队tail++，出队front++,为了让队列能够反复使用，我们将队列想象成圆，就可反复利用
front = (front+1)%cal;
tail = (tail+1)%cal;
如何判断队空、队满：
额外多申请一个元素的内存
队空：front == tail
队满：(tail +1)%cal == front
数量：(队尾-队头+1+容量)%容量
代价是空了一个位置不能使用，计算数量时较麻烦
另一种方法是队列结构中多增加一个数据项用于记录数据个数，判断空满直接判断该数据项即可，更方便
链式队列：
由链表节点组成的队列结构
数据项：
队头指针
队尾指针
节点数量
运算：
创建，销毁，队空，入队，出队，队头，队尾
队列的应用：
1，消息队列
2，树的层序遍历 使用队列
3，图的广度优先遍历使用队列
4，封装线程池、数据池
顺序表、链式表的几种运算
顺序表
#include
#include
#include
#include
#define TYPE int
//设计顺序表结构
typedef struct Array
{
TYPE* ptr;//存储元素的内存首地址
size_t cal;//表的容量
size_t cnt;//已存储元素的数量
}Array;
//创建
Array* create_array(size_t size);
Array* create_array(size_t size)
{
//分配顺序表结构内存
Array* arr = malloc(sizeof(Array));
//分配存储元素的内存
arr->ptr = malloc(sizeof(TYPE)*size);
//记录表的容量
arr->cal = size;
//初始化元素数量
arr->cnt = 0;
return arr;
}
//销毁
void destory_array(Array* arr);
void destory_array(Array* arr)
{
free(arr->ptr);
free(arr);
}
//清空
void clean_array(Array* arr);
void clean_array(Array* arr)
{
arr->cnt=0;
}
//插入
bool insert_array(Array* arr,int index,TYPE val);
bool insert_array(Array* arr,int index,TYPE val)
{
//判断表是否已满
if(arr->cnt >= arr->cal) return false;
//判断下标是否破坏了表的连续性
if(index > arr->cnt) return false;
memmove(arr->ptr+index+1,arr->ptr+index,(arr->cnt-index)*sizeof(TYPE));
void show_array(Array* arr);
arr->ptr[index] = val;
arr->cnt++;
return true;
}
//删除
bool deleat_array(Array* arr,size_t index);
bool deleat_array(Array* arr,size_t index)
{
if(index >= arr->cnt) return false;
memmove(arr->ptr+index,arr->ptr+index+1,(arr->cnt-index-1)*sizeof(TYPE));
arr->cnt--;
return true;
}
//访问
bool access_array(Array* arr,size_t index,TYPE* val);
bool access_array(Array* arr,size_t index,TYPE* val)
{
if(index >= arr->cnt) return false;
*val = arr->ptr[index];
return true;
}
//查询
int query_array(Array* arr,TYPE val);
int query_array(Array* arr,TYPE val)
{
for(int i=0;icnt;i++)
{
if(val == arr->ptr[i]) return i;
}
return -1;
}
//修改
bool modify_array(Array* arr,size_t index,TYPE val);
bool modify_array(Array* arr,size_t index,TYPE val)
{
if(index >= arr->cnt) return false;
arr->ptr[index]=val;
return true;
}
//排序
void sort_array(Array* arr);
void sort_array(Array* arr)
{
TYPE temp;
for(int i=0;icnt-1;i++)
{
for(int j=i+1;jcnt;j++)
{
if(arr->ptr[i]>arr->ptr[j])
{
temp=arr->ptr[i];
arr->ptr[i] = arr->ptr[j];
arr->ptr[j] = temp;
}
}
}
}
//遍历
void show_array(Array* arr);
void show_array(Array* arr)
{
for(int i=0;icnt;i++)
{
printf("%d ",arr->ptr[i]);
}
printf("n");
}
int main(int argc,const char* argv[])
{
Array* arr = create_array(10);
for(int i=0;i<5;i++)
{
insert_array(arr,0,i+1);
}
show_array(arr);
//insert_array(arr,2,8);
deleat_array(arr,3);
show_array(arr);
TYPE num = 0;
access_array(arr,2,&num);
printf("num=%dn",num);
int id = query_array(arr,3);
printf("index=%dn",id);
modify_array(arr,0,7);
show_array(arr);
sort_array(arr);
show_array(arr);
}
链式表1（不带头节点）
#include
#include
#include
#define TYPE int
//设计链表中的节点
typedef struct Node
{
TYPE date;//节点的数据域
struct Node* next;//节点的指针域
}Node;
//创建节点
Node* create_node(TYPE date)
{
//分配节点内存
Node* node = malloc(sizeof(Node));
node->date = date;
node->next = NULL;
return node;
}
//头添加
void add_head_list(Node** head,TYPE date)
{
Node* node = create_node(date);
node->next = *head;
*head = node;
}
//按值删除
bool del_value_list(Node** head,TYPE date)
{
if(date == (*head)->date)
{
Node* temp = *head;
*head = temp->next;
free(temp);
return true;
}
for(Node* n=*head;NULL != n->next;n=n->next)
{
//找出待删除节点的上一个节点
if(date == n->next->date)
{
Node* temp = n->next;//备份待删除节点
n->next = n->next->next;//连接待删除节点的上一个和下一个节点
free(temp);//释放删除
return true;
}
}
return false;
}
//按位置删除
bool del_index_list(Node** head,size_t index)
{
if(0 == index)
{
Node* temp = *head;
*head = temp->next;
free(temp);
return true;
}
//待删除节点的上一个
Node* n=*head;
while(0 < --index)
{
n = n->next;
if(NULL == n->next) return false;
}
Node* temp = n->next;
n->next = temp->next;
free(temp);
return true;
}
//排序
void sort_list(Node* head)
{
for(Node* n=head;NULL != n->next;n=n->next)
{
for(Node* i=n->next;NULL != i;i=i->next)
{
if(n->date > i->date)
{
TYPE temp = i->date;
i->date = n->date;
n->date = temp;
}
}
}
}
//访问
bool access_list(Node* head,int index,TYPE* val)
{
Node* node = head;
for(int i=0;inext;
if(NULL == node) return false;
}
*val = node->date;
return true;
}
//遍历
void show_list(Node* head)
{
for(Node* n=head;n != NULL;n=n->next)
{
printf("%d ",n->date);
}
printf("n");
}
int main(int argc,const char* argv[])
{
Node* head = NULL;
for(int i=0;i<10;i++)
{
add_head_list(&head,i+1);
}
show_list(head);
del_value_list(&head,1);
show_list(head);
sort_list(head);
show_list(head);
TYPE num = -10;
access_list(head,0,&num);
printf("%dn",num);
del_index_list(&head,3);
show_list(head);
}
链式表2（带头结点）
#include
#include
#include
#define TYPE int
//设计链表中的节点
typedef struct Node
{
TYPE date;//节点的数据域
struct Node* next;//节点的指针域
}Node;
//创建节点
Node* create_node(TYPE date)
{
//分配节点内存
Node* node = malloc(sizeof(Node));
node->date = date;
node->next = NULL;
return node;
}
//头添加
void add_head_list(Node* head,TYPE val)
{
Node* node = create_node(val);
node->next = head->next;
head->next = node;
}
//尾添加
void add_tail_list(Node* head,TYPE val)
{
Node* node = create_node(val);
Node* n=head;//n找到最后一个节点
while(NULL != n->next) n=n->next;
n->next = node;
}
//按值删除
bool del_value_list(Node* head,TYPE val)
{
Node* n = head;
while(NULL != n->next)
{
if(n->next->date == val)
{
Node* temp = n->next;
n->next = n->next->next;
free(temp);
return true;
}
n=n->next;
}
return false;
}
//按位置删除
bool del_index_list(Node* head,size_t index)
{
Node* n=head;
if(NULL == n->next) return false;
while(0 < index--)
{
n = n->next;
if(NULL == n) return false;
}
Node* temp = n->next;
n->next = temp->next;
free(temp);
return true;
}
//插入
bool insert_list(Node* head,size_t index,TYPE val)
{
Node* node = create_node(val);
Node* n = head;
while(0 < index--)
{
n = n->next;
if(NULL == n) return false;
}
node->next = n->next;
n->next=node;
return true;
}
//修改
bool modify_list(Node* head,TYPE old,TYPE val)
{
for(Node* n=head->next;NULL != n;n=n->next)
{
if(n->date == old)
{
n->date = val;
}
return true;
}
return false;
}
//排序
void sort_list(Node* head)
{
for(Node* n=head->next;NULL != n->next;n=n->next)
{
for(Node* i=n->next;NULL != i;i=i->next)
{
if(n->date > i->date)
{
TYPE temp = i->date;
i->date = n->date;
n->date = temp;
}
}
}
}
//访问
bool access_list(Node* head,int index,TYPE* val)
{
Node* node = head->next;
if(NULL == node) return false;
for(int i=0;inext;
if(NULL == node) return false;
}
*val = node->date;
return true;
}
//查找
int query_list(Node* head,TYPE val)
{
Node* n = head->next
for(int i=0;NULL != n;i++)
{
if(n->date == val) return i;
n=n->next;
}
return -1;
}
//遍历
void show_list(Node* head)
{
for(Node* n=head->next;n != NULL;n=n->next)
{
printf("%d ",n->date);
}
printf("n");
}
int main(int argc,const char* argv[])
{
//头节点，永远指向第一个有效数据
Node* head = create_node(0);
for(int i=0;i<10;i++)
{
add_head_list(head,i+rand()%10);
}
show_list(head);
sort_list(head);
show_list(head);
add_tail_list(head,99);
show_list(head);
del_value_list(head,99);
show_list(head);
del_index_list(head,0);
show_list(head);
del_index_list(head,8);
show_list(head);
insert_list(head,7,70);
show_list(head);
}
栈
顺序栈
#include
#include
#include
#define TYPE int
//设计顺序栈结构
typedef struct ArrayStack
{
TYPE* ptr;//内存首地址
size_t cal;//栈的容量
size_t top;//栈顶下标 从0开始 空增栈
}ArrayStack;
//创建
ArrayStack* creatr_array_stack(size_t cal)
{
//分配内存
ArrayStack* stack = malloc(sizeof(ArrayStack));
//元素内存
stack->ptr = malloc(sizeof(TYPE)*cal);
//记录容量
stack->cal = cal;
//栈顶
stack->top = 0;
return stack;
}
//销毁
void destory_array_stack(ArrayStack* stack)
{
free(stack->ptr);
free(stack);
}
//栈空
bool empty_array_stack(ArrayStack* stack)
{
return 0 == stack->top;
}
//栈满
bool full_array_stack(ArrayStack* stack)
{
return stack->top >= stack->cal;
}
//入栈
bool push_array_stack(ArrayStack* stack,TYPE val)
{
if(full_array_stack(stack)) return false;
stack->ptr[stack->top++] = val;
return true;
}
//出栈
bool pop_array_stack(ArrayStack*stack)
{
if(empty_array_stack(stack)) return false;
stack->top--;
return true;
}
//栈顶
bool top_array_stack(ArrayStack* stack,TYPE* val)
{
if(empty_array_stack(stack)) return false;
*val = stack->ptr[stack->top-1];
return true;
}
bool is_pop_stack(int a[],int b[],int len)
{
//创建一个栈
ArrayStack* tt = creatr_array_stack(len);
for(int i=0,j=0;i
链式栈
#include
#include
#include
#define TYPE int
typedef struct Node
{
TYPE date;
struct Node* next;
}Node;
Node* create_node(TYPE date)
{
Node* node = malloc(sizeof(Node));
node->date = date;
node->next = NULL;
return node;
}
//链式栈结构
typedef struct ListStack
{
Node* top;//栈顶节点
size_t cnt;//节点当前数量
}ListStack;
//创建栈结构
ListStack* create_list_stack(void)
{
ListStack* stack = malloc(sizeof(ListStack));
stack->top = NULL;
stack->cnt = 0;
return stack;
}
//入栈
void push_list_stack(ListStack* stack,TYPE val)
{
Node* node = create_node(val);
node->next = stack->top;
stack->top = node;
stack->cnt++;
}
//栈顶
TYPE top_list_stack(ListStack* stack)
{
return stack->top->date;
}
//栈空
bool empty_list_stack(ListStack* stack)
{
return 0 == stack->cnt;
}
//出栈
bool pop_list_stack(ListStack* stack)
{
if(empty_list_stack(stack)) return false;
Node* temp = stack->top;
stack->top = stack->top->next;
stack->cnt--;
free(temp);
}
//数量
size_t size_list_stack(ListStack* stack)
{
return stack->cnt;
}
//销毁
void destory_list_stack(ListStack* stack)
{
//把所有节点释放才释放栈结构
while(pop_list_stack(stack));
free(stack);
}
int main(int argc,const char* argv[])
{
ListStack* stack = create_list_stack();
for(int i=0;i<10;i++)
{
push_list_stack(stack,i+1);
printf("top:%d size:%dn",top_list_stack(stack),size_list_stack(stack));
}
while(!empty_list_stack(stack))
{
printf("top:%d size:%dn",top_list_stack(stack),size_list_stack(stack));
pop_list_stack(stack);
}
destory_list_stack(stack);
}
队列
顺序队列
#include
#include
#include
#define TYPE int
typedef struct ArrayQueue
{
TYPE* ptr;
size_t cal;
size_t front;//队头
size_t tail;//队尾，即将入队位置
}ArrayQueue;
//创建顺序队列
ArrayQueue* create_array_queue(size_t cal)
{
ArrayQueue* queue = malloc(sizeof(ArrayQueue));
queue->ptr = malloc(sizeof(TYPE)*(cal+1));//多申请一个内存，解决队空、队满问题
queue->cal = cal+1;
queue->front = 0;
queue->tail = 0;
return queue;
}
//销毁
void destory_array_queue(ArrayQueue* queue)
{
free(queue->ptr);
free(queue);
}
//队空
bool empty_array_queue(ArrayQueue* queue)
{
return queue->front == queue->tail;
}
//队满
bool full_array_queue(ArrayQueue* queue)
{
return (queue->tail+1)%queue->cal == queue->front;
}
//入队
bool push_array_queue(ArrayQueue* queue,TYPE val)
{
if(full_array_queue(queue)) return false;
queue->ptr[queue->tail] = val;
queue->tail = (queue->tail+1)%queue->cal;
return true;
}
//出队
bool pop_array_queue(ArrayQueue* queue)
{
if(empty_array_queue(queue)) return false;
queue->front = (queue->front+1)%queue->cal;
return true;
}
//队头
TYPE front_array_queue(ArrayQueue* queue)
{
return queue->ptr[queue->front];
}
//队尾
TYPE tail_array_queue(ArrayQueue* queue)
{
return queue->ptr[(queue->tail-1+queue->cal)%queue->cal];
}
//数量
size_t size_array_queue(ArrayQueue* queue)
{
return (queue->tail - queue->front + queue->cal)%queue->cal;
}
int main(int argc,const char* argv[])
{
ArrayQueue* queue = create_array_queue(10);
for(int i=0;i<10;i++)
{
push_array_queue(queue,rand()%100);
printf("tail:%d size:%d n",tail_array_queue(queue),size_array_queue(queue));
}
}
链式队列
#include
#include
#include
#define TYPE int
typedef struct Node
{
TYPE date;
struct Node* next;
}Node;
Node* create_node(TYPE date)
{
Node* node = malloc(sizeof(Node));
node->date = date;
node->next = NULL;
return node;
}
typedef struct ListQueue
{
Node* front;//队头
Node* tail;//队尾
size_t cnt;//数量
}ListQueue;
//创建
ListQueue* create_list_queue(void)
{
ListQueue* queue = malloc(sizeof(ListQueue));
queue->front = NULL;
queue->tail = NULL;
queue->cnt = 0;
return queue;
}
//队空
bool empty_list_queue(ListQueue* queue)
{
return 0 == queue->cnt;
}
//入队
void push_list_queue(ListQueue* queue,TYPE val)
{
Node* node = create_node(val);
if(empty_list_queue(queue))
{
queue->front = node;
queue->tail = node;
}
else
{
queue->tail->next = node;
queue->tail = node;
}
queue->cnt++;
}
//出队
bool pop_list_queue(ListQueue* queue)
{
if(empty_list_queue(queue)) return false;
Node* temp = queue->front;
queue->front = temp->next;
queue->cnt--;
if(0 == queue->cnt) queue->tail = NULL;
free(temp);
return true;
}
//队头
TYPE front_list_queue(ListQueue* queue)
{
return queue->front->date;
}
//队尾
TYPE back_list_queue(ListQueue* queue)
{
return queue->tail->date;
}
//数量
size_t size_list_queue(ListQueue* queue)
{
return queue->cnt;
}
//销毁
void destory_list_queue(ListQueue* queue)
{
while(pop_list_queue(queue));
free(queue);
}
int main(int argc,const char* argv[])
{
ListQueue* queue = create_list_queue();
for(int i=0;i<10;i++)
{
push_list_queue(queue,i);
printf("t:%d s:%dn",back_list_queue(queue),size_list_queue(queue));
}
printf("------------------------------n");
while(!empty_list_queue(queue))
{
printf("t:%d s:%dn",front_list_queue(queue),size_list_queue(queue));
pop_list_queue(queue);
}
}
