2線性表2.1線性表基礎(chǔ)2.2順序表2.3STL之vector2.4鏈表2.5STL之list2.6在線題目求解學(xué)習(xí)目標(biāo)1.記憶和理解線性表、順序表和鏈表的基礎(chǔ)知識(shí)。2.掌握順序表、鏈表的實(shí)現(xiàn)。3.學(xué)會(huì)運(yùn)用順序表、鏈表求解具體問題。4.學(xué)會(huì)運(yùn)用STL之vector、list求解具體問題。2線性表2.1線性表基礎(chǔ)線性表(a1，a2，…，ai，…，an)是一種最簡(jiǎn)單的線性結(jié)構(gòu)，是n個(gè)特性相同的數(shù)據(jù)元素構(gòu)成的有限序列；其中，n稱為線性表的表長(zhǎng)；n=0的線性表稱為空表；i稱為數(shù)據(jù)元素ai的位序。線性表(a1，a2，…，ai，…，an)具有以下基本特征：（1）存在唯一的一個(gè)“首元素”（第一個(gè)元素），即a1；（2）存在唯一的一個(gè)“尾元素”（最后一個(gè)元素），即an；（3）除首元素之外，其他元素均僅有一個(gè)前驅(qū)，如a2的前驅(qū)為a1，an的前驅(qū)為an-1；（4）除尾元素之外，其他元素均僅有一個(gè)后繼，如a1的后繼為a2，an-1的后繼為an。2.1線性表基礎(chǔ)6個(gè)英文字母可構(gòu)成線性表(A,B,C,D,E,F)5個(gè)整數(shù)可構(gòu)成線性表(1,2,3,4,5)。線性表具有創(chuàng)建、遍歷、插入、刪除、修改和查詢等基本操作。線性表既可采用順序存儲(chǔ)結(jié)構(gòu)，又可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，相應(yīng)的線性表分別稱為順序表和鏈表。2.2順序表順序表是采用順序存儲(chǔ)結(jié)構(gòu)的線性表，用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素。線性表(a1，a2，…，ai，…，an)的順序存儲(chǔ)示意圖：在順序表中，以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1，ai>數(shù)據(jù)元素ai的存儲(chǔ)地址LOC(ai)=LOC(ai-1)+C，C表示一個(gè)數(shù)據(jù)元素所占的存儲(chǔ)量。首元素a1的地址LOC(a1)稱為線性表的起始地址或基地址。因線性表中的所有其他數(shù)據(jù)元素的存儲(chǔ)位置均取決于首元素a1的存儲(chǔ)位置，故LOC(ai)=LOC(a1)+(i-1)×C2.2順序表順序表的實(shí)現(xiàn)結(jié)構(gòu)體定義constintN=80;//順序表的最大容量為NtypedefintElemType;//為int類型取別名ElemTypestructSqList{ElemType*elem;//存儲(chǔ)空間基址intlength;//當(dāng)前長(zhǎng)度voidInit();//初始化voidClear();//清除線性表intLocate(ElemTypee);//查找voidInsertBefore(inti,ElemTypee);//插入元素voidDelete(inti,ElemType&e);//刪除元素boolEmpty();//判斷空表voidTraverse();//遍歷};typedef為已有類型int取別名ElemType，從而提升代碼的可維護(hù)性。2.2順序表順序表的實(shí)現(xiàn)初始化//初始化順序表voidSqList::Init(){//構(gòu)造空的順序表

elem=newElemType[N];//創(chuàng)建動(dòng)態(tài)數(shù)組，首地址存放在elem中

length=0;}順序表的初始化操作申請(qǐng)一個(gè)長(zhǎng)度為N的動(dòng)態(tài)數(shù)組由數(shù)據(jù)成員elem指向，則elem可視為一個(gè)數(shù)組名；另外，置數(shù)據(jù)成員length為0。::是類屬運(yùn)算符，表明其后的函數(shù)（此處為Init）屬于其前的結(jié)構(gòu)體類型（此處為SqList）。時(shí)間復(fù)雜度為O(1)。2.2順序表順序表的實(shí)現(xiàn)查找//在順序表中查找第一個(gè)滿足判定條件的數(shù)據(jù)元素，//若存在，則返回它的位序，否則返回0intSqList::Locate(ElemTypee){

