数据结构_实验一_线性表的操作(一)

待我称王封你为后i 2021-11-23 03:14 267阅读 0赞

一、线性表和链表的基本操作  
 1.1 需求分析  
 1.2 概要设计  
 1.3 详细设计  
 1.4 调试分析  
 1.5 用户使用说明  
 1.6 测试结果  
 1.7 附录

#### 一、线性表和链表的基本操作 ####

###### 1.1 需求分析 ######

A、顺序表的输入形式如下：

（1）顺序表的定位、取值  
输入顺序表  
定位  
数值  
位置  
\-1退出  
取值  
位置  
数值  
0/超出数组大小退出  
（2）顺序表的插入、删除  
随机数组  
Insert  
插入数值 插入位置  
插入后数组  
delete  
删除数据  
删除后的数组  
（3）顺序表的合并  
输入数组1数组2大小  
输出随机数组1  
输出随机数组2  
输出合并的数组

功能：利用顺序表实现线性表的定位、取值、插入、删除和合并

数据范围：1~100  
测试数据：随机数 正确执行各项操作

B、链表的输入形式如下：  
（1）链表的定位  
输入单链表的各个数据，输入-1结束  
输入定位的数值  
输出数值位置  
（2）链表的取值  
输入单链表的各个数据，输入-1结束  
输入位置  
输出该位置的数值  
（3）链表的插入  
输入一个单链表，输入-1结束  
输入插入的数值、位置  
输出插入后的单链表  
（4）链表的删除  
输入一个单链表，输入-1结束  
输入需要删除的数据  
输出删除后的单链表  
（5）链表的合并  
输入按值非递减单链表A，输入-1结束  
输入按值非递减单链表B，输入-2结束  
输出插入后的按值非递减单链表

功能：利用链表实现线性表的定位、取值、插入、删除和合并

数据范围：1~100  
测试数据：正确输入：1~100 正确执行 错误输入：数据超出范围的数据 跳出程序

###### 1.2 概要设计 ######

A、顺序表：

（1）顺序表的定位、取值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]  
（2）顺序表的插入、删除  
生成随机数组→输入插入数值、插入位置→插入位置后面数值往后摞，将插入数值放入插入位置→输出插入后数组→输入删除数据→将该数值的数组后面的数值全部往前放一个→输出删除后的数组

（3）顺序表的合并  
生成随机数组→建立第三个数组，长度为数组1和数组2之和→将数组2复制到数组1后面

B、链表：  
（1）链表的定位  
建立单链表→调用定位函数→输出数值  
（2）链表的取值  
建立单链表→调用取值函数→输出位置  
（3）链表的插入  
建立单链表→调用插入函数→输出插入后的单链表  
（4）链表的删除  
建立单链表→调用删除函数→输出删除后的单链表  
（5）链表的合并  
建立按值非递减单链表AB→调用合并函数→输出合并后的函数

###### 1.3 详细设计 ######

A、顺序表：

（1）顺序表的定位、取值  
创建list\[size\]  
cin>>m  
for循坏判断list\[i\]==m  
if list\[i\]==m ,cout<*>number  
for循坏到list\[number\], cout<<list\[number\]*

（2）顺序表的插入删除  
随机生成数组  
输入插入数值、位置  
for循环到相应位置，将数组的数值后摞一个位置  
将插入数值放入插入位置  
输出插入后的数组  
输入删除数组  
for循环删除该数值，所有后续数值前摞一个位置  
输出删除后的数组

（3）顺序表的合并  
输入数组1，数组2大小  
随机数组1  
随机数组2  
将数组2复制到数组1后面并输出合并后的数组1

