单项链表（数据结构）

目录

单项链表：

单向链表结点

单项链表的初始化：

单向链表的头插法

 单项链表的打印：

单项链表的尾插法

获取链表上的指定元素

获取链表上指定位置上的元素

删除链表上指定位置的元素

删除链表上指定元素所在的结点

在链表指定位置前插入一个结点

插入一个元素使得整个链表依然保持为升序

销毁链表

总的代码：

 前面学习顺序表的时候，线性表的数据储存结构的特点是逻辑关系上相邻的两个元素在物理位置上也是相邻的，虽然顺序表的查询很快，但是由于时间复杂度问题，增删的效率是比较低的，每一次的增删操作都伴随的大量的移动。

　    线性表的链式存储结构（也称之为链表）的特点是逻辑关系上相邻的两个数据元素在物理位置上不一定是相邻的，换言之数据元素在存储器中的位置可以是任意的。为了表示每个数据元素ai与其直接后继 ai+1之间的逻辑关系，对于数据元素ai来说，除了存储其本身的信息外，还需存储一个能够保存直接后继的存储位置的指针，这两部分信息组成数据元素ai的存储映像，我们称之为结点（node）。

        结点包含两个或者三个域：存储数据元素信息的域叫做数据域，存储直接后继存储位置的域叫做指针域，存储直接前驱存储位置的域也叫做指针域。

　　如果只有一个指针域保存直接后继存储位置，这样的链表我们称之为单向链表。

　为了方便对链表进行插入结点和删除结点的操作，一般地链表中的第一个结点不存储实际的数据元素，该结点我们称之为：头结点。

　　单向链表的头结点中数据域不存储实际数据元素：

单项链表：

        在对单项链表经行访问的时候，需要使用一个结点（头节点），这个指针我们称之为头指针。头指针保存了链表中头节点的存储位置、

单向链表结点

/** 单项链表的结点* */
typedef int ElemType ;
typedef struct LNode{ElemType data;//数据域struct LNode *next;//指针域，指向当前结点的直接后继} LNode,*LinkList;//LinkList 的类型为LNode*

单项链表的初始化：

当链表为空的时候头结点的指针域为空；

初始化一个链表：

1、创建一个头结点，头结点的指针域为空

2、创建一个头指针，头指针指向头结点

/** @brief 单项链表的初始化* @return 返回链表的头指针* */
LinkList List_Init()
{LNode *t;t=(LNode *)malloc(sizeof(LNode));//创建一个头节点t->next=NULL;LinkList head;//定义一个头指针head = t;//头指针指向头节点return head;
}

单向链表的头插法

1、创建一个新的结点p

2、将新的结点p的next指向头结点的下一个结点

3、头结点的next指向新的结点p

//单项链表的头插法
/** @brief 头插法插入一个结点* @param 需要插入链表的头指针* @param 需要插入的数据* return 成功返回TRUE,失败返回FALSE* */
int Head_Insert(LinkList head,ElemType data)
{if(NULL==head)return FALSE;//创建一个新的结点pLNode *p=(LNode *)malloc(sizeof(LNode));p->data=data;//将新的结点p的next指向头结点的下一个结点(之前的上一个结点)（head->next）p->next=head->next;//头结点的next指向新的结点phead->next=p;return TRUE;
}

 单项链表的打印：

1、使用一个临时指针指向头结点后的第一个结点

2、使用临时指针进行遍历，直到临时指针为NULL

//单项链表的打印
/** @brief 输出链表中的所有结点* @param head 链表的头指针* @return 成功返回TRUE ，失败返回FALSE* */
int Print_List(LinkList head)
{if(NULL==head)return FALSE;//使用一个临时指针对链表进行遍历LNode *p=head->next;while(p!=NULL){printf("[%d]",p->data);p=p->next;}return TRUE;
}

单项链表的尾插法

1、新建一个新的结点

2、将为指针的next指向新的结点地址

3、将尾指针指向新的结点

在写尾插法之前先要获取链表的尾指针地址

1、在链表创建完成后遍历一边链表，以获取其尾指针地址

2、在创建链表的同时，确定尾指针地址

显然，第二种方法比第一种简单，所以我们直接修改之前的头插法函数

//单项链表的头插法
/** @brief 头插法插入一个结点* @param head 需要插入链表的头指针* @param tail 尾结点指针地址* @param data 需要插入的数据* return 成功返回TRUE,失败返回FALSE* */
int Head_Insert(LinkList head,LNode **tail,ElemType data)
{if(NULL==head)return FALSE;//创建一个新的结点pLNode *p=(LNode *)malloc(sizeof(LNode));p->data=data;P->next=NULL;//如果链表为空，那么插入的结点就是整个链表的尾结点if(NULL==head->next)*tail = p;//将新的结点p的next指向头结点的下一个结点(之前的上一个结点)（head->next）p->next=head->next;//头结点的next指向新的结点phead->next=p;return TRUE;
}

尾插法代码示例：

//单项链表的尾接法
/** @brief 头插法插入一个结点* @param head 需要插入链表的头指针* @param tail 尾结点指针的地址* @param date 需要插入的数据* return 成功返回TRUE,失败返回FALSE* */
int Tail_insert(LinkList head,LNode **tail,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}//创建一个新的结点pLNode *p=(LNode *)malloc(sizeof(LNode));p->data=data;p->next=NULL;//如果链表为空，那么插入的结点就是整个链表的尾结点if(NULL==head->next){head->next=p;}else{(*tail)->next=p;}*tail=p;return TRUE;
} 

