【数据结构】单链表的基本操作及实现

        线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素的存储映像，称为节点，它包括两个域，其中存储数据单元信息的域被称为数据域，存储直接后继存储位置的域被称为指针域，指针域中的存储信息乘坐指针或链。n个节点((1<=i<=n)的存储映像)链接成一个链表，即为线性表。

        单链表特点：随机存储，顺序存取。

        下图即为单链表的图示表示，其中蓝色框表示节点的地址，第一个为头指针，它只存储第一个节点的地址。Data为数据域，Next为指针。

        图一       

        我创建的单链表结构体如下所示。注意最后一行注释，这里使用一个LNode表示该结构体，*linkList表示该结构体的地址

typedef struct LNode {
	ElemType data;
	LNode* next;
}LNode, *linkList;//注意

        本次初始化代码如下所示，当调用初始化方法，在方法体内声明一个linkList变量，即表示LNode结构体类型的地址（图一中的Head）。我这里没有进行分配失败判断，自己写的时候要注意。分配成功后，将该节点的next属性赋成NULL，即没有直接后继。最后将这个节点返回， 即头结点。

linkList InitLNode() {
	linkList L;
	L = (linkList)malloc(sizeof(LNode));
	L->next = NULL;
	return L;
}

        下面代码是自己根据自己思路完成，有很多可以优化的地方。特别是单链表的逆置操作。

//线性表的单链表
# include
# include
 #define ERROR -2
typedef char ElemType;

typedef struct LNode {
	ElemType data;
	LNode* next;
}LNode, *linkList;

linkList InitLNode() {
	linkList L;
	L = (linkList)malloc(sizeof(LNode));
	L->next = NULL;
	return L;
}

void createlinkList(linkList L, int num) {
	int elem = 0;
	linkList head = L;
	printf("请输入元素内容");
	for (int i = 0; i < num; i++) {
		L->next = (LNode*)malloc(sizeof(LNode));
		scanf_s("%d", &elem);
		L->next->data = elem;
		L = L->next;
	}
	L->next = NULL;
	L = head;
}
//获取链表长度
int listLength(linkList L) {
	linkList first = L;
	int length = 0;
	while (L->next != NULL) {
		length++;
		L = L->next;
	}
	L = first;
	return length;
}
//定位某个元素
void LocationElem(linkList L, ElemType elem) {
	int i = 0;
	bool flag = false;
	linkList first = L;
	while (L->next != NULL){
		i++;
		if (L->next->data == elem) {
			flag = true;
			printf("%d位于第%d位",elem,i);
		}
		L = L->next;
	}
	L = first;
	if (!flag) {
		printf("抱歉，没有该元素");
	}
}
//通过位置获取元素
void GetElem(linkList L, int Location) {
	LNode* first = L;
	int i = 0;
	int length = 0;
	while (L->next != NULL) {
		length++;
		L = L->next;
	}
	L = first;
	if (length < Location|| Location<1) {
		printf("下标不合法n");
		L = first;
		return;
	}
	else {
		while (i < Location) {
			L = L->next;
			i++;
		}
		printf("第%d位置的元素是%dn",Location, L->data);
		L = first;
	}
}
//插入元素
void InsertList(linkList L, ElemType elem, int location) {
	LNode* wait = NULL;//待插入LNode
	LNode* wait_next = NULL;
	LNode* first = L;
	int i = 0;
	int length = 0;
	while (L->next != NULL) {
		length++;
		L = L->next;
	}//获取链表长度
	L = first;
	if (location > length + 1 || location < 1) {
		printf("下标不合法n");
		L = first;
		return;
	}
	while (i <= (location - 2)) {
		L = L->next;
		i++;
	}//将L转到插入位置的前面
	wait_next = L->next;
	wait = (LNode*)malloc(sizeof(LNode));//分配空间给待插入的LNode
	wait->data = elem;
	L->next = wait;//将待插LNode的前一个LNode的next指向待插LNode地址
	wait->next = wait_next;
	printf("插入成功n");
	L = first;
}

