数据结构-顺序表与链表

（1）顺序表

【1】基础版

#define MAXSIZE 100
#include<iostream>
using namespace std;
typedef int ElemType;
struct SeqList{
	ElemType data[MAXSIZE];//方便以后直接修改数据类型 
	int length;
};
void initList (SeqList* L){
	L->length=0;
}
int appendElem(SeqList *L,ElemType e){
	if(L->length>MAXSIZE){
		cout<<"顺序表已经满了"<<endl;
		return false; 
	}
	L->data[L->length]=e;
	L->length++;
	return true;
}
void listElem(SeqList *L){
	for(int i=0;i<L->length;i++){
		cout<<L->data[i]<<" ";
	}
	cout<<endl;
}
int insertElem(SeqList* L,int pos,ElemType e){
	if(pos<=L->length){
		for(int i=L->length-1;i>=pos-1;i--){
			L->data[i+1]=L->data[i]; 
		}
		L->data[pos-1]=e;
	    L->length++;
	}
	return true;
}
int deleteElem(SeqList* L,int pos,ElemType *e)//e是返回我要删除的元素 
{
	*e=L->data[pos-1];
	if(pos<L->length){
		for(int i=pos-1;i<L->length;i++){
			L->data[i]=L->data[i+1];
		}
	}
	L->length--;
	return true; 
}
int findElem(SeqList* L,ElemType e){
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e)
		return i+1;
	}
	return false;
}
int main(){
	SeqList list;
	initList(&list);
	cout<<sizeof(list.data)<<endl;//所占内存 
	appendElem(&list,80);//尾部添加元素函数
	appendElem(&list,81);
	appendElem(&list,82);
	appendElem(&list,83);
	insertElem(&list,2,18);//插入元素 
	ElemType DeleteElem;
	deleteElem(&list,2,&DeleteElem);//删除元素 
	findElem(&list,80);//查找元素 
	listElem(&list);//遍历 
}

【2】动态分配内存地址初始化版

#define MAXSIZE 100
#include<iostream>
using namespace std;
typedef int ElemType;
struct SeqList{
	ElemType* data;//方便以后直接修改数据类型 
	int length;
};
SeqList* initList (){
	SeqList*L=new SeqList;
	L->data=new ElemType[MAXSIZE];
	L->length=0;
	return L;
}
int appendElem(SeqList *L,ElemType e){
	if(L->length>MAXSIZE){
		cout<<"顺序表已经满了"<<endl;
		return false; 
	}
	L->data[L->length]=e;
	L->length++;
	return true;
}
void listElem(SeqList *L){
	for(int i=0;i<L->length;i++){
		cout<<L->data[i]<<" ";
	}
	cout<<endl;
}
int insertElem(SeqList* L,int pos,ElemType e){
	if(pos<=L->length){
		for(int i=L->length-1;i>=pos-1;i--){
			L->data[i+1]=L->data[i]; 
		}
		L->data[pos-1]=e;
	    L->length++;
	}
	return true;
}
int deleteElem(SeqList* L,int pos,ElemType *e)//e是返回我要删除的元素 
{
	*e=L->data[pos-1];
	if(pos<L->length){
		for(int i=pos-1;i<L->length;i++){
			L->data[i]=L->data[i+1];
		}
	}
	L->length--;
	return true; 
}
int findElem(SeqList* L,ElemType e){
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e)
		return i+1;
	}
	return false;
}
int main(){
	SeqList* list=initList();
	cout<<sizeof(list->data)<<endl;//所占内存 
	appendElem(list,80);//尾部添加元素函数
	appendElem(list,81);
	appendElem(list,82);
	appendElem(list,83);
	insertElem(list,2,18);//插入元素 
	ElemType DeleteElem;
	deleteElem(list,2,&DeleteElem);//删除元素 
	findElem(list,80);//查找元素 
	listElem(list);//遍历 
}

（2）单链表

