文档介绍：2017-2-17 1一、绪论?(一) 数据结构的研究对象: ?数据结构的研究对象包括:数据的各种逻辑结构和存储结构以及对数据的各种操作。?(二)算法的五个特征: ?有穷性、确定性、可行性、输入、输出。?(三)算法的时间复杂度: ?T(n) = O(f(n)) ?T(n)叫算法的渐进时间复杂度,简称时间复杂度, O为数量级。 2017-2-17 2 ?习题: ?1、写出下列算法的时间复杂度。?(1) for(i=0;i<n;i+ +) ? c[i]=i ; ?(2) for(i=0;i<m;i+ +) ? for(j=0;j<n;j+ +) ? a[i][j]=i *j; ?2、数据结构的研究对象包括( )。?3、从逻辑上可以把数据结构分为( )和( ) 两种类型。 2017-2-17 3二、线性表?(一)顺序表: 2017-2-17 4 顺序表的存储结构: ?#define Maxsize maxlen ? typedef int elemtype; ? typedef struct ?{ ? elemtype v[Maxsize]; ? int len; ?}sqlist; 2017-2-17 5 ?习题: 给出顺序表的结构定义, 在顺序表 List 中元素数组下标位置 i插入一个元素 x。?#define MAXSIZE 100 ? struct list // 顺序表结构?{ ? int v[MAXSIZE]; // 元素数组? int len; // 顺序表当前包含的元素个数?}; ? typedef struct list List; ? int insert(List * L , int i , int x) ?{ ? // 略?} 2017-2-17 6 ?(二)单链表?每个结点包括两个域:数据域、指针域。?单链表存储结构: ? typedef struct node ?{ ? elemtype data; ? struct node * next; ?} Lnode ,* linklist; 2017-2-17 7 ?习题: 给出单链表的结构定义, 编写函数实现链表的插入和删除操作。? struct linknode // 单链表结点结构?{ ? int data; // 结点数据? struct linknode * next; // 后继结点指针?}; ? typedef struct linknode Lnode; ?(1)在结点 p之后插入值为 x的新节点 s ? void insert(Lnode * p,int x;) ?{ ?} ?(2)将结点 p的后继结点删除,并释放结点空间? void delete(Lnode *p) ?{ ?} 2017-2-17 8 ?(三)单循环链表: ?使单链表的最后一个节点的指针域的值不为 NULL, 而是指向头结点。这样,整个链表就形成了一个环, 这种链表称为单循环链表。 2017-2-17 9 ?习题: ?,要求内存中可用存储单元的地址( )。?A)必须是连续的 B)部分地址必须是连续的?C)一定是不连续的 D)连续或不连续都可以?( )。?A)插入和删除不需要移动元素?B)可随机访问任一节点?C)不必预分配空间?D)所需空间与其长度成正比 2017-2-17 10 ?3. 不带头结点的单链表 head 为空的判定条件是( )。?A) head = = NULL B ) head —>next = = NULL ?C) head —>next = = head D ) head ! = NULL ? head 为空的判定条件是( )。?A) head = = NULL B ) head —>next = = NULL ?C) head —>next = = head D ) head ! = NULL ? head 为空的判定条件是( )。?A) head = = NULL B ) head —>next = = NULL ?C) head —>next = = head D ) head ! = NULL