数据结构——C++单链表的基本实现

#include
#include
#include

using namespace std;

typedef struct LNode{
	int data;//数据域 
	struct LNode *next;//指针域 
}LNode, *LinkList;

//初始化一个空的单链表 
void InitList(LinkList &L){
	L = new LNode;
	L->next = NULL;
}

//判空 
bool Empty(LinkList &L){
	return(L->next==NULL);
}

//求表长
int Length(LinkList L){
	int len = 0;
	LNode *p = L;
	while(p->next!=NULL){
		p = p->next;
		len++;
	}
	return len;
} 

//尾插法
LinkList List_TailInsert(LinkList &L){
	LNode *r = L; // r为尾指针
    int e;
    cin >> e;
    while (e != 999) {
        LNode *s = new LNode;
        s->next = r->next;
        s->data = e;
        r->next = s;
        r = s; // 将r置为新的尾指针
        cin >> e;
    }
    r->next = NULL; // 尾指针的next置为NULL
    return L;
} 

//头插法
LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	cin >> x;
	L->next = NULL;
	while(x!=999){
		cin >> x;
		LNode *s;
		s->next = L->next;
		s->data = x;
		L->next = s;
	}
	
	return L;
	
} 

//按值查找数据=e的结点 
LNode *LocateElem(LinkList &L,int e){
	LNode *p = L->next;
	while(p->next!=NULL && p->data==e){
		p = p->next;
	}
	return p;
}

//按序查找
LNode *GetElem(LinkList &L,int i){
	if(i<1)
		return NULL;
	
	LNode *p = L;
	int num = 0;
	while(p->next != NULL && num < i){
		p = p->next;
		num++;
	}
	return p;
};

//前插操作
bool InsertPriorNode(LNode *p,int e){
	if(p->next==NULL)
	return false;
	
	LNode *s = new LNode;
	s->next = p->next;
	s->data = p->data;
	p->next = s;
	p->data = e;
	
	return true;
} 

//后插操作，在p节点后插入e
bool InsertNextNode(LNode *p,int e){
	if(p->next == NULL)
	return false;
		
	LNode *q =new LNode;
	q->data = e;
	q->next = p->next;
	p->next = q;
	
	return true;
} 

//按序插入数据e 
bool InsertList(LinkList &L,int i,int e){
	if(i<1)
		return false;
	//遍历找到第i-1个结点 
	LNode *p = GetElem(L,i-1);
	
	InsertNextNode(p,e);
//	InsertPriorNode(p,e);
	return true;
}
 
//删除
bool DeleteNextNode(LNode *p,int &e){
	if(p->data==NULL)
	return false;
	if(p->next==NULL)
	return false;
	
	LNode *q = p->next;
	e = q->data;
	p->next = q->next;
	delete q;
	return true;
	
} 
//按序删除
bool ListDelete(LinkList &L,int i,int &e){
	if(i<1)
	return false;
	
	LNode *p = GetElem(L,i-1);
	
	return DeleteNextNode(p,e);
}  

//输出单链表 
void TraverseList(LinkList &L) {
    if (L->next == NULL) {
        return;
    }
    LNode *p = L->next; // 指向头指针
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}


int main(){
	LinkList L;
	InitList(L);
	
	L = List_TailInsert(L);
//	L = List_HeadInsert(L);    头插法 
	
	Empty(L); 

	cout << "当前长度为：" << Length(L) << endl;
	
	InsertList(L,3,5);   //在序列3的位置插入数据5 
	TraverseList(L);
	
	int e;
	ListDelete(L,4,e);
	cout << "被删除的是：" << e << endl;
	TraverseList(L);
	
	return 0;
}