链表

ACM版本

struct Node{
	int value;
	Node *pre,*nxt;
};
Node *head, *tail;
void initialize(){
	head = new Node();
	tail = new Node();
	head->nxt=tail;
	tail->pre=head;
}
void insert(Node *p, int val){
	Node *q;
	q = new Node(); 
	q->value=val;//先赋值 
	p->nxt->pre=q;//p->nxt最容易丢失，所以先处理它 
	q->nxt=p->nxt;//同上 
	p->nxt=q; 
	q->pre=p;
}
void remove(Node *p){
	p->nxt->pre=p->pre;
	p->pre->nxt=p->nxt;
	delete p;
}
void recycle(){//旧链表换不锈钢盆 
	while(head!=tail){
		head = head -> nxt;
		delete head->pre;
	} 
	delete tail;
}
void output_node(){
	Node *q;
	q=new Node();
	q=head;
	while(q->nxt!=tail){
		cout<<q->nxt->value;
		q=q->nxt;
	}
}

数据结构版本

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5
typedef int Status;
typedef int ElemType;//这里可以自定义类型
typedef struct node{
	ElemType element;
	struct node *link;
}Node;
typedef struct headerList{	
	struct node *head;
	int n;
}HeaderList;
void Init(HeaderList *h){
	h->head=(Node*)malloc(sizeof(Node));//为链表表头分配一个空间
	if(!h->head){
		printf("ERROR in Init()\n");
		return ;
	}
	h->head->link=NULL;
	h->n=0;
}
 //初始化实际上是链表表头的初始化

Status Find(HeaderList *h,int i){
	int j;
	Node *p;
	if(!h->n||i<0||i>h->n-1){
		printf("ERROR in Find\n");
		return ERROR;
	}
	p=h->head->link;
	for(j=0;j<i;j++)p=p->link;//找到查找的位置，输出值
	return p->element;
}

void Insert(HeaderList *h,int i,ElemType x){
	if(i<-1||i>h->n-1){//判断位置是否合法
		printf("ERROR in Insert\n");
		return ;
	}
	Node *p=h->head;//将头结点地址赋予指针p
	for(int j=0;j<=i;j++)p=p->link;//找到需要的位置
	Node *q=new Node;//创建一个新结点保存需要插入的数据
	q->element=x;
	q->link=p->link;//将新结点指向该位置的后一结点
	p->link=q;//将该位置的上一结点指向新结点
	h->n=h->n+1;//最后要将元素个数加一
}
void Delete(HeaderList *h,int i){
	int j;
	Node *p,*q;
	if(!h->n||i<0||i>h->n-1){//判断是否合法
		printf("ERROR in Delete\n");
		return ;
	}
	q=h->head;
	for(j=0;j<i;j++)q=q->link;//找到删除位置前驱
	p=q->link;//保存删除位置的空间地址以防止内存泄漏
	q->link=p->link;//从链表中删去这个结点
	free(p);//释放删去结点的空间
	h->n--;//总长减一
}
void Output(HeaderList *h){
	Node *p=h->head;//这里对应于下面while()中的判断语句，可以做相应改动
	while(p->link!=NULL){//从头到尾遍历，直到指针指向NULL
		printf("%d ", p->link->element);
		p=p->link;
	}
} 
void Destory(HeaderList *h){
	Node *p;
	while(h->head){
		p=h->head->link;
		free(h->head);
		h->head=p;
	}
}
void Inverse(HeaderList *h){
	if(h->n<=1)return ;
	Node *p=h->head->link,*q;	
	h->head->link = NULL;	
	while(p){		
		q=p->link;//记录下一次迭代的值		
		p->link=h->head->link;    //将指针p的后驱设置为表头后驱		
		h->head->link=p;          //将表头设为指针p（其中带着此次迭代的值）的前驱 
		p=q;	//往下迭代 
	}
}
int main(){
	int i;
	HeaderList list;
	Init(&list);
	for(i=0;i<9;i++)Insert(&list,i-1,i);
	printf("原始数据：");
	Output(&list);
	printf("\n");
	printf("翻转后：");
	Inverse(&list); 
	Output(&list);
	Destory(&list);
	return 0;
}