基本概念和术语

数据

是客观事物的符号表示 ,所有能输入到计算机中并被计算机程序处理的符号的总称,即数字化的信息

数据元素

是数据的基本单位,在程序中通常作为一个整体来进行考虑和处理,
一个数据元素可由若干个数据项组成

数据项是数据的不可分割的‘最小单位’

数据项是对客观事物某一方面特性的数据描述

数据对象

是性质相同的数据元素的集合,是数据的一个子集.如字符集合

数据结构

形式定义为一个二元组:DS=(D,S)
D是数据元素的有限集(数据对象),S是D上关系的有限集(关系),即DS是指相互之间具有一定关系的数据元素的集合

逻辑结构

逻辑结构有4种基本类型:

集合:除了属于同一个集合外没有其他关系
线性结构:一对一
树形结构:一对多
图状结构或网状结构:数据元素之间存在多对多的关系

存储结构（物理）

数据及其逻辑结构在物理内存呢中的存储方式,成为数据的存储结构
数据在计算机内存中的存储分为顺序存储和非顺序存储

衍生出了数据结构两种不同的存储结构
1. 顺序存储结构
2. 链式存储结构

算法

定义

解决问题方法的一种描述

特性

输入：有零个或多个输出，取自于某个特定对象的集合
输出：有一个或多个输出，同输出有着某些特定关系的量
有穷性：时间有穷
确定性：明确含义
可行性：能行的

线性结构

线性表

概念

线性表是一种典型的线性结构
所有结点具有相同的数据类型
当表非空时,记作L=(a1,a2,…,ai…,an)
a1称为线性表的第一个(首)结点,an称为线性表的最后一个(尾)结点
a1,a2…..都是ai的前驱,其中ai-1是ai的直接前驱
ai+1,ai+2都是ai的后继,其中ai+1是ai的直接后继

特点

基本特点:线性表中的数据元素是有序的,且是有限的
若线性表中的结点是按值或关键字值由小到大或从大到小有序排列，则称线性表是有序的
线性表是一种相当灵活的数据结构

顺序存储

线性表是物理结构
顺序存储:把线性表的结点按逻辑顺序一次存放在一个地址连续的存储单元里用这种方式存储的线性表简称顺序表
特点
1. 线性表的逻辑顺序于物理顺序一致
2. 数据元素之间相邻

typedef struct sqlist{
  ElemType data[MAX_SIZE];//静态数组->初始化对应(2,1)
  //ElemType *data 动态数组->初始化对应(2,2)
  int len;//线性表的长度
}SqList;

链式存储

例如链表
特点:
1. 可以连续也可以不连续
2. 结点的逻辑顺序和物理顺序不一定相同
3. 设置头结点
4. 双链表是为了克服单链表的单向性的缺陷而引入的

线性表

#define MAX_SIZE 100
typedef int ElemType;
typedef struct sqlist {
	ElemType data[MAX_SIZE];
	int len;
}sqlist;

void initiate(sqlist &L)
{
	L.len = 0;
}
int length(const sqlist &L)
{
	return L.len;
}
ElemType get(const sqlist &L, int i)//去下表为i的元素
{
	if (i < 0 || i >= L.len)
	{
		return 0;
	}
	return L.data[i];
}
int locate(int L[], int e)
{

}
void insertion(sqlist &L, int i, ElemType e)
{
	if (i<0 || i>L.len||L.len>=MAX_SIZE)
	{
		return;
	}
	for (int j = L.len - 1; j >= i; --j)
	{
		L.data[j + 1] = L.data[j];
	}
	L.data[i] = e;
	L.len++;
	return;
}
ElemType deleteElm(sqlist& L, int i) {
	ElemType  x; //待删除的结点(下标=i)
	if (L.len == 0) {
		return 0;
	}
	else if (i < 0 || i >= L.len) {
		return 0;
	}
	else {
		x = L.data[i];   /*保存待删除结点的值*/
		/*(A)i之后的所有结点依次前移一位(i+1 ~ n-1) */
		for (int k = i + 1; k < L.len; k++) {
			L.data[k - 1] = L.data[k];
		}
		/*(B)线性表长度-1 */
		L.len--;
		return (x);
	}
}
bool empty(sqlist &L)
{
	if (L.len == 0)
	{
		return true;
	}
	return false;
}
void clear(sqlist &L)
{
	L.len = 0;
}

