当前位置：首页 > java >正文

数据结构：单向链表的逆置；双向循环链表；栈，输出栈，销毁栈；顺序表和链表的区别和优缺点；0825

java 2025/8/26 22:09:50

单向链表的逆置

代码如下

//12.单向链表 逆置
void reverse_link(link_p H)
{//判断入参为空if(H==NULL) //判断 入参为空{printf("入参为空，无法清除单向链表，请检查\n");return ;}//判断单向链表为空if(empty_link(H)){printf("单向链表为空，无法输出，请检查\n");return ;}//H 1 2 3 4 5 6//S结点 保留2 3 4 5 6结点link_p S=H->next->next;H->next->next=NULL;//H 1//S 2 3 4 5 6//H 2 1//S 3 4 5 6link_p prev;while(S!=NULL){prev=S->next;//prev 保留S 的下一个位置//头插结点的操作S->next=H->next;//S被头插到 H链表H->next=S;//循环步长S=prev;}
}

双向循环链表

1.创建双向循环链表

2.创建新结点

3. 判断双向循环链表为空

4.头插双向链表

5.头删双向链表

6.输出双向链表

10.尾删

8.按位置插入双向链表

9.按位置删除双向链表

代码如下

looplink.c

#include"loop.h"//1.创建 双向循环链表
node_p creat_link()
{node_p H=(node_p)malloc(sizeof(node));if(H==NULL)//申请失败{printf("申请失败\n");return NULL;}H->next=H;H->prev=H;H->data=0;return H;
}
//2.创建 新结点
node_p creat_node(int V)
{node_p N=(node_p)malloc(sizeof(node));if(N==NULL)//申请失败{printf("申请失败\n");return NULL;}N->next=NULL;N->prev=NULL;N->data=V;return N;
}
//3.判断 双向循环链表为空
int empty(node_p H)
{if(H==NULL)//入参为空{printf("入参为空\n");return -1;}return H->next==H;
}
//4.头插 双向循环链表
void insert_head(node_p H,int V)
{if(H==NULL)//入参为空{printf("入参为空\n");return;}//新建结点node_p N=creat_node(V);//头插 结点链接N->next=H->next;//1N->prev=H;//2H->next=N;//2N->next->prev=N;//4 双向循环 不需要判断了 哈哈
}	
//6.输出 双向循环链表
void show(node_p H)
{if(H==NULL)//入参为空{printf("入参为空\n");return;}if(empty(H)){printf("链表为空\n");return;}//S结点 循环输出node_p S=H->next;printf("H ");do{printf("%d ",S->data);S=S->next;}while(S!=H);printf("H\n");
}
//8.尾删 双向循环链表
void del_tail(node_p H)
{if(H==NULL)//入参为空{printf("入参为空\n");return;}if(empty(H)){printf("链表为空\n");return;}//D结点 保留尾结点node_p D=H->prev;//尾删 指针链接H->prev=D->prev;D->prev->next=D->next;//释放空间free(D);
}
//9.按位置插入 双向循环链表
void insert_pos(node_p H,int pos,int V)
{       if(H==NULL)//入参为空{printf("入参为空\n");return;}if(pos<=0){printf("插入的位置不合理\n");return;}//S找到pos-1位置node_p S=H;int i;for(int i=0;i<pos-1;i++,S=S->next){if(S->next==H){printf("插入的位置不合理\n");return;}}//插入新结点node_p N=creat_node(V);//按位置插入 指针链接N->next=S->next;//1N->prev=S;//2N->next->prev=N;//3S->next=N;//4
}
//10.按位置删除 双向循环链表
void del_pos(node_p H,int pos)
{if(H==NULL)//入参为空{printf("入参为空\n");return;}if(pos<=0){printf("插入的位置不合理\n");return;}//D找到pos位置node_p D=H;int i;for(int i=0;i<pos;i++,D=D->next){if(D->next==H){printf("删除的位置不合理\n");return;}}//按位置删除 指针链接D->prev->next=D->next;D->next->prev=D->prev;//释放空间free(D);
}

loopmain.c

