實(shí)驗(yàn)二線性表的基本操作一、實(shí)驗(yàn)?zāi)康?．掌握用C++/C語言調(diào)試程序的基本方法。2．掌握線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的基本運(yùn)算，如插入、刪除等。二、實(shí)驗(yàn)要求1．C++/C完成算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過。2．撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)結(jié)果和數(shù)據(jù)。3．分析算法，要求給出具體的算法分析結(jié)果，包括時(shí)間復(fù)雜度和空間復(fù)雜度，并簡(jiǎn)要給出算法設(shè)計(jì)小結(jié)和心得。三、實(shí)驗(yàn)內(nèi)容：1.分析并運(yùn)行以下各子程序的主要功能。程序1：順序存儲(chǔ)的線性表和運(yùn)算#include<stdio.h>#defineMAXSIZE100intlist[MAXSIZE];intn;/*insertinaseqlist*/intsq_insert(intlist[],int*p_n,inti,intx){intj; if(i<0||i>*p_n)return(1); if(*p_n==MAXSIZE)return(2); for(j=*p_n+1;j>i;j--) list[j]=list[j-1]; list[i]=x; (*p_n)++; return(0); }/*deleteinaseqlist*/intsq_delete(intlist[],int*p_n,inti) {intj; if(i<0||i>=*p_n)return(1); for(j=i+1;j<=*p_n;j++) list[j-1]=list[j]; (*p_n)--; return(0); }voidmain() {inti,x,temp; printf("pleaseinputthenumberforn\n"); printf("n="); scanf("%d",&n); for(i=0;i<=n;i++) {printf("list[%d]=",i); scanf("%d",&list[i]);} printf("Thelistbeforeinsertionis\n"); for(i=0;i<=n;i++)printf("%d",list[i]); printf("\n"); printf("pleaseinputthepositionwhereyouwanttoinsertavalue\nposition="); scanf("%d",&i); printf("pleaseinputthevalueyouwanttoinsert.\nx="); scanf("%d",&x); temp=sq_insert(list,&n,i,x); switch(temp) {case0:printf("Theinsertionissuccessful!\n"); printf("Thelistisafterinsertionis\n"); for(i=0;i<=n;i++)printf("%d",list[i]); printf("\n"); printf("%d\n",n); break; case1: case2:printf("Theinsertionisnotsuccessful!\n");break;} /*deleting*/ printf("Thelistbeforedeletingis\n"); for(i=0;i<=n;i++)printf("%d",list[i]); printf("\n"); printf("pleaseinputthepositionwhereyouwanttodeleteavalue\nposition="); scanf("%d",&i); temp=sq_delete(list,&n,i); switch(temp) {case0:printf("Thedeletingissuccessful!\n"); printf("Thelistisafterdeletingis\n"); for(i=0;i<=n;i++)printf("%d",list[i]); printf("\n"); printf("%d",n); break; case1:printf("Thedeletingisnotsuccessful!");break;} }2.分析并運(yùn)行以下各子程序的主要功能。程序2鏈?zhǔn)酱鎯?chǔ)的線性表和運(yùn)算#include<stdio.h>#include<malloc.h>structnode{ chardata; structnode*next; };typedefstructnodeNODE;/*Thisfunctioncreatesalink_listwithNnodes.*/NODE*create_link_list(intn){inti; NODE*head,*p,*q; if(n==0)returnNULL; head=(NODE*)malloc(sizeof(NODE)); p=head;printf("Pleaseinput%dcharsforthelinklist\n",n); for(i=0;i<n;i++) {scanf("%c",&(p->data)); q=(NODE*)malloc(sizeof(NODE)); printf("test3\n"); p->next=q; p=q;} scanf("%c",&(p->data)); getchar(); p->next=NULL; return(head);}/*Thisfunctioninsertsanodewhosevalueisb*//*beforethenodewhosevalueisa,ifthenodeisnotexist,*//*theninsertitattheendofthelist*/voidinsert(NODE**p_head,chara,charb) {NODE*p,*q; q=(NODE*)malloc(sizeof(NODE)); q->data=b; q->next=NULL; if(*p_head==NULL)*p_head=q; else {p=(NODE*)malloc(sizeof(NODE)); p=*p_head; while(p->data!=a&&p->next!=NULL) p=p->next; q->next=p->next; p->next=q;} }/*Thefunctiondeletesthenodewhosevalueisa,*//*ifsuccess,return0,orreturn1*/intdeletenode(NODE**p_head,chara) {NODE*p,*q; q=*p_head; if(q==NULL)return(1); if(q->data==a) {*p_head=q->next; free(q); return(0);} else {while(q->data!=a&&q->next!=NULL) {p=q; q=q->next;} if(q->data==a) {p->next=q->next; free(q); return(0);} elsereturn(1);} }voidmain(){ NODE*my_head,*p; /*createalinklistwithmnodes*/ intm; charch_a,ch_b; printf("pleaseinputthenumberofnodesforthelink_list\nm="); scanf("%d",&m); getchar(); printf("test1\n"); my_head=(NODE*)malloc(sizeof(NODE)); my_head=create_link_list(m);/*Outputthelinklist*/ printf("Thelinklistislike:\n"); p=my_head; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");/*insertanodewhosevalueisbbeforea*/ printf("Pleaseinputthepositionfora\nch_a="); getchar(); scanf("%c",&ch_a); getchar(); printf("Pleaseinputthevaluethatyouwanttoinsert\nch_b="); scanf("%c",&ch_b); getchar(); insert(&my_head,ch_a,ch_b); printf("Thelinklistafterinsertionislike:\n"); p=my_head; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");/*deleteanodewhosevalueisa*/ printf("Pleaseinputthepositionforaa="); scanf("%c",&ch_a); getchar(); deletenode(&my_head,ch_a); printf("Thelinklistafterdeletingislike:\n"); p=my_head; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");}3.運(yùn)行以下程序并分析各子函數(shù)的主要功能。#include<stdio.h>#include<stdlib.h>structtagNode{ intdata; structtagNode*pNext;};typedefstructtagNode*pNode;//將結(jié)點(diǎn)插入到鏈表的適當(dāng)位置，這是一個(gè)降序排列的鏈表//voidinsertList(pNodehead,//鏈表頭結(jié)點(diǎn) pNodepnode)//要插入的結(jié)點(diǎn){ pNodepPri=head; while(pPri->pNext!=NULL) { if(pPri->pNext->data<pnode->data) { pnode->pNext=pPri->pNext; pPri->pNext=pnode; break; } pPri=pPri->pNext; } if(pPri->pNext==NULL)//如果要插入的結(jié)點(diǎn)最小 { pPri->pNext=pnode; }}//輸出鏈表voidprintLinkedList(pNodehead){ pNodetemp=head->pNext; while(temp!=NULL) { printf("%d",temp->data); temp=temp->pNext; }}//從鏈表中刪除結(jié)點(diǎn)voiddelformList(pNodehead,intdata){ pNodetemp=head->pNext; pNodepPri=head; while(temp!=NULL) { if(temp->data==data) { pPri->pNext=temp->pNext; free(temp); break; } pPri=temp; temp=temp->pNext; }}voidmain(){ pNodehead=(pNode)malloc(sizeof(structtagNode));//給頭指針分配空間 pNodepTemp=NULL; inttemp; head->pNext=NULL;//比較好的習(xí)慣就是分配好空間，馬上賦值 printf("請(qǐng)輸入要放入鏈表中的數(shù)據(jù)，以-1結(jié)尾："); //讀入數(shù)據(jù)，以-1結(jié)尾，把數(shù)據(jù)插入鏈表中 scanf("%d",&temp); while(temp!=-1) { pTemp=(pNode)malloc(sizeof(structtagNode)); pTemp->data=temp; pTemp->pNext=NULL; insertList(head,pTemp); scanf("%d",&temp); } printf("降序排列的鏈表為：\n"); printLinkedList(head); printf("\n");//下面的代碼當(dāng)刪除函數(shù)編寫成功后，可以取消注釋，讓其執(zhí)行,主要是調(diào)用函數(shù)實(shí)現(xiàn)鏈表結(jié)點(diǎn)的刪除//printf("請(qǐng)輸入要?jiǎng)h除數(shù)，以-1結(jié)尾：");//scanf("%d",&temp); //while(temp!=-1)//{// delformList(head,temp);// scanf("%d",&temp);//}//printf("刪除節(jié)點(diǎn)后，鏈表中剩余數(shù)據(jù)為：");//printLinkedList(head);//printf("\n");}四、思考與提高試將以上鏈表改為有序表，并分析有序表有哪些顯著的優(yōu)點(diǎn)和缺點(diǎn)？庫函數(shù)載和常量定義：（代碼,C++）#include<iostream>usingnamespacestd;constintMaxSize=100;（1）順序表存儲(chǔ)結(jié)構(gòu)的定義(類的聲明)：（代碼）template<classdatatype>//定義模板類SeqListclassSeqList{public:SeqList();//無參構(gòu)造函數(shù)SeqList(datatypea[],intn);//有參構(gòu)造函數(shù)~SeqList(){};//析構(gòu)函數(shù)為空intLength();//求線性表的長(zhǎng)度datatypeGet(inti);//按位查找，取線性表的第i個(gè)元素intLocate(datatypeitem);//查找元素itemvoidInsert(inti,datatypeitem);//在第i個(gè)位置插入元素itemdatatypeDelete(inti);//刪除線性表的第i個(gè)元素voiddisplay();//遍歷線性表，按序號(hào)依次輸出各元素private:datatypedata[MaxSize];//存放數(shù)據(jù)元素的數(shù)組intlength;//線性表的長(zhǎng)度};（2）初始化順序表算法實(shí)現(xiàn)（不帶參數(shù)的構(gòu)造函數(shù)）/**輸入：無*前置條件：順序表不存在*功能：構(gòu)建一個(gè)順序表*輸出：無*后置條件：表長(zhǎng)為0*/實(shí)現(xiàn)代碼：template<classdatatype>SeqList<datatype>::SeqList(){length=0;}（3）順序表的建立算法（帶參數(shù)的構(gòu)造函數(shù)）/**輸入：順序表信息的數(shù)組形式a[],順序表長(zhǎng)度n*前置條件：順序表不存在*功能：將數(shù)組a[]中元素建為長(zhǎng)度為n的順序表*輸出：無*后置條件：構(gòu)建一個(gè)順序表*/實(shí)現(xiàn)代碼：template<classdatatype>SeqList<datatype>::SeqList(datatypea[],intn){ if(n>MaxSize) { cout<<"數(shù)組元素個(gè)數(shù)不合法"<<endl; } for(inti=0;i<n;i++) data[i]=a[i]; length=n;}（4）在順序表的第i個(gè)位置前插入元素e算法/**輸入：插入元素e,插入位置i*前置條件：順序表存在，i要合法*功能：將元素e插入到順序表中位置i處*輸出：無*后置條件：順序表插入新元素，表長(zhǎng)加1*/實(shí)現(xiàn)代碼：template<classdatatype>voidSeqList<datatype>::Insert(inti,datatypeitem){ intj; if(length>=MaxSize) { cout<<"溢出"<<endl; } if(i<1||i>length+1) { cout<<"i不合法！"<<endl; } for(j=length;j>=i;j--) data[j]=data[j-1]; data[i-1]=item; length++;}（5）刪除線性表中第i個(gè)元素算法/**輸入：要?jiǎng)h除元素位置i*前置條件：順序表存在,i要合法*功能：刪除順序表中位置為i的元素*輸出：無*后置條件：順序表冊(cè)除了一個(gè)元素，表長(zhǎng)減1*/實(shí)現(xiàn)代碼：template<classdatatype>datatypeSeqList<datatype>::Delete(inti){ intitem,j; if(length==0) { cout<<"表為空,無法刪除元素!"<<endl; } if(i<1||i>length) { cout<<"i不合法!"<<endl; } item=data[i-1];//獲得要?jiǎng)h除的元素值 for(j=i;j<length;j++) data[j-1]=data[j];//注意數(shù)組下標(biāo)從0記 length--; returnitem;}（6）遍歷線性表元素算法/**輸入：無*前置條件：順序表存在*功能：順序表遍歷*輸出：輸出所有元素*后置條件：無*/實(shí)現(xiàn)代碼：template<classdatatype>voidSeqList<datatype>::display(){ if(length==0) { cout<<"表為空，無法輸出!"<<endl; } for(inti=0;i<length;i++) { cout<<data[i]<<""; }}（7）獲得線性表長(zhǎng)度算法/**輸入：無*前置條件：順序表存在*功能：輸出順序表長(zhǎng)度*輸出：順序表長(zhǎng)度*后置條件：無*/實(shí)現(xiàn)代碼：template<classdatatype>intSeqList<datatype>::Length(){ returnLength;}（8）在順序線性表中查找e值，返回該元素的位序算法/**輸入：查詢?cè)刂礶*前置條件：順序表存在*功能：按值查找值的元素并輸出位置*輸出：查詢?cè)氐奈恢?后置條件：無*/實(shí)現(xiàn)代碼：template<classdatatype>intSeqList<datatype>::Locate(datatypeitem){ for(inti=0;i<length;i++) if(data[i]==item) returni+1; //下標(biāo)為i的元素等于item，返回其序號(hào)i+1 return0;//查找失敗}（9）獲得順序線性表第i個(gè)元素的值/**輸入：查詢?cè)匚恢胕*前置條件：順序表存在，i要合法*功能：按位查找位置為i的元素并輸出值*輸出：查詢?cè)氐闹?后置條件：無*/實(shí)現(xiàn)代碼：template<classdatatype>datatypeSeqList<datatype>::Get(inti){ if(i<0||i>length) { cout<<"i不合法!"<<endl; } elsereturndata[i-1];}（10）判表空算法/**輸入：無*前置條件：無*功能：判表是否為空*輸出：為空返回1，不為空返回0*后置條件：無*/實(shí)現(xiàn)代碼：template<classdatatype>boolSeqList<datatype>::Empty(){ if(length==0) { return1; } else { return0; }}(11)求直接前驅(qū)結(jié)點(diǎn)算法/**輸入：要查找的元素e，待存放前驅(qū)結(jié)點(diǎn)值e1*前置條件：無*功能：查找該元素的所在位置，獲得其前驅(qū)所在位置。*輸出：返回其前驅(qū)結(jié)點(diǎn)的位序。*后置條件：e1值為前驅(qū)結(jié)點(diǎn)的值*/實(shí)現(xiàn)代碼：template<classdatatype>intSeqList<datatype>::Pre(datatypeitem){ intk=Locate(item)-1; if(k>0) returnk; else { cout<<"無前驅(qū)結(jié)點(diǎn)！"<<endl; return0; }}(12)求直接后繼結(jié)點(diǎn)算法/**輸入：要查找的元素e，待存放后繼結(jié)點(diǎn)值e1*前置條件：無*功能：查找該元素的所在位置，獲得其后繼所在位置。*輸出：返回其后繼結(jié)點(diǎn)的位序。*后置條件：e1值為后繼結(jié)點(diǎn)的值*/實(shí)現(xiàn)代碼：template<classdatatype>intSeqList<datatype>::Suc(datatypeitem){ intk=Locate(item)+1; if(k>length) { cout<<"無后繼結(jié)點(diǎn)!"<<endl; return0; } else { returnk; }}上機(jī)實(shí)現(xiàn)以上基本操作，寫出main()程序：用以上基本操作算法，實(shí)現(xiàn)A=AUB算法。（利用函數(shù)模板實(shí)現(xiàn)）/**輸入：集合A,集合B*前置條件：無*功能：實(shí)現(xiàn)A=AUB*輸出：無*后置條件：A中添加了B中的元素。*/實(shí)現(xiàn)代碼：template<classdatatype>SeqList<datatype>SeqList<datatype>::Add(SeqList<datatype>&item){ if(item.Empty()) return*this; else { intk=item.Length(); intnum=this->Length(); for(inti=1;i<=k;i++) { for(intj=0;j<num;j++) if(data[j]==item.Get(i)) { break; } elseif(num-1==j&&data[num-1]!=item.Get(i)) { this->Insert(++num,item.Get(i)); } } return*this; }}voidmain(){ SeqList<int>A,B; cout<<"A∪B的結(jié)果是:"<<endl; A.Insert(1,1); A.Insert(2,2); A.Insert(3,3); A.Insert(4,4); A.Insert(5,5);//插入集合A中元素 B.Insert(1,2); B.Insert(2,6); B.Insert(3,1); B.Insert(4,8); B.Insert(5,9);//插入集合B中元素 A.Add(B); A.display(); cout<<endl;}實(shí)現(xiàn)代碼：template<classdatatype>voidSeqList<datatype>::orderInsert(datatypeitem){ intnum=this->Length(); for(inti=0;i<num;i++) { if((data[i]<item&&data[i+1]>item)) { for(intk=num;k>i;k--) data[k]=data[k-1]; data[i+1]=item; length++; break; } if(data