//查找

inti=1;//i的初值為第一個(gè)元素的位序（即1）

while(i<=length&&elem[i-1]!=e){

i++;

}

if(i<=length)returni;

elsereturn0;}時(shí)間復(fù)雜度為O(n)。2.2順序表順序表的實(shí)現(xiàn)插入順序表操作InsertBefore(i,e)實(shí)現(xiàn)在順序表的第i個(gè)元素之前插入元素e。在第i個(gè)元素之前插入新元素e，將使線性表從(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)，即從一個(gè)有序?qū)?lt;ai-1,ai>變?yōu)閮蓚€(gè)有序?qū)?lt;ai-1,e>、<e,ai>，且表長(zhǎng)增1。插入前后的示意圖分別如下：2.2順序表順序表的實(shí)現(xiàn)插入//在順序表的第i個(gè)元素（下標(biāo)為i-1）之前插入新的元素evoidSqList::InsertBefore(inti,ElemTypee){

if(i<1||i>length+1)return;

//若插入位置非法，則不做插入操作

for(intj=length-1;j>=i-1;j--)

elem[j+1]=elem[j];//插入位置及之后的元素后挪

elem[i-1]=e;//插入e

length++;//表長(zhǎng)增1}時(shí)間復(fù)雜度為O(n)。2.2順序表順序表的實(shí)現(xiàn)插入考慮移動(dòng)元素的平均情況，假設(shè)在第i個(gè)元素之前插入的概率為pi，則在長(zhǎng)度為n的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）如下：若假定在線性表中任何一個(gè)位置i（1≤i≤n+1）上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值如下：2.2順序表順序表的實(shí)現(xiàn)刪除順序表操作Delete(i,&e)實(shí)現(xiàn)刪除順序表中的第i個(gè)元素，并通過引用參數(shù)e返回該元素。設(shè)刪除元素ai，則線性表從(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?/p>

(a1,…,ai-1,ai+1,…,an)，即從兩個(gè)有序?qū)?lt;ai-1,ai>,<ai,ai+1>變?yōu)橐粋€(gè)有序?qū)?lt;ai-1,ai+1>，且表長(zhǎng)length減1。刪除前后的示意圖如右：2.2順序表順序表的實(shí)現(xiàn)刪除//順序表中輸出第i個(gè)元素，通過引用參數(shù)e返回該元素voidSqList::Delete(inti,ElemType&e){

if(i<1||i>length)return;//待刪位置非法，則返回

e=elem[i-1];

//被刪除元素的值賦給e

//被刪除元素之后的元素左移

for(intj=i;j<=length-1;j++)elem[j-1]=elem[j];

length--;

//表長(zhǎng)減1}待刪元素通過引用參數(shù)e返回，若刪除之后無(wú)需再用到該元素，則可省略引用參數(shù)e。時(shí)間復(fù)雜度為O(n)。2.2順序表順序表的實(shí)現(xiàn)刪除考慮移動(dòng)元素的平均情況，假設(shè)刪除第i個(gè)元素的概率為qi，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）如下：若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值如下：2.2順序表順序表的實(shí)現(xiàn)其他操作//清空順序表，時(shí)間復(fù)雜度為O(1)voidSqList::Clear(){

delete[]elem;

length=0;}//遍歷順序表，時(shí)間復(fù)雜度為O(n)voidSqList::Travese(){

for(inti=0;i<length;i++){

if(i>0)cout<<"";

cout<<elem[i];

}

cout<<endl;}//判斷是否空順序表，時(shí)間復(fù)雜度為O(1)boolSqList::Empty(){

