嵌入式開發學習———Linux環境下數據結構學習（三）

單向循環鏈表

單向循環鏈表是一種特殊的單向鏈表，尾節點的指針指向頭節點，形成一個閉環。適用于需要循環訪問的場景，如輪詢調度。

結構特點：每個節點包含數據域和指向下一個節點的指針，尾節點的指針指向頭節點而非空值。
操作復雜度：
- 插入/刪除頭節點：O(1)
- 插入/刪除尾節點：O(n)（需遍歷到尾部）
代碼示例（C++）：

struct Node {int data;Node* next;Node(int val) : data(val), next(nullptr) {}
};

雙向鏈表

雙向鏈表的每個節點包含前驅和后繼指針，支持雙向遍歷，但需要更多內存存儲指針。

結構特點：節點包含前驅指針（prev）、數據域和后續指針（next）。
操作復雜度：
- 任意位置插入/刪除：O(1)（已知前驅節點時）
- 按值查找：O(n)
代碼示例（C++）：

struct DNode {int data;DNode* prev;DNode* next;DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

?
作業：

?1.雙向鏈表的部分操作

#include "linklist.h"int main(int argc, const char *argv[])
{//定義一個頭linklistptr headptr=NULL;//定義循環變量int i;//定義位置變量int seat;//頭的初始化headptr=LinklistHeadnodeApply();//定義新輸入數據datatype nwedata;//循環輸入數據for(i=0;i<5;i++){puts("請輸入一個數：");scanf(" %d",&nwedata);//調用雙向鏈表的頭插函數LinklistHeadinsert(headptr,nwedata);}//調用雙向鏈表的遍歷函數nextLinklistShownext(headptr);//調用雙向鏈表的遍歷函數frontLinklistShowfront(headptr);//循環輸入數據for(i=0;i<5;i++){puts("請輸入一個數：");scanf(" %d",&nwedata);//雙向鏈表的尾插函數LinklistTailinsert(headptr,nwedata);}//調用雙向鏈表的遍歷函數nextLinklistShownext(headptr);//調用雙向鏈表的頭刪函數LinklistHeaddelete(headptr);//調用雙向鏈表的遍歷函數nextLinklistShownext(headptr);//調用雙向鏈表的尾刪函數LinklistTaildelete(headptr);//調用雙向鏈表的遍歷函數nextLinklistShownext(headptr);//分別輸入位置和新數據puts("輸入想插入的位置：");scanf(" %d",&seat);puts("輸入想插入的數據：");scanf(" %d",&nwedata);//調用雙向鏈鏈表按位置插入函數LinklistSeatinsert(headptr,seat,nwedata);//調用雙向鏈表的遍歷函數nextLinklistShownext(headptr);//輸入位置puts("輸入想刪除的位置：");scanf(" %d",&seat);//調用雙向鏈鏈表按位置插入函數LinklistSeatdelete(headptr,seat);//調用雙向鏈表的遍歷函數nextLinklistShownext(headptr);//分別輸入位置和新數據puts("輸入想要修改的位置：");scanf(" %d",&seat);puts("輸入想改成的數據：");scanf(" %d",&nwedata);//調用雙向鏈鏈表按位置修改函數LinklistSeatalter(headptr,seat,nwedata);//調用雙向鏈表的遍歷函數nextLinklistShownext(headptr);//輸入位置puts("輸入想查找的位置：");scanf(" %d",&seat);//調用雙向鏈鏈表按位置查找函數LinklistSeatsift(headptr,seat);return 0;
}

#ifndef _LINKLIST_H__
#define _LINKLIST_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>//返回值枚舉
enum returntype
{//失敗返回FAULSE=-1,//成功返回SUCCESS
};//存儲數據類型
typedef int datatype;//雙向鏈鏈表結構體
typedef struct Node
{//數據域共用體union{//頭節點數據域int len;//普通節點數據域datatype data;};//前向指針域struct Node *front;//后向指針域struct Node *next;
}linklist,*linklistptr;//頭節點堆區申請函數
linklistptr LinklistHeadnodeApply(void);//普通節點堆區申請函數
linklistptr LinklistComnodeApply(datatype nwedata);//雙向鏈表的頭插函數
int LinklistHeadinsert(linklistptr headptr,datatype nwedata);//雙向鏈表的遍歷函數next
int LinklistShownext(linklistptr headptr);//雙向鏈表的遍歷函數front
int LinklistShowfront(linklistptr headptr);//雙向鏈表的尾插函數
int LinklistTailinsert(linklistptr headptr,datatype nwedata);//雙向鏈表的頭刪函數
int LinklistHeaddelete(linklistptr headptr);//雙向鏈表的尾刪函數
int LinklistTaildelete(linklistptr headptr);//雙向鏈鏈表按位置插入函數
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata);//雙向鏈鏈表按位置刪除函數
int LinklistSeatdelete(linklistptr headptr,int seat);//雙向鏈鏈表按位置修改函數
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata);//雙向鏈鏈表按位置查找函數
linklistptr LinklistSeatsift(linklistptr headptr,int seat);#endif

