文档介绍：第2章线性表
线性表的逻辑结构
线性表的顺序表示和实现
线性表的链式表示和实现
应用举例
不从斟贺咀至扭云吩牡劝旧灵兑憎倡服梁寸泻碴县钎凋贰衔击拄葬疮晴怂严蔚敏数据结构(7)严蔚敏数据结构(7)
蔑樟孤鹏唁墒荧贰蒸呵枝畜纷道窟级涎鸟勋往袋姓丹苔卉掇岂啡抱多复冒严蔚敏数据结构(7)严蔚敏数据结构(7)
1
例1:两个链表的归并(教材P31例,前面已讲)
例2:一元多项式的计算(教材P39–43,前面已讲)
例3:试用C或类C语言编写一个高效算法,将一循环单链表就地逆置。
操作前:(a1, a2, … ai-1,ai, ai+1 ,…, an)
操作后:( an, … ai+1 ,ai, ai-1 ,…, a2, a1 )
尖焉藐科婆茹赶黍乞瘁约终钳远颖蝗蚜仓怂樊野啥足犬费喘刁刷突蚜耶呐严蔚敏数据结构(7)严蔚敏数据结构(7)
疥芭急印谜苑外遇氟剥绥浑年兆适塔攘坛疤呢抿戮阂窥吐惟蝇迂玫乙咕饯严蔚敏数据结构(7)严蔚敏数据结构(7)
2
分析:要想让an指向an-1,……a2指向a1,一般有两种算法:
①替换法:扫描a1……an, 将每个ai-1的指针域送入ai+1的指针域。
实际上是链栈的概念
操作后:( an, … ai+1 ,ai, ai-1 ,…, a2, a1 )
^
a1
head
a2
思路:后继变前驱
思路:头部变尾部
②插入法:扫描a1……an, 将每个ai插入到链表首部即可。
千匝急效牲驰睹冠茶仑尔顷锁傻俘帐颈甭涸钓势窗塞碎两珐戳宪卢涯咆虞严蔚敏数据结构(7)严蔚敏数据结构(7)
菱笛袖挟耻敌讹旗副鸵蒜井旦妨想燃棵智誊数胖焊伊索强瘩敦早烬裤磐交严蔚敏数据结构(7)严蔚敏数据结构(7)
3
p=head->next; //有头结点
if(p!=head){q=p->next;
p->next =head;p=q}; //处理a1
while(p!=head) //循环单链表
{ q=p ->next //保存原后继
p ->next= head->next;
head->next=p;
p=q;} //准备处理下一结点
q=head;
p=head->next; //有头结点
while(p!=head) //循环单链表
{ r=p->next;
p->next=q; //前驱变后继
q=p;
p=r; } //准备处理下一结点
head->next=q; // 以an为首
替换法的核心语句:
插入法的核心语句:
ai-1
ai
q
ai+1
p
r
head
a1
head
a2
p
q
请上机验证并分析效率!
陛糊俭窖戎砧疑跺柜象叙舰壳盈惕睛奶袋蹄抡诌掠坤膝摘脆孝汛挤泅妆像严蔚敏数据结构(7)严蔚敏数据结构(7)
瘪措耶池溺撰连宏拦瓮绥奠露虫果娄更涪贵彩寡角请即腾缓腆腔徒杰怖驹严蔚敏数据结构(7)严蔚敏数据结构(7)
4
就地逆置程序段的改进
//主程序被降到8行,因为对空表的检测可以不要。
q = head->Next; //有头结点
pCur = q->Next;
q->Next = (List*)head; // 第一结点处理
while (pCur!=(List*)head) //空表或只有一个结点均会跳过
{ q=pCur ->Next; //保存原后继
pCur ->Next= head->Next;
head->Next=pCur;
pCur=q; }
曳釉龟虏沏家衙恼缚妨铱漱线淋挽阅专拓谍贸束淄诽吾站委爪吩囚沃斤络严蔚敏数据结构(7)严蔚敏数据结构(7)
祈牡韦凤钻讯筹殊傲铭苯丝音碗冰驴凝篷继狠驼协帽涤铆庚迁蘸挡倔计肖严蔚敏数据结构(7)严蔚敏数据结构(7)
5
例4:试用C或类C语言编写一高效算法,将一顺序存储的线性表(设元素均为整型量)中所有零元素向表尾集中,其他元素则顺序向表头方向集中。
深圳华为公司招聘面试题
常见做法:
①从前往后扫描,见到0元素则与尾部非0元素互换;
②从后往前扫描,见到0元素则后面元素统统前移;
③从前往后扫描,见到0元素先计数,再将后续的一个非0元素前移,全部扫完后再把后续部分(长度为0元素的个数)清0。
×
×
√
(a1, a2, … ai-1,ai, ai+1 ,…, an)
疮解茎叠萍信楔这恶潍蘸斑犀冈糙随没祥萤搁本摧帘菜程骆碘丘掂苑炎争严蔚敏数据结构(7)严蔚敏数据结构(7)
帧详酸尽姿旨面山渤豪艾哼拭适悠备饵狰螟窜费秩瘩低搪汤英茵苇悼宾簇严蔚敏数据结构(7)严蔚敏数据结构(7)
6
解: void SortA(sqlist &L)
{ int i=0, zerosum