returnlength==0;}2.3STL之vector基礎(chǔ)知識(shí)STL之vector（向量）可用于表示順序表，頭文件是vector。定義向量時(shí)，可同時(shí)指定其長(zhǎng)度。例如：intn;cin>>n;vetcor<int>a(n);//指定a的每個(gè)元素的類型都是int，長(zhǎng)度為n2.3STL之vector基礎(chǔ)知識(shí)vetcor部分常用成員函數(shù)向量a元素為

1、3、5、7。2.3STL之vector例2.3.1一維vector使用方法#include<iostream>#include<vector>usingnamespacestd;voidprtVector(vector<int>a);intmain(){

intn,i;

cin>>n;

vector<int>v(n);

for(i=0;i<v.size();i++)v[i]=i+1;

v.push_back(123);

//

在尾部插入

v.insert(v.begin(),456);//

在頭部插入

v.erase(v.begin()+1);

//

刪除第二個(gè)元素2.3STL之vector例2.3.1一維vector使用方法

prtVector(v);

//

輸出向量元素

v.clear();

//

清空向量

v.resize(n*2);

//

重新定義長(zhǎng)度

cout<<v.size()<<endl;

return0;}voidprtVector(vector<int>a){//輸出向量中所有元素，以空格間隔

for(inti=0;i<a.size();i++){

if(i>0)cout<<"";

cout<<a[i];

}

cout<<endl;}2.3STL之vector例2.3.2二維vector簡(jiǎn)單示例#include<iostream>#include<vector>usingnamespacestd;intmain(){

inti;

intr,c;

cin>>r>>c;

//

下面的語(yǔ)句直接定義r行c列的二維動(dòng)態(tài)數(shù)組

vector<vector<int>>tv(r,vector<int>(c));

for(i=0;i<r;i++){

for(intj=0;j<c;j++)

cin>>tv[i][j];

}2.3STL之vector例2.3.2二維vector簡(jiǎn)單示例

for(i=0;i<r;i++){

for(intj=0;j<c;j++){

if(j>0)cout<<"";

cout<<tv[i][j];

}

cout<<endl;

}

tv.clear();

return0;}2.3STL之vector例2.3.2二維vector簡(jiǎn)單示例vector<vector<int>>tv(r,vector<int>(c));定義一個(gè)r行c列的二維向量，注意“>>”中兩個(gè)>之間有空格，否則會(huì)被編譯器理解為>>運(yùn)算符而出錯(cuò)；定義二維向量的另一種寫法：vector<vector<int>>tv;//定義二維向量tv.resize(r);

//重置第一維長(zhǎng)度（行數(shù)）為rfor(i=0;i<r;i++)tv[i].resize(c);

//重置第二維長(zhǎng)度（列數(shù)）為c二維vector的每行的列數(shù)可以不一樣for(i=0;i<r;i++)tv[i].resize(i+1);//