#include"loop.h"
int main()
{//1.创建 双向循环链表node_p H=creat_link();int pos;int V;//4.头插 双向循环链表for(int i=99;i>95;i--){insert_head(H,i);}//6.输出 双向循环链表show(H);//8.尾删 双向循环链表del_tail(H);//输出show(H);//9.按位置插入 双向循环链表printf("按位置插入 双向循环链表\n");printf("插入位置:");scanf("%d",&pos);printf("插入值:");scanf("%d",&V);insert_pos(H,pos,V);//输出show(H);//10.按位置删除 双向循环链表printf("按位置删除 双向循环链表\n");printf("删除位置:");scanf("%d",&pos);del_pos(H,pos);//输出show(H);return 0;
}

loop.h

#ifndef __LOOP_H_
#define __LOOP_H_ 1#include<stdio.h>
#include<stdlib.h>//双向循环链表 结点的结构体
typedef struct node
{struct node *prev;struct node *next;int data;
}node,*node_p;
//1.创建 双向循环链表
node_p creat_link();
//2.创建 新结点
node_p creat_node(int);
//3.判断 双向循环链表为空
int empty(node_p);
//4.头插 双向循环链表
void insert_head(node_p,int);
//6.输出 双向循环链表
void show(node_p);
//8.尾删 双向循环链表
void del_tail(node_p);
//9.按位置插入 双向循环链表
void insert_pos(node_p,int,int);
//10.按位置删除 双向循环链表
void del_pos(node_p,int);#endif

栈

1.新建栈

2.数据压入栈

3.判空

4.判满

5.数据弹出栈

6.输出栈

7.销毁栈

代码如下

stack.c

#include"stack.h"
//1.新建栈
stack_p creat()
{stack_p S=(stack_p)malloc(sizeof(struct stack));if(S==NULL)//申请空间失败{printf("申请空间失败\n");return NULL;}S->top=-1;//top初始值-1bzero(S,sizeof(S->data));//置0 S->datareturn S;
}
//2.数据 压入栈
void push_stack(stack_p S,int V)
{if(S==NULL)//传参为空{printf("传参为空\n");return;}if(full(S)){printf("栈满,不可压栈\n");return;}//压栈//先加再压S->data[++S->top]=V;//运算符优先级 回去看看嘛
}
//3.判空
int empty(stack_p S)
{if(S==NULL)//传参为空{printf("传参为空\n");return -1;}return S->top==-1;
}
//4.判满
int full(stack_p S)
{       if(S==NULL)//传参为空{printf("传参为空\n");return -1;}return S->top==MAX-1;
}
//5.数据 弹出栈
//返回值 元素的值
int pop_stack(stack_p S)
{       if(S==NULL)//传参为空{printf("传参为空,无法进行弹栈\n");return -1;}if(empty(S))//判断栈为空{printf("栈为空,不能进行弹栈\n");return -2;}//弹栈//先弹后减return S->data[S->top--];
}
//6.输出栈
void show(stack_p S)
{       if(S==NULL)//传参为空{printf("传参为空,无法进行输出\n");return ;}if(empty(S))//判断栈为空{printf("栈为空,不能进行输出\n");return;}//输出栈for(int i=0;i<=S->top;i++){printf("%d ",S->data[i]);}putchar(10);
}
//7.销毁栈
void free_stack(stack_p S)
{if(S==NULL)//传参为空{printf("传参为空\n");return ;}while(S->top!=-1){pop_stack(S);}free(S);
}

main.c

#include"stack.h"
int main()
{//1.新建栈stack_p S= creat();//2.数据 压入栈for(int i=99;i>95;i--){push_stack(S,i);}//5.数据 弹出栈printf("弹栈,弹出的值是%d\n",pop_stack(S));//6.输出栈show(S);//7.销毁栈free_stack(S);return 0;
}

stack.h

#ifndef __STACK_H_
#define __STACK_H_ 1#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define MAX 5typedef struct stack
{int data[MAX];int top;
}seq_stack,*stack_p;//1.新建栈
stack_p creat();
//2.数据 压入栈
void push_stack(stack_p,int);
//3.判空
int empty(stack_p);
//4.判满
int full(stack_p);
//5.数据 弹出栈
int pop_stack(stack_p);
//6.输出栈
void show(stack_p);
//7.销毁栈
void free_stack(stack_p);#endif

运行情况