链表C/C++实现大全

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <conio.h>
using namespace std;

typedef struct student
{
	int data;
	struct student *next;
}node;

/* 链表的创建*/
node *creat()
{
	node *head,*p,*s;
	int x;
	int cycle=1;
	head=(node*)malloc(sizeof(node));
	p=head;
	while(cycle)
	{
		cout<<"please enter a number"<<endl;
		cin>>x;
		if(x!=0)
		{
			s=(node*)malloc(sizeof(node));
			s->data=x;
			p->next=s;
			p=s;
		}
		else
			cycle=0;
	}
	head=head->next;
	p->next=NULL;
	return (head);
}

/*链表的测长*/        
int length(node *head)
{
	int n=0;
	node *p;
	p=head;
	while(p!=NULL)
	{
	    p=p->next;
			n++;
	}
	return n;


}  
  
/*链表的排序*/  

node *sort(node* head, int n)
{
	int i;
	int j;
	int temp;
	node *p;
	if(head==NULL||head->next==NULL)
		return (head);
	p=head;
	for(i=1;i<n;i++)
	{
		p=head;
		for(j=0;j<n-i;j++)
		{
			if(p->data>p->next->data)
			{
				temp=p->next->data;
				p->next->data=p->data;
				p->data=temp;
			}
			p=p->next;
		}

	}
	return (head);


} 
               
/*链表的逆置*/ 
node *reverse(node* head)
{
	node *p1;
	node *p2;
	node *p3;
	if(head==NULL||head->next==NULL)
		return head;
	p1=head;
	p2=p1->next;
	while(p2)
	{
		p3=p2->next;
		p2->next=p1;
		p1=p2;
		p2=p3;
	}
	head->next=NULL;
	head=p1;
	return head;
}                    

/*链表插入一个节点*/  

node *insert(node* head,int num)
{
	node *p0,*p1,*p2;
	p1=head;
	p0=(node*)malloc(sizeof(node));
	p0->data=num;
	while((p0->data)>(p1->data)&&p1->next!=NULL)
	{
		p2=p1;
		p1=p1->next;
	}
	if(p0->data<=p1->data)
	{
          if(head==p1)                                      //插入的是头结点
		  {
			  p0->next=p1;
			  head=p0;
		  }
		  else 
		  {
			  p2->next=p0;                                  //插入的是中间结点
			  p0->next=p1;
		  }
	}
	else                                                    //插入的是尾结点
	{
		p1->next=p0;
		p0->next=NULL;
	}
return (head);
}                                                      

/*链表删除一个节点*/               
node *del(node* head,int num)
{
	node *p1,*p2;
	p1=head;
	while(num!=p1->data&&p1->next!=NULL)
	{
		p2=p1;
		p1=p1->next;
	}
	if(num==p1->data)
	{
		if(head==p1)
		{
			head=p1->next;
			free(p1);
		}
		else 
			p2->next=p1->next;
	}
else 
cout<<num<<"couldn't be found"<<endl;
return (head);
}
                                               

void main()
{
	node *p;
	node *head;
	int n;
    head=(node*)malloc(sizeof(node));
	head=creat();
	n=length(head);
	p=head;
	cout<<"原始链表是:";
	if(head!=NULL)                                                 //原始链表的打印
		while(p!=NULL)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;

		head=reverse(head);
     	p=head;
		cout<<"链表长度为:"<<n;
/**************************************************************/  

    	cout<<"逆置后链表是:";
    	if(head!=NULL)                                                 //逆置后链表的打印
		while(p!=NULL)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;  
/**************************************************************/  

		head=sort(head,n);
		p=head;
		cout<<"排序后链表:";
        if(head!=NULL)                                                 //排序后链表的打印
		while(p!=NULL)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl; 
 /**************************************************************/    
		int a;
		cout<<"insert a number:"<<endl;
		cin>>a;
		head=insert(head,a);
		p=head;
		cout<<"插入后链表是:";
	     if(head!=NULL)                                                 //插入后链表的打印
		while(p!=NULL)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;
/**************************************************************/	
		int b;
		cout<<"delete number:"<<endl;
		cin>>b;
        head=del(head,b);
		p=head;
		cout<<"删除后链表是:";
	     if(head!=NULL)                                                 //删除后链表的打印
		while(p!=NULL)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;                             

}

我自己完全用C语言版本的实现:

list.h

typedef struct ListNode
{
    int val;
    struct ListNode *next;
} Node;