获取链表上的指定元素

思路：

1、从链表的第一个数据开始遍历

2、将遍历到的每一个结点上的数据域与需要获取/查找的元素比较

3、如果相等则返回该结点的地址

4、如果不相等则继续往后遍历

5、如果遍历到链表末尾依然没有找到则返回NULL

//获取链表上的指定的元素
/** @brief 获取链表上的指定元素* @param head 需要查找链表的头指针* @param data 需要查找的元素* @return 成功返回结点所在的地址，失败返回NULL* */
LNode * Get_elem(LinkList head,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode *t;t=head->next;while(t!=NULL){if(t->data==data)return t;t=t->next;}return NULL;
}

获取链表上指定位置上的元素

思路：

1、从链表的第一个数据结点开始遍历

2、每遍历一个结点遍历次数都加一，同时判断是否遍历到了链表的末尾

3、如果遍历到了链表的末尾返回NULL

4、遍历到了指定位置返回结点指针

//获取链表指定位置的元素
/** @brief 获取指定位置的元素* @param head 需要遍历的链表的头指针* @param* @return 成功返回结点所在的地址，失败返回NULL* */
LNode *Get_elem_BY_Index(LinkList head,unsigned int index)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}//使用一个临时指针指向链表的第一个数据结点LNode *t=head->next;int i=1;//判断是否遍历到了链表的末尾或者遍历到了指定位置while(i<=index && t!=NULL){i++;t=t->next;}return t;
}

删除链表上指定位置的元素

思路：

1、使用临时指针t从链表的第一个数据结点开始遍历

2、使用临时指针遍历p保存遍历到的结点的前驱结点

3、每遍历一个结点遍历次数+1，指针p与随之往后移动，同时判断是否遍历到链表的末尾

4、如果遍历到链表的末尾则返回FALSE

5、如果遍历到的位置恰好是最后一个结点（尾结点），则将尾指针指向该结点的前一个结点

6、如果遍历到的结点是中间结点，则将前驱结点指向遍历到的结点的下一个结点

/** @brief 删除指定位置的结点* @param head 需要删除的链表的头指针* @param tail 需要删除的链表的尾指针地址* @param index 需要删除的元素的位置* @return 成功返回ＴＲＵＥ,失败返回FALSE* */
int Delete_By_index(LinkList head,LNode **tail,uint index)
{if(NULL==head)//如果是空指针{printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode *t=head->next;LNode *p=head;int i=1;while(inext;p=p->next;}if(t==NULL){printf("【%s %d】 can not delete\n ",__FUNCTION__,__LINE__ );return FALSE;}//如果刚好遍历到了最后一个结点if(t->next==NULL){*tail=p;(*tail)->next=NULL;free(t);return TRUE;}//如果是中间结点p->next=t->next;free(t);return TRUE;
}

删除链表上指定元素所在的结点

思路：

1、使用临时指针t从链表的第一个数据结点开始遍历，一直遍历到链表的末尾

2、使用临时指针p保存遍历到的结点的前驱结点（换句话说就是保存前一个结点）

3、将遍历到的每一个结点上的数据域与需要删除的元素作比较

4、如果遍历到的结点是尾结点，将尾指针tail指向所需要删除的结点的前驱结点p,为指针p->next=NULL,释放当前结点free(t),返回TRUE

5、如果遍历到的结点是中间结点，前驱结点指向当前结点的下一个结点p->next=t->next,释放当前结点free（t）,临时指针t指向下一个结点继续开始往后遍历

