链表的实现

顺序表的链式存储

#include <iostream>
using namespace std;
typedef int ElemType;

typedef struct LinkList {
	ElemType value;
	struct LinkList *next;
} LinkList;

LinkList *InitList(LinkList *Ptrl) { //创建(1-10)的链表
	LinkList *temp = new LinkList;
	temp->value = 1;
	temp->next = NULL;
	Ptrl->next = temp;
	for (int i = 2; i <= 10; i++) {
		LinkList *a = new LinkList;
		a->value = i;
		a->next = NULL;
		temp->next = a;
		temp = temp->next;
	}
	return Ptrl;
}

int length(LinkList *Ptrl) { //求表长
	LinkList *p = Ptrl;
	int j = 0;
	while (p) {
		p = p->next;
		j++;
	}
	return j;
}

LinkList *FindKth(int K, LinkList *Ptrl) { //按序号查找
	LinkList *p = Ptrl;
	int i = 1;
	while (p != NULL && i < K) {
		p = p->next;
		i++;
	}
	if (i == K)
		return p;
	else
		return NULL;
}

LinkList *Find(LinkList *Ptrl, ElemType x) { //按值查找
	LinkList *p = Ptrl;
	while (p != NULL && x != p->value)
		p = p->next;
	return p;
}

LinkList *Insert(ElemType x, int i, LinkList *Ptrl) { //在第i个位置插入x
	LinkList *p, *s;
	if (i == 1) {
		LinkList *s = new LinkList;
		s->value = x;
		s->next = Ptrl;
		return s;
	}
	p = FindKth(i - 1, Ptrl);
	if (p == NULL) {
		cout << "参数i错误";
		return NULL;
	} else {
		LinkList *s = new LinkList;
		s->value = x;
		s->next = p->next;
		p->next = s;
		return Ptrl;
	}
}

LinkList *Delete(int i, LinkList *Ptrl) { //删除第i个位置的节点
	LinkList *p, *s;
	if (i == 1) {
		s = Ptrl;
		if (Ptrl != NULL)
			Ptrl = Ptrl->next;
		else
			return NULL;
		free(s);
		return Ptrl;
	}
	p = FindKth(i - 1, Ptrl);
	if (p == NULL) {
		cout << "第i个节点不存在";
		return NULL;
	} else if (p->next == NULL) {
		cout << "第i个节点不存在";
		return NULL;
	} else {
		s = p->next;
		p->next = s->next;
		free(s);
		return Ptrl;
	}
}

void DispList(LinkList *Ptrl) {//遍历链表
	if (Ptrl == NULL)
		return ;
	else {
		cout << Ptrl->value << " ";
		DispList(Ptrl->next);
	}
}