数据结构(c语言版)_知识点串联

《数据结构(c语言版)_知识点串联》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一章绪论逻辑结构：线性结构（2线性表；3栈和队列；4数组和广义表；5串）和非线性（6树；7图）8查找；9排序存储结构：顺序存储、链式存储、索引存储、散列存储顺序存储和链式存储的优缺点：n顺序存储优点：存取方式是随机的，读取数据比较方便缺点：插入和删除操作需要移动大量的数据n链式存储方式的优缺点与顺序相反。判断算法好坏的标准：时间复杂度和空间复杂度第二章线性表线性表：由n（n>=0）个相同数据类型的元素组成的有限序列。逻辑特征：（1：1）l第一个结点是开始结点，无前驱有唯一的后继l最后一个结点是

2、终端节点，无后继有唯一的前驱l中间结点，有唯一前驱和唯一的后继逻辑结构的定义方式：（元素1，元素2，。。。）存储结构：（物理结构）l顺序存储(用数组体现)：预先分配一段连续的区域，静态分配inta[10];a表示a[0]的地址顺序表：两层含义：逻辑结构上线性结构物理上顺序存储l链式存储（用指针）：占用的区域不一定连续，动态分配；mallocfree链表：两层含义：逻辑结构上线性结构物理上链式存储顺序表的插入：maxsize表示最多存放的元素的个数，size表示有效元素的个数1、判断满不满：满的条

3、件：size==maxsize2、插入的位置是不是合法（i>=1&&i<=size+1）3、后移（先移动后面的）4、插入size++；顺序表的删除：1、判断空间是否是空（size==0）2、判断位置是不是合法（1<=i<=size）3、前移（先移动前面的）4、Size--链表：分类：单链表、循环链表、双链表三个术语：头结点、头指针、开始结点插入操作：p结点的后面1、生成空间：s=(S*)malloc(sizeof(S));2、赋值：s->data=X;3、s->next=p->next;(修改新

4、结点的指针)1、P->next=s;链表的删除：p结点的后面的结点1、q=p->next;2、p->next=q->next;//p->next=p->next->next;3、free(q);删除p结点本身：A、寻找p结点的前驱结点,转化为删除p结点的前驱结点的后继q=head;while(q->next!=p)q=q->next;q->next=p->next;free(p);B、删除p的后继（p结点不是终端结点，p一定要有后继）q=p->next;p->data=q->data;p->ne

5、xt=q->next;free(q);第三章栈和队列栈和队列是特殊的线性表。特殊在插入和删除操作都是在表的端点处进行。栈Stack：操作受限（插入和删除）的线性表。在线性表的末尾做插入和删除，叫做栈顶top线性表的开始部分叫做栈底bottom特点：FILO典型应用：函数的调用存储方式：l顺序存储（用数组体现，静态分配存储空间）l链式存储（涉及到指针，动态分配存储空间）顺序栈的插入：top表示栈顶元素的下标，定义是int类型的，格式是inttop；maxsize表示空间的大小，最多存放多少个元素(

6、在顺序表的基础上修改的，红颜色粗体部分去掉)1、判断满不满：满的条件是top==maxsize-12、插入的位置是不是合法（i>=1&&i<=size+1）：去掉原因是位置固定size+13、后移（先移动后面的）：去掉4、top++；插入（data[top]=X）顺序栈的删除：(在顺序表的基础上修改的，红颜色粗体部分去掉)1、判断空间是否是空（top==-1top<0）2、判断位置是不是合法（1<=i<=size）3、前移（先移动前面的）1、top--链栈的插入操作：top表示栈顶的指针，类似于

7、head，top是指针变量格式：数据类型*top；1、生成空间：s=malloc（。。。。）；2、赋值：s->data=X;3、修改指针：s->next=top;(先修改的是新结点的指针)4、修改top指针：top=s；链栈的删除：1、p=top;2、top=top->next;3、free(p);进栈的顺序是123，则可能的出栈的顺序是123、132、213、231、312、321进栈的顺序是1234，则可能的出栈的顺序是1234、1243、1324、1342、1432、2134、2143、2

8、314、2341、2431、3214、3241、3421、4321队列：1、定义：操作受限的线性表（在表的一端进行插入、在另一端进行删除）2、在线性表的末尾进行插入操作，叫做队尾rear在线性表的开始做删除操作，叫做队头front3、特点：FIFO4、存储结构：l顺序存储（用数组体现，静态分配存储空间）l链式存储（用指针体现，动态分配存储空间）入队列的顺序是1234，则出队的顺序是1234。循环队列：队列的顺序存储结构循环队列长度是maxsize，则最多存放maxsize-1个元素lFront表