定義了一個(gè)下三角矩陣2.4鏈表鏈表概述鏈表用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。鏈表可認(rèn)為是以“結(jié)點(diǎn)的序列”表示的線性表。鏈表中的一個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和指針域兩部分，其中，數(shù)據(jù)域存放數(shù)據(jù)元素，而指針域存放其他結(jié)點(diǎn)的地址。單鏈表結(jié)點(diǎn)類型：structLNode{

//結(jié)點(diǎn)結(jié)構(gòu)體類型

intdata;

//數(shù)據(jù)域

LNode*next;//指針域，用于存放下一個(gè)結(jié)點(diǎn)的地址};2.4鏈表鏈表概述帶頭結(jié)點(diǎn)的單鏈表頭結(jié)點(diǎn)：該結(jié)點(diǎn)的數(shù)據(jù)域不存放有效數(shù)據(jù)頭指針：存放頭結(jié)點(diǎn)的地址的指針變量，通常取名為head鏈表結(jié)束標(biāo)志：空指針NULL，圖中以“∧”表示前驅(qū)與后繼：后繼（后一個(gè)結(jié)點(diǎn)）的地址存放在前驅(qū)（前一個(gè)結(jié)點(diǎn)）的指針域，前驅(qū)的指針域指向后繼單鏈表的訪問規(guī)則：從頭開始、順序訪問何時(shí)宜用鏈表：頻繁進(jìn)行插入和刪除操作2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)帶頭結(jié)點(diǎn)的鏈表的結(jié)構(gòu)體類型LinkListtypedefintElemType;

//定義ElemType為int類型的別名structLinkList{

//聲明鏈表結(jié)構(gòu)體類型

LNode*head;

//頭指針，指向頭結(jié)點(diǎn)

voidInit();

//初始化

voidClear();

//清空鏈表

voidCreate(intn);

//建立含n個(gè)結(jié)點(diǎn)的單鏈表

intLocate(ElemTypee);

//查找

voidInsertBefore(inti,ElemTypee);//插入元素

voidDelete(inti,ElemType&e);

//刪除元素

voidTraverse();

//遍歷

boolEmpty();

//判斷空鏈表};2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)初始化（創(chuàng)建空鏈表）//創(chuàng)建結(jié)點(diǎn)并用頭指針指向，并置其指針域?yàn)榭罩羔?/p>

voidLinkList::Init(){

head=newLNode;

head->next=NULL;}判斷是否空鏈表//若頭指針?biāo)附Y(jié)點(diǎn)的指針域?yàn)榭罩羔槃t返回true，否則返回falseboolLinkList::Empty(){

returnhead->next==NULL;}2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)插入結(jié)點(diǎn)：在第i個(gè)結(jié)點(diǎn)之前插入數(shù)據(jù)域值為e的結(jié)點(diǎn)eaiai-11）指針p指向第i-1個(gè)結(jié)點(diǎn)2）創(chuàng)建一個(gè)新結(jié)點(diǎn)由指針q指向3）q所指結(jié)點(diǎn)數(shù)據(jù)域賦值為e4）修改q所指結(jié)點(diǎn)的next指針值5）修改p所指結(jié)點(diǎn)的next值qp插入結(jié)點(diǎn)對(duì)應(yīng)的工作：2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)插入結(jié)點(diǎn)//在帶頭結(jié)點(diǎn)的單鏈表的第i（1<=i<=n+1）個(gè)結(jié)點(diǎn)之前插入數(shù)據(jù)域值為e的結(jié)點(diǎn)voidLinkList::InsertBefore(inti,ElemTypee){

LNode*

p=head;

while(p&&i>1){

//

找第i-1個(gè)結(jié)點(diǎn)，用p指向該結(jié)點(diǎn)

p=p->next,i--;

}

if(p==NULL||i<1)return;//若i超出范圍，則插入位置非法

LNode*

q=newLNode;//生成新結(jié)點(diǎn)，用q指向該結(jié)點(diǎn)

q->data=e;

q->next=p->next;//新結(jié)點(diǎn)鏈到第i個(gè)結(jié)點(diǎn)之前

p->next=q;

//新結(jié)點(diǎn)鏈到第i-1個(gè)結(jié)點(diǎn)之后}2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)刪除結(jié)點(diǎn)：刪除第i個(gè)結(jié)點(diǎn)（數(shù)據(jù)域值通過引用參數(shù)e返回）eai+1ai-1qp刪除結(jié)點(diǎn)對(duì)應(yīng)的工作：1）指針q指向待刪結(jié)點(diǎn)的前驅(qū)2）指針p指向待刪結(jié)點(diǎn)3）修改q所指結(jié)點(diǎn)的next指針值4）釋放所刪結(jié)點(diǎn)的空間2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)刪除結(jié)點(diǎn)：刪除第i個(gè)結(jié)點(diǎn)（數(shù)據(jù)域值通過引用參數(shù)e返回）//刪除帶頭結(jié)點(diǎn)的單鏈表中第i（1<=i<=n）個(gè)結(jié)點(diǎn)，并用引用參數(shù)e返回其值voidLinkList::Delete(inti,ElemType&e){

