数据结构之链表
思维导图
练习
头文件
#ifndef __HEAD_H__
#define __HEAD_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum
{FALSE=-1,SUCCESS
};
typedef int datatype;
//定义节点结构体
//节点：数据域 指针域typedef struct Node
{//数据域：存储数据元素datatype data;//指针域：存储指针struct Node *next;
}*Linklist;Linklist creat();
Linklist insert_head(Linklist head,datatype element);
void output(Linklist head);
Linklist insert_rear(Linklist head,datatype element);
Linklist delete_head(Linklist head);
Linklist delete_rear(Linklist head);
Linklist insert_pos(Linklist head,int pos,datatype element);
Linklist delete_pos(Linklist head,int pos);
Linklist change_pos(Linklist head,int pos,datatype element);
void search_pos(Linklist head,int pos);
int search_element(Linklist head,datatype element);
Linklist rev(Linklist head);
int search_transpos(Linklist head,int pos);
Linklist chang_element(Linklist head,datatype key,datatype element);
Linklist delete_element(Linklist head,datatype key);
void Bubble(Linklist head);
void Select(Linklist head);
Linklist free_space(Linklist head);#endif
自定义函数
#include "head.h"
/** function: 创建新节点* @param [ in] * @param [out] * @return */
Linklist creat()
{Linklist s=(Linklist)malloc(sizeof(struct Node));if(NULL==s)return NULL;//成功则初始化s->data=0;s->next=NULL;return s;
}
/** function: 头插入* @param [ in] * @param [out] * @return * 如果形参头指针发生指向的改变，则必须返回*/
Linklist insert_head(Linklist head,datatype element)
{//创建新节点sLinklist s=creat();s->data=element;//判断链表是否为空if(head==NULL){head=s;}else{s->next=head;head=s;}return head;
}/** function: 遍历输出* @param [ in] * @param [out] * @return */
void output(Linklist head)
{if(NULL==head)return;Linklist p=head;while(p!=NULL)//也可以是while(p){printf("%-5d",p->data);p=p->next;}puts("");
}/** function: 尾插入* @param [ in] * @param [out] * @return */Linklist insert_rear(Linklist head,datatype element)
{Linklist s=creat();s->data=element;Linklist p=head;if(NULL==head)head=s;else{while(p->next!=NULL){p=p->next;}p->next=s;}return head;
}
/** function: 头删* @param [ in] * @param [out] * @return */
Linklist delete_head(Linklist head)
{if(head==NULL)return NULL;else{Linklist del=head;head=head->next;free(del); del=NULL;}return head;
}
/** function: 尾删* @param [ in] * @param [out] * @return */
Linklist delete_rear(Linklist head)
{if(head==NULL)return NULL;else if(head->next==NULL){free(head);head==NULL;return head;}else{Linklist del=head;while(del->next->next!=NULL){del=del->next;}free(del->next);del->next=NULL;}return head;
}
/** function: 计算链表长度* @param [ in] * @param [out] * @return */
int length(Linklist head)
{int len=0;while(head!=NULL){head=head->next;len++;}return len;
}/** function: 按任意位置插入* @param [ in] * @param [out] * @return */
Linklist insert_pos(Linklist head,int pos,datatype element)
{if(pos<0||pos>length(head)+1)return head;Linklist s=creat();s->data=element;if(pos==1){head=insert_head(head,element);return head;}Linklist p=head;for(int i=1;i<pos-1;i++) {p=p->next; } s->next=p->next; p->next=s; return head;
}
/** function: 按任意位置删除* @param [ in] * @param [out] * @return */
Linklist delete_pos(Linklist head,int pos)
{if(pos<0||pos>length(head)+1)return head;if(pos==1){head=delete_head(head);return head;}Linklist p=head;for(int i=1;i<pos-1;i++) {p=p->next; } Linklist s=p->next; p->next=s->next;free(s);s=NULL;return head;
}
/** function: 按任意位置修改* @param [ in] * @param [out] * @return */
Linklist change_pos(Linklist head,int pos,datatype element)
{if(pos<0||pos>length(head)+1)return head;if(pos==1){head->data=element;return head;}Linklist p=head;for(int i=1;i<pos;i++) {p=p->next; } p->data=element;return head;
}
/** function: 按任意位置查找* @param [ in] * @param [out] * @return */
void search_pos(Linklist head,int pos)
{ if(pos<0||pos>length(head))return;if(head==NULL)return;Linklist p=head;for(int i=1;i<pos;i++){p=p->next;}printf("%d\n",p->data);
}/** function: 按任意元素查找* @param [ in] * @param [out] * @return */
int search_element(Linklist head,datatype element)
{if(head==NULL)return FALSE;Linklist p=head;int pos=0;while(p){pos++;if(p->data==element){return pos;}p=p->next;}if(pos==0)return FALSE;
}
/** function: 逆置链表* @param [ in] * @param [out] * @return */
Linklist rev(Linklist head)
{if(head==NULL)return head;Linklist p=head->next;head->next=NULL;Linklist t=p;while(p){t=p;p=p->next;t->next=head;head=t;}return head;
}/** function: 查找倒数第ｎ个值* @param [ in] * @param [out] * @return */
int search_transpos(Linklist head,int pos)
{if(head==NULL)return FALSE;if(pos<0||pos>length(head))return FALSE;Linklist p=head;Linklist q=head;for(int i=0;i<pos;i++){p=p->next;}while(p){p=p->next;q=q->next;}return q->data;
}
/** function: 按任意元素修改* @param [ in] * @param [out] * @return */
Linklist chang_element(Linklist head,datatype key,datatype element)
{if(head==NULL)return NULL;int pos=search_element(head,key);head=change_pos(head,pos,element);return head;
}/** function: 按任意元素删除* @param [ in] * @param [out] * @return */
Linklist delete_element(Linklist head,datatype key)
{if(head==NULL)return NULL;int pos=search_element(head,key);head=delete_pos(head,pos);return head;
}
/** function: 冒泡排序(从小到大)* @param [ in] * @param [out] * @return */
void Bubble(Linklist head)
{if(head==NULL)return;for(int i=0;i<length(head)-1;i++){Linklist p=head;for(int j=0;j<length(head)-i-1;j++){if(p->data >p->next->data){datatype temp=p->data;p->data=p->next->data;p->next->data=temp;}p=p->next;}}
}/** function: 简单选择排序(从大到小)* @param [ in] * @param [out] * @return */
void Select(Linklist head)
{if(head==NULL)return;Linklist p=head;for(int i=0;i<length(head)-1;i++){datatype max=p->data;Linklist q=p->next;for(int j=i+1;j<length(head);j++){if(p->data<q->data){max=q->data;}q=q->next;}chang_element(head,max,p->data);p->data=max;p=p->next;}
}
/** function: 释放空间* @param [ in] * @param [out] * @return */
Linklist free_space(Linklist head)
{if(head==NULL)return NULL;for(int i=0;i<length(head);i++){Linklist s=head;head=head->next;free(s);s=NULL;}return head;
}
主函数
#include "head.h"
int main(int argc, const char *argv[])
{//定义单链表的头指针Linklist head=NULL;int n;//插入的值datatype element;printf("请输入链表长度\n");scanf("%d",&n);for(int i=0;i<n;i++){printf("请输入第%d个值:",i+1);scanf("%d",&element);//head=insert_head(head,element);head=insert_rear(head,element);}
// head=delete_head(head);
// head=delete_rear(head);
// 按位置插入int pos;
/*printf("请输入要插入的位置");scanf("%d",&pos);printf("请输入要插入的值");scanf("%d",&element);head=insert_pos(head,pos,element);output(head);printf("请输入要删除的位置");scanf("%d",&pos);head=delete_pos(head,pos);output(head);
*/
/*printf("请输入要修改的位置");scanf("%d",&pos);printf("请输入要修改后的值");scanf("%d",&element);head=change_pos(head,pos,element);output(head);printf("请输入要查找的位置");scanf("%d",&pos);search_pos(head,pos);
*/printf("请输入要查找的值");scanf("%d",&element);pos=search_element(head,element);printf("%d\n",pos);
// head=rev(head);output(head);/* printf("请输入要查找倒数第几个");scanf("%d",&pos);int num=search_transpos(head,pos);printf("倒数第%d个的值为:%d\n",pos,num);
*/int key;printf("请输入要修改的值");scanf("%d",&key);printf("请输入修改后的值");scanf("%d",&element);head=chang_element(head,key,element);output(head);printf("请输入要删除的值");scanf("%d",&element);head=delete_element(head,element);output(head);Bubble(head);output(head);Select(head);output(head);free_space(head);return 0;
}
效果图
