3第二章、三章复习.ppt

1、第2、3章 复习,基本内容 线性表的定义和基本操作 栈的定义和基本操作 队列的定义和基本操作,退出,#define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int last; SeqList;,一、顺序表,定义：,x,插入操作：,删除操作：,顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充,二、单链表,typedef struct node datatype data; struct node *next

2、; LNode，*LinkList；,定义：,s-next=p-next;,p-next=s;,插入操作：,S=p-next;p-next=s-next,删除操作：,链式存储结构的优缺点,优点 它是一种动态结构 不需预先分配空间,缺点 指针占用额外存储空间 不能随机存取，查找速度慢,图 3-1,三、顺序栈,特点：后进先出,定义：,#define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int top; SeqStack；,x,入栈操作：,出栈操作：,e,s-datas-top=x; s-top+;,s-top-; *x=s-datas-

3、top;,四、链栈,typedef struct node datatype data; struct node *next; StackNode，* LinkStack;,定义：,入栈操作：,s-next=top; top=s;,出栈操作：,*x=top-data; top=top-next;,五、顺序队,define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int rear,front; SeQueue;,特点：先进先出,a1,a2,an,e, ,入队操作：,出队操作：,a1,a2,an, ,sq-rear=(sq-rear+1)%

4、MAXSIZE; sq-datasq-rear=x;,sq-front=(sq-front+1)%MAXSIZE; *x=sq-datasq-front;,typedef struct node/结点类型 datatype data; struct node *next; QNode;,六、链队,typedef struct / 链队列类型 QNode *front; / 队头指针 QNode * rear; / 队尾指针 LinkQueue;,空队列,入队操作：,q-rear-next=p; q-rear=p;,a1,an,q-rear,a2,出队操作：,q-front-next=p-next;,p,例1：设一顺序表中元素递增有序。写一算法，将元素x插入到表中适当位置，并保持顺序表的有序性。,1 3 6 9,插入4,11,例2：已知单链表H，写一算法删除其