数据结构的基础代码

1.单链表的基本操作：

  <1>定义一个单链表

#include 
#include 
typedef int ElemType;

typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode,*linkList;//单链表的定义初始化

<2> 插入元素（带头结点）

bool ListInsert(linkList& L, int i, ElemType e) {//在第i个位置上插入一个元素，（带头结点）
	if (i < 1)
		return false;
	LNode* p;//指针p指向扫描到的结点
	int j = 0;//当前p指向的是第几个结点
	p = L;//L指向头结点，头结点是第0个结点（不存储数据）
	while (p!=NULL&&jnext;
		j++;
	}

	if (p == NULL) {//i值不合法
		return false;
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = p->next;
		p->next = s;//将结点s连接到p之后
		return true;//插入成功
	}
}

<3>不带头结点插入

bool ListInsert(linkList& L, int i, ElemType e) {//不带头结点

	if (i < 1)
		return false;
	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	LNode* p;
	int j = 1;
	p = L;
	while (p!=NULL && jnext;
		j++;
	}

	if (p == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL)
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;

}

<4>元素的后插操作

bool InsertNextNode(LNode* p, ElemType e) {
	if (p == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL)
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

<5>元素按位删除

bool ListDelete(linkList& L, int i, ElemType& e) {//按位序删除
	if (i<1)
		return false;
	LNode* p;//指向扫描点
	int j = 0;//指向第几个结点
	p = L;//指向头结点
	while (p != NULL&&jnext;
		j++;
	}
	if (p == NULL)//i值不合法
		return false;
	if (p->next == NULL)
		return false;//第i-1个结点之后已无其他结点
	LNode* q = p->next;//指向被删除结点
	e = q->data;//用e返回元素的值
	p->next = q->next;//将p结点从链中断开
	free(q);
	return true;
}

<6>元素的按值查找

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

<7>统计表长函数

int Length(linkList L) {//统计表长的函数
	int len = 0;
	LNode* p = L;
	while (p->next!=NULL)
	{
		p = p->next;
		len++;
	}
	return len;
}

<8>正向建立链表

linkList List_TailInsert(linkList& L) {//正向建立单链表
	int x;
	L = (linkList)malloc(sizeof(LNode));
	LNode* s, * r = L;//r为表尾指针
	scanf_s("%d", &x);
	while (x!=9999)
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf_s("%d", &x);
	}
	r->next = NULL;
	return L;
}

<9>逆向建立链表

linkList List_HeadInsert(linkList& L) {//逆向建立单链表
	LNode* s;
	int x;
	L = (linkList)malloc(sizeof(LNode));//创建头结点
	L->next = NULL;//初始为空链表
	scanf_s("%d", &x);
	while (x!=9999)
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf_s("%d", &x);
	}
	return L;
}