大一计科菜鸡新开博客，姑且作为暑假的学习日志 ------------------------暑假安排（大概）-------------------------------------- 预计复习内容：链表，线性表，栈，队列，二叉树，算法分析，BFS,DFS算法，U3D的基本操作 新学编程内容：1，基础（离散数学）2.图论相关题目（生成树算法，网络流，最大流，匹配问题，匈牙利算法）3.一点计算几何内容拓展 新学开发内容：C#与U3D的交互，行为树与AI逻辑（完成三个完整的小项目）

---

链表：

自己的理解，概述：一种基本的数据结构。它的每一个节点（node）含有两部分的信息（1.该节点所存的数据 2.下一节点的地址） 因为每个节点存有下一节点的地址，所以所有节点可以形成一个链式的结构，即链表。最后一个节点若储存某一结点的信息，会使链表成为一个环形链表（可以用于解决约瑟夫环问题），每个节点还可以加上一个指向前一个节点的指针，这样链表就成为了一个双向链表。（参考STL库的List模板）

基本操作：

增（创建链表头，添加节点） 删（删去某个节点，删除整个链表） 查（查找某个结点所存的值，查找是否有含有某个值的节点） 改（修改某个节点所存的值） 链表反转（可能会出现在面试题里面，故加上） 遍历打印（差点忘了）

实现分析（c++）：

（一）数据结构设计

用一个类来包装整个链表，用一个结构体来表示链表的节点（用模板写成泛型） node作为list的一个private成员，公有成员包括：构造/析构函数，addnode（）用来添加节点，deleting(int no)来指定删除节点（重载一个无参的delete（）用来删除整个链表，放在析构函数里），modifying（int no，T a）用来找到某个节点，并修改其中的值，int getlength（）const 获得链表的长度

（二）相关定义，声明

定义一个节点：

template<typename T> class My_Node{ public: My_Node *pnext; My_Node *pprev; T data; };

定义链表：

template<typename T> class My_List{ public: My_List(); ~My_List(){ DeleteNode(); std::cout<<"destruction complete"<<std::endl; } void AddNode(T inpdata); void DeleteNode(int no); void DeleteNode();//overload for destruction void Traversing(); void Modifying(int no,T modi); void Reverse(); int GetLength() const{return length;} T GetElement(); private: My_Node<T> *head; int length; };

（三）函数实现代码

构造函数还是写一下，把length置为0，头节点初始化

//constructor template<typename T> My_List<T>::My_List(){ length=0; head = NULL; };

添加一个结点，注意判断一下链表是否还是空的

//addlistnode template<typename T> void My_List<T>::AddNode(T inpdata){ My_Node<T> *next,*prev; if(!head) { head=new My_Node<T>; head->data=inpdata; head->pnext=NULL; head->pprev=NULL; } else { next=head; while(next!=NULL) { prev=next; next=next->pnext; } next=new My_Node<T>; prev->pnext=next; next->pprev=prev; next->data=inpdata; next->pnext=NULL; } length++; }

遍历打印链表，测试时可以用

//traversing template<typename T> void My_List<T>::Traversing() { My_Node<T> *trav_ptr; trav_ptr=head; while(trav_ptr!=NULL) { std::cout<<trav_ptr->data<<" "; trav_ptr=trav_ptr->pnext; } std::cout<<"\n"; }

删除节点、链表

//deleting node(default) template<typename T> void My_List<T>::DeleteNode(int no) { My_Node<T> *trav_ptr1,*trav_ptr2,*trav_ptr3; trav_ptr1=trav_ptr2=trav_ptr3=head; int cnt=0; if(no>=length)std::cout<<"range exceeded!"<<std::endl; else { while(cnt<no-2) { trav_ptr1=trav_ptr1->pnext; cnt++; } trav_ptr2=trav_ptr1->pnext; trav_ptr3=trav_ptr2->pnext; delete trav_ptr2; trav_ptr1->pnext=trav_ptr3; } } //deleting node(overload) template<typename T> void My_List<T>::DeleteNode() { My_Node<T> *trav_ptr1=head; My_Node<T> *trav_ptr2=head; while(trav_ptr2!=NULL) { trav_ptr2=trav_ptr2->pnext; delete trav_ptr1; trav_ptr1=trav_ptr2; } } //modifying data template<typename T> void My_List<T>::Modifying(int no,T modi) { int cnt=0; My_Node<T> *trav_ptr=head; if(no>=length)std::cout<<"range exceeded!"<<std::endl; else { while(cnt<no-1) { trav_ptr=trav_ptr->pnext; cnt++; } trav_ptr->data=modi; } }

反转链表，写得很水，较为繁琐，日后来更新

template<typename T> void My_List<T>::Reverse() { My_Node<T> *next,*current; current=next=head; current=current->pnext; next=current->pnext; head->pnext=NULL; while(next!=NULL) { current->pnext=head; current->pprev=next; head=current; current=next; next=next->pnext; } current->pnext=head; head=current; }

结：思考不够深入，还有些地方可以优化，请等我之后的更新吧…（咕