数据结构复习(线性表) 第章第章 绪论绪论一、数据结构研究的内容一、数据结构研究的内容数据结构是指数据以及相互之间的联系。数据结构是指数据以及相互之间的联系。包括：包括：（1）数据的逻辑结构：线性表、树、图。）数据的逻辑结构：线性表、树、图。（2）数据的存储结构：顺序存储、链式结构。）数据的存储结构：顺序存储、链式结构。（3）运算（算法）运算（算法） 三、算法分析（设计）的要求：三、算法分析（设计）的要求： （1）正确性）正确性 （2）可读性）可读性 （3）健壮性）健壮性 （4）高效率与低存储量）高效率与低存储量 二、算法的概念二、算法的概念 算法是解决给定问题的一种方法（策略）。算法是解决给定问题的一种方法（策略）。四、算法的时间复杂性分析四、算法的时间复杂性分析 指算法中各语句执行时间的总和指算法中各语句执行时间的总和 用大用大O O表示。表示。 如：如：T(nT(n)=O(n)=O(n2 2) ) 解释解释：随着随着问题规模问题规模 n 的增大，算法的执的增大，算法的执行时间行时间 T(n)与与n2成正比成正比。O(1) O(log2n) O(n)O(nlog2n)O(n2) O(n3) O(2n) 也即随着也即随着n的增大的增大, f(n)增长较慢的算法为增长较慢的算法为较优较优. 例1-1 分析下列的算法，求T(n). （用大O表示）(1) i=1;j=0; while(i+jj) j+; else i+; T(n)=O(n)(2) x=1; for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k1) y= y*x; n=n1; return y;问题：问题：(1) 该算法的功能是计算该算法的功能是计算 xn 。(2) 该算法的时间复杂度是该算法的时间复杂度是 0(n) 。(3) 若执行一次条件判断和执行一次赋值所需时间相同，若执行一次条件判断和执行一次赋值所需时间相同，都是一个单位时间，则该算法的执行时间等于都是一个单位时间，则该算法的执行时间等于 3n1 个单位时间。个单位时间。（1）顺序存储结构（顺序表）顺序存储结构（顺序表） headk1k2k3 k4a2a3aiana1（2）非顺序存储结构（链表）非顺序存储结构（链表）0 1 2 i n 第章第章 线性表线性表一、线性表的定义一、线性表的定义 n（n=0）个元素的有限集，(a1,a2,a3, an)， 每个元素的位置是线性（一维）的。二、线性表的两种结构二、线性表的两种结构三、顺序表和链表的插入和删除操作三、顺序表和链表的插入和删除操作（1）顺序表的插入和删除顺序表的插入和删除在顺序表的第 i 处插入 1 个结点，有n-i+1个结点后移；删除第 i 个结点有n-i个结点前移。 0 1 2 i n（2）链表的插入和删除）链表的插入和删除a2a3aiana1# #define MAXSIZE 10000define MAXSIZE 10000intint aMAXSIZE+1; aMAXSIZE+1; /* /* 线性表的容量线性表的容量 * */ /intint n; n; /* /* 线性表的表长线性表的表长 * */ /线性表的容量线性表的容量aMAXSIZE+1;线性表的长度线性表的长度int n;四、基于顺序表四、基于顺序表( (数组数组) )的算法设计的算法设计loc(ai) = loc(a1)+(i-1)*len（）（）插入算法设计插入算法设计 输入：长度为输入：长度为n的线性表的线性表a1.an, 插入位置插入位置 i 和插入元素和插入元素 x 输出：在第输出：在第i处插入新元素处插入新元素x后，得到长度为后，得到长度为n+1的线性表的线性表void void list_insertlist_insert( ) ( ) /* /* 在长度为在长度为n n的线性表的线性表a1.na1.n的第的第i i处插入新元素处插入新元素x */x */ intint j; j; if (n=MAXSIZE) error if (n=MAXSIZE) error( (“表满表满”);); else if(in+1)errorelse if(in+1)error( (“ 插入位置错插入位置错”); ); else for (j=n; j=i; j-) else for (j=n; j=i; j-) aj+1= aj+1= ajaj; ; /* /* 元素后移元素后移 * */ / aiai= x; = x; /* /* 在第在第i i处插入处插入x */x */ n+ n+ ；/* /* 表长加表长加1 */1 */ 算法list_insert的时间复杂性 T(n)=O(n)（）删除算法设计（）删除算法设计 输入：长度为输入：长度为n的线性表的线性表a1.an, 删除位置删除位置 i ; 输出：删除第输出：删除第i个元素后，得到长度为个元素后，得到长度为n-1的线性表的线性表 void void list_deletelist_delete( ) ( ) /* /* 删除线性表删除线性表a1.na1.n中的第中的第i i个元素个元素 * */ / intint j; j; if (in) errorif (in) error( (“删除位置错删除位置错”) ;) ; else if (n=0) errorelse if (n=0) error( (“表空表空”) )； elseelse for (j=i+1; j=n; j+) for (j=i+1; j=n; j+) aj-1= aj-1=ajaj; ; /* /* 元素前移元素前移 * */ / n- n- ；/* /* 表长减表长减1 */1 */ 算法list_delete的时间复杂性 T(n)=O(n)structstruct node node elemtypeelemtype data; data; /*/*数值域数值域数值域数值域* */ / structstruct node *next; node *next; /*/*指针域指针域指针域指针域* */ / ; ; typedef struct node node; head : 指针变量,存储第一个结点的地址五、基于链表的算法设计五、基于链表的算法设计（）查找（定位）算法设计（）查找（定位）算法设计 1. 1. 功能功能 在链表中查找（定位于）第在链表中查找（定位于）第i i个结点，若存在，个结点，若存在，则返回该结点的地址，否则，返回空（则返回该结点的地址，否则，返回空（NULLNULL）。）。 2. 2. 算法思想算法思想 从第一个结点开始，逐个查找（从第一个结点开始，逐个查找（后移）并计数，后移）并计数，直到第直到第i i个结点止。个结点止。3. 3. 算法设计算法设计node *node *loc(nodeloc(node *head, *head, intint i) i) /*head: /*head:带头结点的单链表的头指针，该算法定位于表中的第带头结点的单链表的头指针，该算法定位于表中的第i i个结点个结点* */ / node *p=head; node *p=head; /*/*指针初始化指针初始化, p, p指向头结点指向头结点* */ / intint j=0; j=0; /* j/* j为计数器，初值为为计数器，初值为0*/0*/ while (p!=NULL)&(ji) while (p!=NULL)&(jnext; p=p-next; j+; j+; /* /* p p后后移移，j j计计数数,p,p移移至至第第i i个个结结点点止止 * */ / return (p); return (p); /* p/* p指向第指向第i i个结点（返回第个结点（返回第i i个结点的地址）个结点的地址）* */ / 算法Loc的时间复杂性 T(n)=O(n)(2)(2)插入算法设计插入算法设计1. .功能：在线性表第功能：在线性表第i i处插入其数值为处插入其数值为x x新结点。新结点。 2.2.算法思想：算法思想： 首先，找到第首先，找到第i-1i-1个结点（个结点（p p指向第指向第i-1i-1个结点）；个结点）；然后，在然后，在p p结点之后插入值为结点之后插入值为x x新结点新结点q q。在结点在结点p p之后插入新结点之后插入新结点q:q: 头结点头结点的作用的作用q-next=p-next;P-next=q;3.3.算法设计算法设计void void ins(nodeins(node *head, *head, intint i, i, elemtypeelemtype x,nodex,node *q *q) ) /* head: /* head:带头结点的单链表的头指针，该算法在第带头结点的单链表的头指针，该算法在第i i个结个结 点后面插入其数值为点后面插入其数值为x x新结点新结点q*/q*/ node *p; node *p; p=loc(head,i-1); p=loc(head,i-1); /* /* 令令 p p 指向第指向第i-1i-1个结点个结点 if (p!=NULL)if (p!=NULL) q-next=p-next; p-next=qq-next=p-next; p-next=q; ; /* /*在在p p结点之后插入值为结点之后插入值为x x新结点新结点q q * */ / 算法ins的时间复杂性 T(n)=O(n)(3)(3)删除算法设计删除算法设计 1. .功能：删除第功能：删除第i i个结点。个结点。 2.2.算法思想：算法思想：首先，找到第首先，找到第i-1i-1个结点（个结点（p p指向第指向第i-1i-1个结点）；个结点）；然后，删除然后，删除p p的下一个结点。的下一个结点。3.3.算法设计算法设计void del (node* head, int i, elemtype *e) /* /* head:head:带带头头结结点点的的单单链链表表的的头头指指针针，删删除除表表中中的的i i个个结结点点，并并将将结结点的值回带（点的值回带（* *e e）* */ / node *p=head; node *p=head; /* /* 指针初始化指针初始化 * */ / intint j=0; j=0; /* /* j j为计数器为计数器 * */ / while (p-next!=NULL & jnext!=NULL & jnext; j+; p=p-next; j+; /*/*寻找第寻找第i-1i-1个结点个结点(p)*/(p)*/ if ( p-next!=NULL & j=i-1 ) if ( p-next!=NULL & j=i-1 ) q=p-next; q=p-next; /*q/*q指向指向p p的下一个结点的下一个结点( (即第即第i i个结点）个结点）* */ / p-next=q-next; p-next=q-next; /*/*删除第删除第i i个结点个结点* */ / *e=q-data ; *e=q-data ; /*/*保留第保留第i i个结点的值个结点的值 * */ / free(qfree(q) ; ) ; 例2-1 线性表有8000个数据元素，若采用顺序存储(一维数组），第一个结点的地址为1000，每个结点的值需占用8个存储单元。问 （1） 该线性表需要多大的存储空间？ （2）第113个结点的起始地址是多少？ （3）在线性表的第 34 处插入一个新元素，有多少个元素向后移动?六、示例六、示例例例2.12.1设线性表存于整型数组设线性表存于整型数组 a1.MAXSIZEa1.MAXSIZE的前的前n n个分量中个分量中 且递增有序且递增有序, , 将将x x插入到线性表的适当位置。插入到线性表的适当位置。 void ins( ) void ins( ) intint i; i; if if （nMAXSIZEn=1 & x=1 & x0 & 1=i & i+k-10 & 1=i & i+k-1=n ) for (j= for (j=i+ki+k; j=n; +j); j=n; +j) aj-kaj-k=aj; =aj; /* /* 前移前移k k个元素，将个元素，将k k个元素一次删除个元素一次删除 * */ / n - = k; n - = k; /* /* 表长表长k k */ */ 思考：算法的选择及效率思考：算法的选择及效率（1）每次删除）每次删除1个元素，做个元素，做k次次（2）一次将）一次将k个元素全部删除个元素全部删除例例2.32.3 已知线性表存于已知线性表存于a1.MAXSIZEa1.MAXSIZE中的前中的前n n个分量个分量 中，写一算法删除表中所有值为中，写一算法删除表中所有值为0 0的元素（将非的元素（将非 0 0元素移到前面来），各元素间的相对位置不变。元素移到前面来），各元素间的相对位置不变。void del_0( ) /* 删除所有值为删除所有值为0的元素的元素 */ i=1; while(i=n)&(ai!=0) i=i+1; /* 找到第找到第1个值为个值为0的结点的结点 */ for(j=i+1;jnext!=NULL & p-next-data!=x)while (p-next!=NULL & p-next-data!=x) p=p-next; p=p-next; /*/*寻找表中值为寻找表中值为x x的结点的结点(p-next=x)*/(p-next=x)*/ if ( p-next!=NULL) if ( p-next!=NULL) q=p-next; q=p-next; /*q/*q指向指向p p的下一个结点的下一个结点( (即值为即值为x x的结点）的结点）* */ / p-next=q-next; p-next=q-next; /*/*删除值为删除值为x x的结点的结点* */ /free(qfree(q) ; ) ; 例2.5 已知线性表中的元素按值递增排列已知线性表中的元素按值递增排列, , 并以单链表作并以单链表作存储结构。写一高效算法存储结构。写一高效算法, , 删除表中所有值大于删除表中所有值大于minmin且小且小于于maxmax的元素（若表中存在这样的元素）。的元素（若表中存在这样的元素）。分析：分析：算法设计算法设计 ：void void del_min_max(nodedel_min_max(node * *head,inthead,int min,intmin,int max) max) /* head:/* head:带头结点的单链表的头指针带头结点的单链表的头指针 * */ / node *q=head, *p=head-next; /* node *q=head, *p=head-next; /*初值初值* */ / while (p!=NULL & p-datadatanext; q=p; p=p-next; /* /* 直至直至p p指向其值指向其值minmin的结点止的结点止, q, q是是p p的前趋的前趋* */ / while (p!=NULL & p-datadatanext; delete u ; u=p; p=p-next; delete u ; /* /* 删除所有的其值删除所有的其值minmin并且并且maxnext=p; q-next=p; /* del_1*/ /* del_1*/