线性结构的特点在数据元素的非空有限集中存在唯.ppt

线性结构的特点：在数据元素的非空有限集中，（1）存在唯一的一个被称为“第一个”的数据元素（2）存在唯一的一个被称为“最后一个”的数据元素（3）除第一个之外，集合中的每个数据元素均只有一个前驱（4）除最后一个之外，集合中的每个数据元素均只有一个后继第二章 线性表酌慈近膳次咀巳鸡缘痈访岿丑便沂篷旧糯苹镀类颜撩度兜平篙第装教狰倪线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯“线性表”简称为表，是零个或多个元素的有穷序列，通常可以表示成k0，k1,　…，kn-1　（n≥1）表中所含元素的个数称为表的“长度长度”长度为零的表称为“空表空表”表中的元素又称“表目表目”线性表中的数据元素在不同的情况下可以有不同的具体含义，它可以是一个数、一个符号，也可是其它更复杂的信息  2.1 线性表的概念中腹营嫩参行娘娩疼泡佣射击概这孪恫腮鄂脓贴瑰休朝售途框襄蚁贮蝇寺线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯通常线性表有以下几种基本运算：1. 性表中插入一个元素；2. 性表中删除某个元素；3. 性表中查找某个特定元素；4. 性表中查找某个元素的后继元素；5. 性表中查找某个元素的前驱元素；6. 创建空线性表；7. 判别一个线性表是否为空表。

……由上面的基本运算还可以构成其它较为复杂的运算，如创建线性表线性表的基本运算个臆娜鼻卡掺暑我泡焊慧蹭漱撤那饲侗悔崭互臻砂颂硼蠢资粒沿噎中届育线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯#include #include /* 符号常量 */#define MAXNUM100    /* 线性表空间大小 */#define FALSE0#define TRUE1#define SPECIAL2147483647  /* 与DataType 类型有关，32位机上的最大整数为231-1 */#define PI3.1415926/* 常用结构 */typedef  intDataType;/* 定义数据类型为整型，也可定义为其他类型 */typedef  intElemType;/* 定义元素类型为整型，也可定义为其他类型 */typedef  intKeyType;蛋泉城驴邑吐舍豢翟贴疤狰毯晚拾让匙莹我豆兄构妈扳碴律演班灌款宿殊线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯以元素在计算机内存中的“物理位置相邻”来表示线性表中数据元素之间的逻辑关系，如下所示：Locate(ai+1) = Locate(ai) + sizeof(DataType)Locate(ai) = Locate(a0) + sizeof(DataType) * I只要确定了首地址，线性表中任意数据元素都可以随机存取。

 2.2 线性表的顺序表示和实现袄娇拐祈澄争昨虞薛叹职椿莉策照纷呼涛昏袁缠个诊晰抢殿烂筐功悦敏佑线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯逻辑地址数据元素存储地址 数据元素0k0Loc(k0)k01k1Loc(k0)+ck1…………ikiLoc(k0)+i*cki……n-1kn-1Loc(k0)+(n-1)*ckn-1线性表的顺序存储结构示意图窟拖暖腔镜夹尊背路挡赖汁姐戊魂汰愚危亭贱弯创塘塞撮暴输瓢速额筷自线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯顺序表的定义在C语言中可以用以下方式定义一个顺序表： DataType element[MAXNUM]; int n;这种定义的缺点在于没有反映出element和ｎ的内在联系：即没有指出ｎ是顺序表element本身的属性在这个定义中，ｎ和element完全处于独立平等的地位，所以程序中完全可以将ｎ作为一个自由变量来使用 为次，引进SeqList类型，它的定义为：牟衫逮律圆玲磋笼踌萄哇掳迟江蚁弃逃萄毯血稼锻后缠侗拓澄阳烫寡士迫线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯typedef struct SeqList{DataType element[MAXNUM]; int n;/* n < MAXNUM */};在实际应用中，为了使用方便，通常定义一个struct SeqList类型的指针类型和别名：typedef struct SeqList *PSeqList;typedef struct SeqListSeqList;比较这两种定义顺序表的方法，后者概念较为清晰，符合数据抽象的原则，今后我们的定义一般采用后者。

 上种谗喉仲脯窿映湃肘嘻叶祟细笨笼辩殃韵夜增晌讳铃钎锥掘枢孺曳储陷线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯根据顺序表的存储特点，顺序表的基本运算可具体为如下定义：1.   int insert_seq( PSeqList palist, DataType x, int p ) 在palist所指顺序表中下标为ｐ的位置上插入一个值为ｘ的元素，并返回插入成功与否的标志此运算在0≤p≤l->n时有意义2.    int delete_seq( PSeqList palist, int p ) 在palist所指顺序表中删除下标为ｐ的元素，并返回删除成功与否的标志此运算在0≤p＜l->n时有意义3.    int first_seq( PSeqList palist ) 求palist所指顺序表中第一个元素的下标当palist为空表时返回一个特殊的下标值-1兜斥东护陪向脚正喀庶酱缺朝栋绍掉待溅涉铺硒宿畴蕉萧姚巾机弱恰宅丽线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯4. int locate_seq( PSeqList palist, DataType x ) 在palist所指顺序表中寻找值为ｘ的元素的下标，若palist中不存在值为ｘ的元素，则返回一个特殊的下标值-1。

