单链表

#include<iostream>
#include<conio.h>
#include <malloc.h>

//定义节点
typedef char ElemType;
typedef struct Node{
	ElemType data;
    struct Node *next;
} LinkList;

/*
*将链表初始化，使得L指向一个头结点，这个头结点数据项为空
*/
void InitList(LinkList *&L){
	L=(LinkList *)malloc(sizeof(LinkList));  	//创建头结点
	L->next=NULL;
}

/*
销毁链表，释放空间
*/
void DestroyList(LinkList *&L){
	LinkList *p=L,*q=p->next;
	while (q!=NULL){
		free(p);
		p=q;
		q=p->next;
	}
	free(p);
}


int ListEmpty(LinkList *L){
	return(L->next==NULL);
}

/*
*获取第i个元素，i>0，如果获取失败返回0；获取的元素存储在e中
*/
int GetElem(LinkList *&L,int i,ElemType &e){
	int j=0;
	LinkList *p=L;
	while (j<i && p!=NULL){
		j++; p=p->next;
	}
	if (p==NULL)
		return 0;
	else{
		e=p->data;	return 1;
	}
}

/*
*删除第i个元素
*/
int ListDelete(LinkList *&L,int i,ElemType &e){
	int j=0;
	LinkList *p=L;
	while (j<i-1 && p!=NULL){
		j++; p=p->next;
	}
	if (p==NULL||p->next==NULL)	
		return 0;
    LinkList *q=p->next;//q指向要删除的结点
	e=q->data;
	p->next=q->next;
	free(q);
	return 1;
}

/*
*插入节点
*/
int ListInsert(LinkList *&L,int i,ElemType e){
	int j=0;
	LinkList *p=L;
	while (j<i-1 && p!=NULL){
		j++;
		p=p->next;
	}
	if (p==NULL)	//未找结点
		return 0;
    LinkList *s=(LinkList *)malloc(sizeof(LinkList));	
	s->data=e;
	s->next=p->next;	
	p->next=s;
	return 1;
}


void ListDisplay(LinkList *L){
	L=L->next;
	while (L!=NULL)
	{
		std::cout<<L->data;
		L=L->next;
	}
	std::cout<<std::endl;
}
int main(){
	LinkList *L;
	InitList(L);
	ListInsert(L,1,'a');
	ListInsert(L,2,'b');
	ListInsert(L,3,'c');
    ListDisplay(L);
	char e;
	ListDelete(L,3,e);
	std::cout<<e<<std::endl;
	ListDisplay(L);
	ListInsert(L,1,'c');
	ListDisplay(L);
	getche();
	return 1;
}

 运行结果：

abc

c

ab

cab