线性表的顺序表示和实现

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>//日常头文件
#define ll long long
#define list_size 100//线性表储存空间的初始分配量(最大存储量!)
#define list_increment 10//线性表存储空间的分配增量(本代码用的是数组,不能动态增加空间~)
#define Datatype int
#define Status int
#define OK 1
#define False 0
using namespace std;
/*
实现:
线性表的初始化,销毁,判断是否存在,长度,元素的位置,位置的元素,前驱元素,后驱元素,
插入元素,删除元素,线性表的遍历*/
typedef struct {
	Datatype data[list_size];//用数组来表示顺序表
	int length;//线性表的当前长度
} sq_list;
//线性表的初始化
Status init_list(sq_list &L) {
	for(int i=0; i<=list_size; i++) {
		L.data[i]=0;//初始化为空
	}
	L.length=0;//空表的长度为0;
	return OK;
}
//线性表的长度
Status length_list(sq_list L) {
	return L.length;
}
//线性表的销毁
Status destory_list(sq_list &L) {
	for(int i=0; i<=length_list(L); i++) {
		L.data[i]=0;
	}
	L.length=0;
	return OK;
}
//判断是否存在
Status empty_list(sq_list L) {
	if(L.length==0)
		return OK;//为空
	else return False;//不为空
}
//查找第i个位置上的数据
Status getelem_list(sq_list L,int i,Datatype *e) {
	if(i<1||i>length_list(L)||empty_list(L)) {
		return False;
	}
	*e=L.data[i-1];
	return OK;

}
//查找数据在的第一个位置
Status locate_list(sq_list L,Datatype e) {
	for(int i=0; i<length_list(L); i++) {
		if(L.data[i]==e)
			return i+1;//返回第几个位置。因为是第 所以加1
	}
	return False;
}
//前驱元素
Status priorelem_list(sq_list L,Datatype cur_e,Datatype *pre_e) {
	if(cur_e==L.data[0]) {
		return False;
	}
	int pos=locate_list(L,cur_e);
	if(pos==False) return False;
	else {
		*pre_e=L.data[pos-1-1];//这样好理解。
		return OK;
	}
}
//后驱元素
Status nextelem_list(sq_list L,Datatype cur_e,Datatype *nex_e) {
	if(cur_e==L.data[length_list(L)-1])
		return False;
	int pos=locate_list(L,cur_e);
	if(pos==False) return False;
	else {
		*nex_e=L.data[pos];
		return OK;
	}
}
//插入元素 在第i个位置插入e……(第第第)
Status insert_list(sq_list &L,int i,Datatype e) {
	if(i<1||i>list_size||length_list(L)>=list_size) {
		//大于等于 list_size就不能再插入了不然就超数组了
		return False;
	}
	for(int j=length_list(L)-1; j>=i-1; j--) { //i-1才是对应数组里的那个位置
		L.data[j+1]=L.data[j];
	}
	L.data[i-1]=e;
	L.length++;
	return OK;

}
//删除元素,删除第i个位置上的元素,返回返回这个元素的值
Status delete_list(sq_list &L,int i,Datatype *e) {
	if(i<1||i>length_list(L)||empty_list(L)) {
		return False;
	}
	*e=L.data[i-1];//要删除的元素
	for(int j=i; j<length_list(L); j++) {
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return OK;

}
//遍历
void traverse_list(sq_list L) {
	if(!empty_list(L)) {
		for(int i=0; i<length_list(L); i++) {
			cout<<L.data[i]<<"  ";
		}
		cout<<endl;
	} else {
		cout<<"Not Found"<<endl;
	}
}
int main() {
	int n,a,pos;
	Datatype e,nex_e,pre_e,cur_e;
	sq_list L;
	cout<<"output the size of list: ";
	cin>>n;
	
	//list表的建立;利用了插入
	init_list(L);
	for(int i=1; i<=n; i++) {
		//第i个位置插入a
		a=rand()%100+1;
		//cout<<a<<"       ";
		insert_list(L,i,a);
	}
	cout<<"sq_list: ";
	traverse_list(L);
	cout<<endl;
	
	//在list 表中插入 新的元素
	cout<<"input the position and element of you wanting to insert: ";
	cin>>pos>>e;//在第pos位置插入e
	insert_list(L,pos,e);
	cout<<"output list after inserting: ";
	traverse_list(L);
	cout<<endl;
	
	//删除第pos个位置上的元素,并且返回这个元素
	cout<<"input the position you want to delete: ";
	cin>>pos;
	if(delete_list(L,pos,&e)) {
		cout<<"the deleted element: "<<e<<endl;
		cout<<"output list after deleting: ";
		traverse_list(L);
	} else cout<<"error"<<endl;
	cout<<endl;
	
	//查找当前元素的前驱元素
	cout<<"input the cur_e you want to search priorelem: ";
	cin>>cur_e;
	if(priorelem_list(L,cur_e,&pre_e)) {
		cout<<pre_e<<" is the previous letter of "<<cur_e<<endl;
	} else cout<<"error"<<endl;
	cout<<endl;
	
	//查找当前元素的后驱元素
	cout<<"input the cur_e you want to search nextelem: ";
	cin>>cur_e;
	if(nextelem_list(L,cur_e,&nex_e))
	{
		cout<<nex_e<<" is the next letter of "<<cur_e<<endl;
	 }else cout<<"error"<<endl;
	cout<<endl;
	
	//查找第i个位置的元素并返回
	cout<<"input the element position you want to search: ";
	cin>>pos;
	if(getelem_list(L,pos,&e))
	{
		cout<<"The element of "<<pos<<"-th position is: "<<e<<endl; 
	}else cout<<"error"<<endl;
	cout<<endl;
	
	//查找元素在第几个位置
	cout<<"input the element you want to search: ";
	cin>>e;
	if(locate_list(L,e))
	{
		cout<<e<<" is the location is "<<locate_list(L,e)<<endl;
	 } else cout<<"error"<<endl;
	 cout<<endl;
	 
	//所有情况已经实现,清空list
	cout<<"Destory_list is coming!!!(〃'▽'〃)" <<endl;
	if(destory_list(L))
	{
		cout<<"destory finished!"<<endl;
	}else cout<<endl<<"Goodbye~"<<endl;
	return 0; 
}

遇到的问题:L->length 与 L.length 混用了,如果写L->length就会出错

解决: -> 是指针操作符, .点是结构操作符。如果L 是一个结构实例的指针,要用 -> 访问结构里的变量,而不能用点。如果L 是一个结构的实例而非指针,只能用点而不能用 -> 。

L->length 相当于 (*L)->length

比如:

struct student{ int length; } *L; 这个是指针 用L->length
struct student{ int length; } L; 这个用L.length

关于带 &不带 & 的区别

带&的是引用型参数,它是地址传递,其实参会随着形参的改变而改变;不带&的参数是一般参数,是值传递,其实参不会随着形参的改变而改变。所以,结构改变,并且需要传回这种改变的要用引用型参数,否则用一般参数。getelem_list(sq_list L,int i,Datatype *e)是找到第i个元素的值,线性表的结构并未发生任何改变,所以参数L前面不用加&。insert_list(sq_list &L,int i,Datatype e)是在线性表L的第i个元素处插入一个数值为e的元素,线性表L的结构发生了改变,长度增加了,所以在L前必须加上&。如果不加,显示L时,新增元素就显示不出来,显示L的长度,也仍然是增加以前的值,比实际长度少1.

集合的交并和差运算的实现(老师课堂作业)

我刚开始理解错意思了……其实就是求 交集、并集、差集。。。。

代码修改后:

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>//日常头文件
#define ll long long
#define list_size 100//线性表储存空间的初始分配量(最大存储量!)
#define list_increment 10//线性表存储空间的分配增量(本代码用的是数组,不能动态增加空间~)
#define Datatype int
#define Status int
#define OK 1
#define False 0
using namespace std;
/*
实现:
线性表的初始化,销毁,判断是否存在,长度,元素的位置,位置的元素,前驱元素,后驱元素,
插入元素,删除元素,线性表的遍历*/
typedef struct {
	Datatype data[list_size];//用数组来表示顺序表
	int length;//线性表的当前长度
} sq_list;
//线性表的初始化
Status init_list(sq_list &L) {
	for(int i=0; i<=list_size; i++) {
		L.data[i]=0;//初始化为空
	}
	L.length=0;//空表的长度为0;
	return OK;
}
//线性表的长度
Status length_list(sq_list L) {
	return L.length;
}
//线性表的销毁
Status destory_list(sq_list &L) {
	for(int i=0; i<=length_list(L); i++) {
		L.data[i]=0;
	}
	L.length=0;
	return OK;
}
//判断是否存在
Status empty_list(sq_list L) {
	if(L.length==0)
		return OK;//为空
	else return False;//不为空
}
//查找第i个位置上的数据
Status getelem_list(sq_list L,int i,Datatype *e) {
	if(i<1||i>length_list(L)||empty_list(L)) {
		return False;
	}
	*e=L.data[i-1];
	return OK;

}
//查找数据在的第一个位置
Status locate_list(sq_list L,Datatype e) {
	for(int i=0; i<length_list(L); i++) {
		if(L.data[i]==e)
			return i+1;//返回第几个位置。因为是第 所以加1
	}
	return False;
}
//前驱元素
Status priorelem_list(sq_list L,Datatype cur_e,Datatype *pre_e) {
	if(cur_e==L.data[0]) {
		return False;
	}
	int pos=locate_list(L,cur_e);
	if(pos==False) return False;
	else {
		*pre_e=L.data[pos-1-1];//这样好理解。
		return OK;
	}
}
//后驱元素
Status nextelem_list(sq_list L,Datatype cur_e,Datatype *nex_e) {
	if(cur_e==L.data[length_list(L)-1])
		return False;
	int pos=locate_list(L,cur_e);
	if(pos==False) return False;
	else {
		*nex_e=L.data[pos];
		return OK;
	}
}
//插入元素 在第i个位置插入e……(第第第)
Status insert_list(sq_list &L,int i,Datatype e) {
	if(i<1||i>list_size||length_list(L)>=list_size) {
		//大于等于 list_size就不能再插入了不然就超数组了
		return False;
	}
	for(int j=length_list(L)-1; j>=i-1; j--) { //i-1才是对应数组里的那个位置
		L.data[j+1]=L.data[j];
	}
	L.data[i-1]=e;
	L.length++;
	return OK;

}
//删除元素,删除第i个位置上的元素,返回返回这个元素的值
Status delete_list(sq_list &L,int i,Datatype *e) {
	if(i<1||i>length_list(L)||empty_list(L)) {
		return False;
	}
	*e=L.data[i-1];//要删除的元素
	for(int j=i; j<length_list(L); j++) {
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return OK;

}
//遍历
void traverse_list(sq_list L) {
	if(!empty_list(L)) {
		for(int i=0; i<length_list(L); i++) {
			cout<<L.data[i]<<"  ";
		}
		cout<<endl;
	} else {
		cout<<"Not Found"<<endl;
	}
}
//集合的 交、并、差 
//定义四个集合  
/*l1,l2是原始集合,l3是交集,l4是并集,l1中删除l3的元素后就变成了差集*/
/*
交集:思路:算l2中的元素在l1中找,有相同的插入到l3中
并集:先在l4中插入l1的所有数据,然后在处理l2 遍历 不一样的插入 一样的略过
差集:在l1中删除l3中的元素,l1就变成差集集合了~~。 
*/
int main() {
	sq_list l1,l2,l3,l4;
	int n=10,e,pos;
	/*为了方便,把元素个数固定了~~~hhh*/
	/*初始化*/
	init_list(l1);
	init_list(l2);
	init_list(l3);//交 
	init_list(l4);//并 
	for(int i=1;i<=n;i++)
	{
		insert_list(l1,i,i);//在第i个位置插入i 
	}
	for(int i=1;i<=n;i++)
	{
		insert_list(l2,i,i*i);//在第i个位置插入i*i 
	}
	cout<<"L1: ";traverse_list(l1);
	cout<<"l2: ";traverse_list(l2); 
	cout<<endl;
	
	/*交集*/
	for(int i=0;i<length_list(l2);i++)
	{
		if(locate_list(l1,l2.data[i]))//在l1中找是否有l2中的元素 有相同的就插入l3 中 
		{
			int len3=length_list(l3)+1;
			insert_list(l3,len3,l2.data[i]); 
		}else continue;
	}
	cout<<"Intersection: ";
	traverse_list(l3);
	
	/*并集*/
	for(int i=0;i<length_list(l1);i++)
	{
		int len4=length_list(l4)+1;
		insert_list(l4,len4,l1.data[i]);
	} 
	//traverse_list(l4);
	for(int i=0;i<length_list(l2);i++)
	{//在l4中找有没有跟l2一样的元素,有点话略过 
		if(!locate_list(l4,l2.data[i]))
		{
			int len4=length_list(l4)+1;
			insert_list(l4,len4,l2.data[i]);
		}else continue; 
	} 
	cout<<"Union: ";
	traverse_list(l4);
	
	/*差集*/
	for(int i=0;i<length_list(l3);i++)
	{/*在l1中删除与l3一样的元素*/
	 //先找位置
		pos=locate_list(l1,l3.data[i]);
		delete_list(l1,pos,&e);	
	} 
	cout<<"Difference set: ";
	traverse_list(l1);
	return 0;	 
}

数组版;

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#define Max_size 100
using namespace std;
/*
求A,B集合的交并差
*/
int half_search(int a[],int l,int r,int key) { //建立在排好序的基础上
	while(l<=r) {
		int mid=(l+r)>>1;
		if(a[mid]==key) return mid;
		else if(a[mid]>key) r=mid-1;
		else l=mid+1;
	}
	return -1;
}
int main() {
	int a[Max_size]= {0},b[Max_size]= {0},c[Max_size*2]= {0},index1=0,index2=0,a1,b1;
	cout<<"输入集合A,集合B的元素(分别以-1结束):"<<endl;
	//输入操作
	while(cin>>a1) {
		if(a1==-1) break;
		if(half_search(a,0,index1,a1)==-1) {
			a[index1++]=a1;
			sort(a,a+index1);
		}
	}
	while(cin>>b1) {
		if(b1==-1) break;
		if(half_search(b,0,index2,b1)==-1) {
			b[index2++]=b1;
			sort(b,b+index2);
		}
	}
	cout<<"集合A: ";
	for(int i=0; i<index1; i++) {
		cout<<a[i]<<" ";
	}
	cout<<endl;
	cout<<"集合B: ";
	for(int i=0; i<index2; i++) {
		cout<<b[i]<<" ";
	}
	cout<<endl;
	/*并集*/
	cout<<"A∪B: ";
	for(int i=0; i<index1; i++) {
		c[i]=a[i];
	}
	int index3=index1;
	for(int i=0; i<index2; i++) {
		if(half_search(c,0,index3,b[i])==-1) {
			c[index3++]=b[i];
			sort(c,c+index3);
		}
	}
	for(int i=0; i<index3; i++)
		cout<<c[i]<<" ";
	cout<<endl;

	/*交集*/
	cout<<"A∩B: ";
	memset(c,0,sizeof(c));
	index3=0;
	for(int i=0; i<index1; i++) {
		for(int j=0; j<index2; j++) {
			if(a[i]==b[j]&&half_search(c,0,index3,b[j])==-1) {
				c[index3++]=b[j];
				sort(c,c+index3);
			}
		}
	}
	for(int i=0; i<index3; i++) {
		cout<<c[i]<<" ";
	}
	cout<<endl;

	/*差集*/
	memset(c,0,sizeof(c));
	index3=0;
	int flag=0;
	cout<<"A-B: ";
	for(int i=0; i<index1; i++) { //a
		flag=0;
//		cout<<"a: "<<a[i]<<" flag; "<<flag<<endl;
		for(int j=0; j<index2; j++) { //b
			if(a[i]==b[j]) {
				flag=1;
				break;
			}
		}
//		cout<<"Flag : "<<flag<<endl;
		if(!flag) {
//			cout<<"asdsa: "<<a[i]<<endl;
			c[index3++]=a[i];
			sort(c,c+index3);
		}
	}
	for(int i=0; i<index3; i++)
		cout<<c[i]<<" ";
	cout<<endl;
	return 0;
}

线性表的链式表示和实现(mycdsn)

更新于:2018.09.26 待完善……

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>//日常头文件
#define ll long long
#define list_size 100//线性表储存空间的初始分配量(最大存储量!)
#define list_increment 10//线性表存储空间的分配增量(本代码用的是数组,不能动态增加空间~)
#define Datatype int
#define Status int
#define OK 1
#define False 0
using namespace std;
/*
实现:
线性表的初始化,销毁,判断是否存在,长度,元素的位置,位置的元素,前驱元素,后驱元素,
插入元素,删除元素,线性表的遍历*/
typedef struct Node
{
	Datatype data;
	struct Node *next;
}node,*sq_list;
//线性表的初始化
Status init_list(sq_list *L)
{
	*L=(sq_list)malloc(sizeof(Node));//创建一个头结点 
	if(!(*L))
	{
		return False;
	} 
	(*L)->next=NULL;//指针域为空 
	return OK; 
}
//线性表的长度 
Status length_list(sq_list L)
{
	int len=0;
    sq_list p=L->next;
    while(p!=NULL)
	{
		len++;
		p=p->next;
	} 
	return len;
}
//清空链表 
Status clear_list(sq_list *L)
{
	sq_list p,q;
	p=(*L)->next;
	while(p)
	{
		q=p->next;
		free(p);
		p=q;
	}
	(*L)->next=NULL;
	return OK;
}
//销毁 链表
Status destory_list(sq_list *L)
{
	sq_list q;
	while(*L)
	{
		q=(*L)->next;
		free(*L);
		*L=q;
	}
	return OK;
 } 
//建立线性表 尾插法
// n 个 元素  
void create_list_tail(sq_list *L,int n)
{//例子:插入的结点顺序为 1 2 3 4 5 输出也是 1 2 3 4 5 按顺序 
	sq_list p,r;
	//r是 尾 一直记录插入的最后一个元素 
	*L=(sq_list)malloc(sizeof(Node));//头结点 
	r=*L;
	for(int i=1;i<=n;i++)
	{
		p=(Node *)malloc(sizeof(Node));
		p->data = rand()%10+1;
		//cout<< p->data <<"   ";
		r->next=p;
		r=p;
	}
	r->next=NULL;
} 
//建立线性表 头插法(画图理解!!!!!)
//n个元素
void create_list_head(sq_list *L,int n)
{//头插法 例子:插入的顺序是 1,21,31,321,2,; 则输出的顺序是 2,321,3,21,1  相反 
	sq_list p;
	*L=(sq_list)malloc(sizeof(Node));//头结点 
	(*L)->next=NULL;
	for(int i=1;i<=n;i++)
	{
		p=(sq_list)malloc(sizeof(Node));
		p->data=rand()%10+1;
		//cout<<p->data<<"   ";
		p->next=(*L)->next;
		(*L)->next=p; 
	}
} 
//查找第i个位置的数据 
Status getelem_list(sq_list L,int i,Datatype *e)
{
	if(i<1||i>length_list(L))
	return False;
	sq_list q=L->next;
	int len=0;
	while(q)
	{
		len++;
		if(len==i)
		{
			*e=q->data;
			return OK;
		}
		q=q->next;
	}return False;
} 
//查询e的位置 
Status locate_list(sq_list L,Datatype e)
{
	int len=0;
	sq_list q;
	q=L->next;
	while(q)
	{
		len++;
		if(q->data==e)
			return len;
		q=q->next;
	}
	return False;
	
}
//在第pos个位置插入元素
Status insert_list(sq_list *L,int pos,Datatype e)
{
	if(pos<1||pos>length_list(*L)) return False;
	sq_list q,p;
	int len=0;
	q=*L;//先指向头节点 
	len=1;//len 要比 q 的位置大一  因为要找的是 pos位置的前驱结点 
	while(q&&len<pos) //寻找pos位置的节点 
	{
		q=q->next;
		len++;
	}
	if(!q||len>pos)//pos位置的元素不存在 
	return False; 
	p=(sq_list)malloc(sizeof(node));
	p->data=e;
	p->next=q->next;
	q->next=p;
	return OK; 
} 

//在第pos位置删除结点,并且,返回这个被删除结点的data
Status delete_list(sq_list *L,int pos,Datatype *e)
{
	int len=0;
	sq_list q,p;
	p=*L;
	len=1;
	while(p->next&&len<pos)//寻找 第pos个元素 
	{
		p=p->next;
		len++; 
	}
	if(!(p->next)||len>pos)
	return False;//pos 位置 元素不存在 
	q=p->next;//q是要删除 
	p->next=q->next;//p=p->next->next; 
	*e=q->data;
	free(q);
	return OK;
}
//前驱元素
//Status priorelem_list(sq_list L,Datatype cur_e,Datatype *pre_e) {
//	if(locate_list(L,cur_e)==1||!locate_list(L,cur_e))//如果cur_的位置为1而且没有当前的这个元素的话说明没有 前驱元素 
//	return False;
//	int len=0;
//	sq_list h,r;
//	r=L->next;
//	len++;
//	h->next=r;
//	while(r)
//	{
//		if(r->data == cur_e)
//		{
//			*pre_e=h->data;	
//		}
//		r=r->next;
//		h->next=r;
//		len++;	 
//	}
//	return OK; 
//	 
//}

//后驱元素
//
//输出
void traverse_list(sq_list L)
{
	sq_list p=L->next;
	while(p)
	{
		cout<< p->data <<"  ";
		p=p->next;
	} 
}
int main()
{
	sq_list L;
	int n,pos,e,cur_e,nex_e,pre_e;
	cin>>n;
	/*这是头插法 
	init_list(&L);
	cout<<"insert head"<<" : ";
	create_list_head(&L,n);
	cout<<endl;
	traverse_list(L);
	cout<<endl;
	*/
	//保留尾插法,,好理解啊, 
	init_list(&L);
	cout<<"insert tail"<<" : ";
	create_list_tail(&L,n);
	cout<<endl;
	traverse_list(L);
	cout<<endl;
	//查询e的位置 
	cout<<"input the element you want to search: ";
	cin>>e;
	if(locate_list(L,e))
	{
		cout<<e<<" is the location is "<<locate_list(L,e)<<endl;
	 } else cout<<"error"<<endl;
	cout<<endl;

	//查找第i个位置的元素并返回
	cout<<"input the element position you want to search: ";
	cin>>pos;
	if(getelem_list(L,pos,&e))
	{
		cout<<"The element of "<<pos<<"-th position is: "<<e<<endl; 
	}else cout<<"error"<<endl;
	cout<<endl; 
	
	//在第pos 位置插入元素 
	cout<<"input the position and element of you wanting to insert: ";
	cin>>pos>>e;//在第pos位置插入e
	if(insert_list(&L,pos,e))
	{
		cout<<"output list after inserting: ";
		traverse_list(L);
	}else cout<<"error"<<endl;
	cout<<endl;
	
	//删除第pos个位置上的元素,并且返回这个元素
	cout<<"input the position you want to delete: ";
	cin>>pos;
	if(delete_list(&L,pos,&e)) {
		cout<<"the deleted element: "<<e<<endl;
		cout<<"output list after deleting: ";
		traverse_list(L);
	} else cout<<"error"<<endl;
	cout<<endl;
	
	//查找当前元素的前驱元素 思路 查找当前元素的位置,然后找上个位置的元素 
	cout<<"input the cur_e you want to search priorelem: ";
	cin>>cur_e;
	if(locate_list(L,cur_e)) {
		int poss=locate_list(L,cur_e);//第一个位置的话就没有 前驱节点了,= = 
		if(poss==1)  cout<<"error"<<endl;
		else 
		{	
			getelem_list(L,poss-1,&pre_e); 
			cout<<pre_e<<" is the previous letter of "<<cur_e<<endl;
		}
	
	} else cout<<"error"<<endl;
	cout<<endl;
	
	//查找当前元素的后驱元素
	cout<<"input the cur_e you want to search nextelem: ";
	cin>>cur_e;
	if(locate_list(L,cur_e))
	{
		int poss=locate_list(L,cur_e);
		if(poss==length_list(L)) cout<<"error"<<endl;
		else
		{
			getelem_list(L,poss+1,&nex_e);
			cout<<nex_e<<" is the next letter of "<<cur_e<<endl;
		}
	
	 }else cout<<"error"<<endl;
	cout<<endl;
	
	//销毁
	cout<<"Destory_list is coming!!!(〃'▽'〃)" <<endl;
	if(destory_list(&L))
	{
		cout<<"destory finished!"<<endl;
	}else cout<<endl<<"Goodbye~"<<endl; 
	return 0;
}
 

在顺序表中插入和删除一个元素,平均需要移动多少个元素

插入 n/2   ——>(n+n-1+.....+0)/(n+1) = n/2;

删除 (n-1)/2  ——>(n-1+n-2+.....+0)/(n) = (n-1)/2;


之前写的链表操作,选择性观看。

//单链表的初始化,建立,插入,查找,删除。
#include <stdio.h>  
#include <stdlib.h>  
typedef int ElemType;  
////////////////////////////////////////////   
//定义结点类型   
typedef struct Node  
{  
    ElemType data;              //单链表中的数据域   
    struct Node *next;          //单链表的指针域   
}Node,*LinkedList;  
////////////////////////////////////////////   
//单链表的初始化  
LinkedList LinkedListInit()  
{  
    Node *L;  
    L = (Node *)malloc(sizeof(Node));   //申请结点空间   
    if(L == NULL)                       //判断是否有足够的内存空间   
        printf("申请内存空间失败/n");  
    L->next = NULL;                  //将next设置为NULL,初始长度为0的单链表   
}  
////////////////////////////////////////////   
//单链表的建立1,头插法建立单链表  
LinkedList LinkedListCreatH()  
{  
    Node *L;  
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间  
    L->next = NULL;                      //初始化一个空链表  
      
    ElemType x;                         //x为链表数据域中的数据  
    while(scanf("%d",&x) != EOF)  
    {  
        Node *p;  
        p = (Node *)malloc(sizeof(Node));   //申请新的结点   
        p->data = x;                     //结点数据域赋值   
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL   
        L->next = p;   
    }  
    return L;   
}   
////////////////////////////////////////////   
//单链表的建立2,尾插法建立单链表  
LinkedList LinkedListCreatT()  
{  
    Node *L;  
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间  
    L->next = NULL;                  //初始化一个空链表  
    Node *r;  
    r = L;                          //r始终指向终端结点,开始时指向头结点   
    ElemType x;                         //x为链表数据域中的数据  
    while(scanf("%d",&x) != EOF)  
    {  
        Node *p;  
        p = (Node *)malloc(sizeof(Node));   //申请新的结点   
        p->data = x;                     //结点数据域赋值   
        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL   
        r = p;   
    }  
    r->next = NULL;   
      
    return L;     
}  
////////////////////////////////////////////   
//单链表的插入,在链表的第i个位置插入x的元素  
LinkedList LinkedListInsert(LinkedList L,int i,ElemType x)  
{  
    Node *pre;                      //pre为前驱结点   
    pre = L;  
    int tempi = 0;  
    for (tempi = 1; tempi < i; tempi++)  
        pre = pre->next;                 //查找第i个位置的前驱结点   
    Node *p;                                //插入的结点为p  
    p = (Node *)malloc(sizeof(Node));  
    p->data = x;   
    p->next = pre->next;  
    pre->next = p;  
      
    return L;                             
}   
////////////////////////////////////////////   
//单链表的删除,在链表中删除值为x的元素  
LinkedList LinkedListDelete(LinkedList L,ElemType x)  
{  
    Node *p,*pre;                   //pre为前驱结点,p为查找的结点。   
    p = L->next;  
    while(p->data != x)              //查找值为x的元素   
    {     
        pre = p;   
        p = p->next;  
    }  
    pre->next = p->next;          //删除操作,将其前驱next指向其后继。   
    free(p);  
    return L;  
}   
/////////////////////////////////////////////  
int main()  
{  
    LinkedList list,start;  
/*  printf("请输入单链表的数据:");  
    list = LinkedListCreatH(); 
    for(start = list->next; start != NULL; start = start->next) 
        printf("%d ",start->data); 
    printf("\n"); 
*/  printf("请输入单链表的数据:");   
    list = LinkedListCreatT();  
    for(start = list->next; start != NULL; start = start->next)  
        printf("%d ",start->data);  
    printf("\n");  
    int i;  
    ElemType x;  
    printf("请输入插入数据的位置:");  
    scanf("%d",&i);  
    printf("请输入插入数据的值:");  
    scanf("%d",&x);  
    LinkedListInsert(list,i,x);  
    for(start = list->next; start != NULL; start = start->next)  
        printf("%d ",start->data);  
    printf("\n");  
    printf("请输入要删除的元素的值:");  
    scanf("%d",&x);  
    LinkedListDelete(list,x);   
    for(start = list->next; start != NULL; start = start->next)  
        printf("%d ",start->data);  
    printf("\n");  
      
    return 0;  
}


下面的是我在课堂上写的,,保存一下

//数据结构基础;链表构成;
//链表建立、清空、初始化、遍历;
//节点查找、插入、删除等
//文件夹 :实验报告+源代码 
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct node {
	int data;
	struct node *next;
}Node,*List;
List creat()//链表的创建 
{
	Node *head,*pre,*p;
	head = (Node *)malloc(sizeof(Node)); 
	int n;
	head=pre=p=new node;
	cin>>p->data;
	p->next=NULL;
	while(cin>>n&&n>=0)//输入截止到数据<0 
	{
		p=new node;
		p->data=n;
		p->next=NULL;
		pre->next=p;
		pre=p;//pre可以理解为 连接作用 
	}
	return (head);
 } 
void show(List head)//打印链表 
{  
	Node *p;
	p=head;               
	while(p!=NULL)        
	{
	    cout<< p->data <<" ";
		p=p->next; 
	} 
}
List insert(List head,int i,int n)//插入 
{
	Node *pre;
	pre=head;
	for(int j=1;j<i;j++)//查找第i个位置的前驱结点 
	{
		pre=pre->next;
	}
	Node *p;
	p = (Node *)malloc(sizeof(Node));  //为新结点申请空间 
	p->data=n;
	p->next=pre->next;//p结点的地址指向前驱结点的下一个
	pre->next=p;
	return (head);
}
List Delete(List head,int x)  //删除 
{  
    Node *p,*pre;  
	pre=head;              
    p=head->next;  
    while(p->data != x)              //查找值为x的元素   
    {     
        pre = p;   
        p = p->next;  
    }  
    pre->next = p->next;          //删除操作,将其前驱next指向其后继。   
    free(p);  
    return (head); 
}   
int main()
{
	int n,i,x;
	List list,begin;
	list=creat();
	show(list);
	cout<<endl<<"输入你想在链表的第i个位置插入什么数据  ";
	cin>>i>>n;
	cout<<"输出插入后的链表:"; 
	insert(list,i,n);
	show(list);
	cout<<endl;
        cout<<"请输入要删除的元素的值:";  
        cin>>x;  
        cout<<"输出删除后的链表:"; 
        Delete(list,x);    
        show(list);
        cout<<endl;
	return 0;
}

先整理这一点,以后慢慢补充…… 😳


年轻也需要有所作为( ・´ω`・ )