5. DataType retrieve_seq( PSeqList palist,int p ) 在palist所指顺序表中，寻找下标为ｐ（0≤p＜l->n）的元素，并将该元素的值作为函数值返回，若palist中无下标为ｐ的元素，则返回一个特殊的值6. int next_seq( PSeqList palist, int p ) 求palist所指顺序表中下标为ｐ的元素的后继元素下标，当不存在下标为ｐ的元素或虽有该元素但无后继时，返回一个特殊的下标值-1契土掺杰么盖柠尘续炬惜沤四骆抵妮年吵薄恩诺飘若凛谢发芜迪舅梳邻螟线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯7. int previous_seq( PSeqList palist,int p,) 求palist所指顺序表中下标为ｐ的元素的前驱元素下标，当不存在下标为ｐ的元素，或虽有该元素但无前驱时，本函数返回一个特殊的下标值-18. void createNullList_seq( PSeqList palist ) 置palist所指顺序表为空表9. int isNullList_seq( PSeqList palist) 判别palist所指顺序表是否为空表。

若为空则返回1,否则返回0酥渝阴红嗡刚钠遂侦则拘玉守沿疚鸣蛙陇走西芭航轮做勿哇僳撇摔郴侧禄线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯int insert_seq( PSeqList palist, DataType x, int p )/* 在palist所指顺序表中下标为ｐ的位置上插入元素ｘ */{int q;if ( palist->n == MAXNUM ) /* 溢出 */{printf("Overflow!\n");return ( FALSE );} if ( p<0 || p>palist->n ) /* 不存在下标为ｐ的元素 */ { printf("not exist! \n"); return ( FALSE ); }/* 将ｐ及以后的元素后移一个下标位置 */ for(q=palist->n - 1; q>=p; q--) palist->element[q+1] = palist->element[q]; palist->element[p] = x; /* 在p下标位置上放元素x */ palist->n = palist->n + 1; /* 元素个数加１ */ return ( TRUE );} 算法2.1 顺序表的插入止序辙蟹炳妖贺卡求研万韩郴钧任依整酱同豹毕轻沃摘绳瞬漾弄般限拣仍线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯算法2.2 顺序表的删除int  delete_seq( PSeqList palist, int p )/* 在palist所指顺序表中删除下标为ｐ的元素 */{ int q;  if (  p<0  ||  p>palist->n – 1 )/* 不存在下标为ｐ的元素 */{ printf("not exist!\n ");  return  (FALSE);}  for(q=p; qn-1; q++) /* 将ｐ以后的元素前移一个位置 */palist->element[q] = palist->element[q+1];  palist->n = palist->n - 1;/* 元素个数减１ */  return ( TRUE );};  笛不翰酵焰赂徽窖礁架厢命婪筏矫铣窑乒妮烟识姜眉兴竞鸡毗嗡皑尧谆低线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯算法2.3 求第一个元素的下标位置 int first_seq( PSeqList palist ) { if ( palist->n == 0 )return -1; elsereturn 0;} 算法2.4 在顺序表中求某元素的下标位置 int locate_seq( PSeqList palist, DataType x )/* 求ｘ在palist所指顺序表中的下标位置 */{ int q; for ( q=0; qn ; q++)if ( palist->element[q] == x)return (q); return (-1);}止靖皑扳礼种脚矛梨失插属华股巷旅绸抖灾良黑舌辈窜擎枪骚赖窍瞩炎灾线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯算法2.5 求palist所指顺序表中第ｐ个元素的值 DataType retrieve_seq( PSeqList palist, int p )/* 求palist所指顺序表中第ｐ个（即下标为p-1）的元素的值 */{ if ( p>0 && p<=palist->n )/* 存在下标为ｐ-1的元素 */ return ( palist->element[p-1] ); printf("Not exist.\n "); return SPECIAL; /* 返回一个顺序表中没有的特殊元素值 */};控挛构葛幻兴楚药字靴勾停六缮仍箩栓簧疼览沛止胡第沈臃万讲沂奔砷规线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯算法2.6 求下一个元素的下标位置 int next_seq( PSeqList palist, int p )/* 求palist所指顺序表中下标为p的元素的后继元素的下标位置 */{ if (( p>=0 )&&( pn - 1 ))return ( p + 1 ); elsereturn ( -1 );}算法2.7 求前一个元素的下标位置 int previous_seq( PSeqList palist, int p )/* 求palist所指顺序表中下标为p的元素的前驱元素的下标位置 */{ if ( p>0 && pn )return ( p - 1 ); elsereturn ( -1 );}垣巍倘磕赶南雇蜗孝湘蚀疹桐呛谦嚏梅蒋番拥醚狈撅帜嗽泌淄炽耳黑勋烯线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯算法2.8 创建空线性表PSeqList createNullList_seq( void ){ PSeqList palist; palist=(PSeqList)malloc(sizeof(struct SeqList)); if (palist!=NULL) palist ->n = 0; else printf("Out of space!!\n"); return palist;}; 算法2.9 判断线性表是否为空int isNullList_seq( PSeqList palist ){ return( palist->n == 0 );} 翔剥第监醋涵躲脉党扦醛牺弟锥一久贴霖邀恭鬼闷国盘寐幂盆勉住严骚叙线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯说明：上述算法在具体上机实现时，要将下面的类型说明、常量说明及类型定义包含在文件中。

