全部 文章 问答 分享 共找到20个相关内容
[文章] (10)王道数据结构-建立链表
尾插法#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);LinkListListTailInsert(LinkList&L);LNode*GetElem(LinkListL,inti);intlength(LinkListL);intmain(void){LinkListL;L=ListTailInsert(L);if(!Empty(L)){//获取第3个节点的值intnum=GetElem(L,3)->data;printf("第3个节点的值为:%d\n",num);printf("链表长度为:%d\n",length(L));}return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//按位查找,返回第i个元素(带头结点)LNode*GetElem(LinkListL,inti){if(i<0){returnNULL;}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i){//循环找到第i个节点p=p->next;j++;}returnp;}//尾插法建立单链表(正向建立单链表)LinkListListTailInsert(LinkList&L){intx;L=(LinkList)malloc(sizeof(LNode));//建立头结点LNode*s,*r=L;//r为表尾指针scanf("%d",&x);while(x!=9999){//输入9999结束s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;r=s;//r指向新的表尾节点scanf("%d",&x);}r->next=NULL;//尾节点指针置空returnL;}//求表长度intlength(LinkListL){intlen=0;//统计表长LNode*p=L;while(p->next!=NULL){p=p->next;len++;}returnlen;}头插法#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);LinkListListHeadInsert(LinkList&L);LNode*GetElem(LinkListL,inti);intlength(LinkListL);intmain(void){LinkListL;L=ListHeadInsert(L);if(!Empty(L)){//获取第3个节点的值intnum=GetElem(L,3)->data;printf("第3个节点的值为:%d\n",num);printf("链表长度为:%d\n",length(L));}return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//按位查找,返回第i个元素(带头结点)LNode*GetElem(LinkListL,inti){if(i<0){returnNULL;}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i){//循环找到第i个节点p=p->next;j++;}returnp;}//头插法建立单链表(逆向建立单链表)LinkListListHeadInsert(LinkList&L){LNode*s;intx;L=(LinkList)malloc(sizeof(LNode));//创立头结点L->next=NULL;//初始为空链表scanf("%d",&x);//输入节点的值while(x!=9999){//输入9999结束s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=L->next;L->next=s;scanf("%d",&x);}returnL;}//求表长度intlength(LinkListL){intlen=0;//统计表长LNode*p=L;while(p->next!=NULL){p=p->next;len++;}returnlen;}
2022-08-08 17:24 · 数据结构 / 单链表 / 插入操作
[文章] (12)王道数据结构-循环链表
循环链表基本操作循环单链表#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表节点类型intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolisTail(LinkListL,LNode*p);LinkListCreatList();LinkListLListInsert(LinkListL,inti,intx);intcount=0;intmain(void){inti;LinkListlist,start;InitList(list);printf("请输入循环单链表的数据,以0结束!\n");list=CreatList();printf("循环单链表的元素有:\n");for(start=list->next;start!=NULL;start=start->next){if(count==0){break;}printf("%d",start->data);count--;}printf("\n");return0;}//初始化一个循环链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配一个头结点if(L==NULL){//内存分配不足,分配失败returnfalse;}L->next=L;//头结点next指向头结点returntrue;}//判断循环单链表表尾节点boolisTail(LinkListL,LNode*p){if(p->next==L){returntrue;}else{returnfalse;}}//判断循环单链表是否为空boolEmpty(LinkListL){if(L->next==L){returntrue;}else{returnfalse;}}//循环单链表的建立LinkListCreatList(){LNode*L;L=(LNode*)malloc(sizeof(LNode));L->next=L;LNode*r;r=L;intx;while(scanf("%d",&x)){if(x==0){break;}count++;LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=x;r->next=p;r=p;}r->next=L;returnL;}//循环单链表的插入,在循环链表的第i个位置插入x的元素LinkListLListInsert(LinkListL,inti,intx){LNode*pre;pre=L;inttempi=0;for(tempi=1;tempi<i;tempi++){pre=pre->next;}LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=x;p->next=pre->next;pre->next=p;returnL;}//循环单链表的删除,在循环链表中删除值为x的元素LinkListDelData(LinkListL,intx){LNode*p,*pre;p=L->next;while(p->data!=x){pre=p;p=p->next;}pre->next=p->next;free(p);returnL;}循环双链表#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表节点类型intdata;//每个节点存放一个数据structDNode*prior,*next;//指针指向下一个节点}DNode,*DLinklist;boolInitDLinkList(DLinklist&L);boolisTail(DLinklistL,DNode*p);intmain(void){return0;}//初始化空的循环双链表boolInitDLinkList(DLinklist&L){L=(DNode*)malloc(sizeof(DNode));//分配一个节点if(L==NULL){//内存不足,分配失败returnfalse;}L->prior=L;//头结点的prior指向头结点L->next=L;//头结点的next指向头结点returntrue;}//判断节点p是否为循环双链表的尾节点boolisTail(DLinklistL,DNode*p){if(p->next==L){returntrue;}else{returnfalse;}}//在p节点之后插入s节点boolInsertNextDNode(DNode*p,DNode*s){s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;}
2022-08-11 18:05 · 数据结构 / 循环链表
[文章] (13)王道数据结构-静态链表
静态链表定义分配一整片连续的内存空间,各个节点集中安置#defineMaxSize10//静态链表的最大长度typedefstruct{//静态链表结构的定义intdata;//存储数据元素intnext;//下一个元素的数组下标}SLinkList[MaxSize];注意事项:**查找:**从头结点除法挨个往后遍历节点插入位序为i的节点:①找到一个空的节点,存入数据元素②从头结点出发找到位序为i-1的节点③修改新节点的next④修改i-1号节点的next删除某个节点:①从头结点出发找到前驱节点②修改前驱节点的游标③被删除节点的next设为-2基本功能#include<stdio.h>#definemaxSize7typedefstruct{chardata;intcur;}component;//将结构体数组中所有分量链接到备用链表中voidreserveArr(component*array);//初始化静态链表intinitArr(component*array);//向链表中插入数据,body表示链表的头结点在数组中的位置,add表示插入元素的位置,a表示要插入的数据voidinsertArr(component*array,intbody,intadd,chara);//删除链表中含有字符a的结点voiddeletArr(component*array,intbody,chara);//查找存储有字符elem的结点在数组的位置intselectElem(component*array,intbody,charelem);//将链表中的字符oldElem改为newElemvoidamendElem(component*array,intbody,charoldElem,charnewElem);//输出函数voiddisplayArr(component*array,intbody);//自己需要实现的malloc和free函数intmallocArr(component*array);voidfreeArr(component*array,intk);intmain(){componentarray[maxSize];intbody=initArr(array);printf("静态链表为:\n");displayArr(array,body);printf("在第3的位置上插入结点‘e’:\n");insertArr(array,body,3,'e');displayArr(array,body);printf("删除数据域为‘a’的结点:\n");deletArr(array,body,'a');displayArr(array,body);printf("查找数据域为‘e’的结点的位置:\n");intselectAdd=selectElem(array,body,'e');printf("%d\n",selectAdd);printf("将结点数据域为‘e’改为‘h’:\n");amendElem(array,body,'e','h');displayArr(array,body);return0;}//创建备用链表voidreserveArr(component*array){for(inti=0;i<maxSize;i++){array[i].cur=i+1;//将每个数组分量链接到一起}array[maxSize-1].cur=0;//链表最后一个结点的游标值为0}//提取分配空间intmallocArr(component*array){//若备用链表非空,则返回分配的结点下标,否则返回0(当分配最后一个结点时,该结点的游标值为0)inti=array[0].cur;if(array[0].cur){array[0].cur=array[i].cur;}returni;}//初始化静态链表intinitArr(component*array){reserveArr(array);intbody=mallocArr(array);//声明一个变量,把它当指针使,指向链表的最后的一个结点,因为链表为空,所以和头结点重合inttempBody=body;for(inti=1;i<5;i++){intj=mallocArr(array);//从备用链表中拿出空闲的分量array[tempBody].cur=j;//将申请的空线分量链接在链表的最后一个结点后面array[j].data='a'+i-1;//给新申请的分量的数据域初始化tempBody=j;//将指向链表最后一个结点的指针后移}array[tempBody].cur=0;//新的链表最后一个结点的指针设置为0returnbody;}voidinsertArr(component*array,intbody,intadd,chara){inttempBody=body;for(inti=1;i<add;i++){tempBody=array[tempBody].cur;}intinsert=mallocArr(array);array[insert].cur=array[tempBody].cur;array[insert].data=a;array[tempBody].cur=insert;}voiddeletArr(component*array,intbody,chara){inttempBody=body;//找到被删除结点的位置while(array[tempBody].data!=a){tempBody=array[tempBody].cur;//当tempBody为0时,表示链表遍历结束,说明链表中没有存储该数据的结点if(tempBody==0){printf("链表中没有此数据");return;}}//运行到此,证明有该结点intdel=tempBody;tempBody=body;//找到该结点的上一个结点,做删除操作while(array[tempBody].cur!=del){tempBody=array[tempBody].cur;}//将被删除结点的游标直接给被删除结点的上一个结点array[tempBody].cur=array[del].cur;freeArr(array,del);}intselectElem(component*array,intbody,charelem){inttempBody=body;//当游标值为0时,表示链表结束while(array[tempBody].cur!=0){if(array[tempBody].data==elem){returntempBody;}tempBody=array[tempBody].cur;}return-1;//返回-1,表示在链表中没有找到该元素}voidamendElem(component*array,intbody,charoldElem,charnewElem){intadd=selectElem(array,body,oldElem);if(add==-1){printf("无更改元素");return;}array[add].data=newElem;}voiddisplayArr(component*array,intbody){inttempBody=body;//tempBody准备做遍历使用while(array[tempBody].cur){printf("%c,%d",array[tempBody].data,array[tempBody].cur);tempBody=array[tempBody].cur;}printf("%c,%d\n",array[tempBody].data,array[tempBody].cur);}voidfreeArr(component*array,intk){array[k].cur=array[0].cur;array[0].cur=k;}
2022-08-11 18:06 · 数据结构 / 静态链表
[文章] (19)王道数据结构-队列的链式实现
带头结点#include<stdio.h>#include<stdlib.h>typedefstructLinkNode{intdata;structLinkNode*next;}LinkNode;typedefstruct{LinkNode*front,*rear;}LinkQueue;voidInitQueue(LinkQueue&Q);voidEnQueue(LinkQueue&Q,intx);boolDeQueue(LinkQueue&Q,int&x);boolIsEmpty(LinkQueueQ);intmain(void){LinkQueueQ;intx;InitQueue(Q);EnQueue(Q,1);EnQueue(Q,2);EnQueue(Q,3);EnQueue(Q,4);EnQueue(Q,5);EnQueue(Q,6);EnQueue(Q,7);DeQueue(Q,x);DeQueue(Q,x);DeQueue(Q,x);DeQueue(Q,x);if(!IsEmpty(Q)){printf("x=%d\n",x);}return0;}//初始化队列voidInitQueue(LinkQueue&Q){//初始时,队头和队尾指针指向头结点Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next=NULL;}//判断队列是否为空boolQueueEmpty(LinkQueueQ){if(Q.rear==Q.front){//队空条件returntrue;}else{returnfalse;}}//入队(带头结点)voidEnQueue(LinkQueue&Q,intx){LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;Q.rear->next=s;//新节点插入到rear之后Q.rear=s;//修改表尾指针}//队头元素出队boolDeQueue(LinkQueue&Q,int&x){if(Q.front==Q.rear){//空队returnfalse;}LinkNode*p=Q.front->next;x=p->data;//用变量x返回队头元素Q.front->next=p->next;//修改头结点的next指针if(Q.rear==p){//此次是最后一个节点出队Q.rear=Q.front;//修改rear指针}free(p);//释放节点空间returntrue;}//判断队列是否为空boolIsEmpty(LinkQueueQ){if(Q.front==Q.rear){returntrue;}else{returnfalse;}}不头结点#include<stdio.h>#include<stdlib.h>typedefstructLinkNode{intdata;structLinkNode*next;}LinkNode;typedefstruct{LinkNode*front,*rear;}LinkQueue;voidInitQueue(LinkQueue&Q);voidEnQueue(LinkQueue&Q,intx);boolDeQueue(LinkQueue&Q,int&x);boolIsEmpty(LinkQueueQ);intmain(void){LinkQueueQ;intx;InitQueue(Q);EnQueue(Q,1);EnQueue(Q,2);EnQueue(Q,3);EnQueue(Q,4);EnQueue(Q,5);EnQueue(Q,6);EnQueue(Q,7);DeQueue(Q,x);DeQueue(Q,x);DeQueue(Q,x);DeQueue(Q,x);if(!IsEmpty(Q)){printf("x=%d\n",x);}return0;}//初始化队列voidInitQueue(LinkQueue&Q){//初始时,队头和队尾指针指向头结点Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next=NULL;}//判断队列是否为空boolQueueEmpty(LinkQueueQ){if(Q.rear==Q.front){//队空条件returntrue;}else{returnfalse;}}//入队(带头结点)voidEnQueue(LinkQueue&Q,intx){LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;if(Q.front==NULL){//在空队列中插入第一个元素Q.front=s;//修改队头队尾指针Q.rear=s;}else{Q.rear->next=s;//新节点插入到rear之后Q.rear=s;//修改表尾指针}}//队头元素出队boolDeQueue(LinkQueue&Q,int&x){if(Q.front==Q.rear){//空队returnfalse;}LinkNode*p=Q.front;//p指向此次出队的节点x=p->data;//用变量x返回队头元素Q.front=p->next;//修改front指针if(Q.rear==p){//此次是最后一个节点出队Q.rear=NULL;//rear指向NULLQ.front=NULL;//front指向NULL}free(p);//释放节点空间returntrue;}boolIsEmpty(LinkQueueQ){if(Q.front==NULL){returntrue;}else{returnfalse;}}
2022-08-18 10:32 · 数据结构 / 队列 / 链式存储
[文章] (15)王道数据结构-栈的基本概念
基本定义栈是只允许在一端进行插入或删除操作的线性表重要概念栈顶:允许插入和删除的一端栈底:不允许插入和删除的一端基本结构逻辑结构:与普通线性表相同数据运算:插入、删除操作有区别基本操作InitStack(&S):初始化栈。构造一个空栈S,分配内存空间****DestoryStack(&S):销毁栈。销毁并释放栈S所占用的内存空间Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶Pop(&S,&x):出栈,若栈S未空,则弹出栈顶元素,并用x返回GetTop(S,&x):读取栈顶元素。若栈S非空,则用x返回栈顶元素其他操作:StackEmpty(S):判断一个栈是否为空。若S为空,则返回true,否则返回false常考题型进栈顺序:a->b->c->d->e,有哪些合法的出栈顺序卡特兰数n个不同元素出栈,出栈不同排列的个数为
2022-08-11 18:11 · 数据结构 /
[文章] (09)王道数据结构-单链表的查找
按位查找#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolListInsert(LinkList&L,inti,inte);boolListDelete(LinkList&L,inti,int&e);LNode*GetElem(LinkListL,inti);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!\n");}ListInsert(L,1,11);ListInsert(L,2,22);ListInsert(L,3,33);ListInsert(L,4,44);ListInsert(L,5,55);ListInsert(L,6,66);ListInsert(L,7,77);ListInsert(L,8,88);if(!Empty(L)){printf("插入成功!\n");}inte=0;ListDelete(L,8,e);//判断是否删除成功LNode*node=NULL;node=GetElem(L,8);if(node==NULL){printf("删除成功!\n");}node=GetElem(L,6);printf("获取元素:%d\n",node->data);return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//在第i个位置插入元素e(带头结点)boolListInsert(LinkList&L,inti,inte){if(i<1){returnfalse;printf("插入失败!\n");}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL){//i值不合法returnfalse;printf("插入失败!\n");}LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;//将节点s连接到p之后returntrue;//插入成功}//按位序删除:带头结点boolListDelete(LinkList&L,inti,int&e){if(i<1){returnfalse;}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL){//i值不合法returnfalse;}if(p->next==NULL){//第i-1个节点之后已无其他节点returnfalse;}LNode*q=p->next;//令p指向被删除节点e=q->data;//用e返回元素的值p->next=q->next;//将*q节点从链中“断开”free(q);returntrue;}//按位查找,返回第i个元素(带头结点)LNode*GetElem(LinkListL,inti){if(i<0){returnNULL;}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i){//循环找到第i个节点p=p->next;j++;}returnp;}封装之后#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolListInsert(LinkList&L,inti,inte);boolListDelete(LinkList&L,inti,int&e);boolInsertNextNode(LNode*p,inte);LNode*GetElem(LinkListL,inti);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!\n");}ListInsert(L,1,11);ListInsert(L,2,22);ListInsert(L,3,33);ListInsert(L,4,44);ListInsert(L,5,55);ListInsert(L,6,66);ListInsert(L,7,77);ListInsert(L,8,88);if(!Empty(L)){printf("插入成功!\n");}inte=0;ListDelete(L,8,e);//判断是否删除成功LNode*node=NULL;node=GetElem(L,8);if(node==NULL){printf("删除成功!\n");}node=GetElem(L,6);printf("获取元素:%d\n",node->data);return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//在第i个位置插入元素e(带头结点)boolListInsert(LinkList&L,inti,inte){if(i<1){returnfalse;}LNode*p=GetElem(L,i-1);//找到第i-1个节点returnInsertNextNode(p,e);//p后插入新元素e}//按位序删除:带头结点boolListDelete(LinkList&L,inti,int&e){if(i<1){returnfalse;}LNode*p=GetElem(L,i-1);//找到第i-1个节点if(p==NULL){//i值不合法returnfalse;}if(p->next==NULL){//第i-1个节点之后已无其他节点returnfalse;}LNode*q=p->next;//令p指向被删除节点e=q->data;//用e返回元素的值p->next=q->next;//将*q节点从链中“断开”free(q);returntrue;}//按位查找,返回第i个元素(带头结点)LNode*GetElem(LinkListL,inti){if(i<0){returnNULL;}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i){//循环找到第i个节点p=p->next;j++;}returnp;}//后插操作:在p节点之后插入元素eboolInsertNextNode(LNode*p,inte){if(p==NULL){returnfalse;}LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL){//内存分配失败returnfalse;}s->data=e;//用节点s保存数据元素es->next=p->next;p->next=s;returntrue;}按值查找#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolListInsert(LinkList&L,inti,inte);boolListDelete(LinkList&L,inti,int&e);boolInsertNextNode(LNode*p,inte);LNode*LocalElem(LinkListL,inte);LNode*GetElem(LinkListL,inti);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!\n");}ListInsert(L,1,11);ListInsert(L,2,22);ListInsert(L,3,33);ListInsert(L,4,44);ListInsert(L,5,55);ListInsert(L,6,66);ListInsert(L,7,77);ListInsert(L,8,88);if(!Empty(L)){printf("插入成功!\n");}inte=0;ListDelete(L,8,e);//判断是否删除成功LNode*node=NULL;node=LocalElem(L,88);if(node==NULL){printf("删除成功!\n");}node=LocalElem(L,66);printf("获取元素位序:%d\n",node->data);return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//在第i个位置插入元素e(带头结点)boolListInsert(LinkList&L,inti,inte){if(i<1){returnfalse;}LNode*p=GetElem(L,i-1);//找到第i-1个节点returnInsertNextNode(p,e);//p后插入新元素e}//按位序删除:带头结点boolListDelete(LinkList&L,inti,int&e){if(i<1){returnfalse;}LNode*p=GetElem(L,i-1);//找到第i-1个节点if(p==NULL){//i值不合法returnfalse;}if(p->next==NULL){//第i-1个节点之后已无其他节点returnfalse;}LNode*q=p->next;//令p指向被删除节点e=q->data;//用e返回元素的值p->next=q->next;//将*q节点从链中“断开”free(q);returntrue;}//按值查找,找到数据域==e的节点LNode*LocalElem(LinkListL,inte){LNode*p=L->next;//从第一个节点开始查找数据域为e的节点while(p!=NULL&&p->data!=e){p=p->next;}returnp;}//按位查找,返回第i个元素(带头结点)LNode*GetElem(LinkListL,inti){if(i<0){returnNULL;}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i){//循环找到第i个节点p=p->next;j++;}returnp;}//后插操作:在p节点之后插入元素eboolInsertNextNode(LNode*p,inte){if(p==NULL){returnfalse;}LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL){//内存分配失败returnfalse;}s->data=e;//用节点s保存数据元素es->next=p->next;p->next=s;returntrue;}求表长度#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolListInsert(LinkList&L,inti,inte);boolInsertNextNode(LNode*p,inte);LNode*GetElem(LinkListL,inti);intlength(LinkListL);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!\n");}ListInsert(L,1,11);ListInsert(L,2,22);ListInsert(L,3,33);ListInsert(L,4,44);ListInsert(L,5,55);ListInsert(L,6,66);ListInsert(L,7,77);ListInsert(L,8,88);printf("链表长度为:%d\n",length(L));return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//在第i个位置插入元素e(带头结点)boolListInsert(LinkList&L,inti,inte){if(i<1){returnfalse;}LNode*p=GetElem(L,i-1);//找到第i-1个节点returnInsertNextNode(p,e);//p后插入新元素e}//按位查找,返回第i个元素(带头结点)LNode*GetElem(LinkListL,inti){if(i<0){returnNULL;}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i){//循环找到第i个节点p=p->next;j++;}returnp;}//后插操作:在p节点之后插入元素eboolInsertNextNode(LNode*p,inte){if(p==NULL){returnfalse;}LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL){//内存分配失败returnfalse;}s->data=e;//用节点s保存数据元素es->next=p->next;p->next=s;returntrue;}//求表长度intlength(LinkListL){intlen=0;//统计表长LNode*p=L;while(p->next!=NULL){p=p->next;len++;}returnlen;}
2022-08-08 17:23 · 单链表 / 数据结构 / 查找
[文章] (02)王道数据结构-空间复杂度
算法1:逐步递增型爱你#include<stdio.h>voidloveYou(intn);intmain(void){loveYou(3000);return0;}voidloveYou(intn){//n为问题规模inti=1;//爱你的程度while(i<=n){//每次+1i++;printf("ILoveYou%d\n",i);}printf("ILoveYouMoreThan%d\n",n);}代码分析:(1)程序运行时,会将程序代码装载进内存中,而内存中存放程序代码的部分大小是固定的,与问题规模无关(2)本程序中,装入内存的变量有局部变量i和参数n,他们所占内存空间大小是不变的(3)本程序空间复杂度:S(n)=O(1)算法2:数组的空间复杂度#include<stdio.h>intmain(void){intflag[n];//声明一个长度为n的数组,此时时间复杂度S(n)=O(n)/*下列代码空间复杂度度:S(n)=O(n*n)+O(n)+O(1)=O(n*n)*/intflag[n][n];intother[n];inti;return0;}**算法2:**递归型爱你#include<stdio.h>voidloveYou(intn);intmain(void){loveYou(5);return0;}voidloveYou(intn){//n为问题规模inta,b,c;//声明一系列局部变量if(n>1){loveYou(n-1);}printf("ILoveYou%d\n",n);}代码分析:第1层调用:n=5,a,b,c第2层调用:n=4,a,b,c第3层调用:n=3,a,b,c第2层调用:n=2,a,b,c第1层调用:n=1,a,b,c空间复杂度:等于递归调用的深度,S(n)=O(n)(去掉了常数项5)算法3:递归型爱你#include<stdio.h>voidloveYou(intn);intmain(void){loveYou(5);return0;}voidloveYou(intn){//n为问题规模intflag[n];//声明一个数组if(n>1){loveYou(n-1);}printf("ILoveYou%d\n",n);}代码分析:第1层调用:n=5,flag[5]第2层调用:n=4,flag[4]第3层调用:n=3,flag[3]第2层调用:n=2,flag[2]第1层调用:n=1,flag[1]空间复杂度:
2022-08-05 10:32 · 数据结构 / 王道 / 空间复杂度
[文章] (07)王道数据结构-单链表的定义
不带头结点#include<stdio.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!");}return0;}//初始化空的单链表boolInitList(LinkList&L){L=NULL;//空表,暂时没有任何节点returntrue;}//判断单链表是否为空boolEmpty(LinkListL){return(L==NULL);}注意事项(一)不带头结点只要判断头指针是否为空就能判断链表是否为空(二)初始化链表之前需要将头指针置空带头结点#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!");}return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}注意事项(一)头结点并不存储数据,是为了之后的操作(二)判断链表是否为空,判断的是头结点之后的节点是否为空
2022-08-08 17:19 · 单链表 / 数据结构
[文章] (14)王道数据结构-顺序表和链表比较
逻辑结构都属于线性表,都是线性结构存储结构相同点:都属于线性表,都是线性结构顺序表优点:支持随机存取、存储密度高缺点:大片连续空间分配不方便,改变容量不方便链表优点:离散的小空间分配方便,改变容量方便缺点不可随机存取,存储密度低基本操作创建顺序表需要预先分配大片连续空间,分配空间过小不好扩展,过大浪费空间。容量不可改变链表只需要分配一个头结点(或头指针)之后方便扩展。容量可以改变,但需要移动大量元素,时间代价高销毁顺序表修改lengh=0,使用静态数组系统自动回收空间。链表依次删除各个节点(free)使用的是动态数组。需要特别注意的是malloc和free必须成对出现,使用的是stdllib包增删顺序表插入/删除元素要将后续元素都后移/前移,时间复杂度O(n),时间开销主要来自移动元素。如果数据元素很大,则移动的时间代价很高链表插入/删除元素只需要修改指针即可,时间复杂度O(n),时间开销主要来自查找目标元素。查找元素的时间代价更低查找顺序表**按位查找:**O(1)**按值查找:**O(n),若表内元素有序,可在O(log2n)时间内找到链表**按位查找:**O(n)**按值查找:**O(n)选择表长难以预估、经常需要增加/删除元素选择链表表长可以预估、查询(搜索)操作较多选择顺序表
2022-08-11 18:08 · 数据结构 / 顺序表 / 链表
[文章] (04)王道数据结构-顺序表的定义
顺序表的定义:定义:用顺序存储的方式实现线性表。顺序存储是把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。顺序表实现-静态分配:#defineMaxSize10//定义最大长度typedefstruct{intdata[MaxSize];//用静态的“数组”存放数据元素intlength;//顺序表的当前长度}SqList;//顺序表的类型定义//基本操作-初始化顺序表voidInitList(SqList&L);intmain(void){SqListL;//声明一个顺序表InitList(L);//初始化顺序表return0;}voidInitList(SqList&L){for(inti=0;i<MaxSize;i++){L.data[i]=0;//将所有数据元素设置为默认初始值}//顺序表初始长度为0L.length=0;}注意事项:(01)静态分配的方式中,需要对数据进行初始化,否则内存中可能存在遗留的脏数据(02)静态分配的方式无法保证之后添加数据后的操作顺序表实现-动态分配:#include<stdio.h>#include<stdlib.h>#defineInitSize10//默认的最大长度typedefstruct{int*data;//指示动态分配数组的指针intMaxSize;//顺序表的最大容量intlength;//顺序表的当前长度}SqList;voidInitList(SqList&L);voidIncreaseSize(SqList&L,intlen);intmain(void){SqListL;//声明一个顺序表InitList(L);//初始化顺序表IncreaseSize(L,5);//增加顺序表长度return0;}voidInitList(SqList&L){//用malloc函数声明一片连续的存储空间L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;}//增加动态数组的长度voidIncreaseSize(SqList&L,intlen){int*p=L.data;L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));for(inti=0;i<L.length;i++){L.data[i]=p[i];}L.MaxSize=L.MaxSize+len;free(p);}顺序表的特点:(1)随机访问,即可以在O(1)时间内找到第i个元素(2)存储密度高,每个节点只存储数据元素(3)扩展容量不方便(即便采用动态分配的方式实现,扩展长度的时间复杂度也比较高)
2022-08-05 10:36 · 数据结构 / 王道 / 顺序表
[文章] (01)王道数据结构-时间复杂度
算法1:逐步递增型爱你#include<stdio.h>voidloveYou(intn);intmain(void){loveYou(3000);return0;}voidloveYou(intn){//n为问题规模inti=1;//爱你的程度while(i<=n){//每次+1i++;printf("ILoveYou%d\n",i);}printf("ILoveYouMoreThan%d\n",n);}(一)代码分析:(1)语句频度第09行:执行了1次第10行:执行了3001次第11行:执行了3000次第12行:执行了3000次第14行:执行了1次T(3000)=1+3001+2*3000+1(2)时间复杂度时间开销与问题规模n之间的关系T(n)=3n+3实际上时间复杂度只考虑阶数高的部分,高阶的常数项可以忽略故本代码时间复杂度为:T(n)=n(二)运算规则(三)时间复杂度排序记忆口诀:常对幂指阶算法2:嵌套循环型爱你#include<stdio.h>voidloveYou(intn);intmain(void){loveYou(5);return0;}voidloveYou(intn){//n为问题规模inti=1;//爱你的程度while(i<=n){//每次+1i++;printf("ILoveYou%d\n",i);for(intj=1;j<=n;j++){//嵌套循环两层printf("IamIronMan\n");//内层循环共执行n*n次}}printf("ILoveYouMoreThan%d\n",n);}结论:(1)顺序执行的代码只会影响常数项,可以忽略(2)只需要挑循环中的一个基本操作分析它的执行次数与n的关系即可(3)如果有多层循环嵌套,只需关注最深层循环循环了几次算法3:指数递增型爱你#include<stdio.h>voidloveYou(intn);intmain(void){loveYou(100);return0;}voidloveYou(intn){//n为问题规模inti=1;//爱你的程度while(i<=n){i=i*2;//每次翻倍printf("ILoveYou%d\n",i);}printf("ILoveYouMoreThan%d\n",n);}时间复杂度分析:(1)最深层语句频度为x(2)循环结束时满足:(3)时间复杂度:算法4:搜索数字型爱你#include<stdio.h>voidloveYou(intflag[],intn);intmain(void){intflag[]={1,2,3,4,5,6,7,8,9};loveYou(flag,5);return0;}voidloveYou(intflag[],intn){//n为问题规模printf("IAmIronMan\n");for(inti=0;i<n;i++){if(flag[i]==n){printf("ILoveYou%d\n",i);break;}}}时间复杂度分析:最好情况:元素n在第一个位置,时间复杂度为T(n)=O(1)最坏情况:元素n在最后一个位置,时间复杂度为T(n)=O(n)平均情况:元素n在任意一个位置的概率为1/n,时间复杂度为T(n)=O(n)引申出最好时间复杂度,最坏时间复杂度,平均时间复杂度
2022-08-05 10:27 · 数据结构 / 王道 / 时间复杂度
[文章] (06)王道数据结构-顺序表的查找
按位查找:#defineInitSize10//默认最大长度#include<stdio.h>#include<stdlib.h>typedefstruct{int*data;//指示动态分配数组的指针intMaxSize;//顺序表的最大容量intlength;//顺序表的当前长度}SqList;//初始化数组voidInitList(SqList&L);//获取数组元素(按位)intGetElem(SqListL,inti);//判断数组是否已满boolIsFull(SqList&L);//追加元素boolListAppend(SqList&L,inte);intmain(void){SqListL;//初始化顺序表InitList(L);//插入元素ListAppend(L,11);ListAppend(L,22);ListAppend(L,33);ListAppend(L,44);ListAppend(L,55);ListAppend(L,66);ListAppend(L,77);//获取数组元素intnum=GetElem(L,3);printf("获取到%d",num);return0;}voidInitList(SqList&L){//用malloc函数申请一片连续的存储空间L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;}intGetElem(SqListL,inti){//和数组的获取方法相同returnL.data[i-1];}boolIsFull(SqList&L){//顺序表当前长度和最大长度一样说明满了if(L.length==L.MaxSize){returntrue;}else{returnfalse;}}boolListAppend(SqList&L,inte){if(IsFull(L)){printf("数组满了!\n");returnfalse;}else{//数组当前位置插入eL.data[L.length]=e;//插入后长度+1L.length++;returntrue;}}时间复杂度时间复杂度:O(1),因为在内存中是连续存放的,可以根据起始地址和数据元素大小立即找到第i个元素按值查找:#defineInitSize10//默认最大长度#include<stdio.h>#include<stdlib.h>typedefstruct{int*data;//指示动态分配数组的指针intMaxSize;//顺序表的最大容量intlength;//顺序表的当前长度}SqList;//初始化数组voidInitList(SqList&L);//获取数组元素(按值)intLocateElem(SqListL,inte);//判断数组是否已满boolIsFull(SqList&L);//追加元素boolListAppend(SqList&L,inte);intmain(void){SqListL;//初始化顺序表InitList(L);//插入元素ListAppend(L,11);ListAppend(L,22);ListAppend(L,33);ListAppend(L,44);ListAppend(L,55);ListAppend(L,66);ListAppend(L,77);//获取数组元素下标intlocal=LocateElem(L,33);printf("获取到%d",local);return0;}voidInitList(SqList&L){//用malloc函数申请一片连续的存储空间L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;}intLocateElem(SqListL,inte){//在顺序表L中查找第一个元素值等于e的元素,并返回其位序for(inti=0;i<L.length;i++){if(L.data[i]==e){returni+1;//数组下标为i的元素值等于e,其返回的位序i+1}}return0;//退出循环说明查找失败}boolIsFull(SqList&L){//顺序表当前长度和最大长度一样说明满了if(L.length==L.MaxSize){returntrue;}else{returnfalse;}}boolListAppend(SqList&L,inte){if(IsFull(L)){printf("数组满了!\n");returnfalse;}else{//数组当前位置插入eL.data[L.length]=e;//插入后长度+1L.length++;returntrue;}}时间复杂度最好情况:目标元素在表头,循环1次,最好时间复杂度=O(1)最坏情况:目标元素在表尾,循环n次,最坏时间复杂度=O(n)平均情况:假设目标元素出现在任何一个位置的概率相同,都是1/n目标元素在第1位,循环1次;在第2位,循环2次;在第n位,循环n次平均循环次数=
2022-08-08 17:19 · 数据结构 / 查找操作 / 顺序表
[文章] (05)王道数据结构-顺序表的插入与删除
插入操作:#defineMaxSize10//定义最大长度typedefstruct{intdata[MaxSize];//用静态的“数组”存放数据元素intlength;//顺序表的当前长度}SqList;//顺序表的类型定义//基本操作-初始化顺序表voidInitList(SqList&L);//基本操作-插入元素boolListInsert(SqList&L,inti,inte);intmain(void){SqListL;//声明一个顺序表InitList(L);//初始化顺序表ListInsert(L,1,1);ListInsert(L,2,2);ListInsert(L,3,3);return0;}voidInitList(SqList&L){for(inti=0;i<MaxSize;i++){L.data[i]=0;//将所有数据元素设置为默认初始值}//顺序表初始长度为0L.length=0;}boolListInsert(SqList&L,inti,inte){if(i<1i>L.length+1){//判断i的范围是否有效returnfalse;}if(L.length>=MaxSize){//当前存储空间已满,不能插入returnfalse;}for(intj=L.length;j>=i;j--){//将第i个元素及之后的元素后移L.data[j]=L.data[j-1];}L.data[i-1]=e;//在位置i处放入eL.length++;//长度加1returntrue;}时间复杂度最好情况:新元素插入到表尾,不需要移动元素,其中i=n+1时循环0次,最好时间复杂度为O(1)最坏情况:新元素插入到表头,需要将原有的n个元素全部都向后移动,其中i=1,循环n次,最坏时间复杂度O(n)平均情况:假设新元素插入任何一个位置的概率相同,即i=1,2,3,...,length+1的概率都是p=1/(n+1),i=1,循环n次;i=2时,循环n-1次;i=3,循环n-2次...i=n+1时循环0次删除操作:#defineMaxSize10//定义最大长度typedefstruct{intdata[MaxSize];//用静态的“数组”存放数据元素intlength;//顺序表的当前长度}SqList;//顺序表的类型定义//基本操作-初始化顺序表voidInitList(SqList&L);//基本操作-插入元素boolListInsert(SqList&L,inti,inte);boolListDelete(SqList&L,)intmain(void){SqListL;//声明一个顺序表InitList(L);//初始化顺序表ListInsert(L,1,1);ListInsert(L,2,2);ListInsert(L,3,3);return0;}voidInitList(SqList&L){for(inti=0;i<MaxSize;i++){L.data[i]=0;//将所有数据元素设置为默认初始值}//顺序表初始长度为0L.length=0;}boolListInsert(SqList&L,inti,inte){if(i<1i>L.length+1){//判断i的范围是否有效returnfalse;}if(L.length>=MaxSize){//当前存储空间已满,不能插入returnfalse;}for(intj=L.length;j>=i;j--){//将第i个元素及之后的元素后移L.data[j]=L.data[j-1];}L.data[i-1]=e;//在位置i处放入eL.length++;//长度加1returntrue;}时间复杂度最好情况:删除表尾元素,不需要移动元素,其中i=n时循环0次,最好时间复杂度为O(1)最坏情况:删除表头元素,需要将后续的n-1个元素全部都向前移动i=1,循环n-1次,最坏时间复杂度O(n)平均情况:假设删除任何一个位置元素的概率相同,即i=1,2,3,...,length+1的概率都是p=1/n,其中i=1,循环n-1次,i=2时,循环n-2次;i=3,循环n-3次,...,i=n时,循环0次
2022-08-05 10:41 · 王道 / 数据结构 / 顺序表
[文章] (17)王道数据结构-栈的链式存储实现
基本结构typedefstructLinknode{ElemenTypedata;//数据域structLinknode*next;//指针域}*LiStack;//栈类型定义实现代码#include<stdio.h>#include<stdlib.h>typedefstructNode{intvalue;structNode*next;}Node;typedefstruct{Node*top;intcount;}Stack;boolinit(Stack*s);boolpush(Stack*s,inte);boolpop(Stack*s,int*e);intmain(){inti,e;Stacks;init(&s);for(i=0;i<5;i++){push(&s,i);pop(&s,&e);printf("%d\n",e);}return0;}boolinit(Stack*s){s->top=NULL;//初始化为空栈s->count=0;returntrue;}boolpush(Stack*s,inte){Node*newNode=(Node*)malloc(sizeof(Node));if(NULL==newNode){returnfalse;}newNode->next=s->top;newNode->value=e;s->top=newNode;s->count++;returntrue;}boolpop(Stack*s,int*e){Node*temp=NULL;if(0==s->count){returnfalse;}temp=s->top;*e=temp->value;s->top=temp->next;free(temp);s->count--;returntrue;}
2022-08-18 10:27 · 数据结构 / / 链式存储
[文章] (11)王道数据结构-双链表的基本操作
双链表基本操作#include<stdio.h>#include<stdlib.h>typedefstructDNode{//定义双链表节点类型intdata;//数据域structDNode*prior,*next;//前驱和后继指针}DNode,*DLinkList;DNode*InitDLinkList(DLinkList&L);boolInsertNextDNode(DNode*p,DNode*s);boolDListInsert(DNode*head,inti,inte);DNode*GetElem(DNode*head,inti);boolDeleteNextDNode(DNode*p);voidDestoryList(DLinkList&L);voidShowList(DNode*head);DNode*DelData(DNode*head,intdata);intmain(void){//创建头结点DNode*head=NULL;DLinkListList;//初始化链表head=InitDLinkList(List);DListInsert(head,1,11);DListInsert(head,2,22);DListInsert(head,3,33);DListInsert(head,4,44);DListInsert(head,5,55);DListInsert(head,6,66);DListInsert(head,7,77);DListInsert(head,8,88);//获取元素,判断是否插入成功intnum=-1;num=GetElem(head,8)->data;printf("最后一个元素是%d\n",num);ShowList(head);//DestoryList(List);DelData(head,66);ShowList(head);return0;}//初始化双链表DNode*InitDLinkList(DLinkList&head){head=(DNode*)malloc(sizeof(DNode));//分配一个头结点if(head==NULL){//内存不足,分配失败returnNULL;}head->prior=NULL;//头结点prior永远指向NULLhead->next=NULL;//头结点之后暂时没有节点returnhead;//返回头结点}//在p节点之后插入s节点boolInsertNextDNode(DNode*p,DNode*s){if(p==NULL||s==NULL){returnfalse;}s->next=p->next;if(p->next!=NULL){p->next->prior=s;}s->prior=p;p->next=s;returntrue;}//链表中插入数据boolDListInsert(DNode*head,inti,inte){//声明一个指向首元节点的指针,方便后期向链表中添加新创建的节点DNode*list=head;DNode*body=(DNode*)malloc(sizeof(DNode));//创建新的节点并初始化if(i==1){//头结点赋值head->prior=NULL;head->next=NULL;head->data=e;}else{intj=2;while(j<i){j++;list=list->next;}body->prior=NULL;body->next=NULL;body->data=e;//新节点与链表最后一个节点建立关系InsertNextDNode(list,body);}returntrue;//p后插入新元素e}//按位查找,返回第i个元素(带头结点)DNode*GetElem(DNode*head,inti){if(i<0){returnNULL;}DNode*p;//指针p指向当前扫描到的节点intj=1;//当前p指向的是第几个节点p=head;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i){//循环找到第i个节点p=p->next;j++;}returnp;}//删除p结点的后继节点boolDeleteNextDNode(DNode*p){if(p==NULL){returnfalse;}DNode*q=p->next;//找到p的后继节点qif(q==NULL){//p没有后继节点returnfalse;}p->next=q->next;if(q->next!=NULL){//q节点不是最后一个节点q->next->prior=p;}free(q);returntrue;}//清空双链表voidDestoryList(DLinkList&L){//循环释放各个数据节点while(L->next!=NULL){DestoryList(L);}free(L);//释放头结点L=NULL;//头指针指向NULL}//双链表的遍历voidShowList(DNode*head){printf("后向遍历:\n");DNode*temp=head;while(temp!=NULL){/*如果该节点无后继节点,说明此节点是链表的最后一个节点*/if(temp->next==NULL){printf("%d\n",temp->data);}else{printf("%d->",temp->data);}temp=temp->next;}/*后向遍历:while(p!=NULL){p=p->next;}前向遍历:while(p!=NULL){p=p->prior;}前向遍历(忽略头结点):while(p!=NULL){p=p->prior;}*/}//删除结点的函数,data为要删除结点的数据域的值DNode*DelData(DNode*head,intdata){DNode*temp=head;//遍历链表while(temp!=NULL){//判断当前结点中数据域和data是否相等,若相等,摘除该结点if(temp->data==data){temp->prior->next=temp->next;temp->next->prior=temp->prior;free(temp);returnhead;}temp=temp->next;}printf("链表中无该数据元素");returnhead;}注意事项双向链表不可随机读取,按位查找、按值查找都只能用遍历的方式实现。时间复杂度为O(n)
2022-08-11 18:04 · 数据结构 / 双联表
[文章] (16)王道数据结构-栈的顺序存储实现
方式一:#include<stdio.h>#defineMaxSize10//定义栈中元素最大个数typedefstruct{intdata[MaxSize];//静态数组存放栈中元素inttop;//栈顶指针}SqStack;voidInitStack(SqStack&S);boolStackEmpty(SqStackS);boolPush(SqStack&S,intx);boolPop(SqStack&S,int&x);intGetTop(SqStackS,int&x);intmain(void){SqStackS;intx,top;InitStack(S);Push(S,1);Push(S,2);Push(S,3);Push(S,4);Push(S,5);Push(S,6);Push(S,7);Pop(S,x);Pop(S,x);Pop(S,x);Pop(S,x);printf("x=%d\n",x);top=GetTop(S,x);printf("top=%d\n",top);if(!StackEmpty(S)){Push(S,8);printf("x=%d\n",x);}return0;}//初始化栈voidInitStack(SqStack&S){S.top=-1;//初始化栈顶指针}//判断栈空boolStackEmpty(SqStackS){if(S.top==-1){//栈空returntrue;}else{returnfalse;}}//新元素入栈boolPush(SqStack&S,intx){if(S.top==MaxSize-1){//栈满报错returnfalse;}S.top=S.top+1;//指针加1S.data[S.top]=x;//新元素入栈returntrue;}//出栈操作boolPop(SqStack&S,int&x){if(S.top==-1){//栈空,报错returnfalse;}x=S.data[S.top];//栈顶元素先出栈S.top=S.top-1;//指针减1returntrue;}//读取栈顶元素intGetTop(SqStackS,int&x){if(S.top==-1){//栈空,报错returnfalse;}x=S.data[S.top];//x记录栈顶元素returnx;}方式二#include<stdio.h>#defineMaxSize10//定义栈中元素最大个数typedefstruct{intdata[MaxSize];//静态数组存放栈中元素inttop;//栈顶指针}SqStack;voidInitStack(SqStack&S);boolStackEmpty(SqStackS);boolPush(SqStack&S,intx);boolPop(SqStack&S,int&x);intGetTop(SqStackS,int&x);intmain(void){SqStackS;intx,top;InitStack(S);Push(S,1);Push(S,2);Push(S,3);Push(S,4);Push(S,5);Push(S,6);Push(S,7);Pop(S,x);Pop(S,x);Pop(S,x);Pop(S,x);printf("x=%d\n",x);top=GetTop(S,x);printf("top=%d\n",top);if(!StackEmpty(S)){Push(S,8);printf("x=%d\n",x);}return0;}//初始化栈voidInitStack(SqStack&S){S.top=-1;//初始化栈顶指针}//判断栈空boolStackEmpty(SqStackS){if(S.top==-1){//栈空returntrue;}else{returnfalse;}}//新元素入栈boolPush(SqStack&S,intx){if(S.top==MaxSize-1){//栈满报错returnfalse;}S.data[S.top++]=x;returntrue;}//出栈操作boolPop(SqStack&S,int&x){if(S.top==-1){//栈空,报错returnfalse;}x=S.data[--S.top];returntrue;}//读取栈顶元素intGetTop(SqStackS,int&x){if(S.top==-1){//栈空,报错returnfalse;}x=S.data[S.top];//x记录栈顶元素returnx;}共享栈两个栈共享同一片空间,栈满的条件是top0+1=top1#defineMaxSize10//定义栈中元素的最大个数typedefstruct{intdata[MaxSize];//静态数组中存放栈中元素inttop0;//0号栈栈顶指针inttop1;//1号栈栈顶指针}ShStack;intmain(void){ShStackS;InitStack(S);return0;}//初始化栈voidInitStack(ShStack&S){S.top0=-1;//初始化栈顶指针S.top1=MaxSize;}
2022-08-11 18:12 · / 顺序存储
[文章] (08)王道数据结构-单链表插入和删除
按位序插入带头节点#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolListInsert(LinkList&L,inti,inte);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!\n");}ListInsert(L,1,11);ListInsert(L,2,22);ListInsert(L,3,33);ListInsert(L,4,44);ListInsert(L,5,55);ListInsert(L,6,66);ListInsert(L,7,77);ListInsert(L,8,88);if(!Empty(L)){printf("插入成功!");}return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//在第i个位置插入元素e(带头结点)boolListInsert(LinkList&L,inti,inte){if(i<1){returnfalse;printf("插入失败!\n");}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL){//i值不合法returnfalse;printf("插入失败!\n");}LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;//将节点s连接到p之后returntrue;//插入成功}不带头结点#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolListInsert(LinkList&L,inti,inte);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!\n");}ListInsert(L,1,11);ListInsert(L,2,22);ListInsert(L,3,33);ListInsert(L,4,44);ListInsert(L,5,55);ListInsert(L,6,66);ListInsert(L,7,77);ListInsert(L,8,88);if(!Empty(L)){printf("插入成功!");}return0;}//初始化空的单链表boolInitList(LinkList&L){L=NULL;//空表,暂时没有任何节点returntrue;}//判断单链表是否为空boolEmpty(LinkListL){return(L==NULL);}boolListInsert(LinkList&L,inti,inte){if(i<1){returnfalse;printf("插入失败!\n");}if(i==1){//插入第1个节点的操作与其他节点操作不同LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=L;L=s;//头指针指向新的节点returntrue;}LNode*p;//指针p指向当前扫描到的节点intj=1;//当前p指向的是第几个节点p=L;//p指向第1个节点(非头节点)while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL){//i值不合法returnfalse;printf("插入失败!\n");}LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;//将节点s连接到p之后returntrue;//插入成功}后插操作#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolListInsert(LinkList&L,inti,inte);boolInsertNextNode(LNode*p,inte);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!\n");}ListInsert(L,1,11);ListInsert(L,2,22);ListInsert(L,3,33);ListInsert(L,4,44);ListInsert(L,5,55);ListInsert(L,6,66);ListInsert(L,7,77);ListInsert(L,8,88);if(!Empty(L)){printf("插入成功!");}return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//在第i个位置插入元素e(带头结点)boolListInsert(LinkList&L,inti,inte){if(i<1){returnfalse;printf("插入失败!\n");}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}returnInsertNextNode(p,e);}//后插操作:在p节点之后插入元素eboolInsertNextNode(LNode*p,inte){if(p==NULL){returnfalse;}LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL){//内存分配失败returnfalse;}s->data=e;//用节点s保存数据元素es->next=p->next;p->next=s;returntrue;}前插操作//前插操作:在p节点之前插入元素eboolInsertPriorNode(LNode*p,inte){if(p==NULL){returnfalse;}LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL){//内存分配失败returnfalse;}s->next=p->next;p->next=s;//新节点s连在p之后s->data=p->data;p->data=e;returntrue;}boolInsertPriorNode(LNode*p,LNode*s){if(p==NULL){returnfalse;}LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL){//内存分配失败returnfalse;}s->next=p->next;p->next=s;//新节点s连在p之后s->data=p->data;p->data=e;returntrue;}按位序删除带头结点#include<stdio.h>#include<stdlib.h>typedefstructLNode{//定义单链表结构intdata;//每个节点存放一个数据structLNode*next;//指针指向下一个节点}LNode,*LinkList;boolInitList(LinkList&L);boolEmpty(LinkListL);boolListInsert(LinkList&L,inti,inte);boolListDelete(LinkList&L,inti,int&e);intmain(void){LinkListL;InitList(L);if(Empty(L)){printf("链表为空!\n");}ListInsert(L,1,11);ListInsert(L,2,22);ListInsert(L,3,33);ListInsert(L,4,44);ListInsert(L,5,55);ListInsert(L,6,66);ListInsert(L,7,77);ListInsert(L,8,88);if(!Empty(L)){printf("插入成功!");}inte=0;ListDelete(L,8,e);return0;}//初始化空的单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));//分配头结点if(L==NULL){//内存不足,分配失败returnfalse;}L->next=NULL;//头结点之后暂时没有节点returntrue;}//判断单链表是否为空(带头结点)boolEmpty(LinkListL){if(L->next==NULL){returntrue;}else{returnfalse;}}//在第i个位置插入元素e(带头结点)boolListInsert(LinkList&L,inti,inte){if(i<1){returnfalse;printf("插入失败!\n");}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL){//i值不合法returnfalse;printf("插入失败!\n");}LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;//将节点s连接到p之后returntrue;//插入成功}//按位序删除:带头结点boolListDelete(LinkList&L,inti,int&e){if(i<1){returnfalse;}LNode*p;//指针p指向当前扫描到的节点intj=0;//当前p指向的是第几个节点p=L;//L指向头结点,头结点是第0个节点(不存数据)while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL){//i值不合法returnfalse;}if(p->next==NULL){//第i-1个节点之后已无其他节点returnfalse;}LNode*q=p->next;//令p指向被删除节点e=q->data;//用e返回元素的值p->next=q->next;//将*q节点从链中“断开”free(q);returntrue;}注意事项:这里没有写查找功能,无法验证是否删除成功,留在下一节查找功能验证!//删除指定节点pboolDeleteNode(LNode*p){if(p==NULL){returnfalse;}LNode*q=p->next;//令q指向*p的后继节点p->data=p->next->data;//和后继节点交换数据域p->next=q->next;free(q);returntrue;}其中时间复杂度为O(1)
[文章] (20)王道数据结构-栈在括号匹配中的应用
基本思想遇到左括号就入栈,遇到右括号,就“消耗”一个左括号。扫描到右括号且栈空,右括号单身处理完所有括号后,栈非空,左括号单身实现代码#include<stdio.h>#defineMaxSize10//定义栈中元素最大个数typedefstruct{chardata[MaxSize];//静态数组存放栈中元素inttop;//栈顶指针}SqStack;voidInitStack(SqStack&S);boolStackEmpty(SqStackS);boolPush(SqStack&S,charx);boolPop(SqStack&S,char&x);charGetTop(SqStackS,char&x);boolBracketCheck(charstr[],intlength);intmain(void){charstr[]="[(())]";intlength=sizeof(str)-1;//括号匹配判断if(BracketCheck(str,length)){printf("括号匹配成功!\n");}charerr_str[]="[(()))]";length=sizeof(err_str)-1;if(!BracketCheck(err_str,length)){printf("括号匹配失败!\n");}return0;}//初始化栈voidInitStack(SqStack&S){S.top=-1;//初始化栈顶指针}//判断栈空boolStackEmpty(SqStackS){if(S.top==-1){//栈空returntrue;}else{returnfalse;}}//新元素入栈boolPush(SqStack&S,charx){if(S.top==MaxSize-1){//栈满报错returnfalse;}S.top=S.top+1;//指针加1S.data[S.top]=x;//新元素入栈returntrue;}//出栈操作boolPop(SqStack&S,char&x){if(S.top==-1){//栈空,报错returnfalse;}x=S.data[S.top];//栈顶元素先出栈S.top=S.top-1;//指针减1returntrue;}//读取栈顶元素charGetTop(SqStackS,char&x){if(S.top==-1){//栈空,报错returnfalse;}x=S.data[S.top];//x记录栈顶元素returnx;}boolBracketCheck(charstr[],intlength){SqStackS;InitStack(S);//初始化一个栈for(inti=0;i<length;i++){if(str[i]=='('||str[i]=='['||str[i]=='{'){Push(S,str[i]);//扫到左括号,入栈}else{if(StackEmpty(S)){//扫到有括号且当前栈空returnfalse;}chartopElem;Pop(S,topElem);//栈顶元素先出栈if(str[i]==')'&&topElem!='('){returnfalse;}if(str[i]==']'&&topElem!='['){returnfalse;}if(str[i]=='{'&&topElem!='{'){returnfalse;}}}returnStackEmpty(S);//检索完全部括号后,栈空说明匹配成功}扫描过程依次扫描所有字符,遇到左括号入栈,遇到右括号则弹出栈顶元素检查是否匹配。匹配失败的情况:①左括号单身②右括号单身③左右括号不匹配
2022-08-18 10:34 · 数据结构 / / 括号匹配
[文章] (18)王道数据结构-队列的定义和基本操作
基本结构只允许在一端进行插入,在另一端删除的线性表,先进入队列的元素先出队概念队头:允许删除的一端队尾:允许插入的一端操作InitQueue(&Q):初始化队列,构造一个空队列QDestroyQueue(&Q):销毁队列,销毁并释放队列Q所占用的内存空间EnQueue(&Q,x):入队,若队列Q未满,将x加入,使之成为新的队尾DeQueue(&Q,&x):出队,若队列Q非空,删除队头元素,并用x返回GetHead(Q,&x):读队头元素,若队列Q非空,则将队头元素赋给x其他操作QueueEmpty(Q):判断列空,若队列Q为空返回true,否则返回false普通队列#include<stdio.h>#defineMaxSize10//定义队列中元素最大个数typedefstruct{intdata[MaxSize];//用静态数组存放队列元素intfront,rear;//队头指针和队尾指针}SqQueue;voidInitQueue(SqQueue&Q);boolQueueEmpty(SqQueueQ);boolEnQueue(SqQueue&Q,intx);boolDeQueue(SqQueue&Q,int&x);boolGetHead(SqQueueQ,int&x);intmain(void){SqQueueQ;intx;InitQueue(Q);EnQueue(Q,1);EnQueue(Q,2);EnQueue(Q,3);EnQueue(Q,4);EnQueue(Q,5);EnQueue(Q,6);GetHead(Q,x);printf("x=%d\n",x);DeQueue(Q,x);DeQueue(Q,x);DeQueue(Q,x);DeQueue(Q,x);printf("x=%d\n",x);return0;}//初始化队列voidInitQueue(SqQueue&Q){//初始时,队头和队尾指针指向0Q.rear=Q.front=0;}//判断队列是否为空boolQueueEmpty(SqQueueQ){if(Q.rear==Q.front){//队空条件returntrue;}else{returnfalse;}}//入队boolEnQueue(SqQueue&Q,intx){if(Q.rear==MaxSize){//队满不入队returnfalse;}Q.data[Q.rear]=x;//将x插入队尾Q.rear=Q.rear+1;//队尾指针后移returntrue;}//出队boolDeQueue(SqQueue&Q,int&x){if(Q.rear==Q.front){//队空不出队returnfalse;}x=Q.data[Q.front];Q.front=Q.front+1;}//获取队头元素boolGetHead(SqQueueQ,int&x){if(Q.rear==Q.front){//队空不出队returnfalse;}x=Q.data[Q.front];returntrue;}循环队列#include<stdio.h>#defineMaxSize10//定义队列中元素最大个数typedefstruct{intdata[MaxSize];//用静态数组存放队列元素intfront,rear;//队头指针和队尾指针}SqQueue;voidInitQueue(SqQueue&Q);boolQueueEmpty(SqQueueQ);boolEnQueue(SqQueue&Q,intx);boolDeQueue(SqQueue&Q,int&x);boolGetHead(SqQueueQ,int&x);intmain(void){SqQueueQ;intx;InitQueue(Q);EnQueue(Q,1);EnQueue(Q,2);EnQueue(Q,3);EnQueue(Q,4);EnQueue(Q,5);EnQueue(Q,6);EnQueue(Q,7);EnQueue(Q,8);EnQueue(Q,9);EnQueue(Q,10);EnQueue(Q,11);EnQueue(Q,12);GetHead(Q,x);printf("x=%d\n",x);DeQueue(Q,x);DeQueue(Q,x);DeQueue(Q,x);DeQueue(Q,x);printf("x=%d\n",x);return0;}//初始化队列voidInitQueue(SqQueue&Q){//初始时,队头和队尾指针指向0Q.rear=Q.front=0;}//判断队列是否为空boolQueueEmpty(SqQueueQ){if(Q.rear==Q.front){//队空条件returntrue;}else{returnfalse;}}//入队boolEnQueue(SqQueue&Q,intx){if(Q.rear==MaxSize){//队满不入队returnfalse;}Q.data[Q.rear]=x;//将x插入队尾Q.rear=(Q.rear+1)%MaxSize;//队尾指针后移returntrue;}//出队boolDeQueue(SqQueue&Q,int&x){if(Q.rear==Q.front){//队空不出队returnfalse;}x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;}//获取队头元素boolGetHead(SqQueueQ,int&x){if(Q.rear==Q.front){//队空不出队returnfalse;}x=Q.data[Q.front];returntrue;}
2022-08-18 10:30 · 数据结构 / 队列
[文章] (03)王道数据结构-线性表定义和基本操作
线性表的定义**定义:**线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。若用L命名线性表,则其一般表示为几个概念:(1)ai是线性表中的“第i个”元素线性表中的位序(2)a1是表头元素,an是表尾元素(3)除了第一个元素外,每个元素有且仅有一个直接前驱;除了最后一个元素外,每个元素有且只有一个直接后继线性表中的基本操作:InitList(&L):初始化表。构造一个空的线性表L,分配内存空间Destory(&L):销毁操作。销毁线性表,并释放线性表L所占内存空间ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素eListDelete(&L,i,&e):删除操作。删除表L中的第i个位置的元素,并用e返回删除元素的值LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值其他操作:Lengt(L):求表长。返回线性表L的长度,即L中数据元素的个数PrintList(L):输出操作。按先后顺序输出线性表L的所有元素值Empty:判空操作。若L为空表,则返回true,否则返回false
2022-08-05 10:35 · 王道 / 数据结构 / 线性表
  • 1