單項循環鏈表及其帶頭指針的鏈表

對于鏈表我們要仔細深入的學習它，為何呢，因為他是我們在后面學習非線性數據結構的基礎，像后面的樹，圖等結構都是由鏈表演變出來的，所以我們這篇博客繼續探究鏈表

帶頭指針的鏈表

我們上篇博客講述了帶頭節點的鏈表

如圖

然后演示出了一系列公式化的打法

像什么插入刪除

//找到前置節點p
//插入
new_node->next=p->next;
p->next=new_node;
//刪除
temp=p->next;
p->next=temp->next;
free(temp);

但是我們今天的主角帶頭指針的鏈表，你需要考慮的就多了，公式化的打法已經無法滿足我們了

看圖

那我們是否能復刻之前的打法，一套代碼打天下？

肯定不行，你會發現你想要采用頭插法一下就要如下

new_node->next=head;
head=new_node;

當你遇見空的頭指針的時候還要if一下，看起來就麻煩。

那么有簡化一下書寫難度的方法嗎？

有的兄弟，有的。

我們可引入一個dummy節點，這個節點是一個臨時節點，然后將指針的信息臨時傳入進去，而后我們就可以繼續我們的公式化打法處理了，處理完以后再將地址的 值返回。

如圖

這樣的好處就又回到了之前的公式化的打法，只要我們注意最后的維護就行了

具體的代碼如下

帶頭指針的鏈表（代碼）

結構定義及其接口

#ifndef CHAINLIST_H
#define CHAIN_LIST_H
//帶頭指針的單向鏈表，維護節點也是node
#include"common.h"//定義鏈表頭結構只保存頭指針
typedef struct {node_t *header;int cout;}ChainList_t;
//表頭放到數據區，放到全局變量
//初始化
void initChainList(ChainList_t *table);
//釋放空間
void destoryChainList(ChainList_t *table);//插入
int insertChainListHeader(ChainList_t* table, Element_t data);//頭插法
int insertChainListpos(ChainList_t* table,int pos, Element_t data);//按位置插入//刪除
int deleteChainListHeader(ChainList_t* table, Element_t data);//打印
void showChainList(const ChainList_t* table);#endif //CHAIN_LIST_H

對操作的具體實現