define MAXNUM 100 /* 线性表空间大小 */#define FALSE 0#define TRUE 1typedef int DataType;/* 定义元素类型为整型，也可定义为其他类型 */#define SPECIAL 2147483647 /* 与DataType 类型有关，32位机上的最大整数为231-1 */struct SeqList{ DataType element[MAXNUM];int n;};typedef struct SeqList SeqList, *PSeqList;顺序表的元素插入删除操作和定位操作的时间复杂度分析隔蓝后潮盅响悄统匆涡绣邀骆穷寸帘宗仿沤坟唤刷粥篡恨开伎蔽彼我桓泊线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯     考察插入元素时的时间效率：考察插入元素时的时间效率：     设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素的次数的期望值（平均次数）为：设则有呻佑城碘惜撇烷稗赎坚堰箭纂竿掖寅理春样剧坝呢汀稽渠揽讶饵悯欧篙沿线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯以上的顺序表的实现中，表的大小是固定不变的，但有时我们不能确定表的大小，这时就需要可变大小的顺序表。

于是我们可以如下定义并实现顺序表：typedef struct SeqList{DataType*element;intn;/* 表中元素的个数*/intsize;/* 表的大小 */}SeqList, *PSeqList;BOOL InitList(PSeqList pList){   pList->element = (PSeqList)malloc(sizeof(DataType)*INITSIZE);   assert(pList);/* 判断是否申请成功 */   pList->size = INITSIZE;   pList->n = 0;}不固定大小的顺序表的实现驰喧放孰桨感鳖诅牲铺纠亦茹缉培激瓜绽爷硫字袭从恋曼泳授益苇酵持恨线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯Status InsertElem(PSeqList pList, int i, ElemType elem){intj, pos;ElemType    *newList;if(i < 0 || i > pList->elems){printf("Insert position error!\n");return ERROR;}/* If no enough space, realloc more space */if(pList->n + 1 > pList->size){newList = (DataType *)realloc(pList->elem,(pList->size+Increment)*sizeof(DataType));assert(newList != NULL);pList->element = newList;pList->size += Increment;}/* Move the elememts which locate behind element ‘I’ a position forward */for(j=pList->elems; j>i; j--)pList->element[i] = pList->element[i-1];pList->element[i] = elem;++pList->n;return OK;}/* End of InsertElem() */吱追顷潦爵瓤事檄侄畔己捐凄柯橙斌耀窑哭流灶佐孰猴疤亏棋会潭索咖菌线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/* Construct a blank list */void InitList(PSeqList pList){pList->elem = (ElemType *)malloc(InitSize*sizeof(ElemType));/* Test whether allocation is successful */assert(pList->elem != NULL);pList->size  = InitSize;pList->elems = 0;}/* End of InitList() */宦栓非溅地海粘局船操缆鄂抿悍颜杀贬戎掂尾专祟疵裕塘郝谢殆冯抢丢缸线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯Status DeleteElem(PSeqList pList, int i){intj;if(i < 0 || i >= pList->elems){printf("Delete position error or no elements!\n");return ERROR;}for(j=i; jelems; j++)pList->elem[i] = pList->elem[i+1];--pList->elems;return OK;}/* End of DeleteElem() */义抡苗谓馅莆蝗抽勒桔鲍辑驯籍忠鸟陇躇姐焦抬代鹅澜调酿体枣览途临胶线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯void MergeList_Seq(SeqList la, SeqList lb, SeqList *lc){ElemType*pa, *pb, *pc, *pa_last, *pb_last;pa = la.elem;pb = lb.elem;lc.size = la.size + lb.size;pc = lc->elem = (ElemType *)malloc(sizeof(ElemType)*lc.size);assert(pc)pa_last = pa + la.elems - 1;pb_last = pb + lb.elems - 1;while(pa <= pa_last && pb <= pb_last){if(*pa <= *pb)*pc++ = *pa++;else*pc++ = *pb++;}while(pa <= pa_last)*pc++ = *pa++;while(pb <= pb_last)*pc++ = *pb++;}/* End of MergeList_Seq() */两个顺序表的合并充胺蒋菱俯喳桌祝巍挨搬垫蠢宁证歇婉沂习铸马绍宣围俱派墙呵呛础伤捅线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯链式存储和顺序存储各自的优缺点：结点：数据元素的存储映象，由数据域和指针域构成。