/** @brief 删除链表上指定元素所在的结点* @param head 需要删除的链表的头指针* @param tail 需要删除的链表的尾指针地址* @param index 需要删除的元素的位置* @return 成功返回ＴＲＵＥ,失败返回FALSE* */
int Delete_By_elem_Value(LinkList head,LNode **tail,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode * t=head->next;LNode * p=head;while (t!=NULL){//如果遍历到了需要删除的结点if(t->data==data){//如果当前结点是尾结点if(t->next==NULL){*tail=p;(*tail)->next=NULL;free(t);return TRUE;}p->next=t->next;free(t);t=p->next;}else{t=t->next;p=p->next;}}return TRUE;
}

在链表指定位置前插入一个结点

思路：

1、使用一个临时指针t从链表的第一个数据结点开始遍历。

2、使用临时指针p保存遍历到的结点的前驱结点

3、每遍历一个结点遍历次数就加1，指针p与之往后移动，同是否遍历到了链表的末尾

4、如果遍历到了链表的末尾则返回FALSE

5、如果遍历到了指定位置，创建一个新的结点n.

6、将前驱结点p指向新的结点n,p->next=n,将新的结点指向遍历到的结点，n->next=t,

7、返回TRUE

//在链表指定位置/指定位置前插入一个结点
/** @brief 在链表指定位置前插入一个结点* @param head 需要插入的链表的头指针* @param index 需要插入的元素位置* @param data 需要插入的元素的值* @return 成功返回ＴＲＵＥ,失败返回FALSE* */
int Insert_By_index(LNode *head,uint index,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode *t=head->next;LNode *p=head;int i=1;while(inext;p=p->next;}//如果将整个链表都遍历完了，则说明需要插入的位置不在链表上，（超出了链表的长度）if(NULL==t){printf("[%s %d] index:%d out of range ...",__FUNCTION__ ,__LINE__,index);return FALSE;}//创建一个新的结点nLNode * n;n=(LNode *)malloc(sizeof(LNode));n->next=NULL;n->data=data;//如果是中间结点将前驱结点p指向新点n,p->next=n,将新的结点指向遍历到的结点，n->next = tp->next=n;n->next=t;return TRUE;
}

插入一个元素使得整个链表依然保持为升序

思路：

找到一个比需要插入的元素大的结点，在这个结点的前面插入新的结点

1、使用临时指针p保存遍历到的节点的前驱结点

2、使用临时指针t从链表的第一个数据开始遍历

3、每遍历一一个结点遍历的次数都加1，指针p随之往后移动，同时判断遍历到的结点是否比插入的元素大

4、如果比插入的元素小则继续往后遍历，

5、如果比插入的元素大，则创建一个新的结点n

6、判断该结点是否为尾结点，

7、如果不是前驱结点将前驱结点p指向新的结点n,p->next=n,将新的结点指向遍历到的结点，n->next=t

8、如果将整个链表遍历完毕依然没有找到比需要插入的元素大的结点 则说明该结点将会是整个链表上的最大结点，应插入到链表的末尾。

//插入一个元素使得整个链表依然保持为升序（原列表为升序序列）
/** @brief 插入一个结点使原链表依然保持原有的升序排列* @param head 头指针* @param tail 指向尾指针的地址* @param data 结点的数据域* return 返回FALSE或者TRUE* */
int ascending_insert(LNode * head,LNode **tail,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}//创建一个新的结点nLNode *n;n=(LNode *)malloc(sizeof(LNode));n->data=data;n->next=NULL;LNode *t=head->next;LNode *p=head;while(t!=NULL){if(t->data<=data){t=t->next;p=p->next;continue;}//前驱结点p指向新的结点n,p->next=n,将新的结点指向遍历到的结点，n->next=t;p->next=n;n->next=t;break;}//如果将整个链表遍历完毕依然没有找到需要插入的元素的结点，则说明该新结点是整个链表上最大的结点，应该插入到链表的结尾p->next=n;*tail=n;//尾指针指向尾结点return TRUE;}

销毁链表

思想：

1、使用临时指针t从链表的第一个数据开始遍历，直到遍历到链表的末尾

2、每遍历到一个结点首先将头结点的next赋值尾当前结点的下一个结点head->next=t->next,然后临时指针t指向下一个结点t=head->next

3、如果整个链表遍历完毕则删除结点

//销毁链表
/** @brief* @param* @return* */
int List_destroy(LNode *head)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode *t=head->next;while(t==NULL){head->next=t->next;free(t);t=head->next;}//把头结点也释放掉free(head);return TRUE;
}

