线性表的基本操纵

_实验二 线性表的基本操作一、实验目的1．掌握用C++/C语言调试程序的基本方法。2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。感谢阅读二、实验要求1．C++/C完成算法设计和程序设计并上机调试通过。感谢阅读2．撰写实验报告，提供实验结果和数据。3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。感谢阅读三、实验内容：1.分析并运行以下各子程序的主要功能。程序1：顺序存储的线性表和运算#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.分析并运行以下各子程序的主要功能。程序2链式存储的线性表和运算#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");}运行以下程序并分析各子函数的主要功能。#include<stdio.h>谢谢阅读#include<stdlib.h>structtagNode{intdata;structtagNode*pNext;};typedefstructtagNode* pNode;感谢阅读//将结点插入到链表的适当位置，这是一个降序排列的链表感谢阅读//voidinsertList(pNodehead,//链表头结点感谢阅读pNodepnode)//要插入的结点{_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)//如果要插入的结点最小感谢阅读{pPri->pNext=pnode;}}//输出链表voidprintLinkedList(pNodehead)感谢阅读{pNodetemp=head->pNext;while(temp!=NULL){_printf("%d ",temp->data);temp=temp->pNext;}}//从链表中删除结点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;//比较好的习惯就是分配好空间，马上赋值谢谢阅读printf("请输入要放入链表中的数据，以-1结尾：");谢谢阅读//读入数据，以-1结尾，把数据插入链表中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");//下面的代码当删除函数编写成功后，可以取消注释，让其执行,主要是调用函数实现链表精品文档放心下载结点的删除//printf("请输入要删除数，以-1结尾：");感谢阅读//scanf("%d",&temp);//while(temp!=-1)//{// delformList(head,temp);感谢阅读// scanf("%d",&temp);//}//printf("删除节点后，链表中剩余数据为：");感谢阅读//printLinkedList(head);//printf("\n");}四、思考与提高试将以上链表改为有序表，并分析有序表有哪些显著的优点和缺点？感谢阅读库函数载和常量定义：（代码,C++）#include<iostream>usingnamespacestd;constintMaxSize=100;_（1）顺序表存储结构的定义(类的声明)：（代码）template<classdatatype> //定义模板类SeqList感谢阅读classSeqList{public:SeqList(); //无参构造函数SeqList(datatypea[],intn); //有参构造函数谢谢阅读~SeqList(){}; //析构函数为空intLength(); //求线性表的长度datatypeGet(inti); //按位查找，取线性表的第i个元素精品文档放心下载intLocate(datatypeitem);//查找元素item感谢阅读voidInsert(inti,datatypeitem);//在第i个位置插入元素item谢谢阅读datatypeDelete(inti); //删除线性表的第i个元素精品文档放心下载voiddisplay(); //遍历线性表，按序号依次输出各元素谢谢阅读private:datatypedata[MaxSize]; //存放数据元素的数组感谢阅读intlength; //线性表的长度};（2）初始化顺序表算法实现（不带参数的构造函数）/**输 入：无*前置条件：顺序表不存在*功 能：构建一个顺序表*输 出：无*后置条件：表长为0*/实现代码：template<classdatatype>SeqList<datatype>::SeqList()谢谢阅读{length=0;}（3）顺序表的建立算法（带参数的构造函数）/**输 入：顺序表信息的数组形式a[],顺序表长度n精品文档放心下载*前置条件：顺序表不存在*功 能：将数组a[]中元素建为长度为n的顺序表精品文档放心下载*输 出：无*后置条件：构建一个顺序表*/实现代码：template<classdatatype>SeqList<datatype>::SeqList(datatypea[],intn)谢谢阅读{if(n>MaxSize){cout<<"数组元素个数不合法"<<endl;}for(inti=0;i<n;i++)data[i]=a[i];length=n;}（4）在顺序表的第i个位置前插入元素e算法谢谢阅读_/**输 入：插入元素e,插入位置i*前置条件：顺序表存在，i要合法*功 能：将元素e插入到顺序表中位置i处*输 出：无*后置条件：顺序表插入新元素，表长加1*/实现代码：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个元素算法/**输 入：要删除元素位置i*前置条件：顺序表存在,i要合法*功 能：删除顺序表中位置为i的元素*输 出：无*后置条件：顺序表册除了一个元素，表长减1*/实现代码：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];//获得要删除的元素值精品文档放心下载for(j=i;j<length;j++)data[j-1]=data[j];length--;returnitem;}（6）遍历线性表元素算法/**输 入：无*前置条件：顺序表存在*功 能：顺序表遍历*输 出：输出所有元素