#include <stdio.h>
#include <stdlib.h>
#include "chainList.h"void initChainList(ChainList_t *table) {table->cout=0;table->header=NULL;
}int insertChainListHeader(ChainList_t *table, Element_t data) {node_t dummy;//定義臨時節點dummy.next=table->header;node_t*p=&dummy;node_t* newnode=(node_t*)malloc(sizeof(node_t));if (newnode==NULL) {return -1;}newnode->data=data;newnode->next=p->next;p->next=newnode;;++table->cout;table->header=dummy.next;return 0;
}int insertChainListpos(ChainList_t *table, int pos, Element_t data) {node_t dummy;dummy.next=table->header;//判斷邊界條件if (data<0||pos>table->cout) {return -1;}//尋找到插入位置node_t *p=&dummy;int node=-1;while (node<pos-1) {p=p->next;node++;}//插入node_t *newnode=(node_t*)malloc(sizeof(node_t));newnode->data=data;newnode->next=p->next;p->next=newnode;++table->cout;table->header=dummy.next;return 0;}
int deleteChainListHeader(ChainList_t *table, Element_t data) {node_t dummy;dummy.next=table->header;node_t* p=&dummy;while (p->next&&p->next->data!=data) {p=p->next;}//判斷是否為空if (p->next==NULL) {printf("No find");return-1;}//刪除node_t*node=p->next;p->next=node->next;free(node);table->cout--;table->header=dummy.next;return 0;}void destoryChainList(ChainList_t *table) {node_t dummy;dummy.next=table->header;node_t* p=&dummy;node_t*node;while (p->next) {node=p->next;p->next=node->next;free(node);table->cout--;}printf("link list number %d",table->cout);}void showChainList(const ChainList_t *table) {node_t* p=table->header;printf("link list number %d\n:",table->cout);while (p) {printf(" %d ",p->data);p=p->next;}printf("\n");}

其實說實話跟之前的帶鏈表的頭指針一樣，只不過需要先申請一個節點對節點做包裝，而后維護一下表頭指針的數據罷了。

我們再來做一下測試

int text2() {ChainList_t stu1;initChainList(&stu1);for (int i=0;i<10;i++) {insertChainListHeader(&stu1,i+100);}insertChainListpos(&stu1,3,300);showChainList(&stu1);destoryChainList(&stu1);}int main() {text2();return 0;
}

這就是對帶頭指針的鏈表的實現

但是如果我們再想提出一個需求，就是鏈表的最后的一個元素要指向第一個元素應該咋整。

這就是引出我們下一個主題

單項循環鏈表

單項循環鏈表

在開始我們的學習之前，我們可以先思考一個對代碼

node_t*p=&header;
while(p->next)
{p=p->next;
}
……node_t*p=&header;
while(p)
{p=p->next
}

你思考就會發現，這兩段代碼是站在不同的角度進行遍歷的，一個是對自己前一個元素進行看的，一個是對自己本身進行看的。

前者更適合插入和刪除，而后者更適合遍歷。

但是，一到循環鏈表這兩段代碼就不管用了，為啥？因為首尾連接了唄。

很自然的，也有兩種循環鏈表的表示方法，一種是帶頭指針的，一種是不帶頭指針的

帶頭指針的

不帶頭指針的

很正常的我們先實現帶頭指針的

單項循環鏈表代碼

結構定義以及函數接口

#ifndef LINKLOOP_H
#define LINKLOOP_H
typedef int Element;
//節點
typedef struct _loop_node {Element val;struct _loop_node *next;}loopnode;
//頭節點
typedef struct {loopnode head;loopnode *tail;int num;
}LinkLoopList;//結構操作
//初始化
void initLinkLoopList(LinkLoopList *link_loop);
//插入(頭插，尾插)
int insertLinkLoop(LinkLoopList *link_loop, Element val);
int inserLinkLoopRear(LinkLoopList *link_loop, Element val);
//遍歷顯示
void showLinkLoop(const LinkLoopList *link_loop);
//刪除
int deleteLinkLoop(LinkLoopList *link_loop, Element val);
//釋放空間不釋放表頭
void destoryLinkLoopRear(LinkLoopList *link_loop);#endif //LINKLOOP_H

結構操作的實現

#include "linkLoop.h"
#include <stdio.h>
#include <stdlib.h>void initLinkLoopList(LinkLoopList *link_loop) {//循環鏈表一開始就要指向自己link_loop->head.next=link_loop->tail=&link_loop->head;link_loop->num=0;}int insertLinkLoop(LinkLoopList *link_loop, Element val) {//先定義一個新節點loopnode*node=malloc(sizeof(loopnode));if (node==NULL)return -1;node->val=val;node->next=link_loop->head.next;link_loop->head.next=node;//判斷是否維護尾指針if (link_loop->tail==&link_loop->head) {link_loop->tail=node;}link_loop->num++;return 0;}int inserLinkLoopRear(LinkLoopList *link_loop, Element val) {loopnode*node=malloc(sizeof(loopnode));if (node==NULL)return -1;node->val=val;node->next=link_loop->tail->next;link_loop->tail->next=node;link_loop->tail=node;link_loop->num++;return 0;}void showLinkLoop(const LinkLoopList *link_loop) {loopnode*node=link_loop->head.next;while (node!=&link_loop->head) {printf("%d->", node->val);node=node->next;}printf("\n");}int deleteLinkLoop(LinkLoopList *link_loop, Element val) {loopnode*node=&link_loop->head;while (node->next!=&link_loop->head&&node->next->val!=val) {node=node->next;}if (node->next->val==val) {loopnode *tmp=node->next;node->next=tmp->next;free(tmp);link_loop->num--;}else {printf("not found%d\n",val);}return 0;}void destoryLinkLoopRear(LinkLoopList *link_loop) {loopnode*node=link_loop->head.next;while (node!=&link_loop->head) {loopnode *tmp=node;node=node->next;free(tmp);link_loop->num--;}printf("Table %d element\n",link_loop->num);
}

測試函數

#include "linkLoop.h"void text1() {LinkLoopList table;initLinkLoopList(&table);for (int i = 0; i < 10; i++) {inserLinkLoopRear(&table, i+100);}deleteLinkLoop(&table,101);showLinkLoop(&table);destoryLinkLoopRear(&table);}int main() {text1();return 0;
}

結構如下

好了這篇博客到這里就結束了，喜歡的點點贊(?′?‵?)Ｉ L???????