总的代码：

#include 
#include #define FALSE 0
#define TRUE 1
typedef unsigned int uint;
/** 单项链表的结点* */
typedef int ElemType ;
typedef struct LNode{ElemType data;//数据域struct LNode *next;//指针域，指向当前结点的直接后继} LNode,*LinkList;//LinkList 的类型为LNode*/** @brief:单项链表的初始化* @return 返回头结点的地址* */
LinkList List_Init()
{LNode *t;t=(LNode *)malloc(sizeof(LNode));//创建一个头节点t->next=NULL;LinkList head;//定义一个头指针head = t;//头指针指向头节点return head;
}//单项链表的头插法
/** @brief 头插法插入一个结点* @param 需要插入链表的头指针* @param 需要插入的数据* return 成功返回TRUE,失败返回FALSE* */
int Head_Insert(LinkList head,ElemType data)
{if(NULL==head)return FALSE;//创建一个新的结点pLNode *p=(LNode *)malloc(sizeof(LNode));p->data=data;//将新的结点p的next指向头结点的下一个结点(之前的上一个结点)（head->next）p->next=head->next;//头结点的next指向新的结点phead->next=p;return TRUE;
}
//(修改Head_Insert函数)//获取尾指针
/** @brief 头插法插入一个结点* @param head 需要插入链表的头指针* @param tail 尾结点指针的地址* @param date 需要插入的数据* return 成功返回TRUE,失败返回FALSE* */
int Change_Head_Insert(LinkList head,LNode **tail,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}//创建一个新的结点pLNode *p=(LNode *)malloc(sizeof(LNode));p->data=data;p->next=NULL;//如果链表为空，那么插入的结点就是整个链表的尾结点if(NULL==head->next)*tail=p;//将新的结点p的next指向头结点的下一个结点（head->next）p->next=head->next;//头结点的next指向新的结点phead->next=p;return TRUE;
}
//单项链表的尾接法
/** @brief 头插法插入一个结点* @param head 需要插入链表的头指针* @param tail 尾结点指针的地址* @param date 需要插入的数据* return 成功返回TRUE,失败返回FALSE* */
int Tail_insert(LinkList head,LNode **tail,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}//创建一个新的结点pLNode *p=(LNode *)malloc(sizeof(LNode));p->data=data;p->next=NULL;//如果链表为空，那么插入的结点就是整个链表的尾结点if(NULL==head->next){head->next=p;}else{(*tail)->next=p;}*tail=p;return TRUE;
}//单项链表的打印
/** @brief 输出链表中的所有结点* @param head 链表的头指针* @return 成功返回TRUE ，失败返回FALSE* */
int Print_List(LinkList head)
{if(NULL==head)return FALSE;//使用一个临时指针对链表进行遍历LNode *p=head->next;while(p!=NULL){printf("[%d]",p->data);p=p->next;}printf("\n");return TRUE;
}//获取链表上的指定的元素
/** @brief 获取链表上的指定元素* @param head 需要查找链表的头指针* @param data 需要查找的元素* @return 成功返回结点所在的地址，失败返回NULL* */
LNode * Get_elem(LinkList head,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode *t;t=head->next;while(t!=NULL){if(t->data==data)return t;t=t->next;}return NULL;
}//获取链表指定位置的元素
/** @brief 获取指定位置的元素* @param head 需要遍历的链表的头指针* @param* @return 成功返回结点所在的地址，失败返回NULL* */
LNode *Get_elem_BY_Index(LinkList head,unsigned int index)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}//使用一个临时指针指向链表的第一个数据结点LNode *t=head->next;int i=1;//判断是否遍历到了链表的末尾或者遍历到了指定位置while(i<=index && t!=NULL){i++;t=t->next;}return t;
}/** @brief 删除链表上指定位置的元素* @param head 需要删除的链表的头指针* @param tail 需要删除的链表的尾指针地址* @param index 需要删除的元素的位置* @return 成功返回ＴＲＵＥ,失败返回FALSE* */
int Delete_By_index(LinkList head,LNode **tail,uint index)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode *t=head->next;LNode *p=head;int i=1;while(inext;p=p->next;}if(t==NULL){printf("【%s %d】 can not delete\n ",__FUNCTION__,__LINE__ );return FALSE;}//如果刚好遍历到了最后一个结点if(t->next==NULL){*tail=p;(*tail)->next=NULL;free(t);return TRUE;}//如果是中间结点p->next=t->next;free(t);return TRUE;
}/** @brief 删除链表上指定元素所在的结点* @param head 需要删除的链表的头指针* @param tail 需要删除的链表的尾指针地址* @param index 需要删除的元素的位置* @return 成功返回ＴＲＵＥ,失败返回FALSE* */
int Delete_By_elem_Value(LinkList head,LNode **tail,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode * t=head->next;LNode * p=head;while (t!=NULL){//如果遍历到了需要删除的结点if(t->data==data){//如果当前结点是尾结点if(t->next==NULL){*tail=p;(*tail)->next=NULL;free(t);return TRUE;}p->next=t->next;free(t);t=p->next;}else{t=t->next;p=p->next;}}return TRUE;
}//在链表指定位置/指定位置前插入一个结点
/** @brief 在链表指定位置前插入一个结点* @param head 需要插入的链表的头指针* @param index 需要插入的元素位置* @param data 需要插入的元素的值* @return 成功返回ＴＲＵＥ,失败返回FALSE* */
int Insert_By_index(LNode *head,uint index,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode *t=head->next;LNode *p=head;int i=1;while(inext;p=p->next;}//如果将整个链表都遍历完了，则说明需要插入的位置不在链表上，（超出了链表的长度）if(NULL==t){printf("[%s %d] index:%d out of range ...",__FUNCTION__ ,__LINE__,index);return FALSE;}//创建一个新的结点nLNode * n;n=(LNode *)malloc(sizeof(LNode));n->next=NULL;n->data=data;//如果是中间结点将前驱结点p指向新点n,p->next=n,将新的结点指向遍历到的结点，n->next = tp->next=n;n->next=t;return TRUE;
}//插入一个元素使得整个链表依然保持为升序（原列表为升序序列）
/** @brief 插入一个结点使原链表依然保持原有的升序排列* @param head 头指针* @param tail 指向尾指针的地址* @param data 结点的数据域* return 返回FALSE或者TRUE* */
int ascending_insert(LNode * head,LNode **tail,ElemType data)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}//创建一个新的结点nLNode *n;n=(LNode *)malloc(sizeof(LNode));n->data=data;n->next=NULL;LNode *t=head->next;LNode *p=head;while(t!=NULL){if(t->data<=data){t=t->next;p=p->next;continue;}//前驱结点p指向新的结点n,p->next=n,将新的结点指向遍历到的结点，n->next=t;p->next=n;n->next=t;break;}//如果将整个链表遍历完毕依然没有找到需要插入的元素的结点，则说明该新结点是整个链表上最大的结点，应该插入到链表的结尾p->next=n;*tail=n;//尾指针指向尾结点return TRUE;}//销毁链表
/** @brief* @param* @return* */
int List_destroy(LNode *head)
{if(NULL==head){printf("【%s %d】 head pointer is NULL\n ",__FUNCTION__,__LINE__ );return FALSE;}LNode *t=head->next;while(t==NULL){head->next=t->next;free(t);t=head->next;}//把头结点也释放掉free(head);return TRUE;
}int main() {printf("Hello, World!\n");//创建一个链表 、 初始化一个链表LNode *T=List_Init();//定义一个指针,指向链表的最后一个结点（尾结点）LNode * tail=NULL;//定义一个指针接受获取的值LNode *find;int i=0;for(i=0;i<10;i++){
//        Change_Head_Insert(T,&tail,100+i);//头插法Tail_insert(T,&tail,100+i);//尾插法}Print_List(T);printf("tail:%d\n",tail->data);//获取链表上的指定元素find=Get_elem(T,103);if(find!=NULL){printf("this data:%d\n",find->data);} elseprintf("NO this data\n");//获取链表上指定位置的元素find=Get_elem_BY_Index(T,3);if(find!=NULL){printf("this location:%d\n",find->data);} elseprintf("NO this location\n");//删除链表上指定位置的元素Delete_By_index(T,&tail,3);printf("chance data:");Print_List(T);//删除链表上指定元素所在的结点Delete_By_elem_Value(T,&tail,100);printf("chance elem:");Print_List(T);//在链表指定位置插入一个结点Insert_By_index(T,1,1);printf("insert index 1 data 1 :");Print_List(T);//插入一个元素使得整个链表依然保持升序ascending_insert(T,&tail,102);printf("插入后的链表：");Print_List(T);//销毁链表List_destroy(T);printf("销毁后的链表：");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！