#include "linklist.h"//頭節點堆區申請函數
linklistptr LinklistHeadnodeApply(void)
{//頭節點堆區申請linklistptr headptr=(linklistptr)malloc(sizeof(linklist));//判斷申請是否成功if(headptr==NULL){return NULL;}//初始化headptr->len=0;headptr->front=NULL;headptr->next=NULL;return headptr;
}//普通點堆區申請函數
linklistptr LinklistComnodeApply(datatype nwedata)
{//普通節點堆區申請linklistptr comptr=(linklistptr)malloc(sizeof(linklist));//判斷申請是否成功if(comptr==NULL){return NULL;}//初始化comptr->data=nwedata;comptr->front=NULL;comptr->next=NULL;return comptr;
}//雙向鏈表的頭插函數
int LinklistHeadinsert(linklistptr headptr,datatype nwedata)
{//定義普通節點指針linklistptr comptr=NULL;//判斷是否為nullif(headptr==NULL){return FAULSE;}//普通節點申請comptr=LinklistComnodeApply(nwedata);//申請判斷if(comptr==NULL){return FAULSE;}//頭插comptr->next=headptr->next;comptr->front=headptr;//判斷是否為首個數據if(headptr->next){headptr->next->front=comptr;}headptr->next=comptr;//個數自增headptr->len++;return SUCCESS;
}//雙向鏈表的遍歷函數next
int LinklistShownext(linklistptr headptr)
{//定義鏈表指針linklistptr ptr=NULL;//定義循環變量int i;//判斷是否為null//判斷鏈表是否為空if(headptr==NULL||headptr->len==0){return FAULSE;}//輸出ptr=headptr->next;puts("正序鏈表現有數據：");while(ptr){printf("%d ",ptr->data);ptr=ptr->next;}putchar(10);return SUCCESS;
}//雙向鏈表的遍歷函數front
int LinklistShowfront(linklistptr headptr)
{//定義鏈表指針linklistptr ptr=NULL;//定義循環變量int i;//判斷是否為NULL//判斷鏈表是否為空if(headptr==NULL||headptr->len==0){return FAULSE;}//找尾部ptr=headptr->next;while(ptr->next){ptr=ptr->next;}//輸出puts("逆序鏈表現有數據：");while(ptr!=headptr){printf("%d ",ptr->data);ptr=ptr->front;}putchar(10);return SUCCESS;
}//雙向鏈表的尾插函數
int LinklistTailinsert(linklistptr headptr,datatype nwedata)
{//定義鏈表指針和普通節點指針linklistptr ptr=NULL,comptr=NULL;//判斷頭是否為nullif(headptr==NULL){return FAULSE;}//找尾部ptr=headptr;while(ptr->next){ptr=ptr->next;}//初始化普通節點comptr=LinklistComnodeApply(nwedata);//判斷申請是否成功if(comptr==NULL){return FAULSE;}//尾插ptr->next=comptr;comptr->front=ptr;//個數自增headptr->len++;return SUCCESS;
}
//雙向鏈表的頭刪函數
int LinklistHeaddelete(linklistptr headptr)
{//定義鏈表指針和將刪節點指針linklistptr deltr=NULL,ptr=NULL;//判斷頭是否為nullif(headptr==NULL||headptr->len==0){return FAULSE;}//找到要刪除的數據第一個節點deltr=headptr->next;//頭刪headptr->next=deltr->next;//判斷是否只有一個節點if(deltr->next){deltr->next->front=headptr;}free(deltr);deltr=NULL;//個數自減headptr->len--;return SUCCESS;
}//雙向鏈表的尾刪函數
int LinklistTaildelete(linklistptr headptr)
{//定義鏈表指針和將刪節點指針linklistptr deltr=NULL,ptr=NULL;//判斷頭是否為nullif(headptr==NULL||headptr->len==0){return FAULSE;}//找尾部ptr=headptr;while(ptr->next){ptr=ptr->next;}ptr->front->next=NULL;free(ptr);ptr=NULL;headptr->len--;return SUCCESS;
}//雙向鏈鏈表按位置插入函數
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata)
{//定義循環變量int i;//定義鏈表指針和普通節點指針linklistptr ptr=NULL,comptr=NULL;//判斷頭是否為NULL//判斷位置是否合法if(headptr==NULL||seat<=0||seat>headptr->len+1){return FAULSE;}//找到對應位置的前一個位置ptr=headptr;for(i=0;i<seat-1;i++){ptr=ptr->next;}//初始化普通節點comptr=LinklistComnodeApply(nwedata);//if(comptr==NULL){return FAULSE;}//插入comptr->next=ptr->next;comptr->front=ptr;if(ptr->next!=NULL){ptr->next->front=comptr;}ptr->next=comptr;headptr->len++;return SUCCESS;
}//雙向鏈鏈表按位置刪除函數
int LinklistSeatdelete(linklistptr headptr,int seat)
{//定義循環變量int i;//定義鏈表指針和將刪節點指針linklistptr deltr=NULL,ptr=NULL;//判斷是否為NULL//判斷鏈表是否為空//判斷位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return FAULSE;}//找到對應位置的前一個位置ptr=headptr;for(i=0;i<seat-1;i++){ptr=ptr->next;}deltr=ptr->next;ptr->next=deltr->next;if(deltr->next!=NULL){deltr->next->front=deltr->front;}free(deltr);deltr=NULL;headptr->len--;return SUCCESS;
}//雙向鏈鏈表按位置修改函數
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata)
{//定義循環變量int i;//定義鏈表指針linklistptr ptr=NULL;//判斷是否為NULL//判斷鏈表是否為空//判斷位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return FAULSE;}//找到對應位置ptr=headptr;for(i=0;i<seat;i++){ptr=ptr->next;}ptr->data=nwedata;return SUCCESS;
}//雙向鏈鏈表按位置查找函數
linklistptr LinklistSeatsift(linklistptr headptr,int seat)
{//定義循環變量int i;//定義鏈表指針linklistptr ptr=NULL;//判斷是否為NULL//判斷鏈表是否為空//判斷位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return NULL;}//找到對應位置ptr=headptr;for(i=0;i<seat;i++){ptr=ptr->next;}printf("linklist[%d]=%d\n",seat,ptr->data);return ptr;
}

運行示例：

2.牛客網刷題