CPJ Linux Dev Engineer

3-1-1-1单链表

2017-08-16
phone

WELCOME TO READ ME

关键记忆

#include <stdio.h>
typedef   char  datatype;
typedef   struct    node{
    datatype      data;
    struct  node  *next;
} listnode;
typedef  listnode  *linklist;
listnode  *p;  

一 新建单链表 01:头插法建立单链表

linklist  createlist(void)
{
    ¦ char ch; 
    ¦ linklist  head;
    ¦ listnode  *p; 
    ¦ head=NULL;/*初始化为空*/
    ¦ ch=getchar( );
    ¦ while (ch!='\n'){
    ¦   ¦  p=(listnode*)malloc(sizeof(listnode));/*分配空间*/
    ¦   ¦  p->data=ch;/*数据域赋值*/
    ¦   ¦  p->next=head;/*指定后继指针*/
        ¦  head=p;/*head指针指定到新插入的结点上*/
    ¦   ¦  ch=getchar( );
    ¦ } 
    ¦ return (head);
}

02:尾插法建立单链表

linklist  creater()
{
    char  ch; 
    linklist  head;
    listnode  *p,*r;
    head=NULL;
    r=NULL;/*r为尾指针*/
    while((ch=getchar())!='\n'){
    ¦   p=(listnode *)malloc(sizeof(listnode));
    ¦   p->data=ch;
    ¦   if(head==NULL)
    ¦   ¦   head=p;/*head 指向第一个插入结点*/
    ¦   else
            r->next=p;/*插入到链表尾部*/
    ¦   r=p;/*r指向最新结点,即最后结点*/
    ¦}  
    ¦if (r!=NULL)
    ¦   ¦ r->next=NULL;/*链表尾部结点的后继指针指定为空*/
    ¦return(head);
 } 

03:限制链表长度建立单链表

linklist  createlist(int n)
{
    int i;
    linklist  head;
    listnode *p; 
    head=NULL;
    for(i=n;i>0;--i)/*指定长度为n,插入次数受限制*/
    {   
        p=(listnode*)malloc(sizeof(listnode));
    ¦   scanf("%c",&p->data);
    ¦   p->next=head;
    ¦   head=p;
    }   
    return(head);
}

二 查找元素 01:按序号查找单链表

listnode * getnode(linklist head,int i)
{            
    ¦int j;
    ¦listnode * p;
    ¦p=head;
    ¦   ¦j=0;
    ¦while(p->next && j<i){/*遍历第i个结点前的所有结点*/
    ¦   ¦  p=p->next;
    ¦   ¦  j++;
    ¦}  
    ¦if (i==j)
    ¦{  
    ¦   ¦printf("%c\n",p->data);
    ¦   ¦return p;
    ¦}  
    ¦else
    ¦   ¦return NULL;
}

02:按值查找单链表

listnode * locatenode(linklist head,char key)
{                                 
    listnode * p=head;
    while( p->next&& p->data!=key)
    ¦   p=p->next;
    if(p!=NULL)
    ¦   printf("%c\n",p->data);
    return p;
}

三 插入某项

void  insertnode(linklist  head,char x,int i)
{
    int j=0;
    listnode  * p,*s;
    p=head;
    while(p&&j<i-1){              
        p=p->next;
        ++j;
    }   
    if(!p||j>i-1)
        exit(1);
    s=(linklist)malloc(sizeof(listnode));
    s->data=x;
    s->next=p->next;
    p->next=s;
}

四 删除链表

void  deletelist(linklist head,int i)
{
int j=0;
    listnode * p,*r;
    p=head;
    while(p&&j<i-1){
        p=p->next;
        ++j;
    }   
    if(!p->next||j>i-1)
    ¦   exit(1);
    r=p->next;
    p->next=r->next;
    free(r) ;
}

五 归并两个单链表

linklist  concatenate(linklist list1,linklist list2)
{                                 
    listnode *temp;
    if (list1==NULL)
        return list2;
    else {
    ¦   if (list2!=NULL) {
    ¦   ¦   for ( temp =list1; temp->next; temp = temp->next )
                ; /*遍历到list1的末尾*/
    ¦   ¦   temp->next=list2;/*将list2链接到list1末尾*/
    ¦   }   
    }   
    return list1;
}

六 链表反转

void list_reverse(node_ptr L)  
{  
    if (L->next == NULL) return;  
    node_ptr p = L->next, first = L->next;  
    while (p != NULL && p->next != NULL) {  
           node_ptr next_node = p->next;  
           p->next = next_node->next;  
           next_node->next = first;  
           first = next_node;  
        }  
    L->next = first;  
}

Similar Posts

Comments