数据结构-单链表

1、单链表 

#include<stdio.h> #include<iostream> using namespace std; #define MAX_SIZE 255 // 1、定义数据元素 struct ElementType { int id; char* name; }; // 2、定义顺序表结构 struct Seqlist { ElementType datas[MAX_SIZE]; // 顺序表中数据元素结合 int length; //当前顺序表中元素的个数 }; // 3、定义链表的结点，包含数据域和指针域 struct Node { ElementType data; // 数据域 Node* next; // 指针域，指向下个结点 }; // 4、定义头结点 // 定义链表时，习惯性的会定义头节点，以便统一链表结点的插入和删除操作 // 头结点也可以称为首元结点，最后一个结点叫做尾元结点 struct LinkList { Node* next = NULL; // 头指针（如果链表有头结点，next就指向头结点；没有就指向第一个结点） int length; // 链表的长度，初始值为0 }; // 5、初始化链表 void InitLinkList(LinkList* linklist, ElementType *dataArray, int length); // 6、在指定的位置插入链表 void InsertLinkList(LinkList* linklist, int pos, ElementType element); // 7、打印列表 void PrintLinkList(LinkList* linklist); // 8、链表是否为空 int IsLinkListEmpty(LinkList* linkList); // 9、返回pos位置的元素 ElementType GetLinkList(LinkList* linkList, int pos); // 10、删除pos位置的元素 ElementType DeleteLinkListElement(LinkList* linkList, int pos); // 11、单链表的整表删除 // 销毁单链表，释放内存空间 // (1)声明结点p和q // (2)将第一个结点赋值给p // (3)循环将下一个结点赋值给q，释放p,将q赋值给p void ClearLinkList(LinkList* linkList); ElementType dataArray[] = { {1, "史莱克"}, {2, "哥斯拉"}, {3, "蜥蜴长者"}, {4, "远古魔像"}, {5, "纳什男爵"} }; void TestLinkList() { LinkList linklist; linklist.length = 0; // 容易忽略的地方 InitLinkList(&linklist, dataArray, 5); PrintLinkList(&linklist); // 测试插入结点 cout << "==========测试插入结点================" << endl; Node newNode; newNode.data.id = 2017; newNode.data.name = "孙浩楠"; InsertLinkList(&linklist, 2, newNode.data); PrintLinkList(&linklist); // 测试获取结点 cout << "=============测试获取结点==============" << endl; ElementType receivedNode; receivedNode = GetLinkList(&linklist, 2); cout << receivedNode.id << " " << receivedNode.name << endl; // 测试删除结点 cout << "==========测试删除结点==================" << endl; ElementType deletedNode; deletedNode = DeleteLinkListElement(&linklist, 2); cout << "删除结点的id:" << deletedNode.id<< "\n" << "删除结点的name:" << deletedNode.name << endl; cout << "打印删除结点后的列表：" << endl; PrintLinkList(&linklist); cout << "==============测试清空列表==================" << endl; ClearLinkList(&linklist); PrintLinkList(&linklist); } int main() { TestLinkList(); system("pause"); } void InitLinkList(LinkList* linklist, ElementType *dataArray, int length) { for (int i = 0; i < length; i++) { InsertLinkList(linklist, i + 1, dataArray[i]); } } void InsertLinkList(LinkList* linklist, int pos, ElementType element) { // 1、创建空结点并为数据域赋值 Node* node = new Node(); node->data = element; node->next = NULL; // 2、找到要插入位置的结点 if (pos == 1) // 如果插入的是第一个元素，非常简单 { node->next = linklist->next; linklist->next = node; linklist->length++; return; } // 通过循环找到要插入的结点位置 Node* currNode = linklist->next; for (int i = 1; currNode && i < pos - 1; i++) { currNode = currNode->next; } // 3、将结点插入，并对接前面的结点 if (currNode) { node->next = currNode->next; // 把当前结点的下一条赋值给插入结点的下一条（右侧对接完成） currNode->next = node; // 把插入结点赋值给当前结点（左侧对接完成） linklist->length++; } } void PrintLinkList(LinkList* linklist) { Node* node = linklist->next; if (!node) { cout << "链表为空" << endl; linklist->length = 0; return; } for (int i = 0; i < linklist->length; i++) { cout << node->data.id << " " << node->data.name << endl; node = node->next; } } int IsLinkListEmpty(LinkList* linkList) { return linkList->length == 0 ? 1 : 0; } ElementType GetLinkList(LinkList* linkList, int pos) { Node* node = linkList->next; for (int i = 0; node&& i < pos - 1; i++) { node = node->next; } return node->data; } ElementType DeleteLinkListElement(LinkList* linkList, int pos) { ElementType element; // 被删除的元素 element.id = -999; Node* node = NULL; if (pos == 1) { node = linkList->next; if (node) { element = node->data; linkList->next = node->next; delete(node); // 释放结点的内存，容易遗漏 linkList->length--; } return element; } // 不是第一个结点，删除的方法 // 1、找到要删除结点和它的前缀结点 // 2、要删除结点->next赋值给前缀结点->next // 3、释放要删除的结点内存 Node* preNode = NULL; //前缀结点 node = linkList->next; for (int i = 0; node && i < pos - 1; i++) { preNode = node; node = node->next; } if (node) { element = node->data; preNode->next = node->next; delete(node); linkList->length--; } return element; } void ClearLinkList(LinkList* linkList) { Node* node = linkList->next; Node* nextNode; while (node) { static int i = 0; i++; nextNode = node->next; // 先记录当前结点的下个结点，以便释放当前结点的内存 cout << node->data.id << " " << node->data.name << endl; delete(node); node = nextNode; } linkList->next = NULL; linkList->length = 0; }