数据结构学习总结

　　本文主要记录自己学习和记录相关总结，比较乱勿怪，
　　1、C语言链表
　　c语言的单向链表翻转是面试官常问的问题之一,故此,咱就谈一谈,链表并不是如此可怕,学不会,想不通.
　　链表和数组一样都是存储数据,链表是非连续,非顺序的存储结构.
　　链表是灵活的内存动态管理(随机分配空间),删除创建结点非常方便
　　链表组成:由一系列结点组成.
　　链表结点:实际上是结构体变量.
　　typedef struct _LINKNODE
　　{
　　int data;// 数据域
　　struct _LINKNODE *next;// 指针域
　　}Link_Node;
　　链表结点包含两个部分:
　　1.存储数据元素的数据域(结构体),
　　2.存储下一个结点地址的指针域.
　　上图中的就是一个简单的单向链表,明白了单向链表就可以进军其余的链表结构了,都是一一相通的.
　　结点:data数据域就是存放的结构体(含有各种数据),或者理解为int data;
　　next就是链表的核心了,就是一个指针,指向下一个结点,与下一个结点建立联系
　　2. 链表和数组的区别
　　数组:一次性分配连续的存储区域,int num[60] = {0};
　　优点:随机访问元素效率高
　　缺点:
　　l 开辟内存过大时,易分配失败
　　l 插入和删除元素效率低下
　　链表:无需一次性分配连续的存储空间,只需要分配n块结点存储区域,通过指针建立联系
　　优点:
　　l 不需要一次性分配连续的存储区域
　　l 删除和插入效率高
　　缺点:
　　随机访问元素效率低
　　3. 链表分类
　　l 1. 静态链表和动态链表
　　链表按照线性表链式存储结构分为静态链表和动态链表
　　静态链表:是在初始化的时候分配好足够的内存空间,存储空间是静态的,分配在栈上,模拟数组实现的,是顺序的存储结构
　　动态链表:是动态申请内存的,每个节点物理地址不连续
　　静态链表实例:
　　#pragma warning(disable:4996)
　　#include 
　　#include 
　　#include 
　　// 定义链表结点
　　typedef struct _LINKNODE
　　{
　　int data;// 数据域
　　struct _LINKNODE *next;// 指针域
　　}Link_Node;
　　int main(int argc, char *argv[])
　　{
　　// 初始化三个链表结点(结构体)
　　Link_Node Node1 = {1,NULL};
　　Link_Node Node2 = {2,NULL};
　　Link_Node Node3 = {3,NULL};
　　// 链表串联起来,第一个结点指向第二个
　　Node1.next = &Node2;// Node1的next指针指向Node2
　　Node2.next = &Node3;
　　Node3.next = NULL;// 尾结点
　　// 定义头结点,指向第一个结点
　　Link_Node *head = &Node1;
　　// 遍历链表,头结点-->尾结点
　　while (head != NULL)
　　{
　　printf(＂data : [ %d ] ＂,head->data);
　　// 指针下移
　　head = head->next;
　　}
　　printf(＂hello... ＂);
　　system(＂pause＂);
　　return 0;
　　}
　　动态链表实例:
　　#pragma warning(disable:4996)
　　#include 
　　#include 
　　#include 
　　// 定义链表结点
　　typedef struct _LINKNODE
　　{
　　int data;// 数据域
　　struct _LINKNODE *next;// 指针域
　　}Link_Node;
　　int main(int argc, char *argv[])
　　{
　　// 动态申请3个结点
　　Link_Node *Node1 = (Link_Node *)malloc(sizeof(Link_Node));
　　// 初始化数据域
　　Node1->data = 1;// Node是指针所以用指向箭头
　　Link_Node *Node2 = (Link_Node *)malloc(sizeof(Link_Node));
　　Node2->data = 2;
　　Link_Node *Node3 = (Link_Node *)malloc(sizeof(Link_Node));
　　Node3->data = 3;
　　// 建立结点关系
　　Node1->next = Node2;// Node1的next指向Node2;
　　Node2->next = Node3;
　　Node3->next = NULL;
　　// 定义头结点指向第一个结点Node1
　　Link_Node *head = Node1;
　　// 遍历链表
　　while (head != NULL)
　　{
　　printf(＂data:[ %d ] ＂,head->data);
　　// 指针下移
　　head = head->next;
　　}
　　printf(＂hello... ＂);
　　system(＂pause＂);
　　return 0;
　　}
　　l 2. 带头链表和不带头链表
　　n 带头链表:固定一个节点作为头结点,不关心数据域,起一个标志位的作用,链表结点如何变化,此头结点固定不变
　　n 不带头结点:头结点不固定,所有结点都可以作为头,可以随机变化
　　链表的基本操作基于单向链表1. 创建链表结点域
　　链表结点:数据域和指针域à结构体
　　typedef struct _LINKNODE
　　{
　　int data;// 数据域
　　struct _LINKNODE *next;// 指针域
　　}Link_Node;
　　2. 创建链表
　　建立带头结点的单向链表,循环创建结点,结点数值为<=0时,作为结束,链表的头结点地址作为函数值返回.
　　Link_Node* Init_Link_Node()
　　{
　　Link_Node *cur = NULL;// 保存上一个结点
　　Link_Node *pNew = NULL;// 辅助指针
　　Link_Node *head = NULL;// 固定为头结点
　　// 创建头结点
　　pNew = (Link_Node *)malloc(sizeof(Link_Node));
　　// 初始化头结点(有头结点不保证数据安全)
　　pNew->data = -1;
　　pNew->next = NULL;
　　head = cur = pNew;// head作为头结点,cur保存结点
　　// 循环创建结点
　　int dataid = 0;
　　while (1)
　　{
　　printf(＂请输入data id编号:＂);
　　scanf(＂%d＂,&dataid);
　　if (dataid <= 0)
　　{
　　break;// 跳出循环
　　}
　　// 创建新结点
　　pNew = (Link_Node *)malloc(sizeof(Link_Node));
　　pNew->data = dataid;
　　// 建立关联,头结点指向新结点
　　cur->next = pNew;// 此时head已经指向了新结点
　　pNew->next = NULL;
　　cur = pNew;// 指针下移
　　}
　　return head;
　　}
　　3. 遍历链表
　　// 遍历结点,传入链表
　　int Print_Link_Node(Link_Node *head)
　　{
　　if (head == NULL)
　　{
　　return -1;
　　}
　　// 保存链表(带头链表的除了头之外的链表)
　　Link_Node *cur = head->next;
　　printf(＂head --> ＂);
　　while (cur != NULL)
　　{
　　// 打印结点数据域
　　printf(＂%d --> ＂,cur->data);
　　// 指针下移操作
　　cur = cur->next;
　　}
　　printf(＂NULL  ＂);// cur指向了NULL
　　}
　　4. 在头部插入结点
　　// 头插法
　　void Init_Head_Link_Node(Link_Node *head,int dataid)
　　{
　　if (head == NULL)
　　{
　　return;
　　}
　　// 保存第一个有效结点
　　Link_Node *cur = head->next;
　　// 创建新结点
　　Link_Node *pNew = (Link_Node *)malloc(sizeof(Link_Node));
　　pNew->data = dataid;
　　// 建立关系
　　head->next = pNew;
　　pNew->next = cur;
　　}
　　5.尾部插入
　　// 尾插法
　　void Init_Tail_Link_Node(Link_Node *head,int dataid)
　　{
　　if (head == NULL)
　　{
　　return;
　　}
　　// 保存结点,获取最后一个结点
　　Link_Node *cur = head;
　　while (cur->next != NULL)
　　{
　　// 结点后移
　　cur = cur->next;
　　}
　　// 创建新结点,插入
　　Link_Node *pNew = (Link_Node *)malloc(sizeof(Link_Node));
　　pNew->data = dataid;
　　// 尾结点的next指向新结点
　　cur->next = pNew;
　　// 新结点的next指向NULL
　　pNew->next = NULL;
　　}
　　6.指定位置
　　// 找到data为num的前面插入,找不到就尾插
　　void Init_Insert_Link_Node(Link_Node *head,int num,int dataid)
　　{
　　if (head == NULL)
　　{
　　return;
　　}
　　// cur为第一个有效结点
　　Link_Node *cur = head->next;
　　Link_Node *pre = head;//保存前结点
　　while (cur != NULL)
　　{
　　if (cur->data == num)
　　{
　　break;
　　}
　　// 循环查找data
　　// 指针下移
　　pre = pre->next;
　　cur = cur->next;
　　}
　　// 1.找到匹配结点,cur为匹配结点,pre为上一个结点
　　// 2.没有找到,说明cur指向NULL,pre为cur的上一个结点
　　// pre->next = cur
　　// cur = NULL
　　// 插入新结点
　　Link_Node *pNew = (Link_Node *)malloc(sizeof(Link_Node));
　　pNew->data = dataid;
　　// 尾结点的next指向新结点
　　pre->next = pNew;
　　// 新结点的next指向NULL
　　pNew->next = cur;
　　}
　　7. 删除指定data第一个值
　　// 删除指定data第一个值
　　void Del_Link_Node(Link_Node *head,int dataid)
　　{
　　if (head == NULL)
　　{
　　return;
　　}
　　// cur为第一个有效结点
　　Link_Node *cur = head->next;
　　// pre保存cur的上个结点
　　Link_Node *pre = head;
　　// 没有找到匹配结点,1代表找到
　　int flag = 0;
　　while (cur != NULL)
　　{
　　if (cur->data == dataid)
　　{
　　// 找到匹配结点
　　flag = 1;
　　pre->next = cur->next;
　　free(cur);
　　cur = NULL;
　　break;
　　}
　　pre = pre->next;
　　cur = cur->next;
　　}
　　if (0 == flag)
　　{
　　printf(＂没有找到%d的结点 ＂,dataid);
　　}
　　}
　　8.释放链表
　　// 清空链表
　　void Destroy_Link_Node(Link_Node *head)
　　{
　　Link_Node *cur = head;
　　while (cur->next != NULL)
　　{
　　// 先保存下一个结点
　　head = head->next;
　　// 释放第一个结点
　　free(cur);
　　cur = NULL;
　　// 当前结点下移
　　cur = head;
　　}
　　printf(＂链表清空 ＂);
　　}
　　9.main函数
　　int main(int argc, char *argv[])
　　{
　　// 创建链表
　　Link_Node *headLink_Node = Init_Link_Node();
　　Print_Link_Node(headLink_Node);
　　// 头插
　　Init_Head_Link_Node(headLink_Node,1111);
　　// 尾插法
　　Init_Tail_Link_Node(headLink_Node,2222);
　　Print_Link_Node(headLink_Node);
　　// 查找4,插入
　　Init_Insert_Link_Node(headLink_Node,4,3333);
　　Print_Link_Node(headLink_Node);
　　// 删除2
　　Del_Link_Node(headLink_Node,2);
　　Print_Link_Node(headLink_Node);
　　// 清空链表
　　Destroy_Link_Node(headLink_Node);
　　printf(＂hello... ＂);
　　system(＂pause＂);
　　return 0;
　　}