LNode*q=head,*p;

intj=0;

//

找到第i-1個(gè)結(jié)點(diǎn)，用q指向該結(jié)點(diǎn)，則q->next指向第i個(gè)結(jié)點(diǎn)

while(q->next&&j<i-1){

q=q->next,

j++;

}

if(!(q->next)||j>i-1)return;//

i超出范圍，刪除位置非法

p=q->next,e=p->data;

q->next=p->next,deletep;//刪除并釋放結(jié)點(diǎn)}2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)清空鏈表//

將單鏈表重新置為一個(gè)空表voidLinkList::Clear(){while(head->next){

LNode*p=head->next;

head->next=p->next;

deletep;

}}2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)查找結(jié)點(diǎn)//

在單鏈表中查找數(shù)據(jù)域值為e的結(jié)點(diǎn)，//若找到，返回指向該結(jié)點(diǎn)的位序，否則返回0intLinkList::Locate(ElemTypee){LNode*p=head->next;inti=1;

while(p){

if(e==p->data)break;

i++,p=p->next;

}

if(!p)return0;

elsereturni;}2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)創(chuàng)建鏈表//創(chuàng)建包含n個(gè)元素的逆序鏈表voidLinkList::Create(intn){

Init();

for(inti=n;i>0;i--){

LNode*

q=newLNode;

cin>>q->data;

q->next=head->next;

head->next=q;

}}逆序鏈表：新結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后，第一個(gè)數(shù)據(jù)結(jié)點(diǎn)之前。2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)遍歷鏈表//遍歷單鏈表voidLinkList::Traverse(){

LNode*p=head->next;

intcnt=0;

while(p){

cnt++;

if(cnt>1)cout<<"";

cout<<p->data;

p=p->next;

}

cout<<endl;}2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)調(diào)用鏈表基本操作#include<iostream>usingnamespacestd;intmain(){

intm,n,t;

LinkListL;

//定義鏈表

L.Init();

//初始化鏈表

cin>>n;

//調(diào)用InsertBefore算法創(chuàng)建順序鏈表，時(shí)間復(fù)雜度為平方階

for(inti=0;i<n;i++){

cin>>t;

L.InsertBefore(i+1,t);

//插入結(jié)點(diǎn)

}2.4鏈表單鏈表基本操作及其實(shí)現(xiàn)調(diào)用鏈表基本操作

L.Traverse();

//遍歷鏈表

cout<<L.Locate(5)<<endl; //查找結(jié)點(diǎn)

L.Delete(5,m);

//刪除結(jié)點(diǎn)

L.Traverse();

//遍歷鏈表

L.Clear();

//清空鏈表

return0;}2.4鏈表其他形式的鏈表循環(huán)單鏈表循環(huán)單鏈表是最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回頭結(jié)點(diǎn)的鏈表。循環(huán)單鏈表和單鏈表的差別僅在于：判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。2.4鏈表其他形式的鏈表雙向鏈表雙向鏈表包含兩個(gè)指針域，其中一個(gè)指向前驅(qū)，另一個(gè)指向后繼。設(shè)雙向鏈表中的指向前驅(qū)的指針域?yàn)閜rior，指向后繼的指針域?yàn)閚ext，則在p所指結(jié)點(diǎn)之后插入一個(gè)q所指的新結(jié)點(diǎn)的語(yǔ)句序列：q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;2.4鏈表其他形式的鏈表雙向鏈表刪除p所指結(jié)點(diǎn)的后繼的語(yǔ)句序列（不考慮釋放所刪結(jié)點(diǎn)的空間）：p->next->next->prior=p;p->next=p->next->next;2.5STL之list基礎(chǔ)知識(shí)STL之list對(duì)應(yīng)雙向鏈表，相當(dāng)于每個(gè)結(jié)點(diǎn)既有后繼指針，又有前驅(qū)指針，則list可以從前往后訪問，也可以從后往前訪問。使用list首先需要包含頭文件list。定義數(shù)據(jù)元素類型為整型的list的代碼：list<int>myList;//用int類型實(shí)例化list2.5STL之list基礎(chǔ)知識(shí)list常用成員函數(shù)2.5STL之list應(yīng)用舉例例2.5.1建立順序鏈表#include<iostream>#include<list>

