关于单链表的一些小结

链表算是C语言中比较重要一个知识点了,之前学习时粗略的学过链表,这次回过头来回顾一下

首先是链表的前置知识结构体和指针,链表就是一个结构体内有一个指向本类型的指针,这样一个一个串起来形成逻辑上的连续存储.

(里面有少许c++语法,可以自行替换成c语法)

#define Sfault 0
#define Strue  1


typedef char NodeDataC;
typedef int  NodeDataI;
typedef struct NodeLink
{
    NodeDataC *name;
NodeDataI id;
struct NodeLink * next;
}Node;


//头插法
int Head_insert(Node * h,NodeDataI Serial_number, NodeDataC * pszname)
{
    Node * node = (Node*)malloc(sizeof(Node)/sizeof(char));
if(node == NULL)
return Sfault;
node->name = pszname;
node->id   = Serial_number;
    
node->next = h->next;
h->next    = node;
    return Strue;
}


//遍历链表,打印数据
int Traverse_Link(Node* h)
{
Node* tmp = h->next;
while(tmp)
{
         cout << tmp->id << "  " << tmp->name << endl; 
         tmp  = tmp->next;
}
return Strue;
    
}


//尾插法
int Tail_insert(Node* h,NodeDataI Serial_number, NodeDataC * pszname)
{
    Node* node = (Node*)malloc(sizeof(Node)/sizeof(char));
if(node == NULL)
return Sfault;
node->next = NULL;


    Node* tmp = h;
while(tmp->next)
{
tmp   = tmp->next;
}
node->id  = Serial_number;
node->name = pszname;
tmp->next = node;
return Strue;
}


//删除第pos个结点
int Delete_pos(Node* h,int pos)
{
    Node* tmp = h;
for(int i = 0;i < pos - 1;i++)
{
if(tmp->next != NULL)
{
tmp = tmp->next;
}
}
Node* p = tmp->next;
tmp->next = p->next;
free(p);
return Strue;
}


//链表逆序
int Reverse_List(Node* h)
{
Node* pre = h->next;
Node* cur = h->next->next;
Node* tmp;
while(cur)
{
        tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
h->next->next = NULL;
h->next = pre;
return Strue;
}


int main()
{
Node * h = (Node *)malloc(sizeof(Node)/sizeof(char));
h->next = NULL;
        Head_insert(h,3,"xin");
Head_insert(h,2,"jia");
        Head_insert(h,1,"li");
        Tail_insert(h,4,"ni");
        Tail_insert(h,5,"hao");
Tail_insert(h,6,"a");
        // Delete_pos( h,4);
        Traverse_Link(h);
        Reverse_List(h);
Traverse_Link(h);
return 0;
}

这里讲下思路

首先是头插法思路:(头插法是最简单的插入方法,不过头插法插入的数据是反的)

①先malloc一个节点空间,判断是否成功

②向新节点写入数据,注意新节点node->next = h->next

③h->next=node

尾插法思路:

①先malloc一个节点空间判断是否成功

②创一个结构体指针Node*tmp=h,当tmp->next存在时tmp=tmp->next(一步一步将tmp向后移直到tmp->next=NULL)

③向新节点写入数据.注意,由于是尾插法,所以node->next=NULL

④tmp->next=node

删除第pos个结点思路:

①创建一个结构体指针tmp指向h,用来指向要删除位置的前一个结点

②循环向后移寻找结点,直到pos-1的位置

③创建一个结构体指针p指向tmp->next,这时p就是要删除的第pos个结点

④tmp->next=p->next

⑤free(p)

链表逆序思路:

①判断传进来的链表是否有两个以上的结点(如果节点数小于两个,就没必要逆序)

②创建三个结构体指针pre,cur,tmp,   pre=h->next,cur= h->next->next

③判断cur的存在,即当cur不为NULL时,可以进入循环 tmp =cur->next,就算cur是链表的最后一个节点也无所谓,这时cur->next=NULL及tmp=NULL

④逆序 cur->next=pre

⑤循环后移交换三个变量pre=cur,cur=tmp

⑥将逆序前的第一个节点的next指向NULL,h->next->next=NULL

⑦将h指向pre,h->next=pre

逆序图示: