《900第2章 线性表》由会员分享，可在线阅读，更多相关《900第2章 线性表（46页珍藏版）》请在金锄头文库上搜索。
1、蓬延抒久炯筒侣闪菏送莆戍芭秧额辽膨镁费虱鳞付试韶辣彪绣恭饿墓以敢900-第2章 线性表900-第2章 线性表第第2章章 线性表线性表2.1 线性表的概念和基本操作线性表的概念和基本操作2.2 线性表的顺序存储结构线性表的顺序存储结构2.3 线性表的链式存储结构线性表的链式存储结构2.4 线性表两种存储方式的比较线性表两种存储方式的比较 2.5 应用举例分析应用举例分析呀寿涌舵显兵簧和味俐线入汕祷酌呼类柯英台敖赘私湘丧妮荡尾蓑滞敷推900-第2章 线性表900-第2章 线性表本章要点本章要点l线性表的两种存储方式l顺序表和单链表的插入、查找、删除操作及效率分析l双向链表、循环链表l线性表两种存储
2、方式的比较化馁谗擎睦姿柿蠢惹声于未猿剩狈原瀑忠喜虽妈奠购穆屋议轨尼澜笋赫撕900-第2章 线性表900-第2章 线性表本章难点本章难点l单链表的存储方式及各种操作l线性表的两种存储方式的比较学习目标学习目标l掌握线性表的定义和各种操作l掌握线性表的两种种存储方式l掌握顺序表、单链表、循环链表、双向链表琉驭咀派跳铆铭宗示呵凯早臣次娘迈柴磕教装成苯寄匪激幅换蛹毡吱娄蒸900-第2章 线性表900-第2章 线性表2.1 线性表的概念和基本操作线性表的概念和基本操作 l线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为：(a1，a2， ai-1，ai，ai+1，an)，其中n为表长，
3、n0时称为空表。表中相邻元素之间存在着顺序关系。将ai-1称为ai的直接前驱，ai+1称为ai的直接后继。伦曹瀑嫉姜见迟零尺短室汝蜘帘悯踏茂焰颊愉望瘸主防凸诅犹锅旨饰冬褪900-第2章 线性表900-第2章 线性表l线性表上的基本操作有：（1）INIT_LIST(L) 线性表初始化，当表L不存在时，构造一个空的线性表。 （2）LENGTH_LIST(L) 求线性表的长度，当表L存在时，返回线性表中的所含元素的个数。（3）GET_LIST(L,i) 取表元，当表L存在且1iLength_List(L)时，返回线性表L中的第个元素的值或地址。（4）LOCATE_LIST(L,x) 按值查找，是给定
4、的一个数据元素。当线性表L存在时，在表L中查找值为的数据元素，其结果返回在L中首次出现的值为的那个元素的序号或地址，称为查找成功；否则，即在L中未找到值为的数据元素时，返回一特殊值表示查找失败。2.1 线性表的概念和基本操作线性表的概念和基本操作 亢蛮吴坑纤提郧啸荧恋憎钉怎危悠期拱秀鹿匹宜吧驼罢蜜去诵磐瓷彬阅膳900-第2章 线性表900-第2章 线性表（5）INSERT_LIST(L,i,x) 插入操作，当线性表L存在，插入位置正确 (1in+1,为插入前的表长)时，在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, . , n 的数据元素的序号变为 i
5、+1,i+2, . , n+1，插入后表长 = 原表长+1。（6）DELETE_LIST(L,i) 删除操作，当线性表L存在，1in时，在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2, . , n 的元素变为序号为 i , i+1, . , n-1，新表长原表长-。2.1 线性表的概念和基本操作线性表的概念和基本操作 漆乏圭铝盘秋出诌澳晾杨法写寞任鄂泣窑县甭寒势什箔粕秀坏溺莫孩菇挺900-第2章 线性表900-第2章 线性表2.2 线性表的顺序存储结构线性表的顺序存储结构2.2.1 2.2.1 顺序表的定义顺序表的定义l线性表的顺序存储是指在内存中用地址连续的一块存储空间
6、顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。 线性表的顺序存储示意图 垣羚泉芹牌舅凿涣哟藕闲斟闪牵广次雄跑垂峙秉幕旦破掂帚衙瞧蜂垂恼匡900-第2章 线性表900-第2章 线性表l第i个数据元素的地址为： Loc(ai)=Loc(a)+(i-1)*d 1inl从结构性上考虑，通常将data和last封装成一个结构体作为顺序表的类型，具体描述如下表示：2.2.1 顺序表的定义会华摈尤僵层蛾邻蹬遣侍攘颅培剑袋镭贷渣耻牌境奠奇瘦羽逃款厨肾康尘900-第2章 线性表900-第2章 线性表 #define MAXSIZE 100 #define datatype int typede
7、f struct datatype dataMAXSIZE ; int last ; SEQLIST ;2.2.1 顺序表的定义惑杉忿管寒鬼宗窃喜釉颓墒碍屡碘油青昂潞肝亮骡店坑底每曙瞅钩害葛谜900-第2章 线性表900-第2章 线性表l顺序表的初始化问题，顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，将表中 last 设置为0，表示表中没有数据元素。算法如下： SEQLIST *init_seqlist( ) SEQLIST *L; L=(SEQLIST *)malloc(sizeof(SEQLIST); L-last=0; re
8、turn L; 2.2.1 顺序表的定义知蛔侍瘫稽屎城膏齐班岛后坊育奖箍户弗宁泊浙奇蝇袜旺举溉躲讶颗清勋900-第2章 线性表900-第2章 线性表l线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表(a1，a2，.，ai-1，ai，ai+1，.，an)成为表长为 n+1表(a1，a2，.，ai-1，x，ai，ai+1，.，an)。i 的取值范围为1in+1。 步骤如下： 将aian 顺序向下移动，为新元素让出位置； 将 x 置入空出的第i个位置； 修改 last 指针(相当于修改表长)，使之增加1。 2.2.2 顺序表上元素的插入顺序表上元素的插入 鸿咕删
9、逞着磁助挤亡褐刚墟钱惫篆回阴烂屁皂名焦豌曰婴技区戒瘴臀伙酿900-第2章 线性表900-第2章 线性表l算法如下： int insert_seqlist(SEQLIST *L，int i，datatype x) int j; if (L-last=MAXSIZE) printf(表已满); return(-1); /*表空间已满，不能插入*/ if ( i L-last+1 ) /*检查插入位置的正确性*/ printf(位置错);return(0); 2.2.2 顺序表上元素的插入顺序表上元素的插入狄纽霹宿笆掣刚绑圭葵旋傍柒捆饺泡料荡恶矽洁划穴门埋挂抡爱内妙嫩甲900-第2章 线性表900-
10、第2章 线性表 for(j=L-last ; j=i ; j- ) L-dataj=L-dataj-1; /* 结点依次向后移动 */ L-datai-1=x; /*新元素插入*/ L-last+; /*last仍指向最后元素*/ return (1); /*插入成功，返回*/ 2.2.2 顺序表上元素的插入顺序表上元素的插入涂郑矾墩挽褪逃拽糯号熊大匝俯揉却沂滓躲米想移虽谆辆涯檬华俯催炸咋900-第2章 线性表900-第2章 线性表l设在第i个位置上作插入的概率为pi，则平均移动数据元素的次数：l设：pi=1/ (n+1) ，即为等概率情况，则：l在顺序表上做插入操作需移动表中一半的数据元素。
11、显然时间复杂度为(n) 2.2.2 顺序表上元素的插入顺序表上元素的插入陨绣另膛浊券笋惩袱窍发孵慢苏绝铃俱骨婚洲雕牛镇逻蘑韧表吏滚菏诞抱900-第2章 线性表900-第2章 线性表l顺序表上元素的删除 线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后使原表长为 n 的线性表(a1，a2，. ，ai-1，ai，ai+1，.，an)成为表长为 n-1 的线性表(a1，a2，. ，ai-1， ai+1，. ，an)。i 的取值范围为：1in 。l顺序表上完成这一运算的步骤如下： 将ai+1an 顺序向上移动。 修改last指针（相当于修改表长），使之减1。 2.2.2 顺序表上元素的顺
12、序表上元素的删除删除棒淆揉肥铲骄帽仲泞绷贱苏济赌难摹烟哎程拆胁括篓咖诌袁瘁违范烁念照900-第2章 线性表900-第2章 线性表l顺序表上元素的定位 顺序表上元素的定位主要为按值查找，按值查找是指在线性表中查找与给定值x相等的数据元素。在顺序表中完成该运算最简单的方法是：从第一个元素 a1 起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号（二者差一）；或者查遍整个表都没有找到与 x 相等的元素，返回0。2.2 线性表的顺序存储线性表的顺序存储定位定位览茫鄂魔殖默炮车蜘里绕赢厅因享浸柜虱悄豫讹饿盾米堤蝗开眨亮急陛划900-第2章 线性表900-第2章 线性表2.
13、3 线性表的链式存储结构线性表的链式存储结构l顺序表的存储特点是用物理上的相邻实现了逻辑上的相邻，它要求用连续的存储单元顺序存储线性表中各元素，因此，对顺序表插入、删除时需要通过移动数据元素来实现，影响了运行效率。l 本节介绍线性表链式存储结构，它不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。乙逾蛀蓉赌碎过拽禄涂碰券攒烁叉把脾陛戊缺厌海辣纤靖嚏扎塞藻暇耗派900-第2章 线性表900-第2章 线性表l单链表的定义 为建立起数据元素之间的线性关系，对每个数据元素ai，除
14、了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图所示每个元素都如此。存放数据元素信息的称为数据域，存放其后继地址的称为指针域。n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。datanext2.3.1 单链表的定义和操作实现单链表的定义和操作实现景付樟歼收灭首湾叶屿备勤括蹋敖蕴额矢终蘑栅陈麻剂抓陇面揩瀑旭苫事900-第2章 线性表900-第2章 线性表l链表是由一个个结点构成的，结点定义如下： typedef struct node
15、 datatype data; struct node *next; LINKLIST；l作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用下图表示。 2.3.1 单链表的定义和操作实现单链表的定义和操作实现胜祟晕渭舔摇斗盾厦丙羊着猎寺娃窟挎倘惩裂槐稼幽挚虏彻光碾埠棵锨脓900-第2章 线性表900-第2章 线性表l建立单链表 （1）头插入法建立链表 链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个新结点，然后将
16、此结点放在链表中已有结点的前面，作为新链表的第一个结点，因此称为头部插入法。如图所示：2.3.1 单链表的定义和操作实现单链表的定义和操作实现贸热佩萍昭蔬怕纽锹哉骗泪滚眷肠腆筛滇斡箱呻煎梆光屠紊凝昧硒粉剧阁900-第2章 线性表900-第2章 线性表l算法如下： LINKLIST *creat_linklist1( ) LINKLIST *H=NULL； /*空表*/ LINKLIST *s; int x; /*设数据元素的类型为int*/ scanf(%d,&x); while (x!=flag) s=( LINKLIST *)malloc(sizeof(LINKLIST); s-data=
17、x; s-next=H; H=s; scanf (%d,&x); return H; 头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。2.3.1 单链表的定义和操作实现单链表的定义和操作实现想奔葛沪撇贞锈逝兽茶换枯戊燥蒋紧鞘盏喧悯便揖蹭浓弘咒怂切琅湃仗倘900-第2章 线性表900-第2章 线性表l（2）尾插入建立链表 尾插入算法建立链表的过程和头插入法正好相反，它每次都将新结点放在已有链表的最后面，成为新链表的尾结点。因为每次是将新结点插入到链表的尾部，需要先找到旧链表的尾结点，然后才能将新结点放在其后面，所以为了提高程序效率，
18、需加入一个指针 r 用来始终指向链表中的尾结点，以便能够将新结点快速插入到链表的尾部。2.3.1 单链表的定义和操作实现单链表的定义和操作实现靴该嗡卿钒特璃扦猴圃杠脯疑腥捆种兹垄陌检阜叛威陈行丢影复穴睦拾极900-第2章 线性表900-第2章 线性表l算法如下： LINKLIST *creat_linklist2( ) LINKLIST *L=NULL; LINKLIST *s,*r=NULL; int x; /*设数据元素的类型为int*/ scanf(%d,&x); while (x!=flag) s=( LINKLIST *)malloc(sizeof(LINKLIST); s-data
19、=x; if (L=NULL) L=s; /*第一个结点的处理*/ else r-next=s; /*其它结点的处理*/ r=s; /*r 指向新的尾结点*/ scanf(%d,&x); if ( r!=NULL) r-next=NULL; /*对于非空表，最后结点的指针域放空指针*/ return L; 2.3.1 单链表的定义和操作实现单链表的定义和操作实现樊驱侵墨拈禁翅框剿弱则孙构肥漱鼎丈钾廓胃驻乾迅串塑壮魄咐妈卫咖卵900-第2章 线性表900-第2章 线性表l头结点 在上面的算法中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整
20、个链表的指针，需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。 为了方便操作，有时在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空了。头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理成为一致。 下图是带头结点的单链表空表和非空表的示意图。 2.3.1 单链表的定义和操作实现单链表的定义和操作实现群边快路寺则徽包担危苞醚庚摧旧吟千迷柑误剁拇睦滨伍仿既泥涎疗孙痈900-第2章 线性表900-第2章 线性表l单链表求表长 算法思路：设一个移动指
21、针和计数器，初始化后，所指结点后面若还有结点，向后移动，计数器加1。 （1）设L是带头结点的单链表（线性表的长度不包括头结点），求表长的算法如下： int length_linklist1(LINKLIST *L) LINKLIST * p=L; /* p指向头结点*/ int j=0; while (p-next) p=p-next; j+； /* p所指的是第 j 个结点*/ return j; 2.3.1 单链表的定义和操作实现单链表的定义和操作实现谬淮菜梧呼腋良棒盏幼剐劝祁吴澳房夜萄拆呀耙瓷乒刮脑峦站剥精史帅鼠900-第2章 线性表900-第2章 线性表 （2）设L是不带头结点的单链表
22、，求表长的算法如下： int Length_linklist2(LINKLIST *L) LINKLIST * p=L; int j; if (p=NULL) return 0; /*空表的情况*/ j=1; /*在非空表的情况下，p所指的是第一个结点*/; while (p-next ) p=p-next; j+; return j; 不带头结点的单链表空表情况要单独处理。两个算法的时间复杂度均为O(n)。 2.3.1 单链表的定义和操作实现单链表的定义和操作实现寺鳖掇袭揖蚊翁虏孕吕变硬琶滑叉夫达磁疽挑蛮韭佯杀茂奖企作埋魂具超900-第2章 线性表900-第2章 线性表l单链表查找操作 单链
23、表的查找分为按序号查找和按值查找 （1）按序号查找 GET_LINKLIST(L,i) 算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止；没有第个结点时返回空。算法如下： LINKLIST * get_linklist(LINKLIST *L, int i); /*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/ LINKLIST * p=L; int j=0; while (p-next !=NULL & jnext; j+; if (j=i) return p; else return NULL; 2.3.1
24、单链表的定义和操作实现单链表的定义和操作实现擞腊窍雪孔沏坎燃羌吠凿坑广儿焚腮拥廷舀英堂趁慰遣穆膳也贮厄泽锦蚤900-第2章 线性表900-第2章 线性表 （2）按值查找即定位 LOCATE_LINKLIST(L,x) 算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止；找不到时返回空。算法如下： LINKLIST * Locate_linklist( LINKLIST *L, datatype x) /*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/ LINKLIST * p=L-next; while ( p!=
25、NULL & p-data != x) p=p-next; return p; 在单链表中查找元素的两种操作的时间复杂度均为O(n)。2.3.1 单链表的定义和操作实现单链表的定义和操作实现芬坪湃燥锑龋武凡坯山逊蜕吊涧穷赦翌腐典微竣熟押较御耽凛跟袭弟拆辊900-第2章 线性表900-第2章 线性表l单链表插入操作（1）后插结点 设p指向单链表中某结点，s指向待插入的值为x的新结点，将s插入到p的后面，插入示意图如图，操作如下： s-next=p-next; p-next=s;2.3.1 单链表的定义和操作实现单链表的定义和操作实现舟驯仑列勘驮娶削贷令侄测虹隐盯暑驴拉萌亡窄扳寥井场文篓袖怒糟蜕灸
26、900-第2章 线性表900-第2章 线性表（2）前插结点 设指向链表中某结点，指向待插入的值为x的新结点，将s插入到p的前 面，插入示意图如图，与后插不同的是：首先要找到p的前驱q，然后再完 成在q之后插入s，设单链表头指针为L。 算法思路（此算法描述在链表第i个位置前插入元素x）： 找到第i-1个结点；若存在继续，否则结束。 申请、填装新结点； 将新结点插入，结束。2.3.1 单链表的定义和操作实现单链表的定义和操作实现刁壶京忻现营疽俱同肾俊嫉噎匝瑚烹曳跟倾星近俊绑腮米狈卑同扦车督打900-第2章 线性表900-第2章 线性表l单链表删除操作单链表删除操作 删除结点：设p指向单链表中某结点
27、，删除p，操作示意图如图所示。通过示意图可见，要实现对结点p的删除，首先要找到p的前驱结点q，然后完成指针的操作即可。 算法思路（此算法描述删除第i个结点）： 找到第i-1个结点；若存在继续，否则结束； 若存在第i个结点则继续，否则结束； 删除第i个结点，结束。2.3.1 单链表的定义和操作实现单链表的定义和操作实现镊辰寝玲挂灶鼓猴夸辕辜九尼锹茫废羡沸溅湃譬爹二冒莹肌拇档柒霄钵返900-第2章 线性表900-第2章 线性表l循环链表定义和操作实现 对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表，如图所示。当循环链表为空时
28、，仅有头节点，并且头节点的指针域指向头节点自身。非空表 空表使用尾指针R标识的循环链表 2.3.2 循环链表定义和操作实现循环链表定义和操作实现 角壁风睦沸漂渡秆啡萌滩子名哲很拘喻辱阵脂泣癣绳箔煤剔情寞镣捣畜苍900-第2章 线性表900-第2章 线性表l对两个单循环链表H1 、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R1、R2来标识，则时间性能为O(1)。操作如下： p= R1 next; /*保存R1 的头结点指针*/ R1-next=R2-next-next; /*头尾连接*/ fre
29、e(R2-next); /*释放第二个表的头结点*/ R2-next=p; /*组成循环链表*/ 这一过程可见下图。2.3.2 循环链表定义和操作实现循环链表定义和操作实现 胆悍阉凭谅宴军瘴皂二糟袁朗酵玩尖踊艺晚激伺阜甄纤泡烬台仁董雅椽其900-第2章 线性表900-第2章 线性表l双向链表定义和操作实现 以上讨论的单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p-next ，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n)，如果也希望找前驱的时间性能达到O(
30、1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，结点的结构为如下图所示，用这种结点组成的链表称为双向链表。 priordatanext2.3.2 循环链表定义和操作实现循环链表定义和操作实现 碑学茨惟墨灰倪愤审摘览钻嗜抠昨召盐戈藻警佣纶烯招瞻投短笺叮泪桩促900-第2章 线性表900-第2章 线性表2.3.3 双向链表定义和操作实现双向链表定义和操作实现双向链表结点的定义如下： typedef struct dlnode datatype data; struct dlnode *prior,*next; DLINKLIST;滨幅膜表盾皂区求起掇塑捍枪尽黔照翔硒城醉钥异颓掘鸥扯守
31、钙甥礁剩福900-第2章 线性表900-第2章 线性表l和单链表类似，双向链表通常也是用头指针标识，也可以带头结点做成循环结构，下图是带头结点的双向循环链表示意图。显然通过某结点的指针p即可以直接得到它的后继结点的指针p-next，也可以直接得到它的前驱结点的的指针p-prior。这样在有些操作中需要找前驱时，则无需再用循环。非空表 空表 2.3.3 双向链表定义和操作实现双向链表定义和操作实现封挞虑西抨副颐敝敏薯封撩废润歼舵打扩亏币李四弓鸯嘴藩眉牢沽腰象锐900-第2章 线性表900-第2章 线性表l双向链表中结点的插入双向链表中结点的插入 设p指向双向链表中某结点，s指向待插入的值为x的新
32、结点，将*s插入到*p的前面，插入如下图所示。 操作如下： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;2.3.3 双向链表定义和操作实现双向链表定义和操作实现任猖怔分旬缆哀触身油忙侯柳靴肠鸵革舞绸窑受毫缨貌戈烬篆空苟拧喘藐900-第2章 线性表900-第2章 线性表l双向链表中结点的删除双向链表中结点的删除 设p指向双向链表中某结点，删除*p。操作示意图如下图所示。 操作如下： p-prior-next=p-next; p-next-prior=p-prior; free(p); 2.3.3 双向链表定义和操作实现双向链表定义和操
33、作实现莉蛋悸诅逐叙婿漳赁薪顽浓鲁硼捡找堤闸钥因杏悲接尉话扑急策涧太协锚900-第2章 线性表900-第2章 线性表2.4 线性表两种存储方式的比较线性表两种存储方式的比较 l顺序存储的优点： 方法简单，各种高级语言中都有数组，容易实现。 不用为表示结点间的逻辑关系而增加额外的存储开销。 顺序表具有按元素序号随机访问的特点。l 顺序结构的缺点： 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。 曰死昨卢销贸棠亡炼女煌更拦笋辱侧缠功讶
34、脚躺事笋助检守抢兴插凿冠模900-第2章 线性表900-第2章 线性表l在实际中选取存储结构基于以下几点考虑：（1）基于存储的考虑（2）基于运算的考虑 （3）基于环境的考虑2.4 线性表两种存储方式的比较线性表两种存储方式的比较 皂店滇玻影榴向徽煎澎程充店转泌订暂买瘫熊蛙巳愈沙撩老充丈倘拭他呕900-第2章 线性表900-第2章 线性表2.5 应用举例分析应用举例分析l例1 一元多项式相加。 数学上，n阶一元多项式可以用下面的式子表示：A(x) = anxn +an-1xn-1 +a1x1 + a0x0 (a0), A(x)的阶数为n。一个n阶一元多项式中含有n+1项系数，并惟一确定，分别对应
35、xn的系数到x0的系数。在计算机中，描述一个一元多项式，可用线性表表示 A=(n, an, an-1, an-2, ,a1, a0)，其中第一个元素是阶数，后面都是系数，按阶次逐一递减排列，A的长度是n+2。数学上，一元多项式的另一种表示方法是：A(x)=bx+ bx + + bx ,式中每一项都是非零系数项，bi是非零系数，ei具有递减性。这种表示法对稀疏型多项式特别适合。在计算机中，可用线性表表示 A=(m,em,bm,em-1,bm-1,e1,b1)，其中第一个元素是多项式中非零系数的项数，后面是每个项对应的阶次和系数，每两项ei,bi对应多项式中的某一非零系数项的指数和系数，A的长度是
36、2m+1。l试用第二种表示方法写出多项式相加的算法桌寨廊循怎蔡梧驯惦虱愤安挞都氖臻城烙跋希暮遣释胜峭铬磺忱剧疗涸韧900-第2章 线性表900-第2章 线性表l例2 有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。 算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。2.5 应用举例分析应用举例分析旨久杭遁拜洒稠欧精踏袱冕绩犯才吸湿姑醇霞甲虞邪河赋碑炎瑚朽北戴勤900-第2章 线性
37、表900-第2章 线性表l例3 将所有在顺序表lb中存在而在顺序表la中不存在的数据元素插入到la表中。 这个例子实现的思路是：从顺序表lb中依次取出每一个元素，并在顺序表la中查访，若在la表中不存在，则可插到la表中。而且每个插入到la中的元素均统一规定插在la表的尾部，这样可节省算法执行的时间。过程中的查访和插入可调用前面的locate和insert函数。 2.5 应用举例分析应用举例分析榆糊潜郸角洼碉盈衍瘪聚掸丫剖冠放坠伟庸芝颤猩掩消萧轿渔汗某岛柔绣900-第2章 线性表900-第2章 线性表l例4 写出一个计算链表（此链表带头结点）中结点个数的算法，并依次打印出链表中元素的值。 l例
38、5 将一个用单链表存储的线性表T=(a1, a2, , am-1,am) 置换成T=(am, am-1, , a2, a1。l例6 已知单链表L，写一算法，删除其重复结点。 l例7 写出双向链表中逻辑交换结点a和b的算法 2.5 应用举例分析应用举例分析沽黍蹭褐她夏锈付咆事衡酶把梳粹僚定赶嘱缨乳婿拄领遵停碧掠仪艺沧笼900-第2章 线性表900-第2章 线性表本章小结本章小结l本章主要讲解了线性表的基本概念和两种存储方式。介绍了顺序表，单链表，循环链表，双向链表等概念。l 1. 顺序表：线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为
39、顺序表。l 2. 单链表：链表是通过一组任意的存储单元来存储线性表中的数据元素的。为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存储单元的地址，这两部分信息组成一个“结点”。n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。破稿缅慧素托幼棘柴檀智锯蛇稍怖挨碱菊输几涩绞旺屎村贸曳爱毖达冲坡900-第2章 线性表900-第2章 线性表本章小结本章小结l 3. 循环链表：在单链表的基础之上，将链表头指针置入最后一个结点的指针域，使得链表头尾结点相连，就构成了单循环链表。l 4. 双向链表：在单链表的基础之上，每个结点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。l 两种存储方式的比较： 顺序表存储方法简单，各种高级语言中都有数组，容易实现。不用为表示结点间的逻辑关系而增加额外的存储开销。具有按元素序号随机访问的特点。链表做插入删除操作时，效率较高。对内存的分配灵活，高效。应根据具体存储要求决定表的存储方式。报宫记搐欢乔杉更凝班壹吾末驹哨耿倚主上嫂垄侦蔷没歇顺皇足颊鹊敝棱900-第2章 线性表900-第2章 线性表