//

包含list頭文件usingnamespacestd;list<int>createList(intn){//

建立順序鏈表

list<int>myList;

intt;

for(inti=0;i<n;i++){

cin>>t;

myList.push_back(t);//

元素t鏈接到表尾

}

returnmyList;}2.5STL之list應(yīng)用舉例例2.5.1建立順序鏈表voidprtList(list<int>myList){//

輸出鏈表

list<int>::iteratorit;//

迭代器

for(it=myList.begin();it!=myList.end();it++){

if(it!=myList.begin())//

若it所指的不是第一個(gè)數(shù)據(jù)

cout<<"";

//

則先輸出一個(gè)空格

cout<<*it;

//

輸出it所指的數(shù)據(jù)

}

cout<<endl;}2.5STL之list應(yīng)用舉例例2.5.1建立順序鏈表intmain(){

intn;

cin>>n;//

輸入數(shù)據(jù)個(gè)數(shù)

list<int>lst=createList(n);//

建立順序鏈表

prtList(lst);

return0;}2.5STL之list運(yùn)用list實(shí)現(xiàn)大整數(shù)加法例2.5.2大整數(shù)A+B

給定非負(fù)整數(shù)A和B，請(qǐng)計(jì)算A+B的值。要求采用鏈表或list完成。

例如，輸入：222222222222222258944444444444444444

則輸出：58946666666666666666基本思路：兩個(gè)非負(fù)整數(shù)作為字符串輸入，并用輸入的字符串創(chuàng)建逆序鏈表，再根據(jù)“右對(duì)齊、逐位相加”的方法進(jìn)行運(yùn)算。因創(chuàng)建的是逆序鏈表，按從頭開始、順序訪問即可實(shí)現(xiàn)右對(duì)齊逐位相加。另外，在進(jìn)位處理方面，可以用一個(gè)整型變量表示，其初值一開始設(shè)為0，在計(jì)算過程中把其加到當(dāng)前和中，并不斷更新為最新的進(jìn)位。2.5STL之list運(yùn)用list實(shí)現(xiàn)大整數(shù)加法例2.5.2大整數(shù)A+Blist<int>bigAddList(list<int>La,list<int>Lb){

list<int>Lc;

list<int>::iteratorit1,it2;

it1=La.begin(),it2=Lb.begin();

intcarry=0;

//保存進(jìn)位

//當(dāng)兩個(gè)鏈表沒有處理完畢時(shí)，逐位相加

while(it1!=La.end()||it2!=Lb.end()){

intc=carry;

//c暫存當(dāng)前和

if(it1!=La.end()){

c=c+*it1,it1++;

}2.5STL之list運(yùn)用list實(shí)現(xiàn)大整數(shù)加法例2.5.2大整數(shù)A+B

if(it2!=Lb.end()){

c=c+*it2;

it2++;

}

carry=c/10;

//求得新的進(jìn)位

Lc.push_front(c%10);

}

if(carry>0)Lc.push_front(carry);//處理最后的進(jìn)位

returnLc;}2.5STL之list運(yùn)用list實(shí)現(xiàn)大整數(shù)加法例2.5.2大整數(shù)A+B#include<iostream>#include<list>include<string>usingnamespacestd;intmain(){

strings,t;

cin>>s>>t;

//非負(fù)整數(shù)作為字符串輸入

list<int>La,Lb,Lc;

for(inti=0;i<s.size();i++){

//創(chuàng)建第一個(gè)逆序鏈表

La.push_front(s[i]-'0');

}

2.5STL之list運(yùn)用list實(shí)現(xiàn)大整數(shù)加法例2.5.2大整數(shù)A+B