B、链表：  
（1）链表的定位  
建立单链表  
cin>>number  
int k=1;  
while(L->next!=NULL)  
\{  
If（结点数据==number）//判断该结点的数据与定位数值是否相等  
cout<<k;  
else  
\{  
L->next=L->next->next; //下一个结点  
k++;  
\}  
\}  
（2）链表的取值  
建立单链表  
输入取值的位置  
循环到相应的位置  
输出该位置的数值  
（3）链表的插入  
建立单链表  
输入插入的数值、位置  
循坏判断下一个结点的数据是否是插入位置  
If（是）  
\{  
新建结点，赋值，指针下一个  
此结点的next指向新建结点  
\}  
else  
\{  
结点指向下一个  
位置+1  
\}  
（4）链表的删除  
建立单链表  
输入需要删除的数据  
循坏判断下一个结点的数值是否为该数据  
If（是）  
\{  
新建结点  
将下一结点的数据、指针赋给新建结点  
此结点指向下一个的下一个  
释放新建结点  
\}  
else  
\{  
此结点指向下一个结点  
\}  
（5）链表的合并  
建立按值非递减单链表AB  
判断AB结点的数值大小  
新建单链表，新建结点  
将小的数值赋给新建结点  
新建结点是单链表的下一个结点

###### 1.4 调试分析 ######

A、顺序表：

算法时间复杂度为n，空间复杂度根据数组大小而定，可以建立动态数组，要求用户输入数组大小。

B、链表：  
时间复杂度n，空间复杂度取决输入数值数量，操作时容易丢失指针，特别是操作第一个数据时，可以新建结点替代需要调用的结点。定位取值等操作单独实现较易，一起实现容易造成指针位置不明。

###### 1.5 用户使用说明 ######

A、顺序表：

（1）顺序表的定位、取值  
当程序输出定位时，用户输入显示数据中的一个，按下回车键，程序会输出该数据所在位置，输入-1跳出循坏；程序输出取值时，用户输入位置，按下回车键，程序会输出该位置的数据，没有该位置时跳出程序。  
（2）顺序表的插入、删除  
程序生成随机数组，提示Insert时，先输入插入的数据，空格输入插入位置，回车输出插入后的数组，提示delete时，输入想删除的数据，回车输出删除后的数组。  
（3）顺序表的合并  
输入数组1和数组2大小即可

B、链表：  
（1）链表的定位  
输入新建链表的数据，遇到-1时结束，提示定位时，输入定位数据，按回车键，输出该位置的数据。  
（2）链表的取值  
输入新建链表的数据，遇到-1时结束，提示取值时，输入位置，按回车键，输出该位置的数据。  
（3）链表的插入  
输入新建链表的数据，遇到-1时结束，提示插入时，输入插入的数据、位置，按回车键，输出插入后后的单链表。  
（4）链表的删除  
输入新建链表的数据，遇到-1时结束，提示删除时，输入删除数据，按回车键，输出删除后的单链表。  
（4）链表的合并  
输入按值非递减链表A的数据，遇到-1时结束，输入按值非递减单链表B的数据，遇到-2时结束，按回车键，输出合并后的按值非递减后的单链表。

###### 1.6 测试结果 ######

A、顺序表：

（1）顺序表的定位、取值  
![在这里插入图片描述][20190725184702567.png]  
（2）顺序表的插入、删除  
![在这里插入图片描述][20190725184731295.png] ![在这里插入图片描述][20190725184739857.png]  
（3）顺序表的合并  
![在这里插入图片描述][20190725184747259.png] ![在这里插入图片描述][20190725184752847.png]

B、链表：  
（1）链表的定位、取值、插入、合并  
![在这里插入图片描述][20190725184759823.png]  
（2）链表的删除  
![在这里插入图片描述][20190725184805766.png]

###### 1.7 附录 ######

A、顺序表：

（1）顺序表的定位、取值

#include<iostream>
    #include<stdlib.h>
    #include<time.h>
    using namespace std;
    int main()
    { 
    	srand(time(0));
    	int list[10];
    	for (int i=0;i<10;i++)           //建立随机数组
    	{ 
    		list[i]=rand()%100+1;
    		cout<<list[i]<<" ";
    	}
    	cout<<endl<<"定位"<<endl;
    	int k;
    	cin>>k;
    	while(k!=-1)               //循坏判定输入数值的位置
    	{ 
    		for (int j=0;j<10;j++)
    		if (list[j]==k)
    			cout<<j+1<<endl;
    		cin>>k;
    	}
    
    	cout<<"取值"<<endl;        //循坏判定输入位置的数值
    	int n;
    	cin>>n;
    	while (n>0&&n<=10)
    	{ 
    		cout<<list[n-1]<<endl;
    		cin>>n;
    	}
    	return 0;
    }

