线性表—单链表的基本操作

1. 线性表的链式存储又称为单链表，对于每个链表结点，分为数据域data（存放元素的自身信息）和指针域next（存放指向其后继的指针）

//单链表结点类型的描述：
typedef struct LNode {
	ElemType data; //数据域
	struct LNode *next; //指针域
}LNode, *LinkList;
           

2.采用头插法建立单链表

//从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到链表的表头
LinkList CreatListHead(LinkList &L) {
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode)); //创建头结点
	L->data = NULL; //初始为空链表
	scanf("%d", &x); //输入结点的值，c++为cin >> x;
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode)); //创建新的结点
		s->data = x; //将x存放在s的数据域中
		s->next = L->next;
		L->next = s; //将新结点插入表中，L为头指针
		scanf("%d", &x);
	}
	return L;
}
           

3.采用尾插法建立单链表

LinkList CreatListTail(LinkList &L) {
	int x;
	L = (LinkList)malloc(sizeof(LNode)); //创建头结点
	LNode *s, *r = L; //r为表尾指针
	scanf("%d", &x);
	while (x != 9999) {
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s; //将结点s插入到表尾
		r = s; //r指向新的表尾结点
		scanf("%d", x);
	}
	r->next = NULL; //尾结点指针为空
	return L;
}
           

4.按序号查找结点

//在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止。
LNode *GetElem(LinkList L, int i) {
	int j = 1;
	LNode *p = L->next; //头结点指针赋给p
	if (i == 0) return L; //若i=0， 则返回头结点
	if (i < 1) return NULL; //若i无效，则返回NULL
	while (p && j < i) { //从第一个结点开始找，查找第i个结点
		p = p->next;
		j++;
	}
	return p; //返回第i个结点的指针
}
           

5. 按值查找表结点

LNode *LocateElem(LinkList L, ElemType e) {
	LNode *p = L->next;
	while (p != NULL && p->data != e)
		p = p->next;
	return p;
}