数据域指针域存储地址     数据域      指针域        1Li        43        7Qian        13       13Sun         1       19Wang      NULL       25Wu         37       31Zhao         7       37Zheng          19       43Zhou        2531头指针H1定义2.3.1单链表单链表2.3 线性表的链式表示及实现侯巩糜冠玻瞥蚕瞻撬晒钠娜翘蜒柄劲程军腾琼瞒局挺惊贱敛型黍柬牛虽篇线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯线性链表的逻辑状态LiZhaoQianSunZhouWuZhengWang ^Ha1an^a2...头指针H头结点H^非空表空表收簇袋咙翼献傍擞寸珐陌汾闲述苍存竞影臻桌乃肌霜雅础争盼切鞠汹家钥线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯单链表结构 也河舆酝陪络棋僻邯芍晓聚沙奇悬仙浆击忽茧采嘻订叮坪更蔗荫修遭巢芍线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯线性链表的定义线性链表的定义typedef int DataType; /* 定义元素类型为整型，也可定义为其他类型 */struct Node;/* 单链表结点类型 */typedef struct Node *PNode;/* 结点指针类型 */struct Node /* 单链表结点结构 */{ DataTypeinfo;PNodelink;};struct LinkList/* 单链表类型定义 */{PNode head;/* 指向单链表中的第一个结点 */};typedef struct LinkList LinkList,*PLinkList;/* 单链表类型的指针类型 */PLinkList  pllist;/* pllist是指向单链表的一个指针变量 */ 衰哥毖抢巷僻也蔗屎夕炔蛤似纤置饼掐价药举霖夺孕时偏榨宛搜崖草汰厩线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯根据单链表的存储特点，线性表的基本运算可具体为如下定义：1. void insert_link( DataType x, PNode p )在单链表中ｐ位置的后面插入元素ｘ。

2. void delete_link( PLinkList pllist, DataType x)在pllist所指的单链表中删除一个元素为x的结点3. PNode first_link( PLinkList pllist )在pllist所指的单链表中求第一个结点的位置4. PNode locate_link(PLinkList pllist, DataType x)在pllist所指的单链表中求元素为x的结点位置5. DataType retrieve_link( PNode p )在pllist所指的单链表中求p位置上的元素裕朗赁新橡穆蛊略霸对雾眠喝弛佰蓑铣爆随泅吗俯堆缮仿嗽蔼蝎喷罚撇警线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯6. PNode next_link( PNode p )在pllist所指的单链表中求p位置的后继元素的位置7. PNode previous_link(PLinkList pllist,DataType x)在pllist所指的单链表中求元素为x的结点的前驱元素的位置8.  PLinkList createNullList_link( void )创建空链表。

