单向链表的基本操作

数据结构的基础知识之一：单向链表的基本操作。

我专门写了一个程序，其中包含尽可能多的链表操作。希望该程序能在工作中帮助到大家~同时也方便大家复习链表。

#include<iostream>#include<cstdlib>#include<algorithm>using namespace std;typedef int datatype;typedef struct node{	datatype data;	struct node *next;}linknode,*link;/*Createlist*/link CreateList(){	int a;	link H,p,r;	H = (link)malloc(sizeof(linknode));//建立头节点	r = H;	cin>>a;	while(a != -1){		p = (link)malloc(sizeof(linknode));//申请新节点 		p->data = a;		r->next = p;		r = p;//存入数据，将新节点链入表尾 		cin>>a;	}	r->next = NULL;	return H;}/*查找*/link GetElem(link H,int i){	int j = -1;	link p = H;	if(i<0) return NULL;	while(p->next&&j<i){		p = p->next;		j++;	}	if(i==j) return p;	else return NULL;//查找失败，即i>表长 }/*按值查找*/link LocateElem(link H,datatype e){	link p = H->next;	while(p && p->data!=e){		p = p->next;	}	return p;//若p->data==e则返回指针p;否则p必为空,返回NULL } /*将一定值e插在元素ai之前*/int ListInsert(link H,int i,datatype e){	link p,q;	p = GetElem(H,i-1);	if(p == NULL) return -1;	q = (link) malloc(sizeof(linknode));	q->data = e;	q->next = p->next;/*插入新节点*/	p->next = q;	return 0;}/*删除*/int ListDel(link H,int i){	link p,q;	if(i==0) p = H;	else p = GetElem(H,i-1);	if(p && p->next){		q = p->next;		p->next = q->next;		free((char*)q);		return 0;	} 	return -1;} /*链表翻转*/void L1nToLn1(link H){	link p,q;	p = H->next;	H->next = NULL;	while(p){		q = p;		p = p->next;		q->next = H->next;		H->next = q;	}} /*最大值返回前一个的指针*/link Adjmax(link H){	link p,p1,q;	int m0,m1;	p = H->next;	p1 = p;	if(p1 == NULL) return NULL;	q = p->next;	if(q == NULL) return NULL;/*表长为1*/	m0 = p->data+q->data;	while(q->next){		p = q;		q = q->next;		m1 = p->data+q->data;		if(m1>m0){			p1 = p;			m0 = m1;		}	} 	return p1;} /*链表合并并递增*/void Merge(link A,link B){	link r,p,q;	p = A->next;	q = B->next;	free(B);	r = A;	while(p && q){		if(p->data <= q->data){			r->next = p;			r = p;			p = p->next;		}		else{			r->next = q;			r = q;			q = q->next;		}	}	if(p == NULL) p = q;	r->next = p;} void ListPRint(link H){	link a,b;	a = H->next;	while(a != NULL){		cout<<a->data<<"<";		b = a;		a = a->next;		free(b);	}}int main(){	link H;	H = CreateList();	L1nToLn1(H);	ListPrint(H);	return 0;}