void deleteElem(linkList L, int location) {
	LNode* first = L;
	int i = 0;
	int length = 0;
	while (L->next != NULL) {
		length++;
		L = L->next;
	}//获取链表长度
	L = first;
	if (location > length || location < 1) {
		printf("下标不合法n");
		L = first;
		return;
	}
	while (i < location -1 ) {
		L = L->next;
		i++;
	}
	L->next = L->next->next;
	printf("删除成功");
	L = first;
}
//打印单链表
void print(linkList L) {
	LNode* first = L;
	while (first->next != NULL) {
		printf("%d ", first->next->data);
		first = first->next;
	}
}
//由于传进地址，排序完成后无法恢复原样
void sort(linkList L) {
	ElemType temp;
	LNode* first = L;
	LNode* flag = L;
	int i = 0;
	int length = 0;
	while (L->next != NULL) {
		length++;
		L = L->next;
	}//获取链表长度
	L = first;
	for (int i = 0; i < length-1; i++) {
		//flag = L;
		for (int j = 0; j < length - i - 1; j++) {
			if (L->next->data > L->next->next->data) {
				temp = L->next->data;
				L->next->data = L->next->next->data;
				L->next->next->data = temp;
			}
			L = L->next;
		}
		//L = flag->next;
		L=first;
	}
	L = first;
	print(L);
}
//逆置
void Invert(linkList L) {
	LNode* first = L;
	LNode* last = L;
	ElemType temp;
	int i = 0;
	int length = 0;
	int length_temp;//用来获取后一半的节点
	while (L->next != NULL) {
		length++;
		L = L->next;
	}//获取链表长度
	length_temp = length;
	last = L;//将最后倒数的节点节点赋给last变量
	L = first;
	for (i = 0; i < length / 2; i++) {
		temp = L->next->data;
		L->next->data = last->data;
		last->data = temp;//交换完毕

		L = L->next;
		last = first;//重新找下一个last节点
		length_temp--;
		for (int j = 0;j < length_temp; j++) {
			last = last->next;
		}//找到后面的节点
	}
	L = first;
	printf("逆置成功n");
	print(L);
}



int main() {
	linkList L = NULL;
	int elem;
	int operate = -1;//操作数
	int length = 0;//求表长用到
	int num = 0;//表元素个数
	int location = 0;//元素下标
	printf("请输入要进行的操作n");
	printf("1---创建单链表n");
	printf("2---单链表长度n");
	printf("3---求指定元素的位置n");
	printf("4---给定下标获取元素n");
	printf("5---插入元素n");
	printf("6---删除元素n");
	printf("7---排序n");
	printf("8---逆置单链表n");
	printf("11---打印单链表n");
	while (operate != 0) {
		scanf_s("%d", &operate);
		switch (operate){
			case 1:
				printf("请输入元素个数n");
				scanf_s("%d", &num);
				L = InitLNode();
				createlinkList(L, num);
				printf("请输入编号进行下一步操作n");break;
			case 2:
				length = listLength(L);
				printf("单链表的长度是%dn", length);
				printf("请输入编号进行下一步操作n");break;
			case 3:
				printf("请输入你想定位的元素n");
				scanf_s("%d", &elem);
				LocationElem(L, elem);
				printf("请输入编号进行下一步操作n");break;
			case 4:
				printf("请输入元素下标:n");
				scanf_s("%d", &location);
				GetElem(L, location);
				printf("请输入编号进行下一步操作n");break;
			case 5:
				printf("请输入插入的元素和插入位置:n");
				scanf_s("%d %d",&elem, &location);
				InsertList(L, elem, location);
				printf("请输入编号进行下一步操作n");break;
			case 6:
				printf("请输入你想删除的元素的位置n");
				scanf_s("%d", &location);
				deleteElem(L, location);
				printf("请输入编号进行下一步操作n");break;
			case 7:
				sort(L);
				printf("请输入编号进行下一步操作n");break;
			case 8:
				Invert(L);
				printf("请输入编号进行下一步操作n");break;
			case 11:
				print(L);
				printf("请输入编号进行下一步操作n");break;
		}
	}

}

  参考：严蔚敏 吴伟民《数据结构（C语言版）》----清华大学出版社