数据结构链表

单链表的定义：

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表的几种操作

定义

typedef int datatype;
typedef struct link_node{
    datatype info;
    struct link_node *next;
}node;

初始化：

1.不带头节点

node *init(){
    return NULL;//不带头节点
}

2.带头节点

node *init()
{
    node *head;
    head=(node*)malloc(sizeof(node));
    head->next=NULL;
    return head;
}

输出所有元素：

node display(node *head){
    node *p;
    p=head;//如果是带头结点的那么p=head->next; 
    if(!p) printf("\n链表为空！\n");
    else{
        while(p){
            printf("%d ",p->info);
            p=p->next;
        }
    } 
}

查找

1.查找第i个结点,返回i的地址

node *find(node *head,int i)
{
    int j=1;
    node *p=head;
    while(p&&j!=i){//如果是查找值x，应该为p->info!=x;
        p=p->next;
        ++j;
    }
    return p;
}

插入

//在i后面插入一个元素x；
node *insert(node *head,datadype x;int i){
    node *p,*q;
    q=find(head,i);
    p=(node*)malloc(sizeof(node));
    p->info=x;
    if(i==0){
        p->next=head;
        head=p;
    }
    else {
        p->next=q->next;
        q->next=p;
    }
}

删除

node *dele(node *head,datatype x){
    node *pre=NULL;
    node *p;
    if(!head) printf("链表为空\n");
    p=head;//如果是带头结点，p=p->next;
    while(p&&p->info!=x){
        pre=p;p=p->next;
    }
    if(p){
        if(!pre) head=head->next;
        else pre->next=p->next;
        free(p);
    }
    return head;
}

反置链表

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

typedef int datatype;
typedef struct ListNode {
    datatype data;
    struct ListNode *next;
}node;

node *createlist(); /*单链表创建*/
node *reverse( node *head );
void printlist(node *head ); /*单链表输出*/

int main()
{
    node  *head;

    head = createlist();
    head = reverse(head);
    printlist(head);

    return 0;
}
node * createlist()
{
    node *head,*r,*s;
    datatype x;
    head=r=NULL;
    scanf("%d",&x);
    while (x!=-1) /*以-1结束输入*/
    {    s=(node *)malloc(sizeof(node));
         s->data=x;
         if (head==NULL)    /*将新结点插入到链表最后面*/
            head=s;
         else
            r->next=s;
        r=s;
        scanf("%d",&x);
   }
    if (r)  r->next=NULL;
    return head;                    /*返回建立的单链表*/
}

void printlist(node *head )
{
     node *p = head;
     if (p==NULL) printf("-1");
     else
        while (p) {
           printf("%d ", p->data);
           p = p->next;
        }
     printf("\n");
}
struct ListNode *reverse( struct ListNode *head )
{
struct ListNode *ptr=NULL,*ptr1=NULL;
while(head!=NULL)
{
    ptr=(struct ListNode *)malloc(sizeof(struct ListNode));
    ptr->data=head->data;
    ptr->next=ptr1;
    ptr1=ptr;
    head=head->next;
}
return ptr;
}

链表错题：

图片标题
图片说明

循环链表

将头结点和尾结点链接起来形成循环链表，无论从哪个结点开始寻找都能遍历到任何一个结点。

各种操作：

typedef int datatype;
typedef struct link_node{
    datatype info;
    struct link_node *next;
}node;
node *init(){
    return NULL;
}
//获得循环单链表的最后一个结点的储存地址
node *read(node *head){
    node *p;
    if(!head){
        p=NULL;
    } 
    else {
        p=head;
        while(p->next!=head){
            p=p->next;
        }
    }
    return p;
}

//展示链表的每一个元素
void  display(node *head){
    node *p;
    if(!head) prinf("空链表\n");
    else{
        printf("%d ",head->info);
        p=head->next;
        while(p!=head){
            printf("%d ",p->info);
            p=p->next;
        }
    }
}

//查找值为x的位置，并返回x所处的结点。
node *find(node *head,datatype x){
        node *p;
        if(!head) {
            printf("空链表\n");
            return NULL;
        }
        p=head;
        while(p!=head&&p->info!=x) p=p->next;
        if(p->info==x) return p;
        else return NULL;
}

//在循环单链表中第i个结点后插入一个值为x的新节点。
node *insert(node *head,datatype x,int i){
    node *p,*q,*myrear;
    int j;
    p=(node*)malloc(sizeof(node));
    p->info=x;
    if(i<=0) printf("无法插入元素\n");//错误
    if(i==0&&!head){
        p->next=p;//空链表
        head=p;
        return head;
    }
    if(i==0&&head){//插入成为头结点
        myrear=read(head);
        p->next=head;
        head=p;
        myrear->next=p;
        return head;
    }
    if(i>0&&!head) {
        printf("无法插入\n");
        free(p);
        return head;
    }//链表都为空，根本就不存在i>0时的结点。
    if(i>0&&head) {
        q=head;
        j==1;
        while(i!=j&&q->next!=head){
            q=q->next;
            j++;
        }
        if(i!=j) {
            printf("无指定位置可以插入\n");
            free(p);
            return head;
        }
        if(i==j){
            p->next=q->next;
            q->next=p;//插入
            return head;
        }
    }
}
//删除元素
node *dele(node *head,datatype x){
    node *p,*q;
    p=head;
    while(p->info!=x&&p->next!=head){
        q=p;
        p=p->next;
    }
    q->next=p->next;
    free(p);

}