Node *list_init(void); //构建头节点head值为-1的单链表
void list_exit(Node **head);
int list_is_empty(Node *head);
void list_print(Node *head);
int list_size(Node *head);
Node *list_insert(Node *head, int n, int val); //在第n个节点之后插入
int list_delete(Node *head, int n);            //删除第n个节点
int list_delete_val(Node *head, int val);      //删除链表中值为val的第一个节点
int list_find(Node *head, int val);            //查找链表中第一个节点值为val的节点位置
Node *list_local_reverse(Node *head, int L, int R);  //局部反转链表第L个到第R个节点
Node *list_reverse(Node *head);  //链表反转

list.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int main(void)
{
    Node *head = list_init();
    list_print(head);
    printf("list size = %d\n", list_size(head));

    list_insert(head, 0, 5);
    list_print(head);
    printf("list size = %d\n", list_size(head));

    list_insert(head, list_size(head), 15);
    list_print(head);
    printf("list size = %d\n", list_size(head));

    list_reverse(head);
    list_print(head);
    printf("list size = %d\n", list_size(head));

    list_delete(head, 1);
    list_print(head);
    list_delete(head, list_size(head));
    list_print(head);
    list_delete(head, 3);
    list_print(head);
    printf("list size = %d\n", list_size(head));

    printf("find -1 in = %d\n", list_find(head, -1));
    printf("find 5 in = %d\n", list_find(head, 5));

    list_local_reverse(head, 1, 3);
    list_print(head);
    printf("list size = %d\n", list_size(head));

    list_deinit(&head);
    list_print(head);
    list_size(head);
    printf("list size = %d\n", list_size(head));
    return 0;
}

Node *list_init(void)
{
    Node *head = (Node *)malloc(sizeof(Node));
    Node *p1 = (Node *)malloc(sizeof(Node));
    Node *p2 = (Node *)malloc(sizeof(Node));
    Node *p3 = (Node *)malloc(sizeof(Node));
    Node *p4 = (Node *)malloc(sizeof(Node));
    Node *p5 = (Node *)malloc(sizeof(Node));
    head->val = -1;
    p1->val = 11;
    p2->val = 5;
    p3->val = 7;
    p4->val = 10;
    p5->val = 1;
    head->next = p1;
    p1->next = p2;
    p2->next = p3;
    p3->next = p4;
    p4->next = p5;
    p5->next = NULL;
    return head;
}

void list_exit(Node **head)
{
    while (*head)
    {
        Node** tmp = head;
        *head = (*head)->next;
        free(*tmp);
        *tmp = NULL;
    }
}

int list_is_empty(Node *head){
    return (!head || !head->next) ? 1 : 0;
}

void list_print(Node *head)
{
    int first = 1;
    while (head)
    {
        if (first)
        {
            first = 0;
            printf("head->");
        }
        else
        {
            printf("(%d)->", head->val);
        }
        head = head->next;
    }
    printf("NULL\n");
}

int list_size(Node *head)
{
    int len = 0;
    if (!head)
        return len;
    head = head->next;

    while (head)
    {
        len++;
        head = head->next;
    }
    return len;
}

Node *list_insert(Node *head, int n, int val)
{
    if (n < 0 || n > list_size(head))
        return NULL;
    while (n--)
    {
        head = head->next;
    }
    Node *tmp = (Node *)malloc(sizeof(Node *));
    tmp->val = val;
    tmp->next = head->next;
    head->next = tmp;
    return tmp;
}

int list_delete(Node *head, int n)
{
    if (n < 1 || n > list_size(head))
        return -1;
    while (--n)
    {
        head = head->next;
    }
    Node *tmp = head->next;
    head->next = head->next->next;
    free(tmp);
    tmp = NULL;
    return 0;
}

int list_delete_val(Node *head, int val)
{
    list_delete(head, list_find(head, val));
}

int list_find(Node *head, int val)
{
    head = head->next;
    int ans = 1;
    while (head)
    {
        if (head->val == val)
            return ans;
        head = head->next;
        ans++;
    }
    return -1;
}

Node *list_local_reverse(Node *head, int L, int R)
{  
    if (!head || !head->next || R <= L || L < 1 || R > list_size(head))
        return NULL;
    int t = L;
    while (--t){
        head = head->next;
    }
    Node *h = head;
    head = head->next;
    Node *p = head;
    Node *q = head->next;
    Node *tmp = NULL;
    p->next = NULL;
    int flag = 1;
    while (flag != R - L + 1)
    {
        tmp = q->next;
        q->next = p;
        p = q;
        q = tmp;
        flag++;
    }
    h->next->next = tmp;
    h->next = p;
    return h;
}

Node *list_reverse(Node *head){
    return list_local_reverse(head, 1, list_size(head));
}
上一篇:Python中的反射


下一篇:从Java视角理解CPU缓存(CPU Cache)