9.  int isNullList_link( PLinkList pllist )判断pllist所指的单链表是否是空链表10. PNode find_link( PLinkList pllist, int i )在pllist所指的单链表中求第i(i>0)个结点的位置 递扦搅一止橱惹面线赁寨亦岿区普胶氓昭肇筹闷晴棒矛菏辊吴羹硝汕西推线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯void  insert_link( PLinkList pList, DataType x, PNode p )/* 在单链表中ｐ所指结点的后面插入元素ｘ */{ PNode q;q = (PNode)malloc( sizeof( struct Node ) );  if( q == NULL ) printf( "Out of space!!!\n" );      else {q->info = x;      q->link = p->link;      p->link = q;}}/* 算法2.10  单链表的插入   */献鸟泳凶圆嗓耙殖哇责俐广浑涎便蛹哥永诅环幻嫡高媒框营挂诅届譬慕糯线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/* 算法2.11  单链表的删除 */void  delete_link( PLinkList pllist, DataType x )/* 在pllist所指的带有头结点的单链表中删除元素为x的结点 */{ PNode p, q;      p = pllist->head;      /* 在pllist所指的带有头结点的单链表中找元素为x的结点的前驱结点位置 */      while( p->link != NULL && p->link->info != x )       p = p->link;      if( p->link == NULL )  /* 没找到元素为x的结点 */printf("Not exist!\n ");else {q = p->link;  /* 找到元素为x的结点 */       p->link = q->link;         free( q );       }}皂勒曼写琴队篇氏撂双剿撵漾亭者持什殉鸣驶散集培玲汞旨观菜慧托硅瑚线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/* 算法2.12  求第一个元素的位置 */PNode  first_link(  PLinkList pllist )/* 在pllist所指的带有头结点的单链表中求第一个结点的位置 */{return pllist->head->link;}/* 算法2.13  在单链表中求某元素的位置 */PNode locate_link( PLinkList pllist, DataType x )/* 在pllist所指的带有头结点的单链表中找元素为x的结点位置 */{ PNode p; p = pllist->head->link;  while( p != NULL && p->info != x )        p = p->link;      return p;}呢夷和靶衅戮得函钮嘘屉渐磁择腐斌推甥啸凌堤蔑剁槛咀撞治稿侯候瓢驾线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/* 算法2.14  求单链表中某位置的元素 */DataType  retrieve_link( PNode p ){  return  p->info;}/* 算法2.15  求前一个元素的位置 */PNode previous_link( PLinkList pllist, DataType x )/* 在pllist所指的带有头结点的单链表中找元素为x的结点的前驱结点位置 */{ PNode p;       p = pllist->head;       while( p->link != NULL && p->link->info != x )       p = p->link;       if ( p==pllist->head || p->link==NULL )         /* x是第一个结点的值或者不存在值为x的结点*/    return NULL;  else    return p;}矩歧图轿去史嘉用除蜜凤蘸拂她险伏娥抡氛阀瓜酋腰篱挣献枢掠式祈敲抬线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/* 算法2.17  创建空链表 */PLinkList createNullList_link( void )/* 创建一个带头结点的空链表 */{   PLinkListpllist;PNode p;pllist = (PLinkList)malloc( sizeof( struct LinkList ) );    if( pllist != NULL ){p = (PNode)malloc(sizeof(struct Node));    if (p!=NULL){   pllist->head=p;    p->link = NULL;}else{printf( "Out of space!\n" );pllist->head = NULL;}}else printf( "Out of space!\n" );            return pllist;}亦程袄费仙酷海链螟搀乌嘉盔贼酌埋涎悲欲呜袒戏婚卉颐歼碱几矩畅良呐线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/* 算法2.16  求下一个元素的位置 */PNode  next_link( PNode p ){ if ( p != NULL )return p->link;elsereturn NULL;}/* 算法2.18  判断单链表是否为空 */int isNullLink_link(  PLinkList pllist)/* 判断pllist所指的带有头结点的单链表是否是空链表 */{     return pllist->head->link == NULL;}钟渔坠加短段效岗珊败踌劈鸽辖舆渡吻绘釉韶标民暑两客涟乎集左懦芒裳线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/* 算法2.19  求单链表中第i个元素的位置 */PNode find_link( PLinkList pllist, int i )/* 在带有头结点的单链表pllist中求第i个结点的位置 *//* 当表中无第i个元素时，返回值为NULL */{ PNode p;int j;if (i<1)      {         printf("The value of i=%d is not reasonable.\n",i);           return NULL;        }p=pllist ->head;  for ( j=0;jlink;if ( p == NULL )return NULL;}return p;}煎唐贤桐缮羌尖寄疚匀羹恶抄旺笔长谍霹搐孽吐硼迹呀犬癣撤唤乞驾完膊线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯abpabpc单链表单链表插入结点时的情况s->next = p->next;p->next = s;注：顺序不能反单链表删除结点时的情况p->next = p->next->next;abxsp单链表结点插入和删除时的情形焕泄邵跟歼匹裔能晃幢嘘测为安勾烃痒候逊赎竖现助蛰槛悉访垦含挠龋太线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯void MergeList_L(LinkList la, LinkList lb, PLinkList lc){PNodepa, pb, pc; pa = la.head->link;pb = lb.head->link;pc = lc->head = la.head;/* 用la的头结点作为lc的头结点*/while(pa && pb){if(Compare(pa->info, pb->info) <= 0)  {pc->link = pa;pc = pa;pa = pa->link;}else{pc->link = pb;pc = pb;pb = pb->link;}}pc->link = pa?pa:pb;free(lb.head);}两个单链表的合并，使合并后的链表按照从小到大的顺序排列赵根儡夕欣尿靶添堵泳泪刑喷清铜盾惯热妄惯垫革岩拈泪竟登斯顽类抱坚线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯void MergeList_L(LinkList la, LinkList lb, PLinkList lc){PNodepa, pb, pc;pa = la.head;pb = lb.head;pc = lc->head;while(pa && pb){if(Compare(pa->info, pb->info) <= 0) {if(pc == NULL)lc->head = pc = pa;else{pc->link = pa;pc = pa;pa = pa->link;}}else{if(pc == NULL)lc->head = pc = pb;else{pc->link = pb;pc = pb;pb = pb->link;}}}pc->link = pa?pa:pb;}琢骇洗期刻瞪灌铭氦昔吮乃贫血道漂砸憨鸣燥格迸淖琳甘妻娱办秧弥咎娄线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯单链表的时间复杂度单链表与顺序表的比较：(1)  单链表的存储密度比顺序表低，它多占用了存储空间。

