数据结构类型
数据结构：线性结构，树形结构，图形结构
线性结构：在存储关系上，每个元素最多有一个前驱，一个后继
树形结构：在存储关系上，每个元素最多有一个前驱，但可以有多个后继
图形结构：在存储关系上，每个元素可以有多个前驱，多个后继
类型重定义 (typedef ）
类型重定义 (typedef type define)
1 普通类型重定义 :把一些类型 替换成你想的名字
typedef int size_t; //typedef 能将int 重定义成size_t
size_t a; //int a
typedef unsigned char UINT8; //UINT8 a; //定义了一个 无符号8位的整型
typedef char INT8;
typedef unsigned short UINT16;
typedef short INT16;
typedef unsigned int UINT32;
typedef int INT32;
结构体类型重定义
学生结构体类型重定义
struct student
{
char name[20];
int age;
};
struct student s1;
方法1:
typedef struct student stu_t;
stu_t s1; //可以省略struct
方法2:
typedef struct student
{
char name[20];
int age;
}stu_t;
方法3: 省略结构体名
typedef struct
{
char name[20];
int age;
}stu_t;
例:
#include <stdio.h>
typedef struct
{
char name[20];
int age;
}stu_t;
int main()
{
stu_t s1 = {"xiaoli", 25};
printf("%s,%d\n", s1.name, s1.age);
}
链表
用来解决1 顺序表数据大量移动的问题
2 解决顺序表元素数量固定的问题
链表分为单向链表，双向链表，单向循环链表，双向循环链表
单向链表有两个域，数据域和指针域
1.带头结点
单向链表 两种类型
1 带头结点 (头结点: 是一个空节点，这个节点不存有效数据，只有next是有效的)
上面名字例子改为用带头结点的单向链表实现：
#include <stdio.h>
typedef struct node_t
{
char name[20];
struct node_t *next;
}link_node_t;
int main()
{
link_node_t A = {"yang", NULL};
link_node_t B = {"li", NULL};
link_node_t C = {"liu", NULL};
link_node_t D = {"wang", NULL};
link_node_t E = {" ", &A};
A.next = &B;
B.next = &C;
C.next = &D;
link_node_t *p = &E;
//输出?????
while(p->next != NULL)
{
p = p->next;
printf("%s\n", p->name);
}
}
用带头结点
用带头结点的单向链表存储n个学生成绩 ，成绩由键盘输入，输入<=0 时结束
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t
{
int data;
struct node_t *next;
}link_node_t;
int main()
{
link_node_t *h = malloc(sizeof(link_node_t));//h 是头节点
h->next = NULL;
link_node_t *q = h; //q 永远指向最后一个节点
while(1)
{
int n;
scanf("%d", &n);
if(n <= 0)
break;
link_node_t *p = malloc(sizeof(link_node_t));//p 是新节点
p->data = n;
p->next = NULL;
q->next = p;
q = p;
}
while(h->next != NULL)
{
h = h->next;
printf("%d\n", h->data);
}
}
实例解析
int main()
{
link_node_t *h = CreateEmptyLinklist();
InsertLinklist(h, 1, 40); //40
InsertLinklist(h, 1, 30); //30, 40
InsertLinklist(h, 1, 10); //10, 30, 40
InsertLinklist(h, 2, 20); //10, 20, 30, 40
print_all(h); //打印所有元素
ReverseLinklist(h);
print_all(h); //打印所有元素 //40, 30, 20, 10
DeleteLinklist(h, 2);
print_all(h); //打印所有元素 //10, 30, 40
reverse_print_all(h); //40, 30, 10
free_list(h); //释放所有元素(每释放一个，打印1)
}
typedef struct node_t
{
int data;
struct node_t *next;
}link_node_t;
link_node_t *CreateEmptyLinklist()
{ //malloc 一个头节点， 头节点的next = NULL ， 然后返回
link_node_t *p = malloc(sizeof(link_node_t));
p->next = NULL;
return p;
}
//1 求链表长度
int LengthLinklist(link_node_t *p)
{
int len = 0;
while(p->next != NULL)
{
len++;
p = p->next;
}
return len;
}
int getValue(link_node_t *p, int pos)
{
int i;
for(i = 0; i < pos; i++)
p = p->next;
return p->data;
}
//3 插入元素 (成功: 返回0 失败返回 -1)
int InsertLinklist(link_node_t *p, int pos, int x)
{
int i;
//容错处理, 如果pos 错，不能插入
if(pos > LengthLinklist(p) + 1)
return -1;
for(i = 0; i < pos - 1; i++)
p = p->next;
link_node_t *q = malloc(sizeof(link_node_t));
q->data = x;
q->next = p->next;
p->next = q;
return 0;
}
int DeleteLinklist(link_node_t *p, int pos)
{
int i;
if(pos > LengthLinklist(p))
return -1;
for(i = 0; i < pos - 1; i++)
p = p->next;
link_node_t *q = p->next;
p->next = q->next;
free(q);
return 0;
}
void print_all(link_node_t *p)
{
while(p->next != NULL)
{
p = p->next ;
printf("%d,", p->data);
}
printf("\n");
}
void reverse_print_all(link_node_t *p)
{
if(p->next == NULL)
return;
reverse_print_all(p->next);
printf("%d,", p->next->data);
}
- //链表逆转 (原来的最后一个节点，变成第一个节点)
void ReverseLinklist(link_node_t *h)
{
link_node_t *p, *q;
p = h->next;
h->next = NULL;
while (p != NULL)
{
q = p;
p = p->next;
q->next = h->next;
h->next = q;
}
return;
}
void free_list(link_node_t *p)
{
while(p != NULL)
{
link_node_t *q = p->next; //保存下一个节点
free(p);
printf("1\n");
p = q;
}
}
双向链表
两个指针域: 1) 指向前一个节点 (prev) 2) 指向后一个节点 ( next )
双向链表，可以向后走，也可以向前走， 速度更快
结构体定义
typedef struct node_t
{
int data;
struct node_t *prev;
struct node_t *next;
}link_node_t;
双向链表的插入和删除操作
int InsertLinklist(link_node_t *p, int pos, int x)
{ //1 找pos 前一个节点
for(i = 0; i < pos – 1; i++)
p = p->next;
link_node_t *q = malloc(sizeof(link_node_t));
q->data = x;
q->next = p->next; //(1)
p->next->prev = q; //(2)
p->next = q; //(3)
q->prev = p; //(4)
//注: 3 不能在1前面
}
栈
栈是只能在一端进行插入和删除操作的线性表(又称为堆栈)
栈的操作规则(后进先出LIFO last in first out) (或者FILO first in last out)
栈的典型应用(函数的执行过程)
栈: 栈顶(top)栈顶 进行插入和删除操
实例解析
int main()
{
stack_t *p = CreateEmptyStack(5);
pushStack(p, 10);
pushStack(p, 20);
pushStack(p, 30);
pushStack(p, 40);
pushStack(p, 50);
pushStack(p, 60); //栈已经满，失败
printf("%d\n", popStack(p)); //50
printf("%d\n", popStack(p)); //40
printf("%d\n", popStack(p)); //30
printf("%d\n", popStack(p)); //20
printf("%d\n", popStack(p)); //10
printf("%d\n", popStack(p)); //栈已经空，失败
}
typedef struct
{
int *data; //
int maxlen; //栈中最多存储的元素个数
int top; //栈顶
}stack_t
stack_t *CreateEmptyStack(int len)
{ //1) 动态分配内存 2) top = 0 3) maxlen = len(不是必须的)
stack_t *p = malloc(sizeof(stack_t));
p->data = malloc(len * sizeof(int));
p->maxlen = len;
p->top = 0;
return p;
}
int EmptyStack(stack_t *p)
{
if(p->top == 0)
return 1;
else
return 0;
}
int FullStack(stack_t *p)
{
if(p->top == p->maxlen) //return p->top == p->maxlen;
return 1;
else
return 0;
}
int pushStack(stack_t *p, int x)
{ //1) 判断是否满， 2) 存入数 3) top++
if(FullStack(p) == 1) //if(FullStack(p))
{
printf("stack full\n");
return -1;
}
p->data[p->top] = x;
p->top++;
return 0;
}
int popStack(stack_t *p)
{ //1) 判断是否空 2) top-- 3) 返回值
if(EmptyStack(p))
{
printf("stack empty\n");
return -1;
}
p->top--;
return p->data[p->top];
}
void clearStack(stack_t *p)
{
p->top = 0;
}
队列
队列(FIFO)first in first out
允许在两端进行插入和删除操作的线性表(队列)
有两个指针(1 取数据端 2 存数据端)
取出端称为 front
存入端称为 rear
实例解析
int main()
{
queue_t *p = CreateEmptyQueue();
InQueue(p, 10);
InQueue(p, 20);
InQueue(p, 30);
InQueue(p, 40);
InQueue(p, 50);
InQueue(p, 60); //满，存入失败
printf("%d\n", OutQueue(p)); //10
printf("%d\n", OutQueue(p)); //20
printf("%d\n", OutQueue(p)); //30
printf("%d\n", OutQueue(p)); //40
printf("%d\n", OutQueue(p)); //50
printf("%d\n", OutQueue(p)); //空，-1
}
typedef struct
{
int data[6];
int rear;
int front;
}queue_t;
queue_t *CreateEmptyQueue()
{
queue_t *p = malloc(sizeof(queue_t));
p->rear = p->front = 0;
return p;
}
int EmptyQueue(queue_t *p)
{
return p->rear == p->front;
}
int FullQueue(queue_t *p)
{
return (p->rear + 1) % 6 == p->front;
}
int InQueue(queue_t *p, int x)
{
if(FullQueue(p))
{
printf("queue full\n");
return -1;
}
p->data[p->rear] = x;
p->rear++;
p->rear = p->rear % 6;
return 0;
}
int OutQueue(queue_t *p)
{
if(EmptyQueue(p))
{
printf("queue empty\n");
return -1;
}
int x = p->data[p->front];
p->front++;
p->front = p->front % 6;
return x;
}
二分查找
每次找中间的数 和 x 进行比较，如果x比中间的数大，那么再在右面找中间的
如果x比中间的数小，那么再在左面找中间的
10, 15, 18, 20, 25, 30, 31, 38, 40 , 45 (下标 0 - 9)
找38：
1) l = 0, h = 9, m = (l + h) / 2 = 4 38 > a[4] 继续在右面找
2) l = m + 1 = 5, h = 9, m = (l + h) / 2 = 7 38 = a[7] 找到了，结束
找10：
1) l = 0, h = 9, m = (l + h) / 2 = 4 10 < a[4] 继续在左面找
2) l = 0, h = m - 1 = 3, m = (l + h) / 2 = 1 10 < a[1] 继续在左面找
3) l = 0, h = m - 1 = 0, m = (l + h) / 2 = 0 10 = a[0] 找到了，结束
找11：
1) l = 0, h = 9, m = (l + h) / 2 = 4 11 < a[4] 继续在左面找
2) l = 0, h = m - 1 = 3, m = (l + h) / 2 = 1 11 < a[1] 继续在左面找
3) l = 0, h = m - 1 = 0, m = (l + h) / 2 = 0 11 > a[0] 继续在右面找
4) l = m + 1 = 1, h = 0 此时 l > h 循环结束
实例解析
int main()
{
int a[10] = {10, 15, 18, 20, 25, 30, 31, 38, 40 , 45};
int n;
scanf("%d", &n); //(38 7) (10 0) (11 not find)
int x = find_by_half(a, 10, n);
if(x >= 0)
printf("find it at %d\n", x);
else
printf("not find\n");
}
int find_by_half(int *p, int n, int x)
{
int l = 0, h = n - 1, m;
while(l <= h)
{
m = (l + h) / 2;
if(x > p[m])
{
l = m + 1;
}
else if(x < p[m])
{
h = m - 1;
}
else if(x == p[m])
{
return m;
}
}
return -1;
}
分块查找
数据有如下特点：块间有序，块内无序
实例
#include <stdio.h>
//结构体定义
typedef struct
{
int max;
int pos;
}index_t;
//查找函数
int find_by_block(int *p, index_t *q, int x) //q 索引表
{
int i;
int start = 0, end = 0;
for(i = 0; i < 4; i++)
{
if(x <= q[i].max)
{ //找到了在哪块
start = q[i].pos;
if(i == 3)
end = 18;
else
end = q[i + 1].pos - 1;
break;
}
}
for(i = start; i <= end; i++)
{
if(p[i] == x)
return i;
}
return -1;
}
//主函数
int main()
{ //1 构建原始数据表
int a[19] = {18, 10, 9, 8, 16, 20, 38, 42, 19, 50, 84, 72, 56, 55, 76, 100, 90, 88, 108};
//2 构建索引表， 用结构体数组
index_t b[4] = {{18, 0}, {50, 5}, {84, 10}, {108, 15}};
int n;
scanf("%d", &n);
int x = find_by_block(a, b, n);
if(x >= 0)
printf("find it at %d\n", x);
else
printf("not find\n");
}
哈希hash查找
哈希表又叫散列表(hash)
有一张表，表里面存的数据的某个关键字和位置有一个对应关系(关键字通过一个计算公式，能求出位置)
那么我们就可以快速找到某条记录
哈希查找有3个概念
1 关键字 (key)
2 计算公司(哈希函数 又称为 散列函数)
3 存储数据的表 (哈希表 又称为 散列表)
个人理解，：哈希表就是如果有10个数 我就拿20个的内存放这十个数，（空间换时间吗），在根据类似加密把数据通过方法转换成我们想要存的位置。
叠加法练习
本例子采用对1000取余在相加在取余的方法
int main()
{
int a[] = {704005265, 103004265, 999000001, 54353524, 435645657, 321312};
int i, n, b[1000] = { 0 }; //哈希表
for(i = 0; i < 6; i++)
{
save_by_add(b, a[i]); //将6个ISBN编号存入到哈希表中
}
scanf("%d", &n); //输入一个ISBN编号，查找是否在哈希表中
int x = find_by_hash(b, n);
if(x >= 0)
printf("find it at %d\n", x);
else
printf("not find\n");
}
void save_by_add(int *p, int x)
{
int pos = hash_fun(x);
if(p[pos] == 0)
p[pos] = x;
}
int find_by_hash(int *p, int x) //返回值: -1 没找到 >=0 位置
{
int pos = hash_fun(x);
if(p[pos] != x)
return -1;
else
return pos;
}
int hash_fun(int x)
{
return (x / 1000000 + x % 1000000 / 1000 + x % 1000) % 1000;
}
linux系统下一些根目录下的文件
/bin ? binary 保存的是二进制可执行命令 (ls mkdir mv ....)
/home ? 当新建一个用户时，在此目录 新建一个目录(用户工作目录)
/etc ? 保存配置文件(用户passwd 密码 shadow ip地址 ....)
/boot ? 保存linux启动相关文件
/dev ? device 保存设备相关文件(串口 ttyS0)
/lib ? library 保存系统库文件 (标准c库libc.so)
/sbin ? 管理员用户单独使用的命令
/mnt ? 当挂载 u盘... 一些硬件设备时，这些设备被挂载到此目录(mount)
树
树形结构：树中每个节点(除了根节点)，都有一个前驱节点，一个或多个后继节点，
根 (最顶层的节点，它没有前驱，有多个后继)
叶子节点(最底层的节点，没有后继，只有一个前驱)
资源管理器、菜单
节点的度数: 一个节点的子节点的个数
二叉树(Binary Tree) (B Tree)
满二叉树 ：深度为k（k≥1）时有2k－1个节点的二叉树
完全二叉树 ：只有最下面两层有度数小于2的节点，
且最下面一层的叶节点集中在最左边的若干位置上。
二叉树的遍历
遍历 ：沿某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次
先序遍历(前序遍历) 根 --> 左 -->右
中序遍历 左 --> 根 -->右
后序遍历 左 -->右 --> 根
实例解析
int main() //构建二叉树
{
tree_t A = {'A', NULL, NULL};
tree_t B = {'B', NULL, NULL};
tree_t C = {'C', NULL, NULL};
tree_t D = {'D', NULL, NULL};
tree_t E = {'E', NULL, NULL};
tree_t F = {'F', NULL, NULL};
A.lchild = &B;
A.rchild = &C;
B.lchild = &D;
B.rchild = &E;
C.lchild = &F;
printf("%d\n", getBTreeHeight(&A));
}
typedef struct node_t
{
int data;
struct node_t *lchild;
struct node_t *rchild;
}tree_t
int getBTreeHeight(tree_t* root){
if(root == NULL)
return 0;
int left = getBTreeHeight(root->lchild);
int right = getBTreeHeight(root->rchild);
return 1 + (left > right ? left: right);
}
最好用递归输出
void first_order(tree_t *r)
{
if(r == NULL)
return;
printf("%d\n", r->data);
first_order(r->lchild);
first_order(r->rchild);
}
快速排序
每次从前面拿出第一个数，开始排序，经过1轮 左面都比其小，右面的都比其大
实例解析
int main()
{
int i;
int a[] = {50,36,66,76,36,12,25,95, 78, 13, 89, 100};
quick_sort(a, 0, 11);
for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
printf("%d,", a[i]);
}
}
void quick_sort(int *x, int low, int high)
{
int i, j, t;
if (low < high) /*要排序的元素起止下标，保证小的放在左边，大的放在右边。这里以下标为low 的元素为基准点*/
{
i = low;
j = high;
t = x[low]; /*暂存基准点的数*/ //x[low]
while (i<j) /*循环扫描*/
{
while (i<j && x[j]>t) /*在右边的只要比基准点大仍放在右边*/
{
j--; /*前移一个位置*/
}
if(i<j)
{
x[i] = x[j]; /*上面的循环退出：即出现比基准点小的数，替换基准点的数*/
i++; /*后移一个位置，并以此为基准点*/
}
while (i<j && x[i]<=t) /*在左边的只要小于等于基准点仍放在左边*/
{
i++; /*后移一个位置*/
}
if (i<j)
{
x[j] = x[i]; /*上面的循环退出：即出现比基准点大的数，放到右边*/
j--; /*前移一个位置*/
}
}
x[i] = t; /*一遍扫描完后，放到适当位置*/
quick_sort(x,low,i-1); /*对基准点左边的数再执行快速排序*/
quick_sort(x,i+1,high); /*对基准点右边的数再执行快速排序*/
}
}
本周总结结束，感谢阅读！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
