02.05

1.单链表

main

#include "1list_head.h"
int main(int argc, const char *argv[])
{
//创建链表之前链表为空Linklist head=NULL;int n;datatype element;printf("please enter n:");scanf("%d",&n);for(int i=0;i<n;i++){printf("please enter %d element:",i+1);scanf("%d",&element);//11head=insert_rear(element,head);		}Output(head);//头删head=delete_head(head);Output(head);//尾删		head=delete_rear(head);Output(head);//按位置插入int pos;printf("please enter insert pos:");scanf("%d",&pos);printf("please enter insert element:");scanf("%d",&element);head=insert_pos(pos,element,head);Output(head);//按位置删除printf("please enter delete pos:");scanf("%d",&pos);head=delete_pos(pos,head);Output(head);	return 0;
}

list.c

#include "1list_head.h"
//创建链表节点
Linklist create_node()
{Linklist s=(Linklist)malloc(sizeof(struct Node));if(NULL==s)return NULL;//s节点的数据域清0s->data=0;s->next=NULL;return s;
}
//尾插
Linklist insert_rear(datatype element,Linklist head)
{Linklist s=create_node();if(NULL==s)return head;s->data=element;if(NULL ==head){head=s;}else {Linklist p=head;while(p->next!=NULL){p=p->next;}p->next=s;}return head;}
//头插
Linklist insert_head(datatype element,Linklist head)
{Linklist s=create_node();if(NULL==s)return head;s->data=element;if(NULL==head){head=s;}else {s->next=head;head=s;}return head;
}
//尾删
Linklist delete_rear(Linklist head)
{if(NULL ==head)return head;if(NULL ==head->next){free(head);head=NULL;}else {Linklist del=head;while(del->next->next!=NULL){del=del->next;}free(del->next);del->next=NULL;}return head;
}
//头删
Linklist delete_head(Linklist head)
{if(NULL==head){return head;}else if(head->next==NULL){Linklist p=head;free(p);p=NULL;}else {Linklist del=head;head=head->next;free(del);del=NULL;}return head;
}
//按位置插入
Linklist insert_pos(int pos,datatype element,Linklist head)
{if( pos<1 || pos>Length(head)+1)return head;if(NULL==head || pos==1)//判断是否只有一个节点head=insert_head(element,head);else {Linklist p=head;for(int i=1;i<pos-1;i++){p=p->next;}Linklist s=create_node();if(NULL==s)return head;s->data=element;s->next=p->next;p->next=s;}return head;}
//按位置删除
Linklist delete_pos(int pos,Linklist head)
{if(NULL==head || pos<1 || pos>Length(head)){return head;}if(head->next==NULL ||pos==1)//只有一个节点{head=delete_head(head);}else //存在多个节点 >=2{Linklist p=head;for(int i=1;i<pos-1;i++){p=p->next;}Linklist q=p->next;p->next=q->next;free(q);q=NULL;}return head;
}
//遍历
int Output(Linklist head)
{//1.判断链表为空if(NULL==head)return -1;//2,循环输出Linklist p=head;while(p!=NULL){printf("%d\t",p->data);p=p->next;//后移}puts("");return 0;
}
//计算长度
int Length(Linklist head)
{int count=0;Linklist p=head;while(p!=NULL){count++;p=p->next;}return count;
}

head

#ifndef __HEAD_H__
#define __HEAD_H__
#include "myhead.h"
typedef int datatype;
//创建节点结构体
typedef struct Node
{//数据域：存储数据元素datatype data;//指针域：存储下一个节点的地址struct Node *next;
}*Linklist;//创建链表节点
Linklist create_node();//尾插
Linklist insert_rear(datatype element,Linklist head);
//头插
Linklist insert_head(datatype element,Linklist head);
//尾删
Linklist delete_rear(Linklist head);
//头删
Linklist delete_head(Linklist head);
//按位置插入
Linklist insert_pos(int pos,datatype element,Linklist head);
//按位置删除
Linklist delete_pos(int pos,Linklist head);
//遍历
int Output(Linklist head);
//计算长度
int Length(Linklist head);#endif

2.双向

main

#include "doublelink_head.h"
int main(int argc, const char *argv[])
{Doublelink head=NULL;int n;datatype element;printf("please enter n:");scanf("%d",&n);for(int i=0;i<n;i++){printf("please enter %d element:",i+1);scanf("%s",element);head=doublelink_insert_rear(element,head);}Output(head);//头删head=delete_head(head);Output(head);//尾删head=delete_rear(head);Output(head);return 0;
}

list.c

#include "doublelink_head.h"
//创建节点
Doublelink create_node()
{Doublelink s=(Doublelink)malloc(sizeof(struct Node));if(NULL==s)return NULL;strcpy(s->data,"");s->next=s->priv=NULL;return s;
}
//头插
Doublelink double_insert_head(datatype element,Doublelink head)
{Doublelink s=create_node();if(s==NULL)return head;strcpy(s->data,element);if(NULL ==head)head=s;else{s->next=head;head->priv=s;head=s;}return head;}
//遍历
int Output(Doublelink head)
{if(NULL ==head)return -1;//正向puts("正向遍历\n");Doublelink p=head;while(p->next!=NULL){printf("%s\t",p->data);p=p->next;}printf("%s\t",p->data);//逆向puts("\n逆向遍历");while(p!=NULL){printf("%s\t",p->data);p=p->priv;	}puts("");return 0;
}//尾插
Doublelink doublelink_insert_rear(datatype element,Doublelink head)
{Doublelink s=create_node();if(s==NULL)return head;strcpy(s->data,element);if(NULL ==head)head=s;else{Doublelink p=head;while(p->next!=NULL){p=p->next;}p->next=s;s->priv=p;}return head;}
//头删
Doublelink delete_head(Doublelink head)
{if(NULL==head)return head;Doublelink q=head;head=head->next;if(head!=NULL)head->priv=NULL;free(q);q=NULL;return head;
}
//尾删
Doublelink delete_rear(Doublelink head)
{if(NULL ==head)return head;if(head->next==NULL){free(head);head=NULL;}else //>=2{Doublelink p=head;while(p->next!=NULL){p=p->next;}p->priv->next=NULL;free(p);p=NULL;}return head;
}

head.h

#ifndef __DOUBLELINK_HEAD_H__
#define __DOUBLELINK_HEAD_H__
#include "myhead.h"typedef char datatype[30];//datatype-->char [30]
//定义结构体
typedef struct Node
{//数据域：存储数据元素datatype data;//指针域：存储下一个节点的地址struct Node *next;//指针域：存储上一个节点的地址struct Node *priv;
}*Doublelink;int Output(Doublelink head);
Doublelink double_insert_head(datatype element,Doublelink head);
Doublelink create_node();
Doublelink doublelink_insert_rear(datatype element,Doublelink head);
Doublelink delete_head(Doublelink head);
Doublelink delete_rear(Doublelink head);
#endif