for(inti=0;i<t.size();i++){//創(chuàng)建第二個(gè)逆序鏈表

Lb.push_front(t[i]-'0');

}

Lc=bigAddList(La,Lb);//調(diào)用bigAddList求解兩個(gè)整數(shù)相加list<int>::iteratorit;

//遍歷輸出結(jié)果

for(it=Lc.begin();it!=Lc.end();it++){

cout<<*it;

}

cout<<endl;

return0;}2.6在線題目求解例2.6.1順序表的就地逆置

試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表(a1,a2,……,an)逆置為(an,an-1,……,a1)。輸入:

測(cè)試數(shù)據(jù)有多組，處理到文件尾。每組測(cè)試數(shù)據(jù)在一行上輸入數(shù)據(jù)個(gè)數(shù)n（n≤15）及n個(gè)整數(shù)。輸出:

對(duì)于每組測(cè)試，將順序表中的元素逆置存儲(chǔ)于原表后輸出。每?jī)蓚€(gè)整數(shù)間留一個(gè)空格。輸入樣例:123222882575295418983241輸出樣例:1248389415297525882232實(shí)現(xiàn)順序表的就地逆置的一種算法思想是以中間位置為界，逐個(gè)交換左右對(duì)稱位置上的元素。順序表的初始化、創(chuàng)建、遍歷的實(shí)現(xiàn)與前述類似。2.6在線題目求解例2.6.1順序表的就地逆置typedefintElemType;structSqList{ElemType*elem;intlength;voidInit(intn);voidCreate(intn);voidTraverse();};2.6在線題目求解例2.6.1順序表的就地逆置//逆置順序表，因需把逆置之后的結(jié)果返回，故使用引用參數(shù)voidreverseSqList(SqList&sl){for(inti=0;i<sl.length/2;i++){swap(sl.elem[i],sl.elem[sl.length-1-i]);}}2.6在線題目求解例2.6.1順序表的就地逆置intmain(){intn;while(cin>>n){SqListsl;sl.Create(n);reverseSqList(sl);sl.Traverse();}return0;}2.6在線題目求解例2.6.1順序表的就地逆置//遍歷順序表voidSqList::Traverse(){for(ElemType*p=elem;p<elem+length;p++)

{if(p!=elem)cout<<"";cout<<*p;}cout<<endl;}2.6在線題目求解例2.6.1順序表的就地逆置//初始化順序表voidSqList::Init(intn)

{

elem=newElemType[n];

length=0;}//建立順序表voidSqList::Create(intn)

{

Init(n);

for(ElemType*p=elem;p<elem+n;p++)

{

cin>>*p;

length++;

}}2.6在線題目求解例2.6.2合并升序單鏈表

各依次輸入遞增有序若干個(gè)不超過100的整數(shù)，分別建立兩個(gè)單鏈表，將這兩個(gè)遞增的有序單鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間，不另外占用其他的存儲(chǔ)空間；且合并后的單鏈表中不允許包含重復(fù)的數(shù)據(jù)。然后輸出合并后的單鏈表。輸入:

首先輸入一個(gè)整數(shù)T，表示測(cè)試數(shù)據(jù)的組數(shù)，然后是T組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)首先在第一行輸入數(shù)據(jù)個(gè)數(shù)n；再在第二行和第三行分別輸入n個(gè)依次遞增有序的不超過100的整數(shù)。輸出:

對(duì)于每組測(cè)試，輸出合并后的單鏈表，每?jī)蓚€(gè)數(shù)據(jù)之間留一個(gè)空格。2.6在線題目求解例2.6.2合并升序單鏈表輸入樣例:115141619222331336768757678819195232526373839465255687578798692輸出樣例:14161922232526313337383946525567687576787981869192952.6在線題目求解例2.6.2合并升序單鏈表算法思想：從頭開始分別用一個(gè)指針指向兩個(gè)鏈表中的當(dāng)前元素，然后逐個(gè)比較兩個(gè)鏈表中的當(dāng)前元素，把其中的小者鏈接到結(jié)果鏈表的尾部。因題目要求不能包含重復(fù)的元素，在兩個(gè)當(dāng)前元素相等時(shí)，把其中一個(gè)鏈接到結(jié)果鏈表中的同時(shí)需跳過另一個(gè)鏈表中的相同元素。2.6在線題目求解例2.6.2合并升序單鏈表#include<iostream>usingnamespacestd;typedefintElemType;structLNode{

