数据结构基础之单链表
对单链表的建立，插入，删除，逆序，打印元素做一个小小的总结，不过我不觉得这些东西在具体的工作后到底能发挥什么作用，因为强大的STL已经把这些都做好了，我们只需要明白在什么场合使用哪一个STL就可以了。链表有一个数据域，有一个指针域，它的操作其实就是对指针域的操作，无非是指来指去而已。也许这些能反映出一个人的思维敏捷度，以及扎实的编程基础吧。
但是我想说的是这些玩意在你头脑比较清楚的时候写这个很简单，但是当你烦躁的时候，不好写吧，除非你经常写这个。单链表看着简单，但是不见得能写的正确。
该代码经过验证，测试正确，但是代码中不免有错误之处，或者哪些部分写的不好，希望高手能指出来，不胜感激。因为代码必须经过验证，那些没有经过验证的代码是不负责任的代码。在代码中我加了详细的注释。
#include <stdio.h>#include <string>#include <iostream>using namespace std;typedef struct NODE_STRU{int data;//数据域struct NODE_STRU *next;//指针域}NODE;//创建单链表NODE *Create(){NODE *head, *p, *s;//head表示头结点，p表示当前节点，s表示添加的新节点int input_data;int cycle_flag = 1;head = (NODE*)malloc(sizeof(NODE));//首先为头结点分配空间p = head;//当前节点指向头结点while(cycle_flag){cout << "please input data(if input 0, cycle over!):"<< endl;cin >> input_data;if(0 != input_data){s = (NODE*)malloc(sizeof(NODE));//为新添加的数据分配节点空间s->data = input_data;p->next = s;//当前节点的下一个节点指向新节点p = s;//将当前节点指向新节点}else{cycle_flag = 0;}}head = head->next;//由于头结点没有数据，使头结点指向下一个节点，即指向第一个真正的节点p->next = NULL;//数据插入完成后，当前节点也跑到了最后，使它的下一个节点置为NULL，表示节点完成return head;}//单链表测长,这个很简单，只需判断当前节点（初始化当前节点为头结点）是不是为空，如果不为空指向下一个节点，并计数就可以了int Length(NODE *head){int length = 0;NODE *p = head;while(p != NULL){p = p->next;length++;}return length;}//打印单链表，这个也很简单，在当前节点（初始化当前节点为头结点）不为空时候，打印出来，并使得当前节点指向下一个节点即可void Print(NODE *head){NODE *p = head;int length = Length(head);cout << "link length is: " << length << endl;while(p != NULL){cout << "data: " << p->data << "\t";p = p->next;}}//删除节点,这里的删除节点是根据节点数据进行删除的，不是从第一个节点进行删除，也不是从最后一个节点进行删除//p->next = p->next->nextNODE *Del(NODE *head, int num){NODE *p1, *p2;//p1表示当前节点，初始化时指向头结点p1 = head;while(num != p1->data && p1->next != NULL)//如果当前节点的数据域与要删除的数据不相等，，使当前节点指向下一个节点{p2 = p1;//在未找到节点时指针指向下一个节点前，先保存该节点p1 = p1->next;}if(num == p1->data)//如果当前节点数据域与要删除的数据相等{if(p1 == head)//如果当前节点为头结点，将头结点指向当前节点的下一个节点，并释放当前节点{head = p1->next;free(p1);}else//如果当前节点为中间节点，使当前节点指向下一个节点，注意：这里不能使用p1->next=p1->next->next,使用之前保存的节点p2->next = p1->next;}elsecout << num << "can not find in link!" << endl;return head;}//插入节点，在这里只在链表的结尾进行插入NODE *Insert(NODE *head, int num){NODE *p0, *p1, *p2;//p0表示新插入的节点，p1表示当前节点，初始化的时候指向头结点，p2用于保存当前节点p1 = head;p0 = (NODE *)malloc(sizeof(NODE));p0->data = num;while(p1->next != NULL)//如果当前节点的下一个节点不为空，当前节点指向下一个节点，这样当前节点最后为最后一个节点{p2 = p1;p1 = p1->next;}p1->next = p0;p0->next = NULL;return head;}//进行排序，其实就是简单的冒泡排序，时间复杂度为O(n2),空间复杂度为O(1),稳定NODE *Sort(NODE *head){NODE *p;if(head == NULL || head->next == NULL)return head;int length = Length(head);//得到链表的长度，用于遍历for(int i=1; i<length; i++){p = head;for(int j=0; j<length-i; j++){if(p->data > p->next->data){int temp = p->data;p->data = p->next->data;p->next->data = temp;}p = p->next;}}return head;}//链表逆序NODE *Reverse(NODE *head){if(head == NULL || head->next == NULL)return head;//这样来实现，在链表中一次从链表尾删除节点，然后在新建立的链表中插入节点（尾插法）int length = Length(head);int a[length];int i = 0;NODE *p = head;while(p != NULL){a[i] = p->data;i++;p = p->next;}for(int j=0; j<length; j++)//暂时用于测试cout << j << ":" << a[j]<<"\n";NODE *newhead, *link, *s;newhead = (NODE *)malloc(sizeof(NODE));link = newhead;for(int k=length-1; k>=0; k–){s = (NODE *)malloc(sizeof(NODE));s->data = a[k];link->next = s;link = s;}newhead = newhead->next;link->next = NULL;return newhead;}//求单链表的中间节点void SearchMid(NODE* head){cout << "head data: " << head->data<< "\n";NODE *tmp1 = head;NODE *tmp2 = head;NODE *mid;while(tmp1->next != NULL && tmp1->next->next != NULL){tmp1 = tmp1->next->next;tmp2 = tmp2->next;cout << "tmp1:" << tmp1->data<< ",tmp2:" << tmp2->data<<"\n";}mid = tmp2;cout << "SearchMid mid data: " << mid->data;}int main(int argc, char *argv[]){cout << "create link…\n" << endl;NODE *p = Create();cout << "print link…\n" << endl;Print(p);int delnode;cout << "\ninput delete node: ";cin >> delnode;cout << "\ndelete node " << delnode << endl;Del(p, delnode);cout << "print link…" << endl;Print(p);cout << "\ninsert link…\n";Insert(p, 20);Print(p);cout <<"\nsort from low to high…";Sort(p);Print(p);cout << "\nreverse…\n";NODE *revlink = Reverse(p);Print(revlink);cout << "\nfind mid node data…\n";SearchMid(p);return 0;}
运行结果：
还有不愿面对失败的尴尬。曾经怀有远大理想，拥有完美的憧憬。
