数据结构 / day04 作业

1. 单链表任意位置删除, 单链表任意位置修改, 单链表任意位置查找, 单链表任意元素查找, 单链表任意元素修改, 单链表任意元素删除, 单链表逆置

// main.c#include "head.h"int main(int argc, const char *argv[])
{Linklist head=NULL; //head 是头指针// printf("head=%p\n", head);// printf("head->data=%d\n", head->data);// printf("head->next=%p\n", head->next);int n;int pos;int key;data_type element;printf("please input n:");scanf("%d", &n);for(int i=0; i<n; i++){printf("please input No.%d element: ", i+1);scanf("%d", &element);head=insert_head(element, head);}puts("---ouput Linklist---");output(head);/*puts("---get tail node---");Linklist node_tail = get_tail_node(head);printf("tail->data=%d\n", node_tail->data);puts("---append element---");printf("please input element to append:");scanf("%d", &element);head=append(head, element);output(head);puts("---delete first node---");head=delete_first(head);head=delete_first(head);output(head);puts("---delete tail node---");head=delete_tail(head);head=delete_tail(head);output(head);puts("---get list len---");int len=get_len(head);printf("len=%d\n", len);puts("---insert_by_pos---");int pos;printf("please input pos: ");scanf("%d", &pos);printf("please input element: ");scanf("%d", &element);head=insert_by_pos(head, pos, element);output(head);puts("---get node by pos---");printf("please input pos:");scanf("%d", &pos);Linklist node  = get_node_by_pos(head, pos);printf("node->data=%d\n", node->data);*/puts("---delete node by pos---");printf("please input pos:");scanf("%d", &pos);head = delete_by_pos(head, pos);output(head);puts("---update node by pos---");printf("please input pos:");scanf("%d", &pos);printf("please element:");scanf("%d", &element);int ret = update_by_pos(head, pos, element);output(head);puts("---get node by element---");printf("please element:");scanf("%d", &element);pos = get_node_by_element(head, element);printf("pos=%d\n",pos);
//puts("---update node by element---");printf("please input a key:");scanf("%d", &key);printf("please input an element:");scanf("%d", &element);ret = update_node_by_element(head, key, element);output(head);
//puts("---delete by element---");printf("please input element:");scanf("%d", &element);head = delete_node_by_element(head, element);output(head);//puts("---reverse list---");head = revser_list(head);output(head);
//return 0;
}

//head.h#ifndef __HEAD_H__
#define __HEAD_H__#include <string.h>
#include <stdlib.h>
#include <stdio.h>typedef int data_type;typedef struct Node
{int data;struct Node *next;}*Linklist;Linklist create();typedef struct Node node;Linklist create_node();
Linklist insert_head(data_type data, Linklist head);
int output(Linklist head);
Linklist append(Linklist head, data_type element);
Linklist get_tail_node(Linklist head);
Linklist delete_first(Linklist head);
Linklist free_node(Linklist node);
Linklist delete_tail(Linklist head);
int get_len(Linklist head);
Linklist insert_by_pos(Linklist head, int pos, data_type element);
Linklist delete_by_pos(Linklist head, int pos);
Linklist get_node_by_pos(Linklist head, int pos);
int update_by_pos(Linklist head, int pos, data_type element);
int get_node_by_element(Linklist head, data_type key);
Linklist delete_node_by_element(Linklist head, data_type key);
Linklist revser_list(Linklist head);
int update_node_by_element(Linklist head, data_type key, data_type element);
#endif