合并两个链表

这里用合并两个方程组举例

typedef struct ploy
{
    float coef;
    int expn;
    struct ploy* next;
} ploy;

ploy* createlink()
{
    ploy* h = (ploy*)malloc(sizeof(ploy));
    h->next = NULL;
    ploy* r = h;
    int n, i;
    printf("输入系数个数\n");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        ploy* p = (ploy*)malloc(sizeof(ploy));
        printf("输入系数,指数\n");
        scanf("%f,%d", &(p->coef), &(p->expn)); // 使用地址运算符&
        r->next = p;
        p->next = NULL;
        r = p;
    } // 尾插法
    return h;
}

ploy* merge(ploy* h1, ploy* h2)
{
    ploy* help = (ploy*)malloc(sizeof(ploy)) ; // 不再使用数组
    help->next = NULL;
    ploy* p1 = h1->next, * p2 = h2->next, * ptr, *r =help; // 使用指针变量
    while (p1 != NULL && p2 != NULL)
    {
        ploy* p = (ploy*)malloc(sizeof(ploy)); // 动态分配内存
        if (p1->expn == p2->expn)
        {
            p->expn = p1->expn;
            p->coef = p1->coef + p2->coef;
            p->next = NULL;
            p1 = p1->next;
            p2 = p2->next;
        }
        else if (p1->expn < p2->expn)
        {
            p->expn = p1->expn;
            p->coef = p1->coef;
            p->next = NULL;
            p1 = p1->next;
        }
        else
        {
            p->expn = p2->expn;
            p->coef = p2->coef;
            p->next = NULL;
            p2 = p2->next;
        }
        r->next = p;
        p->next = NULL;
        r = p;
    }
    while (p1 != NULL)
    {
        ploy* p = (ploy*)malloc(sizeof(ploy)); // 动态分配内存
        p->expn = p1->expn;
        p->coef = p1->coef;
        p->next = NULL;
        r->next = p;
        p->next = NULL;
        r = p;
        p1 = p1->next;
    }
    while (p2 != NULL)
    {
        ploy* p = (ploy*)malloc(sizeof(ploy)); // 动态分配内存
        p->expn = p2->expn;
        p->coef = p2->coef;
        p->next = NULL;
        r->next = p;
        p->next = NULL;
        r = p;
        p2 = p2->next;
    }
    return help;
}

void printlink(ploy* h)
{
    h = h->next;
    printf("合并后\n");
    while (h != NULL)
    {
        printf("%.1fx^%d", h->coef, h->expn);
        if (h->next != NULL)
        {
            printf("+");
        }
        h = h->next;
    }
}

int main()
{
    printf("输入第一个链表\n");
    ploy* h1 = createlink();
    printf("输入第二个链表\n");
    ploy* h2 = createlink();
    ploy* he = merge(h1, h2);
    printlink(he);
    return 0;
}

两个方程组相乘

思路是建立一个链表来储存一个链表第一个数去×另一个的所有

再建立一个空链表

最后将两个链表相加,不断往后得到答案

ploy* mul(ploy* h1, ploy* h2)
{
    ploy* help = (ploy*)malloc(sizeof(ploy));
    help->next = NULL;
    ploy* res = (ploy*)malloc(sizeof(ploy));
    res->next = NULL;;
    ploy* t = h2->next;
    while (t != NULL)
    {
        ploy* r = help; 
        ploy* s = h1->next; 
        while (s != NULL)
        {
            ploy* p = (ploy*)malloc(sizeof(ploy));
            p->coef = s->coef * t->coef;
            p->expn = s->expn + t->expn;
            r->next = p;
            p->next = NULL;
            r = p;
            s = s->next;
        }
        res = merge(res, help); // 将当前计算得到的结果链表和之前的结果链表合并
        t = t->next;
    }
    return res;
}

树

1	有几个孩子就有几个度,度为0的点为叶子结点

除了根节点之外都是内部结点
结点没有高度,只有树有高度,所以一个结点的高度就是把这个节点当作根节点的树的高度
森林

1	把一颗树的根结点删除,余下的树就构成了森林

基本概念和术语

数据

数据元素

数据对象

数据结构

逻辑结构

存储结构（物理）

算法

定义

特性

线性结构

线性表

概念

特点

顺序存储

链式存储

线性表

合并两个链表

树

二叉树