数据结构---链表的基本操作
- 头插法
- 遍历链表
- 尾插法
- 头删法
- 尾删法
- 按位置插入数据
- 按位置删除数据
- 直接插入排序
- 链表翻转
- 快慢指针
linklist.c
#include <stdio.h>
#include <stdlib.h>
#include "./linklist.h"linklist* create_linklist(void)
{linklist* head = (linklist*)malloc(sizeof(linklist)); if(NULL == head){printf("头结点申请失败!\n");return NULL;}head->text.len = 0;head->next = NULL;return head;
}
//头插法
int insertHead_linlist(linklist *head,dataType num)
{//创建一个新结点linklist* temp = (linklist*)malloc(sizeof(linklist));if(NULL == temp){printf("创建失败!\n");return 0;}temp->text.data = num;temp->next = NULL;//头插法插入数据temp->next = head->next;head->next = temp;return 0;
}//遍历链表void show_linklist(linklist* head)
{linklist *p = head;while(p->next != NULL){p = p->next;printf("%d ",p->text.data);}printf("\n");//更新头结点中记录的链表长度head->text.len++;return;
}//尾插法
int insertTail_linlist(linklist* head,dataType num)
{linklist* temp = (linklist*)malloc(sizeof(linklist));if(NULL == temp){printf("创建失败!\n");return 0;}//初始化新结点temp->next = NULL;temp->text.data = num;linklist* p = head;while(p->next != NULL){p = p->next;}p->next = temp;temp->next = NULL;head->text.len++;return 0;
}
//判空
int isEmpty_linlist(linklist* head)
{return head->next == NULL?1:0;
}//头删
dataType delHead_linlist(linklist* head)
{if(isEmpty_linlist(head)){printf("链表为空!");return (dataType)0;}linklist* temp = head->next;head->next = head->next->next;dataType num = temp->text.data;free(temp);temp = NULL;head->text.len--;return num;
}//尾删
dataType delTail_linlist(linklist* head)
{if(isEmpty_linlist(head)){printf("链表为空!");return (dataType)0;}linklist* p = head;linklist* temp;while(p->next != NULL) //p->next->next != NULL{temp = p;p = p->next;}temp->next=temp->next->next;free(p); //free(temp->next)p = NULL; //temp->next = NULLhead->text.len--;return 0;}//按位置插入
void insert_location_linlist(linklist *head,dataType index,dataType num)
{if(index<1 || index >head->text.len+1){printf("位置非法!");return;}int i;linklist* temp=head;linklist* p = (linklist*)malloc(sizeof(linklist));if(NULL == p){printf("插入失败!\n");return ;}//初始化新结点p->text.data = num;p->next = NULL;for(i=0;i<index-1;i++){temp = temp->next;}p->next = temp->next;temp->next = p;head->text.len++;return;}//按位置删除
void del_location_linlist(linklist* head,dataType index)
{if(isEmpty_linlist(head)){printf("链表为空!");return;}linklist* temp = head;for(int i=0;i<index-1;i++){temp = temp->next;}linklist* p = temp->next;temp->next = temp->next->next;free(p);p = NULL;head->text.len--;return;}//按位置查找
void find_location_linlist(linklist* head,dataType index)
{linklist* temp = head;for(int i=0;i<index;i++){temp = temp->next;}printf("%d\n",temp->text.data);head->text.len++;return;}//直接插入排序
void insert_sort_linlist(linklist* head,dataType num)
{linklist* p = head;int sum=0;while(p != NULL){sum++;p = p->next;}linklist* temp = head;for(int i=0;i<sum;i++){linklist* q = temp;while(q->next != NULL){if(q->text.data > q->next->text.data){int tem = q->text.data;q->text.data = q->next->text.data;q->next->text.data = tem;}q = q->next;}}int t=0;linklist* temp2 = head;for(int j=0;j<sum;j++){if(num > temp2->text.data){t++;}temp2 = temp2->next;}//按位置插入insert_location_linlist(head,t,num);}//链表翻转
void reversal_linlist(linklist* head)
{linklist *p;linklist *q;p=head->next;head->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=head->next;head->next=q;}
}
//快慢指针查找中间节点位置
void middleNode_linklist(linklist* head)
{if(isEmpty_linlist(head)){printf("链表为空!");return;} linklist *low,*fast;low = head->next;fast = head->next; while(fast != NULL && fast->next != NULL){low = low->next; fast = fast->next->next;}printf("low = %d\n",low->text.data);return;
} linklist.h
#ifndef __LINKLIDT_H__
#define __LINKLIDT_H__typedef int dataType;union msg{dataType data;int len;
};
typedef struct node
{struct node* next;union msg text;
}linklist;linklist* create_linklist(void);
int insertHead_linlist(linklist *head,dataType num);
void show_linklist(linklist* head);
int insertTail_linlist(linklist* head,dataType num);
dataType delHead_linlist(linklist* head);
dataType delTail_linlist(linklist* head);
void insert_location_linlist(linklist *head,dataType index,dataType num);
void del_location_linlist(linklist* head,dataType index);
void find_location_linlist(linklist* head,dataType index);
void insert_sort_linlist(linklist* head,dataType num);
void reversal_linlist(linklist* head);
void middleNode_linklist(linklist* head)
#endif
main.c
#include <stdio.h>
#include "./linklist.h"
int main(int argc, const char *argv[])
{linklist* head = create_linklist();insertHead_linlist(head,11);insertHead_linlist(head,24);insertHead_linlist(head,46);insertHead_linlist(head,28);insertHead_linlist(head,18);
// show_linklist(head);insertTail_linlist(head,36);insertTail_linlist(head,27);insertTail_linlist(head,30);show_linklist(head);/* dataType num = 0;num = delHead_linlist(head);show_linklist(head);num = delHead_linlist(head);show_linklist(head);num = delTail_linlist(head);show_linklist(head);num = delTail_linlist(head);show_linklist(head);
*/ /* insert_location_linlist(head,1,111);insert_location_linlist(head,5,555);insert_location_linlist(head,8,888);show_linklist(head);
*/
/* del_location_linlist(head,2);show_linklist(head);
*/
/* find_location_linlist(head,1);find_location_linlist(head,3);find_location_linlist(head,8);
*/insert_sort_linlist(head,22);show_linklist(head);reversal_linlist(head);show_linklist(head);middleNode_linklist(head)return 0;
}