ElemTypedata;

//數(shù)據(jù)域

LNode*next;

//指針域};structLinkList{

LNode*head;

//頭指針(帶頭結(jié)點(diǎn))

voidCreate(intn);

//建立含n個(gè)結(jié)點(diǎn)的單鏈表

voidTraverse();

//遍歷，并輸出內(nèi)容};2.6在線題目求解例2.6.2合并升序單鏈表//合并升序鏈表voidmergeList(LinkList&La,LinkList&Lb,LinkList&Lc){

LNode*pa,*pb,*pc;

pa=La.head->next;

//

pa指向第一個(gè)鏈表La的首元素

pb=Lb.head->next;

//

pb指向第二個(gè)鏈表Lb的首元素

pc=Lc.head=La.head;//

用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)

while(pa&&pb){//

當(dāng)兩個(gè)鏈表都沒有結(jié)束時(shí)處理

if(pa->data<pb->data){

pc->next=pa,pc=pa,pa=pa->next;

}2.6在線題目求解例2.6.2合并升序單鏈表

elseif(pa->data>pb->data){

pc->next=pb,pc=pb,pb=pb->next;

}

else{

pc->next=pa,pc=pa,pa=pa->next;

LNode*q=pb->next;

deletepb;

pb=q;

}

}

pc->next

=

pa

?

pa

:

pb;//

插入La或Lb中的剩余結(jié)點(diǎn)

deleteLb.head;

//

釋放Lb的頭結(jié)點(diǎn)}2.6在線題目求解例2.6.2合并升序單鏈表intmain(){

intT;

cin>>T;

while(T--){

LinkLista,b,c;

intn;

cin>>n;

a.Create(n);

b.Create(n);

mergeList(a,b,c);

c.Traverse();

}

return0;}2.6在線題目求解例2.6.2合并升序單鏈表//創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表voidLinkList::Create(intn){

head=newLNode;

//創(chuàng)建頭結(jié)點(diǎn)

head->next=NULL;

//頭結(jié)點(diǎn)的指針域置為空指針

LNode*q=head;

//q為尾指針，指向尾結(jié)點(diǎn)

for(inti=0;i<n;i++){

LNode*

p=newLNode;

cin>>p->data;//輸入元素值

p->next=NULL;

q->next=p;

//新結(jié)點(diǎn)鏈接到尾結(jié)點(diǎn)之后

q=p;

//q指向新的尾結(jié)點(diǎn)

}}2.6在線題目求解例2.6.2合并升序單鏈表//遍歷鏈表voidLinkList::Traverse()

{

LNode*p=head->next;

intcnt=0;

while(p){

cnt++;

if(cnt>1)cout<<"";

cout<<p->data;

p=p->next;

}

cout<<endl;}2.6在線題目求解例2.6.3單鏈表中重復(fù)元素的刪除

按照數(shù)據(jù)輸入的順序建立一個(gè)單鏈表，并將單鏈表中重復(fù)的元素刪除（值相同的元素只保留最早輸入的那一個(gè)）。輸入:

測(cè)試數(shù)據(jù)有多組，處理到文件尾。對(duì)于每組測(cè)試，第一行輸入元素個(gè)數(shù)n；第二行輸入n個(gè)整數(shù)。輸出:

對(duì)于每組測(cè)試，輸出兩行，第一行輸出刪除重復(fù)元素后的單鏈表元素個(gè)數(shù)；第二行輸出刪除重復(fù)元素后的單鏈表。輸入樣例:1021301455326311305530輸出樣例:7213014553263112.6在線題