线性表结构的数据是依次排列(一对一)
(1)顺序结构:数组,顺序栈,顺序队列(顺序表)
(2)链式存储:链表,链式栈,链式队列(线性表)
链表是一种具体的数据结构
1、逻辑上:一对一的排列
2、存储上:非连续的
3、相关操作:查找节点,插入节点,删除节点,更新节点,新建节点,遍历,清空,判断空链表等
4、链表分类
单向链表,双向链表,单向循环链表,双向循环链表
5、链式存储特点
不需要一块连续内存
插入和删除效率极高
链式存储结构:数据元素是随机存储的,通过指针表示数据之间的逻辑关系
单向链表节点模板声明
typedef [节点数据域类型] Datatype;
//单向链表节点
struct Node
{
Datatype data; //数据域
struct Node *next; //指针域
};
经常给节点结构体和节点结构体指针取别名,方便以后的使用
//单向链表节点
typedef struct Node
{
Datatype data; //数据域
struct Node *next; //指针域
}ListNode;
单链表初始化
一般定义一个不带数据的节点(头结点),用来表示整个链表的头部
//初始化链表(新建一个不带数据的头结点) ListNode * InitNode() //不带数据的头节点 { ListNode * head=(ListNode *)malloc(sizeof(ListNode)); if(head != NULL){ head->next = NULL; }else{ return NULL; } return head; } //调用空链表初始化 ListNode *head = init(); if (head == NULL) { return -1; }
新建节点
//新建节点
ListNode * CreateNode(Datatype data)
{
ListNode * new=(ListNode *)malloc(sizeof(ListNode));
if (new!=NULL){
new->next = NULL;
}else{
return NULL;
}
new->data = data;
return new;
}
插入节点
尾插法
//插入节点,尾插法
void InsertNodeTail(ListNode *head,ListNode * new)
{
ListNode *p=head;//定义一个临时中间变量p,用来遍历链表,找到最后的节点,防止头结点地址发生改变
while(p->next != NULL)
{
//一个一个往后找
p = p->next;
}
//找到最后一个节点之后,将最后一个节点的next设置为new(新节点的地址)
p->next = new;
}
头插法
//头插法
void InsertNodeHead(ListNode *head,ListNode *new)
{
new->next = head->next;
head->next=new;
}
遍历链表
//遍历链表
void Display(ListNode *head)
{
ListNode *p=head->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
查找节点
//查找节点
ListNode *FindNode(ListNode *head,Datatype data)
{
ListNode *p=head->next;
while(p!=NULL)
{
if(p->data == data)
{
return p;
}
p=p->next;
}
return NULL;
}
删除节点
//删除节点,以数据来删除 Node_p dele_node(Node_p head, Datatype dele_data) { Node_p p = head; while(p->next != NULL) { if (p->next->data == dele_data) { Node_p dele = p->next; p->next = dele->next;//防止链表的链式关系断开 free(dele); dele = NULL; return p; } p = p->next; } return NULL; } //删除节点,以节点来删除 ListNode * DeleteNode(ListNode *head,ListNode *delNode) { ListNode *p=head; while(p->next!=NULL) { if(p->next == delNode) { ListNode *tmp = p->next; p->next = tmp->next; free(tmp); tmp=NULL; return p->next; } p=p->next; } return NULL; } //删除所有数据为dele_data的节点 ListNode *DeleteNodeByDate(ListNode *head,Datatype data) { ListNode *p=head; while(p->next!=NULL) { if(p->next->data == data) { ListNode *tmp=p->next; p->next=p->next->next;//防止链表的链式关系断开 free(tmp); tmp=NULL; continue; } p=p->next; } return NULL; }
更改节点
//更改节点
void UpdateNode(ListNode *head,DateType old_data,Datatype new_data)
{
ListNode *p = FindNode(head, old_data);
if (p != NULL)
{
p->data = new_data;
}
else
{
printf("没有找到要修改的节点\n");
}
}
判断空链表
//判断空链表
bool IsEmpty(ListNode * head)
{
return (head->next == NULL);
}
清空链表
//清空链表 void ClearLinkNode(ListNode* head) { if(head == NULL || IsEmpty(head)) { return ; } while(head->next != NULL) { ListNode* dele = head->next; head->next = dele->next; free(dele); dele->next = NULL; dele = NULL; } }
取出节点
//取出节点,节点不删除 ListNode* GetNode(ListNode* head, Datatype data) { if(head == NULL || is_empty(head)) { return NULL; } ListNode* p = head; while(p->next != NULL) { if (p->next->data == data) { ListNode* node = p->next; p->next = node->next; return node; } p = p->next; } return NULL; }
指定位置插入节点
void InsertNode_node(ListNode* node1,ListNode* node2)
{
//将node1插入到node2后面
if (node1 == NULL || node2 == NULL)
{
return;
}
//相当于头插法,node2为头结点,node1为新节点
//node1->next = node2->next;
//node2->next = node1;
InsertNodeHead(node2, node1);
}
移动节点
//移动节点 void move_node(ListNode* head, Datatype data1, Datatype data2) { //取出移动的节点data1 ListNode* node1 = GetNode(head, data1); //找到data2的节点 ListNode* node2 = FindNode(head, data2); //将data1插入到data2后面 if (node1 == NULL || node2 == NULL) { return; } node1->next = node2->next; node2->next = node1; }
#include <stdio.h> #include <stdlib.h> typedef int Datatype; typedef struct Node { Datatype data; struct Node *next; }ListNode; ListNode * InitNode() //不带数据的头节点 { ListNode * head=(ListNode *)malloc(sizeof(ListNode)); if(head != NULL){ head->next = NULL; }else{ return NULL; } return head; } //创建 ListNode * CreateNode(Datatype data) { ListNode * new=(ListNode *)malloc(sizeof(ListNode)); if (new!=NULL){ new->next = NULL; }else{ return NULL; } new->data = data; return new; } //尾插 void InsertNodeTail(ListNode *head,ListNode * new) { ListNode *p=head; while(p->next!=NULL) { p=p->next; } p->next = new; } //头插 void InsertNodeHead(ListNode *head,ListNode *new) { new->next = head->next; head->next=new; } void Display(ListNode *head) { ListNode *p=head->next; while(p!=NULL) { printf("%d ",p->data); p=p->next; } printf("\n"); } ListNode * DeleteNode(ListNode *head,ListNode *delNode) { ListNode *p=head; while(p->next!=NULL) { if(p->next == delNode) { ListNode *tmp = p->next; p->next = tmp->next; free(tmp); tmp=NULL; return p->next; } p=p->next; } return NULL; } //删除 ListNode *DeleteNodeByDate(ListNode *head,Datatype data) { ListNode *p=head; while(p->next!=NULL) { if(p->next->data == data) { ListNode *tmp=p->next; p->next=p->next->next; free(tmp); tmp=NULL; continue; } p=p->next; } return NULL; } //查找 ListNode *FindNode(ListNode *head,Datatype data) { ListNode *p=head->next; while(p!=NULL) { if(p->data == data) { return p; } p=p->next; } return NULL; } //更改数据 ListNode *UpdateNode(ListNode *head,DateType old_data,Datatype new_data) { ListNode *p=head->next; while(p!=NULL) { if(p->data == old_data) { p->data = new_data; // return p; } p=p->next; } return NULL; } //删除所有数据为data的节点 ListNode *DeleteNodeAllSame(ListNode *head,Datatype data) { ListNode *p=head; while(p->next!=NULL) { if (p->next->data == data) { ListNode *tmp=p->next; p->next=tmp->next; free(tmp); tmp=NULL; continue; } p=p->next; } return NULL; } //判断空链表 bool IsEmpty(ListNode * head) { return (head->next == NULL); } //清空链表 void ClearLinkNode(ListNode* head) { if(head == NULL || IsEmpty(head)) { return ; } while(head->next != NULL) { ListNode* dele = head->next; head->next = dele->next; free(dele); dele->next = NULL; dele = NULL; } } //取出节点 ListNode* GetNode(ListNode* head, Datatype data) { if(head == NULL || is_empty(head)) { return NULL; } ListNode* p = head; while(p->next != NULL) { if (p->next->data == data) { ListNode* node = p->next; p->next = node->next; return node; } p = p->next; } return NULL; } //移动节点 void move_node(ListNode* head, Datatype data1, Datatype data2) { //取出移动的节点data1 ListNode* node1 = GetNode(head, data1); //找到data2的节点 ListNode* node2 = FindNode(head, data2); //将data1插入到data2后面 if (node1 == NULL || node2 == NULL) { return; } node1->next = node2->next; node2->next = node1; } void InsertNode_node(ListNode* node1,ListNode* node2) { //将node1插入到node2后面 if (node1 == NULL || node2 == NULL) { return; } //相当于头插法,node2为头结点,node1为新节点 //node1->next = node2->next; //node2->next = node1; InsertNodeHead(node2, node1); } int main(int argc, char const *argv[]) { int i,n=10; ListNode * head = InitNode(); for(i=0;i<n;i++) { ListNode *new=NULL; if(i<=3||i>5) new = CreateNode(i); else new = CreateNode(4); // InsertNodeTail(head,new); //尾插 InsertNodeHead(head,new); //头插 } Display(head); int old_num,new_num,num; printf("search num :\n"); scanf("%d",&num); ListNode *tmp = FindNode(head,num); if(tmp!=NULL) { printf("找到 %d\n",tmp->data); } else { printf("未找到!\n"); } printf("delete num : "); scanf("%d",&num); if(DeleteNodeByDate(head,num)); { printf("delete successfully\n"); } DeleteNodeAllSame(head,num); Display(head); printf("update old_num : "); scanf("%d",&old_num); printf("update new_num : "); scanf("%d",&new_num); UpdateNode(head,old_num,new_num); Display(head); return 0; }
list.h
#ifndef LIST_H_ #define LIST_H_ #include <stdlib.h> #include <assert.h> //链表必须为单向链表,链表结点必须包含next指针域 /*list 为链表头指针*/ #define List_Init(list, list_node_t) { list=(list_node_t*)malloc(sizeof(list_node_t)); (list)->next=NULL; } //list 为链表头指针,tmpPtr为链表结点临时指针变量 #define List_Free(list, list_node_t) { assert(NULL!=list); list_node_t *tmpPtr; while(NULL!=(tmpPtr=(list)->next)){ (list)->next=tmpPtr->next; free(tmpPtr); } } //list 为链表头指针,tmpPtr为链表结点临时指针变量 #define List_Destroy(list, list_node_t) { assert(NULL!=list); List_Free(list, list_node_t) free(list); (list)=NULL; } //遍历链表 #define List_ForEach(list, curPos) for ( curPos = (list)->next; curPos != NULL; curPos=curPos->next ) //链表头插法,list为头指针,new为新节点 #define List_AddHead(list, newNode) { (newNode)->next=(list)->next; (list)->next=newNode; } //链表尾插法,list为头指针,curPos为循环变量 new为新节点 #define List_AddTail(list, curPos ,newNode) { for(curPos = (list); ;curPos=curPos->next){ if((curPos)->next == NULL){ (curPos)->next = (newNode); break; } } } //将新节点newNode加入到node之前 #define List_InsertBefore(node, newNode) { (newNode)->prev=(node)->prev; (node)->prev->next=newNode; (node)->prev=newNode; (newNode)->next=node; } //将新节点newNode加入到node之后 #define List_InsertAfter(node, newNode) { (newNode)->next=node->next; (node)->next=newNode; } //判断链表是否为空,list为头指针 #define List_IsEmpty(list) (((list) != NULL) //删除并释放链表结点node, #define List_FreeNode(head ,node,list_node_t) { assert(NULL!=node); if(node -> next != NULL){ list_node_t *temp = node->next; memcpy(node,temp,sizeof(list_node_t)); free(temp); }else{ list_node_t *temp = head; while(temp -> next != node) temp = temp -> next; temp -> next = NULL; free(node); node = NULL; } } #endif
单向循环链表:
单向循环链表和普通的单向链表的操作逻辑几乎一样,唯一就是初始化和结尾判断有区别。
单向链表里面每一个节点的next都要有一个指向,单向循环,最后一个节点的next指向head节点
(1)初始化
//初始化链表(新建一个不带数据的头结点)
ListNode *init(void)
{
ListNode *head = malloc(sizeof(ListNode));
if (head != NULL)
{
head->next = head;
}
else
{
return NULL;
}
return head;
}
( 2 )、尾插法
//插入节点,尾插法 void insert_tail(ListNode *head, ListNode *new) { if (head == NULL || new == NULL) { return ; } ListNode *p = head;//定义一个临时中间变量p,用来遍历链表,找到最后的节点,防止头结点地址发生改变 while(p->next != head) { //一个一个往后找 p = p->next; } //找到最后一个节点之后,将最后一个节点的next设置为new(新节点的地址) p->next = new; //将新的尾部节点 new的next指向 头结点 new->next = head; }
N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。
#include <stdio.h> #include <stdlib.h> typedef int Datatype; typedef struct Node { Datatype data; struct Node *next; }ListNode; ListNode * InitNode(Datatype data) //带数据的头节点 { ListNode * head=(ListNode *)malloc(sizeof(ListNode)); if(head != NULL){ head->data = data; head->next = head; }else{ return NULL; } return head; } //创建 ListNode * CreateNode(Datatype data) { ListNode * new=(ListNode *)malloc(sizeof(ListNode)); if (new!=NULL){ new->next = NULL; }else{ return NULL; } new->data = data; return new; } //尾插 void InsertNodeTail(ListNode *head,ListNode * new) { ListNode *p=head; while(p->next!=head) { p=p->next; } p->next = new; new->next=head; } //头插 void InsertNodeHead(ListNode *head,ListNode *new) { new->next = head->next; head->next=new; } void Display(ListNode *head) { ListNode *p=head; printf("%d ",head->data); while(p->next!=head) { printf("%d ",p->next->data); p=p->next; } printf("\n"); } ListNode * DeleteNode(ListNode *head,ListNode *delNode) { ListNode *p=head; while(p->next!=head) { if(p->next == delNode) { ListNode *tmp = p->next; p->next = tmp->next; free(tmp); tmp=NULL; return p->next; } p=p->next; } return NULL; } void ClearNode(ListNode *head) //清空全部节点 { ListNode *p=head; if(head == NULL ||head->next ==NULL) return; while(p->next!=head) { ListNode *tmp = p->next; p->next = tmp->next; free(tmp); tmp->next=NULL; tmp=NULL; } free(head); head->next=NULL; head=NULL; } void GetSurvival(ListNode *head,int num,int pos) { if(num == 0) return; if(num<pos) { Display(head); ClearNode(head); //清空全部节点 return; } ListNode *p=head; int flag=1; while(1) { ListNode *tmp=p; for(int i=1;i<pos-1;i++) //移动节点 { tmp=tmp->next; } //删除节点 ListNode *delnode = tmp->next; printf("kill %d\n",delnode->data); tmp->next = delnode->next; free(delnode); delnode=NULL; // DeleteNode(p,tmp); p=tmp->next; --num; if(num == pos) { for(int i=1;i<pos;i++) { if (flag) { printf("存活的人为:"); flag=0; } printf("%d ",p->data); p=p->next; } printf("\n"); ClearNode(p); //清空全部节点 return; } } } int main(int argc, char const *argv[]) { int num=11,pos; ListNode *head=NULL; while(1) { head = InitNode(1); printf("输入总人数:"); scanf("%d",&num); printf("输入杀死第几个人:"); scanf("%d",&pos); for(int i=2;i<=num;i++) { InsertNodeTail(head,CreateNode(i)); } Display(head); GetSurvival(head,num,pos); if(num ==0) break; head=NULL; } return 0; }
双向循环链表节点
节点结构体声明
typedef int Datatype;
//双向循环链表节点
typedef struct Node
{
Datatype data;//数据域
struct Node *prev;//前驱指针 //指针域
struct Node *next;//后继指针
}LinkNode;
初始化
//初始化空链表
LinkNode * Init()
{
LinkNode * head = (LinkNode *)malloc(sizeof(LinkNode));
if(head!=NULL)
{
head->prev=head;
head->next=head;
}
return head;
}
新建节点
//新建节点
LinkNode * CreateNode(Datatype data)
{
LinkNode * tmp = (LinkNode *)malloc(sizeof(LinkNode));
if(tmp == NULL)
return NULL;
tmp->data = data;
tmp->prev=NULL;
tmp->next=NULL;
return tmp;
}
插入节点
尾插法
插入是放在尾部节点的后面,那么就相当于等于插入到头结点的前面
//插入节点,尾插法
void InsertNodeTail(LinkNode *head,LinkNode *newNode)
{
LinkNode *tail = head->prev;
newNode->prev = tail;
newNode->next=head;
head->prev=newNode;
tail->next=newNode;
return head;
}
头插法
//头插法
void InsertNodeHead(LinkNode *head,LinkNode *newNode)
{
LinkNode *first = head->next;
newNode->prev=head; //防止链表的链式关系断开
newNode->next=first;
first->prev=newNode;
head->next=newNode;
return head;
}
遍历链表
//遍历从前往后 void DisplayNegative(LinkNode *head) { LinkNode *p=head; while(p->prev!=head) { p=p->prev; printf("%d ",p->data); } printf("\n"); } //遍历从后往前 void DisplayPositive(LinkNode *head) { LinkNode *p=head; while(p->next!=head) { p=p->next; printf("%d ",p->data); } printf("\n"); }
查找节点
LinkNode *FindNode(LinkNode *head,Datatype data)
{
LinkNode *p=head;
while(p->next!=head)
{
p=p->next;
if(p->next==data)
{
return p;
}
}
return NULL;
}
更新节点
//更新节点
void UpdateNode(LinkNode *head,Datatype old_data,Datatype new_data)
{
LinkNode *p=FindNode(head,old_data);
if(p!=NULL)
{
p->data=new_data;
printf("修改成功\n");
}
else
{
printf("没有这个节点");
}
}
删除节点
//删除节点 int DeleteNode(LinkNode *head,Datatype data) { LinkNode *p=head; while(p->next!=head) { if(p->next->data==data) { LinkNode *tmp=p->next; p->next=tmp->next; tmp->next->prev=p; free(tmp); tmp->next=NULL; tmp->prev=NULL; tmp=NULL; return 1; } p=p->next; } return 0; }
//判断空链表
//判断空链表
bool IsEmpty(LinkNode* head)
{
return (head->next == head && head->prev == head);
}
//清空链表
//清空链表 void ClearLinkNode(LinkNode* head) { if(head == NULL || IsEmpty(head)) { return ; } while(head->next != head) { LinkNode tmp = head->next; head->next = tmp->next; tmp->next->prev = head; free(tmp); tmp->next = tmp->prev = NULL; tmp = NULL; } }
#include <stdio.h> #include <stdlib.h> typedef int Datatype; typedef struct Node { Datatype data; struct Node *prev; struct Node *next; }LinkNode; //初始化 LinkNode * Init() { LinkNode * head = (LinkNode *)malloc(sizeof(LinkNode)); if(head!=NULL) { head->prev=head; head->next=head; } return head; } //创建节点 LinkNode * CreateNode(Datatype data) { LinkNode * tmp = (LinkNode *)malloc(sizeof(LinkNode)); tmp->data = data; tmp->prev=NULL; tmp->next=NULL; return tmp; } //尾插法 LinkNode * InsertNodeTail(LinkNode *head,LinkNode *newNode) { LinkNode *tail = head->prev; newNode->prev = tail; newNode->next=head; head->prev=newNode; tail->next=newNode; return head; } //头插法 LinkNode *InsertNodeHead(LinkNode *head,LinkNode *newNode) { LinkNode *first = head->next; newNode->prev=head; //防止链表的链式关系断开 newNode->next=first; first->prev=newNode; head->next=newNode; return head; } //逆序遍历 void DisplayNegative(LinkNode *head) { LinkNode *p=head; while(p->prev!=head) { p=p->prev; printf("%d ",p->data); } printf("\n"); } //正序遍历 void DisplayPositive(LinkNode *head) { LinkNode *p=head; while(p->next!=head) { p=p->next; printf("%d ",p->data); } printf("\n"); } //查找节点 LinkNode *FindNode(LinkNode *head,Datatype data) { LinkNode *p=head; while(p->next!=head) { p=p->next; if(p->next==data) { return p; } } return NULL; } //更新节点 void UpdateNode(LinkNode *head,Datatype old_data,Datatype new_data) { LinkNode *p=FindNode(head,old_data); if(p!=NULL) { p->data=new_data; printf("修改成功\n"); } else { printf("没有这个节点"); } } //删除节点 int DeleteNode(LinkNode *head,Datatype data) { LinkNode *p=head; while(p->next!=head) { if(p->next->data==data) { LinkNode *tmp=p->next; p->next=tmp->next; tmp->next->prev=p; free(tmp); tmp->next=NULL; tmp->prev=NULL; tmp=NULL; return 1; } p=p->next; } return 0; } //判断空链表 bool IsEmpty(LinkNode* head) { return (head->next == head && head->prev == head); } //清空链表 void ClearLinkNode(LinkNode* head) { if(head == NULL || IsEmpty(head)) { return ; } while(head->next != head) { LinkNode tmp = head->next; head->next = tmp->next; tmp->next->prev = head; free(tmp); tmp->next = tmp->prev = NULL; tmp = NULL; } } //从小到大插入 int InsertNodeOrder(LinkNode *head,LinkNode *newNode) { LinkNode *p=head; while(p->next!=head) { if(p->next->data.price > newNode->data.price) { //头插 InsertNodeHead(p,newNode); return 1; } p=p->next; } //尾插入 return (InsertNodeTail(head,newNode)); } int main(int argc, char const *argv[]) { int num=10; LinkNode *head = Init(); for(int i=1;i<=num;i++) { // InsertNodeTail(head,CreateNode(i)); InsertNodeHead(head,CreateNode(i)); } DisplayNegative(head); DisplayPositive(head); return 0; }
联系客服