chap2-课件-1.ppt

顺序结构线性表的删除算法 在表长为n的线性表中删除第i个数据元素（通常还需将第i+1个至第n个元素向前移动一个位置） int Delete_list(int i, Element s[] , int *n_pointer) { int j,n; n=*n_pointer; if ((i1)||(in)) return (0); for (j=i+1; j=n; j++) s[j-1]=s[j]; n--; *n_pointer=n; return (1); } 插入算法花费的时间，主要在于循环中元素的后移（其它语句花费的时间可以省去），即从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，当插入位置i=１时，全部元素都得移动，需n次移动，当i=n+１时，不需移动元素，故在i位置插入时移动次数为n-i+1，假设在每个位置插入的概率相等为 ，则平均移动元素的次数为 = 故时间复杂度为O(n)。 同理，可推出删除运算的平均移动次数为 ， 故时间复杂度为O(n)。 顺序结构线性表的查找算法 在线性表中查找关键字为x的元素，并返回位置。 int Locate_list(Element s[], int n, int x) //n为线性表长度 { int i; for (i=1; i=n; i++) if (s[i]==x) return (i); return (-1); } 线性表的链式存贮结构，也称为链表。其存贮方式是： 在内存中利用存贮单元（可以不连续）来存放元素值及它在内存的地址; 各个元素的存放顺序及位置都可以以任意顺序进行； 逻辑相邻的元素存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址（指针）才能实现。 故不能像顺序表一样可随机访问，而只能按顺序访问。常用的链表有线性链表（单链表）、循环链表和双向链表等。 3．线性表的链式表示和实现 (1）线性链表(单链表):链式存储的线性表 结点除信息域外还含有一个指针域，用来指出其后继结点的位置 最后一个结点没有后继结点，指向它的指针域为空(记为NIL 或∧)。另外还需要设置一个头指针head，指向单链表的第一个结点，如下图示： 链表的重要特点是：插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可。 插 入 删 除 单链表(的结点)的C语言描述 typedef struct Linear_chain_node { Element data; struct Linear_chain_node *link; } NODE; 或者： struct Linear_chain_node { Element data; struct Linear_chain_node *link; }; typedef struct Linear_chain_node NODE; 结点的表示 a b c d 100 218 165 333 p p=? p-data=? p-link=? (p-link)-data=? (p-link)-link=? 1）建立单链表（算法） 创建有n个结点的单链表，结点数值从键盘输入，函数返回链表的 头结点(算法中将已将结点的数值域简化为int简单类型)。 NODE *Create_single_chain (int n) { NODE *head, *p, *q; int i; p=(NODE *)malloc(sizeof(NODE)); p-data=0; p-link=NULL; head=p; for (i=1;i=n;i++) { q=(NODE *)malloc(sizeof(NODE)); scanf(“%d”,q-data); q-link=NULL; p-link=q; p=q; } return (head); } 带头结点的单链表 0 2）查找单链表结点（算法） NODE *Found(NODE *head, int x) { NODE *p; p=head; while