c++数据结构单链表

一:提要:

链表是线性表的链式存储方式,链表的构成: 数据域和指针域,指针指向下一个节点的内存地址,是链式线性结构;方便增加元素和删除元素.

二,链表的定义:

//链表定义typedef struct LINKLIST{	int data;  //数据域	struct LINKLIST *next;//指针域//指向下一个节点}linkList,linkNode;//linkList 表示头结点,linkNode 表示节点

linkList* head;linkNode* node;

三:链表的初始化:

//链表初始化bool linkInit(linkList* &L) {	L = new linkList;//动态分配	if (!L) { return false; }	L->next = NULL;	L->data = -1;//头结点一般没有数据	return true;}

参数是头结点的指针引用

四:链表的前插法

//前插法bool linkNode_front(linkList* & L,linkNode* &N) {		if (!L || !N) {		return false;	}	if (L->next == NULL) {//如果就一个头结点时		L->next = N;		N->next = NULL;		return true;	}	//新的节点插在头结点	N->next = L->next;//新的节点指向头结点的下一个节点	L->next = N;//头结点指向新的节点	return true;}

在main函数调用时:

linkList* head;	linkNode* node;	int count;	int site;		if (!linkInit(head)) {		cout << "初始化失败" << endl;		return 1;	}		cout << "使用前插法插入元素的个数:";	cin >> count;	for (int i = 0; i < count; i++) {		//每个节点都需要动态内存空间		node = new linkNode;		cout << "请输入元素:";		cin>>node->data;		if (!linkNode_front(head, node)) {			cout << "插入失败" << endl;			return 2;		}	}

五:链表的尾插法

//尾插法bool linkNode_back(linkList* &L, linkNode* &N) {	linkNode* s;//创建临时节点	if (!L || !N) {		return false;	}	if (L->next == NULL) {//如果就一个头结点时		L->next = N;		N->next = NULL;		return true;	}		s = L;//头结点赋值给临时节点	while (s->next) {//s指向下一个节点=NULL结束循环		s = s->next;	}	//链表的最后一节点的指针域是NULL	//循环结束后就是链表的尾部	s->next = N;//最后一个节点指向新的节点	N->next = NULL;//新的节点重新指向NULL		return true;}

在main函数调用时:

cout << "使用尾插法插入元素的个数:";	cin >> count;	for (int i = 0; i < count; i++) {		node = new linkNode;		cout << "请输入元素:";		cin >> node->data;		if (!linkNode_back(head, node)) {			return 2;		}	}