（2）顺序表插入与删除

int insert(int list1[],int num,int position)      
    { 
    	if (position<0||position>10)        //输入插入位置超出数组的数据范围，退出程序
    		return -1;
    	for (int i=9;i>=position-1;i--)        //将插入位置及后面的数据全部后摞一个
    		list1[i+1]=list1[i];
    	list1[position-1]=num;            //将插入数据赋给插入位置
    	for (int j=0;j<11;j++)              //输出插入后的数组
    		cout<<list1[j]<<" ";
    	return 0;
    }
    int deletenum(int list2[],int number)
    { 
    	int m;
    	for (int i=0;i<11;i++)            //循环寻找删除数据的位置 
    	{ 
    		if (number==list2[i])
    		{ 
    			m=i;break;
    		}
    		else if(number!=list2[i]&&i==10)   //超出数组范围，退出程序
    			return -1;
    	}
    	for (int j=m;j<10;j++)                //将删除位置后面的数值全部往前摞一位
    		list2[j]=list2[j+1];
    	for (int k=0;k<10;k++)                //输出删除后的数组
    		cout<<list2[k]<<" ";
    	cout<<endl;
    	return 0;
    }

（3）顺序表的合并

int merge(int list1[],int list2[],int a,int b);
    int main()
    { 
    	srand(time(0));
    	int list1[100],list2[100];
    	int a, b;
    	cout<<"Please enter the size of list1 and list2 : ";
    	cin>>a>>b;
    	cout<<"list1 : ";                   //创建顺序表1
    	for (int i=0;i<a;i++)
    	{ 
    		list1[i]=rand()%100+1;
    		cout<<list1[i]<<" ";
    	}
    	cout<<endl<<"list2 : ";             //创建顺序表2
    	for (int j=0;j<b;j++)
    	{ 
    		list2[j]=rand()%100+1;
    		cout<<list2[j]<<" ";
    	}
    	cout<<endl<<"list3 : ";
    	merge(list1,list2,a,b);
    	return 0;
    }
    int merge(int list1[],int list2[],int a,int b)
    { 
    	for (int i=a;i<a+b;i++)                 //将顺序表2加到顺序表1后面
    		list1[i]=list2[i-a];
    	for (int j=0;j<a+b;j++)                 //输出合并后的顺序表1
    		cout<<list1[j]<<" ";
    	cout<<endl;
    	return 0;
    }

B、链表  
（1）链表的定位、取值、插入、合并