//test.c#include "head.h"Linklist create_node()
{Linklist node=(Linklist)malloc(sizeof(struct Node));if(NULL==node){return NULL;}//successnode->data=0;node->next=NULL;return node;
}Linklist insert_head(data_type element, Linklist head)
{//创建新节点Linklist node = create_node();if(NULL==node){return head;}node->data=element;//判断链表是否位空if(NULL==head){head=node;}else //链表不为空{node->next=head;head=node;		}return head;// 这里的head是形参，所以需要返回用以改变主函数的head
}int output(Linklist head)
{if(NULL==head){return -1;}Linklist node = head;while(node!=NULL){//printf("data=%d, next=%p\t", node->data, node->next);printf("%d\t", node->data);node=node->next;}putchar(10);}Linklist get_tail_node(Linklist head)
{Linklist node=head;while(node->next!=NULL && node!=NULL){node=node->next;}return node;}Linklist append(Linklist head, data_type element)
{//Linklist node = create_node();if(NULL==node){return head;}node->data=element;node->next=NULL;Linklist node_tail=get_tail_node(head);if(NULL==node_tail){head = node;}node_tail->next = node;	return	head;}Linklist free_node(Linklist node)
{free(node);node=NULL;return node;}Linklist delete_first(Linklist head)
{if(NULL==head){return head;}Linklist node_deleted = head;head=head->next;node_deleted = free_node(node_deleted);return head;}Linklist delete_tail(Linklist head)
{if(NULL==head){return head;}//找到 tail 之前的nodeLinklist node = head;if(node->next==NULL){head=free_node(node);return head;}while(NULL!=node->next->next){node=node->next;}node->next=free_node(node->next);node->next=NULL;return head;
}int get_len(Linklist head)
{//puts("in get_len");int count=0;Linklist node=head;while(node!=NULL){//printf("len=%d\n", len);count++;node=node->next;}return count;}Linklist insert_by_pos(Linklist head, int pos, data_type element)
{//pos, Linklist pos start from 1 hearint len=get_len(head);if(pos<1 || pos>len+1){return head;}if(NULL==head || pos==1)head=insert_head(element, head);else{//find node at posLinklist node=head;for(int i=1; i<pos-1; i++){node=node->next;}printf("node(pos-1)->data=%d", node->data);//create new nodeLinklist node_new= create_node();if(NULL==node_new){return head;}node_new->data=element;//insert node_new->next=node->next;node->next=node_new;}return head;
}Linklist get_node_by_pos(Linklist head,int pos)
{if(NULL==head){return head;}int len=get_len(head);if(pos<1||pos>len){return NULL;}Linklist node=head;int count=1;while(count<pos){count++;node=node->next;}return node;}Linklist delete_by_pos(Linklist head,int pos)
{//note: list pos start from 1if(NULL==head){return head;}//判断pos合法int len=get_len(head);if(pos<1 && pos>len) {return head;}if(1==len || 1==pos){head=delete_first(head);}else{Linklist node = get_node_by_pos(head, pos-1);//deleteLinklist node_tbd = node->next;node->next=node->next->next;free_node(node_tbd);node_tbd=NULL;}return head;}int update_by_pos(Linklist head, int pos, data_type element)
{if(NULL==head){return -1;}Linklist node = get_node_by_pos(head, pos);if(NULL==node)return -1;node->data=element;return 0;}int get_node_by_element(Linklist head, data_type key)
{//找到返回pos信息if(NULL==head){return -1;}int count=0;int is_found=0;Linklist node=head;while(NULL!=node){//printf("node->data=%d\n", node->data);count++;if(node->data==key){is_found=1;break;}node=node->next;}if(is_found==1){return count;}else{return -1;}
}Linklist delete_node_by_element(Linklist head, data_type key)
{if(NULL==head){return head;}int pos = get_node_by_element(head, key);if(-1==pos){return head;}head=delete_by_pos(head, pos);return head;}Linklist revser_list(Linklist head)
{if(NULL==head||NULL==head->next){return head;}Linklist node=head->next;head->next=NULL;while(NULL!=node){Linklist node_t=node;node=node->next;node_t->next=head;head=node_t;}return head;
}int update_node_by_element(Linklist head, data_type key, data_type element)
{if(NULL==head){return -1;}int pos=get_node_by_element(head, key);if(-1==pos){return -1;}int ret=update_by_pos(head, pos, element);return ret;}

运行结果

please input n:7
please input No.1 element: 1
please input No.2 element: 2
please input No.3 element: 3
please input No.4 element: 4
please input No.5 element: 5
please input No.6 element: 6
please input No.7 element: 7
---ouput Linklist---
7	6	5	4	3	2	1	
---delete node by pos---
please input pos:1
6	5	4	3	2	1	
---update node by pos---
please input pos:2
please element:500
6	500	4	3	2	1	
---get node by element---
please element:4
pos=3
---update node by element---
please input a key:4
please input an element:400
6	500	400	3	2	1	
---delete by element---
please input element:2
6	500	400	3	1	
---reverse list---
1	3	400	500	6	

2.思维导图