数据结构ppt——1

《数据结构ppt——1》由会员分享，可在线阅读，更多相关《数据结构ppt——1（89页珍藏版）》请在金锄头文库上搜索。

1、常见复杂度量级比较,c log2n n nlog2n n2 n3 2n 3n n! 一般情况下，尽可能选择多项式阶O(nk)的算法，而尽量避免指数阶的算法。,2,静态分配的特点：线性表大小固定。,顺序表的存储结构（1）,静态分配存储结构,ElemType elemListSize; /静态分配的线性表空间,typedef int ElemType; /线性表数据类型,#define ListSize 100 /线性表的最大长度,int length; /线性表当前长度,typedef struct ElemType elemListSize; /静态分配的线性表空间 int length; /

2、线性表当前长度 Sqlist;,3,ElemType *elem; /存储空间基址,typedef int ElemType; /线性表数据类型,int listsize; /当前分配的空间大小,int length; /当前长度,typedef int ElemType; /线性表数据类型 typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 Sqlist;,#define LIST_INIT_SIZE 100 /初始空间分配大小 #define LISTINCREMENT 10 /线性表空间分配增量,顺序表的存储结构（2）,动态分

3、配存储结构：课本上主要采用的结构,动态分配的特点：顺序表空间可以根据需要增加。,4,顺序表算法：构造空表 InitList(Sqlist &L),采用动态分配存储结构 实现步骤 1. 获取表存储空间,2.初始化表有关数据 表的当前长度，L.length=_。 当前分配的最大空间，L. listsize= _。,L.elem=(ElemType *)malloc( LIST_INIT_SIZE *sizeof(ElemType) );,0,100,5,Status InitList_Sq ( SqList / InitList_Sq,构造空表完整算法,6,ListInsert(&L, i, e)

4、,插入，在线性表L的第i个位置前插入元素e；,实现步骤： 将第n至第i 位的元素依次向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。,7,找到插入位置；,插入位置及之后的元素右移；,插入e；,表长增1；,return 0; / ListInsert_Sq,int ListInsert_Sq(SqList &L, int i, ElemType e) /在顺序表L中第i个位置之前插入新的元素e,q= /插入位置,for (p=,*q=e;,+L.length;,插入位置是否合法？,空间是否够用？,if (iL.length+1) return -1; /i值不合法 /如果当前空间已

5、满，则 增加分配空间 if (L.length=L.listsize) increment (L) ;,for (j=length;j=i;j-) L.elemj= L.elemj-1; L.elemi-1=e;,8,void increment ( SqList /增加存储容量 ,为顺序表增加存储空间,&,9,插入操作时间复杂度分析,插入 前提：假设每个位置都是等概率的.,T(n) = O(n),10,删除操作时间复杂度分析,删除,T(n) = O(n),11,查找操作的时间复杂度分析,若查找概率 pi 均相等，则,查找不成功，数据比较 n 次。,若查找成功, (设pi查找概率，ci 比较次

6、数),查找操作的最坏情况时间复杂度 T(n) = O(n),12,Summary: 顺序表,本质：逻辑上相邻，物理也相邻 优点：元素存取是随机的。 时间复杂度为O(1)。 缺点：插入/删除元素要移动大量元素。 平均时间复杂度是O(n)。,如何改进？,链式存储结构,13,顺序表的应用(1) 求两个集合的并集,已知两个集合A和B，将集合B合并到A。,算法： 取b中一个元素； 判断该元素是否在A集合中； YES，取b中下一个元素； No，该元素插入到A集合末尾； B集合元素是否处理完； Yes，结束； No，从第一步重复；,14,typedef int ElemType; typedef struc

7、t LNode ElemType data; /结点的数据域 struct LNode *next; /结点的指针域 LNode, *LinkList;,2.3.1 单链表的定义,15,2.3.2 单链表的插入操作,核心语句：,Step 1：s-next=p-next; Step 2：p-next=s ；,p-next,s-next,当!当!当! 万无一失吗? 有没有问题呢?,16,单链表插入操作的特殊情况（1）,核心语句： s-next=head; head=s ；,在第一个结点前插入,原语句： s-next=p-next; p-next=s ；,p,17,单链表插入操作的特殊情况（2）,在

8、末尾插入,核心语句： s-next=NULL; p-next =s ；,p,b,a,head,原语句： s-next=p-next; p-next=s ；,18,单链表插入操作的特殊情况（3）,空表插入,核心语句： s-next=NULL; head =s ；,head=NULL,原语句： s-next=p-next; p-next=s ；,太麻烦了！ 赶快想个办法吧！,19,解决之道：带表头结点的单链表,空表：,首结点：存储第一个数据元素,单链表插入操作的算法描述,status ListInsert_L( LinkList / ListInsert_L P29 算法2.9,21,课后作业,对

9、照不带头结点和带头结点两种单链表的插入操作，自行分析两种单链表对于删除操作的不同。（书面作业） 说明： 必须要做！ 虽然不讲，但是是考试内容！,2.3.3 链表基本算法实现(1)初始化,生成一个带头结点的空链表,Status InitList_L(LinkList ,23,链表基本算法实现(2)建立单链表,建立链表的过程是一个动态生成的过程： 从空表状态，依次建立各元素结点，并逐个插入,head,步骤： （1）找到单链表的末尾； （2）将新结点插入。,尾插法,方法1：调用基本算法 建立链表；,使用基本算法: void InitList(&L)； void ListInsert(&L, i, e

10、),思想： 1.初始化链表； 2.将结点逐个插入表尾,方法2：自编算法建立,思想： 1.初始化链表； 2.申请一个结点； 3.初始化它的值； 4.结点链入表尾； 5.结束否？ 6.Yes，结束创建操作； 7.No，重复步骤2-6；,尾插法建立单链表算法,25,方法2：尾插法建立单链表,int CreatListR(LinkList / CreatListR,方法1实现：利用基本算法建立链表,LinkList CallFunc_CreatLinkList( ) LinkList L; int i=0; InitList(L); /初始化链表 i=1; scanf( ,输入：67，23，10，45

11、，36,T(n)=O(n) 如果不设last指针，则T(n)=O(n2) 不省心，总要记住表尾。 如何改进？,尾插法建立单链表性能分析,头插法,头插法建立单链表（P30 算法2.11）,void CreatList_L(LinkList CreatList_L,输入：36，45，10，23，67,29,总结：单链表的优缺点,优点 能有效利用存储空间； 用“指针“指示数据元素之间的后继关系，便于进行“插入“、“删除“等操作； 缺点： 不能随机存取数据元素。 同时，还丢失了一些顺序表有的长处，如数据元素在线性表中的“位序”，在的单链表中都“看不见”了。 不便于在表尾插入元素，需遍历整个表才能找到表

12、尾。,30,2.3.4 其他类型的链表(1) 循环链表,在此只讨论带头结点的循环链表,好处：从表中任何结点出发均能找到其他结点 此时，算法的循环条件是?,31,判断链表遍历完否？ p-next=head，则遍历完毕 判断链表空吗？ head-next=head，则链表空 插入或删除结点： 与一般的单向链表相同,循环链表基本操作的实现,33,仅设尾指针的循环链表的应用举例：链表合并,头结点,a1,an,La,头结点,b1,bn,Lb,p, La-next = Lb-next-next ;, p = La - next ;, free(Lb-next);, Lb -next = p ;,34,其他

13、类型的链表(2)双向链表,a1,an,a3,a2,H,typedef int ElemType ; typedef struct DuLNode ElemType data ; struct DuLNode *prior ; struct DuLNode *next ; DuLNode, *DuLinkList ;,p-prior-next=s;,双向链表的插入操作 (常考点),a,x,b,p,s,36,双向链表的删除操作,p,37,小结：顺序表和链表的比较,选用原则 长度已知，且变化不大，则选择顺序表； 长度不定，或变化大，则选用链表。 主要操作的特点 顺序表：插入、删除费时间移动数据， 取

14、数据快速； 链表：插入、删除快速，取数据费时间。,38,方法2：仅保存非0系数项的系数和指数,方法2：改进的顺序表,typedef struct float coef; /系数 int exp; /指数 Poly_node; Poly_node SqPolym+1;,39,方法3：用单链表实现,typedef struct Poly_ListNode float coef; /系数 int exp; /指数 struct Poly_ListNode *next; Poly_ListNode ; Poly_ListNode *SqPoly;,1.若学生记录信息为：学号、姓名、成绩，要求以顺序表实

15、现。请分别以静态存储和动态存储两种形式写出其数据结构描述。,#define ListSize 100 typedef int ElemType; typedef struct ElemType elemListSize; int length; Sqlist;,typedef struct int number; char name10; int score; ElemType;,静态分配存储结构,#define ListSize 100 typedef struct int number; char name10; int score; Student; typedef struct Student elemListSize; int length; Sqlist;,#define ListSize 10