第2章基本数据结构及运算 数据处理:数据如何组织,以便提高处理速度,节省存贮空间一一关键问题 研究内容 1.逻辑结构:数据元素间的关系。 2.物理结构/存贮结构:各数据元素在计算机中的存贮关系 3.运算:对各种数据结构的操作 21数据结构的基本概念 数据处理:对数据元素进行运算:包括插入、删除、查找、更新等,也包括分析。 建立数学模型固然好,但有时难以表示成模型,感兴趣的是数据元素之间的关系。为了提高处理效率,应 如何组织他们,即如何表示数据元素 书上通过实例说明数据采用不同表示方法对处理效率的影响 数据结构是一门研究数据如何组织、存储和运篡的一般方法的学科。 212什么是数据结构 数据:描述客观事务的数字符以及所有能输入计算机中并被程序识别和处理的符号的集合,计算机处理的 对象。 ∫数值性数据:工程,科学计算和商业 非数值性数据:字符串,文字,图形和语音 数据元素 Data elemen):数据的基本单位 个数据元素可由若干数据项( ata Item)组成 数据项:数据的最小单位。 书名作者名分类出版年月 数据元素亦称点或己录 数据项亦称字度或越 数据对象 Data object):是性质相同的数据元素的集合,是数据的一个子集 数据结构 Data structure):是相互之间存在一种或多种特定关系的数据元素的集合 1.数据的逻辑结构 数据结构可描述为 Group=(D,R) D:有限个数据元素的集合:R有限个结点间关系的集合 例题见书 图形表示:见书
1 第 2 章基本数据结构及运算 数据处理：数据如何组织，以便提高处理速度，节省存贮空间——关键问题。 研究内容： 1． 逻辑结构：数据元素间的关系。 2． 物理结构/存贮结构：各数据元素在计算机中的存贮关系。 3． 运算：对各种数据结构的操作。 2.1 数据结构的基本概念 数据处理：对数据元素进行运算：包括插入、删除、查找、更新等，也包括分析。 建立数学模型固然好，但有时难以表示成模型，感兴趣的是数据元素之间的关系。为了提高处理效率，应 如何组织他们，即如何表示数据元素。 书上通过实例说明数据采用不同表示方法对处理效率的影响。 数据结构是一门研究数据如何组织、存储和运算的一般方法的学科。 2.1.2 什么是数据结构 数据：描述客观事务的数字符以及所有能输入计算机中并被程序识别和处理的符号的集合，计算机处理的 对象。 非数值性数据： 字符串，文字，图形和语音 数值性数据：工程，科学计算和商业 数据元素(Data Element) ：数据的基本单位。 一个数据元素可由若干数据项(Data Item)组成。 数据项：数据的最小单位。 数据元素亦称结点或记录 数据项亦称字段或域 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 1． 数据的逻辑结构 数据结构可描述为 Group=（D，R） D：有限个数据元素的集合；R 有限个结点间关系的集合 例题见书 图形表示：见书
2.数据的存贮结构 14线性数据结构与非线性数据结构 线性表 A.线性结构了栈 队列 数据的逻辑结构 数组 据 B.非线性结构树形结构 构的三个方面 图形结构 A顺序存储 2、数据的存储结构B链式存储 C索引 3、数据的运算:检索、排序、插入、删除、修改等 A.线性结构(一对一) 特性:1有且只有一个根结点 2每个结点最多一个前件,最多一个后件。(第一个数据元素无前件,最后一个无后件,其它有 且仅有一个前驱和一个后继。 例:(A,B,C 例 学生成缋表 成缚 9861109 卓 100 9861107 如忠 95 Q61103 B.非线性结构树形结构(一对多 学校 系别 计算机系 数学系 物理系 专业计算机应用计算机软件数学 理论物理应用物理 班级91…95991…9959 995991 学生张力……李场…… 赵壮………王芳
2 2． 数据的存贮结构 2.1.4 线性数据结构与非线性数据结构 A. 线性结构（一对一） 特性：1.有且只有一个根结点 2.每个结点最多一个前件，最多一个后件。（第一个数据元素无前件，最后一个无后件，其它 有 且仅有一个前驱和一个后继。） 例：（A , B , C , ·······，X ,Y , Z） 例： 学 生 成 绩 表 B．非线性结构:树形结构（一对多） 1．数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A．线性结构 B．非线性结构 A 顺序存储 B 链式存储 C 索引 线性表 栈 队列 树形结构 图形结构 数 据 结 构 的 三 个 方 面 数组 9861103 胡孝臣 86 9861107 刘忠赏 95 9861109 张卓 100 学号 姓名 成绩
B.非线性结构图形结构(多对多) D={1,2,3,4} R={(1,2),(1,3),(1,4),(2,3) (3,4),(2,4)} 数据的存储结构 A.顺序存储 顺序存储结构常用于线性数据结构,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 顺序存储结构的三个弱点: 1.插入或删除操作时,需移动大量元素 2.长度变化较大时,需按最大空间分配 3表的容量难以扩充 B链式存储 每个节点都由两部分组成:数据域和指针域 数据域存放元素本身的数据,指针域存放指针。 数据元素之间逻辑上的联系由指针来体现 链式存储结构特点 1比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。 2逻辑上相邻的节点物理上不必相邻 3插入、删除灵活(不必移动节点,只要改变节点中的指针) 22线性表及其存贮结构 线性表逻辑结构 n个数据元素的有限序列(al,a2,a3,an) n为线性表的长度(n≥0),n=0的表称为空表 特性: 数据元素呈线性关系 所有数据元素ai在同一个线性表中须是相同的数据类型 ·线性表的基本运算: (1)插入:在两个确定的元素之间插入一个新的元素 (2)删除:删除线性表中某个元素; (3)修改:按某种要求查找元素,需要时,还可找到元素进行值的更新 l顺序存储结构及插入删除运算 线性表的顺序存储结构,可用C语言中的一维数组来描述
3 B．非线性结构:图形结构（多对多） D={ 1 , 2 , 3 , 4} R={(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) } 2、数据的存储结构 A. 顺序存储 顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 顺序存储结构的三个弱点： 1.插入或删除操作时，需移动大量元素。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。 B.链式存储 每个节点都由两部分组成：数据域和指针域。 数据域存放元素本身的数据，指针域存放指针。 数据元素之间逻辑上的联系由指针来体现。 链式存储结构特点： 1.比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成)。 2.逻辑上相邻的节点物理上不必相邻。 3.插入、删除灵活(不必移动节点，只要改变节点中的指针)。 2.2 线性表及其存贮结构 • 线性表逻辑结构 – n 个数据元素的有限序列:(a1, a2 ,a3,…an) n 为线性表的长度(n≥0)，n=0 的表称为空表 • 特性： – 数据元素呈线性关系. – 所有数据元素 ai 在同一个线性表中须是相同的数据类型 • 线性表的基本运算： (1)插入：在两个确定的元素之间插入一个新的元素； (2)删除：删除线性表中某个元素； (3)修改：按某种要求查找元素，需要时，还可找到元素进行值的更新； 1.顺序存储结构及插入删除运算 .线性表的顺序存储结构 ,可用 C 语言中的一维数组来描述. 1 4 2 3
# define LiStInitsize100线性表存储空间的初始分配量 type Elem Type *elem;∥数组指钍表示存储空间基址 当前长度 int listsize∥当前分配的存储容量(以 sizeof( Elem Type)为单位) Status ListInsert sq (Sqlist &v, int i, Elem Typex) ∥在线性表V中第i个元素之前插入x,i的合法值为1≤isⅤ Length+1 if(iⅤ length+1) return ERROR,/i值不合法 if( V length>Ⅴ listsize) return OVERFLoW,∥无存储空间 q=&Ⅴelem[-1l,/下行注:插入位置后的元素依次右移 for(p=&Velem[V length-1]; p>=q:--p *q=x,∥插入x ++ V length;,∥表长加1 return oK Status List Delete sq Elem Type x)( if (iV length return ERROR: P=&velem[i-1 P q=Ⅴelem+Ⅴ length-1; for(++pp<=q;++p)*(p-1)=*p 2链式存储结构及插入删除运算 特点:用一组任意的存储单元可以是连续的也可以是不连续的)存放线性表的数据元素。 存储地址 数据域 指针域 头指针H WANG NLL ZHAO ZHENG ZHOU 上图为(ZHAO,QIAN,SUN,L,ZHOU,wU, ZHENG,wNG)
4 #define LISTINITSIZE 100 //线性表存储空间的初始分配量 typedef struct{ ElemType *elem；//数组指针表示存储空间基址 int length； //当前长度 int listsize //当前分配的存储容量（以 sizeof（ElemType）为单位） }Sqlist Status ListInsert_sq（Sqlist V，int i , ElemType x） { //在线性表 V 中第 i 个元素之前插入 x， i 的合法值为 1 iV.Length+1 if（iV.length+1）return ERROR; //i 值不合法 if(V.length>V.listsize) return OVERFLOW; //无存储空间 q=V.elem[i-1]; //下行注：插入位置后的元素依次右移 for(p=V.elem[V.length-1]; p>=q; − −p) (p+1)= p; q=x; // 插入 x ++V.length; //表长加 1 return OK; } Status ListDelete_sq（Sqlist V，int i , ElemType x）{ if（iV.length）return ERROR; P=V.elem[i-1]; x =P; q= V.elem+ V.length−1 ; for(++p;p<=q;++p) *(p−1)=*p − −V.length; return OK; } 2.链式存储结构及插入删除运算 特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。 上图为(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)
线性表的线性链表存储结构,存储从头指针开始进行。 ZHAO (1)线性表的单链式存储结构 线性表的链式存储结构可用C语言中的“结构指针来描述 Typedef Elem Type data struct Lnode *next 3 Lnode, "linklist 单链表的插入运算 ListInsert L(LinkList &L, int i, Elem Type x)t p=L;j=0; while( p&&jnext; ++j; if(!p I i>i-1)return ERRO s(struct LNode ")malloc(sizeof(struct LNode)) s->data=x; S->next=p->next; p->nexts return OK: 单链表的删除运算 List Delete L(LinkList &L, int i, Elem Type x)i p=L;j=0; while( p->next & jnext; ++j; if(!(p->next) I ii-1)return ERROR gp->next; p-nextq->next; free(q); return OK: (2)循环链表P64
5 线性表的线性链表存储结构，存储从头指针开始进行。 （1）线性表的单链式存储结构 线性表的链式存储结构可用 C 语言中的“结构指针”来描述 Typedef struct Lnode { Elem Type data； struct Lnode *next； } Lnode，*linklist； 单链表的插入运算 ListInsert_L(LinkList &L,int i, ElemType x){ p=L; j=0; while( p&&jnext; ++j;} if( ! p j>i-1) return ERROR; s=(struct LNode *)malloc(sizeof(struct LNode)); s->data=x; s->next=p->next; p->next=s; return OK; } 单链表的删除运算 ListDelete_L(LinkList &L，int i, ElemType x){ p=L; j=0; while( p->next && jnext; ++j; } if( ! (p->next) j>i-1) return ERROR; q=p->next ; p->next=q->next; free(q); return OK; } （2） 循环链表 P64
将最后一个结点的空指针改为指向头结点,从任一结点出发均可找到其它结点 (3)双向链表P55 在每个结点中设置两个指针,一个指向后继,一个指向前驱。可直接确定一个结点的前驱和后继结点 可提高效率。一插入和删除 作业2:对以下单链表分别执行下列各程序段并画出结果示意图 L→D十[5十1 Rs↑ (1)LFP->link; (4)P->link->link->link->data=P->data hile(tl=NUll) T->data=( T=T->link while(T->linkI=NULL T->data=(T->data)2 T=T->link ()P=(JD*)malloc(sizeof(JD)); R->linker: P->link=s TL T->linkep->link. (9)S->link 习题:2。10逆转线性单链表 扫描单链表将第一个节点的next设置为NULL将第二个节点的next指向第一个节点,将第三个节点的 next指向第二个节点 Invert(head) Node *head i node*p, *.*r P=head; q=p->next; While(q=null) head->nextENULL: 33栈
6 将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。 （3） 双向链表 P55 在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。 可提高效率。—插入和删除 作业 2： 对以下单链表分别执行下列各程序段,并画出结果示意图. (1) L=P->link; (2) R->data=P->data; (3) R->data=P->link->data; (4) P->link->link->link->data=P->data; (5) T=P; while(T!=NULL) { T->data=(T->data)*2; T=T->link; } (6) T=P; while(T->link!=NULL) { T->data=(T->data)*2; T=T->link; } (7) P=(JD*)malloc(sizeof(JD)); P->data=10; R->link=P; P->link=S; (8) T=L; T->link=P->link; free(P); (9) S->link=L; 习题：2。10 逆转线性单链表 扫描单链表,将第一个节点的 next 设置为 NULL,将第二个节点的 next 指向第一个节点, 将第三个节点的 next 指向第二个节点,… Invert(head) Node *head; { node *p,*q,*r; P=head; q=p—>next; While (q!=NULL) { r=q—>next; q—>next=p; p=q; q=r; } head—>next=NULL; head=p;} 3.3 栈 L S 2 5 7 3 8 ^ P R
1.栈 stack的定义 栈是特殊的线性表,仅在表的一端进行插入或删除操作 特点:(1)对栈内数据的操作总在栈顶进行 (2)数据进栈称为“压入”push (3)数据出栈称为“弹出”pop (4)遵循“后进先出”的原则LIFO 例题:输入顺序ABC,输出顺序有几种? ABC,ACB,BAC,BCA,CBA,不可能产生CAB 2.栈的顺序存储结构及运算 用数组实现栈, 为栈底,top为栈顶 (1)定义 typedef struct stack type elemtype data MAXNUM; Astack type (2)进栈push 当新元素进栈时,栈顶上移,新元素放在栈顶。 stack top=stack top+l: stack.datalstack top]= new one (3)出栈pop:从栈顶移出一个数据 栈顶元素拷贝出栈,栈顶下移 elemptype pop(stack type *stack) i elemtype out; f(stack->top data[stack->top; stack->top= stack->top-1 return out (4)栈空判断 stack top==0(stack top= MAXNUM-1
7 1. 栈 stack 的定义 栈是特殊的线性表，仅在表的一端进行插入或删除操作 特点：（1）对栈内数据的操作总在栈顶进行 （2）数据进栈称为“压入”push （3）数据出栈称为“弹出”pop （4）遵循“后进先出”的原则 LIFO 例题：输入顺序 A,B,C，输出顺序有几种？ ABC,ACB,BAC,BCA,CBA, 不可能产生 CAB 2.栈的顺序存储结构及运算 用数组实现栈, a[0]为栈底，top 为栈顶 （1）定义 typedef struct stack_type{ elemtype data[MAXNUM]; int top; }stack_type; （2）进栈 push 当新元素进栈时，栈顶上移，新元素放在栈顶。 stack.top = stack.top + 1; stack.data[stack.top] = new_one; （3）出栈 pop: 从栈顶移出一个数据。 栈顶元素拷贝出栈，栈顶下移 elemptype pop(stack_type *stack) { elemtype out; if(stack->top data[stack->top]; stack->top = stack->top -1; } return out; } （4）栈空判断 stack.top = = 0 (stack.top = MAXNUM - 1;
(5)置栈空 stack top=-1 (6)栈的应用 例程序的嵌套,中断的嵌套 见书P35 3.栈的链式存储结构及运算 用链表实现栈 (1)定义 typedef struct stack typet node type* top int length; 3 stack type: (2)压入psh void push(stack, new node)i new_ node->next= stack->top: stack->top= new node ck->length ++ (3)弹出pop node type* pop(stack) node type *out; out=stack->top; stack->top= stack->top->next; stack->length -- return out; (4)栈空判断 stack top= NULL (5)置栈空 能否简单的使用 stack top=NULL? 如果栈中还有链点,必须逐个将链点占用的空间释放 1、逐个将链点弹出 2、释放链点空间 void clean(stack R node type* temp while(! empty(stack))t temp= pop(stack); free(temp);)
8 （5）置栈空 stack.top = -1; （6）栈的应用 例 程序的嵌套，中断的嵌套 见书 P35 3.栈的链式存储结构及运算 用链表实现栈 （1）定义 typedef struct lstack_type{ node_type * top; int length; }lstack_type; （2）压入 push void push(stack, new_node){ new_node->next = stack->top; stack->top = new_node; stack->length ++;} （3）弹出 pop node_type * pop(stack){ node_type* out; out = stack->top; stack->top = stack->top->next; stack->length --; return out;} （4）栈空判断 stack.top == NULL; （5）置栈空 能否简单的使用 stack.top = NULL ? 如果栈中还有链点，必须逐个将链点占用的空间释放 1、逐个将链点弹出 2、释放链点空间 void clean(stack){ node_type * temp; while( ! empty(stack)){ temp = pop(stack); free(temp); }
34队列 1队列定义 类似于排队机制的结构,队列是特殊的线性表, 节点的插入仅限于在表尾进行,节点的删除仅限于在表头进行 队列特点 特点 (1)对队列的操作在表的两端进行 (2)仅在队尾加入节点——入队 enqueue (3)仅在队首移出节点——出队 dequeue ◆(4)遵循“先进先出”的原则—FIFO 队列的顺序存储结构及运算 2.用数组实现队列 (1)定义 typedef struct queue type i elemtype data MAXNUMI int front: int rear: queue type; (2)入队与出队 用循环数组实现队列 void enqueue(queue, new one) i if((queue->rear+1)%MAXNUM== queue->front)error(1) else queue->data queue->rear new one queue->rear=(queue->rear +1)% MAXNUM elemtype dequeue(queue) i elemtype out; queue->front) error(2); else out =queue->datalqueue->front queue->front=(queue->front +1)% MAXNUM; return out; 思考:数组Q0,41 front=l, rear=3
9 } 3.4 队列 1.队列定义 类似于排队机制的结构, 队列是特殊的线性表， 节点的插入仅限于在表尾进行，节点的删除仅限于在表头进行. 队列特点 ◼ 特点： ◆ （1）对队列的操作在表的两端进行 ◆ （2）仅在队尾加入节点——入队 enqueue ◆ （3）仅在队首移出节点——出队 dequeue ◆ （4）遵循“先进先出”的原则——FIFO 队列的顺序存储结构及运算 2. 用数组实现队列 （1）定义 typedef struct queue_type { elemtype data[MAXNUM]; int front; int rear; }queue_type; （2）入队与出队 用循环数组实现队列 void enqueue(queue, new_one) { if( (queue->rear + 1) % MAXNUM = = queue->front ) error(1); else{ queue->data[queue->rear] = new_one; queue->rear = (queue->rear +1) % MAXNUM; } } elemtype dequeue(queue) { elemtype out； if( queue->rear = = queue->front ) error(2); else{ out ＝queue->data[queue->front]; queue->front = (queue->front +1) % MAXNUM; } return out； } 思考：数组 Q[0,4] 1. front=1， rear=3 2. front=3， rear=1
3.用链表实现队列 (一)定义 typedef struct Iqueue type i node type* front node type 云rear int length (二)入队 新链点插入到队尾 注意:队列为空时,rear和 front都要指向新元素 new node ->next= NUlL: list->rear ->next new node (三)出队 删除队首链点 注意:当队列被删空时,rear指针要置空 temp= list->front; list->front list->front->next 习题: 例1若进栈序列为3,5,7,9,进栈过程中可以出栈,则不可能的一个出栈次序是(d)。 (a)7,5,3,9(b)9,7,5,3(c)7,5,9,3d)9.5,7,3 例3对于下面的程序调用过程,请问入栈序列是(1,2,3),出栈次序是(2,1,→ 例2用一维数组设计栈,初态是栈空,top=。现有输入序列是a、b、c、d,经过push、push、pop、 push、pop、push操作后,输出序列是(b,c ),栈顶指针是 程序A程序B程序C程序D Call d return 例4设栈S为空,队Q的状态是abcd,其中a为队首元素,d为队尾元素,经过下面两个操作后,队Q 的状态是(c)。 (1)删除队Q中的元素,将删除的元素插入栈S,直到队Q为空。 (2)依次将栈S中的元素插入队Q,直到栈S为空。 (a)abcd(b)acbd (c) (d) bacd 例5 Josephus问题 n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局:然后从出局的下一 个人重新开始报数,数到第m个人,再让他出局,。。,如此反复直到所有的人都出局为止。下面要解决的 Josephus问题是:对于任意给定的n,s和m,求出这n个人的出局序列。请以n=9,s=3,m=4为例,模拟 Josephus 的求解过程求问题的解 用顺序表结构和循环单链表结构求解 Josephus问题的一般步骤为 1)首先利用线性表的一些运算如创建空线性表、插入元素等构造 Josephus表
10 3．用链表实现队列 （一）定义 typedef struct lqueue_type { node_type * front; node_type * rear; int length; } （二） 入队 ◆ 新链点插入到队尾 ◆ 注意：队列为空时，rear 和 front 都要指向新元素 new_node->next = NULL; list->rear ->next = new_node; （三） 出队 ◆ 删除队首链点 ◆ 注意：当队列被删空时，rear 指针要置空 temp = list->front; list->front = list->front->next; 习题: 例 1 若进栈序列为 3，5，7，9，进栈过程中可以出栈，则不可能的一个出栈次序是（ d ）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3 例 2 用一维数组设计栈，初态是栈空，top=0。现有输入序列是 a、b、c、d，经过 push、push、pop、 push、pop、push 操作后，输出序列是（ b, c ），栈顶指针是（ 2 ） 例 3 对于下面的程序调用过程，请问入栈序列是（1, 2, 3 ），出栈次序是（ 2, 1, 3）。 程序A Call B 1: . . Call D 3: 程序B Call C 2: . . return 程序C Begin return 程序D Begin return 例 4 设栈 S 为空，队 Q 的状态是 abcd，其中 a 为队首元素，d 为队尾元素，经过下面两个操作后，队 Q 的状态是（ c ）。 （1）删除队 Q 中的元素，将删除的元素插入栈 S，直到队 Q 为空。 （2）依次将栈 S 中的元素插入队 Q，直到栈 S 为空。 (a) abcd (b) acbd (c) dcba (d) bacd 例 5 Josephus 问题 设 n 个人围坐在一个圆桌周围，现在从第 s 个人开始报数，数到第 m 个人，让他出局；然后从出局的下一 个人重新开始报数，数到第 m 个人，再让他出局，。。。，如此反复直到所有的人都出局为止。下面要解决的 Josephus 问题是：对于任意给定的 n,s 和 m，求出这 n 个人的出局序列。请以 n=9,s=3,m=4 为例，模拟 Josephus 的求解过程求问题的解。 用顺序表结构和循环单链表结构求解 Josephus 问题的一般步骤为： 1）首先利用线性表的一些运算如创建空线性表、插入元素等构造 Josephus 表；
