computer
数据结构
第一章
算法
- 一个有限指令集
- 接受一些输入
- 产生输出
- 一定要在有限的步骤之后终止
- 每一条指令必须有明确色目标,不可以有歧义,计算机能处理的范围之内,不依赖任何语言和描述。
什么是好算法
- 时间复杂度
- 空间复杂度
复杂度的渐进表示法
输入规模 n
每十亿
`
最大子列和的问题
算法一
int MaxSubeqSum1(int A[],int N)
{
int ThisSum ,MaxSum = 0;
int i,j,k;
for (i =0;i<N;i++){
for(j=i;j<N;j++){
ThisSum = 0;
for(k=0 ;k<=j;j++)
ThisSum += A[k];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
算法二 分而治之
在线处理
int MaxSubseqSum4(int A[],int N){
int ThisSum,MaxSum;
int i;
ThisSum = MaxSum =0;
for(int i = 0;i<N;i++){
ThisSum +=A[i];
if(ThisSum>MaxSum){
MaxSum = ThisSum;
}else if(ThisSum<0)
ThisSum = 0;
}
return MaxSum;
}
线性表
如何表示多项式
- 多项式的各项系数n
- 各项系数以及指数
方法一 顺序存储结直接表示
方法二 顺序存储结构表示非零项
- 用结构数组来表示
- 链表结构存储非零项
什么是线性表(数组)
主要操作的实现
List MakeEmpty(){
List PtrL;
PtriL = (List )alloc (sizeof(struct Lnode));
PtrL-> = -1;
return PtrL;
}
int Find(ElementType X,List PtrL){
int i =0;
while(i<=PtrL->Last&&PtrL->data[i]!=X){
i++;
}
if(i>PtrL->Last)return -1;
else return i;
}
- 插入
链式存储结构(链表)
循环单列表代码
#include<stdlib.h>
typedef struct list{
int data;
struct list *next;
}list;
//data为存储的数据,next指针为指向下一个结点
//初始结点
list *initlist(){
list *head=(list*)malloc(sizeof(list));
if(head==NULL){
printf("创建失败,退出程序");
exit(0);
}else{
head->next=NULL;
return head;
}
}
//创建--插入数据
int create_list(list *head){
int data; //插入的数据类型
printf("请输入要插入的元素:");
scanf("%d",&data);
list *node=initlist();
node->data=data;
//初始化一个新的结点,准备进行链接
if(head!=NULL){
list *p=head;
//找到最后一个数据
while(p->next!=head){
p=p->next;
}
p->next=node;
node->next=head;
return 1;
}else{
printf("头结点已无元素\n");
return 0;
}
}
//插入元素
list *insert_list(list *head,int pos,int data){
//三个参数分别是链表,位置,参数
list *node=initlist(); //新建结点
list *p=head; //p表示新的链表
list *t;
t=p;
node->data=data;
if(head!=NULL){
for(int i=1;i<=pos;i++){
t=t->next;
}
node->next=t->next;
t->next=node;
return p;
}
return p;
}
//删除元素
int delete_list(list *head) {
if(head == NULL) {
printf("链表为空!\n");
return 0;
}
//建立零时结点存储头结点信息(目的为了找到退出点)
//如果不这么建立的化需要使用一个数据进行计数标记,计数达到链表长度时自动退出
//循环链表当找到最后一个元素的时候会自动指向头元素,这是我们不想让他发生的
list *temp = head;
list *ptr = head->next;
int del;
printf("请输入你要删除的元素:");
scanf("%d",&del);
while(ptr != head) {
if(ptr->data == del) {
if(ptr->next == head) { //循环结束的条件换成ptr->next == head
temp->next = head;
free(ptr);
return 1;
}
temp->next = ptr->next;
free(ptr);
//printf("元素删除成功!\n");
return 1;
}
temp = temp->next;
ptr = ptr->next;
}
printf("没有找到要删除的元素\n");
return 0;
}
//遍历元素
int display(list *head) {
if(head != NULL) {
list *p = head;
//遍历头节点到,最后一个数据
while(p->next != head ) {
printf("%d ",p->next->data);
p = p->next;
}
printf("\n"); //习惯性换行 ( o=^•ェ•)o ┏━┓
//把最后一个节点赋新的节点过去
return 1;
} else {
printf("头结点为空!\n");
return 0;
}
}
int main(){
//////////初始化头结点//////////////
list *head=initlist();
head->next=head;
////////通过插入元素完善链表/////////
for(int i=0;i<5;i++){ //只是演示使用,不具体提供输入
create_list(head);
}
display(head);
////////////插入元素////////////////
head=insert_list(head,1,10);
display(head);
////////////删除元素////////////////
delete_list(head);
display(head);
return 0;
}
广义表
- 广义表是线性表的推广
- 对于线性表而言,n个元素都是基本的单元素
- 广义表中,这些元素不仅可以是单元素也可以是另外一个广义表
多重链表
多重链表:链表中的节点可能同时隶属于多个链
- 多重链表中的节点的指针域会有多个
- 但包含两个指针域的链表并不一定是多重链表,比如再双向链表不是多重链表
几个典型的多重链表: - 十字链表
只存储矩阵的非零项,每个节点通过两个指针,把行和列串连起来
堆栈
后缀表达式
中缀表达式:运算符号在两个运算数之间
后缀表达式:运算符号在两个运算数之后
堆栈的数据描述
栈是一种先进后出的数据结构,栈是一个线性的数据结构,规定这个数据结构只允许在其中一端进行操作,并禁止直接访问除这一端以外的数据
栈分为数组栈和链表栈,其区别是数组栈使用数组进行功能的模拟,实现较为快速和便利,而链表栈使用链表的思路去设计,实现较为麻烦,但是其稳定不易出错;在链表栈中又分为静态链表栈和动态链表栈,静态链表栈给定栈的空间大小,不允许超过存储超过给定数据大小的元素,而动态栈使用的是自动创建空间的方法进行创建,只要符合机器的硬件要求以及编译器的控制,其理论上是极大的。
堆栈(stack):具有一定约束的线性表,只在一端做(栈顶)做插入,删除
- 插入元素:入栈 (Push)
- 删除元素:出栈(pop)
- 后入显出
4.
栈的顺序存储实现
栈的定义
#define MaxSise;
typedef struct Snode*Stack;
struct SNode{
ElementType Data[MaxSise];
int top;
}
入栈
void Push (Stack PtrlS,ElementType item){
if(PtrlS->Top == MaxSize-1){
printf("堆栈满了");
return;
}else{
PtrlS->Data[++(PtrlS->Top)] = item;
renturn;
}
}
出栈
if(PtrS-> == -1){
printf("堆栈空");
}else
return (PtrS->Data[(PtrS->top)--]);
}
例子:请用一个数组实现两个堆栈,要求最大地利用数组空间,使数组只要有空间入栈操作就可以成功。
分析:一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长;当两个栈的栈顶指针相遇时,表示这两个栈都满了
#define MaxSize
struct DStack{
ElementType Data[MaxSize];
int top1;
int top2;
}S;
s.top1 = -1;
s.top2 = MaxSize;
void Push (struct DStack *PtrS,ElementType item,int tag){
if(PtrS->top2-PtrS->Top1 == 1){
prtinf("堆栈满");
return;
}
if(Tag == 1)
PtrS->Data[++(PtrS->Top1)] = item;
else
PtrS->Data[--(PtrS->Top2)] = item;
ElementType Pop(struct DStack *PtrS,int Tag){
if(Tag == 1){
if(PtrS ->Top1 == -1){
printf("堆栈空");
return NULL;
}esle
return PtrS->Data[(PtrS->Top1)--];
}
}esle{
if(PtrS->Top2 == MaxSize){
printf("堆栈2空");
return NULL;
}else
return PtrS->Data[(PtrS ->Top2)++];
}
}
堆栈的链式存储实现
栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行。
typedef struct SNode*Stack;
sturct SNode{
ElementType Data;
struct SNode *Next;
};
Stack CreatStack(){
Stack S;
S = (Stack)malloc(sizeof(Struct SNode));
S ->Next =NULL;
return S;
}
int IsEmpty(Stack S){
return (S->Next == NULL);
}
编解码的问题
堆栈应用,表达式求值
队列
什么是队列
队列:具有一定操作约束的线性表
1. 插入和删除操作 :只能在一端插入,而在另一端删除
数据插入 : 入队列
数据删除 : 出队列
先来后服务
先进先出
队列的顺序存储实现
队列的顺序存储结构通常是由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成
为什么会出现空满不分的情况?
解决方案:
- 使用额外标记:size 或者tag
- 仅使用n-个数组空间
队列的操作
队列的链式存储实现
栈的代码实现
#include <stdio.h>
#include <stdlib.h>
//栈的结点设计
//单个结点设计,数据和下一个指针
typedef struct node
{
int data;
struct node *next;
} Node;
//利用上面的结点创建栈,分为指向头结点的top指针和计数用的count
typedef struct stack
{
Node *top;
int count;
} Link_Stack;
//创建栈
Link_Stack *Creat_stack()
{
Link_Stack *p;
//p = new Link_Stack;
p=(Link_Stack*)malloc(sizeof(Link_Stack));
if(p==NULL){
printf("创建失败,即将退出程序");
exit(0);
}
p->count = 0;
p->top = NULL;
return p;
}
//入栈 push
Link_Stack *Push_stack(Link_Stack *p, int elem)
{
if (p == NULL)
return NULL;
Node *temp;
temp=(Node*)malloc(sizeof(Node));
//temp = new Node;
temp->data = elem;
temp->next = p->top;
p->top = temp;
p->count++;
return p;
}
//出栈 pop
Link_Stack *Pop_stack(Link_Stack *p)
{
Node *temp;
temp = p->top;
if (p->top == NULL)
{
printf("错误:栈为空");
return p;
}
else
{
p->top = p->top->next;
free(temp);
//delete temp;
p->count--;
return p;
}
}
//遍历栈:输出栈中所有元素
int show_stack(Link_Stack *p)
{
Node *temp;
temp = p->top;
if (p->top == NULL)
{
printf("");
printf("错误:栈为空");
return 0;
}
while (temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
return 0;
}
int main()
{ //用主函数测试一下功能
Link_Stack *p;
p = Creat_stack();
int n = 5;
int input[6] = {10,20,30,40,50,60};
/////////////以依次入栈的方式创建整个栈//////////////
for(int i=0;i<n;i++){
Push_stack(p, input[i]);
}
show_stack(p);
////////////////////出栈///////////////////////
Pop_stack(p);
show_stack(p);
return 0;
}
树
什么是树
树是数据结构中的一种,其属于非线性数据结构结构的一种,我们前文所提到的数据结构多数都是线性的,这也是较为简单的数据结构,而接下来的树与图均属于非线性数据结构,也是概念极多的一类。
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点,还(很可能)有多个附加结点,所有结点构成一个多级分层结构。
树的定义:n个节点组成的有限集合。n=0,空树;n>0,1个根节点,m个互不相交的有限集,每个子集为根的子树
树的基本术语
- 节点的度:树中某个节点的子树的个数。
- 树的度:树中各节点的度的最大值。
- 分支节点:度不为零的节点。
- 叶子节点:度为零的节点
- 路径:i->j;路径长度:路径经过节点数目减1。
- 孩子节点:某节点的后继节点;双亲节点:该节点为其孩子节点的双亲节点(父母节点);兄弟节点:同一双亲的孩子节点;子孙节点:某节点所有子树中的节点;祖先节点:从树节点到该节点的路径上的节点。
- 节点的层次:根节点为第一层(以此类推);树的高度:树中节点的最大层次。
- 有序树:树中节点子树按次序从左向右安排,次序不能改变;无序树:与之相反
- 森林:互不相交的树的集合。
二叉树简介
二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成
二叉树的特点
- 每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。
- 左子树和右子树是有顺序的,次序不能任意颠倒
- 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。
二叉树的性质
- 二叉树第i层上的结点数目最多为 2的(i-1)次方个节点(i≥1)
- 深度为k的二叉树至多有2的k次方-1个结点(k≥1)
- 包含n个结点的二叉树的高度至少为log2 (n+1)。
- 在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1。
几种特殊的二叉树
斜树
斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树
满二叉树
满二叉树:在一棵二叉树中。如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。
满二叉树的特点有:
- 叶子只能出现在最下一层。出现在其它层就不可能达成平衡
- 非叶子结点的度一定是2
- 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。
完全二叉树
完全二叉树:对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。
#include <cstdlib>
#include <stdio.h>
#include <iostream>
using namespace std;
//树的结点
typedef struct node{
int data;
struct node* left;
struct node* right;
} Node;
//树根
typedef struct {
Node* root;
} Tree;
//创建树--插入数据
void insert(Tree* tree, int value){
//创建一个节点,让左右指针全部指向空,数据为value
Node* node=(Node*)malloc(sizeof(Node));
node->data = value;
node->left = NULL;
node->right = NULL;
//判断树是不是空树,如果是,直接让树根指向这一个结点即可
if (tree->root == NULL){
tree->root = node;
} else {//不是空树
Node* temp = tree->root;//从树根开始
while (temp != NULL){
if (value < temp->data){ //小于就进左儿子
if (temp->left == NULL){
temp->left = node;
return;
} else {//继续往下搜寻
temp = temp->left;
}
} else { //否则进右儿子
if (temp->right == NULL){
temp->right = node;
return;
}
else {//继续往下搜寻
temp = temp->right;
}
}
}
}
return;
}
//树的中序遍历 In-order traversal
void inorder(Node* node){
if (node != NULL)
{
inorder(node->left);
printf("%d ",node->data);
inorder(node->right);
}
}
int main(){
Tree tree;
tree.root = NULL;//创建一个空树
int n;
scanf("%d",&n);
//输入n个数并创建这个树
for (int i = 0; i < n; i++){
int temp;
scanf("%d",&temp);
insert(&tree, temp);
}
inorder(tree.root);//中序遍历
return 0;
}
树的遍历之中序遍历二叉树
- 简介
先序遍历:根左右
中序遍历:左根右
后序遍历:左右根
在上文我们接触到了先序遍历,本文我们开始学习中序遍历,中序遍历采用左根右的遍历方式,如图,就一个最简单的二叉树遍历而言,中序遍历的遍历访问过程是先B再A再C。
实际上的二叉树并没有这么简单,其应该是由多个结点构成的,如图所示,进行第一次访问的时候,我们在ABC中进行遍历,由左根右的顺序,我们遍历访问到B,这时候先别急,B同时又作为BDG的根结点,因此需要继续向下进行遍历,此时我们遍历到DEF,这时E属于这一组之中的左结点,因此我们根据根左右的先后顺序得到了最先的遍历效果,EDF,这EDF同时作为BDG中的左节点(把EDF看作一个整体)进行回溯,此时的访问的结点顺序为EDFBG同理, EDFBG作为ABC的左结点根据左根右的顺序EDFBGAC,左半部分访问完毕接着访问右半部分,我们将CH(表示空)看作一组左中右,而C就是由EDFBGAC组合而成,因此最终的遍历顺序为:EDFBGACH
2. 代码实现
if(node != NULL){
inorder(node->left);
printf("%d",node->data);
inorder(node->right);
}
}
树的遍历之后序遍历二叉树
- 后序遍历就是在访问二叉树的结点的时候采用,先左,再右,再根的方式,对于一个最简单的访问而言如图,先访问左节点B,之后访问右结点C,最后访问根节点A,后序遍历的访问顺序就是BCA
然而实际上的遍历访问并没有那么简单,往往是多个结点相互嵌套构成的二叉树,如图所示,在访问遍历一开始的时候,先访问左节点B再访问右结点C最后访问A,但由于B结点其中也包含了新的结点,就犹如之前介绍的那样,在面对处理的结点后还存在有与之相联的结点的时候,需要优先处理其的子结点,这也是“递归”的基本思路,因此,由于B属于DG的根结点,我们相较于B,应该先访问D结点,而又由于D结点属于EF的根结点,我们就又变成先访问E结点,E属于最末端了,根据后序遍历左右根的访问顺序,依次生成EFDGB作为一个整体,接着我们需要访问C,由于C又是^HC之中的根结点,我们先访问这个空结点,又因为其是一个空的结点,我们会跳过,就变成了HC的访问顺序,那么最后在汇总的时候EFDGB作为左节点,HC作为右结点,A作为根结点,完成我们最终的遍历顺序EFDGBHCA。
- 代码实现
if(node!= NULL){
inorder(node -> left);
inorder(node ->right);
printf("%d",node->data);
}
}
标签:node,结点,return,temp,int,学习,数据结构,节点
From: https://www.cnblogs.com/haholp-blog/p/18532533