链表(上)----单向链表(跑路人笔记)

动态顺序表在头部中部插入数据时和扩容时总会产生一些资源的浪费或性能的浪费所以我们可以用链表进行代替.

(顺序表自然也有其优势从不同方面讲总是各有各优点的)

链表优点

1. 空间上,按需求给空间(不会造成空间的浪费
2. 不要求物理空间连续头部中部插入时不需要挪动数据.

链表

链表是通过结构题创建的一种物理储存结构上非连续的,非顺序的存储结构链表之间的连接是通过指针进行次序连接实现的.

Slistnode.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint SLTdatetype;//为了方便未来更改存储数据structSListNode{
    SLTdatetype date;structSListNode* next;};//单向链表的类型typedefstructSListNode SListNode;//方便使用 单向链表类型// 单链表打印voidSListPrint(SListNode* plist);// 单链表尾插voidSListPushBack(SListNode** pplist, SLTdatetype x);// 单链表的头插voidSListPushFront(SListNode** pplist, SLTdatetype x);// 单链表的尾删voidSListPopBack(SListNode** pplist);// 单链表头删voidSListPopFront(SListNode** pplist);// 单链表查找
SListNode*SListFind(SListNode* plist, SLTdatetype x);// 单链表在pos位置之前插入xvoidSListInsert(SListNode** pplist, SListNode* pos, SLTdatetype x);// 单链表删除pos位置的值voidSListErase(SListNode** pplist, SListNode* pos);

Slistnode.c

#include"work.h"//对链表进行打印voidSListPrint(SListNode* plist){
    SListNode* cur = plist;while(cur !=NULL){printf("%d->", cur->date);
        cur = cur->next;}printf("NULL\n");}

SListNode*BuyNode()//开辟一块新空间{
    SListNode* newnode =malloc(sizeof(SListNode));//新的要插入的区域块if(newnode ==NULL)//防止malloc开辟空间失败{perror("BuyNode");returnNULL;}return newnode;}//尾部插入代码实现voidSListPushBack(SListNode** pplist, SLTdatetype x){
    SListNode* newnode =BuyNode();//得到新空间//初始化数据
    newnode->date = x;
    newnode->next =NULL;//尾插开始if(*pplist ==NULL)//如果*pplist为空指针后面的tail也将为空指针而->是有解引用的作用的我们对空指针的解引用是违法行为{*pplist = newnode;}else{
        SListNode* tail =*pplist;while(tail->next !=NULL)//让tail指向未增容时的链表尾部{
            tail = tail->next;}
        tail->next = newnode;}}//头部插入代码实现voidSListPushFront(SListNode** pplist, SLTdatetype x){
    SListNode* newnode =BuyNode();//得空间
    newnode->date = x;
    newnode->next =*pplist;*pplist = newnode;}//链表尾删实现voidSListPopBack(SListNode** pplist){assert(*pplist);if((*pplist)->next ==NULL){free(*pplist);*pplist =NULL;}else{
        SListNode* tail =*pplist;
        SListNode* prev =*pplist;while(tail->next !=NULL)//让tail指向未增容时的链表尾部{
            prev = tail;
            tail = tail->next;}
        prev->next =NULL;free(tail);}}voidSListPopFront(SListNode** pplist){assert(*pplist);
    SListNode* next =(*pplist)->next;free(*pplist);*pplist = next;}//链表查找实现
SListNode*SListFind(SListNode* plist, SLTdatetype x)//辅助性的功能函数{while(plist !=NULL){if(plist->date == x){return plist;}
        plist = plist->next;}returnNULL;}//定点插入实现pos前插入voidSListInsert(SListNode** pplist, SListNode* pos, SLTdatetype x){if(pos ==*pplist)//如果要定点插入的在头部就和头插一样直接使用头插就好{SListPushFront(pplist, x);}//使用下面else的方式找pos前一位是无法定位到开头的所以需要这个分支else{
        SListNode* newnode =BuyNode();//创建新空间
        newnode->date = x;
        SListNode* prve =*pplist;//寻找pos的前一位while(prve->next != pos){
            prve = prve->next;}//数据处理
        prve->next = newnode;
        newnode->next = pos;}}voidSListErase(SListNode** pplist, SListNode* pos){if(pos ==*pplist){SListPopFront(pplist);}//使用下面else的方式找pos前一位是无法定位到开头的所以需要这个分支else{
        SListNode* prve =*pplist;//寻找pos的前一位while(prve->next != pos){
            prve = prve->next;}
        prve->next = pos->next;free(pos);}}

main.c

#include"work.h"voidTestSList(){
    SListNode* plist =NULL;//用于保存链表头部的地址SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushFront(&plist,0);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);SListPrint(plist);}voidTestSList2(){
    SListNode* plist =NULL;//用于保存链表头部的地址SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushBack(&plist,3);SListPushBack(&plist,4);
    SListNode* pos =SListFind(plist,1);if(pos !=NULL){SListInsert(&plist, pos,50);}SListPrint(plist);}voidTestSList3(){
    SListNode* plist =NULL;//用于保存链表头部的地址SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushBack(&plist,3);SListPushBack(&plist,4);
    SListNode* pos =SListFind(plist,1);if(pos !=NULL){SListErase(&plist, pos);}SListPrint(plist);}intmain(){TestSList3();return0;}

结尾

未来还会有双向链表的实现和习题的练习.如果对你有帮助请帮舒文点个赞和收藏谢谢谢谢.