网页设计学校网站,为企业做贡献的文章,底湘西网站建设,seo网站推广公司单链表一种以链接方式存储的线性表#xff0c;适用于频繁增删操作#xff0c;存储空间不定的情形。单链表的一个存储结点包含两个域#xff0c;数据域和指针域。数据域用于存储线性表的一个数据元素#xff0c;指针域用于指示下一个结点开始的存储地址。链表第一个结点的地… 单链表一种以链接方式存储的线性表适用于频繁增删操作存储空间不定的情形。单链表的一个存储结点包含两个域数据域和指针域。数据域用于存储线性表的一个数据元素指针域用于指示下一个结点开始的存储地址。链表第一个结点的地址可通过头指针找到其他结点的地址则在前驱结点的指针域中最后一个结点没有后继用NULL终结。为了操作的方便习惯上单链表带一个头结点也就是first指向的第一个结点不存放任何数据从第二个结点开始存放数据。由于指针域的存在数据元素的顺序与物理存储顺序可能不一致。定义与封装//结点的定义struct LinkNode { //链表结点类的定义int data; //数据域 LinkNode *link; //链指针域 LinkNode() { link NULL; } //构造函数 LinkNode(int item, LinkNode *ptr NULL) { data item; link ptr; } //构造函数};//链表操作封装class List{protected:LinkNode *first; //表头指针头结点public: List() { first new LinkNode; } //构造函数 List(int x) { first new LinkNode(x); } ~List(){ } //析构函数void inputFront (int val);LinkNode *Search(int x); //搜索含x元素LinkNode *Locate(int i); //返回第i个元素地址bool Insert (int i, int x); //在第i元素后插入bool Remove(int i, int x); //删除第i个元素bool IsEmpty() const //判表空否{ return first-link NULL ? true : false; }void show();};带附加头结点的插入操作1、newnode-link p-link; 2、p-link newnode;注意图中标1和2的位置与代码相结合//将新元素 x 插入在链表中第 i 个结点之后。bool List::Insert (int i, int x) { LinkNode *current Locate(i);if (current NULL) return false; //无插入位置 LinkNode *newNode new LinkNode(x); //创建新结点 //图中标识的1处在不破坏原链表的情况下让新结点先链入 newNode-link current-link; //链入 //图中标识的2处接到新结点 current-link newNode; return true; }带附加头结点的查找操作查找过程就是从第一个结点开始不断沿着link域寻到和所需值相同的结点//在表中搜索含数据x的结点, 搜索成功时函数返//该结点地址; 否则返回NULL。LinkNode *List::Search(int x) { LinkNode *current first-link;while( current ! NULL current-data ! x ) current current-link; //沿着链找含有x的结点return current;}带附加头结点的删除操作1、q p-link;2、p-link q-link;3、delete q; //删除链表第i个元素, 通过引用参数x返回元素值bool List::Remove (int i, int x ) {//图中指针p LinkNode *current Locate(i-1);if(current NULL || current-link NULL) return false; //删除不成功 //图中指针q LinkNode *del current-link; //图中操作2p的link指向指针q的link指向的域越过q current-link del-link; x del-data; //脱节的q可以直接删除 delete del; return true;}附加头结点的单链表创建一般单链表的创建可采用前插法或者尾插法前插法就是每来一个新的结点就把这个结点插在头结点的后面。尾插法就是每来一个新的结点就把这个结点插在链表最后一个结点的后面相比前插法需要设置一个尾指针。实现插入过程和链表的插入操作几乎无区别。void List::inputFront (int val) { LinkNode *newNode new LinkNode;if(newNodeNULL) return; newNode new LinkNode(val);newNode-link first-link; //插在表前端 first-link newNode;}优点长度很容易方便扩充。缺点存储空间上多了指针域存储空间代价比顺序表大。至于带附加头节点和不带附加头节点的好处看过书的同学都知道前者的增删操作更简练代码https://github.com/xiaoYaChh/datastructure.git参考资料数据结构第二版殷人昆清华大学出版社