//注意数组下标从0记*后置条件：无*/_实现代码：template<classdatatype>voidSeqList<datatype>::display()精品文档放心下载{if(length==0){cout<<"表为空，无法输出!"<<endl;}for(inti=0;i<length;i++){cout<<data[i]<<" ";}}（7）获得线性表长度算法/**输 入：无*前置条件：顺序表存在*功 能：输出顺序表长度*输 出：顺序表长度*后置条件：无*/实现代码：template<classdatatype>intSeqList<datatype>::Length()感谢阅读{returnLength;}（8）在顺序线性表中查找e值，返回该元素的位序算法精品文档放心下载/**输 入：查询元素值e*前置条件：顺序表存在*功 能：按值查找值的元素并输出位置*输 出：查询元素的位置*后置条件：无*/实现代码：template<classdatatype>intSeqList<datatype>::Locate(datatypeitem)谢谢阅读{for(inti=0;i<length;i++)感谢阅读if(data[i]==item)returni+1;//下标为i的元素等于item，返回其序号i+1感谢阅读return0; //查找失败}（9）获得顺序线性表第i个元素的值/**输 入：查询元素位置i*前置条件：顺序表存在，i要合法*功 能：按位查找位置为i的元素并输出值*输 出：查询元素的值*后置条件：无*/_实现代码：template<classdatatype>datatypeSeqList<datatype>::Get(inti)精品文档放心下载{if(i<0||i>length){cout<<"i不合法!"<<endl;}elsereturndata[i-1];}（10）判表空算法/**输 入：无*前置条件：无*功 能：判表是否为空*输 出：为空返回1，不为空返回0*后置条件：无*/实现代码：template<classdatatype>boolSeqList<datatype>::Empty()精品文档放心下载{if(length==0){return1;}else{return0;}}(11)求直接前驱结点算法/**输 入：要查找的元素e，待存放前驱结点值e1*前置条件：无*功 能：查找该元素的所在位置，获得其前驱所在位置。感谢阅读*输 出：返回其前驱结点的位序。*后置条件：e1值为前驱结点的值*/实现代码：template<classdatatype>intSeqList<datatype>::Pre(datatypeitem)谢谢阅读{intk=Locate(item)-1;if(k>0)returnk;else{cout<<"无前驱结点！"<<endl;return0;}}(12)求直接后继结点算法_/**输 入：要查找的元素e，待存放后继结点值e1*前置条件：无*功 能：查找该元素的所在位置，获得其后继所在位置。精品文档放心下载*输 出：返回其后继结点的位序。*后置条件：e1值为后继结点的值*/实现代码：template<classdatatype>intSeqList<datatype>::Suc(datatypeitem)感谢阅读{intk=Locate(item)+1;if(k>length){cout<<"无后继结点!"<<endl;return0;}else{returnk;}}上机实现以上基本操作，写出main()程序：用以上基本操作算法，实现A=AUB算法。（利用函数模板实现）感谢阅读/**输 入：集合A,集合B*前置条件：无*功 能：实现A=AUB*输 出：无*后置条件：A中添加了B中的元素。*/实现代码：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的结果是:"<<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;}实现代码：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[