#include<iostream>
    using namespace std;
    
    typedef struct node{                  //建立结构体
    	int date;
    	struct node *next;
    }node;
    
    void print(node *L);                  //打印链表
    int locate(node *L,int number);         //链表定位
    int evaluation(node *L,int i);           //链表的取值
    void insert(node *L,int number,int i);    //链表的插入
    //void deleten(node *L,int number); //链表的删除
    void merge(node *L1,node *L2);       //链表的合并
    
    
    int main()
    { 
        node *p, *r, *L;
    	int number, i;
    	
    	L=new node;
    	r=L;
    	
    	cin>>number;
    	while (number!=-1)             //新建链表L
    	{ 
    		p=new node;
    		p->date=number;
    		r->next=p;
    		r=p;
    		cin>>number;
    	}
    	r->next=NULL;
    
    	cout<<endl<<"定位"<<endl<<"输入定位的数值 : ";
    	cin>>number;
        locate(L,number);                                 //链表定位
    	cout<<endl<<"取值"<<endl<<"输入取值的位置 : ";
    	cin>>i;
    	evaluation(L,i);                                   //链表的取值
    	cout<<endl<<endl<<"插入"<<endl<<"输入插入的数值、位置 : ";
    	cin>>number>>i;
    	insert(L,number,i);                             //链表的插入
    
    	cout<<endl<<"合并"<<endl;                     //链表合并
    	node *L1, *L2, *p1, *p2, *r1, *r2;
    	int number1, number2;
    	L1=new node;
    	r1=L1;
    	L2=new node;
    	r2=L2;
    	cin>>number1;
    	while (number1!=-1)                 //新建链表1
    	{ 
    		p1=new node;
    		p1->date=number1;
    		r1->next=p1;
    		r1=p1;
    		cin>>number1;
    	}
    	r1->next=NULL;
    	cin>>number2;
    	while (number2!=-2)               //新建链表2
    	{ 
    		p2=new node;
    		p2->date=number2;
    		r2->next=p2;
    		r2=p2;
    		cin>>number2;
    	}
    	r2->next=NULL;
        merge(L1,L2);                 //链表1、2的合并
    	return 0;
    }
    
    void print(node *L)                  //打印链表
    { 
    	while (L->next!=NULL)           //下一个结点为空时跳出
    	{ 
    		cout<<L->next->date<<" ";   //输出此结点的数据
    		L->next=L->next->next;     //转到下一个结点
    	}
    	cout<<endl;
    }
    
    int locate(node *L,int number)   //链表定位
    { 
        node *r;
        r=L->next;
    	int i=0;
    	while (r!=NULL)               //结点为空时跳出循坏
    	{ 
    		if ((r->date)==number)     //判断此结点的数据是否为定位数据 
    		{ 
    			cout<<++i<<endl;
    			break;
    		}
    		else
    		{ 
    			++i;                 //位置加1
    			r=r->next;            //指针指向下一个结点
    		}
    	}
    	return i;
    }
    
    int evaluation(node *L,int i)       //链表的取值
    { 
        node *r;
        r=L->next;
    	int j=1;
    	while (r!=NULL)           //结点为空时跳出循坏
    	{ 
    		if (j==i)
    		{ 
    			cout<<r->date;   //输出该位置的数据
    			break;
    		}
    		else
    		{ 
    			++j;            //位置+1
    			r=r->next;       //指针指向下一个结点
    		}
    	}
    	return 0;
    }
    
    void insert(node *L,int number,int i)  //链表的插入
    { 
    	node *p, *r, *t;
    	if(i==1)                   //如果插入位置为第一个时
        { 
            p=new node;       
            p->date=number;      //将数据赋给新建结点的数据域
            p->next=L->next;      //头指针指向下一个的下一个
            p=L;                //将头指针赋给p
        }
        else
        { 
            r=L->next;
    	    int k=1;
    	    while (r!=NULL)      //结点为空时跳出循坏
    	    { 
    	     	if (k+1==i)       //如果下一个结点是插入位置
    	     	{ 
    		    	p=new node;       //新建结点
    		    	p->date=number;   //数值赋给数据域
    			    p->next=r->next;    //指针指向下一个的下一个
    			    r->next=p;         //指针指向新结点
    		    	r=p;              //将新结点赋给此结点
    		    	break;            //跳出循坏
    	     	}
    	    	else
    		    { 
    		    	r=r->next;        //指针指向下一个
    		    	++k;            //位置+1
    	    	}
    	    }
        }
    	print(L);                    //输出插入后的链表
    }
    
    void merge(node *L1,node *L2)   //链表的合并
    { 
    	node *p, *r1, *r2, *L3, *p3, *r3;
    	L3=new node;
    	r3=L3;
    	r1=L1;
    	r2=L2;
    	while (r1->next!=NULL&&r2->next!=NULL)    //两个链表中的一个结点为空时跳出循坏
    	{ 
    		if (r1->next->date<r2->next->date)       //链表1的数据小于链表2的数据
    		{ 
    			p=new node;             //新建结点
    			p->date=r1->next->date;    //将链表1的数据赋给新建结点的数据域
    			r3->next=p;              //链表3的指针指向新建结点
    			r3=p;                   //将新建结点赋给链表3的结点
    			r1->next=r1->next->next;   //链表1的指针指向下一个结点的指针域
    		}
    		else if (r1->next->date==r2->next->date)  //链表1的数据与链表2的数据
    		{ 
    			p=new node;                    //新建结点
    			p->date=r1->next->date;           //将链表1的的数据赋给新结点
    			r3->next=p;                     //链表3指向新建结点
    			r3=p;                          //将新建结点赋给链表3的结点
                p=new node;        //同理，将链表2的此结点拷贝给链表3的下一个结点
    			p->date=r2->next->date;
    			r3->next=p;
    			r3=p;
    			r1->next=r1->next->next;    //链表1的指针指向下一个结点
    			r2->next=r2->next->next;    //链表2的指针指向下一个结点
    		}
    		else if (r1->next->date>r2->next->date)  //链表1的数据大于链表2的数据
    		{ 
    			p=new node;                     //新建结点
    			p->date=r2->next->date;           //将链表2的数据赋给此结点
    			r3->next=p;                      //链表3指向新建结点
    			r3=p;                           //将新建结点赋给链表3
    			r2->next=r2->next->next;           //链表2的指针指向下一个结点
    		}
    	}
    	while (r1->next!=NULL)                   //链表1不为空
    	{ 
    		p=new node;                       //建立新的结点
    		p->date=r1->next->date;              //将链表1的数据赋给新建结点
    		r3->next=p;                        //将链表3指向下一个结点
    		r3=p;                             //将新建结点赋给链表3的此结点
    		r1->next=r1->next->next;            //链表1的指针指向下一个结点
    	} 
    	while (r2->next!=NULL)                  //链表2不为空时
    	{ 
    		p=new node;                      //新建结点
    		p->date=r2->next->date;            //将链表2的数据赋给新建结点
    		r3->next=p;                       //链表3指向新建结点
    		r3=p;                            //将新建结点赋给链表3的此结点
    		r2->next=r2->next->next;           //链表2的指针指向下一个结点
    	}
    	r3->next=NULL;              //链表3的末结点指向空
    	print(L3);                   //输出链表3
    }