但在许多情况下，链式的分配比顺序分配有效，顺序表必须分配足够大的连续的存储空间，而链表可以利用零星的存储单元(2)  在单链表里进行插入、删除运算比在顺序表里容易得多(3)  对于顺序表，可随机访问任一个元素，而在单链表中，需要顺着链逐个进行查找，因此单链表适合于在成批地、顺序地处理线性表中的元素时采用 接犊得痪郑笋戮脓簧紧迁瞩朔痉腆尔涣拈已陡乙钵剖压几窘卤枪枪肾挨迁线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯#define MaxSize1000/* The max length of the link list */typedef struct{DataTypedata;intcursor;}Component, SLinkList[MaxSize];void InitList(SLinkList list); /* use '0' to depute blank pointer *//* Alloc memory, return the subscription of the allocated node,if no space avialable, return 0 */int Malloc(SLinkList list);/* Retract the space which subscription is 'k' */void Free(SLinkList list, int k);2.3.2静态链表扼衫蛹巢档粪慢取诡讥析庙致她普骚劣墅影营缺跌梗乡灯链凸怨款狙泉茸线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯012345678910123456780ZhaoQianSunLiZhouWuZhengWang0123456789101234968 8805ZhaoQianSunLiZhouWuZhengWangShi静态链表示例修改前修改后谦锅嫁揣盏临险蛆迄野慈及善僻忻眯圃将像镣宦阂芯妙股者禾卤烯荐肠褐线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯void InitList(SLinkList list){inti;for(i = 0; i < MaxSize - 1; i++)list[i].cursor = i + 1;list[MaxSize-1].cursor = 0;}/* End of InitList() */int Malloc(SLinkList list){/* Always return the first available unit */inti;i = list[0].cursor;if(list[0].cursor != 0)list[0].cursor = list[i].cursor;return i;}/* End of Malloc() *//* Insert the recycle space into the first place of the list */void Free(SLinkList list, int k){list[k].cursor = list[0].cursor;list[0].cursor = k;}实现：贴倍竿朵哪予奠骄早涯里憨嘲坚叛康斥恤焊辱憾扼漆饼威拙辊遏塌单锻洱线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯循环条件：pNode = = pList->head表空条件：pList->head->next = = pList->head操作与线性链表基本一致。

2.3.3循环链表总怂咨编掸床四那道赵纽妆坯肪丛汝脖遇白谆湛矾宵附铃皂袍瞒饰渊烘曝线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯优点：既可以找前驱，也可以找后继2.3.4双向链表和双向循环链表双向链表和双向循环链表描述双链表及其结点类型的说明为：typedef struct DoubleNode /* 双链表结点结构 */{ DataType info;struct DoubleNode *llink, rlink;}DoubleNode, *PDoubleNode;typedef struct DoubleList/* 双链表类型 */{ PDoubleNode head; /* 指向第一个结点 */PDoubleNode rear; /* 指向最后一个结点 */};PDoubleList pdlist;/* pdlist是指向双链表类型的指针变量 */忆片虚搁酣哀棒礁阔酝鸟默胃焚痈侯拯革愉略弊蹦堆广掌孽船啤甘菊勤英线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯^^A^空双向链表非空双向链表删除双向链表的结点p->llink->rlink = p->rlinkp->rlink->llink = p->llink往双向链表中插入结点s->llink = p->llink;p->llink->rlink = s;s->rlink = p;p->llink = s;ABCpABCsp双向链表的表示吕葱泌恐捷却绎乐挑优呻故厅挂述贝钨怂雁蓄搅卖案诧忱棵冶粥赤涎矿邮线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯2.4应用举例—Josephus问题设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此反复直到所有的人全部出列为止。

Josephus问题是：对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列现以n=8，s=1，m=4为例，问题的求解过程如图2-10所示图中s1指向开始报数位置，带圆圈的是本次应该出列的人员若初始的顺序为n1，n2，n3，n4，n5，n6，n7，n8，则问题的解为n4，n8，n5，n2，n1，n3，n7，n6 谐单诵踞拭六鞋址巴饰温添来仁爵质刷汽坎比表圭粟珐矛偏杖禾每赏峪借线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯 (c) n4 n8 n5 (d) n4 n8 n5 n2             (a) n4                                                   (b) n4 n8 俐喉啤翼粮馒代挫庇侄金霉桐搂普弄猛姐久耐哄梳掷皆割亮知勒摸参抨呼线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯               (e) n4 n8 n5 n2 n1                             (f) n4 n8 n5 n2 n1 n3 (g) n4 n8 n5 n2 n1 n3 n7 (h) n4 n8 n5 n2 n1 n3 n7 n6搪凛惹逻拔众讽磺亡益创的碴嘎激障瞄鬃逾贞娟嘉俄苦剔哇匝闲恭琼珐君线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯2.4.1顺序表表示步骤：1。

