第一章——概述
表结构：用来表示结点之间某种先后次序关系(属于线性关系),一个结点只有一个前驱和一个后继,但首结点没有前驱,尾结点没有后继。“一对一”关系树结构：用来表示结点之间的层次关系、分支关系和嵌套关系,一个结点只有一个前驱(根结点没有前驱),但可以有多个后继。“一对多”关系
图结构:用来表示任何两个结点之间都可能有(或没有)关系。“多对多”关系
散结构：用来表示任何两个结点之间都没有关系,或者说存在一种特殊的关系——无关关系。
从数学角度来讲,树结构和散结构都是图的特例,表结构又是树的特例。
算法定义三要素：有穷性、确定性、可行性。
算法正确性的含义：应当对所有输入数据都能给出正确的结果。
在算法理论中,当T(n)≤0(n^d)( d是任意一个正的常数)时,就称“算法是多项式界的”,都属于“有效算法”。这里说的“有效”是指算法能在“有限时间内”完成;而若T(n)超过多项式，,就属于无效算法。
算法的运行效率主要指时间复杂性和空间复杂性。若一个算法的时间耗用函数T( n)满足T(n)≤cf(n)，则记作T(n)= O(f(n))。有效算法和无效算法的分界线是T(n)是否在多项式范围内。就算法时间复杂性而言,最坏情况指的是T(n)=O(n²);平均情况指的是S(n)=O(n)。
第二章——表结构
①简单链表
当表为空时：head==NULL
在表头插入p所指结点：p->next=head;head=p;
在中间插入p所指结点：p->next=q->next;q->next=p;
②加头链表
当表为空时：head->next==NULL;
//加头链表在表头或表中插入是一样的
在表中插入p所指结点：p->next=head->next; head->next=p;
删除表头结点：p=head->next;head->next=p->next;free(p);
③加尾链表
判空条件：head==NULL;
在表尾插入p所指结点：
last->data=p->data;p->next=NULL,last->next=p,last=p;
④单向循环链表
判空条件：head==NULL;
表头插入p所指结点：p->next=head;head=p;rear->next=p;
删除表头结点：head=head->next;rear->next=head;
//rear代表最后一个结点
⑤单向加头循环链表
判空条件：head->next=head;
表头插入p所指结点：p->next=head->next;head->next=p;
删除表头结点：
head->next=head->next->next; rear->next=head->next;
⑥双向简单链表
判空条件：head->next=NULL;
插入分为三种情况：
表头插入：
p->Rlink=head;p->Llink=NULL;
head->Rlink->Llink=p;head=p;
表中插入：
p->Rlink=q->Rlink;p->Llink=q;
q->Rlink->Llink=p;q->Rlink=p;
表尾插入：
p->Rlink=q->Rlink;p->Link=q;
q->Rlink->Llink=p;q->Rlink=p;
⑦双向循环链表
判空条件：head==NULL;
//表中插入与双向链表一致
p->Rlink=q->Rlink;p->Llink=q;
q->Rlink->Llink=p;q->Rlink=p;
⑧双向加头循环链表
判空条件：head->next=head或head->Rlink=head->Llink
//表中插入与双向链表一致
p->Rlink=q->Rlink;p->Llink=q;
q->Rlink->Llink=p;q->Rlink=p;
⑨静态链表
网友评论