精华内容
下载资源
问答
  • 双向链表

    万次阅读 2019-12-08 21:39:42
    双向链表 1.创建一个双向链表的结构体,里面有两个指针,可以指向前后两个相邻的节点 /*! *\brief 双向链表节点结构体 */ typedef struct list_node { struct list_node* next; struct list_node* previous; }...

    双向链表

    在这里插入图片描述

    1.创建一个双向链表的结构体,里面有两个指针,可以指向前后两个相邻的节点

    /*!
     *\brief    双向链表节点结构体
     */
    typedef struct list_node
    {
    	struct list_node* next;         
    	struct list_node* previous;
    }list_item_t;
    

    2.双向链表初始化

    /*!
     * \brief    双向链表初始化
     *
     * \param    链表头节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_init(list_item_t* list_head)
    {
    	list_head->next      = list_head;
    	list_head->previous  = list_head;
    }
    

    3.双向链表插入一个节点

    /*!
     * \brief    双向链表在一个节点后面插入一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_insert_after(list_item_t* l, list_item_t* n)
    {
    	l->next->previous = n;
    	n->next = l->next;
    
    	l->next = n;
    	n->previous = l;
    }
    
    
    
    
    /*!
     * \brief    双向链表在一个节点前面插入一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_insert_before(list_item_t* l, list_item_t* n)
    {
    	l->previous->next = n;
    	n->previous = l->previous;
    
    	l->previous = n;
    	n->next = l;
    }
    

    4.删除一个节点

    /*!
     * \brief    双向链表删除一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_remove(list_item_t* l)
    {
    	l->previous->next = l->next;
    	l->next->previous = l->previous;
    
    	l->next = l->previous = l;
    }
    

    5.其他函数

    
    /*!
     * \brief    检查双向链表是否为空
     *
     * \param    链表节点
     *
     * \return   1:空   0:非空
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    uint8_t list_isempty(list_item_t* l)
    {
    	return (uint8_t)(l->next ==  l);
    }
    
    /*!
     * \brief    获取双向链表长度
     *
     * \param    链表节点
     *
     * \return   长度
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    uint32_t list_getlen(list_item_t* l)
    {
    	uint32_t len = 0;
    	const list_item_t* p = l;
    
    	while (p->next != l)
    	{
    		p = p->next;
    		len++;
    	}
    	return len;
    }
    

    双向链表的使用

    双向链表的函数不多,其他应用都是在上面的几个函数的基础上增加的。
    常用的用法有两种,第一种就是改变双向链表结构体,里面增加数据等其他的功能,然后在此基础上操作

    /*!
     *\brief    双向链表节点结构体
     */
    typedef struct list_node
    {
    	struct list_node* next;         
    	struct list_node* previous;
    	uint32_t data;
    }list_item_t;
    

    另一种是直接用上面的双链表函数,重新根据需要构造新的数据结构,比如构造一个学生数据结构体,将双链表当作一个钩子。

    typedef struct student
    {
    	list_item_t  list;
    	uint32_t     grade;
    	char name[20];
    	float score;
    }student_t;
    

    但是这样的话,可以通过学生结构体中的list变量,链接到上下两个学生结构体的list成员,但是我们需要操作的是学生变量,因此我们需要根据结构体的list成员地址,求出学生结构体的地址(这个是linux/rtt系统中常用的操作)。

    /**
     * 根据list的地址 获取结构体的基地址
     */
    #define rt_container_of(ptr, type, member) \
        ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
    

    创建100个学生数据结构

    uint8_t grade_init(student_t* head, uint32_t num)
    {
    	student_t* pstudent;
    
    	list_init(&head->list); //初始化头节点
    	head->score = (float)num;
    	head->grade = 0;
    	memset(head->name, 0, offsetof(student_t, score) - offsetof(student_t, name));
    
    	while (num--)
    	{
    		pstudent = (student_t*)malloc(sizeof(student_t));
    		
    		if (pstudent == NULL)
    		{
    			return 1; //分配内存失败
    		}
    		list_insert_after(&head->list, &pstudent->list);
    		pstudent->score = 0;
    		pstudent->grade = 0;
    		memset(pstudent->name, 0, offsetof(student_t, score) - offsetof(student_t, name));
    		
    	}
    	return 0;
    }
    
    int main(void)
    {
    	printf("hello world!\n");
    
    	student_t * student_head = (student_t *)malloc(sizeof(student_t));
    
    	uint8_t err = grade_init(student_head, 100);
    	if (err != 0)
    	{
    		printf("初始化失败\n");
    	}
    	
        /*  通过钩子链表访问上下节点 */
    	student_t * student_head3 = rt_container_of(student_head->list.next->next->next, student_t, list);
    
    	student_head3->score = 18.756;
    /* vs 使用strcpy 需要屏蔽警告 */
    #pragma warning(disable : 4996)
    	strcpy(student_head3->name, "张三");
    
    
    	while (1)
    	{
    
    	}
    	return 0;
    }
    
    展开全文
  • 双链表

    2021-03-02 16:54:50
    双链表1.1双链表的初始化(带头结点)1.2双链表的插入1.3双链表的删除1.4双链表的遍历 1.双链表 1.1双链表的初始化(带头结点) 单链表:无法逆向检索,有时候不太方便 双链表:可进可退,存储密度更低一丢丢 typedef ...

    1.双链表

    1.1双链表的初始化(带头结点)

    单链表:无法逆向检索,有时候不太方便
    双链表:可进可退,存储密度更低一丢丢

    typedef struct DNode{
    	ElemType data;
    	struct DNode *prior,*next;
    }DNode,*DLinklist;
    //DLinkList:强调链表;DNode*:强调结点
    //初始化双链表
    bool InitDLinkList(DLinklist &L){
    	L=new DNode[sizeof(DNode)];//分配一个头结点
    	if(L==NULL)//内存不足,分配失败
    		return false;
    	L->prior=NULL;//头结点的prior永远指向NULL
    	L->next=NULL;//头结点之后暂时还没有结点
    	return true;
    }
    void testDLinkList(){
    	//初始化双链表
    	DLinklist L;
    	InitDLinkList(L);
    }
    

    判空

    // 双链表是否为空
    bool Empty(DLinklist L){
    	if(L->next==NULL)
    		return true;
    	else
    		return false;
    }
    

    1.2双链表的插入

    在这里插入图片描述

    //在p结点之后插入s结点
    bool InsertNextDNode(DNode *p,DNode *s){
    	if(p==NULL||s==NULL)//非法参数
    		return false;
    	s->next=p->next;
    	if(p->next!=NULL)//如果p结点有后继结点
    		p->next->prior=s;
    	s->prior=p;
    	p->next=s;
    	return true;
    }
    

    前插:找到某一个位序的前驱结点,再对前驱结点进行后插

    1.3双链表的删除

    在这里插入图片描述

    //销毁列表
    void DestroyList(DLinklist &L){
    	//循环释放各个数据结点
    	while(L->next!=NULL)
    		DeleteNextDNode(L);
    	delete L;//释放头结点
    	L=NULL;//头指针指向NULL
    }
    

    1.4双链表的遍历

    //后向遍历
    while(p!=NULL){
    	//对结点p做相应处理,如打印
    	p=p->next;
    }
    //前向遍历
    while(p!=NULL){
    	//对结点p做相应处理
    	p=p->prior;
    }
    //前向遍历(跳过头结点)
    while(p->prior!=NULL){
    ......
    }
    

    双链表同样不可随机存取
    按位查找:while加上一个计数器,i++;用于记录此时指向哪个元素
    按值查找:while加上一个值的对比
    时间复杂度O(n)

    展开全文
  • 单向链表和双向链表分析与操作

    万次阅读 2021-03-15 16:03:40
    单链表和双链表 链表结构: 优点: 1、在程序中使用数组之前,必须事先知道数组的大小,增加数组的大小是一个耗时的过程,在运行时几乎不可能扩展数组的大小。而链表不需要提前声明链表的大小,链表的大小是随着使用...

    单链表和双链表
    链表结构:

    优点:
    1、在程序中使用数组之前,必须事先知道数组的大小,增加数组的大小是一个耗时的过程,在运行时几乎不可能扩展数组的大小。而链表不需要提前声明链表的大小,链表的大小是随着使用的过程逐步增大的。
    2、在空间的利用上链表相比数组要更加灵活,不会造成内存的大量浪费。
    3、向链表中插入或从链表中删除一项的操作不需要移动很多项,只涉及常数个节点链的改变,时间复杂度为O(1)。
    缺点:
    由于在链表中,仅仅只有头节点和尾节点是可见的,因此要想查找某个节点,必须从头节点或尾节点一路找下去,时间复杂度至少为O(logn) (二分),不如数组快。

    创建一个链表

    头指针
    一头指针是指链表指向第一个结点的指针,若链表有
    头结点,则是指向头结点的指针。
    一头指针具有标识作用,所以常用头指针冠以链表的名字(指针变量的名字)。
    一无论链表是否为空,头指针均不为空。一头指针是链表的必要元素。
    头结点
    一头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据域一般无意义(但也可以用来存放链表的长度)。
    一有了头结点,对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
    单链表

    储存结构
    假设p是指向线性表第i个元素的指针,则该结点ai的数据域我们可以用p->data的值是一个数据元素,结点ai的指针域可以用p- >next来表示,p- >next的值是一个指针。
    那么p->next指向谁呢?当然指向第i+1个元素!也就是指向ai+1的指针。
    问题:
    一如果p->data = ai,那么p->next->data =?
    答案:p->next->data = ai+1。

    创建一个单链表
    1、声明一个头指针(如果有必要,可以声明一个头节点);
    2、创建多个存储数据的节点,在创建的过程中,要随时与其前驱节点建立逻辑关系;

    例如创建一个存储{1,2,3,4}且无头节点的单链表 实现增删改查

    #include <stdio.h>
    #include <stdlib.h>
    
    //1、声明结点结构
    typedef struct Link {
        int  elem;         //数据域
        struct Link* next; //指针域
    }link;
    
    
    link* initLink();
    //链表插入的函数,p是链表,elem是插入的结点的数据域,add是插入的位置
    link* insertElem(link* p, int elem, int add);
    //删除结点的函数,p代表操作链表,add代表删除节点的位置
    link* delElem(link* p, int add);
    //查找结点的函数,elem为目标结点的数据域的值
    int selectElem(link* p, int elem);
    //更新结点的函数,newElem为新的数据域的值
    link* amendElem(link* p, int add, int newElem);
    void display(link* p);
    
    int main() {
        link* p = NULL;
        int address;
        //初始化链表(1,2,3,4)
        printf("初始化链表为:\n");
        p = initLink();
        display(p);
    
        printf("在第4的位置插入元素5:\n");
        p = insertElem(p, 5, 4);
        display(p);
    
        printf("删除元素3:\n");
        p = delElem(p, 3);
        display(p);
    
        printf("查找元素2的位置为:\n");
        address = selectElem(p, 2);
        if (address == -1) {
            printf("没有该元素");
        }
        else {
            printf("元素2的位置为:%d\n", address);
        }
        printf("更改第3的位置上的数据为7:\n");
        p = amendElem(p, 3, 7);
        display(p);
    
        return 0;
    }
    
    //2、创建链表(1,2,3,4)
    link* initLink() {
        link* p = (link*)malloc(sizeof(link));//创建一个头结点
        link* temp = p;//声明一个指针指向头结点,用于遍历链表
        int i = 0;
        //生成链表
        for (i = 1; i < 5; i++) {
            link* a = (link*)malloc(sizeof(link));
            a->elem = i;
            a->next = NULL;
            temp->next = a;
            temp = temp->next;
        }
        return p;
    }
    
    //插入一个元素
    link* insertElem(link* p, int elem, int add) {
        link* temp = p;//创建临时结点temp
        link* c = NULL;
        int i = 0;
        //首先找到要插入位置的上一个结点
        for (i = 1; i < add; i++) {
            if (temp == NULL) {
                printf("插入位置无效\n");
                return p;
            }
            temp = temp->next;
        }
        //创建插入结点c
        c = (link*)malloc(sizeof(link));
        c->elem = elem;
        //向链表中插入结点
        c->next = temp->next;
        temp->next = c;
        return  p;
    }
    
    //删除一个元素
    link* delElem(link* p, int add) {
        link* temp = p;
        link* del = NULL;
        int i = 0;
        //遍历到被删除结点的上一个结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
        }
        del = temp->next;//单独设置一个指针指向被删除结点,以防丢失
        temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
        free(del);//手动释放该结点,防止内存泄漏
        return p;
    }
    
    //查找一个元素
    int selectElem(link* p, int elem) {
        link* t = p;
        int i = 1;
        while (t->next) {
            t = t->next;
            if (t->elem == elem) {
                return i;
            }
            i++;
        }
        return -1;
    }
    
    //更新元素
    link* amendElem(link* p, int add, int newElem) {
        int i = 0;
        link* temp = p;
        temp = temp->next;//tamp指向首元结点
        //temp指向被删除结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
        }
        temp->elem = newElem;
        return p;
    }
    void display(link* p) {
        link* temp = p;//将temp指针重新指向头结点
        //只要temp指针指向的结点的next不是Null,就执行输出语句。
        while (temp->next) {
            temp = temp->next;
            printf("%d ", temp->elem);
        }
        printf("\n");
    }
    
    

    双链表

    指针域:用于指向当前节点的直接前驱节点;
    数据域:用于存储数据元素;
    指针域:用于指向当前节点的直接后继节点。
    双链表和单链表是差不多的,只是比单链表多操作一步

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct line {
        struct line * prior;
        int data;
        struct line * next;
    }line;
    //双链表的创建
    line* initLine(line * head);
    //双链表插入元素,add表示插入位置
    line * insertLine(line * head, int data, int add);
    //双链表删除指定元素
    line * delLine(line * head, int data);
    //双链表中查找指定元素
    int selectElem(line * head, int elem);
    //双链表中更改指定位置节点中存储的数据,add表示更改位置
    line *amendElem(line * p, int add, int newElem);
    //输出双链表的实现函数
    void display(line * head);
    int main() {
        line * head = NULL;
        //创建双链表
        printf("初始链表为:\n");
        head = initLine(head);
        display(head);
        //在表中第 3 的位置插入元素 7
        printf("在表中第 3 的位置插入新元素 7:\n");
        head = insertLine(head, 7, 3);
        display(head);
        //表中删除元素 2
        printf("删除元素 2:\n");
        head = delLine(head, 2);
        display(head);
    
        printf("元素 3 的位置是:%d\n", selectElem(head, 3));
        //表中第 3 个节点中的数据改为存储 6
        printf("将第 3 个节点存储的数据改为 6:\n");
        head = amendElem(head, 3, 6);
        display(head);
        return 0;
    }
    line* initLine(line * head) {
        int i = 0;
        line * list = NULL;
        head = (line*)malloc(sizeof(line));
        head->prior = NULL;
        head->next = NULL;
        head->data = 1;
        list = head;
        for (i = 2; i <= 3; i++) {
            line * body = (line*)malloc(sizeof(line));
            body->prior = NULL;
            body->next = NULL;
            body->data = i;
    
            list->next = body;
            body->prior = list;
            list = list->next;
        }
        return head;
    }
    line * insertLine(line * head, int data, int add) {
        //新建数据域为data的结点
        line * temp = (line*)malloc(sizeof(line));
        temp->data = data;
        temp->prior = NULL;
        temp->next = NULL;
        //插入到链表头,要特殊考虑
        if (add == 1) {
            temp->next = head;
            head->prior = temp;
            head = temp;
        }
        else {
            int i = 0;
            line * body = head;
            //找到要插入位置的前一个结点
            for (i = 1; i < add - 1; i++) {
                body = body->next;
                if (body == NULL) {
                    printf("插入位置有误\n");
                    break;
                }
            }
            if (body) {
                //判断条件为真,说明插入位置为链表尾
                if (body->next == NULL) {
                    body->next = temp;
                    temp->prior = body;
                }
                else {
                    body->next->prior = temp;
                    temp->next = body->next;
                    body->next = temp;
                    temp->prior = body;
                }
            }
        }
        return head;
    }
    line * delLine(line * head, int data) {
        line * temp = head;
        //遍历链表
        while (temp) {
            //判断当前结点中数据域和data是否相等,若相等,摘除该结点
            if (temp->data == data) {
                temp->prior->next = temp->next;
                temp->next->prior = temp->prior;
                free(temp);
                return head;
            }
            temp = temp->next;
        }
        printf("链表中无该数据元素\n");
        return head;
    }
    //head为原双链表,elem表示被查找元素
    int selectElem(line * head, int elem) {
        //新建一个指针t,初始化为头指针 head
        line * t = head;
        int i = 1;
        while (t) {
            if (t->data == elem) {
                return i;
            }
            i++;
            t = t->next;
        }
        //程序执行至此处,表示查找失败
        return -1;
    }
    //更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值
    line *amendElem(line * p, int add, int newElem) {
        int i = 0;
        line * temp = p;
        //遍历到被删除结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
            if (temp == NULL) {
                printf("更改位置有误!\n");
                break;
            }
        }
        if (temp) {
            temp->data = newElem;
        }
        return p;
    }
    //输出链表的功能函数
    void display(line * head) {
        line * temp = head;
        while (temp) {
            if (temp->next == NULL) {
                printf("%d\n", temp->data);
            }
            else {
                printf("%d->", temp->data);
            }
            temp = temp->next;
        }
    }
    
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,479
精华内容 18,591
关键字:

双链表