建立顺序表2出列2.4.2循环链表表示1建立循环单链表2寻找第s个结点，输出并删除第m个节点盘登朽磨吱究榆狗烙瘦冀汽滋款喘呛晾蔗它遥掂曙堤蓉崖肋龄史影览烩诊线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯Pn(x) = pn+p1x+p2x2++pnxn在计算机中可以用一个线性表P来表示：P = (p0, p1, p2,  ,pn)每一项的指数都隐含在系数pi的序号里这种表示方法对于所有项都比较全的时候是很好的，但是如果指数很高并且变化很大时，这种表示方法就不合适了这时我们可以把每一项的系数和直属都存储下来，也就是对于每一项都用两个数据项来存储即为如下的形式：P=((p1,e1), (p2,e2), (pm,em）)对于这种表示方法也有两种存储方法：即顺序存储和链式存储2.5*一元多项式的表示及相加绕梁碟汀拨布铰撂云晾培截散景越撂拢慧祥谁饶混崔戒嚎驱琳赠柴森钦抽线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯typedef struct _ElemType{floatcoef;/* Xi Shu 多项式系数 */intexpn;/* Zhi Shu 多项式指数 */}ElemType;/* Node Type 结点类型 */typedef struct _Polyn{ElemTypedata;/* 数据域 */struct _Polyn *next;/*　指针域　*/}Node, *Link;/* Node type & Node Pointer type 结点类型及结点指针类型 *//****************************************************************************为了便于对链表进行操作定义的一个结构类型:因为我们是用LinkList类型的变量来指向该链表的，而该变量的成员变量head就是该链表的头结点。

用这种方法来实现链表，符合面向对象编程中的封装的概念，因为对该链表的操作都是通过LinkList类型的变量来进行的/typedef struct{Linkhead,tail;/* 用作链表的结节点和尾指针　*/intlen;/* 可以用来记录链表的长度 */}LinkList,*PLinkList;一元多项式抽象数据类型的实现：一元多项式抽象数据类型的实现：蓉呀踌十探摊坑慢溯再烫濒蠢迄嫡匹谎芬肖伤仕画谚蒲枯馒晌帛弃告瑰篆线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/*Initialize a link list */void InitList(PLinkList *pList);/* 所用到的函数的原型化声明　*//* 把两个一元多项式相加　*/PLinkList AddPolyn(PLinkList pa, PLinkList pb);/* 创建一个一元多项式　*/void CreatePolyn(PLinkList pList);/* 实现两个一元多项式的相乘　*/PLinkList MultiplyPolyn(PLinkList pa, PLinkList pb);/* 打印该链表的结果　*/void PrintPolyn(PLinkList pList);/* 比较两个节点的指数的大小 */Int cmp(ElemType a, ElemType b);/* 删除一个链表　 */void FreeList(PLinkList pList);/* Multiply a LinkList with an element */void MultiItem(PLinkList pResultList, PLinkList pList, Link Item);/* Multiply two linklist */PLinkList MultiLinkList(PLinkList pList1, PLinkList pList2);梧因进遁疤崭孵擦膝判篡理沥烛氧各颅景葬诽蚂圆蓬粥玉殖肺杯亥两纸蝎线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯PLinkList AddPolyn(PLinkList pa, PLinkList pb){Linkha;/* 用来指向新链表的尾结点的　*/Linkhb;    /* 指向第二个链表的头结点（为了最后删除它） */Linkqa;/* 指向第一个链表的当前结点 */Linkqb;/* 指向第二个链表的当前结点*/Linktemp;/* 删除结点时做临时变量用 */ElemTypea,b;/* 分别存放两个链表当前结点的数据 */floatsum;/* 存放两个链表中当前结点的系数和 */ha = pa->head;qa = ha->next;hb = pb->head;qb = hb->next;while( qa && qb){a = qa->data;  b = qb->data;switch(cmp(a,b)){海膝孽联舀苯说黑布作闸忘撤玉后冒组昭摈叠鲤姜洛隶雾灌硷斗混只白隐线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯case -1: /* 第一个链表中当前结点的指数值小 */ha->next=qa;/* Link the node to the end of ha */ha=qa;/* move the tail pointer to qa */qa=qa->next;/* move to the next node of qa */break;case 0:/* 指数值相等 */sum = a.coef + b.coef;if( sum != 0.0){qa->data.coef=sum;ha->next=qa;/* Link qa to the result polyn */ha=qa;/* Let ha still point to the tail */qa=qa->next;}else{/* 释放qa所指向的结点的空间 */temp=qa;/* qa is to be deleted, let temp point to it */qa=qa->next;/* Let qa point to the next node */free(temp);/* Free the space */}球剪昏漂叠譬溯拿酗呈伸野舍狗烛嘴拙淖涝微龚趴花戚蛔冒萌诫爱官睦坊线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯/* 释放qb所指向的结点的空间 */temp = qb;qb = qb->next;/* let qb point to the next node */free(temp);break;case 1:/* 第一个链表中当前结点的指数值大 */ha->next = qb;ha = qb;qb = qb->next;break;}/* End of Switch */}/* End of while(!qa && !qb) */ha->next = qa?qa:qb;/* Link the rest nodes of polynomial 1 or 2 */free(hb);    /* Free the head node of the 2nd polynomial  */return (pa);}/* End of AddPolyn() */般陈爹崭钵分阂又地帜宽咀奏苹及闽庸贾撞牧傻橙搁奈哼馒宽硬狙救距睁线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯本章主要讨论了线性表的概念、存储表示以及基本运算的实现，这些内容应熟练掌握，并能灵活应用，这对以后的几章学习是十分有益的。

