[理学]数据结构复习及应用练习

《[理学]数据结构复习及应用练习》由会员分享，可在线阅读，更多相关《[理学]数据结构复习及应用练习（172页珍藏版）》请在金锄头文库上搜索。

1、2019/1/17,1,数据结构复习及应用练习,2019/1/17,2,内容及目标,1、内容选取的价值原则 比较常用、易于使用、容易想起的内容。 2、内容选取的精简原则 简洁的内容容易立即、易于记忆，增加应用机会；复杂内容难于理解、容易忘记，增加应用障碍，减少应用机会。 3、内容掌握的熟练原则 小知识、小技能难度低，容易熟练掌握，大知识、复杂方法难度高，难以熟练掌握。,2019/1/17,3,第1章 绪论,1、ADT的一般定义形式,2019/1/17,4,第1章 绪论,1、ADT的一般定义形式是： ADT 数据对象： 数据关系： 基本操作： ADT 其中数据对象和数据关系的定义用伪码描述。 基

2、本操作的定义是： () 初始条件： 操作结果： ,2019/1/17,5,第2章 线性表,1、线性表的动态分配顺序存储结构 2、线性表的静态分配顺序存储结构 3、线性表的插入（基于静态分配顺序存储结构） 4、线性表的删除（基于静态分配顺序存储结构） 5、线性表的链式存储结构 6、动态分配结点空间及赋值 7、动态释放结点空间 8、静态分配结点空间及赋值 9、从表头指针head出发寻找表尾 10、在单链表表尾插入一个结点,2019/1/17,6,第2章 线性表,11、从表头到表尾依次输出单链表各个结点值 12、将单链表中的结点数据从表头到表尾依次存储在数组中 13、删除单链表的表尾结点 14、单链

3、表表空条件 15、循环链表表空条件 16、单链表表尾条件 17、 循环链表表尾条件 18、计算单链表中结点数目算法,2019/1/17,7,第2章 线性表,1、线性表的动态分配顺序存储结构 typedef int ElemType ; typedef struct sq ElemType *Elem_array;/存储数据元素 int length ;/存储线性表长度 sqList ;,2019/1/17,8,第2章 线性表,定义一个动态分配顺序存储结构的线性表 sqList sq; 分配存储空间 sq.Elem_array=( ElemType * )malloc(MAX_SIZE*size

4、of( ElemType ) ) ; sq.length= 0;,2019/1/17,9,第2章 线性表,2、线性表的静态分配顺序存储结构 #define MAX_SIZE 100 typedef int ElemType ; typedef struct ssq ElemType Elem_arrayMAX_SIZE;/存储数据元素 int length ;/存储线性表长度 ssqList ;,2019/1/17,10,第2章 线性表,定义一个静态分配顺序存储结构的线性表 ssqList ssq;/存储空间已获得 3、线性表的插入（基于静态分配顺序存储结构） 向整型线性表中连续插入6个元素：

5、 1）插入方法一、初始化时直接赋值（若已经知道插入的数值）： ssqList ssq=7, 4, -2, 19, 13, 6,6;,2019/1/17,11,第2章 线性表,插入方法二、从外界获取插入数据（事先不知道要插入的数据）： ssqList ssq; int i; for(i=0;i6;i+) scanf(“%d”,2019/1/17,12,第2章 线性表,在线性表下标位置k（0=k; -j ) ssq.Elem_arrayj+1=ssq.Elem_arrayj; /* k+1下标位置以后的元素后移 */ ssq.Elem_arrayk=e; /*在k位置插入结点*/ ssq.leng

6、th+ ; 画图分析在空表中插入一个元素时上述算法是否正确，在表尾插入一个元素时该算法是否正确。,2019/1/17,13,第2章 线性表,4、线性表的删除（基于静态分配顺序存储结构） 删除线性表下标位置k（0=kssq.length）处的1个元素e并返回该值： int j,e; e=ssq.Elem_arrayk ; for ( j=k;jssq.length ; j+) ssq.Elem_arrayj=ssq.Elem_arrayj+1; /* i位置以后的所有结点前移 */ ssq.length-; return (e);,2019/1/17,14,第2章 线性表,5、线性表的链式存储结

