线性表的基本操作

实验二线性表的基本操作一、实验目的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");}3.运行以下程序并分析各子函数的主要功能。#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>//定义模板类SeqListclassSeqList{public:SeqList();//无参构造函数SeqList(datatypea[],intn);//有参构造函数~SeqList(){};//析构函数为空intLength();//求线性表的长度datatypeGet(inti);//按位查找，取线性表的第i个元素intLocate(datatypeitem);//查找元素itemvoidInsert(inti,datatypeitem);//在第i个位置插入元素itemdatatypeDelete(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];//注意数组下标从0记 length--; returnitem;}（6）遍历线性表元素算法/**输入：无*前置条件：顺序表存在*功能：顺序表遍历*输出：输出所有元素*后置条件：无*/实现代码：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[k-1]; data[i+1]=item; length++; break; } if(data