东华大学数据结构 参照严蔚敏版.ppt

《数 据 结 构》 东华大学计算机系 教学目录 1.1 本课程研究的问题 1.1 本课程研究的问题 例 3 迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树” 城市间交通网问题 1.1 本课程研究的问题 1．2 数据结构的有关概念 1．2 数据结构的有关概念 1．3 数据结构的分类及表示 1．4 算法与算法分析 描述算法的书写规则 所有算法均以函数形式给出, 算法的输入数据来自参数表 参数表的参数在算法之前均进行类型说明 有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明 解法2 # define N 100 Void scheme( ) { int i, j; for (i=0; i=N/3; i++) for (j=0; j=(N-3*i)/2; j++) { if (3*i+2*j+0.5*(N-i-j)= =N) printf(“%d, %d, %d\n%”, i, j, N-i-j); } } 时间复杂度为O(N2 ) 第二章 线性表 第二章 线性表 2. 1 线性表的概念 2.1 线性表的概念 2.1 线性表的概念 2.1 线性表的概念 2.1 线性表的概念 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 二、顺序表的基本操作算法 插入 insert(v, x, i) 功能：在顺序表v 中的第 i ( 1=i=n+1)个数据元素之前插入一个新元素x, 插入前线性表为 (a1, a2, a3,…, ai-1 ,ai,,… an ) 插入后,线性表长度为n+1, 线性表为 (a1, a2, a3,…, ai-1 , x, ai,,… an ) 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.2 线性表的顺序存储和实现 2.3 线性表的链式存储和实现 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2. 3. 1 线性链表 2.3 线性链表 2.2 线性链表 2. 3. 1 线性链表 2.3.1 线性链表 建立链表 NODE *create_link(n) /*建立有n个结点的线性单链表的算法 { NODE *head, *p, *q; int i; p=( NODE *)malloc(sizeof(NODE));head=p; for(i=I;I=n;i++) {q= ( NODE *)malloc(sizeof(NODE)); q-data=i; q-link=NULL; p-link=q;p=q; } return(head); } 插入结点 q=(NODE *)malloc(sizeof(NODE)); q-deta=‘a’; q-link=p-link; p-link=q; 2. 3. 1 线性链表 2. 3. 1 线性链表 Int insert_link(NODE *head,int x, int i) { NODE *p,*s;int j; p=head;j=0; while ((p!=NULL)(ji-1)) {p=p-link;j++;} if(p==NULL)return(0); s=(NODE *(malloc(sizcof(NODE)); s-data=x; s-link=p-link; p-link=s; return(1); } 删除结点 q=p-link; p-link=q-link; free(q); 2. 3. 1 线性链表 在线性链表中删除第i个结点 Int delete_link(NODE *head, int i) { NODE *p,*q;int j; p=head;j=0; while ((p!=NULL)(ji-1))