双向链表的插入、删除、按位置增删改查、栈和队列区别、什么是内存泄漏

2024年2月4日
1.请编程实现双向链表的头插，头删、尾插、尾删

头文件：

#ifndef __HEAD_H__
#define __HEAD_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int datatype;
enum{FALSE=-1,SUCCSE};
typedef struct Node
{datatype data;struct Node *next;struct Node *prev;
}*Doublelist;Doublelist create();
Doublelist insert_head(Doublelist head,datatype element);
Doublelist insert_rear(Doublelist head,datatype element);
void output(Doublelist head);
Doublelist delete_head(Doublelist head);
Doublelist delete_rear(Doublelist head);#endif

主函数：

#include"head.h"
int main(int argc, const char *argv[])
{Doublelist head=NULL;int n;printf("please enter n:");scanf("%d",&n);datatype element;for(int i=0;i<n;i++){printf("please enter %d element:",i+1);scanf("%d",&element);head=insert_head(head,element);//head=insert_rear(head,element);}output(head);puts("");head=delete_head(head);output(head);puts("");head=delete_rear(head);output(head);return 0;
}

自定义函数：

#include"head.h"
/** function:    节点创建* @param [ in] * @param [out] 成功返回首地址，失败返回空* @return      */
Doublelist create()
{Doublelist s=(Doublelist)malloc(sizeof(struct Node));if(s==NULL)return NULL;s->data=0;s->next=s->prev=NULL;return s;
}
/** function:    头插* @param [ in] 头　插入元素* @param [out] 头* @return      */
Doublelist insert_head(Doublelist head,datatype element)
{Doublelist s=create();s->data=element;if(NULL==head)head=s;else{s->next=head;head->prev=s;head=s;}return head;
}
/** function:    尾插* @param [ in] 头　插入元素* @param [out] 头* @return      */
Doublelist insert_rear(Doublelist head,datatype element)
{Doublelist s=create();s->data=element;if(NULL==head)head=s;else{Doublelist p=head;while(p->next)p=p->next;p->next=s;s->prev=p;}return head;
}
/** function:    遍历输出* @param [ in] 头* @param [out] * @return      */
void output(Doublelist head)
{if(head==NULL){puts("empty");return;}Doublelist p=head;while(p){printf("%-5d",p->data);p=p->next;}
}
/** function:    头删* @param [ in] 头* @param [out] 头* @return      */
Doublelist delete_head(Doublelist head)
{if(head==NULL)return NULL;if(head->next==NULL){free(head);head=NULL;return NULL;}Doublelist del=head;head=head->next;free(del);head->prev=NULL;del=NULL;return head;
}
/** function:    尾删* @param [ in] 头* @param [out] 头* @return      */
Doublelist delete_rear(Doublelist head)
{if(NULL==head)return head;if(head->next==NULL){free(head);head=NULL;return NULL;}Doublelist p=head;while(p->next)p=p->next;Doublelist del=p;p->prev->next=NULL;free(del);del=NULL;return head;
}

头插、头删、尾删：

尾插、头删、尾删：

⒉请编程实现双向链表按任意位置插入、删除、修改、查找

头文件：

#ifndef __HEAD_H__
#define __HEAD_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int datatype;
enum{FALSE=-1,SUCCSE};
typedef struct Node
{datatype data;struct Node *next;struct Node *prev;
}*Doublelist;Doublelist create();
Doublelist insert_head(Doublelist head,datatype element);
Doublelist insert_rear(Doublelist head,datatype element);
void output(Doublelist head);
Doublelist delete_head(Doublelist head);
Doublelist delete_rear(Doublelist head);
Doublelist insert_pos(Doublelist head,int pos,datatype element);
Doublelist delete_pos(Doublelist head,int pos);
void find_pos(Doublelist head,int pos);
int revise_pos(Doublelist head,int pos,datatype element);#endif

主函数：

#include"head.h"
int main(int argc, const char *argv[])
{Doublelist head=NULL;int n;printf("please enter n:");scanf("%d",&n);datatype element;for(int i=0;i<n;i++){printf("please enter %d element:",i+1);scanf("%d",&element);//head=insert_head(head,element);head=insert_rear(head,element);}output(head);puts("");
/*	head=delete_head(head);output(head);puts("");head=delete_rear(head);output(head);
*/	int pos;
/*	printf("please enter pos:");scanf("%d",&pos);printf("please enter insert element:");scanf("%d",&element);head=insert_pos(head,pos,element);output(head);printf("please enter pos:");scanf("%d",&pos);head=delete_pos(head,pos);output(head);
*/	printf("please enter pos:");scanf("%d",&pos);find_pos(head,pos);printf("please enter pos:");scanf("%d",&pos);printf("please enter insert element:");scanf("%d",&element);int num=revise_pos(head,pos,element);if(num==-1)puts("ERROR");elseoutput(head);return 0;
}

自定义函数：

#include"head.h"
/** function:    节点创建* @param [ in] * @param [out] 成功返回首地址，失败返回空* @return      */
Doublelist create()
{Doublelist s=(Doublelist)malloc(sizeof(struct Node));if(s==NULL)return NULL;s->data=0;s->next=s->prev=NULL;return s;
}
/** function:    头插* @param [ in] 头　插入元素* @param [out] 头* @return      */
Doublelist insert_head(Doublelist head,datatype element)
{Doublelist s=create();s->data=element;if(NULL==head)head=s;else{s->next=head;head->prev=s;head=s;}return head;
}
/** function:    尾插* @param [ in] 头　插入元素* @param [out] 头* @return      */
Doublelist insert_rear(Doublelist head,datatype element)
{Doublelist s=create();s->data=element;if(NULL==head)head=s;else{Doublelist p=head;while(p->next)p=p->next;p->next=s;s->prev=p;}return head;
}
/** function:    遍历输出* @param [ in] ｔｏｕ* @param [out] * @return      */
void output(Doublelist head)
{if(head==NULL){puts("empty");return;}Doublelist p=head;while(p){printf("%-5d",p->data);p=p->next;}
}
/** function:    头删* @param [ in] 头* @param [out] 头* @return      */
Doublelist delete_head(Doublelist head)
{if(head==NULL)return NULL;if(head->next==NULL){free(head);head=NULL;return NULL;}Doublelist del=head;head=head->next;free(del);head->prev=NULL;del=NULL;return head;
}
/** function:    尾删* @param [ in] 头* @param [out] 头* @return      */
Doublelist delete_rear(Doublelist head)
{if(NULL==head)return head;if(head->next==NULL){free(head);head=NULL;return NULL;}Doublelist p=head;while(p->next)p=p->next;Doublelist del=p;p->prev->next=NULL;free(del);del=NULL;return head;
}
/** function:    计算长度* @param [ in] 头* @param [out] 长度* @return      */
int lengh(Doublelist head)
{int len=0;while(head){len++;head=head->next;}return len;
}
/** function:    按任意位置插入* @param [ in] 头　位置　插入元素* @param [out] 头* @return      */
Doublelist insert_pos(Doublelist head,int pos,datatype element)
{if(NULL==head || pos<1 || pos>lengh(head)+1){puts("POS ERROR OR EMPTY");return head;}if(pos==1){head=insert_head(head,element);return head;}else if(pos==lengh(head)+1){head=insert_rear(head,element);return head;}Doublelist s=create();s->data=element;Doublelist p=head;for(int i=1;i<pos-1;i++)p=p->next;s->next=p->next;p->next->prev=s;s->prev=p;p->next=s;return head;
}
/** function:    任意位置删除* @param [ in] 头　位置* @param [out] 头* @return      */
Doublelist delete_pos(Doublelist head,int pos)
{if(NULL==head || pos<1 || pos>lengh(head)){puts("POS ERROR OR EMPTY");return head;}if(pos==1)head=delete_head(head);else if(pos==lengh(head))head=delete_rear(head);else{Doublelist p=head;for(int i=1;i<pos-1;i++)p=p->next;Doublelist del=p->next;p->next=del->next;del->next->prev=p;free(del);del=NULL;}return head;
}
/** function:    任意位置查找* @param [ in] 头　位置* @param [out] * @return      */
void find_pos(Doublelist head,int pos)
{if(NULL==head || pos<1 || pos>lengh(head)){puts("POS ERROR OR EMPTY");return;}Doublelist p=head;for(int i=1;i<pos;i++)p=p->next;printf("The pos element is %d\n",p->data);
}
/** function:    任意位置修改* @param [ in] 头　位置　修改后的元素* @param [out] 成功返回０，失败返回－１* @return      */
int revise_pos(Doublelist head,int pos,datatype element)
{if(NULL==head || pos<1 || pos>lengh(head)){puts("POS ERROR OR EMPTY");return FALSE;}Doublelist p=head;for(int i=1;i<pos;i++)p=p->next;p->data=element;return SUCCSE;
}

任意位置插入：

任意位置删除：

任意位置查找：

任意位置修改：

3.请简述栈和队列的区别?

1、栈和队列的出入方式不同：栈是先进后出，队列是先进先出。

2、栈和队列的实现时操作位置不同：栈是出入在一端，后入先出，队列是出入在两端先进先出。

4.请简述什么内存泄露?

程序员释放在堆区申请的内存时，指针未指向释放内存的首地址，导致前部分内存未释放，且没有指针指向导致内存泄漏。