【1】头插法

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node{
	ElemType data;
	Node* next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
int insertHead(Node* L,ElemType e){
	Node *p=new Node;
	p->data=e;
	p->next=L->next;
	L->next=p;
}
void listNode(Node* L)
{
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
int main()
{
	Node* List=initList();//初始化 
	insertHead(List,20);//头插法 
	insertHead(List,22);
	listNode(List);
	
}

【2】尾插法

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node{
	ElemType data;
	Node* next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
void listNode(Node* L)
{
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* inserTail(Node *tail,ElemType e){
	Node *p=new Node;
	p->data=e;
	tail->next=p;
	p->next=NULL;
	return p;
}
int main()
{
	Node* list=initList();//初始化 
	Node* tail=get_tail(list);
	tail=inserTail(tail,10);//尾插法 
	tail=inserTail(tail,20);
	tail=inserTail(tail,30);
	listNode(list);
}

【3】在某个位置插入数据

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node{
	ElemType data;
	Node* next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
void listNode(Node* L)
{
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* inserTail(Node *tail,ElemType e){
	Node *p=new Node;
	p->data=e;
	tail->next=p;
	p->next=NULL;
	return p;
}
int insertNode(Node *L,int pos,ElemType e)
{
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	Node *q=new Node;
	q->data=e;
	q->next=p->next;
	p->next=q;
	return 1;
}
int main()
{
	Node* list=initList();//初始化 
	Node* tail=get_tail(list);
	tail=inserTail(tail,10);//尾插法 
	tail=inserTail(tail,20);
	tail=inserTail(tail,30);
	listNode(list);
	insertNode(list,2,12);//在某个位置插入数据 
	listNode(list);
}

【4】删除节点

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node{
	ElemType data;
	Node* next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
void listNode(Node* L)
{
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* inserTail(Node *tail,ElemType e){
	Node *p=new Node;
	p->data=e;
	tail->next=p;
	p->next=NULL;
	return p;
}
int insertNode(Node *L,int pos,ElemType e)
{
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	Node *q=new Node;
	q->data=e;
	q->next=p->next;
	p->next=q;
	return 1;
}
int deleteNode(Node*L,int pos){
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	if(p->next==NULL)
	{
		cout<<"错误"<<endl;
		return 0;
	}
	Node *q=p->next;
	p->next=q->next;
	delete q;
	return 0;
}
int main()
{
	Node* list=initList();//初始化 
	Node* tail=get_tail(list);
	tail=inserTail(tail,10);//尾插法 
	tail=inserTail(tail,20);
	tail=inserTail(tail,30);
	listNode(list);
	insertNode(list,2,12);//在某个位置插入数据 
	listNode(list);
	deleteNode(list,2);//删除列表的某个元素 
	listNode(list);
}

【5】释放链表

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node{
	ElemType data;
	Node* next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
void listNode(Node* L)
{
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* inserTail(Node *tail,ElemType e){
	Node *p=new Node;
	p->data=e;
	tail->next=p;
	p->next=NULL;
	return p;
}
int insertNode(Node *L,int pos,ElemType e)
{
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	Node *q=new Node;
	q->data=e;
	q->next=p->next;
	p->next=q;
	return 1;
}
int deleteNode(Node*L,int pos){
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	if(p->next==NULL)
	{
		cout<<"错误"<<endl;
		return 0;
	}
	Node *q=p->next;
	p->next=q->next;
	delete q;
	return 0;
}
void freeList(Node* L){
	Node* p=L->next;
	Node* q;
	while(p!=NULL){
		q=p->next; 
		delete p;
		p=q;
	}
	L->next=NULL;
} 
int main()
{
	Node* list=initList();//初始化 
	Node* tail=get_tail(list);
	tail=inserTail(tail,10);//尾插法 
	tail=inserTail(tail,20);
	tail=inserTail(tail,30);
	listNode(list);
	insertNode(list,2,12);//在某个位置插入数据 
	listNode(list);
	deleteNode(list,2);//删除列表的某个元素 
	listNode(list);
	freeList(list);//释放链表 
}

【6】反转链表

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node{
	ElemType data;
	Node* next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
void listNode(Node* L)
{
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* inserTail(Node *tail,ElemType e){
	Node *p=new Node;
	p->data=e;
	tail->next=p;
	p->next=NULL;
	return p;
}
int insertNode(Node *L,int pos,ElemType e)
{
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	Node *q=new Node;
	q->data=e;
	q->next=p->next;
	p->next=q;
	return 1;
}
int deleteNode(Node*L,int pos){
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	if(p->next==NULL)
	{
		cout<<"错误"<<endl;
		return 0;
	}
	Node *q=p->next;
	p->next=q->next;
	delete q;
	return 0;
}
void freeList(Node* L){
	Node* p=L->next;
	Node* q;
	while(p!=NULL){
		q=p->next; 
		delete p;
		p=q;
	}
	L->next=NULL;
} 
Node* reverseList(Node* head)
{
	Node* first=NULL;
	Node* second=head->next;
	Node* third;
	while(second!=NULL){
		third=second->next;
		second->next=first;
		first=second;
		second=third;
	}
	Node *hd=initList();
	hd->next=first;
	return hd;
}
int main()
{
	Node* list=initList();//初始化 
	Node* tail=get_tail(list);
	tail=inserTail(tail,10);//尾插法 
	tail=inserTail(tail,20);
	tail=inserTail(tail,30);
	listNode(list);
	insertNode(list,2,12);//在某个位置插入数据 
	listNode(list);
	deleteNode(list,2);//删除列表的某个元素 
	listNode(list);
	Node* list01=reverseList(list);//反转链表
	listNode(list01);
}

【7】删除链表中间节点

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
struct Node{
	ElemType data;
	Node* next;
};
Node* initList(){
	Node* head=new Node;
	head->data=0;
	head->next=NULL;
	return head;
}
void listNode(Node* L)
{
	Node *p=L->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
Node* get_tail(Node*L){
	Node *p=L;
	while(p->next!=NULL){
		p=p->next;
	}
	return p;
}
Node* inserTail(Node *tail,ElemType e){
	Node *p=new Node;
	p->data=e;
	tail->next=p;
	p->next=NULL;
	return p;
}
int insertNode(Node *L,int pos,ElemType e)
{
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	Node *q=new Node;
	q->data=e;
	q->next=p->next;
	p->next=q;
	return 1;
}
int deleteNode(Node*L,int pos){
	Node *p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL)
		return 0;
	}
	if(p->next==NULL)
	{
		cout<<"错误"<<endl;
		return 0;
	}
	Node *q=p->next;
	p->next=q->next;
	delete q;
	return 0;
}
void freeList(Node* L){
	Node* p=L->next;
	Node* q;
	while(p!=NULL){
		q=p->next; 
		delete p;
		p=q;
	}
	L->next=NULL;
} 
Node* reverseList(Node* head)
{
	Node* first=NULL;
	Node* second=head->next;
	Node* third;
	while(second!=NULL){
		third=second->next;
		second->next=first;
		first=second;
		second=third;
	}
	Node *hd=initList();
	hd->next=first;
	return hd;
}
int delMiddleNode(Node *head){
	Node *fast=head->next;
	Node *slow=head;
	while(fast!=NULL&&fast->next!=NULL){
		fast=fast->next->next;
		slow=slow->next;
	}
	Node* q=slow->next;
	slow->next=q->next;
	delete q;
	return true;
}
int main()
{
	Node* list=initList();//初始化 
	Node* tail=get_tail(list);
	tail=inserTail(tail,10);//尾插法 
	tail=inserTail(tail,20);
	tail=inserTail(tail,30);
	listNode(list);
	insertNode(list,2,12);//在某个位置插入数据 
	listNode(list);
	deleteNode(list,2);//删除列表的某个元素 
	listNode(list);
	Node* list01=reverseList(list);//反转链表 
	delMiddleNode(list01);//删除链表中间节点 
	listNode(list01);
}