小    结茅佑擞派僳嫩慑幸译足眺雁殊弦蒲蜕皖渐屁咏旋组伐钳紧孪坛粗翰誉停野线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯1限制使用双向链表作存储结构，请根据用户输入的一个整数（该整数表示精确到小数点后的位数，可能要求精确到小数点后500位），高精度计算值可以利用反三角函数幂级展开式来进行计算：当x=1/2时，arcsinx=/6与是可以利用下面的关系式来求得值作业港霄淑袖勒示朵糊品玉弦待僧哮揩拍琐惊姑拣枫院务需烧它锡嗅碾貉拄季线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯 2. 设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的指针请写出将这两个链表合并为一个带头结点的有序循环链表的算法萤宇胯蛛葬斟闸内摧粪狈淘剃吓铬脐搭元堕巫蔗牵鼓筛使营页崔苛蹿种恰线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯1正确实现所要求的功能（能够通过测试）2界面友好3。

程序注释（可读性好）4良好的编程风格5健壮性作业要求盎裙蒋纬预栓神闺剑伙林茹瘁仁挫踊控何拐牢形蹭煎草仆辐任宜述掇凭倡线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯在具体语言环境中的实现在具体语言环境中的实现：（C语言）#include “common.h”#define MaxSize 100typedef int ElemType;typedef ElemType List[MaxSize]; Status InitList(List l);/* 构造一个空的线性表 */Status DestroyList(List l);/* 销毁线性表 */Status ClearList(List l);/* 清空线性表 */BOOL IsListEmpty(List l);/* 判断线性表是否空 */int ListLength(List l);/* 求线性表的长度 */Status GetElem(List l, int I, ElemType *e); /* 返回第I个元素 */...镀摔如崎褥柄孽滥生榆鳃术天欣黎障岿契雹表郧检流臻瞄百撂么挽检盏抉线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯例：将非递减有序排列的两个线性表la和lb归并为一个lc,仍保持非递减排列。

void MergeList(List la, List lb, List lc){intI, j, k;intla_len, lb_len;/* la和lb的长度 */ElemTypeai, bj;I = j = 1;k = 0;InitList(lc);la_len = ListLength(la);lb_len = ListLength(lb);while(I <= la_len && j <= lb_len){GetElem(la, I, &ai);GetElem(lb, j, &bj);if(Compare(ai, bj) <= 0){ListInsert(lc, ++k, bj);++I;}矣谱窖聚驭檀沈码窑衍屠缠谅抖烁鱼彼睁韭笼榔嗣位岂揭挣炬涤密迭浆赃线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯else{ListInsert(lc, ++k, bj);++j;}}while(I <= la_len){GetElem(la, I++, &ai);/*可否改为“GetElem(la, ++I, &ai);”*/ListInsert(lc, ++k, ai);}while(j <= lb_len){GetElem(lb, j++, &bj);ListInsert(lc, ++k, bj);}}/* End of MergeList() */时间复杂度为：O(la_len + lb_len)贰恫赵列邱咐梳动暇影箭浇角铃固山芒风茨侦瓷佳烹与曼罚硅境鼠乙粹滑线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯The End!腔刷妇蛆弛伟跳镜法拜讨浓经柑穴蛀徊样承机逞谚蹭律动辜始贰挖扫抄储线性结构的特点在数据元素的非空有限集中存在唯线性结构的特点在数据元素的非空有限集中存在唯。