线性表之单链表实现
- 实现单链表的初始化、插入、删除等基本运算
- 实现单链表的输入、输出运算
- 实现单链表的逆置、归并、排序等复杂运算
main.c
#include <stdio.h>
#include "Slist.h"
int main() {
printf("Hello, World!\n");
List mylist;
List yourlist,itlist;
InitList(&mylist);
ElemType Item;
int select =1;
while (select){
printf("************************************\n");
printf("* [1] push_back [2] push_front *\n");
printf("* [3] show_list [4] pop_back *\n");
printf("* [5] pop_front [6] insert_val *\n");
printf("* [7] find [8] length *\n");
printf("* [9] delete_val [10] sort *\n");
printf("* [11] resver [12] clear *\n");
printf("* [13] merge_list [0] exit system *\n");
printf("************************************\n");
printf("your selection:");
scanf("%d",&select);
if(select==0){
break;
}
switch (select){
case 1:
//push_back
printf("please input your linklist content (-1 to end) :");
while (scanf("%d",&Item),Item!=-1){
push_back(&mylist,Item);
}
break;
case 2:
// push_front
printf("please input your linklist content (-1 to end) :");
while (scanf("%d",&Item),Item!=-1){
push_front(&mylist,Item);
}
break;
case 3:
show_list(&mylist);
break;
case 4:
// pop_back
pop_back(&mylist);
break;
case 5:
// pop_front
pop_front(&mylist);
break;
case 6:
// insert_val
printf("please input the node value:");
scanf("%d",&Item);
insert_val(&mylist,Item);
break;
case 7:
// find
printf("please input the data to find:");
Node *p=NULL;//接收返回的node
scanf("%d",&Item);
p = find(&mylist,Item);
if (p==NULL){
printf("not find");
} else{
printf("date exist\n");
}
break;
case 8:
// length
printf("the LinkList length is : ");
int len=0;
len= length(&mylist);
printf("%d\n",len);
break;
case 9:
// delete_val
printf("please delete value:");
scanf("%d",&Item);
delete_val(&mylist,Item);
break;
case 10:
// sort
sort(&mylist);
break;
case 11:
// resver
resver(&mylist);
break;
case 12:
// clear
clear(&mylist);
break;
case 13:
InitList(&yourlist);
InitList(&itlist);
printf("now input your second list! ");
printf("please input your linklist content (-1 to end) :");
while (scanf("%d",&Item),Item!=-1){
push_back(&yourlist,Item);
}
printf("show your second list:\n");
show_list(&yourlist);
merge_list(&mylist,&yourlist,&itlist);
break;
default:
printf("selection not exist!\n");
break;
}
}
return 0;
}
SList.h
- 标示符常量的定义，单链表的存储类型描述和基本运算的声明
//
// Created by wenrou on 2019-09-16.
//
#ifndef SLIST_SLIST_H
#define SLIST_SLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define ElemType int
typedef struct Node{
ElemType data;
struct Node *next;
}Node,*PNode;
typedef struct List{
PNode first;
PNode last;
int size;
}List;
void InitList(List *list);
void push_back(List *list,ElemType item);
void push_front(List *list,ElemType item);
void show_list(List *list);
void pop_back(List *list);
void pop_front(List *list);
void insert_val(List *list,ElemType item);
Node* find(List *list,ElemType item);
int length(List *list);
void delete_val(List *list,ElemType item);
void sort(List *list);
void resver(List *list);
void clear(List *list);
void merge_list(List *list1,List *list2,List *list3);
#endif //SLIST_SLIST_H
SList.c
//
// Created by wenrou on 2019-09-16.
//
#include "Slist.h"
void InitList(List *list){
list->first=list->last=(Node *)malloc(sizeof(Node));
assert(list->first!=NULL);
list->first->next=NULL;
list->size=0;
}
void push_back(List *list,ElemType item){
Node *s = (Node *)malloc(sizeof(Node));
assert(s!=NULL);
s->data=item;
s->next=NULL;
list->last->next=s;
list->last=s;
list->size++;
}
void show_list(List *list){
Node *p = list->first->next;
while (p!=NULL){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void push_front(List *list,ElemType item){
Node *s = (Node *)malloc(sizeof(Node));
assert(s!=NULL);
s->data=item;
s->next=list->first->next;
list->first->next=s;
if(list->size==0){ //插入的是头结点,尾结点指向头结点，后续不变
list->last=s;
}
list->size++;
}
void pop_back(List *list){
if (list->size==0){
printf("LinkList is NULL");
}
Node *p = list->first;
while (p->next!=list->last){
p=p->next;
}
free(list->last);
list->last=p;
list->last->next=NULL;
list->size--;
}
void pop_front(List *list){
if(list->size==0){
printf("LinkList is NULL");
}
Node *p =list->first->next;
list->first->next=p->next;
free(p);
if(list->size==1){
list->last=list->first;
}
list->size--;
}
void insert_val(List *list,ElemType item){//假设 有序 递增
Node *s = (Node *)malloc(sizeof(Node));
assert(s!=NULL);
s->data=item;
s->next=NULL;
Node *p = list->first;
while (p !=NULL&&p->next->data<item){
p=p->next;
}
if(p->next==NULL){ //在最后插入 尾结点变动
list->last=s;
}
s->next=p->next;
p->next=s;
list->size++;
}
Node* find(List *list,ElemType item){
Node *p = list->first->next;
while (p!=NULL&&p->data!=item){
p=p->next;
}
return p;
}
int length(List *list){
return list->size;
}
void delete_val(List *list,ElemType item){
if(list->size==0){
printf("LinkList empty");
return;
}
Node *p = find(list,item);
if (p==NULL){
printf("data not exist");
return;
}
//删除p的后继
//若删除最后一个节点
if(p==list->last){
pop_back(list);
}else{
/*
* 1 2 3
* 2 的前继 循环 繁琐
* 思路：将 3 拷贝到 2 ，将3 删除
* */
Node *q = p->next;//3
p->data=q->data;//3 copy to 2
p->next=q->next;//2->4
free(q);//rm 3
list->size--;
}
}
void sort(List *list){
if(list->size==0||list->size==1){
return;
}
Node *s = list->first->next;
Node *q = s->next;
list->last=s;
list->last->next=NULL;
while (q!=NULL){
s=q;
q=q->next;
Node *p = list->first;
while (p->next !=NULL&&p->next->data<s->data){
p=p->next;
}
if(p->next==NULL){ //在最后插入 尾结点变动
list->last=s;
}
s->next=p->next;
p->next=s;
}
}
void resver(List *list){
if(list->size==0||list->size==1){
return;
}
//截取头插 逆置
Node *p=list->first->next;
Node *q=p->next;
list->last=p;
list->last->next=NULL;
/*
* (first)1(last) -- 2 3 4 5
*
* */
while (q!=NULL){
p=q;
q=p->next;
p->next=list->first->next;
list->first->next=p;
}
}
void clear(List *list){
if(list->size==0){
return;
}
Node *p = list->first->next;
while (p!=NULL){
list->first->next=p->next;
free(p);
p=list->first->next;
}
list->last=list->first;
list->size=0;
}
void merge_list(List *list1,List *list2,List *list3){
//归并
if(list1->size==0||list2->size==0){
return;
}
sort(list1);
sort(list2);
Node *p = list1->first;
Node *q = list2->first;
while (p->next!=NULL&&q->next!=NULL){
if(p->next->data<q->next->data){
push_back(list3,p->next->data);
p=p->next;
} else{
push_back(list3,q->next->data);
q=q->next;
}
}
while (p->next!=NULL){
push_back(list3,p->next->data);
p=p->next;
}
while (q->next!=NULL){
push_back(list3,q->next->data);
q=q->next;
}
printf("the gerge list is :");
show_list(list3);
}
执行结果
- 归并
当前已有链表1，再输入链表2，归并返回并显示为链表3
OVER
网友评论