7、构 typedef int ElemType ; typedef struct Lnode ElemType data;/*数据域，保存结点的值*/ struct Lnode *next; /*指针域*/ LNode,*LinkList; /*结点的类型 */ 6、动态分配结点空间及赋值 LNode *p; p=(LNode*)malloc(sizeof(LNode); p-data=20; p-next=NULL ;,2019/1/17,15,第2章 线性表,7、动态释放结点空间 free(p); 8、静态分配结点空间及赋值 LNode p; p.data=20; p.next=NULL ;

8、 9、从表头指针head出发寻找表尾 LNode *q=head; while (q-next) q=q-next;/*循环结束时q指向表尾结点*/,2019/1/17,16,第2章 线性表,10、在单链表表尾插入一个结点 LNode *p,*q=head;/*head为头指针*/ while (q-next) q=q-next;/*q指向表尾结点*/ p= (LNode*)malloc(sizeof(LNode);/*分配一个结点空间*/ scanf(“%d”,/*q指向新的表尾结点*/,2019/1/17,17,第2章 线性表,11、从表头到表尾依次输出单链表各个结点值（假设数据域为整型）

9、 LNode *q=head-next;/*head为头指针*/ while (q) printf(“%d ”,q-data);/输出结点值*/ q=q-next; ,2019/1/17,18,第2章 线性表,12、将单链表中的结点数据从表头到表尾依次存储在数组中 LNode *q=head-next;/*head为头指针*/ ssqList ssq; int i=0; while (q) ssq.Elem_arrayi+=q-data; q=q-next; ssq.length=i;,2019/1/17,19,第2章 线性表,13、删除单链表的表尾结点 LNode *p=head,*q=he

10、ad;/*head为头指针*/ while (q-next) p=q; q=q-next; /*q指向表尾结点,p指向q的前驱*/ if(p=q) printf(“空表n”); else p-next=NULL; free(q); /*表不空,则删除表尾结点*/,2019/1/17,20,第2章 线性表,14、单链表表空条件 head-next=NULL 15、循环链表表空条件 head-next=head 16、单链表表尾条件 p-next=NULL 17、 循环链表表尾条件 p-next=head,2019/1/17,21,第2章 线性表,18、计算单链表中结点数目算法 LNode *q=

11、head-next;/*head为头指针*/ int i=0; while (q) i+ q=q-next; return i;,2019/1/17,22,第3章 栈和队列,1、栈的概念 2、栈的动态顺序存储表示 3、申请栈空间，初始化栈顶、栈底指针和栈容量 4、动态顺序栈的入栈 5、动态顺序栈的出栈 6、栈的静态顺序存储表示 7、静态顺序栈的初始化 8、静态顺序栈的入栈 9、静态顺序栈的出栈 10、队列的概念 11、静态顺序队列的存储结构 12、静态顺序循环队列为空的判断条件,2019/1/17,23,第3章 栈和队列,13、静态顺序循环队列为满的判断条件 14、静态顺序循环队列入队操作 1

12、5、静态顺序循环队列出队操作 16、利用栈实现单链表结点值逆序输出功能,2019/1/17,24,第3章 栈和队列,1、栈的概念 栈是仅在表尾进行插入和删除操作的线性表。又称为后进先出LIFO 或先进后出FILO线性表。 栈顶：允许进行插入、删除操作的一端，又称为表尾。 栈底：是固定端，又称为表头。,2019/1/17,25,第3章 栈和队列,2、栈的动态顺序存储表示 #define STACK_SIZE 100 /* 栈大小 */ typedef int SElemType ; typedef struct SElemType *base; /*栈底*/ SElemType *top; /*

13、 栈顶指针 */ int stacksize ; /*当前已分配空间*/ SqStack ;,2019/1/17,26,第3章 栈和队列,3、申请栈空间，初始化栈顶、栈底指针和栈容量 SqStack S; S.base=(SElemType*)malloc(STACK_SIZE *sizeof(SElemType);/*申请栈空间*/ S.top=S.base ; /*栈空时栈顶和栈底指针相同*/ S. stacksize=STACK_SIZE; /*置栈容量*/,2019/1/17,27,第3章 栈和队列,4、动态顺序栈的入栈 int Push(SqStack ,2019/1/17,28,第

14、3章 栈和队列,5、动态顺序栈的出栈 int Pop( SqStack ,2019/1/17,29,第3章 栈和队列,6、栈的静态顺序存储表示 #define STACK_SIZE 100 /* 栈大小 */ typedef int SElemType ; typedef struct SElemType stackSTACK_SIZE; /*栈空间*/ int top; /* 栈顶指针 */ int stacksize ; /* 栈空间大小*/ SSqStack ;,2019/1/17,30,第3章 栈和队列,7、静态顺序栈的初始化 SSqStack ssq; ssq.top=0; ssq.

15、stacksize=STACK_SIZE;,2019/1/17,31,第3章 栈和队列,8、静态顺序栈的入栈 int Push(SSqStack ,2019/1/17,32,第3章 栈和队列,9、静态顺序栈的出栈 int Pop(SSqStack ,2019/1/17,33,第3章 栈和队列,10、队列的概念 队列：是一种先进先出的线性表(简称FIFO表)。只允许在表的一端进行插入，而在另一端进行删除。 队头(队首)(front) ：允许进行删除的一端称为队首。 队尾(rear) ：允许进行插入的一端称为队尾。,2019/1/17,34,第3章 栈和队列,11、静态顺序队列的存储结构 #def

16、ine MAXQSIZE 100 /最大队列长度 typedef int QElemType; typedef struct QElemType baseMAXQSIZE; /*队列空间*/ int front ;/头指针 int rear ;/尾指针 SqQueue;,2019/1/17,35,第3章 栈和队列,12、静态顺序循环队列为空的判断条件 front=rear 13、静态顺序循环队列为满的判断条件 (rear+1)%MAXQSIZE =front,2019/1/17,36,第3章 栈和队列,14、静态顺序循环队列入队操作 int EnQueue(SqQueue /* 入队成功 */ ,2019/1/17,37,第3章 栈和队列,15、静态顺序循环队列出队操作 int DeQueue(SqQueue ,2019/1/17,38,第