（2）链表的删除

#include <iostream>
    using namespace std;
    
    typedef struct node{              //构建链表结构体
    	int date;
    	struct node *next;
    }node;
    
    int main()
    { 
        node *p, *r, *L;
    	int number;
    	
    	L=new node;
    	r=L;
    	
    	cin>>number;               //新建链表
    	while (number!=-1)
    	{ 
    		p=new node;
    		p->date=number;
    		r->next=p;
    		r=p;
    		cin>>number;
    	}
    	r->next=NULL;
    	
    	cout<<"删除"<<endl<<"输入删除的数值 : ";
    	cin>>number;
    	if((L->next->date)==number)      //删除数值为链表的第一个结点
        { 
            p=new node;              //新建结点
            p->date=L->next->date;     //链表的首结点的数据赋给新建结点的数据
            p->next=L->next->next;     //新建结点的指针指向链表的下一个指针域
            L->next=L->next->next;     //链表的指针指向下一个结点的指针
            delete p;                 //删除新建结点
        }
        else
        { 
            r=L->next;              //将链表的首结点赋给指针r
    		while (r!=NULL)                    //指针为空时跳出循坏
    		{ 
    			if ((r->next->date)==number)     //下一个结点的数据等于删除数据
    			{ 
    				p=new node;             //新建结点
    				p->date=r->next->date;     //将链表的下一个结点的数据赋给新建结点
    				p->next=r->next->next;  //新建结点指向链表的下一个结点的下一个指针
    				r->next=r->next->next;  //链表的此结点的指针指向下一个结点的下一个
    				delete p;             //删除新建结点
    				break;               //跳出循坏
    			}
    			else
    			{ 
    				r=r->next;            //链表指向下一个结点的指针
    			}
    		}
        }
        while(L->next!=NULL)              //指针为空时跳出循坏
        { 
            cout<<L->next->date<<" ";      //输入此结点的数据
            L->next=L->next->next;        //指针指向下一个指针域
        }
        cout<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]: /images/20211122/e6305b1be6754b9680f70494cdecd972.png
[20190725184702567.png]: /images/20211122/fd0426fcff8049139df5f69a0b93bdc2.png
[20190725184731295.png]: https://img-blog.csdnimg.cn/20190725184731295.png
[20190725184739857.png]: /images/20211122/3bf03cd25bcb48fab473e23ba0b611be.png
[20190725184747259.png]: https://img-blog.csdnimg.cn/20190725184747259.png
[20190725184752847.png]: /images/20211122/da4649b89f7c46248a844e2d405982b2.png
[20190725184759823.png]: /images/20211122/9b38dee4b30a421581bbb34adcd07a5a.png
[20190725184805766.png]: /images/20211122/8586e77ed15f429ba0f2463849770498.png