-
2022-03-03 19:01:44
一:动态链表建立
C语言搭建动态链表需要两个基本语法点——指针和结构体,至于什么是链表,这里不多做赘述。
(1)首先通过结构体建立节点
typedef struct student{ int num; int age; struct student *next; }student;
(2)建立一个类型为student型返回值为结构体指针的函数用以动态构建链表,链表节点内容和节点数可以自己给定,函数的返回值为链表的头节点
student *int_line(int n){ student *head=NULL; student *p_now,*p_next; int i; for(i=0;i<n;i++){ p_next=(student *)malloc(sizeof(student)); if(p_next==NULL){ printf("第%d个节点分配失败",i+1); break; } printf("请输入第%d个学生编号",i+1); scanf("%d",&p_next -> num); printf("请输入第%d个学生年龄",i+1); scanf("%d",&p_next -> age); printf("\n"); if(i==0){ head=p_next; p_next -> next=NULL;//注:这里也要加入这段话,不然若链表只有一个节点,那么该节点.next就可能是一个未知数,存在漏洞 p_now=p_next; }else{ p_now -> next=p_next; p_now=p_next; p_next -> next=NULL;//这一步可以保证链表末尾节点指向的节点为空,因为malloc函数分配内存时并不能初始化内寸 } } return head; }
(3)增:同样建立一个student型的指针函数,用以给已经建立的链表增加指定数量和内容的节点。这里有两种方法,分别是在链尾或链头增加节点。
链尾增加节点首先需要遍历整个链表,同时需要两个student型指针变量,当链表存储量较大时效率低,而链头增加节点无需遍历,同时只需要一个student变量用于辅助,所以这里采用链头增加节点
student *add_node(student *head,int n){ student *p_new; int i; for(i=0;i<n;i++){ if(head!=NULL){ p_new=(student *)malloc(sizeof(student)); printf("请输入新增第%d个学生编号",i+1); scanf("%d",&p_new -> num); printf("请输入新增第%d个学生年龄",i+1); scanf("%d",&p_new -> age); printf("\n"); p_new -> next=head; head=p_new; } } return head; }
(4)删:删除指定编号的节点,程序如下(改程序有一个问题是节点数必须大于等于2)
student *delete_node(int num,student *head){ student *p_next,*p_last;//p_next为当前要删除的节点,p_last为要删除节点的上一个节点 p_next=p_last=head; while(p_next -> num != num && p_next != NULL){ p_last=p_next; p_next=p_next -> next; } if(p_next != NULL){ p_last -> next=p_next -> next; free(p_next); } return head; }
(5)改和查:这两个功能只需要遍历整个链表即可,简单,不做赘述
(6)最后输出头节点为head的链表
void put_link(student *head){ student *p=head; int i=0; while(p!=NULL){ printf("第%d个学生的编号为%d\n",i+1,p -> num); printf("第%d个学生的年龄为%d\n",i+1,p -> age); p=p -> next; i++; }//比起for+if的方式,直接用while代码执行效率更高,且容错率也高,并且节约资源 }
最后,有以上函数后主程序可以根据自己的需求任意调用或写个状态机进行功能循环选择调用即可,
这里给出一个测试用的完整代码
/********************************** 基于C语言的单链表自动构建以及输出,增删改查程序 **********************************/ #include <stdio.h> #include <string.h> #include <malloc.h> typedef struct student{ int num; int age; struct student *next; }student; student *int_line(int n){ student *head=NULL; student *p_now,*p_next; int i; for(i=0;i<n;i++){ p_next=(student *)malloc(sizeof(student)); if(p_next==NULL){ printf("第%d个节点分配失败",i+1); break; } printf("请输入第%d个学生编号",i+1); scanf("%d",&p_next -> num); printf("请输入第%d个学生年龄",i+1); scanf("%d",&p_next -> age); printf("\n"); if(i==0){ head=p_next; p_next -> next=NULL;//注:这里也要加入这段话,不然若链表只有一个节点,那么该节点.next就可能是一个未知数,存在漏洞 p_now=p_next; }else{ p_now -> next=p_next; p_now=p_next; p_next -> next=NULL;//这一步可以保证链表末尾节点指向的节点为空,因为malloc函数分配内存时并不能初始化内寸 } } return head; } void put_link(student *head){ student *p=head; int i=0; while(p!=NULL){ printf("第%d个学生的编号为%d\n",i+1,p -> num); printf("第%d个学生的年龄为%d\n",i+1,p -> age); p=p -> next; i++; }//比起for+if的方式,直接用while代码执行效率更高,且容错率也高,并且节约资源 } /********************************** 以下可通过程序选择增,删,改和特定编号节点数据的查询功能 ***********************************/ //增:在节点末尾或首部增加指定数量的节点,分析发现,在首部增加节点不用遍历链表,同时节约只需要一个结构体指针针就可以实现,节约了动态存储空间,所以选定在链表前增加节点。 student *add_node(student *head,int n){ student *p_new; int i; for(i=0;i<n;i++){ if(head!=NULL){ p_new=(student *)malloc(sizeof(student)); printf("请输入新增第%d个学生编号",i+1); scanf("%d",&p_new -> num); printf("请输入新增第%d个学生年龄",i+1); scanf("%d",&p_new -> age); printf("\n"); p_new -> next=head; head=p_new; } } return head; } //删除指定编号的节点(节点数必须大于等于两个) student *delete_node(int num,student *head){ student *p_next,*p_last;//p_next为当前要删除的节点,p_last为要删除节点的上一个节点 p_next=p_last=head; while(p_next -> num != num && p_next != NULL){ p_last=p_next; p_next=p_next -> next; } if(p_next != NULL){ p_last -> next=p_next -> next; free(p_next); } return head; } int main(){ int n_original; int n_newAdd; int n_delet; printf("请输入学生人数"); scanf("%d",&n_original); student *head=int_line(n_original); put_link(head); printf("\n"); //节点增加执行程序 printf("请输入新增学生人数"); scanf("%d",&n_newAdd); head=add_node(head,n_newAdd); put_link(head); //节点删除执行程序 printf("请输要删除学生的编号"); scanf("%d",&n_delet); head=delete_node(n_delet,head); put_link(head); return 0; }
更多相关内容 -
c语言创建动态链表代码
2019-10-16 14:08:11//编写一个C程序,功能是: //能接收用户从键盘输入一串正整数,然后建立动态链表; //(注:用户的输入用"-1"表示结束;) //运行示例如下: //请输入: 1 2 3 4 5 6 7 8 9 -1 //结果是: 1->2->3->4->5->6->7->8->9->NULL -
动态链表
2021-11-02 00:47:14最简单的动态链表,新手看 -
C语言静态链表和动态链表
2020-12-26 02:07:071. 静态链表 结构体中的成员可以是各种类型的指针变量,当一个结构体中有一个或多个成员的基类型是本结构体类型时,则称这种结构体为“引用自身的结构体”。如: struct link { char ch; struct link *p;... -
统计学生信息(使用动态链表完成)
2018-02-28 19:44:48统计学生信息(使用动态链表完成),c语言程序设计,适合初学者学习 -
C语言程序动态链表
2018-05-07 21:26:32C语言动态链表简单操作,创建链表,改动数据,插入删除数据。 -
动态链表详解
2021-11-12 12:52:523.动态链表 4.链表的插入和删除 5.双链表 1.链表的简介 链表是一种常见的数据结构,我们经常会使用数组来存放数据,但使用数组时,要先指定数组的大小,如果向这个数组加入过多的元素,则会超出,导致无法保存数据;...链表
目录:
1.链表的简介
2.链表的实现
3.动态链表
4.链表的插入和删除1.链表的简介
链表是一种常见的数据结构,我们经常会使用数组来存放数据,但使用数组时,要先指定数组的大小,如果向这个数组加入过多的元素,则会超出,导致无法保存数据;如果数据太小,又会非常浪费内存空间。
所以,我们希望有一种存储方式,其储存的元素个数是不受限定的,当进行添加元素时,存储的个数也会增加,这种储存方式就是链表。
在链表中,有一个头指针head变量,用这个指针变量保存第一个元素的地址,其中,这个元素包括两个部分:数据部分和指针部分。数据部分用来存放元素的数据,指针部分用来指向下一个元素。于是,头指针指向第一个元素,第一个元素中的指针又指向第二个元素,第二个元素中的指针又指向第三个元素,依次下去,到了最后一个元素的指针就指向Null,表示指向的地址为空。2.链表的实现
需要实现链表这种存储方式,必须要使用指针才能完成。结构体和指针一起实现链表功能。
我们看一下一个简单的元素结点,包含有数据部分和指针部分。struct student { char cname[20]; //学生姓名 (数据部分) int inumber; //学生学号 (数据部分) struct student *pNext; //指向下一个结点的指针 (指针部分) };
如果要向链表添加多一结点,那应该如何操作呢?我们看一个图:
当有新的结点添加到链表中时,原来最后一个结点的指针将保存新添加的结点的地址,而新的结点的指针将指向NULL(空),新的结点就变为最后一个结点。3.动态链表
建立动态链表就是指程序运行过程中,从无到有建立一个链表,即一个一个分配结点内存空间,然后输入结点中的数据,并建立结点间的相连关系。
下面我们来建立一个动态链表:
首先创建结点结构:struct student { char cname[20]; //学生姓名 (数据部分) int inumber; //学生学号 (数据部分) struct student *pNext; //指向下一个结点的指针 (指针部分) }
然后定义一个Create函数,用来创建链表,其函数返回链表头指针:
Static int icount=0; //定义一个全局变量表示链表长度,结点计数器 struct student*create() { struct student *pHead=NULL; //初始化头指针 struct student *pone,*PoneNew; //初始化两个结构体指针 *PoneNew=(struct student*) malloc(sizeof (struct student)); //申请一个新的内存空间,使PoneNew指向这个新内存。 printf("请输入姓名和名字\n"); scanf("%S",&poneNew->cname); //赋值给新元素内的成员 scanf("%S",&poneNew->inumber); //赋值给新元素内的成员 while(poneNew->inumber !=0) //当输入了新学号时 { icount++; //代表多了一个元素结点 icount加1 if(count==1) //如果该链表第一个元素结点还没有建立 { poneNew->pNext=NULL; //将新的结点的指针部分指向空 pone=poneNew; //加入新的结点 pHead=poneNew; //头指针指向新的结点 } else { poneNew->pNext=NULL; //将新的结点的指针部分指向空 pone->Next=poneNew; //将原来的结点的指针部分指向新的结点 pone=poneNew; //将新的结点地址给pone,使得下一次再增加结点前,pone为最后一个元素结点。 } } return pHead; }
以上是从无到有建立一个动态链表的过程。
4.链表的插入和删除
上面我们从0到1建立了动态链表,那如何实现插入和删除操作呢,我们接着往下看。
我们设计一个函数可以实现链表的插入:struct Node { ..... //省略数据部分 struct Node * Next; //指向下一个结点的指针 (指针部分) }: int InsertElement (struct Node *List,int I, struct Node *Node) { // List为链表第一个节点地址,I为要插入的第n个元素,如果存在,返回I,否则返回 0 struct Node *pOne=NULL; struct Node *pNewOne=NULL; int j=0; //计数器 pOne= List; //指向数组的第一个节点 While((pOne!=NULL)&&j<I-1) //顺序查找,一直到目标节点的前一节点 { pOne=pOne->Next; //到下一个节点 j++; //计数加1 } if((pOne->Next==NULL)||(j>I-1)) //第I个元素不存在 return 0: pNewOne= ( struct Node *)malloc(sizeof(struct Node)); //申请一个内存空间,并且将内存地址赋值给pNewOne {/*拷贝参数Node信息到新增加的节点pNewOne*/ pNewOne ->Next= Node ->Next; //(这里的Node是函数里传来的形参)把新的Node的指针部分指向的地址赋给pNewOne里的指针部分。 pNewOne ->Next= pOne ->Next; //将下一结点的地址赋值给插入的节点里,也就是让插入的节点指向下一节点(把新节点和后一位连起来) pOne ->Next= pNewOne; //将前一节点的指针部分指向插入的新节点的地址(把新节点和前一位节点的连起来) return j: }
下面我们再进行链表的删除操作:
struct Node { ..... //省略数据部分 struct Node * Next; //指向下一个结点的指针 (指针部分) }: int InsertElement (struct Node *List,int I) { // List为链表第一个节点地址,I为要删除的第n个元素,如果存在,返回I,否则返回 0 struct Node *pOnepre=NULL; //ponepre表示被删除节点的前一个节点 struct Node *pDeleteOne=NULL; //pDeleteOne表示要删除的节点 int j=0; //计数器 pOnepre= List; //指向数组的第一个节点 pDeleteOne=List; While((pDeleteOne!=NULL)&&j<I-1) //顺序查找,一直到要删除的目标节点 { ponepre=pDeleteOne; //保存好前一节点 pDeleteOne=pDeleteOne->Next; //到下一个节点 j++; //计数加1 } if((pDeleteOne->Next==NULL)||(j>I-1)) //第I个元素不存在 return 0: pOne ->Next= pDeleteOne ->Next; //将要删除的节点的下一节点的地址赋给要删除的节点的前一节点的指针中(有点拗口) free(pDeleteOne); //使用free释放内存空间,删除节点 return j: }
好了,以上就是链表的插入和删除操作,希望能对你有帮助~~后面再补充双链表和循环链表的内容。
-
C语言 动态链表
2020-12-26 13:39:14大家好~在学习C语言的过程中,动态链表的创建总是会把我弄得有点晕(思路是有的,但是写完代码之后就很容易出错,于是今天想把我在链表创建过程中出现的问题给大家分享一下,也希望大家以后遇到了相关问题就) ...
前言
大家好~
在学习C语言的过程中,动态链表的相关操作总是会把我弄得有点晕。思路是有的,但是写完代码之后就很容易被自己绕晕。
于是今天想把我在链表的创建、输出、插入删除的过程中出现的问题总结一下,理清一下自己的思路,防止以后再犯同样的错。
关于链表
链表是一种常见的重要的数据结构。
它是动态地进行存储分配的一种结构。链表有一个头指针变量,它存放一个地址,该地址指向一个元素。
链表中每一个元素称为结点,每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址。
可以看出,头指针 head 指向第一个元素,第一个元素又指向第二个元素……
直到最后一个元素,该元素不再指向其他元素,它称为表尾,它的地址部分放一个 NULL(表示空地址)链表到此结束。可以得出:
1. 链表中各元素在内存中可以不是连续存放的,要找某一元素,必须先找到上一个元素,根据它提供的下一元素地址才能找到下一个元素。
2. 如果不提供头指针 head 则整个链表无法访问。
题目
动态建立一个长度为4的链表,用于存储学生的信息(姓名与学号),并输出;且实现插入与删除功能,所有功能通过写成函数来实现。
C语言代码
PS:我使用的是 Visual Studio 2019,里面的scanf_s就等同于scanf,但字符串的输入需要在后面标注字符串的大小,否则系统会报错,调试不了。
引入函数:#include"stdio.h" #include"stdlib.h" #include"string.h" #define LEN sizeof(struct student)
定义结构体:
typedef struct student { char name[20]; int num; struct student* next; }STU; int n = 0;
下面是具体的代码,我将其分成了四个板块:一、动态链表的创建
代码如下:
STU* create() { STU* p1, * p2, * head; char name[20]; int num; head = NULL; p1 = p2 = (STU*)malloc(LEN); //开创一个空间用于存放结构体内的数据 printf("请输入学号与姓名:(格式:学号,姓名)\n"); scanf_s("%d,%s", &p1->num, &p1->name, 20); while (p1->num != 0) //num=0时,链表创建结束 { n++; //输入了多少个学生的数据 if (n == 1) head = p1; //把第一个结点的地址赋给head指针 else p2->next = p1; //如果输入的不是第一个结点的数据,就让其内的next指针指向下一个结点的开头 p2 = p1; //p2指针移动到p1指针处(下一个结点的开头) p1 = (STU*)malloc(LEN);//p1又指向新开创结点的开头 scanf_s("%d,%s", &p1->num, &p1->name, 20); } p2->next = NULL; //如果输入的num=0,跳出循环,最后一个结点的next指针指向空指针(即指向NULL值) return head; //返回第一个结点的地址(这样才能找到后面的所有结点) }
二、动态链表的输出
代码如下:
void print(STU* head) //输出学生信息的函数 { STU* p; p = head; //p取head的地址之后,二者同时指向第一个结点的开头 n == 0; printf("\n"); if (head != NULL) { do { printf("学号:%d 姓名:%s\n", p->num, p->name); p = p->next; //把next的地址(即下一个结点的开头)赋给p n++; } while (p != NULL); } printf("\n现在共有%d个学生的信息:\n", n); }
三、动态链表的插入
(1)找到位置p(ai-1)
(2)生成新结点s,数据域赋值
(3)新结点指针域指向ai(ai的地址存放在ai-1的指针域)
(4)ai-1的指针域指向新结点s代码如下:
STU* insert_link(STU* head) //插入结点的函数 { STU* p; printf("请输入需要插入数据的位置:\n"); int m; scanf_s("%d", &m); p = head; //p与head指向第一个结点的开头 int i = 1; //插入位置 printf("请输入需要插入的数据 : (格式:学号,姓名)\n"); STU* j; j = (STU*)malloc(LEN); scanf_s("%d,%s", &j->num, &j->name, 20); if (m == 1) //如果要在第一个位置插入数据 { j->next = head; //新的结点的next指针直接指向头结点,新的数据就会成为第一个结点 head = j; //head指针又指向第一个结点的开始 return head; //返回插入数据后的头结点 } else { while (i < m - 1) /*m-1意味着:如果要在第5个位置插入数据, 则需要让第4个结点的next指向插入数据的开头*/ { p = p->next; //循环找到需要插入数据的上一个结点的next所在位置 i++; } } j->next = p->next; //把p的next地址赋给j的next地址,即新的结点可插入两个结点的中间 p->next = j; //p的next指向j的地址 return head; //返回第一个结点的地址 }
四、动态链表的删除
(1)找到要删除的结点前一个结点p(原因是删除结点的位置在前一个结点的指针域)
(2)把p->next指向ai的下一个结点(把ai从链上摘除)
(3)释放ai空间代码如下:
STU* delete_link(STU* head)//删除结点的函数 { STU* p1, * p2; printf("请输入需要删除数据的位置:\n"); int m; scanf_s("%d", &m); p1 = head; if (m == 1) //如果删除的是第一个结点 { p2 = p1->next; //直接把下一个地址作为返回值 free(p1); //释放内存 return p2; } else { int i = 1; while (i < m - 1) { p1 = p1->next; i++; } p2 = p1->next; p1->next = p1->next->next; //p1的next指向了需要删除的结点的next指向的结点(即越过了中间需要删除的结点) free(p2); //释放需要删除的结点的空间 return head; //返回第一个结点的地址 } }
五、总代码
#include"stdio.h" #include"stdlib.h" #include"string.h" #define LEN sizeof(struct student) typedef struct student { char name[20]; int num; struct student* next; }STU; int n = 0; STU* create() { STU* p1, * p2, * head; char name[20]; int num; head = NULL; p1 = p2 = (STU*)malloc(LEN);//开创一个空间用于存放结构体内的数据 printf("请输入学号与姓名:(格式:学号,姓名)\n"); scanf_s("%d,%s", &p1->num, &p1->name, 20); while (p1->num != 0)//num=0时,链表创建结束 { n++;//输入了多少个学生的数据 if (n == 1) head = p1;//把第一个结点的地址赋给head指针 else p2->next = p1;//如果输入的不是第一个结点的数据,就让其内的next指针指向下一个结点的开头 p2 = p1;//p2指针移动到p1指针处(下一个结点的开头) p1 = (STU*)malloc(LEN);//p1又指向新开创结点的开头 scanf_s("%d,%s", &p1->num, &p1->name, 20); } p2->next = NULL;//如果输入的num=0,跳出循环,最后一个结点的next指针指向空指针(即指向NULL值) return head;//返回第一个结点的地址(这样才能找到后面的所有结点) } STU* insert_link(STU* head)//插入结点的函数 { STU* p; printf("请输入需要插入数据的位置:\n"); int m; scanf_s("%d", &m); p = head;//p与head指向第一个结点的开头 int i = 1;//插入位置 printf("请输入需要插入的数据 : (格式:学号,姓名)\n"); STU* j; j = (STU*)malloc(LEN); scanf_s("%d,%s", &j->num, &j->name, 20); if (m == 1)//如果要在第一个位置插入数据 { j->next = head;//新的结点的next指针直接指向头结点,新的数据就会成为第一个结点 head = j;//head指针又指向第一个结点的开始 return head;//返回插入数据后的头结点 } else { while (i < m - 1) /*m-1意味着:如果要在第5个位置插入数据, 则需要让第4个结点的next指向插入数据的开头*/ { p = p->next;//循环找到需要插入数据的上一个结点的next所在位置 i++; } } j->next = p->next;//把p的next地址赋给j的next地址,即新的结点可插入两个结点的中间 p->next = j;//p的next指向j的地址 return head;//返回第一个结点的地址 } STU* delete_link(STU* head)//删除结点的函数 { STU* p1, * p2; printf("请输入需要删除数据的位置:\n"); int m; scanf_s("%d", &m); p1 = head; if (m == 1) //如果删除的是第一个结点 { p2 = p1->next; //直接把下一个地址作为返回值 free(p1); //释放内存 return p2; } else { int i = 1; while (i < m - 1) { p1 = p1->next; i++; } p2 = p1->next; p1->next = p1->next->next;//p1的next指向了需要删除的结点的next指向的结点(即越过了中间需要删除的结点) free(p2);//释放需要删除的结点的空间 return head;//返回第一个结点的地址 } } void print(STU* head)//输出学生信息的函数 { STU* p; p = head;//p取head的地址之后,二者同时指向第一个结点的开头 n == 0; printf("\n"); if (head != NULL) { do { printf("学号:%d 姓名:%s\n", p->num, p->name); p = p->next;//把next的地址(即下一个结点的开头)赋给p n++; } while (p != NULL); } printf("\n现在共有%d个学生的信息:\n", n); } void main() { STU* pointer; pointer = create();//创建动态链表,返回第一个结点的地址赋给pointer n = 0;//n清零,为了保证之后函数里,从第一个结点开始遍历 print(pointer);//输出链表 pointer = insert_link (pointer); n = 0; print(pointer);//输出链表 pointer = delete_link(pointer); n = 0; print(pointer);//输出链表 free(pointer);//释放占用的内存 system("pause"); }
总结
以上就是关于动态链表的一些具体操作,在整理之后,我对链表的结构和一些内容也有了更加深入的了解。
如果大家对于这个内容和代码还有更好的建议,请多多指正~谢谢! -
077创建动态链表_动态链表_
2021-09-30 13:32:07创建动态链表,动态创建数据库信息,动态分配数据内存空间 -
C语言动态链表的建立
2013-10-16 23:33:24动态链表的建立程序,用C语言编写,供技术与编程人员参考 -
静态链表/动态链表C语言实现
2021-03-20 15:04:18动态链表:之前实现的单链表,双链表,循环链表都属于动态链表,可以在使用过程中动态申请内存。 2.静态链表是一种用数组描述的链表,其实是为了给没有指针的高级语言设计的一种实现单链表功能的方法(大话数据结构...静态链表:
1.静态链表和动态链表的区别:
静态链表要预先申请一整块足够内存的空间,其能存储的元素个数在创建的那一刻就不能再更改了。
动态链表:之前实现的单链表,双链表,循环链表都属于动态链表,可以在使用过程中动态申请内存。
2.静态链表是一种用数组描述的链表,其实是为了给没有指针的高级语言设计的一种实现单链表功能的方法(大话数据结构)。
3.静态链表其实包括两个链表,一个是数据链表,一个是空闲链表。
3.静态链表的第一个节点和最后一个节点作为特殊元素处理,
第一个节点作为备用链表的表头,其cur值指向下一个空闲的节点。
最后一个节点作为数据链表的表头,其cur值指向第一个有数据的节点。
4.优点:在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进在顺序存储结构中插入和删除元素需要移动大量元素的缺点
缺点:没有解决连续存储分配带来的表长难以确定的问题。
5.注意静态链表的删除操作,删除操作要更新两个链表,数据链表要更新前一节点的cur,
空闲链表要把空出的节点放入空闲链表的第一个节点(不能放入空闲链表的末尾,因为找不到空闲链表的末尾),大话数据结构也是放入空闲链表的第一个位置静态链表C语言实现:
#include<stdio.h> #include<stdlib.h> #include<unistd.h> #include<signal.h> //signal() #include<string.h> #include<sys/stat.h> #include<time.h> #include<stdarg.h> #if 1 #define INFO_DEBUG "%d lines in "__FILE__", complie time is "__TIME__" "__DATE__" \n",__LINE__ #define ADI_RUN_ERROR 1 #define ADI_NULL_POINTER -1 #define ADI_OK 0 #define ADI_PRINT printf("[%s][%d]:",__FUNCTION__,__LINE__);printf #define ADI_ASSERT(c,prt,ret) if(c) {printf(prt);return ret;} #endif typedef struct list{ int elem; int cur;//静态链表中把这个称为游标(cursor) }list; #define PARAM_FAIL -1 #define P_NULL -2 #define SUCCESS 0 #define LIST_SIZE 10 /*初始化:只创建头结点*/ list* initList(int size) { int i = 0; list *head = (list*)malloc(size*sizeof(list)); if(NULL==head) {printf("NULL");return head;} for(i=0;i<(size-1);i++) { head[i].cur = i+1;//此时整个链表都是空闲链表,注意这里不能用head[i]->cur = i+1 会报错 } head[i].cur = 0;/*目前静态链表为空,最后一个元素的cur为0*/ return head; } /*销毁链表,销毁和初始化成对使用*/ int destoryList(list* list_destory) { if(NULL==list_destory) {printf("NULL");return PARAM_FAIL;} free(list_destory); return SUCCESS; } /*pos从0开始,pos=0为第一个*/ int insertList(list list_insert[],int elem,int pos,int list_size) { int i=0,empty_id=0,cur=0,last_cur=0; if((NULL == list_insert)&& (pos>(list_size-2)) )//最后一个元素作为特殊节点不容纳元素,则支持的插入位置要减2 比如size=10,最大支持的pos=8 { ADI_PRINT("err param\n"); return PARAM_FAIL; } /*取数据链表的表头*/ list head_data = list_insert[list_size-1];//不能用 list *head_data = list_insert[list_size-1];,会报错 cur = list_size-1;//cur的初始值要=list_size-1注意 while(i<pos) { last_cur = cur; cur = head_data.cur; head_data = list_insert[cur]; i++; } /*取空闲链表的表头list_insert[0]*/ empty_id = list_insert[0].cur;//拿到第一个空闲位置 list_insert[empty_id].elem = elem; list_insert[0].cur = list_insert[0].cur+1;//空闲位置指向下一个位置 list_insert[empty_id].cur = list_insert[last_cur].cur; list_insert[last_cur].cur = empty_id; ADI_PRINT("insert elem = %d\n",elem); return SUCCESS; } /*删除操作要更新两个链表,数据链表要更新前一节点的cur, 空闲链表要把空出的节点放入空闲链表的第一个节点(不能放入空闲链表的末尾,因为找不到空闲链表的末尾),大话数据结构也是放入空闲链表的第一个位置*/ int delList(list list_del[],int elem,int list_size) { int i=0,empty_id=0,cur=0,ele=0,last_cur=0; if(NULL == list_del) { ADI_PRINT("err NULL\n"); return P_NULL; } /*取数据链表的表头*/ list head_data = list_del[list_size-1];//不能用 list *head_data = list_insert[list_size-1];,会报错 cur = head_data.cur; last_cur = list_size-1; while((list_del[cur].elem != elem)&&(0 != cur)) { last_cur = cur; cur = list_del[cur].cur; } /*能找到,cur就是待删除元素在链表中的位置*/ if(0 != cur) { //ADI_PRINT("elem cur = %d\n",cur); list_del[last_cur].cur = list_del[cur].cur;//将上一个数据节点的cur进行修改 list_del[cur].cur = list_del[0].cur; list_del[cur].elem = 0; /*取空闲链表的表头list_insert[0],将被删除的元素放入空闲链表的第一个元素*/ list_del[0].cur = cur; } else { ADI_PRINT("can not find ele = %d\n",elem); return PARAM_FAIL; } ADI_PRINT("del elem = %d\n",elem); return SUCCESS; } int printList(list list_prt[],int list_size) { if(NULL == list_prt) { ADI_PRINT("err NULL\n"); return P_NULL; } int i = 0; /*取数据链表的表头,按数据排布的顺序*/ #if 0 list head_data = list_prt[list_size-1]; //ADI_PRINT("head_data.cur = %d\n",head_data.cur); while(head_data.cur) { head_data = list_prt[head_data.cur]; //ADI_PRINT("head_data.cur = %d\n",head_data.cur); ADI_PRINT("list[%d] = %d\n",i,head_data.elem); i++; } #endif #if 1 /*全部打印,按数组0-max顺序*/ for(int i=0;i<list_size;i++) { ADI_PRINT("list[%d].ele=%d,list[%d].cur=%d\n",i,list_prt[i].elem,i,list_prt[i].cur); } #endif return SUCCESS; } int main() { int ret = 0,pos = 0; list *list_test = initList(LIST_SIZE); if(NULL == list_test) { ADI_PRINT("err \n"); return P_NULL; } printList(list_test,LIST_SIZE); ret = insertList(list_test,0,0,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} ret = insertList(list_test,3,1,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} ret = insertList(list_test,5,2,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} ret = insertList(list_test,7,3,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} ret = insertList(list_test,9,4,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} printList(list_test,LIST_SIZE); ret = insertList(list_test,8,4,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} printList(list_test,LIST_SIZE); ret = delList(list_test,3,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} ret = delList(list_test,7,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} ret = delList(list_test,9,LIST_SIZE); if(SUCCESS != ret) {ADI_PRINT("insert err\n");return PARAM_FAIL;} printList(list_test,LIST_SIZE); return SUCCESS; }
-
数据结构实现顺序结构、动态链表结构下的一元多项式的加法、减法源码
2017-02-27 20:18:22本案例实现了一下功能 1)首先判定多项式是否稀疏 2)分别采用顺序和动态存储结构实现; 3)结果M(x)中无重复阶项和无零系数项; 4)要求输出结果的升幂和降幂两种排列情况 -
C语言实现动态链表
2019-12-21 12:41:56链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。...动态链表的C语言实现 结构体定义已经函数声明 节点结构体定义 typedef struct SNode{ void *pdata; ... -
静态链表和动态链表
2020-04-20 22:26:451. 静态链表和动态链表的区别: (1)静态链表放在栈区 (2)动态链表放在堆区,堆区数据必须要手工开辟,手工释放 2. 单链表定义 #include<stdio.h> #include<string.h> #include<stdlib.h>... -
链表简介(一)——创建单向动态链表及输出单向链表内容
2021-07-09 16:48:44本系列文章简要介绍链表的相关知识。 本文将介绍创建链表和输出链表内容的方法,...链表是动态地进行存储分配的一种数据结构,与数组相比,链表可以根据需要动态地开辟内存单元,并且链表中的节点在内存中是非连续的。 -
约瑟夫环 动态链表 处理
2016-03-21 19:46:12约瑟夫环 动态链表 处理 C -
C语言创建动态链表
2021-04-28 22:50:47建立一个有3名学生数据的单向动态链表,如下图所示,只须包含学生学号和成绩。要求:(1)、在函数外申明学生类型;(2)、链表结点是动态创建的;(3)、链表的建立用名为create的函数完成。 代码段: #include <... -
单项动态链表
2015-11-16 23:42:38主要讲解了大一学生在学习C语言时用到的链表,比较简单,容易理解,单项动态链表 -
C语言实现的双向动态链表
2022-01-01 22:03:24C语言实现的双向动态链表: 该资源包含.c和.h文件,可直接使用或者编译为库函数进行使用。实现了动态双向链表的各种基本功能,e.g. 增删节点,访问某一节点等。 -
C语言建立动态链表
2020-11-03 17:08:12建立一个存放学生数据的动态链表 #include <stdio.h> #include <stdlib.h> //定义一个常量LEN,用来表示一个结构体的长度 #define LEN sizeof(struct Student) //声明一个结构体,包括学生编号,... -
静态链表和动态链表详细讲解教程
2011-07-26 14:43:35对初学者很有用的 详细的讲解过程 是初学者学校的好资料 更能容易的接受 -
构建动态链表
2013-08-27 20:46:02有关c语言的动态链表的创建 有兴趣的可以看看啊 -
动态链表的实现(C语言)
2020-05-03 20:31:06今天复习一下动态链表的实现 C语言实现链表 一定会有着结构体和结构体指针; 那什么是动态链表; 打个比方,如果我想做一个学生成绩管理系统,但我不确定学生的人数,学生的信息可以用一个结构体来表示,由于不确定... -
静态链表与动态链表
2019-04-25 21:47:08静态链表和动态链表的区别: 静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。 1、静态链表是用类似于数组方法实现的,是顺序的存储结构,在物理地址上是连续的,而且需要预先分配地址空间大小。所以... -
用create建立动态链表
2021-05-22 11:29:21写一个函数create,用了建立一个动态链表#include using namespace std; struct LINK { int num; char a[20]; char b[20]; char c[20]; struct LINK *next; }; void menu() { cout用C编写一个函数Create(),该函数... -
静态链表和动态链表的区别
2017-10-10 15:09:35静态链表和动态链表的区别: 静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。 1、静态链表是用类似于数组方法实现的,是顺序的存储结构,在物理地址上是连续的,而且需要预先分配地址空间大小。所以... -
数据结构——动态链表(GIF图解)
2019-12-19 11:39:25一、链表的定义 为了表示每个数据元素a1与其直接后继元素ai+1之间的逻辑关系,对数据元素a1来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域,把存储直接...